赵帼英操作系统考研辅导

2016考研辅导赵帼英2015年春2015年考试大纲试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分复习方法研读教材教师：

1、分析形势，列提纲

2、“猜题”

3、答疑同学：

1、紧跟我（花最少的时间）

2、怎么看书 3、做题操作系统大纲1、掌握操作系统基本概念、基本原理和基本功能。理解操作系统的整体运行。2、掌握操作系统的进程、内存和设备管理的策略、算法、机制和相互关系。3、能运用操作系统原理、方法和技术分析问题和解决问题，并能用C语言描述相关算法。一、操作系统的概述1、操作系统的基本概念、特征、功能和提供的服务。2、操作系统的发展和操作系统分类3、操作系统运行环境内核态与用户态中断、异常系统调用4、操作系统的体系结构二、进程管理（一）进程与线程进程的概念进程的状态与转换进程的控制进程组织进程通信线程概念、多线程模型（二）处理机调度

调度的基本概念调度时机、切换与过程进程调度的基本准则进程调度方式进程调度算法（三）进程互斥与同步

进程同步的基本概念实现临界区互斥的基本方法软件实现方法硬件实现方法信号量方法管程方法经典进程互斥与同步问题生产者/消费者问题（四）死锁死锁的概念、引起死锁的原因死锁处理的策略预防死锁避免死锁：安全状态、银行家算法检测并解除死锁三、内存管理（一）内存管理基础内存管理的概念程序链接与程序装入、逻辑地址与物理地址空间、内存保护交换与覆盖连续存储管理方式非连续存储管理分页式存储管理、分段式存储管理、段页式存储管理。（二）虚拟内存管理虚拟内存的基本概念请求分页存储管理页面分配策略固定分配局部置换、可变分配全局置换、可变分配局部置换

页面置换先进先出、最佳置换（OPT）、最近最少使用置换（LRU）和时钟置换算法（Clock）抖动四、文件管理（一）文件系统基础1、文件概念2、文件的逻辑结构顺序文件、索引顺序文件、索引文件、3、目录结构文件控制块和索引结点、单级目录结构、两级目录结构、树型目录结构、图型目录结构4、文件共享5、文件保护：访问类型、访文控制（二）文件系统的实现1、文件系统层次结构2、目录实现3、文件实现（三）磁盘组织与管理1、磁盘结构2、磁盘的调度算法3、磁盘的管理五、输入输出（I/O）管理（一）I/O管理概述1、I/O控制方式2、I/O软件层次结构（二）I/O核心子系统1、I/O调度概念2、高速缓冲与缓冲区3、设备分配和回收4、假脱机处理（Spooling）5、出错处理操作系统概念第一章操作系统引论

操作系统的目标、作用和模型

l

操作系统——是裸机上的第一层软件，它是对硬件系统功能的首次扩充，是填补人与机器之间的鸿沟。用户计算机OS

操作系统的目标●

设置操作系统的目的：

1、方便性:操作系统使计算机更易于使用

2、有效性:操作系统允许以更有效的方式使用计算机系统资源。

3、可扩展性:在操作系统中,允许有效地开发，测试和引进新的系统功能。

4、开放性:实现应用程序的可移植性和互操作性,要求具有统一的开放的环境。

OS的作用●计算机用户需要的用户命令由OS实现的所有用户命令所构成的集合常被人们称为OS的Interface(用户接口)；有时也称为命令接口。

命令的表示形式： 字符形式：较灵活但因繁琐而难记；

菜单形式：(试图在字符终端上提供友好的用户界面)

图形形式：因直观而易记但不灵活。●应用软件需要的SystemCall(系统调用)

由OS实现的所有系统调用所构成的集合被人们称为程序接口或应用编程接口(ApplicationProgrammingInterface,API)。中断与异常（一）强迫性中断事件1、由于外部的请求或某些意外事故而迫使正在运行的进程被打断。2、强迫性中断的类型（时钟、它机）（二）自愿性中断事件（软中断）在进程中请求操作系统服务，通过系统调用所引起的。区别(3-1)1．中断(外中断）

（1）是由CPU外部产生的，对CPU来说，是被动的。

（2）当中断发生时，CPU将下一条指令，也就是接下来要执行的指令的地址压入栈作为中断服务的返回地址。区别(3-2)2．陷入(xianru)内中断

（1）是由CPU本身在执行程序过程中产生的。它是由专设的指令，如X86中的“INTn”，在程序中有意产生的，是主动的。

（2）同中断一样，当陷入发生时，CPU将下一条指令，也就是接下来要执行的指令的地址压入栈，作为中断服务的返回地址。

区别(3-3)3．异常（内中断）(1)是由于CPU因无法完成一些指令而产生的，如除以0、映射失败，等等。(2)当异常发生时，CPU将当前指令的地址（而不是下一条指令的地址）压入栈，作为异常服务的返回地址。这样，就可以在异常处理返回时完成未竟完成的事业。(3)这个特殊性是在CPU的内部电路实现的，而不需由软件干预。即是由Intel实现的，和微软没关系。

同步中断（又称异常）：处理器控制单元在执行指令时产生的，之所以叫同步是因为控制单元在停止指令执行之后立刻就发出中断。该中断主要由于程序错误或者反常的条件必须由内核处理。程序错典型的即为除零。反常的例子如缺页错误，系统对用户屏蔽这种错。异步中断（中断）：是由其它硬件设备在任意时刻发出的，它和CPU的时钟信号相关。该中断主要由间隔的时钟和I/O设备发出的，如用户每次敲击键盘都会给处理器一个中断。（二）管态和目态管态——当CPU处于管态时可执行包括特权在内的一切机器指令。目态——当CPU处理目态时，不允许执行特权指令。操作系统资源管理功能操作系统作为计算机系统资源管理者。1、处理机管理：分配和控制CPU。2、存储器管理：内存分配与回收。3、I/O设备管理：I/O设备的分配与操纵。4、文件管理：文件的存取、共享和保护。操作系统用作扩充机器功能，使其便于使用的机器，这种机器又称为虚拟机。真题：1、

系统调用的目的是（

）。A:请求系统服务 B:终止系统服务C:申请系统资源 D:释放系统资源

真题：当处理器处于管态时，处理器可以执行的指令应该是（

）。A:非特权指令 B:仅限于特权指令C:一切指令D:访管指令

操作系统的发展返回无操作系统时的计算机系统1、

人工操作方式一台计算机的所有资源由用户独占，降低了计算机资源利用率，人操作慢，出现了严重的人机矛盾。2、

脱机输入输出方式在外围计算机的控制下，实现输入输出。主要解决了CPU与设备之间不匹配的矛盾

单道批处理系统1、在内存中仅存一道作业运行，运行结束或出错，才自动调另一道作业运行。2、单道批处理系统主要特征：自动性、顺序性、单道性。3、单道批处理系统主要优点：减少人工操作，解决了作业的自动接续。4、单道批处理系统主要缺点：平均周转时间长，没有交互能力。多道批处理系统一、多道程序的概念：在内存中存放多道作业运行，运行结束或出错，自动调度内存中的另一道作业运行。●多道程序带来的好处：1、提高CPU的利用率。2、提高内存和I/O设备利用率。3、增加系统吞吐率。二、多道批处理系统主要特征：多道性、无序性、调度性（进程调度和作业调度）。三、多道批处理的主要优点：提高了资源利用率和吞吐能力。多道批处理的主要缺点：平均周转时间长，没有交互能力。例1．设在内存中有三道程序A、B和C，按A、B、C的优先次序运行，其内部计算和I／O操作时间由下图给出。

若处理机调度程序每次进行状态转换需要的时间为1ms，试画出按多道程序运行的时间关系图。并计算完成这三道程序共使用了多少时间？并计算比单道运行节省多少时间？BC

答：多道程序运行时间关系图如下图所示：由图可计算出在多道程序运行下执行了196ms的时间，而在单道运行的时间为：30＋1+40＋1＋10＋1+60＋1＋30＋1＋16＋1+20＋1＋40＋1＋20＝274ms多道运行的时间为：30+1+40+1+10+1+20+1+30+1+40+1+20=196则多道程序比单道程序节省的时间为：274一196＝78msA30B40A10B20C20B16C20CPUA40B30C40I/O

分时系统一、分时系统的产生用户需要：人机交互、共享主机、便于用户上机二、分时系统实现的方法简单分时系统具有“前台”和“后台”的分时系统多道分时系统三、分时系统实现中的关键问题：及时接收：实现多个用户的信息及时接收。及时处理：及时控制作业的运行。四、分时系统的特征：多路性：多个用户分时使用一台计算机。独立性：独立运行，不混淆，不破坏。及时性：系统能在很短的时间得到回答。交互性：能实现人机对话。五、影响响应时间的若干因素:改善响应时间的方法采用重入码减少信息的对换量采用虚拟存储技术,减少信息对换量实时系统●所谓实时系统：是计算机及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行。一、实时系统分为两类

1、实时控制系统

2、实时信息处理系统二、实时任务的类型

1、按任务执行是否为周期性来化分

2、按截止时间来化分

三、实时系统的特征

1、多路性：能对多个对象进行控制。

2、独立性：独立运行，不混淆，不破坏。

3、交互性：仅限于访问系统中某些特定的专用服务程序。

4、可靠性：高可靠性，应具有过载防护能力。

5、及时性：不同的系统要求不一样，控制对象必须在截止时间内完成。操作系统的基本特征现代OS的四个基本特征：1、并发2、共享3、虚拟4、异步并发是最重要的特征，其它特征都以并发为前提。

并发并发——并行性和并发性，并发执行的过程。

-并行性是指两个或多个事件在同一时刻发生。

-并发性是指两个或多个事件在同一时间间隔内发生。任务共行

-从宏观上看，任务共行是指系统中有多个任务同时运行

-从微观上看，任务共行是指单处理机系统中的任务并发（TaskConcurrency：即多个任务在单个处理机上交替运行）或多处理机系统中的任务并行（TaskParallelism：即多个任务在多个处理机上同时运行）。

共享所谓共享是指系统中的资源可供内存中多个并发执行的进程共同使用。1、互斥共享方式：

-把在一段时间内只允许一个进程访问的资源，称为临界资源。

-系统中的临界资源可以提供给多个进程使用，但一次仅允许一个进程使用，称为互斥共享方式。2、同时访问方式：

-从宏观上看，资源共享是指多个任务可以同时使用系统中的软硬件资源

-从微观上看，资源共享是指多个任务可以交替互斥地使用系统中的某个资源。例如磁盘。虚拟所谓虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。虚拟处理机：分时实现虚拟设备：SPOOLING技术虚拟存储器：虚拟存储管理实现

异步性异步性——

是指进程以异步的方式执行，进程是以人们不可预知的速度向前推进。

操作系统的结构设计

操作系统是一个大型系统软件，其结构已经历了四代的变革：第一代的OS是无结构的；第二代OS采用了模块式结构；第三代是层次式结构。第四代是把工程学引入到软件开发的过程中，从而形成了软件工程学

模块化OS结构

(1)模块化结构使用分块结构的系统包含若干module（模块）；其中，每一块实现一组基本概念以及与其相关的基本属性。块与块之间的相互关系：

-所有各块的实现均可以任意引用其它各块所提供的概念及属性。(2)模块化OS的优缺点

优点：①提高了OS设计的正确性、可理解性和可维护性。②增强了0S的可适应性。③加速了OS的开发过程。缺点:①对模块的划分及对接口的规定要精确描述很困难。②从功能观点来划分模块时，未能将共享资源和独占资源加以区别；分层式OS结构

使用分层系统结构包含若干layer（层）；其中，每一层实现一组基本概念以及与其相关的基本属性。层与层之间的相互关系：

-所有各层的实现不依赖其以上各层所提供的概念及其属性，只依赖其直接下层所提供的概念及属性；

-每一层均对其上各层隐藏其下各层的存在。

微内核OS结构

微核结构设计思想：尽最大努力剔除核心子系统中的多余成份，并把它们移到核外子系统中实现，核心子系统只实现一些必要的简单的概念及其属性，从而保持核心子系统简洁高效。●当前比较流行的、能支持多处理机运行的OS，几乎全部都采用了微内核结构，微内核技术

微内核的基本功能：（1）进程管理。①把进程作为资源分配的基本单位。②允许一个进程拥有若干个线程。③把线程作为独立运行和调度的基本单位。④在同一进程中的各线程可以共享进程所拥有的资源。⑤允许这些线程并发执行。⑥实现进程间和线程间的同步。

（2）存储器管理①提供了虚拟存储器管理功能，例如页式存储管理。②用于为进程分配和回收运行空间。③从逻辑上扩充内存的容量，以满足更多用户的需求。（3）进程通信管理为实现进程之间的通信，在微内核中采用了消息传递机构，即进程之间是以消息（Message）作为交换单位。（4）I/O设备管理在微内核中，为每一个连接到主机上的I/O设备配置一个设备驱动程序，用以实现设备的I/O处理，因此，通常在微内核中都有若干个I/O设备驱动程序。第二章

进程的描述与控制

一、

相关概念

1、

前趋图——有向无循环的图。表示程序执行的偏序关系。

2、程序的顺序执行——严格按照程序给定的顺序执行，仅当前一个执行结束才执行后一个。

3、

程序的顺序的特征：①顺序性②封闭性③可再现性

4、程序的并发执行——是指两个或两个以上程序段在执行的时间上是重叠的，即使这种重叠只有一小部分，则称这些程序为共行执行。5、程序并发执行的特征：①间断性②失去封闭性③不可再现性1、试比较进程与程序的异同举例例2：若程序Pa和Pb单独执行时间分别Ta、Tb和Tc，Ta=1小时，Tb=1.5小时，Tc=2小时，其中处理机工作时间分别为Ta=10分钟，Tb=15分钟，Tc=35分钟。如果采用多道程序设计的方法，让Ta、Tb和Tc并行工作，假定处理机利用率达到60%，另加20分钟系统开销，请问系统效率能提高百分之几？答：Ta、Tb和Tc并行工作共用CPU时间：（10+15+35）/60%=100系统效率提高：[（60+90+120）-（100+20）]/[（60+90+120）*100%]=（270-120）/（270*100%）=55%3、已知一个求值公式（A2/3B）/（B+5A），

若A、B已赋值，画出该公式求值过程的前趋图

二、

进程的基本概念

1、进程的定义——可并发执行的程序在一个数据集合上的运行过程。

2、进程的基本特征①

动态性②

并发性③

独立性④

异步性⑤

结构特征

3、进程的基本状态及其转变进程的三种基本状态及其转换

带有挂起状态进程五状态转换图

4、

进程控制块——描述和控制进程运行，系统为每个进程定义的一个数据结构。①

进程控制块的内容②

进程控制块的作用③

进程控制块的组织方式三、

进程控制1、进程管理进程图：表明进程的创建关系，创建的进程和被创建的进程可以并发执行。2、引起进程创建的原因①用户登录：为终端用户建立进程。②作业调度：选中的作业建立进程。③提供服务：为用户提供的服务进程。例如：I/O进程等。④应用请求：应用程序自己创建的进程。3、原语：由若干条指令构成，用于完成一定功能的一个过程。4、原子操作（原子性）：一个操作中的所有动作，要么全做，要么全不做。是一个不可分割的操作。四、进程组织

进程控制块的组织方式1）链接方式把具有同一状态的PCB，用其中的链接字链接成一个队列。2）索引方式系统根据所有进程的状态建立几张索引表。1）链接方式2）索引方式5、

线程的基本概念（1）线程：一个被调度和分派的基本单位并可独立运行的实体。（2）线程分类：①内核支持线程：依赖于内核进行控制和管理。②用户级线程：在用户级创建、撤消和切换。（3）在引入线程的O.S系统中，则把线程作为调度和分派的基本单位，而把进程作为资源的拥有的基本单位。（4）在同一进程中的线程切换不会引起进程切换。（5）在不同一进程中的线程切换会引起进程切换。线程状态(1)线程的状态有:执行状态、运行状态、就绪状态等。(2)在线程切换时保存的线程信息:①一个执行栈。②每个线程静态存储局部变量。③对存储器和其进程资源的访问，并与该进程中的其他线程共享这些资源。线程状态变化的4种基本操作:①派生（Spawn)：当产生一个新进程时，同时也为该进程派生了一个线程，随后，进程中的线程可以在同一个进程中派生另一个线程，新线程被放置在就绪队列中。②阻塞（B1ock)：当线程需要等待一个事件时，它将阻塞，此时处理器转而执行另一个就绪线程。③解除阻塞（Unb1ock）：当阻塞一个线程的事件发生时，该线程被转移到就绪队列中。④结束（Finish）：当一个线程完成时，其寄存器的信息和栈都被释放。注意（一）:1、在单线程进程模型中，包括它的进程控制块和用户地址空间，以及用户栈和内核栈。2、在多线程环境中，仍然有一个与进程相关联的进程控制块和用户地址空间，但是每个线程都有一个独立的栈和独立的控制块，包含寄存器值。优先级和其他与线程相关的状态信息。3、进程中的所有线程共享该进程的状态和资源，它们驻留在同一块地址空间中，并且可以访问到相同的数据。4、线程阻塞不会引起进程阻塞。注意（二）:5.

在同一进程中的线程切换不会引起进程切换。6.在不同一进程中的线程切换会引起进程切换。图示：单线程和多线程模式

五、进程同步的基本概念1、进程的相互制约①间接相互制约——资源共享引起②

直接相互制约——相互合作引起2、临界资源：一次仅允许一个进程使用的资源称为临界资源。3、临界区：访问临界资源的那段代码称为临界区。4、同步机制应遵循的准则：①空闲让进——

充分利用资源②忙则等待——

保证同步与互斥③有限等待————

防止陷入“死等”④让权等待——

防止陷入“忙等”

1、用户级线程与内核级线程的区别是什么？2、PCB中包含哪些信息？进程状态属于哪类信息？

3、什么是操作系统的内核？

互斥与同步的解决策略互斥与同步的解决方法:软件方法、硬件方法、信号量方法、管程的方法。软件方法是指由进程通过执行相应的程序指令，实现与其他进程的互斥与同步。很难正确控制进程间的同步与互斥，而且大幅度增加系统的开销。爱斯基摩人的小屋协议硬件方法是指通过屏蔽中断（单CPU）或采用专门的机器指令控制互斥与同步。由于太强的硬件约束条件可能导致进程的饥饿与死锁现象。专用机器指令：TestandSet和ExchangeInstructionTestandSetBoolTS(bool&x){if(x){x=false;Returntrue;}elseReturnfalse;}Bools=true;CobeginProcesspi(){While(!TS(S));{临界区};S=true;}coend信号量机制

1、经典信号量——表示资源的物理实体。

2、记录型信号量——更有效的利用资源，解决忙等的问题。

3、AND型信号量机制——防止系统出现不安全性。①AND型信号量机制的概念化②Swait操作（SP操作）③Ssignal操作（SV操作）

4、信号量应用实例①互斥②前趋③同步三、信号量的应用利用信号量实现进程互斥Process1:while(true){

P(mutex);criticalsection;V(mutex);remaindersection;}while(true){

P(mutex);criticalsection;

V(mutex);remaindersection;}Process2:利用信号量实现前驱关系P1P2三、信号量的应用设置一个信号量S，其初值为0,P1；V(S);P(S)；P2;如此即可实现先执行P1，再执行P2三、信号量的应用Eg:设S1,S2,S3,S4为一组合作进程，其前趋图如图所示，用P、V操作实现其同步。

vara,b,c,d:semaphore:=0,0,0,0;/*表示进程是否执行完*/main(){cobegins1();s2();s3();s4();coend}s1s2s3s4abcdS1(){…v(a);}

S2(){…v(b);v(c);}

S3(){p(a);p(b);

…v(d);}

S4(){p(c);p(d);

...}

利用信号量实现前驱关系（同步例子）三、信号量的应用利用信号量实现同步举例返回

经典进程的同步问题

在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：生产者—消费者问题哲学家进餐问题读者—写者问题返回目录经典进程的同步问题

生产者一消费者问题MMMMMMP1P2PnC1C2CninoutVarmutex，empty，full：semaphore：=1，n，0；

buffer：array[0，…，n-1]ofitem；

in，out：integer：＝0，0；

beginparbeginproceducer：beginrepeat┇produceranitemnextp；┇

wait（empty）；

wait（mutex）；

buffer（in）：=nextp；

in：=（in十1）modn；

signal（mutex）；

signal（full）；

unti1false；

end

consumer：beginrepeatwait(full);wait（mutex）；

nextc：=buffer(out)；

out：=（out十1）modn;signal（mutex）；

signal（empty）；

consumertheiteminnextc;untilfalse；

endparendend2、“哲学家进餐”问题5个哲学家围坐在圆桌旁，每人面前有一只空盘子，每2人之间放一只筷子，如图所示。为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子。

问题描述

semaphorestick[5]={1,1,1,1,1};/*分别表示5支筷子*/Main(){cobeginphilosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);coend

}哲学家进餐问题的解决2、“哲学家进餐”问题2、“哲学家进餐”问题哲学家i的活动为：

voidphilosopher(inti){while(true){

思考；

P(chopstick[i])；//取左边筷子

P(chopstick[(i+1)%5])；//取右边筷子进食；

V(chopstick[i])；//放左边筷子

V(chopstick[(i+1)%5])；//放右边筷子

}}哲学家进餐问题的解决3、“读者—写者”问题读者--写者问题有两种类型：解法1：读者优先

只要有一个读者存在，不管有否写者请求，后续读者都可以执行读过程。解法2：读写平等

即一旦有写者到达，后续的读者必须等待，无论是否有读者在读。写者优先。只要有一个写者请求，读者就要等待，直到所有写者退出。返回设置一个共享变量和两个信号量：共享变量Readcount：记录当前正在读数据集的读进程数目，初值为0。读互斥信号量Rmutex：表示读进程互斥地访问共享变量readcount，初值为1.写互斥信号量wmutex：表示写进程与其它进程（读、写）互斥地访问数据集，初值为1.3、“读者—写者”问题—读者优先semaphorermutex=1;semaphorewmutex=1;intreadcount=0;Main(){cobegin

reader();

writer();coend}3、“读者—写者”问题—读者优先{while(true){

p(rmutex);

if(readcount==1)p(wmutex);/*第一位读者阻止写者*/readcount++;

V(rmutex);

读数据集；

p(rmutex);

readcount--;if(readcount==0)v(wmutex);/*第末位读者允许写者进*/

V(rmutex);}}reader(){while(true){

p(wmutex);

/*阻止其它进程（读、写）进*/

写数据集；

V(wmutex);

/*允许其它进程（读、写）进*/}}writer()3、“读者—写者”问题—读写平等为了提高写者的优先级，我们增加一个信号量w，用以在写进程到达时封锁后续的读者进程。相应的控制算法如下：

BEGINintegerrmutex,wmutex,rc,w;rmutex:=1;wmutex:=1;rc:=0;

w:=1;BEGIN

P(w);P(rmutex);rc:=rc+1;IFrc=1THENP(wmutex);V(rmutex);

V(w);ReadingtheFILE;P(rmutex);rc:=rc-1;IFrc=0THENV(wmutex);V(rmutex);END;readerBEGIN

P(w);P(wmutex);WriteingtheFILE;V(wmutex);

V(w);END;COENDWriter返回3、“读者—写者”问题—写者优先Constreadcount,writecount:integerVarx,y,z,rsem,wrem:=semaphoreReader:BeginRepeatP(z);

P(rsem);P(x);Readcount:=Readcount+1;IfReadcount=1thenP(wsem);V(x);

V(rsem);V(z);读数据;P(x);Readcount:=readcount-1;Ifreadcount=0thenV(wsem);V(x);Forever;End;Writer:BeginRepeatP(y);Writecount:=writecount+1;Ifwritecount=1thenP(rsem);V(y);

P(wsem);写数据;V(wsem);P(y);Writecount:=writecount-1;Ifwritecount=0thenV(rsem);V(y);Forever;End;13真题解析：一座单车道东西桥，当桥上有车时，和该车同向的车都可以通过，只有当桥上没有车时反方向的才可以通过。试用信号量和p、V操作解决该问题。互斥与同步解决方法:管程虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait（S）和signal（s）。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的进程同步工具——管程。管程的定义当共享资源用共享数据结构表示时，资源管理程序可用对该数据结构进行操作的一组过程来表示(例如，资源的请求和释放过程request和release)，我们把这样一组相关的数据结构和过程一并称为管程。Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据”。管程的主要特点：局部数据变量只能被管程的过程访问，任何外部过程都不能访问。一个进程通过调用管程的一个过程进入管程。在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变成可用的。管程必须包含同步工具为进行并发处理，管程必须包含同步工具。例如，假设一个进程调用了管程，它在管程中时，不能执行,须被挂起，直到满足某些条件时才恢复。这就需要一种机制，使得该进程不仅被挂起，而且能释放这个管程，以便某些别的进程可以进入。以后，当条件满足并且管程再次可用时，需要恢复该进程并允许它在挂起点重新进入管程。管程操作函数管程通过使用条件变量提供对同步的支持，这些条件变量包含在管程中，并且只有在管程中才能被访问。有两个函数可以操作条件变量：①cwait(c)：调用进程的执行在条件c上挂起，管程现在可被另一个进程使用。②csignal(c)：恢复在cwait之后为某些条件而挂起的进程的执行。如果有多个这样的进程，选择其中一个；如果没有这样的进程，什么也不做。六、进程通信

进程通信的类型：低级通信和高级通信(1)高级通信方式：①共享存储器系统：共享数据结构、共享存储器区通信方式②消息传递系统：直接通信方式——通过收发原语间接通信方式——通过信箱实现信息交换③管道通信（2）管道通信具有三方面的协调能力：①双方同时存在②

同步关系③

互斥使用管道第三章

调度与死锁一、调度的类型

1、高级调度

2、

低级调度：非抢占式、抢占式抢占式原则：时间片原则、优先权原则、短作业优先原则

3、

中级调度二、面向用户的准则1、

周转时间短：平均周转时间、平均带权周转时间2、

响应时间快3、

截止时间的保证4、

优先权准则

三、面向系统的准则1、

系统的吞吐量2、

CPU的利用率好3、

各类资源平衡使用调度的算法1、

先来先服务调度的算法2、

短作业优先调度的算法3、

时间片轮转调度的算法（分时）或简单轮转调度的算法4、

优先权调度的算法：非抢占式、抢占式①静态优先权

②动态优先权5、

响应比高者优先调度的算法：

RP=1+等待时间/服务时间6、多级队列调度算法：例如，前台、后台7、多级反馈队列调度算法实时系统的调度算法

在实时系统中，广泛采用抢占式调度方式调度算法示例：周转时间（常用于批处理系统）定义：作业从提交――>完成的时间时间组成：（1）驻外等待调度时间（2）驻内等待调度时间（3）执行时间（4）阻塞时间返回平均周转时间带权周转时间

平均带权周转时间平均周转时间可以衡量不同调度算法对相同任务流的调度性能。带权周转时间衡量长短任务的差别，故带权周转时间W越小越好作业名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100周转时间服务时间完成时间-到达时间开始时间+服务时间上一个进程的完成时间0

1

1

11 101 1001101 102100100

102 2021991.991、fcfs作业到达时间服务时间开始时间结束时间周转时间带权周转时间周转时间＝结束-到达带权周转时间＝周转/服务

执行顺序：2、SJF/SPF__非抢占式举例A033103ABCDE24686452B3971.1791131.51115112.751520142.8ECD7.61.84

SRT的调度次序作业到达时间服务时间开始时间结束时间

=1.59034158315820103134142=7.208364522046ABCBE→→→→112.1712.8ECDAB周转时间T=结束时间-到达时间=3-0=3周转时间带权周转时间W=周转时间T/服务时间Tr=3/3=1带权周转时间平均01234567891011121314151617181920D→B剩余时间=6-1=5；C剩余时间=4-0=4；05003、补充:最短剩余时间调度算法（SRT）4、分时系统举例：例：一个分时OS，10个终端，时间片100ms，每个用户的请求进程要300ms的时间处理，问终端用户提出二次请求的时间间隔最少是多少？解：响应时间＝100ms×10＝1s，每个用户的请求要获得3个时间片才能处理完，要轮转3次，才能都处理完，所以终端用户的二次请求时间间隔最少应为3s。5、时间片轮转调度算法—例(1)EG： 进程

到达时间

服务时间

P1 0 7

P2 2 4

P3 4 1

P4 5 4RR（时间片为4）P1P2045678

910111213141516P1P3P4平均周转时间=((16-0)+(8-2)+(9-4)+(13-5))/4=8.75平均等待时间=(9+2+4+4)/4=4.75算法HRP示例

HRP的调度性能作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc

=2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周转时间T=结束时间Tc-到达时间Tin=3-0=3周转时间T带权周转时间W=周转时间T/服务时间Tr=3/3=1带权周转时间W平均=[(9-4)+4]/4=2.25=[(9-6)+5]/5=1.6=[(9-8)+2]/2=1.5RCRDRERD=[(13-6)+5]/5=2.4RE=[(13-8)+2]/2=3.5如果在限制为两道的多到程序系统中有4个作业进入系统，其进入系统时间、估计运行时间列于下表中。系统采用SJF作业调度算法，采用SRTF进程调度算法，请填充下表。作业进入系统时间估计运行时间/min开始运行时间结束运行时间周转时间/minjob110:0030job210:0520job310:105job410:2010平均周转时间T=带权平均周转时间W=

死锁的基本概念1、

何谓死锁？2、产生死锁原因：①

竞争资源②

推进顺序不当3、产生死锁的必要条件①互斥②请求和保持③不剥夺④环路等待条件

指多个进程在运行过程中因争夺资源,推进顺序不当或进程通信而造成的一种僵局（deadly-Embrace)，若无外力作用，这些进程都将无法向前推进。如图R1R2P1P2注意：（1）参与死锁的进程数至少为2（2）参与死锁的所有进程均等待资源（3）参与死锁的进程至少有两个占有资源（4）参与死锁的进程是系统中当前正在运行进程的一部分。返回一、死锁

4、处理死锁的基本方法①预防死锁：设置某些限制条件，破坏四个条件。②

避免死锁：资源动态分配，防止进入不安全状态。

③检测死锁：设置检查机构，定时检查系统是否出现死锁。④解除死锁：已出现死锁。死锁的避免

死锁的预防和避免方法定义:系统运行过程中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。最具有代表性的避免死锁算法是银行家算法

Banker’sAlgorithm

。二、系统的安全状态

安全状态：如果系统能按某种顺序（如P4，P1，…,Pn,称为安全序列）为每个进程分配其所需的资源，直至每个进程都能顺利地完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。安全状态一定是没有死锁发生的。安全状态实例假定系统中有三个进程P1，P2和P3，共有12台磁带机，三个进程对磁带机的需求和占有如下：进程最大需求已分配可用P11053P242P392T0时刻，存在一个安全序列（P2，P1，P3）或（P2，P3，P1），所以系统是安全的。二、系统的安全状态二、系统的安全状态由安全状态向不安全状态的转换：如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。进程最大需求已分配还需可用p110552p2422p3936因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台），将导致死锁。三、避免死锁的算法-银行家算法为实现银行家算法，系统中必须设置若干数据结构。假定系统中有n个进程（P1，P2，…，Pn），m类资源（R1，R2，…，Rm），银行家算法中使用的数据结构如下：可利用资源向量:available[j]=k,资源Rj类有k个可用最大需求矩阵:Max[i,j]=k,进程Pi最大请求k个Rj类资源分配矩阵：Allocation[i,j]=k,进程Pi分配到k个Rj类资源需求矩阵：Need[i,j]=k,进程Pi还需要k个Rj类资源 三个矩阵的关系：Need[i,j]=Max[i,j]–Allocation[i,j].

★银行家算法

设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。

(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

★安全性算法

(1)设置两个向量：①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;②Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true。

(2)从进程集合中找到一个能满足下述条件的进程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，执行步骤(3)，否则，执行步骤(4)。

(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;(4)如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。银行家算法的例子假定系统中有5个进程3类资源及数量分别为10、5、7，T0时刻的资源分配情况。MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057true（1）T0时刻的安全性T0时刻存在着一个安全序列{P1P3P4P2P0}，故系统是安全的。银行家算法的例子(2)P1请求资源Request1(1,0,2)执行银行家算法银行家算法的例子P1请求资源时的资源分配表MaxAllocationNeedAvailableABCABCABCABCP0753010743332(230)P1322200122(302)(020)P2902302600P3222211011P4433002431WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1230020302532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057trueP1请求资源时的安全性检查表存在着一个安全序列{P1P3P4P2P0}，故系统是安全的，可以立即将P1所申请的资源分配给它。银行家算法的例子（3）P4请求资源Request4(3,3,0)

P4发出请求向量Request4(3,3,0)，系统按银行家算法进行检查:1)Request4(3,3,0)≤Need4(4,3,1)2)Request4(3,3,0)>Available(2,3,0),表示资源不够,则让P4等待银行家算法的例子(4)P0请求资源Request0(0,2,0)银行家算法的例子MaxAllocationNeedAvailableABCABCABCABCP0753010743332[030][723](230)[210]P1322200122(302)(020)P2902302600P3222211011P4433002431P0请求资源时的资源分配表Available＝(2,1,0)不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配返回目录真题:

1、设当前的系统状态如下，此时Available=(1,1,2)进程进程claimAllocationR1R2R3R1R2R3P1322100P2613511P3314211P4422002（1）系统是否处于安全状态，为什么？（3’）（2）进程P2发出请求向量request2(1,0,1),系统能把资源分配给它吗？为什么？（2’）（3）若在进程P2申请资源后，P1发出请求向量request1(1,0,1)，系统能把资源分配给它吗？为什么？（2’）（4）若在进程P1申请资源后，P3发出请求向量request3(0,0,1)，系统能把资源分配给它吗？为什么？（2’）二、死锁判定法则有环无死锁二、死锁判定法则有环有死锁第四章

存储器管理

一、程序的装入

1、绝对装入方式直接用物理地址编址程序。

2、可重定位装入方式（静态重定位）

重定位——把在装入时对目标程序中的指令和数据地址的修改过程称为重定位。

3、动态运行时装入方式（动态重定位）

作业在存储空间的位置，也是装入时确定的，但在作业运行过程中，每次存访内存之前，将程序的地址（逻辑地址）变为内存的物理地址。这种变换是依靠硬件地址变换机构、自动连续实施，这样程序在内存的地址是可变的，可申请临时空间。二、程序的链接1、

静态链接——事先进行链接，以后不再拆开的链接方式，称为静态链接。2、

装入时动态链接——编译后的目标模块，是在装入内存时，边装入，边链接的。3、运行时动态链接——将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，再由操作系统去找到该模块，将它装入内存，并把它链接到调用者模块上。4、静态链接需要共享目标模块的拷贝，而动态链接不需要共享目标模块的拷贝。三、连续分配存储管理方式1、固定式分区2、动态分区分配——根据用户实际需要，动态的分配连续空间。拼接技术3、动态重定位分区分配——采用动态重定位技术的分区分配。紧凑技术4、

多重定位分区分配——可为一个作业分多个区。四、分区管理的算法1、首次适应算法：每个空白区按地址顺序链接在一起，表头指向第一个空白区。2、

循环首次适应算法：将空白区构成循环链表。表头指向当前开始查找的第一个空白区。3、

最佳适应算法：空白区按尺寸大小递增顺序构成队列。表头指向第一个空白区。五、对换技术（交换技术）

就是将主存中的信息以文件的形式写入到辅存，接着将指定的信息从辅存读入主存，并将控制转给它，让其在系统上运行。五、覆盖技术什么叫覆盖？什么叫覆盖段？什么叫覆盖区？覆盖技术示意图采用覆盖技术可以实现小空间运行大作业。六、分页存储器管理1、在分页存储管理方式中，一个进程的逻辑地址空间分成若干个大小相等的片，称为页面。内存空间也分成与页相同大小的存储块，并将进程的每一个页面离散地存储在内存的任一物理块中，建立相应的页表，由系统实现进程的正确运行。2、快表——为了提高地址变换速度，可在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲存储器，称为快表。地址变换机构为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构，分为基本的地址变换机构和具有快表的地址变换机构。地址变换机构的基本任务实现逻辑地址向物理地址的转换（页号->块号）地址变换借助页表来完成。分页系统的基本地址变换机构如图所示：页表始址页表长度页表寄存器0123页号块号逻辑地址页号页内地址>越界中断页表块号块内地址物理地址+1B四、地址变换例题1例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。页号块号02132136四、地址变换例题解：由题知逻辑地址为：物理地址为：（1）逻辑地址1011（十进制）的二进制表示为：

001111110011，由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中；其物理地址的二进制表示为：0101111110011，所以逻辑地址1011对应的物理地址为0BF3H。其地址转换图如后所示。页号2位位移量w10位块号b3位块内位移d10位

例：有一页式系统，其页表存放在主存中：①如果对主存的一次存取需要1.5μs,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间是多少?答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间

=1.5*2=3(μs)■增加快表后的存取访问时间

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)七、分段存储管理①在分段存储管理方式中，一个作业的地址空间分成若干个段，每一段定义了一组逻辑信息，则为每个段分配连续的分区，而进程中的各段可以离散地存储在内存中不同的分区中，建立相应的段表，由系统实现进程的正确运行。

②分页与分段存储管理的区别？八、段页式管理（1）

基本思想（2）地址变换机构

物理地址段表始址段表长度段表寄存器段号段内地址>逻辑地址+段号段长基址030k40k120k80k215k120k310k150k+地址变换机构-实现逻辑地址向物理地址的变换例1、在一个段式存储管理系统中，其段表为：段号内存起始地址段长

02105001235020210090313505904193895试求右表中逻辑地址对应的物理地址是什么？解：逻辑地址为：逻辑地址对应的物理地址为：210+430=640。逻辑地址因为段内地址120>段长90，所为该段为非法段。段号段内地址0430212004302120分段地址变换例题1由段表可知段号为3位，段内地址为10位。虚拟存储管理1、虚拟存储器的概念？

使用虚拟存储管理技术，用户将会感觉到系统的内存空间比实际内存大。系统的可用内存空间并非计算机系统中的实际物理内存，它包含物理内存及一部分磁盘空间。习惯上，人们把这种用户感觉上存在但实际上并不存在的内存称为虚拟内存。注意：

虚拟存储的特性交换性:对换性是指作业的运行过程中进行换进、换出，换进和换出能有效地提高内存利用率。多次性:多次性是指一个作业被分成多次调入内存运行，在作业运行时只需将当前要运行的那部分程序和数据装入内存即可；当要运行时尚未调入的那部分程序时，再将它调入。虚拟性虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。以CPU时间与外存空间换取昂贵内存空间，这是操作系统中的资源转换技术2、

请求分页存储管理方式基本思想

在请求分页存储管理方式中，不限定把进程的整个地址空间全部装入主存，而只要求把当前需要的一部分装入主存，由系统实现进程的正确运行，其它的页面当需要时才去调用。这样实现了主存的“扩充”。地址变换机构（见P170或P129）一、请求分页中的硬件支持1、页表机制（1）状态位P：指示该页是否已调入内存。（2）访问字段A：记录本页在一段时间内被访问的次数或最近未被访问的时间。（3）修改位M：表示该页在调入内存后是否被修改过。若修改过，则换出时需重写至外存。（4）外存地址：指出该页在外存上的地址。页号块号状态位P访问字段A修改位M外存地址供程序访问时参考供选择页面换出时参考供置换页面时参考供调入该页时参考(3)页面的管理：①页面调入策略●请求式调页●预先调页②页面置换算法：

●FIFO

●最近最久不用页面置换算法LRU3、系统抖动？4.7请求分页中的页面置换算法常用的页面置换算法：最佳置换算法：选择永远不再需要的页面或最长时间