Race Conditions and Semaphore

Presentation on theme: "Race Conditions and Semaphore"— Presentation transcript:

1 Race Conditions and Semaphore
Operating Systems Race Conditions and Semaphore 这是操作系统里面这门课重点、难点，最最重要的。一般来讲，期末考试也是压轴大题！ 要有一个作业说明，文档，讲一下大概思路，编程序在软件工程里占的比重不是太大的。重点是怎么阐述你的思想。 进程间的通信。 1

2 Relationship of Processes
Two types of relationship Mutex Synchronization Solutions Busy Waiting Sleep and Wakeup 进程指的是一段代码是针对一组数据的一次执行活动，是一个实体，有生命，有诞生，有成熟，有死亡。在生存周期里，会拥有一定的资源，一个进程如果什么资源也没有，那就没法工作。一个进程起码需要 内存，CPU时间，外部设备等。由于进程拥有资源，就给我们带来一些问题，我们知道现代操作系统有个重要特征就是multiprogramming，指我们现代操作系统都支持在广义上来讲在相对较长的时间内同时运行多个进程的能力。就好比说，可以同时的，无序的，并发的，没有规律的不可预期的执行多个进程。就好像说，你可以打开电脑后，先打开ie再打开qq，再打开word。操作系统对你打开进程没有时间上的要求， 也没有顺序上的要求，你想什么时候打开，打开多少个都没有问题。就是进程并发的，无序的，大量的，并行的在执行； 第二点，进程所拥有的资源却是非常有限的，什么叫资源，内存，硬件，外设，打印机，键盘，鼠标，显卡，声卡，甚至说一个变量，一个文件都是资源。资源都是非常有限的。而且很多资源有个特点就是不可同时被多个进程使用。这样的资源我们一般叫做独占的临界资源。什么叫临界资源，就是不可同时被多个进程使用的资源。随便举个例子，打印机，可以打印进程所交过来的文档。比如说在word点击打印按钮，会有一个很本能的意识，打印机不可能同时为多个进程服务，先打进程1发过来的第一行，再打进程二第二行…再打进程1打印的第1行，是不可能，所以打印机这种资源可以被多个进程轮流使用，但是不可能同时使用。有限的资源，要被进程独占的，不可抢占的使用，就给我们造成了一个矛盾，什么矛盾，并发的无序的大量的进程在使用着有限的独占的不可抢占的资源。由于进程无线，资源有限，使得其产生不可调和的矛盾，这个矛盾就叫竞争。Race！ 进程与进程之间race condition有两种情况，第一次叫互斥，即两个或者多个进程同时要使用同一个东西，而这个东西不能同时被两个或者多个进程使用，这时就要打架。如刚才举的例子，什么是互斥的呢？In这个变量，这个变量不能被两个进程或者多个进程同时访问或者修改。应该怎么做呢？如果有一个人来查in这个变量，再查之后要改，在改之前别的人不允许访问in这个变量，查也不行，改也不行。这样做才能保证逻辑上不出问题。刚才打印机的例子，如果没有打印队列的话，两个进程抢一个打印机，第一个进程占上，第二个进程就等着。两个进程抢占同一个临界资源所形成的竞争条件我们叫互斥，mutex。 还有一种关系叫同步。比如，我们三个进程来处理一段数据，第一个进程负责从外部设备上读进来，第二个进程负责对这些数据进程处理和计算，第三个进程负责把结果打印到打印机上。这三个进程之间存在着内在的关系，第一个进程不执行完，第二个进程就不能开始工作，第二个进程不把数据准备处理好，第三个进程就不能开始打印。这三个进程之间存在一种内在的逻辑的制约关系。这种关系就叫Sychon，同步。这两种关系好区分，互斥一般来讲互斥的两方，彼此并不认识，也没有什么内在的逻辑关系。例如打印的例子，但是由于两个进程抢占了临界资源，导致他们两个可能会互相制约，也可能制约不上。A工作的很快，算完去打印。打印完了而B还在运算，那A和B根本没有发生制约关系，也没有竞争任何资源。也许A打的慢一点，B工作快一点。那么A就把B当在了打印机外面，那么A和B就有制约关系了。A和B之间并没有内在的逻辑的必然的制约关系。他们只是由于抢占了某个临界资源而导致他们可能会产生一种制约关系。这种关系叫做互斥。 而第二个例子，第一个没处理完，第二个就没法工作，第二个没处理完，第三个就没法工作。是认识的，是合作，是前一个进程为后一个进程来服务的，他们有 内在的逻辑关系的，这样的关系就叫同步。进程与进程之间，要么就没关系，要有就是不外乎这两种关系。或者互斥，或者同步。显然，竞争条件给我们带来很大的挑战，因为如果不处理好竞争条件，要么不能同时用的东西同时用了，要么本来该等待的，也没等待。下面我们来看一下如何来解决竞争条件。

3 Two processes want to access shared memory at the same time.
Race Conditions 两个或多个进程读写某些共享数据或资源，而最后的结果取决于进程运行的精确时序，称为竞争条件。 我们看这个例子，比如说，打印机不可以同时被两个后者多个进程同时使用，你去打印店，word打开，当你点打印时，会显示正在打印第一页，第二页…但是你会发现， 打印完毕，但是你会发现，那边的打印机根本没有在为你的任务而工作，可能是正在为别的机器而工作，或者说卡纸了，卡在那不能再工作了，但是word仍然报告给你打印已完成。去打印店，总共只有三台打印机，十几台电脑在发打印指令。每个人提交打印任务的时候都是很快提交上去并完成，你可以打开很多个word，打印打印，全都打印完了，把word全部关掉，u盘拔掉，可是打印机还是没有开始为你工作。但是你的任务并不会丢，打印机早晚会想起来你，帮你把那些文档打印出来。这是为什么呢？因为有Spooling，中文假脱机。打印的时候并不是真的送到打印机上，实际上只是把打印的文档送到一个打印队列，这实际上这是硬盘的一块区域。我只要把我的任务送到队列中，早晚有一天打印机可以把它打出来。因为大家轮流在这排队，打印机会依次把这些文档打印出来。我们这个例子讨论的就是这个事，比如说现在有一个进程A要打印它的文档，他回来检查他的打印队列，打印队列中把一个一个任务叫做一个一个的slot，进程A发现slot7是空闲的，可能打印机已经打印完了123，456还在等着，7是空闲的。这时打印机为了说明这个问题，维护了两个变量，一个叫In，一个叫out。In=7，代表了如果有新的任务进来，那么送到7号槽里，out=4，如果打印机有时间了，可以打印来，那么去4号槽里去取任务打印。ProcessA检查发现7是空闲，就决定把它的任务送到7号槽里来。但是我们刚才讲了操作系统的特点就是并发的无序的在执行，所以ProcessA刚发现这个问题的时候，它的时间片到了，根据我们上一堂课讲的，scheduler决定将processA从running变成ready。Scheduler就去挑下一个任务去运行，processB从ready变成了running，ProcessB正好要去打印，他也来检查这个变量，发现in=7，就把自己的任务送到7号槽里。然后就认为自己的任务完成了，就去做其他事情。过了一会，ProcessB的时间片也到了，重新换ProcessA开始运行。由于A已经检查过了7号槽是空闲的，他就不会再检查了，它就理所当然的把自己的任务放到了7号槽。那么问题就来了！由于两个进程轮流执行，检查和修改，问题在于检查和修改（将in=7改为8）中间被打断了。我先检车后修改，结果检查完还没来得及修改的时候我去睡觉了，而这种情况是无法避免的，因为进程在并发的无序的执行。就出现了这样的矛盾。类似的问题太多了，例如售票系统，12306，你查的时候还有最后一张票，你点购买，结果查的时候还有另外一个人也查到还有最后一张票，他也点购买，那如果这个系统不加以限制的话，，就有可能同一张票 卖给两个人，因为你先查但没买，他接着查但没买，你买了，结果他也买了。两个人拿着两个一模一样的票上了火车。但是目前来说没有发生。大家想想你做的程序有没有这种可能性。例如，计算pai，你肯定有个全局变量叫sum，一个线程算奇数项，一个线程算偶数项。你这两个线程有没有考虑sum=sum+自己算的结果。你有没有考虑如果两个线程同时去做加法。第一个线程发现sum=0，加上自己算出来的数，第二个线程发现sum也等于0，他也拿0加上自己算出来的数加。算完以后并不是两者加起来的和，而是最后一个执行加法的数。你有没有考虑过这个问题。 类似的问题都叫竞争条件。 Two processes want to access shared memory at the same time.

4 Critical Regions (1) Conditions required to avoid race condition:
No two processes may be simultaneously inside their critical regions. No assumptions may be made about speeds or the number of CPUs. No process running outside its critical region may block other processes. No process should have to wait forever to enter its critical region. 解决竞争条件有很多方法，我们先来看一下要解决竞争条件要满足哪些条件： 第一个叫做，临界区，critical region，这个词很容易被考，例如名词解释，选择题等。什么叫临界区？首先临界区首先是一段代码，不是内存的区，这段代码要使用某个临界资源。刚才我们已经提到过critical resource，什么叫临界资源呢？就是可以共享使用，但不能同时使用。操作系统有些题目非常可恶，经常会考察一下概念，例如打印机是可以共享的么？可以。可以共享给大家轮流的用，但是必须轮流用，而不能一起用。所以打印机是临界的，但是共享的。所谓临界资源，就是不能同时被两个或多个进程同时使用的资源叫临界资源。使用临界资源的代码叫临界区。 为了避免竞争条件，对于临界区的使用，有这样四点规定： 1.任何两个进程不能够同时进入他们的临界区。即不能进入使用同一个资源的临界区； 2.不能对CPU的个数和速度做出假设。是说你不能预测你的系统中有多少个任务在执行，谁执行的快，谁执行的慢，即系统中的进程完全是自发的，独立的，无序的在执行，谁快谁慢谁先谁后都不知道，你作为一个操作系统的设计者，你必须能够适应各种情况； 3.任何在临界区之外的进程，不能阻碍其他进程进入临界区；即你不能自己不进临界区还不让其他人进入； 4. 任何进程都不应该被长期阻塞在临界区之外，即早晚我得进得去。 这四点很重要，可以用来判断我们的算法是否解决了竞争条件。

5 Mutual exclusion using critical regions.
我们刚才说了两个进程不能同时进入同一个资源的临界区。所以，这里有个图，进程A在执行，执行中，进程b也要执行进入临界区，所以B先block，等A退出的时候，B才进入临界区。 Mutual exclusion using critical regions.

6 Mutual Exclusion with Busy Waiting
Proposals for achieving mutual exclusion: Disabling interrupts Lock variables Strict alternation Peterson's solution The TSL instruction 解决竞争条件的方法有很多很多，我们一会会讲一大堆，正确的，错误的，好的，不好的。这些方法的，大致上可以分为两大类，一类是busy waiting, 另一类叫sleep and wake up。busy waiting就是等着，一直很忙的等着，我不是被动的等，而是不断的去检查检查，直到我能进入临界区为止。而第二种方法，睡眠与唤醒，即我检查发现不能进入临界区那么我就去睡觉，等我能进入临界区的时候，就有人把我唤醒。我们先来看几个busy waiting的，比较著名的有这么几种，有对的，有错的，有可行的，也有不可行的。 第一种方法，屏蔽中断或禁用中断。大家想这个方法能否解决竞争条件？中断是什么，系统所有的工作都离不开中断，最最起码的还有时钟中断。如果把中断全都禁用，则系统不会允许进程的scheduling，即调度不会发生，调度不发生，会发生什么？例如A占着CPU，不允许调度，那意味着绝对不会有进程去抢，因为他们都在睡觉。所以一定没有竞争。所以，你想打败敌人最简单的方法，把所有人都迷倒，下点蒙汗药。都睡着了，你一定想干什么干什么。这个方法好么？不好，虽然能工作。代价太大了。把整个系统都停下来，整个世界都为你而停止。而且禁止中断这件事，轻易不能让一个普通进程拥有这样的能力。如果谁都可以拥有这样的能力，谁都想把这个系统给独占了。但是禁止中断这个方法，确实是一个非常有效的避免竞争的方法。我们大家如果去读操作系统内核，有时内核处于安全，方便或者书简单的考虑，会把中断先关一下，做一个非常敏捷的事情，然后再把中断打开。在这个过程中因为中断都被关了，整个系统通常不会出现什么问题。一定是在内核的控制之下，可以很快的把问题解决掉。对于操作系统内核来讲，确实很善于用这个方法，但是绝对不是用来解决普通进程的问题。 第二个叫lock variable，即内存中我定义一个变量。如果lock=0，说明没人用，我可以用。如果lock=1，说明有人用，我就等着。这个方法行不行？如果弄一个变量，哪个进程要用打印机，如果变量=0，我就去用，同时把变量改为1.行不行？如果我去检查这个变量等于 零，然后就睡着了。然后醒来，不会再次检查，就会误以为可以归你用了。有人说，我可以再加一个变量，做第二次检查，如果再睡着了呢？？这是一个循环问题，永远误解，设置多少都没有用。检查和修改，即检查完还没修改，只要中间能被打断，就有可能出问题。所以，这其实体现在全局变量，全部变量可能被多个线程访问，那么这个变量你怎么保护他。 所以，lock variable是不可行的。

7 Strict Alternation 下面看strict alternation，严格轮转法: 这段代码里用了一个变量叫turn，是int型的，取值是0或者1.代表这两个进程0和1. 进程零是这样写的，注意，英文版没问题，中文2、3版都缺一个分号。这是这段代码里最关键的东西，没有这个分号，while就管下一句话了。一个分号代表空语句。等着，知道while等于0为止，执行临界区，执行完，让turn=1.进程1，同理，当turn不等于1，做死循环，直到turn=1为止，进入临界区… 大家考虑一下，这段代码有没有解决临界区的竞争条件问题，turn是一个共享变量，两个进程都能访问到。要说这段代码对不对，我们得看那四个条件是否满足。 第一个，满足。Turn要么等于0，要么等于1，反正不会既等于0又等于1.看起来应该是满足的。有没有可能两个进程都进入临界区？ 第二个，满足； 第三个，我们看这个严格轮转法有个问题，必须是按顺序，进程0，进程1，0,1.当进程0的连续第二次访问，就不行，就自己把自己阻塞在临界区之外。 所以这个方法是有问题的，是能保证两个进程不同时进入临界区，但是必须按照顺序，看turn初始化是0还是1，然后按照顺序来。 A proposed solution to the critical region problem. (a) Process 0. (b) Process 1. In both cases, be sure to note the semicolons terminating the while statements.

8 Peterson’s solution for achieving mutual exclusion.
定义了两个进程。定义了整型数组interested，数组有两个元素。 进程0的process=0，other=1，而进程1的process=1，other=0.进程0会让intested0=TRUE，进程1会让intested1=true。 turn是全局变量，Other是局部变量。 每个进程在执行临界区之前，都会让turn=process。 while 注意分号。 离开的时候，都会让自己的intested=false，intested代表进程想进临界区，不一定能进，是想进。走了就不想进了，所以置为false。什么情况下进程会停下来等呢？turn=我自己，并且对方有兴趣要进。turn代表谁应该让路。对方想进且我该让路，两者缺一不可，都满足我就等着。 这个算法是否满足四个条件？ 1. 两个进程会不会都进临界区？不会。假设都执行到while，turn要么等于0要么等于1，所以turn要么等于process要么等于另一个process，不可能两个都成立。所以不可能同时进入临界区。 2. 一个进程会不会阻塞别的进程进入临界区。假设一开始来的是进程0，进程1没来。c语言有个假设，一个变量如果没有初始化的话，假定都是0，即false。会因为intested[1]=false,而进入临界区，假设再执行一次，还是可以进去。不会一直傻等着。所以没有问题，总能进去，不会阻塞掉。 这个算法虽然麻烦了点，但是正确的。适应面比较窄，只适用于2个进程，当然扩展一下也能有多进程版本。 我们看到正确的算法有个特点，就是对于一个变量不会是先查看再修改。先查再改的问题是，查完了睡着了改错了。正确的算法一定是先改再查。要改对了，所以加了一大堆条件。先插再改，中间会被打断，你的改不能依赖于查。 Peterson’s solution for achieving mutual exclusion.

9 Entering and leaving a critical region using the TSL instruction.
TSL算法：test and set lock 我们书上讲了，在某些计算机上，有这么一条汇编语句，测试并设值。TSL，这条语句后面跟了一个寄存器，跟了一个变量。首先将内存中变量的值复制到寄存器中，同时将内存中变量lock的值赋为1.注意这两者必须同时执行，这两个事情必须同时做，不可打断。我们大家都知道，一条汇编语句是不可能被打断的，多条语句中间有可能被打断，但是一条语句执行了一般是不能被打断的。这条语句就是从内存中取值放到寄存器，同时把内存置为1，不管原来内存中的值是什么。 然后比较寄存器和0，如果不等于0，就跳转到enter_region起始的地方，做个循环。相当于，我过去检查，先把里面的值取出来设为1，先设再看，是不是0，是零说明没有人用那么进入临界区，不是零说明有人用，已经被加锁了，那就等着。不停的做这个事情。取出来，设个1，回来慢慢看，是不是零，不是零。再取出来，慢慢看....直到有进程退出临界区，锁才会被置零。 这个方法是好用的。正确的方法一定是先设再看，看完再设就来不及了。 这个算法为什么正确？最根本的是TSL是一条语句，这就不可能被打断了。问题是这条语句在很多系统中不存在，在x86中就不存在。虽然说这个语句没有，但是我们有替代方案。 Entering and leaving a critical region using the TSL instruction.

10 Entering and leaving a critical region using the XCHG instruction.
The TSL Instruction (2) 换个exchange。就是交换，交换是原子的。先让寄存器等于1，然后再交换。跟原来是完全一样的，交换这个语句是确实有的，这个方法很重要，我们很多系统里面都是用这个方法来加锁解锁。exchange保证交换的内容是原子性的。 Entering and leaving a critical region using the XCHG instruction.

11 Semaphore Semaphore PV operations
1965 E. W. Dijkstra PV operations Atomic operations: very quick and uninterruptable Also known as down/up or wait/signal operations Semaphore can be operated by PV operation only. The only exception is the initialization. Even read the value is prohibited 说了这么多，我们今天的主角才上场。 前面的几个方法都是忙等待，交换一下比比，不行，再交换一下比比，这样一直也许成千上万次，终于有一次可以进去了。这类方法的特点就是忙等待，一直很忙，一直很忙。我们这一章的重点就是信号量。 这个人是数据结构之父，它提出数据结构+算法=程序。 在1965年提出一个词叫信号量，非英语国家，词都比较怪异。 信号量只能够通过PV两个操作来完成。PV是两个原语。原语是指原子性的，不可打断的代码。如果保证呢？可以停止中断等。down就是P，荷兰语中。up就是v。荷兰语相关。我们教材中用的是down和up，down就是P，up就是V。还有的教材用的是signal和wait，也是PV的意思。为了避免混淆，我们课件里通通只用P和V。首先是原子性的，就是不可打断而且速度还特别快。 信号量能被PV原语所访问，别的都不行。这句话很重要，我们每年都至少有一道PV编程题，我一上来我就看如果你出现了，信号量s=1，如果这道题十分，如果我能给的话，我能给你负10分。S=s+1，if f=1等等。信号量既不能读，也不能写，不能来碰他，只能用PV来操作它。你只能P S， V S，不能写s=s+1， if s=10….只要出现这句话，就说明你对PV一无所知，这学期都白学了。唯一的一点例外就是信号量可以单独赋初值。例如 Semaphore s=0可以写s=0或者s=1，定义的时候可以赋初值，其他时候既不能读，又不能写，碰都不能碰。只能用P和V来操作。什么是信号量呢，首先，信号量并不是一个简单的整数，信号量有一个整数部分，不光有整数部分。如果在睡眠与唤醒里面，信号量还伴随着一个等待序列。当然信号量也可以用在忙等待，在那种情况下就没有等待序列了。就是一个整数。所以信号量既有整数部分，还可能有一个等待序列。如何定义信号量呢，semaphore s;而不是int s。我会根据你的定义来决定是一个普通变量还是信号量。你定义int i，你写个p i或者V i，那你也离负10分不远了。普通的东西是不能加到PV里面的，而信号量也不能拿到外面来。信号量的整数部分是什么含义呢，有这么几部分：

12 Semaphore What’s is semaphore?
An integer variable In sleep and wakeup, with a process waiting queue (usu. first in first out) Variable range has different definitions: Whole integer (sleep and wakeup) Positive: the number of resources available Zero: no resource available, no waiting process Negative: the number of processes waiting to use the resources Zero and positive integer (busy waiting) Zero: no resource available Zero and One only (mutex) Binary semaphores 信号量有多种定义。我们先讲一个最完整的定义。它可以取遍整个整数集，从负无穷到正无穷，包括正整数，负整数和零。在这种定义里，正整数代表这个信号量所代表的资源的可用的个数。比如说信号量s=1，代表这个资源可用的个数为1，如果信号量是负值，说明是等待使用该资源的进程的个数。例如s=-3，表明等待使用这个资源的进程数是3，s=0，代表没有空闲的资源也没有等待的进程。

13 PV in Sleep and Wakeup P (Semaphore s) { s=s-1; if (s<0)
added to the semaphore's queue and sleep; } V (Semaphore s) { s=s+1; if (s<=0) wakeup the waiting process in the semaphore's queue; } 我们先看这个定义。将PV用于信号量。 首先对PV给个定义，这是PV用于睡眠和唤醒的一段代码。咱们这门课尽量不要求大家背什么东西，主要是理解，不然就成政治课了，但是这个PV操作要求大家必须背下来。你得会用，用的时候脑子里必须有这个。好，P原语定义是这样的，其入口参数是信号量s，它对s有什么操作呢？首先看，p是个原语，一定不能被打断。如果s小于零，则睡觉去，去哪睡呢？我们说每个信号量都带有一个等待队列，去那个对列睡觉。 V原语，如果s《=零，则唤醒该信号量所对应的等待队列，一般是最前面的那个进程。P代表下降，s=s-1，V代表上升，s=s+1.

14 S = 1 Process A: … … P(S); Print(a.doc); V(S); Runnable
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); P和V两个定义放在这了。这个例子里面，有一台临界资源，叫打印机，不可同时被使用，所以是临界资源。我设置一个信号量是S用来代表打印机，系统中只有一台打印机，所以初值为1，所有的进程在进临界区即要使用这个临界资源之前，对这个资源所对应的信号量做P操作，离开的时候对它做V操作。所以，一上来进程A要打印了，要打印这段代码是临界区，print A.doc这是临界区，一上来P操作，信号量从1变成0。A.doc送到打印机去打印了，打印机工作很慢啊，正打着进程B来了，进程B要打印B.doc,在进入临界区之前先进行P操作，S编程-1，小于零，所以睡觉。过了一会C又来，这时A还在打呢，打得老慢了，C执行完P操作，信号量变成-2，所以C又去睡觉了。所以我们看一下信号量的变化过程，一上来有1个进程可用，所以s=1，A开始打了就没有打印机可用，但是也没有进程在等待呀，所以s=0，B来了以后有一个B在等着，所以s=-1，c来了以后有两个进程在等着，所以是-2.注意，一定要把P原语处理完再做判断。过了一会A执行完。临走前要执行V操作，s=s+1，s变成-1，小于等于零，所以还不能走要在走之前叫醒一个等待的进程，一般都是先进先出，B被唤醒。B唤醒后变成-1，B开始打印，信号量是-1说明有一个进程c在等待。B打印完，会让s=s+1, s变成零，0小于等于零，说明还有人等，要唤醒c。C又开始打印，信号量这时是0，是没有人等，也没有闲着的。等C也执行完，s=s+1，s变成1,1不小于等于零，直接走掉，s=1.说明有一个打印机闲着。整个过程就是这样。 PV之所以好用，主要是PV是原语，原子的，不可能被打断。刚才那段代码如果被打断，就没法执行了。 这种叫做PV原理的睡眠与唤醒方案，还有一种是忙等待方案。 V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable

15 S = 1 -> 0 a.doc Process A: … … P(S); Print(a.doc); V(S); Runnable
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable

16 S = 1 -> 0 a.doc Process A: … … P(S); Print(a.doc); V(S);
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Runnable

17 B S = 1 -> 0 -> -1 a.doc Process A: … … P(S); Print(a.doc);
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Blocked

18 B S = 1 -> 0 -> -1 a.doc Process A: … … P(S); Print(a.doc);
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Blocked Runnable

19 B C S = 1 -> 0 -> -1 -> -2 a.doc Process A: … … P(S);
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Blocked Blocked

20 B C S = 1 -> 0 -> -1 -> -2 Process A: … … P(S); Print(a.doc);
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Blocked Blocked

21 C S = 1 -> 0 -> -1 -> -2 -> -1 b.doc Process A: … … P(S);
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Runnable Blocked

22 C S = 1 -> 0 -> -1 -> -2 -> -1 Process A: … … P(S);
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Runnable Blocked

23 S = 1 -> 0 -> -1 -> -2 -> -1 -> 0
c.doc S = 1 -> 0 -> -1 -> -2 -> -1 -> 0 P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Runnable Runnable

24 S = 1 -> 0 -> -1 -> -2 -> -1 -> 0
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Runnable Runnable

25 S = 1 -> 0 -> -1 -> -2 -> -1 -> 0 -> 1
P (Semaphore s){ s=s-1; if (s<0){ sleep…; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s=s+1; if (s<=0){ wakeup…; } Runnable Runnable Runnable

26 PV in Busy Waiting P (Semaphore s) { while (!s>0) yield the CPU;
} V (Semaphore s) { s++; } 这个方案里，信号量可以取正值，可以取零，但是不能取负值。当S不大于零，放弃CPU。说明不执行，主动转入ready。S大于零时，s--。V原语就变简单了。 这是怎么工作的呢？看下一个动画

27 S = 1 Process A: … … P(S); Print(a.doc); V(S); Runnable
P (Semaphore s){ while (!s>0) yield; s--; } Process A: … … P(S); Print(a.doc); V(S); 一上来，s=1. A来打印，s大于零，直接跳过，S--，s变成零。A开始打印。B来了，会检查s》0，等着等着，C又来了，B和C不停的来测试测试，成千上万遍，终于A打印完了退出临界区时S变成1。下一个轮到B还是C呢？不一定，虽然B来的早，也许正好先被C测到。 这跟进程状态是一致的，如果发现我用的资源得不到满足，我就去睡觉，这就是睡眠与唤醒方案。A去打印，B来打不了就去睡觉，谁负责叫醒B呢，A。而忙等待方案，就是谁也不睡觉，就是不停的测，不停的测，一直测到能进临界区为止。没有睡眠这个状态，一直都是runnable，一个在running，其他在ready。大家会不会觉得忙等待不太好，浪费CPU，睡眠与唤醒好一点。但是比较简单，所以也经常用。 信号量是这本书的重点和难点，我们后面会讲用信号量的方法来解决同步和互斥的一系列经典问题。 V (Semaphore s){ s++; } Runnable

28 S = 1 -> 0 a.doc Process A: … … P(S); Print(a.doc); V(S); Runnable
P (Semaphore s){ while (!s>0) yield; s--; } Process A: … … P(S); Print(a.doc); V(S); V (Semaphore s){ s++; } Runnable

29 S = 1 -> 0 a.doc Process A: … … P(S); Print(a.doc); V(S);
P (Semaphore s){ while (!s>0) yield; s--; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); V (Semaphore s){ s++; } Runnable Runnable

30 S = 1 -> 0 a.doc Process A: … … P(S); Print(a.doc); V(S);
P (Semaphore s){ while (!s>0) yield; s--; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s++; } Runnable Runnable Runnable

31 S = 1 -> 0 Process A: … … P(S); Print(a.doc); V(S); Process B: … …
P (Semaphore s){ while (!s>0) yield; s--; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); V (Semaphore s){ s++; } Runnable Runnable Runnable

32 S = 1 -> 0 -> 1 ? ? Process A: … … P(S); Print(a.doc); V(S);
P (Semaphore s){ while (!s>0) yield; s--; } Process A: … … P(S); Print(a.doc); V(S); Process B: … … P(S); Print(b.doc); V(S); Process C: … … P(S); Print(c.doc); V(S); ? ? V (Semaphore s){ s++; } Runnable Runnable Runnable

33 The Producer-Consumer Problem
下面看一下PV原语怎么来解决进程间的互斥与同步的关系。 第一个例子叫生产者-消费者问题。我们假设生活中有一个面包房，特点是前店后厂。在卖的柜台上，有n个篮子或者盒子，在面包房里有个生产者，即做面包的人。每做出一个面包就会放在格子里。最多只能放n个。第二个人叫消费者，即买面包的。消费者将从格子里取走面包，即生产者不停的生产，消费者不停的消费，他们之间存在什么样的制约关系呢？这两者存在几种制约关系？ 我们先来想一下，什么情况下消费者不能消费？空的，面包数为零。什么情况下生产者可以生产？有空的篮子就可以生产。满了就不能生产。生产者如果出现了不能生产这种现象，谁能解决这个问题？消费者。而消费者不能消费，即篮子空了，谁能解决这个问题？生产者！所以这两个进程就存在内在的制约关系，生产者不生产出来，消费者无法消费，消费者不及时消费掉，生产者无法继续生产。当然他们可能没那么严格。我们考虑一个极端的情况，n=1，就必须严格轮转。生产者生产一个，消费者消费一个，生产，消费，生产，消费。当n大于1时，缓和一些。刚才我们描述这个问题，是同步还是互斥呢？互斥是两个进程抢一个资源，而两者之间没有内在的制约关系。同步必然是两者之间内在的逻辑关系，前者不怎么样，后者就不怎么样。所以这个问题是同步还是互斥？这个问题里面是有互斥，但是不是我刚才描述的这个现象。这n个格子，后者n个元素的缓冲区。它不能被生产者同时访问。例如厨师正在往里面放面包，消费者必须等它放完了才能来消费，必须先放好再拿走。所以在消费和生产的过程中，这个缓冲区是被互斥访问的，但是他们之间的制约关系是同步问题。 那么请大家想一下，我们用p和v以及信号量来解决这样一个问题。我们先看一个错误的解法。 定义n=100，定义count的全局变量，生产者如果count=n，就去睡觉，生产一个，count=count+1，如果count=1，则唤醒消费者。这边如果count=0则睡觉，count=count-1，如果count小于1，则唤醒生产者。这个解法是完全错误的，你们看看有什么错误？？ 首先，如果消费者先来count==0则睡觉，生产者如果count=1，说明刚才是0则唤醒消费者。这个逻辑对么？这里边还是存在先检查后修改所引发的问题。假设消费者先来，看所有格子都是空的，n=0，在他将睡未睡的时候，它被打断了。现在轮到生产者来生产，他就生产了一个面包，还是一个，说明刚才是零个，消费者还没来得急睡。所以生产者看等待队列没人，就打一晃走了。走了以后，轮到消费者工作，消费者去睡觉了，消费者睡着后，将再也没有机会被叫醒了。因为再生产的面包都是第二个第三个第四个，再也不会被叫醒了。 问题出在哪？？ Count这个变量是全局变量，使用这个变量没有加保护。不加保护的结果就是检查完以后可能白检查。我们说的先检查再修改就有可能被打断了，前边的检查就无效了，但是进程又不知道就会出问题。 . . . The producer-consumer problem with a fatal race condition.

34 The producer-consumer problem using semaphores.
我们来看正确的解法，这段代码你要是无法顺利的默写下来的话，操作系统就不可能及格了。这段代码可圈可点的特别多。 这一章我们是有几个东西要背下来的，PV的定义，信号量的含义，生产者消费者问题的解法。 大家将来在做这种PV题是，也需要这样来写。 首先定义n=100，Semaphore类型的变量有三个。即定义了三个信号量，一定不能写成int… 通篇处理在初始化时有赋值，其他都没有对信号量的读和写操作。 信号量一个叫mutex，初值为1.保护这段缓冲区，不会让生产者和消费者同时来访问，它起到的互斥的作用。然后定义另外两个信号量，一个叫empty，一个叫full。Empty是空格子的个数，空格子对生产者是资源，是用来给生产者使用的。Full是消费者所使用的满格子。满格子初值为零，代表当前没有一个满格子。对于消费者来讲，满格子是他的资源，有几个满格子，就能消费几个面包，就能执行几次。所以empty和full分别用来管生产者和消费者，也叫做通行证。 信号量这个词翻译很多，有的叫信号灯，也有叫通行证。比如说，你有几个满盒子，就意味着你允许消费者消费几次。所以慢格子这样的通行证是交给消费者去通行的标志。这样的通行证，谁又能发放呢？这样说，谁能产生满格子？生产者，所以生产者产生满格子通行证。每生产一个面包就发放一个满格子通行证。消费者来消费的时候，必须持有一张满格子通行证，如果一张满格子通行证也没有，就不得不等待。 生产者要生产需要什么通行证？空格子通行证，有几个空格子就有几张空格子通信证。谁来签发空格子通行证？消费者。所以他们是互相发放通行证。如果我使用通行证没有成功，说明我一张通行证也没有。就得去睡觉，如果有空格子通行证，接下来申请控制整个缓冲区。Mutex相当于是整个缓冲区的一把锁，我先锁上，再往里方面包，放完以后再解开缓冲区的锁。生产完我再产生一张满格子通行证。消费者正好相反，p full，p mutex，v mutex，v empty。生产者是使用空格子，产生满格子。消费者是使用满格子，产生空格子通行证。代码就是这样的，好我们休息一会。 看代码，down和P是一样的。 Empty,full,通行证，也叫私有信号量，是用来控制同步的；而mutex，也叫公有信号量，是来控制互斥的，即用来加锁解锁的，基本上来讲，如果对于某一个临界资源使用，使用之前要加锁p mutex，用完之后要解锁，v mutex。而对于同步的制约关系通过互发通行证或者自己给自己发通行证来解决。 还有可能发生死锁。什么叫死锁呢？死了锁在那了。A等着B,B等着A，就锁住了。生产者和消费者的这两个P颠倒一下。例如生产者先来，消费者后来 ，两个进程因为mutex就死锁了。所谓死锁就是每个进程都拥有的部分资源，期望占有更多资源。谁也不让步。 . . . The producer-consumer problem using semaphores.