临界区和C++使用方式

2020-03-15 10:07:59

一.临界资源临界资源是一次仅允许一个进程使用的共享资源。各进程采取互斥的方式，实现共享的资源... 每个进程中访问临界资源的那段代码称为临界区（criticalsection），每次只允许一个进程进入临界区，进入后，...

一.临界资源

临界资源是一次仅允许一个进程使用的共享资源。各进程采取互斥的方式，实现共享的资源称作临界资源。属于临界资源的硬件有，打印机，磁带机等；软件有消息队列，变量，数组，缓冲区等。诸进程间采取互斥方式，实现对这种资源的共享。

二.临界区：

每个进程中访问临界资源的那段代码称为临界区（criticalsection），每次只允许一个进程进入临界区，进入后，不允许其他进程进入。不论是硬件临界资源还是软件临界资源，多个进程必须互斥的对它进行访问。多个进程涉及到同一个临界资源的的临界区称为相关临界区。使用临界区时，一般不允许其运行时间过长，只要运行在临界区的线程还没有离开，其他所有进入此临界区的线程都会被挂起而进入等待状态，并在一定程度上影响程序的运行性能。

三、优缺点

优点:效率高，与互斥和事件这些内核同步对象相比，临界区是用户态下的对象，即只能在同一进程中实现线程互斥。因无需在用户态和核心态之间切换，所以工作效率比较互斥来说要高很多。

缺点:资源释放容易出问题，Critical Section不是一个核心对象，无法获知进入临界区的线程是生是死，如果进入临界区的线程挂了，没有释放临界资源，系统无法获知，而且没有办法释放该临界资源。

临界区是一种轻量级的同步机制，与互斥和事件这些内核同步对象相比，临界区是用户态下的对象，
即只能在同一进程中实现线程互斥。因无需在用户态和核心态之间切换，所以工作效率比较互斥来说要高很多。

四、API介绍

1、初始化对象
InitializeCriticalSection

2、尝试进入临界区，如果成功调用，则进入临界区，如果资源被占用，不会阻塞

TryEnterCriticalSectionThis function attempts to enter a critical section without blocking. If the call is successful, the calling thread takes ownership of the critical section.
A nonzero value indicates that the critical section is successfully entered or the current thread already owns the critical section. Zero (FALSE) indicates
that another thread already owns the critical section.

3、EnterCriticalSection 进入临界资源，取到控制权之前会阻塞
Before using a critical section, some thread of the process must call the InitializeCriticalSection to initialize the object.

To enable mutually exclusive access to a shared resource, each thread calls the EnterCriticalSection function to request ownership of the critical section before executing any section of code that accesses the protected resource。
EnterCriticalSection blocks until the thread can take ownership of the critical section.

4、离开临界资源
When it has finished executing the protected code, the thread uses the LeaveCriticalSection function
to relinquish ownership, enabling another thread to become owner and access the protected resource.
The thread must call LeaveCriticalSection once for each time that it entered the critical section.

5、删除临界对象
Any thread of the process can use the DeleteCriticalSection function to release the system resources that were allocated when the critical section object was initialized. After this function has been called, the critical section object can no longer be used for synchronization.
删除之后临界资源就无效了

五、代码示范

#include <iostream>
#include <windows.h>
#include <thread>
using namespace std;
CRITICAL_SECTION g_cs;

int g_Count = 0;
void func1()
{
	while(1)
	{
		EnterCriticalSection(&g_cs);
		g_Count++;
		cout <<"t1 g_Count = " << g_Count << endl;
		Sleep(3000);
		LeaveCriticalSection(&g_cs);
	}
}

void func2()
{
	while (1)
	{
		EnterCriticalSection(&g_cs);
		g_Count++;
		cout << "t2 g_Count = " << g_Count << endl;

		Sleep(2000);
		LeaveCriticalSection(&g_cs);
	}
}
int main()
{
	InitializeCriticalSection(&g_cs);
	std::thread t1(func1); // t1 is not a thread
	std::thread t2(func2); // t1 is not a thread
	t1.join();
	t2.join();

	
	cin.get();
	DeleteCriticalSection(&g_cs);
	return 0;
}

六、注意

1. 临界区对象不是内核对象，因此不能继承，不能跨进程，也不能用waitfor什么的函数来限定时间等待。这个很好理解，你想想WaitFor要求传一个句柄，而临界区对象的类型都不是句柄，也不能用CloseHandle来关闭，怎么可能会能让WaitForXXX搞了。

2. 临界区对象使用前必须初始化，不初始化会崩溃，这是我的亲历。

3. 线程进入临界区之前会先自旋那么几次，所有自旋锁都失败了之后会创建一个内核对象然后等待这个内核从而进入到内核模式。

4. Enter和Leave必须匹配，每Enter一次，就得Leave一次，这又是可恶的计数机制。参见下面的代码：

typedef struct _RTL_CRITICAL_SECTION {
    PRTL_CRITICAL_SECTION_DEBUG DebugInfo;

    //
    //  The following three fields control entering and exiting the critical
    //  section for the resource
    //

    LONG LockCount;
    LONG RecursionCount;
    HANDLE OwningThread;        // from the thread's ClientId->UniqueThread
    HANDLE LockSemaphore;
    ULONG_PTR SpinCount;        // force size on 64-bit systems when packed
} RTL_CRITICAL_SECTION, *PRTL_CRITICAL_SECTION;

这是临界区对象的定义，看见

RecursionCount

这个对象了吧，你觉得它能干点啥？同时在这里你还能看到一个信号量的内核对象，还有一个自旋数量。这些玩意印证了上面的话。如果你同一个线程Leave之前Enter了两次，必须调用两个Leave，不然这个临界区对象依然会阻塞别的线程。再不明白就去看我前面有关挂起线程的那个博文。

5. 由于进入临界去是无限等待的，因此你有时间肯定希望有种方法能够查看一下临界区是否可用，不可用则希望线程立刻去做其它的事情。这时候，你就需要一个TryEnterCriticalSectionAPI，这玩意很好理解，你踹一脚临界区，如果能进去就进去，不能进去这个API立刻以False返回，你就可以安排线程去做其它的事情。注意：你一脚踹进去了之后完事了记得要离开（LeaveCriticalSection）。

6. 前面说了，临界区真正用内核对象挂起线程之前会自旋好几次，因此你看对象里就有一个自旋锁的计数。你可以改这个自旋锁的数量。当然我不是说让你直接修改对象的成员变量！你可以在初始化的时候指定自旋锁的数量，用这个API：InitializeCriticalSectionAndSpinCount。在这里小说一下临界区为什么会自旋。因为程序从用户态转到内核模式需要昂贵的开销（大概数百个CPU周期），很多情况下，A线程还没完成从用户态转到内核态的操作呢，B线程就已经释放资源了。于是临界区就先隔一段时间自旋一次，直到所有自旋次数都耗尽，就创建个内核对象然后挂起线程。但是，如果您的机器只有一个CPU，那么这个自旋次数就没用了，操作系统直接会无视它。原因如下：你自旋着呢，操作B线程释放不了资源，于是你还不如直接切入等待状态让B来释放资源。动态更改自旋数量请使用SetCriticalSectionSpinCount，别做直接更改对象成员变量的二事！

7. 最后，初始化临界区和进入临界区的时候都有可能会遇到异常状况，比如初始化的时候需要申请一些内存来保存DEBUG的信息（参见上面代码的第一个成员变量），如果内存不够，初始化就崩了。进入临界区的时候可能需要新建一个内核对象，如果内存不够，也崩了。解决这个问题的方法有两种

结构化异常处理
初始化的时候使用InitializeCriticalSectionAndSpinCount。这个API有返回值，如果它申请DEBUG信息失败，返回FALSE，另外，刚才提到了这个API可以指定自旋锁的自旋次数。这个自旋次数的范围并非是用0到0xFFFF
FFFF而是0--->0x00FF FFFF，因此你可以设定高位为1指示初始化的时候直接建立内核对象。如果建立失败，这个函数也会调用失败。当然了，一上来就搞一个内核对象似乎有点浪费内存，但是这样能够保证进入临界区不会失败！但是吧，你需要注意，设置高位来保证内核对象的创建只能在2000上玩。MSDN上有说明，不信你看：
Windows 2000: If the high-order bit is set, the function pre-allocates the event used by theEnterCriticalSection
function. Pre-allocation guarantees that entering or leaving the critical section will not raise an exception in low memory conditions. Do not set this bit if you are creating a large number of critical section objects, because it consumes a significant amount
of nonpaged pool. Note that this event is allocated on demand starting with Windows XP and the high-order bit is ignored.

最后是一些实验：

我们看看用InitializeCriticalSection初始化一个临界区对象后，这些成员变量（除去DEBUG外）都是什么样子。

我们Enter一下，看看会变成什么样子

我们再让其它线程也Enter一下看看

可见，新建了一个内核对象。

我们现在让主线程退出临界区

对照线程句柄我们可以看出第二个线程获得了临界区对象。

我们再让第二个线程退出临界区。

临界区除去内核对象外回到了原始状态。

实验2：我们让临界区对象在同一线程内相继被进入两次

::EnterCriticalSection(&g_cs);
::EnterCriticalSection(&g_cs);

可见，计数增加了一个，变成了，因此你得leave两次才能开锁

RTL_CRITICAL_SECTION 结构。为方便起见，将此结构列出如下：

struct RTL_CRITICAL_SECTION
{
PRTL_CRITICAL_SECTION_DEBUG DebugInfo;
LONG LockCount;
LONG RecursionCount;
HANDLE OwningThread;
HANDLE LockSemaphore;
ULONG_PTR SpinCount;
};

以下各段对每个字段进行说明。

DebugInfo 此字段包含一个指针，指向系统分配的伴随结构，该结构的类型为
RTL_CRITICAL_SECTION_DEBUG。这一结构中包含更多极有价值的信息，也定义于 WINNT.H 中。我们稍后将对其进行更深入地研究。

LockCount 这是临界区中最重要的一个字段。它被初始化为数值 -1；此数值小于-1
时，表示此临界区被占用。当其不等于 -1 时，OwningThread 字段（此字段被错误地定义于 WINNT.H 中 — 应当是 DWORD 而不是
HANDLE）包含了拥有此临界区的线程 ID。

RecursionCount
此字段包含当前所有者线程已经获得该临界区的次数。如果该数值为零，下一个尝试获取该临界区的线程将会成功。

OwningThread 此字段包含当前占用此临界区的线程的线程标识符。此线程 ID 与
GetCurrentThreadId 之类的 API 所返回的 ID 相同。

LockSemaphore
此字段的命名不恰当，它实际上是一个自复位事件，而不是一个信号。它是一个内核对象句柄，用于通知操作系统：该临界区现在空闲。操作系统在一个线程第一次尝试获得该临界区，但被另一个已经拥有该临界区的线程所阻止时，自动创建这样一个句柄。应当调用
DeleteCriticalSection（它将发出一个调用该事件的 CloseHandle 调用，并在必要时释放该调试结构），否则将会发生资源泄漏。

SpinCount 旋转次数。仅用于多处理器系统。MSDN
文档对此字段进行如下说明：“在多处理器系统中，如果该临界区不可用，调用线程将在对与该临界区相关的信号执行等待操作之前，旋转 dwSpinCount
次。如果该临界区在旋转操作期间变为可用，该调用线程就避免了等待操作。”旋转计数可以在多处理器计算机上提供更佳性能，其原因在于在一个循环中旋转通常要快于进入内核模式等待状态。此字段默认值为零，但可以用
InitializeCriticalSectionAndSpinCount API 将其设置为一个不同值。

InitializeCriticalSectionAndSpinCount作用

The InitializeCriticalSectionAndSpinCount function initializes a critical section object and sets the spin count for the critical section.

BOOL InitializeCriticalSectionAndSpinCount(
LPCRITICAL_SECTION lpCriticalSection,
                      // pointer to critical section
DWORD dwSpinCount   // spin count for critical section
);SetCriticalSectionSpinCountThe SetCriticalSectionSpinCount function sets the spin count for the specified critical section. DWORD SetCriticalSectionSpinCount(
LPCRITICAL_SECTION lpCriticalSection,
                      // pointer to critical section
DWORD dwSpinCount   // spin count for critical section
);

当线程试图进入另一个线程拥有的关键代码段时，调用线程就立即被置于等待状态。这意
味着该线程必须从用户方式转入内核方式（大约1 0 0 0个C P U周期）。这种转换是要付出很大代价的。

因此， InitializeCriticalSectionAndSpinCount 的作用不同于InitializeCriticalSection 之处就在于设置了一个循环锁，不至于使线程立刻被置于等待状态而耗费大量的CPU周期，而在dwSpinCount后才转为内核方式进入等待状态。通常dwSpinCount设为4000较为合适。

实际上对 CRITICAL_SECTION 的操作非常轻量，为什么还要加上旋转锁的动作呢？其实这个函数在单cpu的电脑上是不起作用的，只有当电脑上存在不止一个cpu，或者一个cpu但多核的时候，才管用。

如果临界区用来保护的操作耗时非常短暂，比如就是保护一个reference counter，或者某一个flag，那么几个时钟周期以后就会离开临界区。可是当这个thread还没有离开临界区之前，另外一个thread试图进入此临界区——这种情况只会发生在多核或者smp的系统上——发现无法进入，于是这个thread会进入睡眠，然后会发生一次上下文切换。我们知道context switch是一个比较耗时的操作，据说需要数千个时钟周期，那么其实我们只要再等多几个时钟周期就能够进入临界区，现在却多了数千个时钟周期的开销，真是是可忍孰不可忍。

所以就引入了InitializeCriticalSectionAndSpinCount函数，它的第一个参数是指向cs的指针，第二个参数是旋转的次数。我的理解就是一个循环次数，比如说N，那么就是说此时EnterCriticalSection()函数会内部循环判断此临界区是否可以进入，直到可以进入或者N次满。我们增加的开销是最多N次循环，我们可能获得的红利是数千个时钟周期。对于临界区内很短的操作来讲，这样做的好处是大大的。

MSDN上说，他们对于堆管理器使用了N=4000的旋转锁，然后“This gives great performance and scalability in almost all worst-case scenarios.” 可见还是很有用的:-)

8、多次调用 LeaveCriticalSection 导致死锁

来自MSDN的忠告

If a thread calls LeaveCriticalSection when it does not have ownership of the specified critical section object, an error occurs that may cause another thread using EnterCriticalSection to wait indefinitely.

文章参考

1、注意事项

收起

展开全文

操作系统——临界区对信号量保护的实现

2021-08-16 17:32:31

一、临界区的引出从上一篇文章中，我们了解到了信号量的概念。信号量的数值表达的语义用来控制进程的走和停，因此，信号量的数值是非常重要的，信号量的数值吧必须和信号量的语义相一致，才能正确地决定进程的同步...

一、临界区的引出

从上一篇文章中，我们了解到了信号量的概念。信号量的数值表达的语义用来控制进程的走和停，因此，信号量的数值是非常重要的，信号量的数值吧必须和信号量的语义相一致，才能正确地决定进程的同步。比如信号量的数值为0，但此时实际上有一个进程阻塞在该信号量，那么即使对该信号量执行V操作也不会唤醒被阻塞的进程。

但是信号量是一个会被多个进程操作的共享变量，各个并发进程竞争使用CPU会导致各种各样的调度问题，部分调度顺序可能会导致信号量出现语义错误。

以生产者——消费者问题为例，初始情况empty=-1，P1、P2都应当阻塞在该信号量上，empty=-3，但是由于P2在P1完成empty=P1.register之前，就开始对empty进行操作，导致最后empty=-2，出现了语义错误。

为了对信号量进行保护，就要使一个进程在对信号量进行修改操作时，其他的进程必须处于等待状态，当该进程修改完成以后，才能接着对信号量进行操作。即进程对信号量的修改要么是一点不做，要么是全部做完，对信号量的修改必须是一次原子操作。

那么引入什么样的机制可以使进程对信号量的操作变成原子操作？

在软件系统中，无论增加什么机制，都表现为增加了代码，所以对信号量的保护就是在对信号量操作代码的基础上“包裹”其他代码来让信号量的修改操作成为原子操作。

如图所示，当P1进入临界区修改信号量数值的时候，即empty--，P2就不能进入临界区执行empty--了。

临界区就是进程中一段代码，这段代码与其他相关进程中的相关代码是对应的，一次只允许一个进程进入，就是互斥进入。一旦进入这段代码，操作系统的状态就发生了改变，不能随意地切换进程，而在执行进程中的其他代码时是可以切换的，因此这一段代码称为临界区。

了解了临界区的概念，我们发现问题就转变为如何将修改信号量的代码转变为临界区代码。那么就需要在修改代码的前后加上进入区代码和退出区代码，如何实现进入区和退出区就成了核心问题。

二、临界区的软件实现

1.轮换法

临界区要求互斥进入，那么可以采用轮换法。

如上图所示，P0和P1同时只能有一个进入临界区去修改信号量的大小。但也存在问题，P0只有当turn=0的时候才能进入临界区，假设P0进入过一次临界区后，turn=1，那么只有当）P1执行一次后，turn才会重新变成0，那如果P1不执行的话P0也始终无法得到执行。

因此，临界区的实现不仅仅要考虑互斥进入一个因素：

1.互斥进入。一次只允许一个进程进入临界区。

2.有空让进。如果没有进程在临界区执行，并且有进程请求进入临界区，那么就应当让请求进程的一个进入临界区，防止资源死锁。

3.有限等待。任何人一个进程在提出进入临界区的请求后，在等待有限的时间后就能够进入临界区。

2.标记法

标记法即给每一进程加一个标记flag[i]，当该进程要进入临界区时，就把flag置1，再扫描是否有其他进程想要进入临界区，即其他进程的flag为true，如果有的话就进入自循环等待。

标记法虽然能做到互斥进入，但当P0和P1都想进入临界区，flag都为true的时候，两个进程都会进行自循环，这就无法满足有空让进的原则。

对标记法进行改进：

1.用标记法判断进程是否想进入临界区；

2.如果进程想进入临界区，就用轮换法给出一个明确的优先顺序；

3.将轮换法和标记法结合在一起，这就是Peterson算法。

如果P0和P1都进入了临界区，说明flag[0]=flag[1]=ture，而turn=1=0，这是不可能的，所以满足互斥进入；如果P0想进入临界区而P1不想，则flag[0]=1、flag[1]=0，那么P0就不满足自循环条件，会进行信号量的修改，而如果两个进程都想进入临界区，那么轮到的那个进程就能够进入临界区，另一个自循环等待，满足有空让进；当一个进程进入临界区以后，执行完成后就会将flag置0，那么在等待的另一个进程就可以不再进入自循环，转而修改信号量数值，满足有限等待原则。

3.Lamport面包店算法

Peterson算法虽然能实现对临界区的保护，但是它只能处理两个进程的临界区，因此就诞生Lamport面包店算法来对多进程临界区进行保护。

该算法将在面包店购买面包的例子与对临界区的保护进行类比，面包店同时只能接待一位顾客买单，其余顾客处在队列中等待买单。面包店会给每一个进店的顾客一个号码，顾客按照由小到大的顺序进行买单，而买完单的顾客的序号就变成了0，想要再次购买就必须重新取号。

do
{
    choosing[i] = true;
    number[i] = maxnumber[0],number[1],···,number[n-1] + 1;//号码选取
    choosing[i] = false;
    
    for(j = 0; j < n; j++)
    {
        while(choosing[j]);
        while((number[j] != 0) && (number[j],j) < (number[i],i));
    }
    ···//临界区代码
    number[i] = 0;
}while(true);

1.由于每一个进程都有自己的序号，相同序号的进程再按照名字顺序排列，选出进入临界区的进程一定是唯一的；

2.没有竞争时想要进入的进程直接进入，由竞争的时候一定会选出一个进程进入临界区；

3.一旦进程获得一个号码后，后面的进程获得的号码一定会大于这个号码，进程的等待时间也是有限的。

三、临界区的硬件实现

Lamport面包店算法虽然实现了多进程的临界区访问问题，但是效率比较低下，号码选取、号码维护、号码判断的代价都不小，并且选取的号码数值不断变大，可能会发生溢出的情况。既然软件实现可能会存在一定问题，那么就考虑使用硬件方法实现多进程对临界区的访问。

对于只有一个CPU的计算机，当P0进入临界区之后，意味着CPU正在执行P0临界区中的代码，而当P1进入临界区后，CPU转而去执行P1临界区中的代码，那么CPU在这个过程中进行了进程的调度和切换。而对于单CPU计算机来说，如果能阻断调度，就不会发生在CPU在执行一个进程临界区代码的时候切换去执行其他进程，进入另一个临界区的情况。

进程切换需要调用schedule()函数，而调用schedule()函数需要进入内核，而进入内核需要中断，如果能禁止中断就可以防止CPU的切换。

cli()的工作原理是将CPU标志寄存器中的中断允许标志寄存位IF设置为0，这样CPU就不会在执行完指令后去检查并处理中断了。但对于多CPU计算机而言，其他的CPU仍然可以执行其他的想要进入临界区的进程。

换一种思路，这个问题有点像生产者——消费者问题中为了保证共享缓存区中信号量语义的正确性，一次只能有一个进程进行访问，我们用一个互斥信号量mutex=1来实现互斥访问的控制，那么是否可以用这个信号量来保护临界区了？

但是临界区本身是用来保证信号量操作的原子性，又要在临界区中使用信号量，mutex=1本身作为一个信号量就需要其他手段来保证其操作的原子性，这是一个无法实现的循环问题。

那么我们可以通过硬件的方式来实现mutex操作的原子性，再用mutex实现临界区，再用临界区去保证其他任意信号量操作的原子性。

保护临界区的互斥信号量只有0和1两个数值，这个信号量的P、V操作简单规整，可以用硬件方法实现，而由于信号量只有两个数值，很像一个锁，所以常被命名为lock。

lock=0时，说明没有上锁，进程可以进入到临界区，同时将lock修改为1，这个指令要做成一条硬件指令，一条硬件指令的执行是不会被打断的，所以实现了指令的原子操作。如果lock=1，则进程自旋等待。计算机中有一条硬件指令：TestAndSet。这条指令的操作数存放一个布尔变量的地址，如果该内存中的变量为false，指令会返回false，并将内存中的变量置为true，如果变量为true，则返回true。

function TestAndSet(boolean &lock)
{
    boolean initial = *lock;
    *lock = true;
    return initial;
}

有了这样一条指令来处理lock，我们就可以利用lock来保护临界区。

一旦有进程在lock=false的情况下跳过循环进入临界区，lock就被置为true了，其他进程就处于自旋状态，而当该进程完成信号量操作后，lock=false，其他处于自旋状态的进程才能进入临界区。

即使多个进程执行在多个CPU上，由于大家共享内存，TestAndSet指令操作的lock变量是相同的，对同一个lock变量的TestAndSet可以保证只有一个进程返回false，其他进程返回true。

总结

1.介绍了临界区的概念；

2.说明了临界区使用软件实现的方法；

3.介绍了用硬件方法实现临界区并对信号量进行保护。

收起

展开全文

操作系统多线程

【操作系统系列】临界区算法与信号量实现

2021-01-20 23:58:16

即：没有实现临界区的有空让进标记法标记法的处理思想也很简单进程 P0 想进入临界区就打一个标记，即设置 flag[0]=ture 打完标志以后扫描其他进程是否要进入临界区，如果其他进程都不进入这个进程就进入临界区，...

信号与信号量

在需要同步的位置上，进程将自己阻塞起来等待信号；当该进程所依赖的进程执行到步调一致以后，会向操作系统发出信号；
操作系统收到信号以后，将阻塞进程唤醒执行。

信号量的准确定义：

（1）信号量就是一个整型变量，用来记录和进程同步有关的重要信息；
（2）能让进程阻塞睡眠在这个信号量上；
（3）需要同步的进程通过操作（加 1 和减 1）信号量实现进程的阻塞和唤醒，即进程间的同步。因此，信号量就是一个数据对象以及操作这个数据对象的两个操作
- 其中数据对象是信号量数值以及相应的阻塞进程队列
- 而在这个数据对象上的两个操作就是对信号量数值的加 1 和减 1，并根据加减后的信号量数值决定的睡眠和唤醒。

struct semaphore
{
    int value;  //信号量数值，用来记录资源个数或进程个数
    PCB *queue; //等待在该信号量上的进程队列    
}

//进行减 1 的操作
//根据减去 1 以后的信号量数值来进程决定是否睡眠等待
P(semaphore s) 
{
    s.value--;
    if(s.value<0)
    sleep_on(s.queue);    
}

//进行加 1 的操作
//根据加上 1 以后的信号量数值决定是否要唤醒睡眠在该信号量上的进程。
V(semaphore s) 
{
    s.value++;
    if(s.value <= 0)
    wake_up(s.queue);
}

生产者—消费者同步问题的信号量解法

生产者在缓存区满了以后会睡眠等待，此处要定义一个信号量，当这个信号量的数值为 0 时，生产者要执行 P 操作以后会睡眠等待。
- 所以此处定义的信号量是用 0 来表示缓存区满。因此这个信号量表达的含义就应该是缓存区中空闲单元的个数，所以可以命名为 empty，初值为 BUFFER_SIZE，生产者对 empty 信号量执行 P 操作，而消费者对 empty 信号量执行 V 操作。
类似的，可以分析出消费者进程在缓存区中没有 item 时会阻塞
- 所以对应的信号量为 0 时要表达出缓存区中没有 item 这样的语义，所以该信号量要表达的含义就是缓存区中的 item 个数，可命名为 full，初值为 0。
另外，由于是共享缓存区，当某个进程进入共享缓存区进行修改时，其他进程不能使用缓存区的，只能睡眠等待。有睡眠等待就是一个同步点，因此需要再定义一个信号量来实现这个同步点。
- 由于只能让 1 个进程修改缓存区，所以这个信号量的初值应该为 1，一旦某个进程进入以后就应该将其减为 0 （对应 P 操作）。
- 此时当其他进程再想修改缓存区时，对该信号量的 P 操作会导致进程阻塞等待。根据语义，这个信号量的含义是互斥进入，所以将其命名为 mutex，初值为 1

信号量的命名与初值

关键点：阻塞即将发生（再来一个就发生）的条件，即信号量为 0 时的含义
- 比如生产者，阻塞条件为产品满了，所以生产者阻塞的信号量为 0 时就代表产品敲好满了，所以等待减少来缓解，那就叫 empty
- 比如消费者，阻塞条件为产品空了，所以生产者阻塞的信号量为 0 时就代表产品敲好空了，所以等待增加来缓解，那就叫 full
命名：阻塞即将发生时（即信号量为 0 时），等待消除阻塞的条件名
初值：根据信号量为 0 时的语义决定，每种信号量语义不同

根据上面的分析，生产者消费者同步问题的信号量解法就不难给出了

在这里插入图片描述

临界区

归根结底，信号量的作用就是根据信号量数值表达出来的语义来决定进程的停与走。

比如信号量的当前值为 -1，表达出来的语义就是现在有一个进程等待在这个信号量上，如果再来一个进程执行 P 操作（即要继续减 1，相当于继
续申请资源），此时该进程应该睡眠等待在该信号量上。
而如果再来的进程执行的是 V 操作（即要给信号量加 1，相当于释放资源），则唤醒睡眠在该信号量上的一个进程。

因此，信号量的数值非常重要，只有信号量的数值时刻与信号量对应的语义信息保持一致，才能正确地使用信号量来决定进程的同步（停与走）。

多个进程可以对某个共同的信号量任意修改，但必须是一个进程修改完成以后才能让别的进程修改。
也可以换一种说法，就是每个进程对信号量的修改要么一点不做，要么全部做完，中途不能被打断，即对信号量的修改必须是一个原子操作

临界区就是进程中的一段代码，这段代码和其它相关进程中的相关代码对应，一次至多只允许一个进程进入，即互斥进入。

之所以被称为临界区，是因为一旦进入了这段代码，操作系统的状态就发生了改变，现在就不能在进程之间随意切换了，而执行进程中的其它代码时是可以随意切换的。
信号量保护的实质就是让进程中修改信号量的代码变成为临界区代码。

软件实现

一个实现临界区的方法不仅要做到互斥进入，还应该考虑其他要求：

一、互斥进入，如果有多个进程要求进入空闲的临界区，一次仅允许一个进程进入；在任何时候，一旦已经有进程进入其自身的临界区，则其它所有试图进入相应临界区的进程都必须等待。
二、有空让进，如果没有进程处于临界区内且有进程请求进入临界区，则应该能让某个请求进程进入临界区执行，即不发生资源的死锁情况。
三、有限等待，有限等待意味着一个进程在提出进入临界区请求后，最多需要等待临界区被使用有限次以后，该进程就可以进入临界区。这样任何进程在临界区门口等待的时间是有限的，即不出现因等待临界区而造成的饿死情况。

轮换法

既然是要求互斥进入一次只允许一个进程进入，最容易想到的方法就是“轮换法”
- 即轮到进程 P0 进入时只能让 P0 进入，P0 进入以后再轮换到让进程 P1 进入，依次类推
- 由于 turn 变量在任何时刻都只能取值为 0 或 1，所以图中的两个进程 P0 和 P1 在任何时候最多只能有一个进程在临界区中执行
虽然轮换法能够实现多个进程互斥进入临界区，但也存在缺陷
- 进程 P0 进入一次临界区以后，如果 P0 想再次进入其临界区时就只能等待 P1 进入一次才可以。
- 即：没有实现临界区的有空让进

标记法

标记法的处理思想也很简单
- 进程 P0 想进入临界区就打一个标记，即设置 flag[0]=ture
- 打完标志以后扫描其他进程是否要进入临界区，如果其他进程都不进入这个进程就进入临界区，否则调用代码 while(flag[1]); 自旋等待。
分析标记法的工作效果
- 首先，是否可以保持互斥进入？可以保证，因为如果两个进程都在临界区中，则 flag[0] = falg[1] = ture，而又都没有停在 while(flag[0/1]); 的自旋循环上，说明 flag[0] = flag[1] = false，发生矛盾
- 接下来需要分析是否能够做到用空让进，针对如下调度顺序，进程 P0 执行 flag[0]= true 后切换到进程 P1 执行，现在 P1 也请求进入临界区，从而flag[1] = true，现在 P1 会在 while(flag[0]); 上一直循环，直到发生调度为止（比如时间片到时）。现在进程 P0 会在 while(flag[1]); 上一直循环，P0 和 P1 两个进程都在临界区门口一直自旋，谁也进不去，尽管并没有进程在临界区内。

因此可以总结出这样的做法（Peterson 算法）

（1）用标记法判断进程是否请求进入临界区；
（2）如果进程想要进入临界区，就用轮换法给进程进行一个明确的优先排序；
（3）将标记法和轮换法两个方法融合在一起来实现临界区，这就是由 Gary L. Peterson 于 1981年提出著名的 Peterson 算法
- 即另外一个进程不让当前线程进（标记），当前线程也不让自己进（轮转，如果两个线程都要进，肯定 turn 会被后来要进的线程改为不让它自己进，所以先到的线程就进去了）

Lamport 面包店算法

采用了“轮换 + 标记”以后，Peterson 算法的确做到通过软件实现了对临界区的保护，但 Peterson 算法只能处理两个进程的临界区，现实系统中的临界区往往要涉及到很多进程。这就诞生了 Lamport 面包店算法，该算法是解决多进程临界区问题的算法，由 Leslie Lamport发明。

do
{
    choosing[i] = true;
    number[i] = maxnumber[0],number[1],…,number[n-1]+1;//选取号码
    choosing[i] = false;
    
    for(j = 0; j<n; j++)
    {
        while (choosing[j]);
        while ((number[j] != 0) && (number[j],j)<(number[i],i));
        //(a,b)<(c,d) 意味着 a<c 或 a==c 且 b<d
    }
    
    ······//临界区代码
        
    number[i] = 0;
}while(true); //Lamport 面包店算法中进程 i 的进入区和退出区代码

面包店算法是 Peterson 算法的扩展，也满足“轮换 + 标记”的基本思想
- 其中选号过程相当于打“标记”的过程，
- 而号码最小的进程进入相当于“轮换”。
所以推广 Peterson 算法在“互斥进入、有空让进和有限等待”上的分析过程，不难看出面包店算法也满足临界区保护的三个条件

硬件实现

虽然 Lamport 给出的面包店算法的确解决了多个进程对临界区的互斥访问问题，但是面包店算法的缺点也是明显的，那就是效率问题。
- 选取号码、号码维护、号码判断等操作的代价都不小。
- 另外在产生号码时总是要比当前所有的号码都要大，这就有可能导致号码溢出的情况，这也必须要完成而且又比较费时的处理。
在计算机系统中，当软件实现变得很复杂时，通
常会想到的方法就是让硬件帮忙来简化操作，提高效率。

对于只有一个 CPU 的计算机

如果在进程进入临界区以后时能阻断调度，即不让系统发生调度，就不会出现“进程在临界区中
执行而 CPU 又切换到其他进程，又进入另一个临界区的情况。”
如何不让调度/切换发生，根据内核级线程切换的实现原理，切换需要调用 schedule() 函数，而需要进入内核才能调用 schedule() 函数，要进入内核又需要中断。所以如果能禁止中断，上述 CPU 切换就不发生了。
因此，禁止中断是一种实现临界区保护的方法

开/关中断的确是保护临界区的简单而有效的方法，但该方法也存在一个很大的缺陷，即只能工作在单 CPU 计算机系统下。

对于一个多 CPU 计算机（多核或多处理器），这个关中断操作对其他 CPU 没有影响，别的 CPU 照样可以执行任何任务，当然完全可以执行另一个要进入临界区的进程并让其进入临界区。
要用硬件实现 lock 操作的原子性。这种方法被称为硬件原子指令法。

信号量实现与使用

临界区保护了信号量 P、V 操作的原子性，从而能够保证信号量数值的语义正确性，接下来根据信号量数值所表达出来的正确语义我们就可以正确地控制进程的阻塞和唤醒了。
现在用户就可以定义信号量并调用信号量的 P、V 操作来实现多个进程的同步了。

信号量接口

根据信号量的含义：

（1）信号量是一个需要被多个进程共享的整数；
（2）要根据信号量对应的整数进程会 sleep_on 和 wake_up，这两个动作操作的对象是进程 PCB；
（3）在操作这个整数时要进行临界区保护，可以调用面包店算法、开关中断操作等等。

不管从这三个方面中的哪一个方面来说，应该将信号量的实现放在操作系统内核，并将信号量的 P、V 操作实现成系统调用

因为将一个变量放在操作系统内核以后所有进程就可以共享了
另一方面在操作系统内核中操作 PCB、进行开关中断等动作既简单可行、安全可靠，又能向用户屏蔽细节。
通常，信号量实现为操作系统内核中的一个数据对象，而 P、V 操作实现为操作系统给上层用户程序提供的两个系统调用。

POSIX 标准针对信号量定义了如下四个基本系统调用：

sem_t *sem_open(const char *name, int oflag, mode_t mode,unsigned int value);
这个系统调用用来打开或创建一个信号量变量，其中 name 信号量的名字，oflag可以选择创建一个新的信号量或打开一个现有的信号量。当然也可以用名字来区别是创建一个新的信号量还是打开现有的信号量，mode 是权限位，value 是信号量的初始值。
int sem_unlink(count char *name);
- 用来根据名字从操作系统中删除信号量。
int sem_wait(sem_t *sem);

int sem_post(sem_t *sem);
- 这两个系统调用对应信号量的 P 操作和 V 操作。

如果要编写一个应用程序“pc.c”来模拟经典的生产者消费者问题：

（1）建立 1 个生产者进程，5 个消费者进程；

（2）通过操作同一个文件来建立一个共享缓冲区；

（3）生产者进程依次向缓冲区文件写入整数 0,1,2,…,499；

（4）每个消费者进程从缓冲区文件中读取 100 个数，每读取一个数字就打印到标准输出上；

（5）缓冲区最多只能保存 10 个数，即缓冲区文件中最多存放 10 个数。

利用上面定义的和信号量有关的系统调用，可是实现这个 pc.c 程序：

main()
{
    if(!fork()) { //生产者进程
        empty = sem_open(”empty”, 10); //只用了名字和初值两个参数
        full = sem_open(”full”, 0);
        mutex = sem_open(”mutex”, 1);
        for (i = 0; i< 500; i++) {
            sem_wait(empty);
            sem_wait(mutex);
            读写文件的操作;
            sem_post(mutex);
            sem_post(full);
    	}
	}
    if(!fork()) { //第 1 个消费者进程
        empty = sem_open(”empty”, 10);
        ······ //其他内容类似

信号量实现

如何实现 sys_sem_wait 和 sys_sem_post 这两个系统调用

这两个系统调用的核心是对系统内核中的一个整型变量进行操作，并根据整型变量的数值决定是否要做进程的睡眠或唤醒，这里涉及了一个阻塞队列的维护操作。

sys_sem_wait

sys_sem_wait(sem_t *sem)
{
    cli(); // 进入区代码，也可以是 Lamport 面包店算法、硬件原子指令法等等
    sem->value -- ; //sem 的结构定义可以很直观的想到，此处略去
    if((sem->value) < 0)
    {
        current->state = SLEEP; 
        // ... 将当前进程阻塞将当前进程（如 current 指针）追加到 sem->queue 队列的尾部;
        schedule(); //调用 schedule 切换到别的进程，由于当前进程已阻塞
    }
    sti(); //退出区代码，和进入区代码对应
}

sys_sem_post

sys_sem_post(sem_t *sem)
{
    cli();
    sem->value ++ ;
    if((sem->value) <= 0)
    {
        //....从 sem->queue 队列的首部取出一个进程 p;
        p->state = READY; //设为就绪态将 p 加入到就绪队列中;
    }
    sti();
}

重构：信号量只取正数、sem_wait 用 while 检测、sem_post 唤醒队列中的所有进程、

正值信号量表示现在有的资源个数，而负值信号量表示有多少进程等待在该信号量上。有正有负的信号量容易理解，根据信号量的正负性可以直观地判断出进程是要阻塞还要唤醒。
但有正有负的信号量实现存在一个问题：新来一个资源时，信号量增加 1，会在阻塞队列上唤醒 1 个进程，现在就出现问题了：“应该唤醒哪个进程？”
- 可以在进程放入信号量阻塞队列时就进行优先排序，那么此处又需要写一个复杂的调度算法。
- 实际上完全可以、也应该使用 schedule() 函数给出的进程调度策略来做这个选择，因为 schedule() 函数本来就是决定让哪个进程先执行的
所以在 sem_post 决定要唤醒队列上的哪个进程时，更好地解决办法唤醒阻塞在信号量上的所有进程，然后由 CPU 调度算法 schedule() 来决定让哪个进程获得这个信号量。
- 在所有等待进程被唤醒时，都要重新检测看自己是否得到了信号量，如果发现自己获得了信号量就继续执行，如果发现自己没有获得信号量，就继续阻塞。
- 由于进程被唤醒以后要再次检测自己是否获得了信号量，所以在 sem_wait 中，当从 if((sem->value) < 0) { 中的 schedule(); 处醒来以后，不能直接向前推进，而是应该再次判断信号量条件
- 另一方面，由于每次都是将信号量阻塞队列中的所有进程都唤醒，所以就没有必要记录信号量上的等待进程个数信息（即信号量负值时的语义），因此信号量就不能出现负数了。
```
sys_sem_wait(sem_t *sem)
{
    cli();
    while((sem->value) == 0)
    {
        //...将当前进程加入到 sem->queue 队列尾部;
        schedule();
    }
    sem->value -–;
    sti();
}
```
```
sys_sem_post(sem_t *sem)
{
    cli();
    sem->value ++ ;
    //...让 sem->queue 中的所有进程就绪并加入就绪队列;
    //当然，如果 sem->queue 为空就什么也不做了
    sti();
}
```

收起

展开全文

操作系统 linux

临界区、互斥量、信号量
2016-12-20 21:09:57
1.临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。 2.互斥量:为协调共同对一个共享资源的单独访问而设计的。 3.信号量:为控制一个具有有限数量用户资源而设计。 临界区...
收起
多线程 C++ 操作系统临界区
软件实现临界区互斥的方法总结思考（四种算法的递进推导）
千次阅读 多人点赞 2016-09-22 21:55:51
核心思想：设置一个公共整形变量turn,用于指示被允许进入临界区的进程编号。若turn = 0, 表示允许P0进入临界区。 OK，到这里肯定很容易想到一个问题，谁来改变turn？这里的turn像是一把锁，控制着进程的进入。如果...
收起
OS 进程互斥
临界区，互斥量，信号量，事件的区别
2021-04-07 14:53:59
1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。 2、互斥量:为协调共同对一个共享资源的单独访问而设计的。 3、信号量:为控制一个具有有限数量用户资源而设计。 4、事件:用来...
收起
[多线程] 互斥量和临界区的区别
2017-09-08 18:32:18
互斥量和临界区的区别通常有4种进程或线程同步互斥的控制方法，它们是： 临界区 互斥量信号量事件其中临界区通过对多线程的串行化来访问公共资源或一段代码，速度快；互斥量为协调共同对一个共享资源的访问而设计...
收起
互斥量临界区
C++互斥锁 临界区 信号量事件的区别总结
千次阅读 2016-11-29 16:43:27
1、临界区CriticalSection: 通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。 2、互斥量Mutex: 为协调共同对一个共享资源的单独访问而设计的。 3、信号量Semaphore: 为控制一个具有有限...
收起
C++多线程同步互斥锁临界区信号量事件
进程机制（临界区、互斥区、事件、信号量）
千次阅读 2017-09-18 15:54:45
临界区、互斥区、事件、信号量四种方式 临界区（Critical Section）、互斥量（Mutex）、信号量（Semaphore）、事件（Event）的区别 1、临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制...
收起
Windows开发——临界区，互斥量，信号量，事件的简单介绍与区别
千次阅读 2020-03-23 20:44:05
1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。 2、互斥量:为协调共同对一个共享资源的单独访问而设计的。 3、信号量:为控制一个具有有限数量用户资源而设计。 4、事件:用来...
收起
操作系统多线程
互斥量与临界区的区别
2016-03-21 09:40:14
如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享...
收起
解开 Windows 下的临界区中的代码死锁
2019-10-03 10:10:24
临界区是一种防止多个线程同时执行一个特定代码节的机制，这一主题并没有引起太多关注，因而人们未能对其深刻理解。在需要跟踪代码中的多线程处理的性能时，对 Windows 中临界区的深刻理解非常有用。本文深入研究...
收起
Delphi线程同步（临界区、互斥、信号量）
千次阅读 2016-10-08 17:25:14
*Delphi线程同步（临界区、互斥、信号量）　当有多个线程的时候，经常需要去同步这些线程以访问同一个数据或资源。　例如，假设有一个程序，其中一个线程用于把文件读到内存，而另一个线程用于统计文件...
收起
多线程同步-临界区（深入理解CRITICAL_SECTION）
千次阅读 2015-02-10 18:09:05
临界区是一种防止多个线程同时执行一个特定代码节的机制，这一主题并没有引起太多关注，因而人们未能对其深刻理解。在需要跟踪代码中的多线程处理的性能时，对 Windows 中临界区的深刻理解非常有用。本文深入...
收起
解决临界区（互斥）的软件方法-Dekker算法和Peterson算法
千次阅读 2017-11-29 00:16:43
—为了控制两个进程互斥进入临界区，可以让两个进程轮流进入临界区。 —当一个进程正在临界区执行时，另一个进程就不能进入临界区，而在临界区外等待。 1.为何是“强制交替”？ Turn=0时，无论CS空闲与否，即使P1...
收起
算法
uCos临界区保护
2013-10-31 20:25:00
第一种method简单的进行关开中断的缺陷是不支持这种临界区的嵌套，也就说内层的退出后中断就打开了。注释这里使用到的PRIMASK是看keil编译器已命名的内核寄存器，在工程文件中是没有定义的。转载于:...
收起
操作系统自旋锁+信号量+互斥量+临界区+死锁的区别
2018-09-20 19:44:41
互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥...
收起
操作系统
操作系统中的临界区、互斥量、信号量和事件的区别
千次阅读 2018-03-30 12:08:25
转载自临界区，互斥量，信号量，事件的区别四种进程或线程同步互斥的控制方法 临界区: 通过对多线程的串行化来访问公共资源的一段代码，速度快，适合控制数据访问。互斥量: 为协调共同对一个共享资源的单独访问...
收起
临界区，互斥量，信号量和事件之间的区别
千次阅读 2016-06-01 14:00:27
1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。 2、互斥量:为协调共同对一个共享资源的单独访问而设计的。 3、信号量:为控制一个具有有限数量用户资源而设计。 4、...
收起
mfc 线程同步互斥
【UE4源代码分析】-003 临界区
2018-06-05 13:12:10
1、临界区 临界区指的是一个访问共用资源（例如：共用设备或是共用存储器）的程序片段，而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时，其他线程或是进程必须等待（例如：bounded ...
收起
互斥量和临界区的区别
2021-07-26 17:48:00
互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。互斥量在系统的任何进程里都是可见的，也就是说，一个进程创建了一个互斥量，另一个进程试图去获取该锁是合法的。然而，临界区的...
收起
Mutex,spinlock,semaphore,临界区
千次阅读 2014-01-10 16:54:14
在使用临界区时，一般不允许其运行时间过长，只要进入临界区的线程还没有离开，其他所有试图进入此临界区的线程都会被挂起而进入到等待状态，并会在一定程度上影响。程序的运行性能。尤其需要注意的是不要将等待用户...
收起
临界区、互斥量、信号量、事件的区别
2015-08-11 14:10:06
1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。 2、互斥量:为协调共同对一个共享资源的单独访问而设计的。 3、信号量:为控制一个具有有限数量用户资源而设计。 4、
收起
临界区互斥量信号量

互斥锁、临界区和事件

文章目录

一.互斥锁的介绍

二.临界区介绍

三.关于条件的使用

临界区和C++使用方式

一.临界资源

二.临界区：

三、优缺点

四、API介绍

五、代码示范

六、注意

操作系统——临界区对信号量保护的实现

一、临界区的引出

二、临界区的软件实现

1.轮换法

2.标记法

3.Lamport面包店算法

三、临界区的硬件实现

总结

【操作系统系列】临界区算法与信号量实现

信号与信号量

临界区

软件实现

硬件实现

信号量实现与使用

信号量接口

信号量实现

临界区、互斥量、信号量

软件实现临界区互斥的方法总结思考（四种算法的递进推导）

临界区，互斥量，信号量，事件的区别

[多线程] 互斥量和临界区的区别

C++互斥锁 临界区 信号量 事件的区别总结

进程机制（临界区、互斥区、事件、信号量）

Windows开发——临界区，互斥量，信号量，事件的简单介绍与区别

互斥量与临界区的区别

解开 Windows 下的临界区中的代码死锁

Delphi线程同步（临界区、互斥、信号量）

多线程同步-临界区（深入理解CRITICAL_SECTION）

解决临界区（互斥）的软件方法-Dekker算法和Peterson算法

uCos临界区保护

操作系统 自旋锁+信号量+互斥量+临界区+死锁的区别

操作系统中的临界区、互斥量、信号量和事件的区别

临界区，互斥量，信号量和事件之间的区别

【UE4源代码分析】-003 临界区

互斥量和临界区的区别

Mutex,spinlock,semaphore,临界区

临界区、互斥量、信号量、事件的区别

临界区命名

C++互斥锁临界区信号量事件的区别总结

操作系统自旋锁+信号量+互斥量+临界区+死锁的区别