《计算机操作系统讲义9.docx》由会员分享，可在线阅读，更多相关《计算机操作系统讲义9.docx（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机操作系统讲义一、课程简介操作系统是计算机系统的核心，它负责控制和管理整个计算机系统的软硬件资源，并使之协调工作。随着计算机的功能不断地发展和创新，计算机系统仍然遵循冯诺依曼提出的体系结构，操作系统的核心功能依然是对处理器、存储器和输入输出设备的管理。对操作系统的基本原理和核心功能的学习和理解，是进一步创新的基础。学习本课程，使学生了解操作系统的基本概念、功能、分类和发展历史，掌握操作系统的使用操作方法，掌握进程和线程的管理技术，掌握处理机的管理和调度策略，掌握存储管理系统、文件系统和设备管理技术，在此基础上结合Linux的进程和存储管理与文件系统进行深入学习与分析，掌握目前主流操作系统L
2、inux的基本原理和功能以及特点。使学生比较清楚地了解现在主流操作系统的一般面貌和内部结构，为进一步学习软、硬件技术及移植、修改、设计和使用系统打下良好的理论基础。通过本课程的学习，可深刻理解计算机软硬件如何协同工作，而且明确开发大型软件必然需要取得操作系统的支持，为以后设计和实现大型应用软件和系统软件打好基础；具备基本的分析问题和解决问题的能力。课程中应使学生掌握计算机操作系统的基本理论知识，基本原理与设计分析方法，掌握基本的实验技能。学生学习本课程后，为后续课程计算机网络、数据库原理、编译原理、计算机接口技术、计算机组成原理、嵌入式系统、软件工程的学习打下一个坚实的基础。二、课程教材教材：
3、张尧学，史美林，张高.计算机操作系统教程（第3版）.北京：清华大学出版社，2006教学内容：第一章绪论第二章操作系统用户界面第三章进程管理第四章处理机调度第五章存储管理第六章进程与存储管理示例第七章文件系统第八章设备管理第九章Linux文件系统三、课程安排1、学时安排总学时：56理论学时：46实验学时：102、参考书目1张尧学编.计算机操作系统教程（第三版）习题解答与实验指导.北京:清华大学出版社，20062汤子瀛主编.计算机操作系统（第三版）.西安:西安电子科技大学出版社，20013J Andrew S.Tanenbaum. Modern Operating Systems, Second
4、Edition.Englewood Cliffs,N.J,Prentice Hall,200114J屠祁等编.操作系统基础（第三版）.北京:清华大学出版社，20005冯耀霖等编.操作系统.西安:西安电子科技大学出版社，20016左万历.计算机操作系统教程（第二版）.北京：高等教育出版社，2004第一章操作系统引论主要内容：本章主要介绍什么是操作系统；操作系统在计算机系统中的地位、作用；操作系统的发展过程；操作系统的基本特征和功能；操作系统的结构设计模式；并对操作系统的今后发展动向和现在流行的操作系统进行介绍。教学安排：理论教学；共2学时银行系统航空订票系统游戏编译器编辑器命令解释器操作系统机器
5、语言微程序物理设备应用程序系统程序r硬件i.1什么是操作系统一、系统软件的构成二、操作系统的作用1、操后系统作为用户与计算机硬件系统之间的接口用户通过两种方式使用计算机：一是命令方式；二是系统调用方式。2、操作系统作为计算机系统资源的管理者系统资源分为：处理机资源（一个或多个）、存储器资源、I/O设备资源以及信息资源。相应操作系统的管理分为：处理机管理（进程管理）、存储器管理、I/O设备管理和文件管理3、操作系统作为扩充机器一虚拟机计算机安装了操作系统后，易于程序设计人员在逻辑上编写程序，方便了用户使用。三、操作系统的定义操作系统可以定义为如下3个方面的程序集合：1、控制和管理计算机系统的硬件
6、和软件资源；2、合理地组织计算机的工作流程；备课札记3、方便用户的使用。1.2操作系统的发展史和分类一、操作系统的发展简史手工操作脱机输入脱机输出单道批处理系统监督程序输入输出缓存多道批处理系统中断多道程序设计技术SPOOLING 技术分时系统实时系统网络并行与分布式系统二、操作系统分类迄今为止，各类操作系统均属于下列操作系统之一或它们的组合：1、单用户（微机）操作系统；2、批处理系统；3、分时系统；4、实时系统；5、网络操作系统；6、分布式操作系统；7、多处理机操作系统；其中前4类操作系统的运行环境以单处理机系统为主，后3类以多计算机系统为主。备课札记1.3操作系统的特征与功能一、操作系统的
7、特征1、并发(Concurrence)指宏观上在一段时间内有多道程序在同时运行，而微观上这些程序是在交替执行。*注意区分并行。并行是指两个或多个事件在同一时刻发生。2、共享(Sharing)程序的并发执行使系统中的全部资源不在为某个程序所独占，而是有多个程序共同使用。3、虚拟(Virtual)多道程序设计技术把一台物理计算机虚拟为多台逻辑上的计算机，使的每个用户都感觉是“独占”计算机。4、异步性(Asynchronism)指一组事件在多次出现时，它们出现的时间和次序没有一定规律。多道程序环境下，指每道持续均以人们不可预知的速度向前推进。其中并发和共享是操作系统的两个基本特征。二、操作系统的功能
8、五大管理功能：1、进程管理一处理机管理主要任务：对处理机的分配和运行实施有效的管理。2、存储器管理主要任务：对内存进行分配、保护和扩充。3、设备管理主要任务：根据设备分配原则对设备进行分配，使设备与主机并行工作，为用户提供良好的设备使用界面。4、文件管理主要任务：有效地管理文件的存储空间，合理地组织和管理文件系统，为文件访问和文件保护提供良好的使用手段。5、作业管理作业：是用户需要计算机完成任务的总和。主要任务：根据用户要求对作业的运行进行合理的组织和控制。1.4操作系统的结构设计模式1、模块化结构模式系统由许多标准的、可兼容的基本单位（模块）构成。各模块备课札记功能独立，可以单独设计，模块之
9、间通过规定的接口相互调用。系统开发周期短，但模块之间调用关系复杂、相互依赖，使分析、移植和维护系统较为困难。2、层次化结构模式把操作系统分成许多基本的模块，并将这些模块按照某种逻辑关系进行分层，各层之间只能单向依赖，即上层软件基于下层之后，不能构成循环。整个系统的正确性由各层次的正确性来保证，易于保证可靠性，也便于维护和移植。3、客户/服务器结构模式操作系统的基本功能构成了内核。用户进程（即客户进程）向服务器进程发出请求，服务器进程完成操作后，把结果返回给客户进程。服务器进程运行在用户态下而不是核心态下。4、对象模式利用面向对象技术设计的操作系统。5、对称多处理模式操作系统工作在所有的处理机上
10、且共享同一内存。1.5主要操作系统的介绍-、Windows 系列1985个人操作系统Windows 1.0商用操作系统1987Windows2.01990Windows3.01993Windows3.XWindows NT3.1（NT 第1版）1993Windows NT3.5（NT 第2版）19941995Windows95WindowsNT3.51（NT 第3版）19951998Windows98WindowsNT4.0（NT 第4版）1996WindowsCE19982000WindowsMEWindows2000（NT5.0）20002001Windows XP备课札记二、UNIX系列
11、三、Linux发展Linux 是由 Linus Torvalds 于1991年开发的。年年年年11 11 11 4*9 9 9 99 9 9 99月,Linux 0.0.1,很不完善。10月，Linux 0.0.2,第一个“正式”版本。两周后0.0.3。12月，Linux 0.1.0,已经有许多人在上面工作了。1.1 月，Linux 1.01. 6小结操作系统是由一系列程序模块组成的，它的基本功能是资源管理和方便用户：它管理处理机、内存、I/O设备和文件，提供用户接口。操作系统发展40年来，主要有两个目的：第一，为程序开发和执行提供一个方便的环境：第二，为保证计算机系统顺利执行，操作系统对各个
12、计算机活动进行调度。操作系统的形成和发展是与计算机硬件发展密切相关的。操作系统这类系统软件有自己的基本特征，这就是：并发、共享和异步性。操作系统提供大量的服务，在最低层是系统调用，它允许正在运行的程序直接得到操作系统的服务；在较高层，命令解释程序为用户提供请求服务的机制，而不必编写程序第二章进程的描述与控制主要内容:本章的重点在于建立进程的概念，深入理解进程动态性以及进程间的相互作用。程序是静态的，进程是动态的。进程有不同的状态，在一定的条件下发生状态变迁，每个进程有惟一的进程控制块（PCB）, PCB是进程存在的惟一标志。教学安排：理论教学；共6学时1.2 前趋图和程序执行一、前趋图的定义1
13、、前趋图前趋图是一个有向无环图。有向是指结点Pi到Pj有边，用Pi, Pj）表示。无环是指在整个图中不存在循环。2、前趋图的表示使用两个集合来表示。一个是结点集合“P”，另一个是前趋关系（有向边）的集合“一例：P=P1, P2, P3, P4, P5, P6, P7,-*=Pl, P2),P1, P3),(P2, P4),(P3, P5),P4, P6),P5, P6),(P6, P7)o二、程序的顺序执行(单道程序设计环境)顺序程序活动有三个主要特点：(1)程序所规定的动作在机器上严格地按顺序执行。备课札记(2)只有程序本身的动作才能改变程序的运行环境。(3)程序的执行结果与程序运行的速度无
14、关。上述特点概括起来就是程序顺序性、封闭性和可再现性。所谓顺序性就是处理机的操作严格按程序所规定的顺序执行，即程序和机器执行程序的操作一一对应。所谓封闭性就是指程序一旦运行起来，其计算结果仅取决于程序本身；除了人为地改变运行状态或机器出现故障外，没有别的因素能影响程序运行的过程。所谓可再现性就是当机器在同一数据集上重复执行同一程序，每次执行都会得到相同的结果。程序顺序执行的特征：顺序性、封闭性、可再现性三、程序的并发执行(多道程序设计环境)1、多道程序设计在硬件引入通道和中断机构后，使得处理机和外部设备之间，外部设备和外部设备之间可以并行操作。这样就引入了多道程序设计技术。多道程序设计是在一台
15、计算机上同时运行两个或更多个程序。从宏观上看，系统中的多个程序都同时得到执行，从微观上看它们是在交替执行，即程序是并发执行的。多道程序设计具有提高系统资源利用率和增加作业吞吐量的优点。例：(一个极端化的例子，但能说明问题)假定有两道作业A和B都在执行，每个作业都是执行一秒钟，然后等待一秒钟，进行数据输入，随后再执行，再等待一直重复60次。如果按单道方式，先执行作业A, A作完了再执行B,那么两个作业都运行完，共需要4分钟，CPU的利用率为百分之五十。如果我们采用多道程序技术来执行同样的作业A和B就能大大改进系统性能，作业A先运行，它运行一秒后等待输入。此时让B运行，B运行一秒后等待输入，此时恰
16、好A输入完，可以运行了，就这样在CPU上交替地运行A和B,在这种理想的情况下，CPU不空转，其使用率升到百分之百，并且吞吐量也随之增加 To2、并发程序的表示为了在高级语言以及描述程序中的并发成分，Dijkstra引出了一组并发语句 Parbegin/Parendo具体形式：ParbeginS1；S2；Sn； parend 其中SI, S2,，Sn表示可以并发执行的语句。3、程序并发执行时的特征1)间断性(制约性)并发程序在执行期间可以相互制约2)失去封闭性由于资源共享，所以资源状态的改变不再取决于某一个程序，而是由并发执行的多个程序所共同决定。3)不可再现性失去封闭性后，对于同一个程序来说，
17、即使初始条件相同，但在程序重复执行时，因资源状态受到其他并发程序的影响，每次并不相同，所以其运行的结果可能不同。四、程序并发执行的条件程序的并发执行能有效的提高资源利用率和系统的吞吐量，但并发执行也带来了“不可再现性”缺点。为了去掉这一缺点，由Bernstein 于1966年提出了程序并发执行的条件。1、读集和写集R (Pi)=al, a2,，am,表示程序Pi在执行期间所需参考的所有变量的集合，称“读集W (Pi)=bl, b2,，bn,表示程序Pi在执行期间要参改变的所有变量的集合，称“写集二2、程序并发执行的条件程序Pi和Pj若满足下述条件，他们能并发执行，且具有“可再现性”。Berns
18、tein 条件：R(Pi) nw(Pj) uR(Pj) nw(Pi) uw(Pi) nw(Pj)=o1.3 进程的描述一、进程的定义与特征1、进程概念的引入由于多道程序并发执行时共享系统资源，共同决定这些资源的状态，因此系统中各程序在执行过程中就出现了相互制约的关系，程序的执行出现“走走停停”的新状态。这些都是在程序的动态过程中发生的。而程序本身是机器能够翻译或执行的一组动作或指令，是静止的。因此，用程序这个静态概念已不能如实反映程序并发执行过程中的这些特征。为此，人们引入“进程”(Process)这一概念来描述程序动态执行过程的性质。即进程就是操作系统为进行处理机管理而引入的概念。2、进程的
19、定义备课札记进程定义为：在并发环境下，程序在一个数据集合上的的执行过程。即：进程是进程实体的运行过程。3、进程的特征序号特征说明1动态性是动态概念，有一事实上的生命期，是动态地产生和消亡的。2并发性多个进程的实体能存在于同一内存中，在一段时间内都能运行。3独立性作为资源申请和独立调度的基本单位。4异步性各进程向前推进的速度是不可预知的。5结构性程序段、数据段、控制结构和堆栈段等组成。*小结：进程与程序的主要区别序号进程程序1动态的静态的2是独立性的，能并发执行不能并发执行3程序和进程无一一对应关系。一个程序可由多个进程共用；另一方面，一个进程在其活动中又可顺序地执行4异步运行，会相互制约程序不
20、具备此特征二、进程的基本状态进程的动态性是由它的状态和转换体现出来的。1、进程的基本状态三种基本状态是：执行态、就绪态和阻塞态(或等待态)(1)执行态(Running)运行状态是指当前进程已分配到CPU,它的程序正在处理机上执行时的状态。(2)就绪态(Ready)就绪状态是指进程已具备运行条件，但因为其它进程正占用CPU,所以暂时不能运行而等待分配CPU的状态。备课札记(3)阻塞态(Blocked)阻塞态是指进程因等待某种事件发生而暂时不能运行的状态。进程的状态及其转换：如下图2、进程状态的转换(1)就绪一一执行处于就绪状态的进程被调度程序选中，分配到CPU后，该进程的状态就由就绪态变为运行态
21、。(2)执行阻塞正在运行的进程因某个条件未满足而放弃对CPU的占用，这个进程的状态就由运行态变为阻塞态。(3)阻塞就绪处于阻塞状态的进程所等待事件发生了，系统就把该进程的状态由阻塞态变为就绪态。(4)执行就绪正在运行的进程如用完了本次分配给它的CPU时间片，它就得从CPU 上退下来，暂停运行。该进程状态就由运行态变为就绪态.等待事件发生 (如等待I/O)所等待事件发生7(如I/O完成)阻塞状态*小结：进程基本状态执行态：此时正用CPU；就绪态：可运行，但未分到CPU；阻塞态：不能运行，等待某个外部事件发生。在一定条件下，进程状态才发生转换三、进程的组成1、进程的组成进程实体通常由程序、数据集合
22、和PCB这三部分组成。进程的这三部分构成进程在系统中的存在和活动的实体，有时也统称为“进程映象”。PCB程序段数据段备课札记2、进程控制块的组成（Process Control Block,简称PCB ）进程控制块有时也称进程描述块（Process Descriptor）它是进程组成中最关键的部分。其中含有进程描述信息和控制信息，是进程动态性的集中反映，它是系统对进程进行识别和控制的依据。用来描述进程当前的状态、本身的特性的数据结构被称为进程控制块。一般来说，进程控制块包括如下内容：1）进程标识符信息外部标识符：进程名；内部标识符：进程的序号（PID）；其他：族系关系，UID, GID, PP
23、ID2）处理机状态信息当进程进行切换时，需要保护的信息包括：通用寄存器、指令计数器、程序状态字（PSW）和用户栈指针。3）进程调度信息进程状态、进程优先权、调度所需的其它信息和事件（原因）。4）进程控制信息程序和数据的存储情况；同步和通信机制；资源清单和链接指针。3、进程控制块的作用：进程控制块是进程组成中最关键的部分。每个进程有惟一的进程控制块。操作系统根据PCB对进程实施控制和管理。进程的动态、并发等特征是利用PCB表现出来的。PCB是进程存在的惟一标志。4、PCB的组织方式有链接方式和索引方式两种。1）链接方式把具有相同状态的PCB,用其中的链接指针，链接成一个队列。如教材P45图2-7
24、所示。2）索引方式系统根据所有进程的状态，建立几张索引表。索引表目中，记录相应状态的PCB在PCB表中用地址。每张索引表的地址放在相应的专用单元中。如教材P46图2-8所示。备课札记2.3 进程控制为了防止用户程序对系统程序的破坏，系统提供了不同的处理机执行状态，通常分为系统态（也称做管理态）和用户态两种。 、系统态：当操作系统程序执行时，处理机处于系统态。即内核运行在系统态下。 、用户态：用户程序在用户态下执行。3一、操作系统内核（Kernel） 、操作系统内核内核是计算机硬件的第一层扩充软件。它们常住内存，对进程进行控制、对存储器进行管理以及对设备进行管理。内核一般由中断处理程序、各种常用
25、设备的驱动程序以及一些运行频率较高的模块（如时钟管理、进程调度等）组成。2、内核的功能 ）支撑功能 中断管理是内核的最基本功能。是整个操作系统赖以活动的基础。 时钟管理是内核的基本功能。操作系统中的许多活动也都需要它。 原语操作所谓原语（Primitive）是机器指令的延伸，往往是为了完成某些特定的功能而编制的一段系统程序。为保证操作的正确性，在许多机器中规定，执行原语操作时，要屏蔽中断，以保证操作的不可分割性，即一个操作中的所有动作要么全做，要么全不做。操作系统中完成某些基本操作时，往往利用原语操作来实现。2）资源管理功能 进程管理由于进程管理的运行频率高，所以这些模块的全部或部分功能都放在
26、内核中。 存储器管理目的是保证存储器管理的运行速度。 设备管理设备管理和设备密切相关，因此其中一大部分也放在内核中。二、进程的控制1、进程图进程图是用来描述进程家族关系的有向树。由父进程创建子进程，子进程再创建子进程，从而构成一棵树型的进程图。如教材P48图2-9o 2、进程控制原语内核中有很多原语，如创建进程、终止进程、阻塞进程等。1）进程创建 引起进程创建的事件用户登录、作业调度、提供服务和应用请求。 进程创建原语的主要操作过程(1)(2)(3)(4)申请一个空闲的PCB；为新进程分配资源；将进程的PCB初始化；将新进程加到就绪队列中。2）进程终止 引起进程终止的事件正常终止、异常结束和外
27、界干预。 终止进程的主要操作过程（1）从系统的PCB表中找到指定进程PCB；（2）回收该进程所占用的全部资源；（3）若该进程还有子孙进程，则还要终止其所有子孙进程，回收它们所占用的全部资源；（4）释放被终止进程的PCB,并从原来队列中摘走。3）进程阻塞正在运行的进程通过调用阻塞原语主动地把自己阻塞。 引起进程阻塞的事件请求系统服务、启动某种操作、新数据尚未到达和无新工作可做。 阻塞的过程（1）立即停止当前进程的执行；（2）将现行进程的CPU现场送到该进程的PCB现场保护区中保存起来，以便将来重新运行时恢复此时的现场。（3）把该进程PCB中的现行状态由“运行”改为阻塞，把它插入到具有相同事件的阻
28、塞队列中。（4）然后转到进程调度程序，重新从就绪队列中挑选一个合适进程投入运行。4）进程唤醒唤醒原语执行过程：（1）首先把被阻塞进程从相应的阻塞队列中摘下；（2）将现行状态改为就绪态，然后把该进程插入到就绪队列中；（3）如果被唤醒进程比运行进程有更高的优先级，则设置重新调度标，4、。阻塞原语与唤醒原语恰好是一对相反的原语：调用前者（阻塞原语）是自己去睡眠，调用后者（唤醒原语）是把“别人”唤醒。使用时也要成对，前边有睡的，后边有叫醒的。否则，前者就要“长眠”了。如同两个士兵轮流站岗值班和睡觉休息。相关者唤醒，自己不能唤醒自己。2.4 线程的基本概念一、线程的引入1,处理机分配单位的演变进程的两个
29、基本属性：一是拥有资源的独立单位；二是独立调度和分配的基本单位。由于进程是一个资源的拥有者，所以进程在创建、终止和切换中，系统必须为之付出较大的时空开销。于是想把这两个属性分开，即对拥有资源的基本单位，不进行频繁的切换；而对于调度和分配的基本2、线程的定义x A/z线程是进程中的一个实体，是被系统独立调度和分配的基本单位。又称为轻型进程。二、线程与进程的比较程与进程备课札记的比较三、线程的分类线程分为用户级线程（ULT）和内核支持线程（KLT）。1、用户级线程（ULT）线程仅存在用户级中，对于线程的创建、撤消和切换，都不利用系统调用来实现，因而这种线程与内核无关。内核空间用户空间线程库单线程进
30、程模式多W戋程进1星模式用户栈线程控制块线程控制块进程控制块进程控制块用户栈用户栈内核栈用户地址空间用户地址空间内核栈内核栈线程线程1、单线程和多线程的进程模型性能进程线程调度进程内的线程切换，不会引起进程切换。当不同进程内的线程进行切换时，进程进行切换。调度的基本单位并发性可以可以拥有资源拥有资源的独立单位仅拥有能运行的基本资源系统开销大小备课札记3.1进程同步的基本概念一、进程的同步与互斥进程间的相互关系分为同步关系和互斥关系。1、同步（直接制约关系）同步是指为完成同一任务的伙伴进程间，因为需要在某些位置上协调 它们的工作而相互等待、相互交换信息所产生的制约的关系。2、内核支持线程（KLT
31、）又称轻便进程。线程的实现依赖内核。用户空间内核空间Z主要内容：本章将在系统动态模型基础上讨论进程（线程）间的 同步和互斥、进程通信以及操作系统提供的相应工具。 教学安排：理论教学；共6学时2. 5小结进程可以理解为：“程序在并发环境中的执行过程它最基本的特征 是并发性和动态性，一个进程至少应有三种状态，它们在一定条件下相互 转化。每一个进程都有惟一的进程控制块（PCB）,它是进程存在的惟一标志。PCB表的物理组织方式有若干种，最常见的是线性方式、链接方式和 索引方式。第三章进程的同步与通信两者要步调协调一致，是同步关系，同时又相互牵制。2、互斥（间接制约关系）两个进程在逻辑上本来完全独立，毫
32、无关系，只是由于竞争同一个物理资源而相互备课札记制纵二、临界资源和临界区1、临界区的定义一次仅允许一个进程使用的这类资源称为临界资源，在每个进程中访问临界资源的那段程序区叫临界区。访问临界资源的程序结构描述：repeatEntry sectionCritical section；Exit sectionRemainder section；Until false；2、互斥准则 空闲让进只要临界资源空闲，允许请求者使用。 忙则等待当临界资源正被进程访问，其他请求则等待，保证临界资源的互斥访问。 有限等待让等待进入临界资源的进程，在等待一段有限的时间后进入临界区，以免出现“死等”。 让权等待当请求进
33、程不能进入临界区时，应立即释放处理机，以免进程陷入“忙等二三、利用软件方法解决进程互斥问题使用软件设计方法，在Entry code和exit code位置上设计相应代码，实现对临界区的互斥执行。在进行下面的讲解前，首先假设进程Pi（i=0,1）和Pj（j=l-i）。算法1一严格轮换法设置整形变量turn （令牌），用turn=i还是j来区分进入临界区的进程。Pi进程算法的描述备课札记repeatWhile turn# i do skip；Critical section；Tum=j；non critical section；until false；缺点：如果初值turn=i；则算法严格按Pif
34、 Pj轮换使用临界资源，即使某时刻临界区空闲（准则1空闲让进）。算法2为了避免出现忙等的情况，使用数组flag来记录各进程使用临界区的情况。Var flag： arrayO.l of Boolean；Flagi=true表示进程Pi正在执行其临界区。Pi进程算法的描述repeat即扛kWhile ilagljJ do skip；Flag（i=true；Critical section；Flagi=false；non critical section；until false；缺点：虽然解决了算法1中的忙等，但却不能保证临界资源的互斥使用（准则2忙则等待）。算法3为了解决while语句和ilagi
35、设置语句之间为另一进程执行留有可乘之机的情况，交换这两个语句执行的顺序。Pi进程算法的描述repeatFlagi=true；While flagj do skip；Critical section；Flagi=false；non critical section；备课札记until false；缺点：虽然解决了算法2中的不能互斥使用的情况，但却导致了都不能进入的情况(准则1空闲让进)。算法4为了解决上述问题，同时引入两个变量，一个flagi表示Pi进程要求进入或正在执行临界区，另一个turn表示要求进入的进程编号。Pi进程算法的描述repeatFlag(i=true； tum=j；While
36、flagjand turn=j do skip；Flagi=false；Critical section；non critical section；until false；缺点：能保证互斥使用，但却导致了浪费处理机资源的情况(准则4让权等待)。四、利用硬件方法解决进程互斥问题使用硬件指令保证其操作的原子性，但不能满足“让权等待”。1、Test一andSet指令实现互斥1) Test一andSet 指令功能function TS (var lock： boolean )： boolean beginTS=lock；Lock=true；EndLOCK： TRUE表示在使用；FALSE表示空闲。TS
37、是一条指令，执行过程，不会被打断。2)利用TS实现进程互斥repeatWhile TS (lock) do skip；Critical section；lock=false；non critical section；备课札记until false；2、利用SWAP指令实现进程互斥1) SWAP指令功能procedure SWAP (var a, b： boolean)var temp： boolean；begintemp=a；a=b；b=temp；End交换变量a和b的值。2)利用SWAP实现进程互斥Key=true ；While key do swap (key, lock)； repeat
38、Critical section；lock=false；non critical section；until folse；3.2 信号量机制信号量是操作系统解决进程互斥与同步的工程。一、整型信号量机制1、整型信号量定义：把信号量定义为一个整型量，除初始化外，仅能通过两个原子操作WAIT和SIGNAL来访问。WAIT和SIGNAL的描述：WAIT (S)： WHILE (S =0) DO SKIP；S=S-1；SIGNAL (S)： S=S+1；小结： S是正数，表示资源的个数。 WAIT和SIGNAL是原子操作。、 原子操作的实现一般采用屏蔽中断(适用于单处理机)或利用备课札记TS和SWAP硬
39、指令(适用于多处理机)实现。 仍然不能实现让权等待。2、利用整型信号量实现互斥问题repeatWAIT (S)；Critical section；SIGNAL (S)；non critical section；until false；3、利用整型信号量描述前趋关系Var a, b, c： semaphore=0,0,0；ParbeginBegin SI； SIGNAL (a)； end；Begin S2； SIGNAL (b)； end；Begin WAIT (a)； WAIT (b)； S3； SIGNAL (c)； end；Begin WAIT (c)； S4； end；parend二、记
40、录型信号量机制1、定义type semaphore=recordvalue： integer；L： List of process；End；其中L表示等待信号量进程的链表。S取值为负、零和正。负和零表示阻塞进程个数，正表示现有资源的个数。2、原子操作WAIT (S)： S.value=S.value-1;备课札记IfS.VALUE0 THEN BLOCK(S.L);SIGNAL(S):S.VALUE=S.VALUE+1;If S.VALUE=0 THEN WAKEUP(S.L);三、信号量集机制当进程互斥使用多个临界资源时，可能出现死锁问题(在第四章中介绍)。为了解决上述问题，引入了信号量集的
41、技术。1、AND型信号量集机制就是将进程在整个运行过程中所需要的所有临界资源，一次性的全部分配给它，待进程使用完后一次性的释放，只要尚有一个资源不能分配给它，则全部不能进行分配。2、两个原子操作SWAIT (SI, Tl, D1, Sn, Tn, Dn)；其中Si表示某类资源数，Ti表示分配下限，Di表一次分配的个数。SSIGNAL (SI, D1, Sn, Dn)；其中Si表示某类资源数，Di表示回收的个数。3.3 经典进程同步问题一、生产者消费者问题1、问题的提出2、问题的解决var mutex, fulL empty ： semaphore=L 0, n； buff： array0.n-
42、l of item； in, out： integer=0,0；beginparbeginproducer ()；consumer 0；parend endprocedure producer ()procedure consumer ()beginbeginrepeatrepeatproduce an item in nextp；wait (full)；wait (empty)；wait (mutex)；wait (mutex)；nextc=buffout；buffi in=nextp；out=(out+l) mod n；in=(in+1) mod n；signal (mutex)；sign
43、al (mutex)；signal (empty)；signal (full)；consume the item in nextc；until false；until false；endend3、小结MUTEX用于控制互斥访缓存池，问初值为1,表示消费者进程和生产者进程在对缓存池使用时，按照互斥方式。FULL用于同步控制，初值为0,表示当前缓存池中“满”缓存区数。EMPTY用于同步控制，初值为N,表示当前缓存池中“空”缓存区数。不论是互斥还是同步，WAIT和SIGNAL操作都配对出现。WAIT操作不能颠倒，SIGNAL操作可以。二、读者写者问题1、问题描述有两种情况：一是READER有较高的优
44、先权；二是WRITER有较高的优先权。下面描述的是READER有较高优先权的情况。1）如果当前无人访问数据，无论READER或WRITER都可直接进入访问。2）如果已有一个READER正在访问数据，那么其它欲访问数据的READER可直接进行访问，而当前欲访问数据的WRITER则必须无条件等待。3）若某个WRITER正在访问数据，则当前欲访问数据的READER和WRITER 均须等待。4）当最后一个结束访问数据的READER发现有WRITER正在等待时，则将其中的一个唤醒。备课札记5）当某个WRITER结束访问数据时发现存在等待者，则按FIFO或其他原则唤醒READER和WRITER o2、句题解决var mutex, wmt： semaphore=1,1；rcount： integer=0；beginparbeginreader