1、 Chapter 2 Processes2.1 Introduction to processes*common Parallelism=Pseudoparallelism*It is the cpu rapid switching back and forth*multiprocessor is the real parallelism*people design a model,sequential processes 顺序进程顺序进程2.1.1 The process modelABCDABCDABCDProcess-Program理解进程和程序的区别：理解进程和程序的区别：CPU：计算
2、机科学家程序1：烘制生日蛋糕的食谱数据：面粉、鸡蛋、糖和香草汁等对应的进程1：阅读食谱、取来各种原料以及烘制蛋糕的一系列动作的总和。事件：女儿被蜜蜂螫伤保存进程1的当前状态：计算机科学家就记录下自己照着食谱做到哪儿了。程序2：急救手册数据：药物等对应的进程2：实施医疗救治（高优先级进程）当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他离开时的那一步继续做下去。离开时的那一步继续做下去。进程的创建进程的创建1.系统初始化系统初始化2.(1)前台进程：同用户交互并替它们完成工作的哪些进程。3.(2)后台进程：守护进程，处理网页、打印之类活动的
3、进程。2.正在运行的一个进程执行了创建进程的系统调用。正在运行的一个进程执行了创建进程的系统调用。3.用户请求创建一个新进程。用户请求创建一个新进程。在交互式系统中，用户可以通过键入命令启动程序。4.批处理作业的初始化批处理作业的初始化 在操作系统认为有资源运行另一个作业时，它创建一个新的进程，并运行其输入队列中的一个作业。进程的终止进程的终止1.正常退出：正常退出：多数进程由于完成了它们的工作而终止。2.出错退出（自愿）出错退出（自愿）:进程发现了严重错误。3.严重错误（非自愿）：严重错误（非自愿）：通常是由于程序中的错误所致。例如，执行了一条非法指令，引用了不存在的内存，或除数是零。4.被
4、其它进程杀死：被其它进程杀死：当一个进程终止时，由该进程所创建的所有进程也都立即被杀死。Process hierarchies Process States1.运行态（运行态（Running，在该时刻实际占用处理机）。，在该时刻实际占用处理机）。2.就绪态（就绪态（Ready，可运行，因为其它进程正在运行而暂时，可运行，因为其它进程正在运行而暂时被挂起）。被挂起）。3.阻塞态（阻塞态（Blocked，除非某种外部事件发生，否则不能运，除非某种外部事件发生，否则不能运行）。行）。RunningBlockedReady1234123n-3 n-2n-12.1.2 Implementation of
5、 Processes多线程的应用（多线程的应用（1）多线程的应用（多线程的应用（2）网络蚂蚁网络蚂蚁(NetAnts)是从因特网下载文件的工具软件，设计特是从因特网下载文件的工具软件，设计特点如下：点如下：(A)支持支持HTTP和和FTP协议，可同时下载协议，可同时下载1-5个文件；个文件；(B)可随时中止正在下载的任务，任务将自动保存当前状可随时中止正在下载的任务，任务将自动保存当前状态；态；(C)支持拖放，可从浏览器中将链接拖入任务列表；支持拖放，可从浏览器中将链接拖入任务列表；(D)裁剪板自动监视，并可指定将捕获的文件类型；裁剪板自动监视，并可指定将捕获的文件类型；(E)捕获浏览器的动作
6、，当用户在浏览器中单击链接时，捕获浏览器的动作，当用户在浏览器中单击链接时，网络蚂蚁将自动激活。网络蚂蚁将自动激活。To A:when sever is busy,it will stopped,the writing will stopped.save the destination to.To B:when server is busy,other threads will still try.the writing wont stopped.use flashget netant进程和线程的区别进程和线程的区别每个进程项每个进程项每个线程项每个线程项地址空间全局变量打开文件子进程定时器信
7、号和信号处理程序统计信息程序计数器寄存器堆栈状态 允许在同一个进程环境中有多个执行流（线程），允许在同一个进程环境中有多个执行流（线程），这些流在很大程度上相对独立，但共享相同的地址这些流在很大程度上相对独立，但共享相同的地址空间。空间。进程用来集合资源，而线程是进程用来集合资源，而线程是CPU中调度的实体。中调度的实体。The difference of the two kind of OS临界区的定义：临界区的定义：假如两个或更多的进程需要访问一个不可共享的资源假如两个或更多的进程需要访问一个不可共享的资源（打印机），在执行过程中，每个进程都给该（打印机），在执行过程中，每个进程都给该I/
8、O设备发送设备发送命令，接受状态信息，发送数据，接收数据。我们把这类资命令，接受状态信息，发送数据，接收数据。我们把这类资源称作临界资源，使用临界资源的那一部分程序称作成程序源称作临界资源，使用临界资源的那一部分程序称作成程序的临界区。的临界区。一次只允许有一个程序在临界区中。一次只允许有一个程序在临界区中。互斥的定义：互斥的定义：用某种手段，避免多个进程访问同一个临界区的操作用某种手段，避免多个进程访问同一个临界区的操作叫做互斥。叫做互斥。互斥，指多个进程不能同时使用同一个共享资源；互斥，指多个进程不能同时使用同一个共享资源；死锁，指多个进程互不相让，都得不到足够的资源；死锁，指多个进程互不
9、相让，都得不到足够的资源；饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源相互感知的程度相互感知的程度 交互关系交互关系 一个进程对其他进程一个进程对其他进程 的影响的影响 潜在的控制问题潜在的控制问题 相互不感知相互不感知(完全不完全不了解其它进程的存了解其它进程的存在在)竞争竞争(competition)一个进程的操作对其一个进程的操作对其他进程的结果无影响他进程的结果无影响 互斥，死锁（可释放的互斥，死锁（可释放的资源），饥饿资源），饥饿 间接感知间接感知(双方都与双方都与第三方交互，如共享第三方交互，如共享资源资源)通过共
10、享进行协作通过共享进行协作 一个进程的结果依赖一个进程的结果依赖于从其他进程获得的于从其他进程获得的信息信息 互斥，死锁（可释放的互斥，死锁（可释放的资源），饥饿，数据一资源），饥饿，数据一致性致性 直接感知直接感知(双方直接双方直接交互，如通信交互，如通信)通过通信进行协作通过通信进行协作 一个进程的结果依赖一个进程的结果依赖于从其他进程获得的于从其他进程获得的信息信息 死锁，饥饿死锁，饥饿 忙等待形式的互斥忙等待形式的互斥*Close interrupt（关中段）（关中段）the simplest way,when the process entered the critical area
11、.It will close the interrupt,when it is finished,it will open the interrupt again;Shortage:it is fool to let the user has right to start or close interrupt.and to multi-processor PC,close interrupt is effected to one processor,and to other processors,the visit of the shared memory will continue.*锁变量
12、锁变量对于某一个临界区，在它之外设置一个锁，每个进对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开程要进入临界区的时候，首先要测试这把锁，如果锁打开着的（锁的值为着的（锁的值为0 0），则该进程可以进入（并将锁置），则该进程可以进入（并将锁置1 1），），如果关闭着的如果关闭着的（锁的值为（锁的值为1），则该进程不能够进入；同，则该进程不能够进入；同样，一个进程进入了临界区后就把这把锁给锁上，当它出样，一个进程进入了临界区后就把这把锁给锁上，当它出来后再打开这把锁，这样会对这个临界区有很好的保护作来后再打开这把锁，这样会对这个临界区有很好的保护作用
13、，实现了互斥。用，实现了互斥。临界区临界区锁锁Process 1Process 2Process 3但是矛盾依然有，但是矛盾依然有，跟跟SpoolerSpooler目录一目录一样。样。严格轮换法是指几个进程轮换进入某一临界区，且顺序严格轮换法是指几个进程轮换进入某一临界区，且顺序不能紊乱。不能紊乱。While(TRUE)while(turn!=0);/*wait*/critical_region();turn=1;noncritical_region();While(TRUE)while(turn!=1);/*wait*/critical_region();turn=0;noncritical
14、_region();初始值：初始值：turn=0;忙等待：进程不断地读忙等待：进程不断地读turn的值，只是他没有做任何有的值，只是他没有做任何有意义的事（等待），而且浪费了意义的事（等待），而且浪费了cpu的时间（忙）。故的时间（忙）。故称作忙等待称作忙等待 busy waiting turn=1正常情况正常情况假如两个进程：假如两个进程：首先首先A进程进入，使用临界区后，修改进程进入，使用临界区后，修改turn的值，然后的值，然后进入非临界区，然后进入非临界区，然后B进程进入，根据判断，发觉可以进入，进程进入，根据判断，发觉可以进入，就进入临界区，执行完后，修改临界区的值，在然后进入自己就
15、进入临界区，执行完后，修改临界区的值，在然后进入自己的非临界区。依次的非临界区。依次A、B轮换执行。轮换执行。异常异常:(此时虽然不会竞争，但浪费了资源此时虽然不会竞争，但浪费了资源)如果进程如果进程A的非临界区很快能执行完，而进程的非临界区很快能执行完，而进程B的非临界区却的非临界区却非常慢，则会：非常慢，则会：ttt 此时，此时，两个进程的完成时间的衡量就应该两个进程的完成时间的衡量就应该按照慢的那个来衡量按照慢的那个来衡量，而且，如果任何一个进，而且，如果任何一个进程死掉了，则进程则会永远堵塞下去，不管是程死掉了，则进程则会永远堵塞下去，不管是在临界区内还是在临界区外。在临界区内还是在临
16、界区外。荷兰数学家荷兰数学家T.Dekker通过设置通过设置加警告变量加警告变量的方法的方法来回避这种情况的发生，但警告的同时也必须来回避这种情况的发生，但警告的同时也必须能够监测其他进程此时对临界区的使用情况，能够监测其他进程此时对临界区的使用情况，即出现了即出现了Dekker算法。参考别的书籍。（操算法。参考别的书籍。（操作系统内核与设计原理作系统内核与设计原理P154）Dekkers AlgorithmPeterson算法是正确的算法turn=j;描述可进入的进程（同时修改标志值）检查对方flag，如果不在临界区则自己进入空闲则入；否则再检查turn：保存的是较晚的一次赋值，则较晚的进程
17、等待，较早的进程进入先到先入，后到等待。硬件方法的优点硬件方法的优点 适用于任意数目的进程，在单处理器或多处理器上适用于任意数目的进程，在单处理器或多处理器上 简单，容易验证其正确性简单，容易验证其正确性 可以支持进程内存在多个临界区，只需为每个临界区设立一可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量个布尔变量硬件方法的缺点硬件方法的缺点 等待要耗费等待要耗费CPU时间，不能实现时间，不能实现让权等待让权等待 可能可能饥饿饥饿：从等待进程中随机选择一个进入临界区，有的：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上进程可能一直选不上 可能死锁（见下页）可能死锁（见
18、下页）对于对于Peterson和和TSL问题，都能够很好地实现互斥，但也都问题，都能够很好地实现互斥，但也都同时存在问题：同时存在问题：*忙等待，浪费忙等待，浪费CPU的资源。的资源。*进程的优先级有差别：当有两个进程，进程的优先级有差别：当有两个进程，A、B，A的优先的优先级高，处于就绪状态，而此时，级高，处于就绪状态，而此时，B在临界区内，由于优先级低，在临界区内，由于优先级低，故无法被调度，也就无法离开临界区，那故无法被调度，也就无法离开临界区，那A就只能够在临界区就只能够在临界区外等待。外等待。解决的途径就是引入新的概念：睡眠解决的途径就是引入新的概念：睡眠 唤醒唤醒睡眠：对应着在临界
19、区外的不停判断和等待；睡眠：对应着在临界区外的不停判断和等待；唤醒：对应着触发另一个满足条件的进程进入临界区。唤醒：对应着触发另一个满足条件的进程进入临界区。问题描述：问题描述：若干进程通过有限的共享缓冲区交换数据。其中，若干进程通过有限的共享缓冲区交换数据。其中，生产生产者者进程不断写入，而进程不断写入，而消费者消费者进程不断读出；共享缓冲区共进程不断读出；共享缓冲区共有有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。个；任何时刻只能有一个进程可对共享缓冲区进行操作。等待使用资源的消费者等待使用资源的消费者#define N 100int count=0;void producer(v
20、oid)while(TRUE)produce_item();if(count=N)sleep();enter_item();count=count+1;if(count=1)wakeup(consumer)void consumer(void)while(TRUE)remove_item();if(count=0)sleep();enter_item();count=count-1;if(count=N-1)wakeup(producer)对于生产者：对于生产者：只有当缓冲区里为零的时候，这时候消费者才有可能睡觉；只有当缓冲区里为零的时候，这时候消费者才有可能睡觉；对于消费者：对于消费者：只有
21、当缓冲区里装满的时候，这时候生产者才有可能睡觉。只有当缓冲区里装满的时候，这时候生产者才有可能睡觉。导致的问题：类导致的问题：类SpoolerSpooler目录问题目录问题 缓冲区为空，消费者检查，得到缓冲区为空，消费者检查，得到count=0,count=0,但未睡觉的时但未睡觉的时候，被调度程序挂起，此时它将保留一个局部变量来存储候，被调度程序挂起，此时它将保留一个局部变量来存储countcount的值，此时生产者开始工作并向缓冲区内放入资源，当资源等的值，此时生产者开始工作并向缓冲区内放入资源，当资源等于于1 1后，向消费者发送唤醒信号，而此时消费者没有睡眠，等消后，向消费者发送唤醒信号
22、，而此时消费者没有睡眠，等消费者被恢复以后，检查自己存储过的费者被恢复以后，检查自己存储过的countcount，发觉它等于零，则，发觉它等于零，则开始睡眠，而生产者则不停生产，当缓冲区满了以后自己也开开始睡眠，而生产者则不停生产，当缓冲区满了以后自己也开始睡眠，这时候他们就都处于睡眠状态。始睡眠，这时候他们就都处于睡眠状态。1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到他接受到一个特定
23、的信号。为了发信号，需要一个特殊的变量-信号量s为了通过信号量s传送信号，进程可执行原语signal(s);为了通过信号量s接收信号，进程可执行原语wait(s);1.一个信号量可以初始化为非负数一个信号量可以初始化为非负数2.Wait操作是信号量减一，如果值变为了负数，则执行操作是信号量减一，如果值变为了负数，则执行wait的进程被阻塞；的进程被阻塞；Signal操作是信号量加一，如果值不是正数，则被操作是信号量加一，如果值不是正数，则被wait操作操作阻塞的进程被解除阻塞。阻塞的进程被解除阻塞。除了以上三种操作以外，没有任何其他地方可以检查或操除了以上三种操作以外，没有任何其他地方可以检查
24、或操作信号量。作信号量。Wait=PSignal=VStruct semaphore int count;queueType queue;Void wait(semaphore s)s.count-;if(s.count 0)place this process in s.queue;block this process;Void signal(semaphore s)s.count+;if(s.count =0)remove a process P from s.queue;place process P on ready list;此处的此处的wait wait 和和signal sign
25、al 都是原子操都是原子操作，不会被中断影响。作，不会被中断影响。Void waitB(binary_semaphore s)if(s.value=1)s.value=0;else place this process in s.queue;block this process;Void signalB(binary_semaphore s)if(s.queue.is_empty()s.value=1;else remove a process P from s.queue;place process P on ready list;Struct binary_semaphore enmu(z
26、ero,one)value;queueType queuw;P原语wait(s)s.count-;/表示申请一个资源;if(s.count 0)/表示没有空闲资源;调用进程进入等待队列s.queue;阻塞调用进程;V原语signal(s)s.count+;/表示释放一个资源；if(s.count=0)/表示有进程处于阻塞状态；从等待队列s.queue中取出一个进程P;进程P进入就绪队列;利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语
27、则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏V(mutex);critical sectionremainder sectionP(mutex);#define N 100 /缓冲区内槽数缓冲区内槽数Typedef int semaphore;semaphore mutex=1;semaphore full=0;semaphore empty=N;Void producer(void)int item;while(TRUE)produce_item(&item);down(&empty);down(&mutex);ent
28、er_item(item);up(&mutex);up(&full);Void consumer(void)int item;while(TRUE)down(&full);down(&mutex);remove_item(item);up(&mutex);up(&empty);consumer_item(item);上面程序是利用信号量互斥来解决生产者上面程序是利用信号量互斥来解决生产者-消费者问题的。消费者问题的。其中：其中：信号量mutex用于互斥，保证任意时刻只能有一个进程读写缓冲区和相关的变量，保证了临界区、临界资源的合理安全使用。信号量full和empty用来保证一定的时间顺序发生或
29、不发生，它用来通知生产者和消费者，保证了当缓冲区满的时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。1.信号量同步的缺点信号量同步的缺点同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；2.2.管程的引入管程的引入1973年，Hoare和Hanson所提出；其基本思想是把信
30、号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。3.管程的主要特性模块化：一个管程是一个
31、基本程序单位，可以单独编译；抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的.4.管程的实现要素管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程互斥进入；管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作；5.条件变量(condition)由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入
32、管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量-条件变量。每个表示一种等待原因，并不取具体数值相当于每个原因对应一个队列。6.管程的格式（类Pascal）TYPE TYPE monitor_namemonitor_name=MONITOR;=MONITOR;共享变量说明共享变量说明define define 本管程内所定义、本管程外可调用的过程（函数）名本管程内所定义、本管程外可调用的过程（函数）名字表字表use use 本管程外所定义、本管程内将调用的过程（函数）名本管程外所定义、本管程内将调用的过程（函数）名字表字表PROCEDURE P
33、ROCEDURE 过程名（形参表）；过程名（形参表）；过程局部变量说明；过程局部变量说明；BEGINBEGIN语句序列；语句序列；END;END;.7.管程的的组成名称：为每个共享资源设立一个管程数据结构说明：一组局部于管程的控制变量操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。初始化代码：对控制变量进行初始化的代码生产者生产者消费者的管程实现消费者的管程实现 Monitor ProducerConsumer condition full,empty;integer cou
34、nt;procedure enter;begin if count=N then wait(full);enter_item;count:=count+1;if count=1 then signal(empty)end procedure remove;begin if count=0 then wait(empty);remove_item;count:=count-1;if count=N-1 then signal(full)end count:=0;End monitor;管程与信号量的比较管程与信号量的比较 由于管程的机制，在某个时刻，只能有一个管程过程是活由于管程的机制，在某个时
35、刻，只能有一个管程过程是活跃的，就类似于原语操作一样，也能够很好地解决跃的，就类似于原语操作一样，也能够很好地解决Spooler目目录的问题，而且更为简洁，在使用的过程中，能够直接分析录的问题，而且更为简洁，在使用的过程中，能够直接分析代码，更容易理解使用。而且它的互斥操作是由编译器所支代码，更容易理解使用。而且它的互斥操作是由编译器所支持的，更为安全，不宜出错。持的，更为安全，不宜出错。用信号量可实现进程间的同步，但由于信号量的控制分布用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同在整个程序中，其正确性分析很困难。管程是管理进程间同步的
36、机制，它保证进程互斥地访问共享变量，并方便地阻塞步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。比信号量好控制。弊端，弊端，支持管程的编程语言太少，因为它要求编译器的支支持管程的编程语言太少，因为它要求编译器的支持持，而信号量对于一个操作系统来说是很容易添加的；他们，而信号量对于一个操作系统来说是很容易添加的；他们都是用来解决访问同一个公共存储器的一个或多个都是用来解决访问同一个公共存储器的一个或多个CPU的互的互斥问题。通过将信号量放入共享内存中并用斥问题。通过将信号量
37、放入共享内存中并用TSL指令来保护他指令来保护他们，可以避免竞争。但对于一个具有多个们，可以避免竞争。但对于一个具有多个CPU，且每个，且每个CPU有自己的内存，有一个局域网相连的分布式系统来说，这些有自己的内存，有一个局域网相连的分布式系统来说，这些原语将完全失败。而管程由于编程语言的限制很难被实际应原语将完全失败。而管程由于编程语言的限制很难被实际应用。所以这两种都不是很实际的解决方法。用。所以这两种都不是很实际的解决方法。需要新的解决方法。需要新的解决方法。2）消息接收的处理）消息接收的处理发送者发送消息，接收者收到后发送一个应答，这时：发送者发送消息，接收者收到后发送一个应答，这时：*
38、应答信息被发送者收到，则继续发送新的消息；应答信息被发送者收到，则继续发送新的消息；*应答信息丢失，则重发刚才的信息，此时，接收者需要区应答信息丢失，则重发刚才的信息，此时，接收者需要区分消息的新旧，利用给消息加上连续序号来解决；分消息的新旧，利用给消息加上连续序号来解决；3）消息系统消息系统设计的其他注意事项设计的其他注意事项*系统需要解决进程命名的问题，保证消息的正确发送和接系统需要解决进程命名的问题，保证消息的正确发送和接收；收；*效率的提升：严格控制系统中所用信息的长度，保证能够效率的提升：严格控制系统中所用信息的长度，保证能够送入寄存器。送入寄存器。使用消息的互斥使用消息的互斥此处的
39、此处的mailboxmailbox表示一种数据表示一种数据结构，它是用来对一定数量结构，它是用来对一定数量的消息进行缓冲的地方，一的消息进行缓冲的地方，一般在信箱创建时确定消息的般在信箱创建时确定消息的数量。数量。描述：描述：这里使用的是阻塞receive原语和无阻塞send原语，一组并发进程共享一个信箱mutex，它可以供所有的进程在发送和接收时使用，该信箱被初始化成一个无内容的消息。希望进入临界区的进程首先试图接收一条消息，如果信箱为空，则该进程被阻塞，一旦进程获得消息，它执行它的临界区，然后把该消息放回信箱。消息函数可以看成是在进程之间传递的一个令牌。对上述方案假设如果有多个进程并发执行
40、接收操作，则：*如果有一条消息，它仅仅被传递给一个进程，其他进程被阻塞。*如果消息队列为空，所有进程被阻塞，当有一条消息可用时，只有一个阻塞进程被激活并得到这条消息。Void producer(void)int item;message m;/*消息缓冲区消息缓冲区*/while(TRUE)produce_item(&item);/*产生数据放入缓冲区产生数据放入缓冲区*/receive(consumer,&item);/*等待空消息到达了，进入等待空消息到达了，进入*/build_message(&m,item);/*构造消息供发送构造消息供发送*/send(consumer,&m);/*向
41、消费者发送一个数据项向消费者发送一个数据项*/2.3.1哲学家进餐问题哲学家进餐问题#define N 5/*哲学家的人数哲学家的人数*/void philosopher(int i)/*给哲学家编号给哲学家编号*/while(TRUE)think();/*思考思考*/takefork(i);/*取叉子取叉子*/takefork(i+1)%N);/*取右边叉子取右边叉子*/eat();/*进餐进餐*/putfork(i);/*放下左边叉子放下左边叉子*/putfork(i+1)%N);/*放下右边叉子放下右边叉子*/上述算法的局限与改进上述算法的局限与改进极限阻塞：极限阻塞：当当5个哲学家同时
42、拿起叉子时，就会同时处于阻塞，然后同时个哲学家同时拿起叉子时，就会同时处于阻塞，然后同时放下，再同时拿起放下，再同时拿起.-饥饿态饥饿态 解决办法解决办法1：加随机数，使哲学家们拿叉子的时间错开，可：加随机数，使哲学家们拿叉子的时间错开，可以解决问题。以解决问题。缺陷：太不可靠缺陷：太不可靠 解决办法解决办法2：在：在think后加上一个后加上一个mutex,使哲学家都要首先使哲学家都要首先访问临界区，才能进餐，可以解决问题。访问临界区，才能进餐，可以解决问题。缺陷：浪费，因为实际上可以有缺陷：浪费，因为实际上可以有2个同时进餐，但实际上加个同时进餐，但实际上加了互斥后，只能有一个进餐，其了互
43、斥后，只能有一个进餐，其4人都要等待。人都要等待。#define N 5/*哲学家的人数哲学家的人数*/#define LEFT(i-1)%N/*某个哲学家左边人的号码某个哲学家左边人的号码*/#define RIGHT(i+1)%N/*某个哲学家右边人的号码某个哲学家右边人的号码*/#define THINKING 0/*思考思考*/#define HUNGRY 1/*想取叉子想取叉子*/#define EATING 2/*哲学家在进餐哲学家在进餐*/typedef int semaphore;/*信号量信号量*/int state N;/*记录每个人状态的数组记录每个人状态的数组*/Sem
44、aphore mutex=1;/*临界区的互斥临界区的互斥*/semaphore s N;/*各个哲学家的信号量各个哲学家的信号量*/void philosopher(int i)/*i:哲学家的号码哲学家的号码,从从0 到到 N-1*/while(TRUE)/*循环循环*/think();/*思考思考*/takeforks(i);/*想取两个叉子，有可能阻塞想取两个叉子，有可能阻塞*/eat();/*进餐进餐*/putforks(i);/*放回两只叉子放回两只叉子*/void takeforks(int i)/*i:某个哲学家的编号某个哲学家的编号,从从 0 到到 N-1*/down(&mu
45、tex);/*进入临界区进入临界区*/statei=HUNGRY;/*记录下第记录下第 i 个哲学家饥饿个哲学家饥饿*/test(i);/*尝试去拿两个叉子尝试去拿两个叉子*/up(&mutex);/*退出临界区退出临界区*/down(&si);/*得不到就阻塞得不到就阻塞*/void putforks(i)/*i:某个哲学家的编号某个哲学家的编号,从从 0 到到 N-1*/down(&mutex);/*进入临界区进入临界区*/statei=THINKING;/*记录下第记录下第 i 个哲学家已经完成进餐个哲学家已经完成进餐*/test(LEFT);/*测试左侧是否能进餐测试左侧是否能进餐*/
46、test(RIGHT);/*测试右侧是否能进餐测试右侧是否能进餐*/up(&mutex);/*退出临界区退出临界区 */void test(i)/*i:某个哲学家的编号某个哲学家的编号,从从 0 到到 N-1*/if(statei=HUNGRY&stateLEFT!=EATING&stateRIGHT!=EATING)statei=EATING;up(&si);/*唤醒阻塞唤醒阻塞*/如果第一个进入，通过如果第一个进入，通过test来表示自己的状态，表示可以进来表示自己的状态，表示可以进餐，如果他完成以后，通过餐，如果他完成以后，通过test标识可以进餐的人的标号，标识可以进餐的人的标号，在在
47、test函数里将阻塞的进程唤醒，即每个哲学家放下叉子之函数里将阻塞的进程唤醒，即每个哲学家放下叉子之后，再去判断两侧的是否有阻塞，如果有，将它唤醒，之后，后，再去判断两侧的是否有阻塞，如果有，将它唤醒，之后，放开对临界区的控制，让两侧的哲学家进餐。放开对临界区的控制，让两侧的哲学家进餐。函数只以函数只以philosopher为主函数，其余的均为被调用的函为主函数，其余的均为被调用的函数。不是单独的进程。数。不是单独的进程。属于多个进程访问有限资源类问题。属于多个进程访问有限资源类问题。2.3.2 读者读者-写者问题写者问题问题描述：问题描述：有一个许多进程共享的数据区，这个数据区可以是一个文有
48、一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间，甚至可以是一组处理器寄存器，有件或者主存的一块空间，甚至可以是一组处理器寄存器，有一些只读取这个数据区的进程，和一些只向数据区中写数据一些只读取这个数据区的进程，和一些只向数据区中写数据的进程。此外，还需要满足：的进程。此外，还需要满足：1.任意多的读进程可以同时读这个文件任意多的读进程可以同时读这个文件;2.一次只有一个写进程可以往文件中写；一次只有一个写进程可以往文件中写；3.如果一个写进程正在往文件中写，禁止任何读进程读文如果一个写进程正在往文件中写，禁止任何读进程读文件。件。数据库的访问模型数据库的访问模型typed
49、ef int semaphore;/*根据需要自定义根据需要自定义 */semaphore mutex=1;/*控制对控制对 rc的访问的访问*/semaphore db=1;/*控制对数据库的访问控制对数据库的访问*/int rc=0;/*正在读或准备读的进程数正在读或准备读的进程数*/void reader(void)while(TRUE)/*无限循环无限循环*/down(&mutex);/*禁止对禁止对 rc的访问的访问*/rc=rc+1;/*读者进入读者进入*/if(rc=1)down(&db);/*如果是第一个读者如果是第一个读者.*/up(&mutex);/*恢复恢复允许访问允许访
50、问 rc*/read_data_base();/*访问数据访问数据*/down(&mutex);/*禁止对禁止对 rc的访问的访问*/rc=rc-1;/*读者离开读者离开*/if(rc=0)up(&db);/*如果是最后一个读者如果是最后一个读者.*/up(&mutex);/*恢复允许访问恢复允许访问 rc*/use_data_read();/*非临界区非临界区*/void writer(void)while(TRUE)/*无限循环无限循环*/think_up_data();/*非临界区非临界区*/down(&db);/*锁定临界区锁定临界区数据库数据库*/write_data_base();
