共享内存
共享内存（shared memory）指在多处理器的计算机系统中，可以被不同中央处理器访问的大容量内存。由于多个CPU需要快速访问存储器，这样就要对存储器进行缓存。由于其他处理器可能也要存取，任一缓存数据更新后，共享内存就需要立即更新，否则不同处理器可能用到不同的数据（参见缓存一致和内存一致）。 共享内存的类似方案有分布内存、分布共享内存，用以解决同类问题。 软件术语 在软件中，共享内存指可被多个进程存取的内存，一个进程是一段程序的单个…
标签：#并发控制
共 40 篇文章
互斥锁
互斥锁（，缩写 Mutex）是一种用于多线程编程中，防止两条线程同时对同一公共资源（比如全域變數）进行读写的机制。该目的通过将代码切片成一个一个的临界区域（critical section）达成。临界区域指的是一块对公共资源进行存取的代码，并非一种机制或是算法。一个程序、进程、线程可以拥有多个临界区域，但是并不一定会应用互斥锁。 需要此机制的资源的例子有：旗标、队列、计数器、中断处理程序等用于在多条并行运行的代码间传递数据、同步状态等的…
消息队列
在计算机科学中，消息队列（）是一种进程间通信或同一进程的不同线程间的通信方式，軟體的貯列用來處理一系列的輸入，通常是來自使用者。消息队列提供了异步的通信协议，每一個貯列中的紀錄包含詳細說明的資料，包含發生的時間，輸入裝置的種類，以及特定的輸入參數，也就是说：消息的发送者和接收者不需要同时与消息队列交互。消息会保存在队列中，直到接收者取回它。 一個 WIMP 環境像是 Microsoft Windows，藉由優先的某些形式（通常是事件的時…
信号量
信号量（）又稱為-{zh-cn:信号标; zh-tw:旗號; zh-hk:訊號標;}-，是一个同步对象，用于保持在0至指定最大值之间的一个计数值。当线程完成一次对该对象的等待（）时，该计数值减一；当线程完成一次对对象的释放（）时，计数值加一。当计数值为0，则线程等待该对象不再能成功直至该对象变成状态。对象的计数值大于0，为状态；计数值等于0，为状态。 信号量的概念是由荷兰计算机科学家艾兹赫尔·戴克斯特拉（）发明的，广泛的应用于不同的操作…
異步I/O
异步I/O是计算机操作系统对输入输出的一种处理方式：发起I/O请求的线程不等I/O操作完成，就继续执行随后的代码，I/O结果用其他方式通知发起I/O请求的程序。与异步I/O相对的是更为常见的“同步（阻塞）I/O”：发起I/O请求的线程不从正在调用的I/O操作函数返回（即被阻塞），直至I/O操作完成。 类Unix操作系统与POSIX POSIX提供下述API函数： aio io_uring (Linux 5.1以後支援) Windows操…
臨界區段
在同步的程式設計中，臨界區段（）或稱為关键区段 ，指的是一個存取共用資源（例如：共用裝置或是共用記憶體）的程式片段，而這些共用資源又無法同時被多個執行緒存取的特性。 當有執行緒進入臨界區段時，其他執行緒或是行程必須等待（例如：bounded waiting 等待法），有一些同步的機制必須在臨界區段的進入點與離開點實現，以確保這些共用資源是被互斥或的使用，例如：semaphore。 只能被單一執行緒存取的裝置，例如：印表機。 一個最簡單的…
优先转置
優先權倒置，又称優先權反轉、優先權逆轉、優先權翻轉，是一种不希望发生的任务调度状态。在该种状态下，一个高优先级任务间接被一个低优先级任务所抢先(preempted)，使得两个任务的相对优先级被倒置。 这往往出现在一个高优先级任务等待访问一个被低优先级任务正在使用的临界资源，从而阻塞了高优先级任务；同时，该低优先级任务被一个次高优先级的任务所抢先，从而无法及时地释放该临界资源。这种情况下，该次高优先级任务获得执行权。 在多數個案，發生優先…
事件 (同步原语)
事件作为一种同步原语，是计算机科学中的一种同步机制，用来指示等待中的进程特定条件已经变为真。 事件对象一般具有下述操作： wait - 执行中的线程被挂起直到事件为真。如果执行wait时事件已为真，则空操作。 set - 设置事件状态为真，所有等待此事件的进程变为可调度。 clear - 设置事件状态为假。 事件类似于管程中的条件变量。 Windows系统 Microsoft Windows操作系统提供的事件内核对象，状态为signal…
比较并交换
比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。 该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。 概述 一个CAS操作等价于以下c代码的原子实现: int cas(long addr, long old, long new) { / …
可等待定时器
可等待定时器对象是Windows操作系统的一种同步对象，当设定的期限到了时，对象被置为signaled状态。 可创建两种可等待定时器对象： 手工重置（manual-reset）：保持signaled状态直至调用SetWaitableTimer函数设置了新的期限。 同步（synchronization）：保持signaled状态直至一个线程在该对象上完成了等待操作。 两种可等待定时器对象都可以是周期定时器（periodic timer）。…
租约 (计算机科学)
在计算机科学中，租约授予其持有者在一定期限内对某些资源的特定权利。由于它是有时间限制的，因此租用是资源序列化锁的替代方法。 动机 传统的资源上的锁一直都处于持有状态，直到锁定它的进程显式释放它为止。 可能无法释放锁的原因包括： 客户端在释放资源之前失效 客户端在尝试分配其他资源时陷入僵局 客户被阻止或延迟了不合理的时间 客户可能由于错误而忘记了释放资源 释放资源的请求已丢失 资源管理器失效或丢失了对资源的控制 在重置系统之前，所有这些方…
Read-modify-write
读-修改-写（read-modify-write）是计算机科学中的一个原子操作（atomic operation，类似的还有test-and-set, fetch-and-add, compare-and-swap等），操作过程是读一个内存位置（或IO端口），修改其值，再写回原位置。 必须要先读操作的一个原因是，系统架构往往只允许字（word）级的读写，必须先读出那些不做修改的位元，保持不变再写回。写成C语言语句类似于： pRegist…
Fetch-and-add
fetch-and-add是CPU指令（FAA），对内存位置执行增加一个数量的原子操作。具体内容为： :令 变为，其中是个内存位置，是个值 FAA可用于实现互斥锁、信号量。 1991年，证明fetch-and-add具有一个有限的数，能解决不超过两个并发进程的无等待consensus问题。 用途 下述伪代码用ticket lock算法实现了互斥锁： record locktype { int ticketnumber int turn …
排号自旋锁
排号自旋锁是计算机科学中的一种多线程同步机制。类似于自旋锁，但每一个申请排队自旋锁的线程获得一个排队号（ticket）。至多一个线程拥有自旋锁，当它释放锁时，把自身的ticket加1作为下一个可获得锁的ticket，持有该ticket的线程在自旋检查时就可发现已经获得了自旋锁。这种机制类似于一些提供社会服务的场所（如银行）：进门的顾客从排号机获取一个等待号，然后不断检查当前可服务的号，直至轮到其手持的号。 这是一种先进先出(FIFO)的…
多版本并发控制
多版本并发控制(Multiversion concurrency control， MCC 或 MVCC)，是数据库管理系统常用的一种并发控制，也用于程序设计语言实现事务内存。 MVCC意图解决读写锁造成的多个、长时间的读操作饿死写操作问题。每个事务读到的数据项都是一个历史快照，并依赖于实现的隔离级别。写操作不覆盖已有数据项，而是创建一个新的版本，直至所在操作提交时才变为可见。快照隔离使得事务看到它启动时的数据状态。 算法 MVCC使用…
惊群问题
惊群问题是计算机科学中，当许多进程等待一个事件，事件发生后这些进程被唤醒，但只有一个进程能获得CPU执行权，其他进程又得被阻塞，这造成了严重的系统上下文切换代价。 解决办法可能有： 不希望把所有进程都唤醒，就采用定点唤醒某一个进程的做法。 尽量避免进程上下文切换。 参考文献
乐观并发控制
在关系数据库管理系统里，乐观并发控制（又名“乐观锁”，Optimistic Concurrency Control，缩写“OCC”）是一种并发控制的方法。它假设多用户并发的事务在处理时不会彼此互相影响，各事务能够在不产生锁的情况下处理各自影响的那部分数据。在提交数据更新之前，每个事务会先检查在该事务读取数据后，有没有其他事务又修改了该数据。如果其他事务有更新的话，正在提交的事务会进行回滚。乐观事务控制最早是由孔祥重（H.T.Kung）教…
重叠I/O
重叠I/O（Overlapped I/O）是Windows操作系统对异步I/O的实现。自Windows NT引入. 重叠I/O对应于Unix的POSIX异步I/O的API (AIO). 重叠I/O特别适合于大量文件或者socket通信、pipe等场合. Windows 9x不支持重叠I/O. 原理 线程请求一个重叠操作的Windows API函数返回时，该重叠操作可能已经执行完，也可能未执行完还处于pending状态。发起重叠操作的操作…
可唤醒I/O
可唤醒I/O（Alertable I/O）是一种重叠I/O，发起I/O请求的线程在可唤醒状态下（alertable state）执行I/O请求的完成例程。也即完成例程作为回调函数（callback function），被这个线程异步过程调用。 线程只有在执行下述API函数之一，并设置适当的参数标记时，才阻塞于可唤醒状态： SleepEx WaitForSingleObjectEx WaitForMultipleObjectsEx Sig…
优先级继承
优先级继承是实时计算中去除优先级翻转的一种方法。进程调度算法对获取到临界资源的进程(A)增加其优先级为所有等待该资源的进程中的最高优先级。 一旦进程(A)释放了该资源，就恢复到原来的优先级。 例子 考虑下例: 假定L获取到共享资源后，H申请该资源不得而被阻塞。优先级继承协议把L的优先级升级到H的级别。M将不能抢先L因而M被阻塞。当L释放资源后，恢复到低优先级并唤醒H。H有高优先级因而抢先了L的执行权。随后M、L依次恢复执行。 参考文献 …