操作系统教学02PPT学习教案

1、会计学1操作系统教学操作系统教学02第1页/共255页2.1 进程的基本概念进程的基本概念程序和数据程序和数据进程结构进程结构指令流指令流第2页/共255页2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征第3页/共255页2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征第4页/共255页2.1.2 前趋图前趋图第5页/共255页P=P1, P2, P3, P4, P5, P6, P7, P8, P9= (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8),

2、 (P7, P9), (P8, P9) 第6页/共255页2.1.3 程序的并发执行及其特征程序的并发执行及其特征P1P2P3P4I1I2I3I4C1C2C3C4在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1在Pi-1和Ci以及Ii+1之间，可以并发执行多个程序同时在系统中运行，这些程序的执行在时间上是重叠的，即前一程序的执行尚未结束，后一程序的执行已经开始。第7页/共255页2.1.3 程序的并发执行及其特征程序的并发执行及其特征第8页/共255页第9页/共255页不可再现性的例子：l两个并发执行的程序A和B，如下所示： A：N:=N+1； B：

3、print（N）； N:=0；l 分析：1）并发：A、B交替占用CPU执行；2）异步性导致：CPU交替执行A、B的语句时顺序可能不同！l 设某次循环前，N的值为8, CPU执行顺序 打印结果 N的值1)N:=N+1;print(N);N:=0; 9 02)print(N);N:=0;N:=N+1; 8 13)print(N);N:=N+1;N:=0; 8 0第10页/共255页第11页/共255页第12页/共255页引入进程后引入进程后第13页/共255页第14页/共255页2.1.4 进程的特征与状态进程的特征与状态多道程序环境下，如何能使程序并发执行？如何对并发执行的程序加以控制和描述？第

4、15页/共255页l 进程和程序的区别很微妙l 想象一位好厨艺的科学家正在为女儿烘制生日蛋糕。有食谱，有原料：面粉、鸡蛋、糖、香草汁等等。在这个比喻中，食谱就是程序(即用适当形式描述的算法)，科学家就是处理机(CPU)，各种原料就是输入数据。进程就是厨师阅读食谱、取来各种原料、以及烘制蛋糕的一系列动作的总和。第16页/共255页l 现在假设科学家的儿子哭着跑了进来，说他被一只蜜蜂螫了。科学家就记录下他照着食谱做到哪儿了(保存进程的当前状态)，然后拿出一本急救手册，按照其中的指示处理螫伤。l 这里，我们看到处理机从一个进程(做蛋糕)切换到另一个高优先级的进程(实施医疗救治)，每个(进程)拥有各自

5、的程序(食谱和急救书)。当蜜蜂螫伤处理完之后，科学家又回来做蛋糕，从他离开时的那一步继续做下去。l 关键思想是：一个进程是某种类型的一个活动，它有程序、输入、输出、及状态。单个处理机被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。第17页/共255页阅读菜谱阅读菜谱准备原料准备原料烹制菜肴烹制菜肴饭菜饭菜阅读洗衣机手册阅读洗衣机手册准备衣服、洗衣粉准备衣服、洗衣粉设定参数，洗衣服设定参数，洗衣服干净衣服干净衣服程序程序输入输入运行运行输出输出程序程序输入输入运行运行输出输出分时切换分时切换第18页/共255页l 进程的核心思想进程是某个程序在某个数据集

6、合上的运行过程，它有程序、输入、输出和状态。在分时操作系统中，单个CPU被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。第19页/共255页操作系统维护一个程序计数器，在进程间切换操作系统维护一个程序计数器，在进程间切换对每一个进程而言，都有独立的计数器和对每一个进程而言，都有独立的计数器和CPUCPU时间时间操作系统实现分时，任意时刻只有一个进程运行操作系统实现分时，任意时刻只有一个进程运行第20页/共255页进程同程序的差别进程同程序的差别第21页/共255页一个程序对应两个进程第22页/共255页一个进程包括多个程序第23页/共255页进程的特征进程

7、的特征第24页/共255页第25页/共255页运行态运行态阻塞态阻塞态就绪态就绪态进程就绪，可以运行状态转换：进程等待外部事件，阻塞OS决定由哪个进程占用CPU，进程调度？第26页/共255页l 运行态变为就绪态l 强制终止某进程的运行（系统原因）l 运行态变为阻塞态l 运行进程等待外部事件发生（自身原因）l 阻塞态变为就绪态l 外部事件已经发生，可准备运行l 就绪态变为运行态l 停止其他进程运行后，运行该进程占用CPU第27页/共255页l 问题1：为什么不能从阻塞态变为运行态呢？l 问题2：为什么不能从就绪态变为阻塞态呢？l 答案：l 三种状态的变换体现了OS的资源管理作用l 进程的核心思

8、想在于运行CPU资源的分配第28页/共255页第29页/共255页是一个进程刚刚建立，但还未将它送入就绪队列时的状态是一个进程刚刚建立，但还未将它送入就绪队列时的状态一个进程已经正常结束或异常结束，一个进程已经正常结束或异常结束，OSOS已将它从就绪队列中移出，但尚未将它撤消已将它从就绪队列中移出，但尚未将它撤消第30页/共255页活动活动挂起挂起事件事件发生发生事件事件发生发生等待等待事件事件挂起挂起调度调度超时超时释放释放活动活动挂起挂起第31页/共255页第32页/共255页l 重要的术语 Cocurrency & Parallel & MultiProgramming Program

9、& Process & Thread Running & Ready & Block & Suspend Dispatch & Activate & Suspend & Wakel 重要的思想 程序与进程：静态和动态的思想 多道程序：并发与互斥的思想 进程管理：杂七杂八好烦哪？第33页/共255页2.1.5 进程控制块进程控制块第34页/共255页第35页/共255页第36页/共255页思考：PCB是进程存在的唯一标志 为什么？ 因为因为PCB 1PCB 1、包含了进程的包含了进程的描述信息和控制信息描述信息和控制信息，2 2、是进是进程的程的动态特征的集中反映动态特征的集中反映，3 3、系统

10、系统根据根据PCBPCB而感知某一进程的而感知某一进程的存在存在，所以，所以PCBPCB是进程存在的唯一标志。是进程存在的唯一标志。( (只有在多任务即多道只有在多任务即多道批处理系统中，才可能建立批处理系统中，才可能建立PCBPCB结构，该系统才具有进程活动结构，该系统才具有进程活动) )第37页/共255页PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针系统中可能拥有数十个、数百个乃至数千个PCB，如何组织？第38页/共255页执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索

11、引表就绪表指针阻塞表指针第39页/共255页第40页/共255页第41页/共255页第42页/共255页(1) (1) 创建进程原语创建进程原语 (2) (2) 撤消进程原撤消进程原语语 (3) (3) 挂起进程原语挂起进程原语 (4) (4) 解挂进程原解挂进程原语语(5) (5) 阻塞进程原语阻塞进程原语(6) (6) 唤醒进程原唤醒进程原语语(7) (7) 调度进程运行原语调度进程运行原语(8) (8) 改变优先级改变优先级原语原语第43页/共255页2.2.1 进程的创建进程的创建DEFGHBCIJKLMA第44页/共255页引起创建进程的事件 (1) 用户登录 （分时系统）(2)作业

12、调度 （批处理系统）(3)提供服务 （打印进程）(4)应用请求 系统内核创建进程系统内核创建进程应用程序创建进程应用程序创建进程第45页/共255页进程的创建步骤(Creation of Process) 调用进程创建原语Create（） (1)申请空白PCB (2)为新进程分配资源（内存等） (3)初始化进程控制块 (4)将新进程插入就绪队列 第46页/共255页程序中的第程序中的第1 1语句是调用查找语句是调用查找进程名过程进程名过程“ “ Get Internal Get Internal Name ”Name ”，参数为进程外部名参数为进程外部名n n。该过程查找该过程查找PCBPCB

13、集合，如已集合，如已有此同样外部名进程则返回出有此同样外部名进程则返回出错消息，否则返回一个空闲的错消息，否则返回一个空闲的PCBPCB内部标识号内部标识号i i。第第2 2语句是把进程外部名语句是把进程外部名n n登记登记到第到第i i个个PCBPCB的相应外部名表目的相应外部名表目中。中。语句语句3 3是往是往PCBPCB中登记优先数。中登记优先数。语句语句4 4登记现场状态初始值登记现场状态初始值 S0S0到 相 应 的 现 场 保 留 区 中 或到 相 应 的 现 场 保 留 区 中 或CpustateCpustate中。中。procedure Create (n, Sprocedur

14、e Create (n, S0 0, k, k0 0, M, M0 0, R, R0 0) )beginbegin/ / 请求分配请求分配PCBPCB空间空间i : = Get Internal i : = Get Internal Name(n);Name(n);/ / 初始化初始化PCB PCB Id(i) : =n;Id(i) : =n;Priority(i) : = kPriority(i) : = k0 0; ;Cpustate(i) : = SCpustate(i) : = S0 0; ;Main Store(i) : = MMain Store(i) : = M0 0; ;Res

15、ources(i) : = RResources(i) : = R0 0; ;Status(i) : = Status(i) : = ReadysReadys Parent(i) : = CALLERParent(i) : = CALLER / / 插入就绪队列插入就绪队列Insert(RL,i);Insert(RL,i);endend建立进程原语的工作大致描述为：建立进程原语的工作大致描述为：第47页/共255页 ，分别记入主存和资源的分别记入主存和资源的初始占有情况，这是由父进程初始占有情况，这是由父进程将自己的一部分资源分给子进将自己的一部分资源分给子进程的。程的。是把进程初始状态置为是

16、把进程初始状态置为“ “ 挂起就绪挂起就绪 ” ”。语句语句中中CALLERCALLER代表调用本过代表调用本过程的父进程之内部标识号，将程的父进程之内部标识号，将它记入子进程它记入子进程PCBPCB的父进程名这的父进程名这一栏。一栏。语 句语 句 也 是 调 用 插 入 过 程也 是 调 用 插 入 过 程InsertInsert，其中，其中RLRL表示就绪队列表示就绪队列，即把进程，即把进程i i插入就绪队列。插入就绪队列。procedure Create (n, Sprocedure Create (n, S0 0, k, k0 0, M, M0 0, R, R0 0) )beginbe

17、gin/ / 请求分配请求分配PCBPCB空间空间i : = Get Internal i : = Get Internal Name(n);Name(n);/ / 初始化初始化PCB PCB Id(i) : =n;Id(i) : =n;Priority(i) : = kPriority(i) : = k0 0; ;Cpustate(i) : = SCpustate(i) : = S0 0; ;Main Store(i) : = MMain Store(i) : = M0 0; ;Resources(i) : = RResources(i) : = R0 0; ;Status(i) : = S

18、tatus(i) : = ReadysReadys Parent(i) : = CALLERParent(i) : = CALLER / / 插入就绪队列插入就绪队列Insert(RL,i);Insert(RL,i);endend第48页/共255页2.2.2 进程的终止进程的终止第49页/共255页进程的终止过程进程的终止过程l 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态l 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度l 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的

19、进程l 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统l 将被终止进程(它的PCB)从所在队列(或链表)中移出第50页/共255页2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒第51页/共255页进程的阻塞过程进程的阻塞过程第52页/共255页进程的唤醒过程进程的唤醒过程第53页/共255页2.2.4 进程的挂起与激活进程的挂起与激活进程的挂起第54页/共255页2.2.4 进程的挂起与激活进程的挂起与激活进程的激活第55页/共255页进程控制原语与进程状态转换的对应第56页/共255页UNIX系统实例：1-进程家族树1、系统初启后，由系统核心程序建立init进程。init进

20、程读取文件/etc/ttys，该文件告诉系统共有几个终端并提供每个终端的说明。init进程将为每个终端生成一个子进程，然后将自己阻塞直到所有子进程结束。2、每个子进程等待用户登记（login）使用系统，接着执行shell命令解释程序。3、图例系统中有三个终端。运行在终端0上的子进程仍在等待用户登录；在终端1上的子进程已成功登录了用户，正运行shell等待命令输入；在终端2上的子进程也成功登录了用户，该用户正运行cp程序，cp是shell的子进程，shell 则等待该进程结束。cp结束后，shell再接收输入，创建新进程执行新输入命令。第57页/共255页UNIX系统实例：2-相关系统调用1.f

21、ork系统调用：功能：建立子进程返回值：fork对子进程返回0，对父进程返回子进程的标识符。具体描述：子进程是父进程的一个副本，这就允许父进程可以很容易地与子进程通信。父子进程都从fork后的那条指令继续执行。2. exec系统调用：输入参数：新程序名，功能：以指定程序覆盖当前进程的程序代码。3. wait系统调用：输入参数：进程号功能：等待指定进程结束。第58页/共255页UNIX系统实例：3-shell的内部部分代码显示命令提示符等待用户输入命令行对命令行分析和解释，得到要运行的程序（例如cp）及其运行参数if (pid=fork( )0 ) /*父进程代码，典型地如：*/wait ( p

22、id); /*等待该子进程结束*/显示下一个命令提示符else /*子进程代码，典型地如：*/exec(cp, L);第59页/共255页第60页/共255页2.3 进程的同步进程的同步进程同步进程同步的主要任务，是使并发执行的诸进程之间的主要任务，是使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行能有效的共享资源和相互合作，从而使程序的执行具有可再现性。具有可再现性。第61页/共255页2.3.1 进程同步的基本概念进程同步的基本概念第62页/共255页Out：4In：7进程进程A：N_f_s = In; /In = 7InsertFileIntoSpooler(N_f_s

23、);In=N_f_s+; /In = 8N_f_s4：File15：File26：File37：Null8：NullSpooler目录目录进程切换，一切正常进程切换，一切正常第63页/共255页Out：4In：7进程进程A：N_f_s = In; /In = 7进程进程B：N_f_s = In; /In = 7InsertFileIntoSpooler(N_f_s);In=N_f_s+; /In = 84：File15：File26：File37：Null8：NullSpooler目录目录进程切换进程切换进程进程A：InsertFileIntoSpooler(N_f_s);In=N_f_s+;

24、 /In = 8进程切换，进程进程切换，进程B数据丢失数据丢失第64页/共255页l Get、Copy、Put为三个并发的程序l F、G为保存多条数据的缓冲区，S、T为临时缓冲区l 三个程序顺序执行，可将F的值经过S、T保存到G中l 正常情况下，不存在任何问题，但是程序运行顺序发生变化时，结果可能出错第65页/共255页同步问题举例（同步问题举例（2 2）初始状态FSTG分析程序运行顺序3，4，5221，2G、C、P4，5331，2，3正确G、P、C4，5331，2，2错误C、P、G4，5321，2，2错误C、G、P4，5321，2，2错误P、C、GP、G、C第66页/共255页问题分析两个独

25、立进程如何保持同步？现实应用中存在大量的类似实例司机进程司机进程While(True)While(True) 启动公车；启动公车；驾驶公车；驾驶公车；停止公车；停止公车； 售票员进程售票员进程While(True)While(True) 关车门；关车门；卖车票；卖车票；开车门；开车门； 正确运行过程正确运行过程While(True)While(True) （司机）启动公车；（司机）启动公车；（售票员）关车门；（售票员）关车门；（司机）驾驶公车；（司机）驾驶公车；（售票员）卖车票（售票员）卖车票（司机）停止公车；（司机）停止公车；（售票员）开车门；（售票员）开车门； 第67页/共255页只能排它

26、使用的资源称为临界资源。一次仅允许一个进程使用的资源。第68页/共255页例：二人合作存款例：二人合作存款cobeginPA: N: = count N: = N+100 count: = N;PB: M: = count M: = M+200由由 count: = Mcoendcs1cs2cs1cs2countcs临界区临界区临界资源临界资源执行速度的不同，导致结果不唯一。执行速度的不同，导致结果不唯一。countcount是一个互斥性使是一个互斥性使用的变量用的变量 ( (有排它性有排它性) )。第69页/共255页生产者-消费者问题第70页/共255页由于生产者和消费者并发运行，且共享变

27、量counter counter ，造成：第71页/共255页第72页/共255页可把一个访问临界资源的循环进程描述如下：repeat 进入区进入区 critical section; 临界区临界区 退出区退出区 remainder section; 剩余区剩余区 until false; 第73页/共255页第74页/共255页第75页/共255页假如有两个进程假如有两个进程PiPi和和PjPj，它们共享一个临界资源，它们共享一个临界资源R R。如何用软件方法使进程如何用软件方法使进程PiPi和和PjPj能互斥地访问资源能互斥地访问资源R R呢？呢？程序上如何实现互斥使用临界资源第76页/共

28、255页利用软件解决进程互斥问题利用软件解决进程互斥问题 设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号，若turn=i，表示允许Pi进程进入临界区。该算法可确保每次只允许一个进入临界区 Pj进程:repeat while turnj do no op Critical section turn=iRemain Section until falsePi进程:repeat while turni do no op Critical section turn=jRemain Section until false但采用强制两个进程轮流进入临界区，很容易造成资源利用不充分。缺点：

29、强制两进程轮流进入临界区；不能保证“空闲让进”第77页/共255页利用软件解决进程互斥问题利用软件解决进程互斥问题l在每一个进程访问临界区资源之前，先动查看一下临界资源是否正被访问，若正被访问，该进程需等待，否则才进入自己的临界区。设置了一个数组 flag，如第i个元素值为false表示Pi进程未进入临界区，值为true表示Pi进程进入临界区。Pi: repeat while flagj do no_op; flagi:=true; critical_section; flagi:=false; remainder section; until false Pj: repeat while f

30、lagi do no_op; flagj:=true; critical_section; flagj:=false; remainder section; until false 缺点：会出现缺点：会出现PiPi和和PjPj同时进入临界区错误。先检测对方进程状态标志后再置自己同时进入临界区错误。先检测对方进程状态标志后再置自己标志，由于在检测和放置中可插入另一个进程时检测操作，会造成二个进程在分标志，由于在检测和放置中可插入另一个进程时检测操作，会造成二个进程在分别检测后同时进入临界区。解决了别检测后同时进入临界区。解决了“空闲让进空闲让进”，但又违背了，但又违背了“忙则等待忙则等待”第78

31、页/共255页利用软件解决进程互斥问题利用软件解决进程互斥问题算法2是先检测对方进程状态标志后再置自己标志，由于在检测和放置中可插入另一个进程时检测操作，会造成二个进程在分别检测后同时进入临界区。为此算法3采用先设置自己标志后再检测对方状态标志，它的程序如下。Pj: repeat flagj:=true; while flagi do no_op; critical_section; flagj:=false; remainder section; until falsePi: repeat flagi:=true; while flagj do no_op; critical_section

32、; flagi:=false; remainder section; until false缺点：可能出现二个进程先后同时设置后再分别检测对方状态标志，造成缺点：可能出现二个进程先后同时设置后再分别检测对方状态标志，造成对方都不能进入临界区，无限期等待。解决了对方都不能进入临界区，无限期等待。解决了“忙则等待忙则等待”，但又违背了，但又违背了“空闲让进空闲让进”和和“有限等待有限等待”第79页/共255页利用软件解决进程互斥问题利用软件解决进程互斥问题 Repeat flagi = false Critical section; Remainder sectiont; Until flase;

33、 flagi:= true; turn:=j; While (flagj and turn=j) do no-op; 说明：说明：Flagi=true PiFlagi=true Pi要进或正进要进或正进turn=jturn=j应轮到应轮到PjPjPi第80页/共255页l 组合了算法组合了算法1 1和算法和算法3 3，既实现了，既实现了“空闲让进空闲让进”，又保证了，又保证了“忙则等待忙则等待”l 为了防止二进程进入临界区而无限期等待，又为了防止二进程进入临界区而无限期等待，又设置变量设置变量turnturn，表示不允许进入临界区的编号，表示不允许进入临界区的编号，每个进程在先设置自己标，每个

34、进程在先设置自己标志后再设置志后再设置turnturn标志，不允许另一个进程进入，这时再同时标志，不允许另一个进程进入，这时再同时检测另一个进程状态标志和不允许进入标志，这样可以保证检测另一个进程状态标志和不允许进入标志，这样可以保证当二个进程同时要求进入临界区时，只允许一个进程进入临当二个进程同时要求进入临界区时，只允许一个进程进入临界区。界区。l 缺点：四种算法全部属于缺点：四种算法全部属于“忙等待忙等待”方式，现在已很少使用方式，现在已很少使用。第81页/共255页利用硬件解决进程互斥问题利用硬件解决进程互斥问题第82页/共255页第83页/共255页开锁操作： lock false，任

35、何机器一条指令可以实现。关锁操作 ：共有3步 （1）测试lock的值是false，才可关锁。 （2）lock true （3）原lock值为true时，返回。等待别的进程释放资源后开锁。 前两步应作为一个整体来执行，不可分开，这样才能保证在前两步之间，lock不被别的进程改变。这一点在许多机器中都提供了专门的硬件指令来实现。不同的机器，指令略有不同，但基本功能是相同的，例如在IBM370系列机中的TS指令（test and set），和在Intel 8086中的XCHG（交换指令）。第84页/共255页检测和设置（TS）的功能可用PASCAL语言描述如下：function TS(var loc

36、k：boolean): boolean；begin TS:=lock; Lock:=true;EndC+语言描述如下: bool TS(bool& lock)if(lock=true)return true;elselock=true; return false;第85页/共255页l 程序中的第一条语句用于检查TS指令执行后的TS状态。若为false表示资源空闲，进程可进入临界区；否则，不断测试执行TS指令后的TS变量值，直至其为false。l 当进程退出临界区时，设置变量lock为false，以允许其它进程进入临界区。l 可为每个临界资源设置一可为每个临界资源设置一个布尔变量个布尔变量1o

37、ck1ock，并赋予其初，并赋予其初值为值为falsefalse，以表示资源空闲，以表示资源空闲。利用。利用TSTS指令实现互斥的循环指令实现互斥的循环进程可描述为：进程可描述为： 关锁操作关锁操作 Repeat Lock := false; Critical section; Remainder section; Until false; While TS(lock) do skip; 开锁操作开锁操作 利用利用TSTS实现进程互斥实现进程互斥第86页/共255页l 在利用Swap实现进程互斥时，可为临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中再利用一个局部布尔变量

38、key。利用Swap指令实现进程互斥的循环进程可描述为： Repeat Lock := false; Critical section; Remainder sectiont; Until flase; Key:=true; Repeat Swap(lock,key); until key = false; 利用交换指令利用交换指令SwapSwap实现进程互斥实现进程互斥第87页/共255页锁方法缺点：l“忙等”，违背了“让权等待”原则l 某种临界资源只能一个进程使用l 很难用它解决复杂的同步问题第88页/共255页2.3.2 信号量机制信号量机制第89页/共255页信号量机制信号量机制整型信

39、号量整型信号量wait(S): while S0 do no-op S =S-1;signal(S): S =S+1;Wait操作，只要信号量S 0，就会不断测试，忙等，违背让权等待。 第90页/共255页思考题：设有两个优先级相同的进程思考题：设有两个优先级相同的进程P1P1、P2P2如下。令信号量如下。令信号量S1S1、S2S2的初值为的初值为0 0，已知，已知z=2z=2，试问，试问P1P1、P2P2并发运行后并发运行后x=?y=?z=?(x=?y=?z=?(北航北航2001)2001)进程进程P1 P1 进程进程P2 P2 y:=1; x:=1;y:=y+2; x:=x+1;V(S1)

40、; P(S1);z:=y+1; x:=x+y;P(S2); V(S2); y:=z+y; z:=z+x;第91页/共255页l y:=z+y在z:=z+x之前 x=5 , y=12 , z=9l y:=z+y在z:=z+x之后 x=5 , y=7, z=9结果结果第92页/共255页记录型信号量记录型信号量第93页/共255页信号量机制信号量机制记录型信号量记录型信号量数据结构数据结构type semaphore=record value:integer; L:list of process; endprocedure wait(S) var S: semaphore; begin S.val

41、ue:=S.value-1; if S.value0 then block(S,L) endprocedure signal(S) var S: semaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S,L); end 第94页/共255页第95页/共255页前趋关系处理程序或语句间的前趋关系信号量应用举例信号量应用举例第96页/共255页利用信号量实现进程互斥利用信号量实现进程互斥第97页/共255页var mutex：semaphore：l；begin parbegin process 1:begin repeat wai

42、t(mutex); critical section signal(mutex); remainder section until false; end process 2:begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend第98页/共255页下面是两进程模拟执行情况：下面是两进程模拟执行情况：如果如果P2P2先进入临界区，则先进入临界区，则P1P1等待，等待，P1P1，P2P2不会同时进入临界区。不会同时进入临界区。第99页/共255页 1 1

43、无进程进入临界区无进程进入临界区mutexmutex= 0 1= 0 1个进程在临界区个进程在临界区 -1 1-1 1个进程在等待临界区个进程在等待临界区（对两个进程：（对两个进程：mutexmutex只能取三个值）只能取三个值）用用mutexmutex实现实现n n个进程的互斥时，个进程的互斥时，mutexmutex取值？取值？ 1 -(n-1)1 -(n-1)第100页/共255页利用信号量实现前趋关系利用信号量实现前趋关系l 设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。希望在S1执行后再执行S2，怎么办？l 为实现这种前趋关系，用一个公用信号量S并赋予其初值为初

44、值为0 0，且使P1、P2取如下形式： P1 中： S1S1；signalsignal（S S）；）； P2 中： waitwait（S S）；）； S2S2； 第101页/共255页S4S5S3S1S6S2 前趋图举例前趋图举例 第102页/共255页 Var a,b,c,d,e,f,g; semaphore =0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e);

45、 end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end 第103页/共255页信号量机制信号量机制AND型信号量型信号量第104页/共255页AND型信号量型信号量第105页/共255页 if Si1 and and Sn1 then for i =1 to n do Si =Si-1; endfor else place the process in the waiting queue ass

46、ociated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endifSwait(S1, S2, , Sn)第106页/共255页 for i =1 to n do Si=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue. endfor; Ssignal(S1, S2, , Sn)第107

47、页/共255页信号量机制信号量机制信号量集信号量集第108页/共255页 If S1 = t1 AND s2 = t2 Sn = tn then for I := 1 to n do Si:= Si di; endfor else place the process in the waiting queue associated with the first Si found with Si =1 then L:=L-1 Else waiting endif If mx =1 then mx:=mx-0 Else waiting endif 利用信号量集机制解决读者利用信号量集机制解决读者-写

48、者问题写者问题 L :=L+1 第143页/共255页 writer:begin repeat Swait(mx,1,1; L,RN,0);Swait(mx,1,1; L,RN,0); perform write operationperform write operation; ; Ssignal(mx,1);Ssignal(mx,1); until false; end parend end If mx =1 and L=RN then mx:=mx-1; L:=L-RN; Else waiting endif mx :=mx+1 第144页/共255页第145页/共255页2.4.3 睡

49、眠理发师问题问题描述一把理发椅，N把等待座位理发师为理发椅上的顾客理发，没有顾客就在理发椅上睡觉有一个顾客时需要叫醒理发师多个顾客时需要在等待座位上等候第146页/共255页互斥关系分析理发椅上只能有一位顾客等待座位是有限缓冲区同步关系分析只要存在顾客，理发师就不能睡觉信号量设计互斥信号量：实现对“等待顾客数”的互斥同步信号量1：理发师“睡眠”和“工作”的同步同步信号量2：等待顾客与等待座位的同步第147页/共255页 var waiting : integer; /*等候理发的顾客数*/ CHAIRS: integer; /*为顾客准备的椅子数*/ customers, barbers，mu

50、tex : semaphore; customers := 0; barbers := 0; waiting := 0; mutex := 1;第148页/共255页Procedure barber;beginwhile(TRUE); /*理完一人,还有顾客吗?*/ P( P(cutomerscutomers); ); /*若无顾客,理发师睡眠*/ P(mutex); /*进程互斥*/ waiting := waiting 1; /*等候顾客数少一个*/ V(barbers); V(barbers); /*理发师去为一个顾客理发*/ V(mutex); /*开放临界区*/ cut-hair(

51、); /*正在理发*/end;第149页/共255页procedure customerbegin P(mutex); /*进程互斥*/ if waitingCHAIRS begin /*看看有没有空椅子*/ waiting := waiting+1; /* 等候顾客数加1*/ V(customers); V(customers); /*必要的话唤醒理发师*/ V(mutex); /*开放临界区*/ P(barbers); P(barbers); /*无理发师, 顾客坐着养神*/ get-haircut( ); /*一个顾客坐下等理发*/ end else V(mutex); /*人满了,走吧

52、!*/end;第150页/共255页第151页/共255页请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。第152页/共255页【解析】Semaphore seets = 10; /表示空余座位数量的资源信号量，初值为10Semaphore mutex = 1; /管理取号机的互斥信号量，初值为1，表示取号机空闲。Semaphore custom = 0; /表示顾客数量的资源信号量，初值为0第153页/共255页第154页/共255页优点分析彻底解决忙等待忙等待弊端，提高OS的管理层次可实现复杂复杂

53、的同步与互斥情况，特别是多进程多进程间通信可最大限度的保证并发效率缺点分析实现机制复杂复杂，互斥和同步关系分析困难存在死锁陷阱，需要谨慎小心严密的设计第155页/共255页1.有桥如图所示，车流方向如箭头所示。回答下列问题：有桥如图所示，车流方向如箭头所示。回答下列问题：桥假设：该桥上每次只能有一辆车行驶，试用信号量的假设：该桥上每次只能有一辆车行驶，试用信号量的P、V操作实现桥上的交通管理。操作实现桥上的交通管理。假设：该桥上不允许两车交会，但允许同方向多个车依假设：该桥上不允许两车交会，但允许同方向多个车依次通过（即桥上可有多个同方向行驶的车）。试用信号次通过（即桥上可有多个同方向行驶的车

54、）。试用信号量的量的P、V操作实现桥上的交通管理。操作实现桥上的交通管理。第156页/共255页.第157页/共255页第158页/共255页.第159页/共255页第160页/共255页ParBegin Var x: integer; Process P1 Var y, z:integer; Begin x:=1; y:=0; If x1 then y:=y+1; z:=y; End; Process P2 Var t,u:integer; Begin x:=0; t:=0; If x1 then t:=t+2; u:=t; End;ParEnd1、下面是两个并发执行的进程。试回答：1) 它

55、们能正确执行吗（有唯一确定的结果）？若不能，试举例说明2)进行适当修改，使两个并发执行的进程能够正确执行。课堂讨论题课堂讨论题第161页/共255页第162页/共255页2 2、 对于诸如公共汽车上驾驶员和售票员的工作，如视其为对于诸如公共汽车上驾驶员和售票员的工作，如视其为2 2个进个进程，试用程，试用P.VP.V操作控制这类关系。操作控制这类关系。（可直接在下面加（可直接在下面加P.VP.V操作，并给出信号量初值）操作，并给出信号量初值） 驾驶员驾驶员售票员售票员 L1L1：L2L2： 停车停车开车门开车门 开车开车关车门关车门goto L1goto L1goto L2goto L2第16

56、3页/共255页 到站停车到站停车 开开 车车 开开 车车 门门 关关 车车 门门 售售 票票 正常行车正常行车。售票员售票员司机司机第164页/共255页3、某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定： （1）每2个学生组成一组，各占一台机器，合作完成上机实习。 （2）只有一组2个学生到齐，并且此时机房有空闲机器时，该组学生才能进入机房。 （3）上机实习由一名教师检查，检查完毕，一组学生同时离开机房，试设计相应的数据结构，并用P.V操作模拟上机实习过程。第165页/共255页4、设有三个进程P1，P2，P3共用一个缓冲池协同工作。P1和P2负责循

57、环地分别从设备1和设备2上输入数据，“加工”后送入缓冲池，P3负责循环地以任何顺序从缓冲池中取数据在设备3上输出。缓冲池中共有9个长度相等的缓冲区（进程每次传输的数据与缓冲区长度相同），初始均为空。利用两个栈S1和S2分别记录空，满缓冲区始地址。 （1）试写出各进程工作流程示意图； （2）进程间是否存在临界区问题，为什么？ （3）用P.V操作控制各进程正确运行。第166页/共255页进程的基本概念 进程控制 进程同步 经典进程的同步问题 管程机制 进程通信 线程 第167页/共255页第168页/共255页第169页/共255页图 2-11 管程的示意图 共享数据一组操作过程初始化代码进入队列

58、条件(不忙)队列第170页/共255页type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 第171页/共255页第172页/共255页第173页/共255页第174页/共255页第175页/共255页第176页/共255页第177页/共255页第178页/共255页 第179页/共255页typ

59、e producer-consumer=monitortype producer-consumer=monitor var in,out,count:integer; var in,out,count:integer; buffer:array buffer:array0,n-10,n-1 of item;of item; notfull, notempty:condition; notfull, notempty:condition; procedure entry put(item)procedure entry put(item) begin begin if countn then i

60、f countn then notfull.wait;notfull.wait; buffer(in)=nextp; buffer(in)=nextp; in=(in+1) mod n; in=(in+1) mod n; count=count+1; count=count+1; if notempty.queue then if notempty.queue then notempty.signal;notempty.signal; end end procedure entry get(item) begin if count0 then notempty.wait; nextc =buf