操作系统设计与实现(第二章)

《操作系统设计与实现(第二章)》由会员分享，可在线阅读，更多相关《操作系统设计与实现(第二章)（113页珍藏版）》请在金锄头文库上搜索。

1、 操作系统设计与实现Chapter 2 Processes*The importance of process in an operating system*The importance of process in an operating system2.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

2、, sequential processes 顺序进程顺序进程2.1.1 The process modelCharacters:Characters:* All the * All the runnablerunnable software are organized into a number software are organized into a number of sequential of sequential processes; (in this chapter we called it processes) processes; (in this chapter we ca

3、lled it processes)* The process is an executing program;* The process is an executing program; The process include the values of the all the program The process include the values of the all the program counter, registerscounter, registers，and variables;(and variables;(进程包括程序计数器、进程包括程序计数器、进程包括程序计数器、

4、进程包括程序计数器、寄存器和变量的当前值。）寄存器和变量的当前值。）寄存器和变量的当前值。）寄存器和变量的当前值。）To these characters , it is easy to analysis the collection To these characters , it is easy to analysis the collection of the processes than keep track the rapid switch of CPUof the processes than keep track the rapid switch of CPUABCDOne On

5、e progprog count countABCDFour Four progprog count countABCDtimetimeprocessesprocessesProcess-ProgramProcess is an executing program, it has program, input, Process is an executing program, it has program, input, output, and state.output, and state.An example: An example: scientist prepare the cake

6、for his daughter.scientist prepare the cake for his daughter.Recipe: /Recipe: /resipiresipi/ / 食谱食谱食谱食谱* * A Process is an activity of some kind, It has a A Process is an activity of some kind, It has a program ,input, output, and a state, A single processor program ,input, output, and a state, A si

7、ngle processor may be shared among several processes, with some may be shared among several processes, with some scheduling algorithm being used to determine when to scheduling algorithm being used to determine when to stop work on one process and service a different one.stop work on one process and

8、 service a different one.理解进程和程序的区别：理解进程和程序的区别：CPU：计算机科学家程序1：烘制生日蛋糕的食谱数据：面粉、鸡蛋、糖和香草汁等对应的进程1：阅读食谱、取来各种原料以及烘制蛋糕的一系列动作的总和。事件：女儿被蜜蜂螫伤保存进程1的当前状态：计算机科学家就记录下自己照着食谱做到哪儿了。程序2：急救手册数据：药物等对应的进程2：实施医疗救治（高优先级进程）当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他离开时的那一步继续做下去。离开时的那一步继续做下去。进程的创建进程的创建1.系统初始化系统初始化2.

9、(1) 前台进程：同用户交互并替它们完成工作的哪些进程。3. (2) 后台进程：守护进程，处理网页、打印之类活动的进程。2.正在运行的一个进程执行了创建进程的系统调用。正在运行的一个进程执行了创建进程的系统调用。3.用户请求创建一个新进程。用户请求创建一个新进程。 在交互式系统中，用户可以通过键入命令启动程序。4. 批处理作业的初始化批处理作业的初始化 在操作系统认为有资源运行另一个作业时，它创建一个新的进程，并运行其输入队列中的一个作业。进程的终止进程的终止1.正常退出：正常退出：多数进程由于完成了它们的工作而终止。2.出错退出（自愿）出错退出（自愿）:进程发现了严重错误。3.严重错误（非自

10、愿）：严重错误（非自愿）：通常是由于程序中的错误所致。例如，执行了一条非法指令，引用了不存在的内存，或除数是零。4.被其它进程杀死：被其它进程杀死：当一个进程终止时，由该进程所创建的所有进程也都立即被杀死。Process hierarchies Any OS, to support process, it must provide some way Any OS, to support process, it must provide some way to create all the processes needed.to create all the processes needed.

11、Use fork( ) Use fork( ) to create a new process, the father to create a new process, the father process can create his child processes,0more, and process can create his child processes,0more, and later ,the process tree may appeared.later ,the process tree may appeared.In In MinixMinix, the root is

12、init, and it works in this way:, the root is init, and it works in this way:read info, create terminal, start program, NFS, read info, create terminal, start program, NFS, SMTP , WWW,FTPSMTP , WWW,FTPProcess States 进程之间经常需要交互、通信以及和其他进程同步。进程之间经常需要交互、通信以及和其他进程同步。进程之间经常需要交互、通信以及和其他进程同步。进程之间经常需要交互、通信以及和

13、其他进程同步。For Communication between processesFor Communication between processesexchange info among them, but, once more than one exchange info among them, but, once more than one processes processes lead to block lead to block*logically, it have to stop , it will. (wait our input)*logically, it have t

14、o stop , it will. (wait our input)*logically, it should continue, but it stopped, now,*logically, it should continue, but it stopped, now, the CPU may be occupied by another process. the CPU may be occupied by another process.1.运行态（运行态（Running，在该时刻实际占用处理机）。，在该时刻实际占用处理机）。2.就绪态（就绪态（Ready，可运行，因为其它进程正在运

15、行而暂时，可运行，因为其它进程正在运行而暂时被挂起）。被挂起）。3.阻塞态（阻塞态（Blocked，除非某种外部事件发生，否则不能运，除非某种外部事件发生，否则不能运行）。行）。RunningBlockedReady12341. Process blocks for input1. Process blocks for input2. Scheduler picks another 2. Scheduler picks another processprocess3. Scheduler picks this process3. Scheduler picks this process4. I

16、nput becomes available4. Input becomes availableThree States of process, and four transition are thereThree States of process, and four transition are there123n-3 n-2n-1SchedulerSchedulerUser processUser processDisk processDisk processTerminal processTerminal processIn this model, we dont care In th

17、is model, we dont care about the interruptabout the interrupt2.1.2 Implementation of Processes*Process Table *Process Table (an array of structures)(an array of structures)（进程表）（进程表）（进程表）（进程表）each process is a record of this table, and each each process is a record of this table, and each record inc

18、lude the state of the process, program record include the state of the process, program counter, stack pointer, and allocation of memory.; counter, stack pointer, and allocation of memory.; thus, when the process is in ready state, all the info thus, when the process is in ready state, all the info

19、wont lose.wont lose.In MINIX, the process management, memory In MINIX, the process management, memory management, and file management are each handled by management, and file management are each handled by separate modules within the system ,so the process separate modules within the system ,so the

20、process table is partitioned.table is partitioned.Look at the Look at the picpic: :Interrupt Vector（中断向量）（中断向量）An interruption ,it relate to each kinds of I/O device An interruption ,it relate to each kinds of I/O device (hardware), it contain the (hardware), it contain the address of the interrupt

21、address of the interrupt service procedure.service procedure.The interrupt procedure store the current The interrupt procedure store the current variables and info to stacks, and did some works related variables and info to stacks, and did some works related to its recover . Now ,the pre process is

22、stored, and the to its recover . Now ,the pre process is stored, and the new one could continue. When it is finished, the old new one could continue. When it is finished, the old one could be recalled ,and runs smoothly, just nothing one could be recalled ,and runs smoothly, just nothing had happene

23、d.had happened.Of course the interrupt must related to their priority.Of course the interrupt must related to their priority.The real procedure is:The real procedure is:2.1.3 Threads（线程）（线程）1. Concept1. Conceptto the traditional process, one process just has one to the traditional process, one proce

24、ss just has one control cluecontrol clue（控制流）（控制流）（控制流）（控制流） and one program counter. In and one program counter. In modern OS, more and more OS support the multi-modern OS, more and more OS support the multi-control clue in a process, and we call these control control clue in a process, and we call

25、 these control clue threads.clue threads.The real application of threads model The real application of threads model from the application to show its importance to OSfrom the application to show its importance to OS多线程的应用（多线程的应用（1） explorer explorer netscapenetscape（网络浏览器）（网络浏览器）（网络浏览器）（网络浏览器）许多许多许多

26、许多WebWeb页面都包含有多幅很小的图像。页面都包含有多幅很小的图像。页面都包含有多幅很小的图像。页面都包含有多幅很小的图像。site: the images folder lies D:siteimagessite: the images folder lies D:siteimagesprocess: build up one connectionprocess: build up one connectionthreads: build up more connection threads: build up more connection 在浏览器内设立多个进程，同时请求传输多幅图像

27、，可节在浏览器内设立多个进程，同时请求传输多幅图像，可节在浏览器内设立多个进程，同时请求传输多幅图像，可节在浏览器内设立多个进程，同时请求传输多幅图像，可节省建立和释放链接的时间。省建立和释放链接的时间。省建立和释放链接的时间。省建立和释放链接的时间。To small size files, the connection-building needs To small size files, the connection-building needs more time than transporting.more time than transporting. transmitting us

28、e . transmitting use .rarrar .zip than folder. .zip than folder.多线程的应用（多线程的应用（2）网络蚂蚁网络蚂蚁(NetAnts)是从因特网下载文件的工具软件，设计特是从因特网下载文件的工具软件，设计特点如下：点如下：(A)支持支持HTTP和和FTP协议，可同时下载协议，可同时下载1-5个文件；个文件；(B)可随时中止正在下载的任务，任务将自动保存当前状可随时中止正在下载的任务，任务将自动保存当前状态；态；(C)支持拖放，可从浏览器中将链接拖入任务列表；支持拖放，可从浏览器中将链接拖入任务列表；(D)裁剪板自动监视，并可指定将捕获

29、的文件类型；裁剪板自动监视，并可指定将捕获的文件类型；(E)捕获浏览器的动作，当用户在浏览器中单击链接时，捕获浏览器的动作，当用户在浏览器中单击链接时，网络蚂蚁将自动激活。网络蚂蚁将自动激活。 A AB BTo 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进

30、程和线程的区别进程和线程的区别每个进程项每个进程项每个线程项每个线程项地址空间全局变量打开文件子进程定时器信号和信号处理程序统计信息程序计数器寄存器堆栈状态 允许在同一个进程环境中有多个执行流（线程），允许在同一个进程环境中有多个执行流（线程），这些流在很大程度上相对独立，但共享相同的地址这些流在很大程度上相对独立，但共享相同的地址空间。空间。 进程用来集合资源，而线程是进程用来集合资源，而线程是CPU中调度的实体。中调度的实体。To B: these threads share the same address spaceTo B: these threads share the same

31、address spaceAnd these threads can write the information to the same And these threads can write the information to the same place ,the same file.place ,the same file.So the So the tabletable will can be used to will can be used to threads,thenthreads,then the threads the threads can be restorecan b

32、e restore、block block 、ready .ready .Meaning :Meaning :all the program can use the resources more all the program can use the resources more efficiently, improved the efficiently, improved the OSsOSs performance. performance.2.Problems2.ProblemsTo different OS, the problems are different.To differen

33、t OS, the problems are different.1 1）OS dont know the existence of threadsOS dont know the existence of threadsThe control of threads will by in user space.The control of threads will by in user space. Then many threads packages are there. Then many threads packages are there. egeg P-threads P-threa

34、ds2) OS know the existence of threads2) OS know the existence of threadsthe kernel will create the table to maintain the the kernel will create the table to maintain the threads, threads table.threads, threads table.The difference of the two kind of OSThe first oneThe first oneThe secondThe secondTh

35、reads switched quickly Threads switched quickly 线程线程线程线程完全在用户空间进行管理完全在用户空间进行管理完全在用户空间进行管理完全在用户空间进行管理Threads switched slow, the kernel has Threads switched slow, the kernel has to judge the process and the other to judge the process and the other processprocessOne thread blocked , the kernel One thre

36、ad blocked , the kernel may be blocked. (to may be blocked. (to flashgetflashget, when , when the network is broken, all the the network is broken, all the threads of this process will waste a threads of this process will waste a lot of resource.lot of resource.One thread blocked , the kernel One th

37、read blocked , the kernel may choose another one to run.may choose another one to run.Conclusion:Conclusion:Get them together, adopt them two.Get them together, adopt them two.3) The new problems3) The new problems! Parent-process & child-process! Parent-process & child-processparents process has ma

38、ny child threads, then how parents process has many child threads, then how about the child-processabout the child-process! Multi processes share the data-structure! Multi processes share the data-structureone thread is closing a file, while the file is be one thread is closing a file, while the fil

39、e is be reading by another thread.reading by another thread.one thread is apply the memory, but now , switch one thread is apply the memory, but now , switch happened, another threads will reapply .happened, another threads will reapply .! Error reports! Error reportsin Unix, the returned error valu

40、e is stored in a in Unix, the returned error value is stored in a variable, when one is stored a value there, then another variable, when one is stored a value there, then another cleared the value, and write a new value to there, then?cleared the value, and write a new value to there, then?2.2 Inte

41、r Processes Communication (IPC)CONTENTS:CONTENTS:How a process to send messages to another one;How a process to send messages to another one;We must make sure the processes cant effect each We must make sure the processes cant effect each other when they are visiting the other when they are visiting

42、 the critical areacritical area; ;When the reliable relations are there, When the reliable relations are there, how to design how to design their proper order.their proper order.2.2.1 Race condition（竞争条件）（竞争条件）. . . . .abcabcProg.cProg.cProg.nProg.n4 45 56 67 7Process AProcess AProcess BProcess BOut

43、=4Out=4In=7In=7SpoolerSpooler1.1.To Process A: read In, To Process A: read In, write 7 to Next-free-slot write 7 to Next-free-slot (local);(local);2.2.Interruption: A blocked, Interruption: A blocked, and B came in;and B came in;3.3.B read In, got 7, then B read In, got 7, then save name to slot7; s

44、ave name to slot7; In+1=8, B will think his job In+1=8, B will think his job is finished;is finished;4.4.A came back, and read A came back, and read local next-free-slot, save local next-free-slot, save name to slot 7,and next-name to slot 7,and next-free-slot+1=8, save 8 to In.free-slot+1=8, save 8

45、 to In.5.5. B will never be print. B will never be print.打印机假脱机系统打印机假脱机系统打印机假脱机系统打印机假脱机系统2.2.2 Critical region - Critical sectionMutual exclusionMutual exclusion（互斥）（互斥）（互斥）（互斥）: : any share resource ( memoryany share resource ( memory、file )may happen the file )may happen the similar errors (spoole

46、r) , we have to take this measure to similar errors (spooler) , we have to take this measure to prevent the race.prevent the race.When the race will happenWhen the race will happen? ?If the race happens between two processes, they wont If the race happens between two processes, they wont race from t

47、he beginning to the end. Only when they visit the race from the beginning to the end. Only when they visit the same memory area or the same file, the race will happen.same memory area or the same file, the race will happen.Here , if a program segment could visit the shared Here , if a program segmen

48、t could visit the shared memory, we called the program memory, we called the program segment critical region or segment critical region or critical section.(critical section.(临界区或临界段）临界区或临界段）临界区或临界段）临界区或临界段）临界区的定义：临界区的定义： 假如两个或更多的进程需要访问一个不可共享的资源假如两个或更多的进程需要访问一个不可共享的资源（打印机），在执行过程中，每个进程都给该（打印机），在执行过程中

49、，每个进程都给该I/O设备发送命设备发送命令，接受状态信息，发送数据，接收数据。我们把这类资源令，接受状态信息，发送数据，接收数据。我们把这类资源称作临界资源，使用临界资源的那一部分程序称作成程序的称作临界资源，使用临界资源的那一部分程序称作成程序的临界区。临界区。一次只允许有一个程序在临界区中。一次只允许有一个程序在临界区中。互斥的定义：互斥的定义：用某种手段，避免多个进程访问同一个临界区的操作用某种手段，避免多个进程访问同一个临界区的操作叫做互斥。叫做互斥。进程的交互关系：可以按照相互感进程的交互关系：可以按照相互感知的程度来分类知的程度来分类互斥，指多个进程不能同时使用同一个共享资源；互

50、斥，指多个进程不能同时使用同一个共享资源；死锁，指多个进程互不相让，都得不到足够的资源；死锁，指多个进程互不相让，都得不到足够的资源；饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）相互感知的程度相互感知的程度 交互关系交互关系 一个进程对其他进程一个进程对其他进程 的影响的影响 潜在的控制问题潜在的控制问题 相互不感知相互不感知(完全不完全不了解其它进程的存了解其它进程的存在在) 竞争竞争(competition) 一个进程的操作对其一个进程的操作对其他进程的结果无影响他进程的结果无影响 互斥，死锁（可释放的互斥，死锁（可释放

51、的资源），饥饿资源），饥饿 间接感知间接感知(双方都与双方都与第三方交互，如共享第三方交互，如共享资源资源) 通过共享进行协作通过共享进行协作 一个进程的结果依赖一个进程的结果依赖于从其他进程获得的于从其他进程获得的信息信息 互斥，死锁（可释放的互斥，死锁（可释放的资源），饥饿，数据一资源），饥饿，数据一致性致性 直接感知直接感知(双方直接双方直接交互，如通信交互，如通信) 通过通信进行协作通过通信进行协作 一个进程的结果依赖一个进程的结果依赖于从其他进程获得的于从其他进程获得的信息信息 死锁，饥饿死锁，饥饿 How to solve it?How to solve it?if we coul

52、d settle the processes very well, to if we could settle the processes very well, to avoid the processes visit the shared memory at the same avoid the processes visit the shared memory at the same time, then the race will be solved.time, then the race will be solved. To any good plans, we should make

53、 sure that: To any good plans, we should make sure that:! Any two processes cant stayed in the critical area at ! Any two processes cant stayed in the critical area at the same time;the same time;! We shouldnt do any supposition to CPUs speed and ! We shouldnt do any supposition to CPUs speed and nu

54、mber;number;! The process out of critical area cant block other ! The process out of critical area cant block other process;process;! We shouldnt let the process keep on waiting out of ! We shouldnt let the process keep on waiting out of the critical area.the critical area.2.2.3 Exclusion of busy wa

55、iting忙等待形式的互斥忙等待形式的互斥* Close interrupt（关中段）（关中段）the simplest way, when the process entered the critical area. 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

56、interrupt is effected to one processor, and to other processors, the visit of the shared memory will continue.* 锁变量锁变量对于某一个临界区，在它之外设置一个锁，每个进对于某一个临界区，在它之外设置一个锁，每个进程要进入临界区的时候，首先要测试这把锁，如果锁打开程要进入临界区的时候，首先要测试这把锁，如果锁打开着的（锁的值为着的（锁的值为0 0），则该进程可以进入（并将锁置），则该进程可以进入（并将锁置1 1），），如果关闭着的如果关闭着的（锁的值为（锁的值为1） ，则该进程不能够进

57、入；同，则该进程不能够进入；同样，一个进程进入了临界区后就把这把锁给锁上，当它出样，一个进程进入了临界区后就把这把锁给锁上，当它出来后再打开这把锁，这样会对这个临界区有很好的保护作来后再打开这把锁，这样会对这个临界区有很好的保护作用，实现了互斥。用，实现了互斥。临界区临界区锁锁Process 1Process 2Process 3但是矛盾依然有，但是矛盾依然有，跟跟SpoolerSpooler目录一目录一样。样。严格轮换法（交替法）严格轮换法（交替法） 严格轮换法是指几个进程轮换进入某一临界区，且顺序严格轮换法是指几个进程轮换进入某一临界区，且顺序不能紊乱。不能紊乱。While ( TRUE

58、)while ( turn !=0 ); /*wait*/critical_region ( ) ;turn=1;noncritical_region ( ) ;While ( TRUE )while ( turn !=1 ); /*wait*/critical_region ( ) ;turn=0;noncritical_region ( ) ;初始值：初始值： turn=0;忙等待：进程不断地读忙等待：进程不断地读turn的值，只是他没有做任何有的值，只是他没有做任何有意义的事（等待），而且浪费了意义的事（等待），而且浪费了cpu的时间（忙）。故的时间（忙）。故称作忙等待称作忙等待 bus

59、y waiting turn=1正常情况正常情况假如两个进程：假如两个进程：首先首先A进程进入，使用临界区后，修改进程进入，使用临界区后，修改turn的值，然后的值，然后进入非临界区，然后进入非临界区，然后B进程进入，根据判断，发觉可以进入，进程进入，根据判断，发觉可以进入，就进入临界区，执行完后，修改临界区的值，在然后进入自己就进入临界区，执行完后，修改临界区的值，在然后进入自己的非临界区。依次的非临界区。依次A、B轮换执行。轮换执行。异常异常: (此时虽然不会竞争，但浪费了资源此时虽然不会竞争，但浪费了资源)如果进程如果进程A的非临界区很快能执行完，而进程的非临界区很快能执行完，而进程B的

60、非临界区却非的非临界区却非常慢，则会：常慢，则会：turn=1turn=1turn=0turn=0turn=1turn=1Waiting ( turn ) = 1Waiting ( turn ) = 1A AB Bttt 此时，此时，两个进程的完成时间的衡量就应该两个进程的完成时间的衡量就应该按照慢的那个来衡量按照慢的那个来衡量，而且，如果任何一个进，而且，如果任何一个进程死掉了，则进程则会永远堵塞下去，不管是程死掉了，则进程则会永远堵塞下去，不管是在临界区内还是在临界区外。在临界区内还是在临界区外。荷兰数学家荷兰数学家T.Dekker通过设置通过设置加警告变量加警告变量的方法的方法来回避这种

61、情况的发生，但警告的同时也必须来回避这种情况的发生，但警告的同时也必须能够监测其他进程此时对临界区的使用情况，能够监测其他进程此时对临界区的使用情况，即出现了即出现了Dekker算法。参考别的书籍。（操算法。参考别的书籍。（操作系统内核与设计原理作系统内核与设计原理P154）Dekkers AlgorithmProcess 0Process 0Process 1Process 1.flag0 = true;flag0 = true;flag1 = true; flag1 = true; while (flag1 = = true)while (flag1 = = true)while (fla

62、g0 = = true)while (flag0 = = true) if (turn = = 1) if (turn = = 1) if (turn = = 0) if (turn = = 0) flag0 = false;flag0 = false;flag1 = false;flag1 = false;while (turn = = 1);while (turn = = 1);while (turn = = 0);while (turn = = 0);flag0 = true;flag0 = true; flag1 = true;flag1 = true; ;turn = 1;turn

63、= 1;turn = 0;turn = 0;flag0 = false;flag0 = false;flag1 = false;flag1 = false;.Peterson算法算法- ( (两个进程的两个进程的两个进程的两个进程的PetersonPeterson算法算法算法算法) )Boolean flag2: Boolean flag2: 数组元素数组元素数组元素数组元素intint turn; turn;Void P0 ( )Void P0 ( ) while( TRUE) while( TRUE) flag0= TRUE; flag0= TRUE; turn=0; turn=0; wh

64、ile(flag1&turn=0) /*wait*/ while(flag1&turn=0) /*wait*/ /*critical area*/ /*critical area*/ flag0=false; flag0=false; /*noncritical area*/ /*noncritical area*/ Void P1 ( )Void P1 ( ) while (TRUE) while (TRUE) flag1= TRUE; flag1= TRUE; turn=1;turn=1; while(flag0&turn=1)/*wait*/ while(flag0&turn=1)/*w

65、ait*/ /*critical area*/ /*critical area*/ flag1=false; flag1=false; /*noncritical area*/ /*noncritical area*/ Flag 0Flag 0Flag 1Flag 1初始值初始值初始值初始值为为为为falsefalsePeterson算法是正确的算法turn=j;描述可进入的进程（同时修改标志值）检查对方flag，如果不在临界区则自己进入空闲则入；否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待。硬件手段硬件手段 ( TSL-test and se

66、t lock )( TSL-test and set lock )原子操作：这种操作在运行的过程中，是不能也不允许被打原子操作：这种操作在运行的过程中，是不能也不允许被打原子操作：这种操作在运行的过程中，是不能也不允许被打原子操作：这种操作在运行的过程中，是不能也不允许被打断的，它是操作的最底层的部分，是不可分割的，称其为原断的，它是操作的最底层的部分，是不可分割的，称其为原断的，它是操作的最底层的部分，是不可分割的，称其为原断的，它是操作的最底层的部分，是不可分割的，称其为原子操作。子操作。子操作。子操作。TSLTSL工作原理：将一个存储器字读到寄存器当中，然后在这个工作原理：将一个存储器字

67、读到寄存器当中，然后在这个工作原理：将一个存储器字读到寄存器当中，然后在这个工作原理：将一个存储器字读到寄存器当中，然后在这个内存中存一个非零的值。这个读写的过程是个原子操作，是内存中存一个非零的值。这个读写的过程是个原子操作，是内存中存一个非零的值。这个读写的过程是个原子操作，是内存中存一个非零的值。这个读写的过程是个原子操作，是不可分割的。不可分割的。不可分割的。不可分割的。Enter_regionEnter_region: :tsltsl register , lock register , lockcmpcmp register, #0 register, #0jnejne enter

68、_regionenter_regionretretLeave_regionLeave_region: :move lock, #0move lock, #0retret硬件方法的优点硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量个布尔变量硬件方法的缺点硬件方法的缺点等待要耗费等待要耗费CPU时间，不能实现时间，不能实现让权等待让权等待可能可能饥饿饥饿：从等待进程中随机选择一个进入临界

69、区，有的：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上进程可能一直选不上可能死锁（见下页）可能死锁（见下页）2.2.4 睡眠和唤醒的引入睡眠和唤醒的引入对于对于Peterson和和TSL问题，都能够很好地实现互斥，但也都同问题，都能够很好地实现互斥，但也都同时存在问题：时存在问题： *忙等待，浪费忙等待，浪费CPU的资源。的资源。 *进程的优先级有差别：当有两个进程，进程的优先级有差别：当有两个进程，A、B， A的优先的优先级高，处于就绪状态，而此时，级高，处于就绪状态，而此时，B在临界区内，由于优先级低，在临界区内，由于优先级低，故无法被调度，也就无法离开临界区，那故无法被调度

70、，也就无法离开临界区，那A就只能够在临界区就只能够在临界区外等待。外等待。解决的途径就是引入新的概念：睡眠解决的途径就是引入新的概念：睡眠 唤醒唤醒睡眠：对应着在临界区外的不停判断和等待；睡眠：对应着在临界区外的不停判断和等待；唤醒：对应着触发另一个满足条件的进程进入临界区。唤醒：对应着触发另一个满足条件的进程进入临界区。生产者和消费者问题：生产者和消费者问题：问题描述：问题描述： 若干进程通过有限的共享缓冲区交换数据。其中，若干进程通过有限的共享缓冲区交换数据。其中，生产生产者者进程不断写入，而进程不断写入，而消费者消费者进程不断读出；共享缓冲区共进程不断读出；共享缓冲区共有有N个；任何时刻

71、只能有一个进程可对共享缓冲区进行操作。个；任何时刻只能有一个进程可对共享缓冲区进行操作。等待使用资源的消费者等待使用资源的消费者共享的缓冲区共享的缓冲区共享的缓冲区共享的缓冲区生产者生产者生产者生产者#define N 100int count=0;void producer ( void ) while ( TRUE ) produce_item ( ); if (count= N) sleep ( ); enter_item ( ); count=count+1; if (count=1) wakeup (consumer) void consumer( void ) while ( TR

72、UE ) remove_item ( ); if (count=0) sleep ( ); enter_item ( ); count=count-1; if (count=N-1) wakeup (producer ) 对于生产者：对于生产者： 只有当缓冲区里为零的时候，这时候消费者才有可能睡觉；只有当缓冲区里为零的时候，这时候消费者才有可能睡觉；对于消费者：对于消费者： 只有当缓冲区里装满的时候，这时候生产者才有可能睡觉。只有当缓冲区里装满的时候，这时候生产者才有可能睡觉。导致的问题：类导致的问题：类SpoolerSpooler目录问题目录问题 缓冲区为空，消费者检查，得到缓冲区为空，消费

73、者检查，得到count=0,count=0,但未睡觉的时但未睡觉的时候，被调度程序挂起，此时它将保留一个局部变量来存储候，被调度程序挂起，此时它将保留一个局部变量来存储countcount的值，此时生产者开始工作并向缓冲区内放入资源，当资源等的值，此时生产者开始工作并向缓冲区内放入资源，当资源等于于1 1后，向消费者发送唤醒信号，而此时消费者没有睡眠，等消后，向消费者发送唤醒信号，而此时消费者没有睡眠，等消费者被恢复以后，检查自己存储过的费者被恢复以后，检查自己存储过的countcount，发觉它等于零，则，发觉它等于零，则开始睡眠，而生产者则不停生产，当缓冲区满了以后自己也开开始睡眠，而生产

74、者则不停生产，当缓冲区满了以后自己也开始睡眠，这时候他们就都处于睡眠状态。始睡眠，这时候他们就都处于睡眠状态。 2.2.5 信号量信号量1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到他接受到一个特定的信号。为了发信号，需要一个特殊的变量-信号量s为了通过信号量s传送信号，进程可执行原语signal (s);为了通过信号量s接收信号，进程可执行原语wait (s);对信号量的操作对信号量的

75、操作1. 一个信号量可以初始化为非负数一个信号量可以初始化为非负数2. Wait操作是信号量减一，如果值变为了负数，则执行操作是信号量减一，如果值变为了负数，则执行wait的进程被阻塞；的进程被阻塞；Signal操作是信号量加一，如果值不是正数，则被操作是信号量加一，如果值不是正数，则被wait操作阻操作阻塞的进程被解除阻塞。塞的进程被解除阻塞。除了以上三种操作以外，没有任何其他地方可以检查或操除了以上三种操作以外，没有任何其他地方可以检查或操作信号量。作信号量。Wait=PSignal=V多元信号量的多元信号量的P V 操作操作Struct semaphore int count; queu

76、eType 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 signal 都是原子操都是原子操作，不会被中断影响。作，不会被中断影响

77、。二元信号量的二元信号量的P V操作操作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_semaph

78、ore enmu ( zero , 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进入就绪队列;V V V V原语通常唤醒进程等待队列中的头一个进程原语通常唤醒进程等待队列中的头一个进程原语通常唤醒进程等待队列中的头一个进程原语通常唤醒进程等待队列

79、中的头一个进程 利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏#define N 100 /缓冲区内槽数缓冲区内槽数Typedef int semaphore; semaphore mutex=1; semaphore full=0; semaphore empty=N; Void producer(void) in

80、t item; while(TRUE) produce_item ( &item ) ; down( &empty ) ; down ( &mutex ) ; enter_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 ) ; 上面程序是利用信号量互斥来

81、解决生产者上面程序是利用信号量互斥来解决生产者-消费者问题的。消费者问题的。其中：其中：信号量mutex用于互斥，保证任意时刻只能有一个进程读写缓冲区和相关的变量，保证了临界区、临界资源的合理安全使用。信号量full和empty用来保证一定的时间顺序发生或不发生，它用来通知生产者和消费者，保证了当缓冲区满的时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。2.2.6 管程管程1.信号量同步的缺点信号量同步的缺点同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须

82、通读整个系统或者并发程序；不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；2. 2. 管程的引入管程的引入1973年，Hoare和Hanson所提出；其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的

83、管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。3. 管程的主要特性模块化：一个管程是一个基本程序单位，可以单独编译；抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的.4. 管程的实现要素管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过

84、程（函数）来间接地访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程互斥进入；管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作；5. 条件变量(condition)由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量-条件变量。每个表示一种等待原因，并不取具体数值相当于每个原因对应一个队列。6. 管程的格式（类Pascal）TYPE TYPE monitor_namemonitor_name = MONITOR; = MONIT

85、OR;共享变量说明共享变量说明define define 本管程内所定义、本管程外可调用的过程（函数）名本管程内所定义、本管程外可调用的过程（函数）名字表字表use use 本管程外所定义、本管程内将调用的过程（函数）名本管程外所定义、本管程内将调用的过程（函数）名字表字表PROCEDURE PROCEDURE 过程名（形参表）；过程名（形参表）；过程局部变量说明；过程局部变量说明；BEGINBEGIN语句序列；语句序列；END;END;.7. 管程的的组成名称：为每个共享资源设立一个管程数据结构说明：一组局部于管程的控制变量操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是

86、访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。初始化代码：对控制变量进行初始化的代码生产者生产者消费者的管程实现消费者的管程实现 Monitor ProducerConsumer condition full , empty ; integer count; 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

87、count=0 then wait (empty ) ; remove_item; count:=count-1; if count=N-1 then signal(full) end count:=0;End monitor;Procedure producer;Procedure producer; begin begin while true do while true do begin begin produce_itemproduce_item; ; ProducerConsumer.enterProducerConsumer.enter end end end; end;Proce

88、dure consumer;Procedure consumer; begin begin while true do while true do begin begin ProducerConsumer.removeProducerConsumer.remove; ; consume_itemconsume_item; ; end end end; end; 管程与信号量的比较管程与信号量的比较 由于管程的机制，在某个时刻，只能有一个管程过程是活由于管程的机制，在某个时刻，只能有一个管程过程是活跃的，就类似于原语操作一样，也能够很好地解决跃的，就类似于原语操作一样，也能够很好地解决Spool

89、er目目录的问题，而且更为简洁，在使用的过程中，能够直接分析录的问题，而且更为简洁，在使用的过程中，能够直接分析代码，更容易理解使用。代码，更容易理解使用。而且它的互斥操作是由编译器所支而且它的互斥操作是由编译器所支持的，更为安全，不宜出错。持的，更为安全，不宜出错。 用信号量可实现进程间的同步，但由于信号量的控制分布用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函

90、数库的形式实现。相比之下，管程和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。比信号量好控制。 弊端，弊端，支持管程的编程语言太少，因为它要求编译器的支支持管程的编程语言太少，因为它要求编译器的支持持，而信号量对于一个操作系统来说是很容易添加的；他们，而信号量对于一个操作系统来说是很容易添加的；他们都是用来解决访问同一个公共存储器的一个或多个都是用来解决访问同一个公共存储器的一个或多个CPU的互的互斥问题。通过将信号量放入共享内存中并用斥问题。通过将信号量放入共享内存中并用TSL指令来保护他指令来保护他们，可以避免竞争。但对于一个具有多个们，可以避免竞争。但对于一个具有多个

91、CPU，且每个，且每个CPU有有自己的内存，有一个局域网相连的分布式系统来说，这些原自己的内存，有一个局域网相连的分布式系统来说，这些原语将完全失败。而管程由于编程语言的限制很难被实际应用。语将完全失败。而管程由于编程语言的限制很难被实际应用。所以这两种都不是很实际的解决方法。所以这两种都不是很实际的解决方法。 需要新的解决方法。需要新的解决方法。2.2.7 消息传递消息传递1.1.消息的原语形式消息的原语形式消息的原语形式消息的原语形式Send ( destination , &message )Send ( destination , &message )Receive ( source

92、, &message )Receive ( source , &message )都属于系统调用都属于系统调用都属于系统调用都属于系统调用2.2.2.2.消息传递中的要点消息传递中的要点消息传递中的要点消息传递中的要点-针对与通信进程位于网络中不针对与通信进程位于网络中不针对与通信进程位于网络中不针对与通信进程位于网络中不同机器上的情况同机器上的情况同机器上的情况同机器上的情况1 1 1 1）由于进程发送了消息以后，接受者才能接收，故）由于进程发送了消息以后，接受者才能接收，故）由于进程发送了消息以后，接受者才能接收，故）由于进程发送了消息以后，接受者才能接收，故*对于一个执行对于一个执行对于

93、一个执行对于一个执行sendsendsendsend的进程的进程的进程的进程*对于一个执行对于一个执行对于一个执行对于一个执行receivereceivereceivereceive的进程的进程的进程的进程发送被阻塞，等回复发送被阻塞，等回复发送被阻塞，等回复发送被阻塞，等回复发送没有阻塞，做别的发送没有阻塞，做别的发送没有阻塞，做别的发送没有阻塞，做别的接受消息，继续执行接受消息，继续执行接受消息，继续执行接受消息，继续执行等待消息等待消息等待消息等待消息a)a)a)a)等，直到接收到等，直到接收到等，直到接收到等，直到接收到 b)b)b)b)放弃接收放弃接收放弃接收放弃接收2）消息接收的处

94、理）消息接收的处理发送者发送消息，接收者收到后发送一个应答，这时：发送者发送消息，接收者收到后发送一个应答，这时：*应答信息被发送者收到，则继续发送新的消息；应答信息被发送者收到，则继续发送新的消息；*应答信息丢失，则重发刚才的信息，此时，接收者需要区应答信息丢失，则重发刚才的信息，此时，接收者需要区分消息的新旧，利用给消息加上连续序号来解决；分消息的新旧，利用给消息加上连续序号来解决；3）消息系统消息系统设计的其他注意事项设计的其他注意事项*系统需要解决进程命名的问题，保证消息的正确发送和接系统需要解决进程命名的问题，保证消息的正确发送和接收；收；*效率的提升：严格控制系统中所用信息的长度，

95、保证能够效率的提升：严格控制系统中所用信息的长度，保证能够送入寄存器。送入寄存器。3.3.阻塞的处理及实用性阻塞的处理及实用性阻塞的处理及实用性阻塞的处理及实用性阻塞可以对于阻塞可以对于阻塞可以对于阻塞可以对于sendsend方发生，也可以对方发生，也可以对方发生，也可以对方发生，也可以对receive receive 方发生，一般方发生，一般方发生，一般方发生，一般有三种组合：有三种组合：有三种组合：有三种组合：1 1）阻塞）阻塞）阻塞）阻塞sendsend，阻塞，阻塞，阻塞，阻塞receivereceive：发送和接收者都被阻塞，一直：发送和接收者都被阻塞，一直：发送和接收者都被阻塞，一直

96、：发送和接收者都被阻塞，一直到完成信息的交付，通常称为到完成信息的交付，通常称为到完成信息的交付，通常称为到完成信息的交付，通常称为“ “会合会合会合会合” ”，属于进程间的紧密，属于进程间的紧密，属于进程间的紧密，属于进程间的紧密同步。同步。同步。同步。2 2）无阻塞）无阻塞）无阻塞）无阻塞sendsend，阻塞，阻塞，阻塞，阻塞receivereceive，发送方尽管发送，接收者会，发送方尽管发送，接收者会，发送方尽管发送，接收者会，发送方尽管发送，接收者会阻塞，直到自己等到自己需要的信息来为止。类似于一个服阻塞，直到自己等到自己需要的信息来为止。类似于一个服阻塞，直到自己等到自己需要的信

97、息来为止。类似于一个服阻塞，直到自己等到自己需要的信息来为止。类似于一个服务器进程给其他进程提供服务或资源。务器进程给其他进程提供服务或资源。务器进程给其他进程提供服务或资源。务器进程给其他进程提供服务或资源。3 3）无阻塞）无阻塞）无阻塞）无阻塞sendsend，无阻塞，无阻塞，无阻塞，无阻塞receivereceive，不要求任何一方等待。，不要求任何一方等待。，不要求任何一方等待。，不要求任何一方等待。使用消息的互斥使用消息的互斥const const intint n=/* n=/*进程数目进程数目进程数目进程数目* */ /Void P( Void P( intint i ) i )

98、 message message msgmsg; ; while ( true ) while ( true ) receive ( receive ( mutexmutex , , msgmsg ) ; ) ; /* /* /* /*临界区临界区临界区临界区* * * */ / / / send ( send ( mutexmutex , , msgmsg ) ; ) ; /*/*/*/*其余部分其余部分其余部分其余部分* * * */ / / / Void main()Void main() create_mailbox(mutexcreate_mailbox(mutex); ); sen

99、d(mutexsend(mutex，null);null); parbeginparbegin( P(1) , P(2) , ,( P(1) , P(2) , ,P(nP(n);); 此处的此处的mailboxmailbox表示一种数据表示一种数据结构，它是用来对一定数量结构，它是用来对一定数量的消息进行缓冲的地方，一的消息进行缓冲的地方，一般在信箱创建时确定消息的般在信箱创建时确定消息的数量。数量。描述：描述： 这里使用的是阻塞receive原语和无阻塞send原语，一组并发进程共享一个信箱mutex，它可以供所有的进程在发送和接收时使用，该信箱被初始化成一个无内容的消息。希望进入临界区的进

100、程首先试图接收一条消息，如果信箱为空，则该进程被阻塞，一旦进程获得消息，它执行它的临界区，然后把该消息放回信箱。消息函数可以看成是在进程之间传递的一个令牌。对上述方案假设如果有多个进程并发执行接收操作，则： *如果有一条消息，它仅仅被传递给一个进程，其他进程被阻塞。 *如果消息队列为空，所有进程被阻塞，当有一条消息可用时，只有一个阻塞进程被激活并得到这条消息。生产者生产者生产者生产者消费者问题的解决消费者问题的解决消费者问题的解决消费者问题的解决Void producer ( void ) int item; message m; /* /* 消息缓冲区消息缓冲区* */ / while (

101、TRUE ) produce_item ( &item ) ; /* /* 产生数据放入缓冲区产生数据放入缓冲区* */ / receive ( consumer , &item); /* /* 等待空消息到达了，进入等待空消息到达了，进入* */ / build_message ( &m ,item); /* /* 构造消息供发送构造消息供发送* */ / send (consumer , &m); /* /* 向消费者发送一个数据项向消费者发送一个数据项* */ / Void consumer ( void )Void consumer ( void ) intint item i; it

102、em i; message m; message m; for( i=0; iN; i+ ) send ( producer , &m); /* for( i=0; iN; i+ ) send ( producer , &m); /* 发送发送发送发送N N条空消息条空消息条空消息条空消息 * */ / while(TRUEwhile(TRUE) ) receive (producer, &m ); receive (producer, &m ); /* /* /* /* 收到一条包含数据的消息收到一条包含数据的消息收到一条包含数据的消息收到一条包含数据的消息* * * */ / / / ex

103、tract_item(&mextract_item(&m ,&item); ,&item); /* /* /* /* 从消息中提取数据从消息中提取数据从消息中提取数据从消息中提取数据* * * */ / / / send(producersend(producer ,&m); ,&m); /* /* /* /* 回送空消息作为应答回送空消息作为应答回送空消息作为应答回送空消息作为应答* * * */ / / / consume_item(itemconsume_item(item); ); /* /* /* /* 使用数据项进行操作使用数据项进行操作使用数据项进行操作使用数据项进行操作* *

104、* */ / / / 这里的互斥由消息的发送原语这里的互斥由消息的发送原语这里的互斥由消息的发送原语这里的互斥由消息的发送原语sendsendsendsend和和和和receivereceivereceivereceive来解决，来解决，来解决，来解决，而这里的缓冲区（信箱）实际上是容纳那些被发送而未被而这里的缓冲区（信箱）实际上是容纳那些被发送而未被而这里的缓冲区（信箱）实际上是容纳那些被发送而未被而这里的缓冲区（信箱）实际上是容纳那些被发送而未被目标进程接收的消息。目标进程接收的消息。目标进程接收的消息。目标进程接收的消息。 如果说，这个缓冲区内始终没有东西，而消息的发送如果说，这个缓冲区

105、内始终没有东西，而消息的发送如果说，这个缓冲区内始终没有东西，而消息的发送如果说，这个缓冲区内始终没有东西，而消息的发送和接收仍在运行，则说明这是处于会合态，即消息的发送和接收仍在运行，则说明这是处于会合态，即消息的发送和接收仍在运行，则说明这是处于会合态，即消息的发送和接收仍在运行，则说明这是处于会合态，即消息的发送和接收是同时的，没有迟延。和接收是同时的，没有迟延。和接收是同时的，没有迟延。和接收是同时的，没有迟延。2.3 经典经典IPC问题问题2.3.1哲学家进餐问题哲学家进餐问题#define N 5 /* 哲学家的人数哲学家的人数 */void philosopher(int i)

106、/*给哲学家编号给哲学家编号 */ while (TRUE) think(); /* 思考思考*/ takefork(i); /*取叉子取叉子 */ takefork(i+1) % N); /*取右边叉子取右边叉子 */ eat(); /* 进餐进餐*/ putfork(i); /*放下左边叉子放下左边叉子 */ putfork(i+1) % N); /*放下右边叉子放下右边叉子 */ 上述算法的局限与改进上述算法的局限与改进极限阻塞：极限阻塞：当当5个哲学家同时拿起叉子时，就会同时处于阻塞，然后同时个哲学家同时拿起叉子时，就会同时处于阻塞，然后同时放下，再同时拿起放下，再同时拿起.-饥饿态饥

107、饿态 解决办法解决办法1：加随机数，使哲学家们拿叉子的时间错开，可：加随机数，使哲学家们拿叉子的时间错开，可以解决问题。以解决问题。 缺陷：太不可靠缺陷：太不可靠 解决办法解决办法2：在：在think后加上一个后加上一个mutex,使哲学家都要首先使哲学家都要首先访问临界区，才能进餐，可以解决问题。访问临界区，才能进餐，可以解决问题。 缺陷：浪费，因为实际上可以有缺陷：浪费，因为实际上可以有2个同时进餐，但实际上加个同时进餐，但实际上加了互斥后，只能有一个进餐，其了互斥后，只能有一个进餐，其4人都要等待。人都要等待。#define N 5 /*哲学家的人数哲学家的人数 */#define LE

108、FT (i-1)%N /* 某个哲学家左边人的号码某个哲学家左边人的号码 */#define RIGHT (i+1)%N /*某个哲学家右边人的号码某个哲学家右边人的号码*/#define THINKING 0 /* 思考思考 */#define HUNGRY 1/* 想取叉子想取叉子 */#define EATING 2/* 哲学家在进餐哲学家在进餐*/typedef int semaphore; /* 信号量信号量 */int state N ; /* 记录每个人状态的数组记录每个人状态的数组 */Semaphore mutex = 1; /* 临界区的互斥临界区的互斥 */semapho

109、re 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 (

110、& & mutex ); /* 进入临界区进入临界区 */ statei = HUNGRY;/* 记录下第记录下第 i 个哲学家饥饿个哲学家饥饿 */ test(i); /* 尝试去拿两个叉子尝试去拿两个叉子 */ up(& &mutex); /* 退出临界区退出临界区 */ down(& &si); /* 得不到就阻塞得不到就阻塞 */void putforks (i) /* i: 某个哲学家的编号某个哲学家的编号, 从从 0 到到 N-1 */ down (& &mutex ); /* 进入临界区进入临界区 */ statei = THINKING; /* 记录下第记录下第 i 个哲学家已

111、经完成进餐个哲学家已经完成进餐 */ test (LEFT); /* 测试左侧是否能进餐测试左侧是否能进餐 */ test (RIGHT); /* 测试右侧是否能进餐测试右侧是否能进餐 */ up (& &mutex); /* 退出临界区退出临界区 */void test(i)/* i: 某个哲学家的编号某个哲学家的编号, 从从 0 到到 N-1 */ if (statei = HUNGRY & stateLEFT != EATING & stateRIGHT != EATING) statei = EATING; up(& &si); /* 唤醒阻塞唤醒阻塞 */ 如果第一个进入，通过如果第

112、一个进入，通过test来表示自己的状态，表示可以进来表示自己的状态，表示可以进餐，如果他完成以后，通过餐，如果他完成以后，通过test标识可以进餐的人的标号，在标识可以进餐的人的标号，在test函数里将阻塞的进程唤醒，即每个哲学家放下叉子之后，函数里将阻塞的进程唤醒，即每个哲学家放下叉子之后，再去判断两侧的是否有阻塞，如果有，将它唤醒，之后，放再去判断两侧的是否有阻塞，如果有，将它唤醒，之后，放开对临界区的控制，让两侧的哲学家进餐。开对临界区的控制，让两侧的哲学家进餐。 函数只以函数只以philosopher为主函数，其余的均为被调用的函为主函数，其余的均为被调用的函数。不是单独的进程。数。不

113、是单独的进程。 属于多个进程访问有限资源类问题。属于多个进程访问有限资源类问题。2.3.2 读者读者-写者问题写者问题问题描述：问题描述： 有一个许多进程共享的数据区，这个数据区可以是一个文有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间，甚至可以是一组处理器寄存器，有件或者主存的一块空间，甚至可以是一组处理器寄存器，有一些只读取这个数据区的进程，和一些只向数据区中写数据一些只读取这个数据区的进程，和一些只向数据区中写数据的进程。此外，还需要满足：的进程。此外，还需要满足： 1.任意多的读进程可以同时读这个文件任意多的读进程可以同时读这个文件; 2.一次只有一个写进程可以

114、往文件中写；一次只有一个写进程可以往文件中写； 3.如果一个写进程正在往文件中写，禁止任何读进程读文如果一个写进程正在往文件中写，禁止任何读进程读文件。件。 数据库的访问模型数据库的访问模型typedef int semaphore; /* 根据需要自定义根据需要自定义 */semaphore mutex = 1; /* 控制对控制对 rc的访问的访问 */semaphore db = 1; /* 控制对数据库的访问控制对数据库的访问 */int rc = 0; /* 正在读或准备读的进程数正在读或准备读的进程数 */void reader(void)while (TRUE) /* 无限循环无

115、限循环 */down(&mutex); /* 禁止对禁止对 rc的访问的访问 */rc = rc + 1; /* 读者进入读者进入 */if (rc = 1) down(&db); /* 如果是第一个读者如果是第一个读者 . */up(&mutex); /* 恢复恢复允许访问允许访问 rc */read_data_base(); /* 访问数据访问数据 */down (&mutex); /* 禁止对禁止对 rc的访问的访问 */rc = rc - 1; /* 读者离开读者离开 */if (rc = 0) up(&db); /* 如果是最后一个读者如果是最后一个读者 . */up(&mutex)

116、; /* 恢复允许访问恢复允许访问 rc */use_data_read(); /* 非临界区非临界区 */ void writer (void)while (TRUE) /* 无限循环无限循环 */think_up_data ();/* 非临界区非临界区 */down (&db); /* 锁定临界区锁定临界区数据库数据库 */write_data_base ( ); /* 更新数据更新数据 */up (&db); /* 释放对临界区的控制释放对临界区的控制数据库数据库 */ 局限性：只要有一个读者在，则就可以允许更多的读者进入，局限性：只要有一个读者在，则就可以允许更多的读者进入，而此时如果

117、有更新数据的需求，但也会被无限制的挂起。而此时如果有更新数据的需求，但也会被无限制的挂起。故此种解法为读者优先。故此种解法为读者优先。写进程优先写进程优先 解决解决 读者读者写者问题写者问题问题描述：由于采用读者优先时。只要至少一个读进程在读，问题描述：由于采用读者优先时。只要至少一个读进程在读，就为读保留了数据区的控制权，所以写进程可能会被饿死。就为读保留了数据区的控制权，所以写进程可能会被饿死。 故需要增加如下限制信息：故需要增加如下限制信息：为了保证一个写进程声明想写时，不允许新的读进程访问该为了保证一个写进程声明想写时，不允许新的读进程访问该数据区，需要增加额外的信号量和变量：数据区，

118、需要增加额外的信号量和变量：*信号量信号量rsem:当至少有一个写进程准备访问数据区时，用来当至少有一个写进程准备访问数据区时，用来禁止所有的读进程；禁止所有的读进程；*变量变量writecount:控制控制rsem的设置；的设置；*信号量信号量y:控制控制writecount的更新。的更新。一个额外的信号量一个额外的信号量z，为了写进程优先，不要多余的读进程在，为了写进程优先，不要多余的读进程在rsem里等待，将多余的读进程放入里等待，将多余的读进程放入z中，在那里排队。中，在那里排队。进程中的队列状态进程中的队列状态系统中只有读进程系统中只有读进程a)设置设置db； b)没有队列没有队列系

119、统中只有写进程系统中只有写进程a)设置设置db和和rsem； b)写进程在写进程在db上排队上排队系统中既有读进程系统中既有读进程又有写进程又有写进程,读优先读优先系统中即有读进程系统中即有读进程又有写进程又有写进程,写优先写优先a)读进程设置读进程设置db; b)写进程设置写进程设置rsem；c)所有写进程在所有写进程在db上排队；上排队；d)一个读进程在一个读进程在rsem上排队；上排队；e)其他读进程在其他读进程在z上排队。上排队。a)写进程设置写进程设置db; b)写进程设置写进程设置rsem；c) 写进程在写进程在db上排队；上排队；d)一个读进程在一个读进程在rsem上上排排队；队

120、；e)其他读进程在其他读进程在z上排队。上排队。int readcount , writecountSemaphore mutex=1,y=1,z=1,db=1,rsem=1;Void reader() while (TRUE) down( z); down(rsem); down(mutex); readcount+; if (readcount=1) down(db); up (mutex); up (rsem); up(z); READUNIT();READUNIT(); down ( down (mutexmutex); );Void writer() while(TRUE) down

121、(y); writecount+; if(writecount=1) down(rsem); /*阻塞新的读进程进入阻塞新的读进程进入*/ up(y); down(db); WRITEUNIT(); up(db); down(y); writecount-; if(writecount=0) up(rsem); /*所有写进程完成，允许新读者进入所有写进程完成，允许新读者进入*/ up(y); 2.3.2 理发师睡觉问题理发师睡觉问题问题描述问题描述:理发店里有一位理发师，一次给一名顾客理发，店理发店里有一位理发师，一次给一名顾客理发，店里有里有N把椅子，故最多会有把椅子，故最多会有N个顾客在

122、等待，如果新来的顾客个顾客在等待，如果新来的顾客没有位置，则会离开，即等待的队列有上限；当没有顾客的没有位置，则会离开，即等待的队列有上限；当没有顾客的时候理发师开始睡觉，直到有顾客把它唤醒为止。时候理发师开始睡觉，直到有顾客把它唤醒为止。特殊的多进程对有界资源的使用。特殊的多进程对有界资源的使用。#define CHAIRS 5 /* 椅子的数目椅子的数目 */typedef int semaphore; /* 自定义自定义 */semaphore customers = 0; /* 等待服务的等待服务的顾客数目顾客数目 */semaphore barbers = 0; /* 理发师的数目理

123、发师的数目 */semaphore mutex = 1; /* 互斥量互斥量 */int waiting = 0; /* 等待的顾客（未理发的）等待的顾客（未理发的） */void barber(void)while (TRUE) down(customers); /* 无顾客就去睡眠无顾客就去睡眠 */down(mutex); /* 锁定临界区锁定临界区 */waiting = waiting - 1; /* 等候的顾客数减一等候的顾客数减一 */up(barbers);/* 一个理发师开始理发一个理发师开始理发 */up(mutex);/* 释放刚才的锁定释放刚才的锁定 */Cut_hai

124、r(); /* 理发理发 */ void customer(void)down(mutex); /* 进入临界区进入临界区 */if (waiting Ready suspend, Running Exit中期(medium-term)：将进程的部分或全部加载到内存中。进程状态：Ready Ready suspend, Blocked Blocked suspend短期(short-term)：选择哪个进程在处理机上执行。进程状态：Ready RunningI/O调度：选择哪个I/O等待进程，使其请求可以被空闲的I/O设备进行处理。3.按照OS的分类批处理调度应用场合：大中型主机集中计算，如工

125、程计算、理论计算（流体力学）分时调度、实时调度：通常没有专门的作业调度多处理机调度* 调度的性能准则我们可从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。从两个方面分析：1 . 从用户方面来考虑：2 . 从系统角度来考虑。1.面向用户的调度性能准则面向用户的调度性能准则周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待批处理系统-平均周转时间T-平均带权周转时间（带权周转时间W是 T(周转)/T(CPU执行)响应时间：用户输入一个请求（

126、如击键）到系统给出首次响应（如屏幕显示）的时间分时系统截止时间：开始截止时间和完成截止时间实时系统，与周转时间有些相似。公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。2. 面向系统的调度性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系批处理系统平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时处理机利用率：大中型主机各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配大中型主机3

127、. 调度算法本身的调度性能准则易于实现执行开销比* 进程调度功能：调度程序(dispatcher)记录所有进程的运行状况（静态和动态）当进程出让CPU或调度程序剥夺执行状态进程占用的CPU时，选择适当的进程分派CPU完成上下文切换进程的上下文切换过程：用户态执行进程A代码进入OS核心（通过时钟中断或系统调用）保存进程A的上下文，恢复进程B的上下文（CPU寄存器和一些表格的当前指针）用户态执行进程B代码注：上下文切换之后，指令和数据快速缓存cache通常需要更新，执行速度降低*进程调度中的问题进程调度中的问题好的算法应有的原则：好的算法应有的原则：1 . 公平公平-每个进程有合理的每个进程有合理

128、的CPU份额；份额；2 . 有效有效-CPU百分百忙碌；百分百忙碌；3 . 响应时间响应时间-使交互用户的响应时间尽可能短；使交互用户的响应时间尽可能短；4 . 周转时间周转时间-使批处理用户等待的输出的时间尽可能短；使批处理用户等待的输出的时间尽可能短；5 . 吞吐量吞吐量-使每小时处理的作业数最多。使每小时处理的作业数最多。问题一：原则本身的矛盾问题一：原则本身的矛盾如如3和和4的矛盾，的矛盾，任一个偏向一个类型作业的调度必将损害另一些作业。任一个偏向一个类型作业的调度必将损害另一些作业。矛盾无法解除；矛盾无法解除；问题二：进程的特性和所运行的环境导致的不可预测性问题二：进程的特性和所运行

129、的环境导致的不可预测性*进程之间有差别进程之间有差别1）针对于不同的领域，对）针对于不同的领域，对CPU的占用不可知，如科学运算与的占用不可知，如科学运算与绘图操作之间的差别；绘图操作之间的差别；2）进程是运行中的程序，具体的实时性很强。）进程是运行中的程序，具体的实时性很强。解决方法：设置计时器或者时钟，定期对在系统中的进程进解决方法：设置计时器或者时钟，定期对在系统中的进程进行判断，来决定当前是否需要发生进程切换。另外操作系统行判断，来决定当前是否需要发生进程切换。另外操作系统可以自己根据需要设定时钟频率，可以自己根据需要设定时钟频率，*调度的分类调度的分类可剥夺调度：允许将逻辑上可运行的

130、进程暂时挂起的策略也可剥夺调度：允许将逻辑上可运行的进程暂时挂起的策略也成为可剥夺调度。（较为通用）成为可剥夺调度。（较为通用）非剥夺调度：与可剥夺调度相反，系统一直将进程运行到直非剥夺调度：与可剥夺调度相反，系统一直将进程运行到直至结束时候，这种调度方式为非剥夺调度。至结束时候，这种调度方式为非剥夺调度。-早期批处理系早期批处理系统使用。统使用。对于存在竞争的多用户系统，不适合，但适合专用的系统对于存在竞争的多用户系统，不适合，但适合专用的系统（如数据服务器）。（如数据服务器）。先来先服务先来先服务(FCFS, First Come First Service)这是最直接的调度算法，按先后顺

131、序进行调度。这是最直接的调度算法，按先后顺序进行调度。这是最直接的调度算法，按先后顺序进行调度。这是最直接的调度算法，按先后顺序进行调度。1.1.FCFSFCFS算法算法算法算法按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最直接的算法2. FCFS的特点的特点比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。2.4.1 时间片轮转调度(Round Robin)算法本算法主要用于微观调度，说明怎

132、样并发运行，即切换的方本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率。式；设计目标是提高资源利用率。其基本思路是通过时间片轮转，提高进程并发性和响应时间其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率；特性，从而提高资源利用率；1. 时间片轮转算法时间片轮转算法将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFS原则，排成一个队列。原则，排成一个队列。每次调度时将每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片分派给队首进程，让其执行一个时间片。时间片的长度从几个的长度从几个ms到几百到几百ms。在一个时间片结束

133、时，发生时钟中断。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让进程可以未使用完一个时间片，就出让CPU（如阻塞）。（如阻塞）。2. 时间片长度的确定时间片长度变化的影响过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)时间片长度的影响因素：

134、就绪进程的数目：数目越多，时间片越小（当响应时间一定时）系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。2.4.2 优先级算法(Priority Scheduling) 本算法平衡各进程对响应时间的要求。适用于作业调度和本算法平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式；进程调度，可分成抢先式和非抢先式； 静态优先级 动态优先级2.4.2.1 2.4.2.1 静态优先级静态优先级 创建进程时就确定，直到进程终止前都不改变。通常是一创建进程时就确定，直到进程终止前都不改变。通常是一个整数。个整数。依据：

135、进程类型（系统进程优先级较高）对资源的需求（对CPU和内存需求较少的进程，优先级较高）用户要求（紧迫程度和付费多少）低优先级的会发生饥饿状态低优先级的会发生饥饿状态此时：同一优先级之间使用时间片轮换法。此时：同一优先级之间使用时间片轮换法。2.4.2.2 2.4.2.2 动态优先级动态优先级 在创建进程时赋予的优先级，在进程运行过程中可以自动在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。如：改变，以便获得更好的调度性能。如：在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；进程每执行一个时间片，就降低

136、其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。2.4.3 2.4.3 多重队列多重队列 本算法引入多个就绪队列，通过各队列的区别对待，达到本算法引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标；一个综合的调度目标；根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。每个作业固定归入一个队列。各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。如：系统进程、用户交互进程、批处理进程等。2.4.3 短作业优先短作业优先 (SJF, Shortest Job First)又称为又称为“短进程优先短进程优先”SPN(Shortest Proces

137、s Next)；这是对；这是对FCFS算法的改进，其目标是减少平均周转时间。算法的改进，其目标是减少平均周转时间。1.SJF算法算法2. 对预计执行时间短的作业（进程）优先分派处理机。对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业通常后来的短作业不抢先正在执行的作业,只对队列中就只对队列中就绪的进程进行调整。绪的进程进行调整。2. SJF的特点的特点优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间

138、，从而影响调度性能。平均时间平均时间=（8+12+16+20）/4=14 平均时间平均时间=（4+8+12+20）/4=11四个作业的运行时间为四个作业的运行时间为a，b，c，d，则总的周转时间是，则总的周转时间是4a+3b+2c+d，而最短优先直接影响到最短响应时间，故希望他，而最短优先直接影响到最短响应时间，故希望他同时应用到交互进程之中。同时应用到交互进程之中。交互交互=等待命令等待命令-执行命令，所以如果把执行命令看成一个独执行命令，所以如果把执行命令看成一个独立的作业，则可以用最先运行最短的作业来是响应时间最短。立的作业，则可以用最先运行最短的作业来是响应时间最短。*老化算法：利用加权运算，每次都依据当前得到的实际的老化算法：利用加权运算，每次都依据当前得到的实际的结果对下一次的值进行估算，保证尽可能的准确。结果对下一次的值进行估算，保证尽可能的准确。2.4.5 保证调度算法保证调度算法2.4.6 彩票调度算法彩票调度算法2.4.7 实时调度实时调度2.4.8 两级调度算法两级调度算法