计算机操作系统课件

1、计算机操作系统,南京工业大学信息学院计算机系,2,总 目 录,第1章 操作系统引论 第2章 进程管理 第3章 处理机调度与死锁 第4章 存储器管理 第5章 设备管理 第6章 文件管理 第7章 操作系统接口,3,课内上机实验,进程的创建 线程的创建 进程同步 进程通信 进程调度 银行家算法 页面置换算法的模拟 磁盘I/O 命令解释程序,【说明】以上9个上机实验，共计22学时(包括2个进阶要求的4学时)，可以选择其中的4次实验(共8学时)作为课内上机实验任务。,第1次实验(进程管理),第4次实验(操作系统接口),第3次实验,(存储器管理) (设备管理),(4选1),(2选1),(2选1),4,第1

2、章 操作系统引论,1.1 OS的目标和作用 1.2 OS的发展过程 1.3 操作系统的基本特征 1.4 操作系统的主要功能 1.5 操作系统的结构设计 第1章复习题,5,1.1.1 OS的目标,有效性 方便性 可扩展性 开放性,操作系统（Operating System , OS）是计算机硬件上的第一层软件，是计算机必须配置的最基本、最重要的系统软件。,1.1 OS的目标和作用,6,1有效性(早期OS的主要目标) 有效提高CPU和I/O设备利用率 提高的方法：合理地组织计算机的工作流程 2方便性(现在OS越来越重视方便性) 可使计算机系统更容易使用(解释之),方便性和有效性是设计OS的两个最重

3、要的目标,7,3可扩展性,计算机硬件和体系结构的发展，对OS提出了更高的功能和性能要求 计算机网络，特别是Internet的发展，也对OS提出了一系列更高的要求,为什么要有可扩充性？ 因为：,OS为了能适应发展的要求，须具有良好的可扩充性。,如何才有可扩充性？ 应采用新的OS结构，如微内核结构和客户服务器模式。,8,4开放性 为什么要有开放性？ 计算机网络，特别是LAN的迅速发展，使OS的应用环境由单机转向网络环境。为使不同厂家的计算机和设备能通过网络加以集成化，并能正确、有效地协同工作，实现应用的可移植性和互操作性，必须具有统一的开放环境，进而要求OS具有开放性。 什么是开放性？ 开放性是指

4、系统能遵循世界标准规范，特别是遵循开放系统互连（OSI）国际标准。,9,从用户观点看，OS是用户和计算机硬件系统之间的接口 从资源管理观点看，OS是计算机系统资源（软、硬）的管理者,1.1.2 OS的作用,1OS作为用户和计算机硬件系统的接口 2OS作为计算机资源的管理者 3OS实现了对计算机资源的抽象,操作系统的作用:,10,1.OS作为用户和计算机硬件系统的接口(用户接口),用户可以通过三种方式使用计算机：,命令方式（键盘命令） 图标、窗口方式（GUI） 系统调用方式（程序接口）,操作接口,1.1.2 OS的作用,11,计算机系统资源可归结为四类：处理器、存储器、I/O设备、信息（数据和程

5、序） OS的主要功能也正是针对这四类资源进行有效管理：,2. OS作为计算机资源的管理者,处理机管理：分配和控制处理机 存储器管理：主要是内存分配和回收 I/O设备管理：I/O设备的分配与操纵 文件管理：文件的存取、共享和保护,12,完全无软件的计算机裸机。 “裸机”难于使用。 裸机覆盖了一层I/O设备管理软件如图1-2所示，由它来实现对I/O设备操作的细节，并向上提供一组I/O操作命令，如Read和Write命令，用户可以利用它进行数据输入/输出，而无需关心I/O实现的细节。此时用户所看到的是一台功能显著增强、使用极为方便的的机器，它向上提供了一组抽象的I/O设备，称为扩充机或虚拟机。,3.

6、 OS实现了对计算机资源的抽象,虚拟性是OS的基本特征之一,第一层软件,第二层软件,13,为了方便用户使用文件系统，又在第一层软件上再覆盖一层用于文件的管理软件，用它来实现对文件操作的细节，并向上提供一组对文件进行存取操作的命令。第二个层次的抽象。 又在文件管理软件上再覆盖一层面向用户的窗口软件，用户便可在窗口环境下方便地使用计算机，形成一台功能更强的虚拟机。 由此可知，操作系统是铺设在硬件上的多层系统软件，它们不仅增强了系统功能，而且还隐藏了对硬件操作的细节，由它们实现对计算机硬件的多个层次的抽象。,14,1.1.3 推动OS发展的主要动力,1不断提高计算机资源利用率。,2方便用户: 继续发

7、展的因素分时系统（或称多用户系统）,3器件的不断更新换代,4计算机体系结构的不断发展,最初发展的动力。批处理系统,8位机16位机32位机64位机(8位OS 16位OS . ),单机系统多处理机系统：单机OS多处理机OS 计算机网络：网络OS,15,1.2 OS的发展过程,20世纪50年代中期，第一个简单的批处理系统 60年代中期，多道程序批处理系统，随后出现分时系统 上世纪80年代开始至21世纪初，微型机、多处理机、计算机网络大发展年代微机OS、多处理机OS和网络OS的形成和大发展年代。,16,1.2.1 无OS的计算机系统,人工操作方式 脱机输入/输出（Off-Line I/O）方式 （20

8、世纪50年代末 ）,这一时期有两种操作方式：,17,1人工操作方式,程序员将事先已穿孔（对应于程序和数据）的纸带（或卡片）装入纸带输入机（或卡片输入机）； 再启动输入机将程序和数据输入计算机； 然后启动计算机运行。 当程序运行完毕并取走计算结果后，才让下一个用户上机。,缺点：,用户独占全机； CPU等待人工操作,18,2脱机输入/输出方式,优点：,（1）减少了CPU的空闲时间 （2）提高了I/O速度,19,1.2.2 单道批处理系统,把一批作业以脱机方式输入到磁带上； 在监督程序（Monitor）控制下使这批作业 一个接一个地连续处理。 参看下页的图1-3,它是OS的前身，而非现在人们理解的O

9、S。,1. 单道批处理系统的处理过程,20,开始,还有下一个作业？,停止,把下一个作业的源程序转换为目标程序,源程序有错吗？,装配目标程序,目标程序运行 直到结束,否,是,是,否,图1-3 单道批处理系统的处理流程,21,2. 单道批处理系统的特征,(1) 自动性,在磁带上的作业能自动地逐个地依次运行，而无需人工干预。,(2) 顺序性,(3) 单道性,磁带上的各道作业是顺序地进入内存，各道作业的完成顺序与它们进入内存的顺序相同，即先调入内存的作业先完成。,在内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。,22,

10、1.2.3 多道批处理系统,多道程序设计的基本概念,20世纪60年代中期,用户提交的作业事先存放在外存上，形成“后备队列” 作业调度程序按一定算法从后备队列中选择若干作业调入内存，使它们共享CPU和系统中的各种资源。,好处：,（1）提高CPU利用率 （2）提高内存和I/O设备利用率 （3）增加系统吞吐量,23,多道批处理系统的特征,(1) 多道性：,多道程序在内存中并发执行。提高了资源利用率和系统吞吐量。,(2) 无序性：,先进入内存的作业可能后完成；后进入内存的作业可能先完成。,(3) 调度性：,作业从提交到完成，需经过两种调度：作业调度和进程调度。,24,多道批处理系统的优缺点：,（1）资

11、源利用率高。(CPU、内存、I/O设备利用率),（2）系统吞吐量大。,（3）周转时间长。,（4）无交互能力。,系统吞吐量是指系统在单位时间内所完成的总工作量。,作业周转时间是指从作业进入系统（提交）开始，直至它完成并退出系统为止所经历的时间。,对修改和调试程序极不方便。,25,多道批处理系统需要解决的问题,（1）处理机管理问题(处理机分配、提高利用率) （2）内存管理问题(分配、保护等) （3）I/O设备管理问题(方便用户、提高利用率) （4）文件管理问题(方便用户、数据安全一致) （5）作业管理问题(计算型、I/O型不同处理),26,1.2.4 分时系统,分时系统是指在一台主机上连接多个带有

12、显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。,27,1. 分时系统的产生,是为了满足用户的以下需求而产生的：,（1）人-机交互 （2）共享主机 （3）便于用户上机,28,2分时系统实现中的关键问题,（1）及时接收 （2）及时处理,用户作业不能先进入磁盘，然后再调入内存 不允许一个作业长期占用处理机，直至它运行结束或出现I/O请求后，方才调度其它作业运行 应该规定每个作业只运行一个很短的时间（称为时间片）,要做到上述两条，必须彻底改变批处理系统的运行方式，即：,29,3分时系统的特征,（1）多路性：,允许一台主机上同时联接多个联机终端,（2）独立性

13、：,每个用户各占一个终端，彼此独立操作，互不干扰。,（3）及时性：,用户的请求能在很短时间内获得响应。,（4）交互性：,用户可通过终端与系统进行广泛的对话。,30,1.2.5 实时系统,实时系统（Real-Time System） 是指系统能及时响应外部事件的请求，在规定时间内完成该事件的处理，并控制所有实时任务协调一致地运行。,定义：,31,1应用需求,（1）实时控制。,飞机或火车的订票系统、情报检索系统等 。,（2）实时信息处理。,实时数据采集处理；执行机构；自动控制,32,2实时任务,在实时系统中必然存在着若干个实时任务，这些实时任务通常与某个（某些）外部设备相关，能反映或控制相应的外部

14、设备，因而带有某种程度的紧迫性。,周期性实时任务,按指定周期循环执行，以便周期性地控制某外部设备。,非周期性实时任务,外部设备发出的激励信号无明显周期性，但都必须联系着一个截止时间。,开始截止时间任务在某时间以前必须开始执行 完成截止时间任务在某时间以前必须完成,分类：按执行是否周期性划分,33,分类：实时任务按对截止时间要求划分,硬实时任务,软实时任务,系统必须满足任务对截止时间的要求，否则可能出现难于预测的结果。,它也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大。,34,3实时系统与分时系统特征的比较,（1）多路性：,实时系统的多路性主要表现在：系

15、统经常对多路的现场信息进行采集，以及对多个对象或多个执行机构进行控制。,（2）独立性：,实时系统中对信息的采集和对对象的控制，也都是彼此互不干扰,（3）及时性：,实时系统的及时性，是以控制对象所要求的开始截止时间或完成截止时间来确定的。一般为秒级、百毫秒级直至毫秒级，甚至有的要低于100微秒。,（4）交互性：,实时系统的交互性仅限于访问系统中某些特定的专用服务程序，不象分时系统那样能向终端用户提供数据处理服务、资源共享等服务。,（5）可靠性：,实时系统要求系统高度可靠，往往采用多级容错措施来保证系统的安全性及数据的安全性。,35,1.2.6 微机操作系统的发展,1单用户单任务操作系统,CP/M

16、 上世纪70年代(8位机) MS-DOS 上世纪80年代(16位机/32位机),2单用户多任务操作系统,Windows 95 Windows 98 Windows XP Windows NT,兼容16位应用程序的32位操作系统,36,3多用户多任务操作系统,UNIX OS(AT counter = register1；,消费者执行的操作： register2 = counter ； register2 = register2 - 1 ； counter = register2；,109,假设某一时刻counter的值为5，生产者和消费者同时对counter操作，按下述顺序执行：,registe

17、r1 = counter; (生产者取得counter的当前值为5) register1 = register1 + 1; (生产者将该值增1变为6) register2 = counter; (消费者取得counter的当前值为5) register2 = register2 1; (消费者将该值减1变为4) counter = register2; (消费者保存counter的新值4) counter = register1; (生产者保存counter的新值6),最终counter的值为6，正确的值应是5，出现了差错。 学生考虑：什么情况会出现counter最终值为4的情况。,解决此问题

18、的关键，是应将变量counter作为临界资源处理，亦即让生产者进程和消费者进程互斥地访问变量counter。,110,2.3.1 进程同步的基本概念,3临界区（critical section）,每个进程中访问临界资源的那段代码称为临界区。,不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它们访问。,显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界区的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看是否正被访问，如果此刻该资源未被访问，便可进入临界区对该临界资源进行访问，并设置它正被访问的标志；如果此刻它正被访问，则本进程不能进入临界区。,

19、定义：,进程互斥的定义：,进程互斥不允许两个或两个以上进程同时访问同一个临界资源。 进程互斥不允许两个或两个以上进程同时进入相关临界区。,111,因此必须在临界区前增加一段用于上述检查的代码，把这段代码称为进入区(entry section) 相应地，在临界区后面也要加上一段称为退出区(exit section)的代码，用于将临界区正被访问的标志恢复为未被访问的标志。,repeat 非临界区 进入区 临界区 退出区 非临界区 until false,一般结构,“进入区”和“退出区”的不同构成方法，形成了各种不同的同步机制。,112,4同步机制应遵循的原则,为了实现各进程互斥地进入自己的临界区，

20、一般是在系统中设置专门的同步机制来协调各进程间的运行。,所有同步机制都应遵循如下四条准则：,空闲让进,当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以便有效地利用临界资源。,空闲让进、忙则等待、有限等待、让权等待。,113,有限等待,让权等待,对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死锁”状态。不死等。 不互相阻塞。,当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。不忙碌等待。,忙则等待,当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临

21、界资源的互斥访问。,114,2.3.2 信号量机制,信号量(Semaphores)机制是一种卓有成效的进程同步工具。信号量机制已被广泛应用于单处理机和多处理机系统以及计算机网络中。,信号量机制的发展：,整型信号量,记录型信号量,AND型信号量,信号量集,“忙等”，未遵循“让权等待”准则。略。,后边重点介绍。,115,2、记录型信号量,需要一个用于代表临界资源数目的整型变量value；还要一个在该资源上阻塞的队列（链表）指针L。故信号量应采用记录型（C语言中为结构型）的结构：,struct semaphore int value ； PCB *L ； ；,记录型信号量的结构定义,信号量除初始化外

22、，只能通过两个原子操作(称为原语)wait(S)和signal(S)来访问。它们以前被称为P、V操作。下页介绍wait和signal操作。,116,wait和signal操作可用C/C+语言描述如下：,void wait( semaphore S) S.value = S.value 1 ; if (S.value 0 ) block (S.L ) ; /* 让权等待 */ ,void signal (semaphore S ) S.value = S.value + 1 ; if ( S.value = 0 ) wakeup ( S.L ) ; /*唤醒第一个等待的进程 */ ,P(S),V

23、(S),117,Win32中创建信号量对象的API函数是CreateSemaphore( )； 对应的wait操作是wait类函数，例如WaitForSingleObject( )或WaitForMultipleObjects( )等；与signal操作对应的API函数是 ReleaseSemaphore( )。详见Woed文档“OS课内上机实验使用的相关API函数介绍.doc”或查看MSDN。,创建信号量对象时指定信号量的初值。 执行wait类函数时，信号量值减1；信号量值为0时，执行wait类函数时其值不再减1，而是使调用wait函数的进程(实际上是线程)阻塞。 执行ReleaseSema

24、phore函数，信号量的值增加指定的增量并唤醒一个阻塞的进程。,关于Windows的同步机制，请参阅文档“操作系统课内上机指导书2012.doc”中的3.2节的介绍。,118,wait和signal操作的物理意义：,对信号量S的每次wait操作，意味着进程请求一个该类临界资源，因此描述为S.value=S.value-1；当S.value0时，表示该类资源已分配完，因此进程应调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表S.L(阻塞队列)中。可见该机制遵循了“让权等待”准则。 类似地，可以解释signal操作,S.value的初值表示系统中某类资源的数目。资源信号量。 S.va

25、lue的初值为1，表示只允许一个进程访问，此时信号量转化为互斥信号量。,119,作业1进程同步(1),(2011全国试题)有两个并发进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。,/加1操作 load R1, x /取x到寄存器R1中 inc R1 store x, R1 /将R1的内容存入x,/减1操作 load R2, x dec R2 store x, R2,两个操作完成后，x的值 。 A可能为-1或3B只能为1 C可能为0、1或2D可能为-1、0、1或2,作业中部分题目讲解：,C,120,3. S.queue，S.value是信

26、号灯S的两个组成部分，当S.queue为空时，S.value的值是 。 AS.value0 BS.value=0 CS.value=1 DSvalue0 4. 如果信号量的当前值为-3，则表示系统中在该信号量上有 个等待进程。 7. 设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则M、N分别是_。(2010年全国考研试题) A0、1B1、0 C1、2D2、0,B,D,3,121,设有n个进程使用同一个共享变量，如果最多允许m(m n)个进程同时进入相关临界区，则信号量的变化范围是 。 n,n-1,.,n-m m,m-1,.1,0,-1,.m-n

27、 m,m-1,.1,0,-1,.m-n-1 m,m-1,.1,0,-1,.m-n+1,B,122,3、AND型信号量(不作基本要求),Swait(S1,S2,.,Sn) if S1=1 从所有Si等待队列中移出进程并置入就绪队列。 ,以便下次重新执行Swait操作,123,4、信号量集(不作基本要求),Swait(S1,t1,d1,S2,.,Sn,tn,dn) if S1=t1 从所有Si等待队列中移出进程并置入就绪队列。 ,124,2.3.3 信号量的应用,1利用信号量实现进程互斥,方法要点：,为每个临界资源设置一个互斥信号量mutex，其初值为1； 各进程访问该资源前执行wait(mute

28、x)操作，离开临界区时执行signal (mutex)操作。,请看下页的例子,非临界区 wait(mutex) /进入区 临界区 signal(mutex) /退出区 非临界区,125,利用信号量实现进程互斥的简单例子,某交通路口设置了一个自动计数系统，该系统由“观察者”进程和“报告者”进程组成。观察者进程能识别卡车，并对通过的卡车计数；报告者进程定时（可设为每隔1小时，准点时）将观察者的计数值打印输出，每次打印后把计数值清“0”。两个进程的并发执行可完成对每小时中卡车流量的统计。这两个进程的功能如下：,process observer while (condition) observe a

29、lorry; wait（S）; count = count + 1; signal（S）; ,临界区,process reporter wait（S）; print（count）; count = 0； signal（S）; ,临界区,semaphore S ；int count = 0 ；S.value = 1 ；,【注意】wait (S)和signal (S)必须成对出现,126,利用信号量实现前趋关系,【例】利用信号量，描述语句的前趋关系（见图2-12）,写出一个可并发执行的程序。,图中表示： 进程P1中有语句S1； 进程P2中有语句S2； ,P1执行完应通知P2、P3； P2得到通知后

30、才开始执行；P2执行完应通知P4、P5；,语句S1执行后才能执行语句S2和语句S3； 语句S2执行后才能执行语句S4和S5； 语句S3、S4和S5执行后，才能执行语句S6。,127,semaphore S12,S13,S24,S25,S36,S46,S56; S12.value=S13.value=0; S24.value=S25.value=0; S36.value=S46.value=S56.value=0;,程序描述如下：,初始化,parbegin / parbegin表示并发执行开始 process P1： 执行S1; signal(S12); signal(S13); process

31、 P2： wait(S12); 执行S2; signal(S24); signal(S25); process P3： wait(S13); 执行S3; signal(S36); process P4： wait(S24); 执行S4; signal(S46); process P5： wait(S25); 执行S5; signal(S56); process P6： wait(S36); wait(S46); wait(S56); 执行S6; parend / 用parend表示并发执行结束,128,2.4 经典进程同步问题,生产者-消费者问题 读者-写者问题 哲学家进餐问题,在多道程序环境

32、下，进程同步问题十分重要，引起了不少学者对它进行研究，由此产生了一系列经典的进程同步问题，其中较有代表性的是：,通过对这些问题的研究和学习，可以帮助我们更好地理解进程同步概念及实现方法。,129,2.4.1 生产者-消费者问题,前面已经对生产者-消费者问题做了一些描述，但是未考虑进程的互斥和同步问题，因而造成了共享变量counter的不确定性。 生产者-消费者问题是相互合作进程关系的一种抽象，例如，,先介绍最简单的P-C问题,生产者-消费者问题从特殊到一般(从易到难)可以分3种形式：,一个生产者、一个消费者、一个缓冲区的问题； 一个生产者、一个消费者、n个缓冲区的问题； k个生产者、m个消费者

33、、n个缓冲区的问题；,130,最简单的生产者-消费者问题,一个生产者、一个消费者、一个缓冲区的问题如右图所示。,当缓冲区空时，生产者可将产品存入缓冲区；当缓冲区满时，生产者必须等待 (阻塞)，待消费者取走产品后将其唤醒后，才能将产品存入。 当缓冲区有产品时，消费者可从缓冲区取出产品进行消费；当缓冲区空时，消费者必须等待(阻塞)，待生产者存入产品后将其唤醒后，才能再从缓冲区取产品。,131,用信号量机制解决P-C问题的基本方法：,为生产者设置1个私有信号量empty，其初值为1，表示有1个空缓冲区；为消费者设置1个私有信号量full，其初值为0，表示开始时没有满缓冲区；（信号量初值由物理意义确定

34、） 生产者将产品存入缓冲区之前，应先测试缓冲区是否空：执行wait(empty)操作；离开临界区(存入产品)后，应通知(可能会唤醒)消费者：执行signal(full)操作； 消费者从缓冲区取产品之前，应先测试缓冲区是否满：执行wait(full)操作；离开临界区(取走产品)后，应通知(可能会唤醒)生产者：执行signal(empty)操作,132,最简单的生产者-消费者问题,一个生产者、一个消费者、一个缓冲区的生产者-消费者问题的算法描述如下所示：,semaphore empty,full; empty=1;full=0; parbegin process Producer: . produ

35、ce an item in nextp; wait(empty);/测试 buffer=nextp; signal(full);/通知消费者 ,process Consumer: wait(full); /测试 nextc=buffer; signal(empty); /通知 consume the item in nextc; parend,133,信号量机制解决进程同步问题的一般方法：,为同步双方设置各自的信号量，初值为其初始状态可用的资源数(故该信号量称为资源信号量或私有信号量)； 同步双方任一进程在进入临界区之前，应先对自己的信号量执行wait()操作，以测试是否有自己可用的资源。若有

36、资源可用，则进入临界区，否则阻塞； 同步双方任一进程离开临界区后，应对合作方 (对方)的信号量执行signal()操作，以通知(若对方处于阻塞状态，则唤醒它)对方已有资源可用(对方已可进入临界区)。,134,生产者-消费者问题的第二种特殊情况,一个生产者、一个消费者、n个缓冲区的P-C问题,为生产者设置一个资源信号量empty，其初值为生产者的可用资源数(空缓冲区的个数)n，即empty=n。 为消费者设置一个资源信号量full，其初值为消费者的可用资源数(满缓冲区的个数)0，即full=0。,empty=n,full=0,135,semaphore empty,full; empty=n;f

37、ull=0; int in=0,out=0; /下标 parbegin process Producer: . produce an item in nextp; wait(empty);/测试 bufferin=nextp; in=(in+1)%n; signal(full);/通知消费者 ,与前不同,136,process Consumer: wait(full); /测试 nextc=bufferout; out=(out+1)%n; signal(empty); /通知 consume the item in nextc; parend,本题中in和out不是共享变量(因为只有一个生产

38、者和一个消费者)，无需互斥访问。,137,生产者-消费者问题的一般形式,下面介绍生产者-消费者问题一般形式：k个生产者、m个消费者、n个缓冲区的问题。 一般形式的生产者-消费者问题的图示如下：,0 1 2 3 4 5 n-1,P1 P2 P3 PK,C1 C2 C3 Cm,生产者,消费者,n个缓冲区的循环缓冲,图2-5 生产者-消费者问题示意图,138,设置生产者的资源信号量empty，其初值为n，表示开始时有n个空缓冲区； 设置消费者的资源信号量full，其初值为0，表示开始时有0个满缓冲区； 只要有空的缓冲区，生产者便可将消息送入缓冲区； 只要有满的缓冲区，消费者便可从缓冲区取走一个消息。

39、 用互斥信号量mutex对缓冲区(共享变量in和out)的互斥使用，互斥信号量mutex初值为1； 生产者用共享变量in作为下标访问缓冲区，mutex为其互斥信号量；消费者用共享变量out作为下标访问缓冲区，其互斥信号量也用mutex。,139,生产者-消费者问题可描述如下：,semaphore mutex,empty,full ; item buffern ; int in = 0，out = 0 ； mutex.value = 1; empty.value=n,full.value=0;,初始化,140,parbegin /并发执行开始 process produceri (i=1,2,k

40、) /生产者进程 item nextp ； while (true) produce an item nextp； wait(empty) ;/测试是否有可用的资源 wait(mutex);/互斥(进入临界区) bufferin = nextp ； in = (in + 1)% n ； signal(mutex) ;/退出临界区 signal(full) ;/通知(可能唤醒)协作方 ,临界区,141,process consumerj (j=1,2,m） item nextc ； while (true) wait(full); /测试是否有可用的资源 wait(mutex); nextc =

41、 bufferout ； out = (out + 1)% n ； signal(mutex); signal(empty); /通知(可能唤醒)协作方 consume the item in nextc ; parend /并发执行结束,临界区,142,在每个进程中，实现互斥的wait(mutex)和signal(mutex)必须成对出现； 对资源信号量empty和full的wait和signal操作也要成对地出现，但它们处于不同的进程中(交叉成对)。 在每个进程中的多个wait操作顺序不能颠倒，应先执行对资源信号量（也称私有信号量）的wait操作，然后执行对互斥信号量（公有信号量）的wai

42、t操作，否则可能引起进程死锁。(Why?),注意：,143,重申信号量解决同步问题的要点：,为同步双方设置各自的信号量，初值为其初始状态可用的资源数(故该信号量称为资源信号量或私有信号量)； 同步双方任一进程在进入临界区之前，应先对自己的资源信号量执行wait()操作，以测试是否有自己可用的资源。若有资源可用，则进入临界区，否则阻塞； 同步双方任一进程离开临界区后，应对合作方 (对方)的资源信号量执行signal()操作，以通知(若对方处于阻塞状态，则唤醒它)对方已有资源可用(对方已可进入临界区)。,144,复习思考题,若一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘

43、中取苹果，D只从盘中取梨子。试用P、V操作写出同步算法。 有三个进程PA、PB、PC共享两个缓冲器B1和B2。缓冲器B1中可存放n件产品，缓冲器B2中可存放m件产品。进程PA每次生产一件产品并将其存入缓冲器B1中；进程PB每次从缓冲器B1中取出一件产品后再把它送到缓冲器B2中；进程PC每次从缓冲器B2中取出一件产品去消费。为防止把产品存入已满的缓冲器、或从空的缓冲器取产品、或重复取产品，试用PV操作实现它们之间的制约。(学生可先考虑m=n=1的特例，再),145,3三个进程P1、P2、P3互斥使用一个包含N(N0)个单元的缓冲区。P1每次用produce( )生成一个正整数并用put( )送入

44、缓冲区某个单元中；P2每次用getodd( )从缓冲区中取出一个奇数并用countodd( )统计奇数个数；P3每次用geteven( )从缓冲区中取出一个偶数并用counteven( )统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。(2009全国考研题第45题),【说明】解本题时可不考虑缓冲区中存取各个单元的实现细节。,146,var empty,full1,full2,S: semaphore :=1,0,0,N; begin parbegin Process P1() begin var x:integer; repeat x:

45、= produce( ); wait(S); put(x); if x mod 2=1 then signal(full1); else signal(full2); until false; end; Process P2( ) begin,147,var y:integer; repeat wait(full1); y:= getodd( ); signal(empty); countodd( ); until false; end; Prcess P3( ) begin var z:integer; repeat wait(full2); z:= geteven( ); counteve

46、n( ); signal(empty); until false; end; parend,148,2.4.2 哲学家进餐问题,Dijkstra提出并解决的哲学家就餐问题是经典的进程同步问题。哲学家就餐问题描述如下：,有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，在圆桌上有5个碗和5只筷子，他们的生活方式是交替地进行思考和进餐。平时，每个哲学家进行思考，饥饿时便试图拿起其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。图2-7是其示意图。,149,利用记录型信号量解决哲学家进餐问题,桌子上的筷子f0，f1，f4是临界资源，应互斥使用，可用一个信号量表示一只

47、筷子，5只筷子的5个信号量构成信号量数组，所有信号量的初值均为1。,semaphore chopstick5 ； chopstick0.value=chopstick1.value=1; chopstick2.value=chopstick3.value=1 ; chopstick4.value=1 ;,初始化,每个哲学家算法流程为,(1) 拿起左、右筷子； (2) 吃面条； (3) 放下左、右筷子； (4) 思考问题； (5) 返回(1)。,150,第i个哲学家Pi(i=0,1,2,3,4)的活动可描述如下：,process Pi( ) (i = 0,1,2,3,4) /第i个哲学家 whi

48、le (true) wait (chopsticki); /拿起左边筷子 wait (chopstick(i+1)%5 ); /拿起右边筷子 eating ; /吃面条 signal (chopsticki); /放下左边筷子 signal (chopstick(i+1)%5 );/放下右边筷子 thinking ; /思考 ,151,综上所述，哲学家进餐问题的算法可描述如下： semaphore chopstick5 ； chopstick0.value=chopstick1.value=1; chopstick2.value=chopstick3.value=1 ; chopstick4.

49、value=1 ; process Pi( ) (i = 0,1,2,3,4) /第i个哲学家的活动 while (true) wait (chopsticki); /拿起左边筷子 wait (chopstick(i+1)%5 ); /拿起右边筷子 eating ; /吃面条 signal (chopsticki); /放下左边筷子 signal (chopstick(i+1)%5 );/放下右边筷子 thinking ; /思考 ,152,parbegin P0( ); P1( ); P2( ); P3( ); P4( ); parend,上述算法虽然能保证相邻哲学家对筷子的访问互斥，但可能

50、引起死锁。(Why?),153,对上述哲学家就餐问题算法的死锁问题，可采取下面几种解决方法之一：,至多允许4个哲学家同时取左边的筷子，这样能至少保证一个哲学家能就餐，并在用毕后释放他用过的两只筷子，从而使更多的哲学家能够进餐。（请学生考虑算法的描述） 仅当哲学家左右两只筷子均可用时，才允许他拿起筷子进餐。（用AND信号量机制） 规定奇数号哲学家先拿左边筷子，然后再拿右边筷子；而偶数号哲学家先拿右边筷子，然后再拿左边筷子。 规定每个哲学家先拿序号小的筷子按序号分配。 同一时间最多允许1个哲学家进餐(即进餐互斥)。此算法并发程度最差。 本页内容和其后的解法仅供学生阅读和思考，可跳过。,154,解决

51、哲学家就餐问题算法的死锁问题的方法之一： 规定至多允许4个哲学家同时取左边的筷子。,155,解决哲学家就餐问题算法的死锁问题的方法之二： 用AND信号量机制。,156,解决哲学家就餐问题算法的死锁问题的方法之三： 奇数号哲学家先拿左边筷子，然后再拿右边筷子；而偶数号哲学家先拿右边筷子，然后再拿左边筷子。,157,解决哲学家就餐问题算法的死锁问题的方法之四： 规定每个哲学家先拿序号小的筷子(按序号分配)。,158,解决哲学家就餐问题算法的死锁问题的方法之五： 同一时间最多允许1个哲学家进餐(即进餐互斥)。,159,2.4.3 读者-写者问题,一个数据文件或记录，可被多个进程共享，我们把只要求读该

52、文件的进程称为“读者进程”，其他进程称为“写者进程”。,允许多个读者进程同时读一个共享文件，因为读操作不会使数据文件混乱； 不允许两个或两个以上写者进程同时访问共享文件，因为这种访问将会引起混乱； 不允许一个写者进程和其他读者进程同时访问共享文件，因为这种访问将会引起混乱。,所谓“读者-写者问题”是指保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题。,160,利用记录型信号量解决读者-写者问题,【算法分析】,为实现Reader进程和Writer进程间的互斥，设置一个互斥信号量Wmutex，其初值为1； 设置一个整型变量Rcounter，记录正在读的读者进程数。其初值为0； 由

53、于只要有一个Reader进程在读，便不允许Writer进程去写，因此第一个读者进程需要执行wait(Wmutex)操作，即当Rcounter=0时，Reader进程才需要执行wait(Wmutex)操作。若wait(Wmutex)操作成功（表示此时无Writer进程在写），Reader进程便可去读，同时做Rcounter+1的操作。,161,同理，最后一个读进程Reader离开时，亦即计数变量Rcounter-1后变为0时，应执行signal(mutex)操作，以便让Writer进程写。 Rcounter是被多个Reader进程访问的临界资源，为了对它互斥访问，应为它设置一个互斥信号量Rmut

54、ex。 写进程Writer进入临界区前要对互斥信号量Wmutex执行wait操作，离开临界区时要对互斥信号量Wmutex执行signal 操作。,162,根据前面分析，读者-写者问题可描述如下：,semaphore Wmutex，Rmutex; int Rcounter = 0; /读者计数变量 Wmutex.value=1; /写-写互斥、读-写互斥 Rmutex.value=1; /用于Rcounter互斥 parbegin process Readeri (i = 1, 2, ) /读者进程 wait(Rmutex); /准备访问共享变量Rcounter if(Rcounter=0) w

55、ait(Wmutex); Rcounter = Rcounter + 1; signal(Rmutex);,163, Reading; wait(Rmutex); Rcounter = Rcounter 1; if(Rcounter=0) signal(Wmutex); signal(Rmutex); /读者进程结束,164,process Writerj (j=1, 2, ) /写者进程 wait(Wmutex); /写-写互斥、写-读互斥 Writing; signal(Wmutex); parend,写进程的算法描述如下：,165,【分析】 当第一个读者在读文件时，后续读者也可进入临界区

56、读该文件，后续写者不能写(在Wmutex上阻塞)；待所有读者退出时，由最后退出的读者唤醒一个写者。 当有一个写者在写时，后续写者不能写，在Wmutex上阻塞；后续读者不能读，其中第一个读者在Wmutex上阻塞，其余读者在Rmutex上阻塞。该写者退出时，唤醒一个写者或读者。,166,上述算法实际上是“优先读者”算法，当有读者正在读，且后续读者源源不断到来时，写者将长期得不到服务。写者“饿死”。 为此，可以考虑“优先写者”的算法当有写者要写时，待目前正在读的读者读完后，立即让写者去写（即一旦有写者到达，后续的读者都必须等待，而无论是否有读者在读文件）。 下面介绍写进程具有优先权的算法：,167,

57、“写者优先”问题的一种较简单的解法：可以在教科书解法的基础上，增加一个信号量W，用于在写进程到达时封锁后续的读者进程。,168,【讨论】 上述算法执行时，当一个写者进程写完时，可能唤醒后一个写者，也可能唤醒第一个在W上阻塞是读者进程。要使一个写者写完离开临界区时，若有别的写者，则唤醒一个写者；若无写者等待时，才唤醒一个读者，可以采用下面的算法(该算法中，写者也需计数，最后一个离开的写者才唤醒读者)。,169,互斥信号量Rsem1：第一个写者进程执行wait(Rsem1)操作，用于封锁后续读者进程。最后一个写进程执行signal(Rsem1)操作。 互斥信号量Rsem2：第一个写进程到达后的第一

58、个读者在Rsem1上阻塞，其后的读进程在Rsem2上阻塞。 整型变量Rcounter：初值为0，用于读进程计数。 互斥信号量Rmutex：用于读进程互斥访问共享变量Rcounter。 互斥信号量Wsem：第一个读进程执行wait(Wsem)用于封锁写进程。(读-写互斥、写-写互斥) 整型变量Wcounter：初值为0，用于写进程计数。 互斥信号量Wmutex：用于写进程互斥访问共享变量Wcounter。,设置5个互斥信号量和2个共享计数变量:,170,“优先写者”算法描述如下：,171,复习思考题,今有一个文件F供进程共享，现把这些进程分成A、B两组，规定同组的进程可以同时读文件F；但当有A组（或B组）的进程在读文件F时就不允许B组（或A组）的进程读文件F。试用P、V操作（记录型信号量）来进行管理。(从读者-写者问题得到启发) 生产者-消费者问题中，如果将wait(full)和wait(mutex)互相置换，或者将signal(mutex)和signal(empty)互相置换，结果会如何？,172,试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法。 设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1 加工一个车架放入货架A中；工人2、3