《操作系统习题集(南京晓庄学院操作系统习题答案).pdf》由会员分享，可在线阅读，更多相关《操作系统习题集(南京晓庄学院操作系统习题答案).pdf（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统基础习题解析及实验指导第一篇操作系统基础知识点及习题解答该部分罗列操作系统基础各章节的学习要点，指出学习的重点和难点，在回顾相关知识点的基础上，对典型习题进行分析和解答。第一章操作系统引论本章学习要点 1 掌握操作系统的概念与作用 2 掌握操作系统的基本类型与特点 3 掌握操作系统的特征与功能 4深入领会多道程序设计技术本章学习难点 1 多道程序设计技术【2】操作系统的特征知识点回顾.操作系统的概念一个完整的计算机系统由计算机硬件系统和计算机软件系统两部分组成。操作系统是配置在计算机硬件上的第一层软件，是对硬件系统功能的第一次扩充。1 .操作系统(O pe ra ting S y st
2、e m,简称O S)的作用(1)O S作为用户与计算机硬件系统之间的接口O S处于用户与计算机硬件系统之间，用户通过O S来使用计算机系统。或者说，用户在O S的帮助下能够方便、快捷、安全、可靠地操纵计算机硬件和运行自己的程序。(2)O S作为计算机系统资源的管理者这是广为流行的一个关于O S作用的观点。在一个计算机系统中，通常都包含了各种各样的硬件和软件资源。归纳起来可将资源分为四类：处理器、存储器、I/O设备以及信息(数据和程序)。O S的主要功能正是针对这四类资源进行有效的管理。(3)O S用作扩充机器对于一台完全没有软件配置的计算机系统(裸机)，即使功能再强，也必定难于使用。0$在裸机
3、上分别覆盖I/O 设备管理软件、文件管理软件等，此时用户所看到的机器，将是一台比裸机功能更强、使用更方便的机器。通常把覆盖了软件的机器称为扩充机器或虚机器。在计算机系统上覆盖上一层软件后，系统功能便增强一级。由于O S 自身包含了若干层软件,因此当在裸机上覆盖上O S 后，便可获得一台功能显著增强，使用极为方便的多层扩充机器或多层虚机器。2.操作系统的概念操作系统是一组控制和管理计算机硬件和软件资源、合理组织计算机的工作流程，方便用户使用的程序的集合。操作系统是裸机上的第一层软件，是对硬件功能的首次扩充。二.操作系统的发展过程人工操作方式f脱机输入输出技术一批处理技术一分时、实时系统一通用操作
4、系统一微机操作系统一网络操作系统一分布式操作系统1 .脱机输入输出技术为解决人工操作阶段存在的人机矛盾以及C P U 与 I/O 速度不匹配的矛盾，引入脱机输入输出技术。系统中除主机外配置一台外围机（又称卫星机），它只与输入输出设备打交道，不与主机相连，即脱机。用户程序与数据可以在外围机控制下（脱离主机控制）预先从低速设备输入到磁带上，C P U 需要时再从磁带上输入到主机，即脱机输入技术，以解决C P U 与 I/O 速度不匹配的矛盾。类似地，脱机输出技术通过外围机完成数据从主机到磁带，再到低速输出设备上的输出操作。由于主机C P U 只与高速的输入输出设备打交道，从而有效地减少了 C P
5、U 等待低速设备输入输出的时间。图 1-2 脱机输入/输出方式2 .批处理技术批处理技术是指计算机对一批作业自动进行处理的一种技术。早期的计算机系统为了充分利用系统资源，通常把一批作业以脱机输入方式输入到磁带上,并在系统中配置监督程序，依次将作业装入存，控制磁带上的作业自动地、一个接一个地进行处理，这样就形成了早期的单道批处理系统。3 .多道程序设计技术为进一步改进单道批处理系统中C P U 和存利用率较低的问题，引进多道程序设计技术。多道程序设计技术同时将多个作业放入存并允许作业交替执行，共享系统中的资源。宏观上并行,微观上串行。多道程序设计技术能有效提高系统的吞吐量和改善资源利用率，但是为
6、了协调存中运行的多道程序，应妥善解决处理机分配、存分配、设备分配、文件安全、作业组织的问题。为解决上述问题而设置的一组软件就形成了操作系统。程序A 程序B 程序A 程 序BCPU输入设备-i-!输出设备 1 u运行处理 输入数据 运行处理 输出数据程序 A I _I _ I _运行处理 输出数据 等待C P U运行处理程序 B _I _ L_ L图1-3多道程序运行情况三.操作系统的分类1.单用户操作系统2.批处理操作系统(1)单道批处理系统把一批作业以脱机方式输入到磁带上，在系统中配上监督程序，在它的控制下使这批作业能自动地一个接一个地顺序处理。对作业的处理是成批进行的、且存中始终只保持一道
7、作业。(2)多道批处理系统5引入多道批处理的目的a)提高CPU的利用率b)提高存和I/O设备的利用率c)增加系统吞吐量U 多道批处理的特征一一多道性、无序性、调度性8多道批处理的优缺点资源利用率高，系统吞吐量大，但平均周转时间长，无交互能力。3.分 时操作系统在分时操作系统中，一台计算机和多台终端相连，每个用户通过自己的终端向系统发出命令请求，系统分析并完成各用户的请求。(1)单道分时系统存中只驻留一道作业，当其运行一个时间片后，调至外存，再从外存上选一个作业进入存。作业频繁调进调出，开销大，系统性能较差。(2)具有 前台”和“后台”的分时系统存被固定地划分为“前台区”和“后 台 区 前 台
8、区 存 放 按 时 间 片“调进”和“调出”的作业流，后台区存放批处理作业。仅当前台无作业运行时，方才运行后台的作业。(3)多道分时系统存中的多道作业轮流获得一个时间片来运行。分时系统的特征具有多路性、独立性、及时性和交互性等特征。4.实时操作系统能使计算机系统接收到外部信号后及时进行处理，并且在严格的规定时间处理结束，再给出反馈信号的操作系统。实时操作系统分为实时控制系统和实时信息处理系统。例如生产过程控制系统、航空订票系统等。实时系统具有多路性、独立性、及时性、交互性和可靠性等特征。实时控制系统是以计算机为中心的生产过程控制系统，又称为计算机控制系统，要求快速的响应时间，可靠性要求高。实时
9、信息处理系统在响应时间上和分时系统处于同一级别，但更强调可靠性和安全性，交互性差。批处理操作系统、分时操作系统、实时操作系统是三种基本的操作系统类型。如果一个操作系统兼有三者或其中二者的功能，则该操作系统称为通用操作系统。5.其它操作系统包括网络操作系统、分布式操作系统等。四.操作系统特征一一并发、共享、虚拟、异步性1.并发并发是指两个或多个事件在同一时间间隔发生。宏观上是同时的，微观上是交替的。程序的并发执行能有效改善系统资源的利用率，但会使系统复杂化。要注意区别并发和并行两个概念。2.共享系统中的资源可供存中多个并发执行的进程共同使用。根据资源的不同属性，可分为两种资源共享方式：互斥共享和
10、同时访问。并发和共享是操作系统的两个最基本的特征，两者之间互为存在的条件。一方面，资源的共享是以程序的并发执行为前提的；另一方面，系统若不能对资源共享实施有效管理，则程序的并发执行则无法实现。3.虚拟通过某种技术把一个物理实体变成若干个逻辑上的对应物，物理实体是实的，即实际存在，而后者是虚的，是用户的感觉。例如虚拟存、虚拟设备等。4.异步性在多道程序环境下，多个进程并发执行，但由于资源等因素的限制，存中的每个进程何时执行，何时暂停，以怎样的速度向前推进，每道程序需多少时间才能完成，都是不可预知的，进程以异步的方式运行。但只要运行环境相同，作业经过多次运行，都会获得完全相同的结果。五.操作系统的
11、功能操作系统引入多道程序设计技术，一方面改善了系统资源的利用率，但另一方面也引发了复杂的系统管理问题，诸如存中的作业如何存储，系统资源如何共享等，操作系统必须具有控制和管理各种并发活动的能力，合理组织计算机的工作流程，有效地提高各类资源的利用率。1.处理机管理主要任务是对处理机进行分配，并对其进行有效的控制和管理。在多道程序环境下，处理机的分配和运行是以进程为基本单位，又称进程管理。(1)进程控制一一为作业创建进程，撤消已结束的进程，以及控制进程的状态转换。(2)进程同步一一对诸进程的运行进行协调(互斥和同步)。(3)进程通信一一实现相互合作进程之间的信息交换。(4)进程调度一一从就绪队列中，
12、按照一定的算法选出一新进程，分配处理机，设置运行现场，使之投入运行。2.存储器管理存储器管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率，以及从逻辑上来扩充存。(1)存分配为每道程序分配存空间，提高存的利用率。(2)存保护一一确保每道用户作业都在自己的存空间中运行，互不干扰。(3)地址映射一一将地址空间中的逻辑地址转换为存空间中与之对应的物理地址。(4)存扩充一一借助虚拟技术，从逻辑上扩充存容量。3 .设备管理主要任务是完成用户提出的I/O请求，为用户分配I/O设备；提高CPU和I/O设备的利用率；提高I/O速度；以及方便用户使用I/O设备。(1)缓冲管理
13、一一管理各种类型的缓冲区。(2)设备分配一一根据用户的I/O请求，分配所需设备。(3)设备处理一一实现CPU和设备控制器之间的通信。(4)设备独立性和虚拟设备4.文件管理程序和数据都是以文件的形式存储在存储介质上。文件管理的主要任务是对用户文件和系统文件进行管理，方便用户使用，保证文件的安全性。(1)文件存储空间的管理(2)目录管理一一建立目录项，实现按名存取、实现文件共享。(3)文件的读、写管理和存取控制(4)文件保护5.作 业管理(1)操作系统接口(2)作业的控制方式六.操作系统的结构一一模块接口法、有序分层法1 .模块接口法按功能划分模块，模块间可以不加控制的相互调用和转移。这种结构紧凑
14、、接口简单直接,系统效率高；但模块间的调用随便，独立性差，系统结构不清晰。2 .有序分层法A o,A i.A,(A i+i.A nA。宿主系统(底)，A n是目标系统(顶)。既可采用自底向上法，逐步扩充，也可采用自顶向下法，逐层分解。(1)单向依赖(2)同一层中各模块的功能应相近(3)与硬件紧密相关的模块安排在A。层，便于移植(4)运行频率较高的公用模块应放置在较低的层次(5)由于设计目标不同而变化的部分放在外层，增强系统的适应性习题分析一.判断改错题(判断由下划线标明的关键词的叙述是否正确，正 确 的 打 错 误 的 打X并改正。)(1)实时系统只能应用于生产控制系统,不能应用于信息处理系统
15、。()(2)并发含有 同时进行”的里念，是指两个或者是多个事件在同一时刻发生。()(3)操作系统虚拟机在逻辑功能上与裸机一样,具有一个物理实体。()(4)对用户而言，操作系统是一种人机交互的环境,对设计者而言，它是一种强功能的系统资源管理程序。()(5)资源的共享是以程序的并行执行为受仕的，没有程序的并行执行，就没有资源的共享。()(6)计算机系统的复遮包括程序和数据两大部分。()(7)若把计算机系统分为若干层次,则按由上而下顺序可分为应用系统与应用软件、操作系统、其它系统软件和裸机。()(8)批处理控制程序解决了作业间的自动转换,减少了时间浪费，尤其是主机CP U时间的浪费，如果一个用户的计
16、算作业非常庞大，也不会独自一直占据CP U。()习题解答：(1)错；应为：实时系统能应用于生产控制系统，也能应用于信息处理系统。(2)错；应为：是指两个或者是多个事件在一段时间间隔同时发生。(3)错；应为：操作系统虚拟机在逻辑功能上与裸机不同，但只具有一个物理实体。(4)对；(5)错；应为：资源的共享是以程序的并发执行为条件的，没有程序的并发执行，就没有资源的共享。(6)错；应为：计算机系统的资源包括硬件资源和软件资源两大部分。(7)错：应为：若把计算机系统分为若干层次，则按由上而下顺序可分为应用系统与应用软件、其它系统软件、操作系统和裸机。(8)错；应为：，尤其是主机CP U时间的浪费，如果
17、一个用户的计算作业非常庞大，就会独自一直占据CP U。(9)对；二.填空题(1)实时含有立即、及时之意，因而 是实时系统最关键的因素。(2)操作系统的层次结构中，与 或运行频率较高的模块都安排在紧靠硬件的软件层中，这 一 部 分 通 常 称 为,它在执行基本操作时，往往是利用 操作来实现，该操作具有原子性。(3)UN I X是一个真正的 用户、任务的 操作系统。(4)如 果 一 个 操 作 系 统 兼 有、和 三者或其中两者的功能，这样的操作系统称为通用操作系统。(5)实现多道程序设计必须妥善解决三个问题：、和系统资源的管理和调度。(6)批 处 理 系 统 的 主 要 优 点 是 ,资源利用率
18、高，系统开销小，它的缺点在于作业处理的,用户交互能力较弱。(7)操作系统是对计算机进行 的程序，是计算机和 的接口。(8)提供网络通讯和网络资源共享功能的操作系统称为 操作系统。(9)对系统总体设计目标来说，批处理系统注重提高计算机的效率，尽 量 增 加 系 统 的,分时系统应保证用户的,而实时系统在及时响应和处理的前提下，再考虑。(1 0)在主机控制下进行的输入/输出操作称为 操作。(1 1)在计算机系统中，是整个系统硬件的核心和基础，而在计算机软件系统中，具有同样的核心和基础作用。习题解答：(1)响应时间；(2)硬件紧密相关，核，原语；(3)多，多，网络；(4)批处理操作系统、分时操作系统
19、、实时操作系统；(5)文件，作业；(6)系统吞吐量大，平均周转时间较长；(7)控制和管理，用户；(8)网络；(9)吞吐量，交互性，与用户的交互性；(1 0)联机I/O操作；(1 1)C P U,操作系统；三.简答题1 .简述操作系统在计算机系统中的位置。答：操作系统O S是运行在计算机硬件系统上的最基本的系统软件。它在计算机系统中位于计算机裸机和计算机用户之间，为系统软件和用户应用软件提供了强大的支持。2 .简述描述操作系统的两种主要观点。答：描述操作系统有两种主要观点，一种是虚拟机的观点一一装有操作系统的计算机极扩展了原计算机的功能，给用户提供了一个友好的、易于操作的界面，对用户来说，好像是
20、一个扩展了的机器,即一台虚拟机器。另一种是资源管理的观点，操作系统完成对处理机、存储器、I/O设备等硬件资源和文件等软件资源的管理。3 .什么是操作系统？它有什么基本特征？答：操作系统是一组控制和管理计算机硬件和软件资源、合理组织计算机的工作流程，以及方便用户的程序的集合。操作系统的基本特征是：并发一一是指两个或多个事件在同一时间间隔发生。宏观上是同时的，微观上是交替的。共享一一系统中的资源可供存中多个并发执行的进程共同使用。根据资源的不同属性，可分为两种资源共享方式：互斥共享和同时访问。虚拟一一通过某种技术把一个物理实体变成若干个逻辑上的对应物，物理实体是实的，即实际存在，而后者是虚的，是用
21、户的感觉。异步性一一在多道程序环境下，多个进程并发执行，但由于资源等因素的限制，存中的每个进程何时执行，何时暂停，以怎样的速度向前推进，每道程序需多少时间才能完成，都是不可预知的，进程以异步的方式运行。但只要运行环境相同，作业经过多次运行，都会获得完全相同的结果。4 .多道程序设计时应注意什么问题？答：处理机管理问题一一多道程序之间如何分配C P U,使 C P U既能满足各程序运行的需要，又能提高处理机的利用率。存管理问题一一为每道程序分配必要的存空间，并防止程序遭破坏。I/O设备管理一一分配为多道程序共享的I/O设备，方便用户使用，提高设备利用率。文件管理问题一一组织大量的程序和数据，便于
22、用户使用，保证数据的安全和一致。作业管理问题一一对系统中各种类型的作业进行组织。四.练习题1 .实时操作系统必须在（）处理来自外部的事件。A.一个机器周期 B.被控制对象规定的时间C.周转时间 D.时间片2 .操作系统中最基本的两个特征是（）A.并发和不确定性 B.并发和共享 C.共享和虚拟 D.虚拟和不确定性3 .分时系统追求的目标是（）A.充分利用I/O设备 B.快速响应用户C.提高系统吞吐量 D.充分利用存4 .批处理系统的主要缺点是（）A.系统吞吐量小 B.C P U利用率不高 C.资源利用率低 D.无交互能力5 .在主机控制下进行的输入输出操作称为（）操作。6 .如果操作系统具有很强
23、的交互性，可同时供多个用户使用，系统响应比较及时，则属于（）类型；如果系统可靠，响应及时但仅有简单交互能力则属于（）类型；如果操作系统在用户提交作业后不提供交互能力，它追求的是计算机资源的高利用率，大吞吐量和作业流程的自动化，则 属 于（）类型。7 .设存中有三道程序A、B、C,它们按A、B、C的优先次序执行。它们的计算和I/O操作时间操作,程序ABC计算3 06020I/O403 040计算101020如下表所示（单位：ms）。假设三道程序使用相同设备进行I/O 操作，即程序以串行方式使用设备。试画出单道运行和多道运行的时间关系图（调度程序的时间忽略不计）。在两种情况下，完成三道程序各要花多
24、少时间？8.试比较分时系统和实时系统。9.简述DOS、Windows和 UNIX操作系统的特点。第二章 进程管理本章学习要点 1 掌握进程的定义和特征 2 深入领会进程状态及其状态转换的原因 3 熟练运用信号量解决进程同步问题 4 掌握调度的类型与方式 5 掌握常用的进程调度算法 6 掌握死锁的相关知识 7 深入领会银行家算法本章学习重点和难点 1运用信号量解决进程同步问题 2 进程调度算法 2 银行家算法知识点回顾多道程序设计技术的引入，实现了资源的共享和程序的并发执行。为了描述并发执行的动态特点，引入进程的概念。进程是可并发执行的程序在一个数据集合上的运行过程，具有动态性、并发性、独立性、
25、异步性和结构特征。进程管理包括进程控制、进程同步、进程通信和进程调度四个主要方面。一.前趋图和程序执行1.前趋图是一个有向无循环图，以描述结点（语句、程序段或进程）之间的前趋关系，前趋关系描述了结点执行的先后次序。2 .程序顺序执行和并发执行的特征令程序的顺序执行数 据1：1输 入2计 算3打印 数据2：4输 入5计 算6打印对较大程序的若干个程序段，或者某个程序段的多条语句，执行时必须按照某种先后次序逐个执行。具备顺序性、封闭性和可再现性。令程序的并发执行输入计算输出同一数据的不同操作之间、不同数据的同一操作之间存在着前趋关系。但不同数据的不同操作之间可考虑并发执行。例：13、C 2、P 1
26、,可并发执行。并发执行出现了新特征：间断性、失去封闭性和不可再现性。3.程序并发执行的条件。(B e r n s te i n 条件)R (pi)：读集，表示程序pi 在执行期间所需参考的所有变量的集合。W (pi):写 集,表示程序pi 在执行期间要改变的所有变量的集合。若两个进程P 1和 P 2 能满足下述B e m s te i n 条件，它们便能并发执行，且具有可再现性。R(PD n w(P2)UR(P2)n w(pi)u w(pi)n w(P2)=二.进程的描述1.进程的定义和特征进程是可并发执行的程序在一个数据集合上的运行过程。具有以下特征：令 动态性一一是进程最基本的特性。进程有
27、一定的生命期，由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤消而消亡。而程序是一组有序指令的集合，是静态实体。令并发性一一多个进程在一段时间间隔同时运行。令独立性一一进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立调度的基本单位。令异步性一一进程按各自独立的、不可预知的速度向前推进。令 结构特征一一进程实体由程序段、数据段和进程控制块P C B 组成。令A：进程调度 B：发生某事件无法执行C：时间片到或优先级高的进程到达I)：阻塞的事件消失3.进程控制块令进程控制块是进程实体的一部分，它记录了操作系统所需的、用于描述进程情况及控制进程运行所需的全部信息。令进程控制块的
28、作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能和其它进程并发执行的进程。令P C B 是进程存在的唯一标志。创建新进程时建立一个P C B,进程结束时回收P C B。令P C B 经常被系统访问，应常驻存。令 P C B 的容 进程标识符信息一一外部标识符、部标识符(唯一整数)。A 处理机状态信息 进程调度信息一一进程状态、优先级等。进程控制信息一一程序和数据地址、同步机制、资源清单等。令 PCB的组.织方式A 方式-相同状态的PCB,成一个队列。A 索引方式-建立索引表。三.进程控制1 .操作系统的核核是计算机硬件的第一层扩充软件，由与硬件紧密
29、相关的模块以及运行频率较高的模块组成，常驻存，以提高OS的运行效率。令支撑功能 中断处理是核最基本的功能，它是整个操作系统赖以活动的基础。核只对中断进行 有限的处理”，然后转由有关进程继续处理。时钟管理 原语操作原语本身是由若干条指令构成，用于完成一定功能的一个过程。原语是一个不可分割的原子操作。令资源管理功能一一进程管理、存储器管理和设备管理。2.进程的创建、终止、阻塞与唤醒(1)进程的创建令进程图一一是描述进程家族关系的有向树。有向边表示了进程的创建关系，即父子关系，(注：并不能说明前趋关系)，子进程可以继承父进程所拥有的资源，父进程撤消时必须同时撤消其所有子进程。令引起创建进程的事件 用
30、 户 登 录(分 时 系 统)作业调度(批处理系统)C由系统核创建进程 提供服务 J 应用请求一一应用进程创建令进程的创建一一创建原语申请空白PCB 为进程分配资源一 初始化PCB-插入就绪队列(2)进程的终止一一正常结束、异常结束、外界干预(3)进程的阻塞与唤醒令 原因一一请求系统服务、启动某种操作、新数据未到达、无新工作令 阻塞一一当出现上述事件，进程无法继续执行，进程通过调用阻塞原语block把自己阻塞，是进程自身的一种主动行为。令唤醒一一当阻塞事件结束，由发现者进程调用唤醒原语将阻塞进程唤醒，是一种被动行为。四.进程同步1.进程同步的基本概念多道程序环境下，系统中的进程间可能存在两种关
31、系：间接制约关系一一资源共享，进程同步保证诸进程互斥访问临界资源。直接制约关系一一相互合作，进程同步保证诸进程在执行次序上的协调。令临界资源-段时间只允许一个进程访问的资源。例如：打印机。令临界区进程中访问临界资源的那段代码称为临界区。要保证对临界资源的互斥访问，只需保证进程互斥地进入自己的临界区。R e pe a t进入区(entrysection)检查临界资源的使用，设置访问标志临界区(c r i t i c a l s e c t i o n)退出区(exit section)恢复未访问标志剩余区(r e m a i n d e r s e c t i o n)u n t i l f a
32、 l s e令同步机制应遵循的准则 空闲让进一一有效利用 忙则等待一一互斥 有限等待一一避 免“死等”让权等待一一避 免“忙等”令利用硬件方法解决进程互斥一一特殊的硬件指令2.信号量机制令整型信号量机制 将整型信号量定义为一个整型量，仅能通过两个标准的原子(不可中断)操作(P、V)来访问。P(S)：w h i l e s W O d o n o o p 忙等”s：=s T；V(S)：s：=s+l；A 利用信号量实现互斥为使多个进程能互斥地访问某临界资源，应为该临界资源设置一互斥信号量m u t e x,并设初始值为1,然后将各进程的临界区置于P (m u t e x)和 V (m u t e
33、x)操作之间。注意实现进程互斥时P、V操作必须成对出现。R e pe a t进入区P(mutex)临界区(c r i t i c a l s e c t i o n)退出区V(mutex)剩余区(r e m a i n d e r s e c t i o n)u n t i l f a l s e由于m u t e x 的初值为1 任何时刻只能有一个进程进入临界区，此时互斥信号量=0,其它欲进入临界区的进程忙等。利用信号量描述前趋关系一一设置公用信号量S o令记录型信号量机制一一采用记录型的数据结构 t y p e se m a p h o re=re c o rdv a l u e：i n
34、t e g e r；表示资源数目L：l i st o f p ro c e ss；等待该资源的进程链表e n d p(s)s.v a l u e：=s.v a l u e-1；i f s.v a l u e 0 t h e n b l o c k(s,1)s.v a l u e 的初值表示系统中某类资源的数目。s.v a l u e 0 (不含=0)表示资源已分配完毕，自我阻塞。s.v a l u e v(s)s.v a l u e:=s.v a l u e+1；i f s.v a l u e/0 t h e n w a k e u p(s,1)；s.v a l u e W O表示仍有等待该资
35、源的进程，将第一个等待进程唤醒。当一个进程需要共享多个临界资源时，若进程的推进顺序不当，可能会产生死锁。令信号量集机制 A ND 型信号量集机制将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程使用完后一起释放。S P(S I,S 2,.S n)S V (S I,S 2,.S n)一 般“信号量集”机制P(S i,t”d i)t i 表示资源下限&表示资源需求或分配数目条件：S i t i 分配：S i：=p(s,d,d)p(s,1,1)p(s,1,0)Si-di一般信号量(s l)一般的记录型信号量(s=l)互斥信号量可控开关3.经典进程的同步问题令 生 产 者 消
36、费者问题：相互合作进程关系的抽象0公用缓冲池e m p t y=n 空缓冲的数量 m u t e x=l 互斥信号量f u l l=0 满缓冲的数量生产者消费者是否有产品可消费 每个程序中实现互斥的p (m u t e x)和v (m u t e x)必须成对出现。对生产者和消费者的Pv操作同样需要成对出现，但它们是分别处于不同的程序中。在每个程序中多个P操作顺序不能颠倒。令读者一一写者问题一个数据对象(数据文件或记录)，可被多个进程共享。允许多个re a d e r进程同时读一个共享对象，但绝不允许一个w ri t e r进程和其它re a d e r进程或w ri t e r进程同时访问共
37、享对象。利用记录型信号量解决读者一一写者问题r e a d c o u n t=0：读者数目，临界资源rm u t e x=l：对re a d c o u n t互斥访问的互斥信号量w m u t e x=l：写互斥信号量流程见下图。A 利用信号量集机制解决读者一一写者问题读者：re p e a tsp(L,l,l)L 为读者数(R N)sp(m x,1,0)m x为控制开关.读操作.sv(L,1)写者：re p e a tsp(m x,1,1；L,R N,O)写操作sv (m x,1)u n t i l f a l seu n t i l f a l se读者：p(rm u t e x)第一
38、个读者写者:p (w i i m t e x)p(w m u t e x)re a d c o u n t=0?nre 3 d c o u n t：=re a d c o u n t+lv(rm u t e x)读操作p(rm u t e x)re a d c o u n t：=re a d c o u n t Tre a d c o u n t=0?T j最后一个读者读完nv (rm i Y t e x)v (w m u t e x)写操作v(w m u t e x)令哲学家进餐问题五.进程通信进程通信是指进程间的信息交换。进程的同步是低级通信，效率低，对用户不透明。高级通信是指用户直接利用
39、操作系统所提供的一组通信命令（隐藏了进程通信的实现细节），高效地传送大量数据的一种通信方式。1 .共享存储器系统相互通信的进程共享某些数据结构或共享存储区。令基于共享数据结构的通信方式（低级）令基于共享存储区的通信方式2 .消息传递系统进程间的数据交换以消息为单位。程序员直接利用系统提供的一组通信命令（原语）来实现通信。令直接通信方式发送进程利用O S所提供的发送命令，直接把消息发送给目标进程。要求发送进程和接收进程都以显式的方式提供对方的标识符。S e n d（r e ce i v e r ,m e s s ag e）R e ce i v e（s e n de r ,m e s s ag e
40、）间接通信方式通过中间实体（信箱）进行通信，广泛用于计算机网络中。消息在信箱中可以安全保存，只允许核准的用户随时读取。系统为信箱提供了创建、撤消、消息发送、接收等原语。信箱的种类：私用信箱一一用户进程自己创建，作为该进程的一部分，采用单向链路，其他用户发送消息，主人读取消息。公用信箱一一操作系统创建，在系统运行期始终存在，采用双向通信链路，核准用户可发送和取出消息。共享信箱一一某进程创建，指明共享进程的名字。主人和共享者都有权取走自己的消息。信箱通信，发送和接收进程之间存在1:1、n：L l：n （广播）、m：n （公用信箱）的关系。3.管道通信一一共享文件的通信方式管道是指用于连接一个读进程
41、和一个写进程，以实现它们之间通信的共享文件，又称p i p e 文件。U N IX系统采用。写进程以字符流的形式将大量数据送入管道，读进程接收数据。读 进 程 6 Q 1进程管道通信机制必须提供互斥、同步和确定对方的三种协调能力。六.进程调度i .调度队列模型时间片完批量作业作业调度2 .调度类型令高级调度一一作业调度批处理系统中使用，周期较长。令低级调度一一进程调度是最基本的一种调度，在三种类型的O S 中都必须配置。进程调度可采用非抢占或抢占两种方式。其中抢占方式允许调度程序根据某种原则，例时间片原则、优先权原则、短进程优先原则等去停止某个正在执行的进程，将已分配给该进程的处理机，重新分配
42、给另一进程。进程调度的运行频率最高，故算法不能太复杂。令中级调度引入中级调度的目的是为了提高存的利用率和系统吞吐量。中级调度实际上是存储器管理中的对换功能。3 .选择调度方式和算法的准则周转时间（批处理）面 向 用 户.响 应 时 间（分时）的准则|截止时间的保证（实时）I 优先权准则面向系统 系统吞吐量高（批处理）的 准 则 4 处理机利用率好I 各类资源的平衡利用令周转时间一一指作业提交系统开始，到作业完成为止的时间间隔。令带权周转时间一一作业的周转时间与系统为它提供的实际服务时间之比。W-T/T S令响应时间一一从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。令截止时间一
43、一某任务必须开始执行的最迟时间，或必须完成的最迟时间。令吞吐量一一单位时间所完成的作业数。4 .调度算法（作业调度、进程调度）令先来先服务调度算法（F C F S）按进入后备（或就绪）队列的先后选择目标作业（或进程）。有利于长作业（进程），不利于短作业（进程）。令 最短作业优先调度算法S J （P）F 从 后 备（或就绪）队列中选择估计运行时间最短的作业（或进程）产t+（l-）t 为实际值，为预测值 S J F 有效地降低作业的平均等待时间，提高了系统的吞吐量。A 对长作业（或进程）不利，可能死等，且未考虑作业的紧迫程度。令时间片轮转调度算法（进程调度）系统将所有的就绪进程按先来先服务原则，排
44、成一个队列，每次调度时把C P U分配给队首进程，令其执行一个时间片。就绪队列中所有进程，在一个给定的时间，均能获得一个时间片的处理机执行时间。T=n q令优先权调度算法 适用于作业调度和进程调度。非抢占式、抢占式优先权调度算法 优先权类型：静态优先权、动态优先权令高响应比优先调度算法（作业调度）响应比R 尸响应时间/要求服务时间=（等待时间+要求服务时间）/要求服务时间=1+等待时间/要求服务时间 同时到达的作业(等待时间相同)，要求服务时间越短(短作业)，响应比越高，有利于短作业。要求服务时间相同的作业，等待时间越长，响应比越高，相当于先来先服务。长作业在等待足够长时间后，响应比上升，也可
45、被调度，避免长作业的死等。每次调度需计算响应比，增加系统的开销。令多级队列调度 根据作业的性质或类型的不同，将就绪进程队列分成若干个子队列，各个作业固定分属于一个队列。每个队列采用各自的调度算法。令多级反馈队列调度算法 U N IX系统中的进程调度算法。处理方法：设置多个就绪队列，每个队列赋予不同的优先权展 S),且各队列中进程执行的时间片的大小各不相同(q,2 q n q)o 新进程进入存，首先放在8的末尾，按F CF S排队调度，执行q时间片，若未完成，该进程转入S z,依次类推。仅当S,空闲，才会调度S i”中进程。能较好地满足各种类型用户的需要。七.死锁1 .死锁的概念死锁是指多个进程
46、因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。2 .死锁产生的原因(1)竞争资源一一竞争非剥夺资源、竞争临时性资源(2)进程推进顺序不当3 .产生死锁的必要条件(同时具备)(1)互斥条件一一进程对所分配到的资源进行排它性使用。(2)请求和保持条件一一请求新资源阻塞，保持其它已获得资源不放。(3)不剥夺条件一一进程获得的资源在使用完之前不能被剥夺。(4)环路等待条件一一存在进程一资源环形链。4 .处理死锁的基本方法(1)预防死锁一一设置某些限制条件，破坏必要条件中的一个或几个。(2)避免死锁一一在资源的动态分配过程中，防止系统进入不安全状态。(3)检测死锁一一通过系统设
47、置的检测机构，及时检测出死锁的发生，并精确确定与死锁有关的进程和资源。令保存有关资源的请求和分配信息一一资源分配图资源分配图由一组结点N和一组边E组成。N被分成两个互斥的子集，一组进程结点P=p“P 2,，P ,一组资源结点R=n,.,r E中的边e连接着P中的一个结点和R中的一个结点。e=P i,口 表 示 进 程 p i 请求一个单位的n资源e=r j,p j 表示把一个单位的由资源分配给进程8令提供算法检测系统是否死锁一一死锁定理在资源分配图上，找出一个既不阻塞又非独立的进程结点，简化后使其成为孤立的结点。在进行一系列的简化后，若能消去图中所有的边，使所有结点都成为孤立的结点，则该图是可
48、完全简化的。所有的简化顺序将得到相同的不可简化图。s 为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。（4）解除死锁一一将进程从死锁状态下解脱出来。剥夺资源撤消进程5 .银行家算法令系统的安全状态所谓安全状态，是指系统能按某种顺序，如 PLP2 P n,来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺利完成。若系统不存在这样一个安全序列，则称系统处于不安全状态。如果不按照安全序列分配资源，则系统可能由安全状态进入不安全状态。例，系统共有1 2台磁带机，T O 时刻的情况如下表，已分配出9 台，可用磁带机为3台。经分析发现，T O 时刻存在安全序列P2,Pl,P 3
49、,故系统是安全的。进程最大需求已分配尚 需 要 可 用Pl1055 3(2)P2422P392(3)7(6)若此时P3 请 求 1台磁带机，则分配情况如上表（括号的数据），此时系统不存在安全序列,进入不安全状态，将导致死锁。令利用银行家算法避免死锁 数据结构（n 个进程，m类资源）可利用资源a v a i l a b l e 1.m 最大需求矩阵（n*m）m a x分配矩阵（n*ni）a l l o c a ti o n需求矩阵（n*m）ne e d i,j =m a x i,j -a l l o c a ti o n i,j 步骤设 r e q u e st j =k,表示进程P 需要k个
50、j 类资源。分配 拒绝分配 安全性算法（1）设置向量w o r k 和 f i ni sh 的初始值w o r k=a v a i l able目前可提供的资源数目f i ni sh i =f a l se 表示该进程尚未运行完成。r-（2）从进程集合中找到满足下述条件的进程f i ni sh i =f a l se；ne e d：w o r k；若找到，执 行（3）,否则执行（4）。-（3）进程获得资源，执行并完成，释放资源w o r k=w o r k+a l l o c a ti o nf i ni sh i =tr u e（4）若所有进程的f i ni sh i =tr u e,则表示