uestc操作系统指导教案

操作系统辅导

汤子赢、哲风屏、汤小丹

1第一章操作系统引论

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

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

操作系统的目标●

设置操作系统的目的：

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

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

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

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

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

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

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

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

由OS实现的所有系统调用所构成的集合被人们称为程序接口或应用编程接口(ApplicationProgrammingInterface,API)。4●操作系统作为计算机系统资源管理者。1、处理机管理：分配和控制CPU。2、存储器管理：内存分配与回收。3、I/O设备管理：I/O设备的分配与操纵。4、文件管理：文件的存取、共享和保护。●操作系统用作扩充机器功能，使其便于使用，这种只安装了OS的机器又称为虚拟机。5

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

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

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

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

BC11答：多道程序运行时间关系图如下图所示：由图可计算出在多道程序运行下执行了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/O12分时操作系统(time-sharingsystem)——70年代中期至今

“分时”的含义：分时是指多个用户分享使用同一台计算机。多个程序分时共享硬件和软件资源。

分时(TimeSharing)操作系统的工作方式是：一台主机连接了若干个终端，每个终端有一个用户在使用。用户交互式地向系统提出命令请求，系统接受每个用户的命令，采用时间片轮转方式处理服务请求，并通过交互方式在终端上向用户显示结果。用户根据上步结果发出下道命。分时操作系统将CPU的时间划分成若干个片段，称为时间片。操作系统以时间片为单位，轮流为每个终端用户服务。每个用户轮流使用一个时间片而使每个用户并不感到有别的用户存在。

13

分时系统分时系统实现中的关键问题：及时接收：实现多个用户的信息及时接收。及时处理：及时控制作业的运行。

14分时系统的特征：多路性：同时有多个用户使用一台计算机，宏观上看是多个人同时使用一个CPU，微观上是多个人在不同时刻轮流使用CPU。独立性：用户感觉不到计算机为其他人服务，就像整个系统为他所独占。及时性：系统对用户提出的请求及时响应。交互性：用户根据系统响应结果进一步提出新请求(用户直接干预每一步)。“影响响应时间的若干因素:

Ti=NQ+To.s+Twap改善响应时间的方法采用重入码减少信息的对换量采用虚拟存储技术,减少信息对换量15实时系统●所谓实时系统：是计算机及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行。一、实时系统分为两类

1、实时控制系统

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

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

2、按截止时间来划分16

三、实时系统的特征

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

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

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

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

5、及时性：不同的系统要求不一样，控制对象必须在截止时间内完成。17操作系统的定义OS就是一个“大管家”，可以这样去定义：是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以及方便用户的程序的集合。18操作系统的基本特征现代OS的四个基本特征：1、并发2、共享3、虚拟4、异步并发是最重要的特征，其它特征都以并发为前提。19并发并发——并行性和并发性，并发执行的过程。

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

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

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

-从微观上看，任务共行是指单处理机系统中的任务并发（TaskConcurrency：即多个任务在单个处理机上交替运行）或多处理机系统中的任务并行（TaskParallelism：即多个任务在多个处理机上同时运行）。20共享所谓共享是指系统中的资源可供内存中多个并发执行的进程共同使用。1、互斥共享方式：

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

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

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

-从微观上看，资源共享是指多个任务可以交替互斥地使用系统中的某个资源。例如磁盘。22虚拟所谓虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。虚拟处理机：分时实现虚拟设备：SPOOLING技术虚拟存储器：虚拟存储管理实现23异步性异步性——是指进程以异步的方式执行，进程是以人们不可预知的速度向前推进。内存中的每个进程何时执行,何时暂停,以怎样的速度向前推进,每道程序总共需要多少时间才能完成等,都是不可预知的

24操作系统的结构设计

操作系统是一个大型系统软件，其结构已经历了四代的变革：整体式结构、核心结构和层次结构。

25整体式结构是指将整个操作系统作为一个整体运行操作系统时，不能响应其他中断。核心结构是指把操作系统分为外壳部分和核心部分。CPU在执行外壳部分时，可以响应其他中断；而在执行核心部分时，禁止响应中断。通常核心部分只是操作系统的一小部分，每次运行时间较短。核心部分通常包括进程控制和调度，进程的通信原语中断和中断处理，时钟处理，外设驱动等。层次结构是把操作系统的功能分层，每层有明确的功能，提供接口与上下层联系，上层软件调用下层软件提供的服务。对层次结构实现功能描述的另一种方法是把层次画为同心圆，内层的环比外层的环有较高的特权，当外层环的过程调用内层环的过程时要进行严格的检查。操作系统的核心和层次结构如图所示。2627第二章

进程的描述与控制

28一、

相关概念

1、

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

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

3、

程序的顺序的特征：

①

顺序性

②封闭性

③可再现性

4、程序的并发执行——是指两个或两个以上程序段在执行的时间上是重叠的，即使这种重叠只有一小部分，则称这些程序为共行执行。295、程序并发执行的特征：

①间断性

②失去封闭性

③不可再现性例2：若程序Pa、Pb和Pc单独执行时间分别Ta、Tb和Tc

，Ta=1小时，Tb=1.5小时，Tc=2小时，其中处理机工作时间分别为Ta=10分钟，Tb=15分钟，Tc=35分钟。如果采用多道程序设计的方法，让Ta、Tb和Tc并行工作，假定处理机利用率达到60%，另加20分钟系统开销，请问系统效率能提高百分之几？

30答：Ta、Tb和Tc并行工作共用CPU时间：（10+15+35）/60%=100Ta、Tb和Tc顺序工作共用CPU时间：（60+90+120）=270系统效率提高：（270-（100+20））/270=150/270=55.5%31二、

进程的基本概念

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

2、进程的基本特征

①

动态性

②

并发性

③

独立性

④

异步性

⑤

交往性

3、

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

334、

进程控制块——描述和控制进程运行，系统为每个进程定义的一个数据结构。5、进程控制块的组织方式进程描述信息处理机状态信息进程的调度信息进程的控制信息进程控制块是操作系统最重要的数据结构，是进程存在的唯一标志。进程控制表。6、进程的挂起状态

34三、

进程控制1、进程管理

进程图：表明进程的创建关系，创建的进程和被创建的进程可以并发执行。2、引起进程创建的原因

①用户登录：为终端用户建立进程。

②作业调度：选中的作业建立进程。

③提供服务：为用户提供的服务进程。例如：I/O进程等。④

应用请求：应用程序自己创建的进程。3、原语：由若干条指令构成，用于完成一定功能的一个过程。不允许被中断的程序段，不许并发执行。4、原子操作（原子性）：一个操作中的所有动作，要么全做，要么全不做。是一个不可分割的操作。35创建原语撤销原语阻塞原语唤醒原语挂起与激活原语36

5、

线程的基本概念（1）

线程：一个被调度和分派的基本单位并可独立运行的实体。（2）

线程分类：

①内核支持线程：依赖于内核进行控制和管理。

②用户级线程：在用户级创建、撤消和切换。（3）

在引入线程的OS中，则把线程作为调度和分派的基本单位，而把进程作为资源的拥有的基本单位。（4）

在同一进程中的线程切换不会引起进程切换。（5）在不同一进程中的线程切换会引起进程切换。

37

进程同步的基本概念1、

进程的相互制约

①间接相互制约——资源共享引起互斥关系

②

直接相互制约——相互合作引起进程同步2、

临界资源：一次仅允许一个进程使用的资源称为临界资源。（排他性资源）3、临界区：访问临界资源的那段代码称为临界区。4、

同步机制应遵循的准则：

①空闲让进——充分利用资源

②忙则等待——保证同步与互斥

③有限等待————防止陷入“死等”

④

让权等待——防止陷入“忙等”

38

…

进入控制临界区解除限制

…互斥的加锁实现：临界区有空闲和占有两个状态

whilelock=1doskiplock=1;

临界区

lock=0;

借助硬件来实现39信号量机制

1、

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

2、

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

3、

AND型信号量机制——防止系统出现不安全性。

①

AND型信号量机制的概念化（见P72-6行或P43）

②Swait操作（SP操作）：（见P72或P43）

③

Ssignal操作（SV操作）：（见P72或P43）

4、

信号量应用实例

①互斥②前趋③同步40信号量为一个整数，我们设这个信号量为：sem。很显然，我们规定在sem大于等于零的时候代表可供并发进程使用的资源实体数，sem小于零的时候，表示正在等待使用临界区的进程的个数。根据这个原则，在给信号量附初值的时候，我们显然就要设初值大于零。P原语操作的动作是：（1）sem减1；（2）若sem减1后仍大于或等于零，则进程继续执行；（3）若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。V原语操作的动作是：（1）sem加1；（2）若相加结果大于零，则进程继续执行；（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。需要提醒大家一点就是P,V操作对于每一个进程来说，都只能进行一次。而且必须成对使用。且在P,V愿语执行期间不允许有中断的发生。41一、经典信号量（整型信号量）P操作Wait(s):whiles<=0dono-op;s:=s-1;

V操作signal(s):S:=s+1;42二、记录型信号量让权等待结构体：整形变量，进程链表Typesemaphore=recordvalue:integer;l:listofprocess;endWait(s):vars:semaphore;begins.value:=s.value-1;ifs.value<0thenblock(s.l)End43Signal(s):vars:semaphore;begins.value:=s.value+1;ifs.value<=0thenwakeup(s.l)end44信号量操作：

1)初始化

2)P操作

a)S--

b)if(S<0)在Q队列中睡眠

else进入

3)V操作

a)S++

b)if(S<=0)唤醒一睡眠进程(等待队列中有进程在睡眠)

else继续

P操作可以理解为申请资源，V操作可以理解为释放资源，45

利用信号量和PV操作实现进程互斥的一般模型是：进程P1

进程P2

……

进程Pn……

……

……P（S）；

P（S）；

P（S）；临界区；

临界区；

临界区；V（S）；

V（S）；

V（S）；……

……

……

……

其中信号量S用于互斥，初值为1。

使用PV操作实现进程互斥时应该注意的是：（1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。（2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。

46

利用信号量和PV操作实现进程同步PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。

使用PV操作实现进程同步时应该注意的是：

（1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。

（2）信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。

（3）同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。47【例1】生产者-消费者问题在多道程序环境下，进程同步是一个十分重要又令人感兴趣的问题，而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题，深入地分析和透彻地理解这个例子，对于全面解决操作系统内的同步、互斥问题将有很大帮助。（1）一个生产者，一个消费者，公用一个缓冲区。定义两个同步信号量：empty——表示缓冲区是否为空，初值为1。full——表示缓冲区中是否为满，初值为0。48生产者进程while(TRUE){

生产一个产品;

P(empty);

产品送往Buffer;

V(full);

}消费者进程while(TRUE){

P(full);

从Buffer取出一个产品;

V(empty);

消费该产品;

}49（2）一个生产者，一个消费者，公用n个环形缓冲区。定义两个同步信号量：empty——表示缓冲区是否为空，初值为n。full——表示缓冲区中是否为满，初值为0。

设缓冲区的编号为1～n1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。50生产者进程while(TRUE){

生产一个产品;

P(empty);

产品送往buffer(in);

in=(in+1)modn;

V(full);

}消费者进程while(TRUE){P(full);

从buffer(out)中取出产品;

out=(out+1)modn;

V(empty);

消费该产品;

}

51（3）一组生产者，一组消费者，公用n个环形缓冲区

在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。定义四个信号量：empty——表示缓冲区是否为空，初值为n。full——表示缓冲区中是否为满，初值为0。mutex1——生产者之间的互斥信号量，初值为1。mutex2——消费者之间的互斥信号量，初值为1。

设缓冲区的编号为1～n1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。

52生产者进程while(TRUE){

生产一个产品;

P(empty);

P(mutex1);

产品送往buffer(in);

in=(in+1)modn;

V(mutex1);

V(full);

}消费者进程while(TRUE){P(full);

P(mutex2);

从buffer(out)中取出产品;

out=(out+1)modn;

V(mutex2);

V(empty);

消费该产品;

}

53需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。

54【例2】桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。分析在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：55intS＝1;intSa＝0;intSo＝0;

main()

{

cobegin

father();

/*父亲进程*/

son();

/*儿子进程*/

daughter();

/*女儿进程*/

coend

}

father()

{

while(1)

{

P(S);

将水果放入盘中;

if（放入的是桔子）V(So);

else

V(Sa);

}

}

56son()

{

while(1)

{

P(So);

从盘中取出桔子;

V(S);

吃桔子;

}

}

daughter()

{

while(1)

{

P(Sa);

从盘中取出苹果;

V(S);

吃苹果;

}

}57四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：

（1）应定义的信号量及初值：

。

（2）在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作：

A()

B()

C()

D()

{

{

{

{

[1];

[3];

[5];

[7];

readF;

readF;

readF;

readF;

[2];

[4];

[6];

[8];

}

}

}

}

58（1）定义二个信号量S1、S2，初值均为1，即：S1=1，S2=1。其中进程A和C使用信号量S1，进程B和D使用信号量S2。（2）从[1]到[8]分别为：P(S1)V(S1)P(S2)V(S2)P(S1)V(S1)P(S2)V(S2)

59读者-写者问题-问题描述一个数据文件或记录/数据对象，可以被多个进程共享。其中有些进程要求读；而另一些进程要求对数据对象进行写或修改。允许多个读进程同时读一个共享对象，但不允许写进程与读进程或其他写进程同时访问共享对象。所谓读者—写着问题(theReader-WriterProblem)是指保证写进程必须与其他进程互斥地访问共享对象的同步问题。该问题首先在1971年又Courtois等人解决。

60为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。61读者-写者问题可描述如下：varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;62哲学家进餐问题-问题描述有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时便试图取用其左、右靠他最近的筷子，只有当他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下varchopstick:array[0..4]ofsemaphore;

63所有信号量均被初始化为1，第i位哲学家的活动可描述为：repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5]);think;untilfalse;

64上述解法可保证不会有两个相邻的哲学家同时进餐/互斥使用中间的筷子，但有引起死锁的可能。可采取以下几种解决方法：(1)至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。65在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。66三、AND型信号量机制死锁67四、信号量集机制68管程机制信号量机制是一种方便而有效的进程同步机制，但每个要访问临界资源的进程须自备wait和signal操作。这样不仅给系统管理造成麻烦，而且还会因同步操作使用不当而导致死锁，甚至产生与时间有关的错误，例如：1、颠倒wait和signal操作导致临界资源被同时访问；2、signal误写为wait操作，导致任何进程无法访问临界资源，发生死锁；3、遗漏wait操作会导致多个进程同时访问临界资源，遗漏signal则导致其他进程无法进入临界区。基于以上情况，1971年DIjkstra提出了秘书“进程”机制。1973年Hansan和Hoare又讲“秘书”进程思想发展为“管程”概念，把并发进程间的同步操作分别集中在相应的管程中。

69管程由三部分组成：①局部于管程的共享变量说明；②对该数据结构进行操作的一组过程；③对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。7071条件变量在管程机制中，引起进程等待的原因可能很多，为了区别他们，有引入了条件变量condition。管程中对每个条件变量，都须予以说明，其形式为：Varx,y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：nonbusy:condition。此时，wait原语应改为nonbusy.wait，相应地，signal应改为nonbusy.signal。应当指出，X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s:=s+1操作，因而总会改变信号量的状态。72如果有进程Q处于阻塞状态，当进程P执行了X.signal操作后，怎样决定由哪个进行执行，哪个等待，可采用下述两种方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件。(2)Q等待，直至P离开管程或等待另一条件。采用哪种处理方式，当然是各执一词。但是Hansan却采用了第一种处理方式。73利用管程解决PC问题-基本思想在利用管程方法来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为Proclucer-Consumer，或简称为PC。其中包括两个过程：(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品，消费者应等待74进程通信进程通信的类型：低级通信和高级通信

(1)高级通信方式：

①共享存储器系统：共享数据结构、共享存储器区通信方式

②消息传递系统：直接通信方式——通过收发原语间接通信方式——通过信箱实现信息交换

③管道通信（2）管道通信具有三方面的协调能力：

①双方同时存在

②

同步关系

③

互斥使用管道75第三章

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

1、高级调度

2、

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

3、

中级调度76二、

面向用户的准则1、

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

响应时间快3、

截止时间的保证4、

优先权准则

77三、面向系统的准则1、

系统的吞吐量2、

CPU的利用率好3、

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

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

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

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

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

①静态优先权

②动态优先权795、

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

RP=1+等待时间/服务时间6、多级队列调度算法：例如，前台、后台7、多级反馈队列调度算法（见P108或P80）

实时系统的调度算法

在实时系统中，广泛采用抢占式调度方式80

死锁的基本概念1、

何谓死锁？（见P119或P90）2、

产生死锁原因：

①

竞争资源

②

推进顺序不当3、

产生死锁的必要条件

①互斥

②请求和保持

③不剥夺

④环路等待条件

81

4、

处理死锁的基本方法

①

预防死锁：设置某些限制条件，破坏四个条件。

②

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

③

检测死锁：设置检查机构，定时检查系统是否出现死锁。

④解除死锁：已出现死锁。

82例.

假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示。在此基础上P0进程发出请求向量{1，2，0}，问系统是否能将资源分配给P0进程？如能为P0分配资源则给出安全系列，否则给出解除死锁的方法。

进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122

P2902302600

P3222211011

P4433002431

83安全P3(1)->p1(2)->p0(3)->p2(4)->p4(5)

进程MaxABCAllocationABCNeedABCAvailableABCP0753130

62312(3)753P1321200122(2)623

P2902302600

(4)1055P3222211011(1)

423P4433002431(5)1057

84第四章

存储器管理

85

一、程序的装入

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

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

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

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

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

1、

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

2、

装入时动态链接——编译后的目标模块，是在装入内存时，边装入，边链接的。

3、运行时动态链接——将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，再由操作系统去找到该模块，将它装入内存，并把它链接到调用者模块上。

4、静态链接需要共享目标模块的拷贝，而动态链接不需要共享目标模块的拷贝。87三、连续分配存储管理方式

1、

固定式分区

2、

动态分区分配——根据用户实际需要，动态的分配连续空间。

l拼接技术

3、

动态重定位分区分配——采用动态重定位技术的分区分配。

l

紧凑技术88四、分区管理的算法1、

首次适应算法：每个空白区按地址顺序链接在一起，表头指向第一个空白区。2、

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

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

（交换技术）

就是将主存中的信息以文件的形式写入到辅存，接着将指定的信息从辅存读入主存，并将控制转给它，让其在系统上运行。90六、分页存储器管理1、在分页存储管理方式中，一个进程的逻辑地址空间分成若干个大小相等的片，称为页面。内存空间也分成与页相同大小的存储块，并将进程的每一个页面离散地存储在内存的任一物理块中，建立相应的页表，由系统实现进程的正确运行。2、快表——为了提高地址变换速度，可在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲存储器，称为快表。91

例：有一页式系统，其页表存放在主存中：①如果对主存的一次存取需要1.5μs,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,

试问此时的存取时间是多少?92答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间

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

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

②分页与分段存储管理的区别？答：P160或P12194八、段页式管理（1）

基本思想（见P162或P123）（2）地址变换机构（见P164或P124）95虚拟存储管理1、

虚拟存储器的概念？

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

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

在请求分页存储管理方式中，不限定把进程的整个地址空间全部装入主存，而只要求把当前需要的一部分装入主存，由系统实现进程的正确运行，其它的页面当需要时才去调用。这样实现了主存的“扩充”。地址变换机构（见P170或P129）页面的管理：

①页面调入策略

●请求式调页

●预先调页97②页面置换算法：

●FIFO

例如,P175或P134

●最近最久不用页面置换算法LRU

例如,(P176或P135)●简单的Clock置换算法例如,(P178或P136)3、系统抖动？（P183-18行）983、

请求分段存储管理方式（1）

基本思想

在请求分段存储管理方式中，把作业的所有分段的副本保存在辅存中，当其运行时，只要求把当前需要的一段或数段装入主存，其它的段当需要时才装入，由系统实现进程的正确运行。这样实现了主存的“扩充”。（2）地址变换机构（见P186或P139）

●分段保护：越界检查（段长值）存取控制检查99例1.页式系统中地址结构长度为24位，页面大小为1K，作业地址空间为5K，该作业的各页依次存放在2,9,7,5,11号物理块中,相对地址2000处有一条指令Store1,4500，请给出该作业的页表，该指令的物理单元和数据存放的物理单元。页号帧号021927354112000对应为111，1101，0000物理单元为：100111，1101，0000即：1024×9＋976＝101924500对应为：1024×11+404100例2.在一个请求页式存储系统中，一个程序的页面走向为4，3，2，1，4，3，5，4，3，2,1，5，并采用LRU页面置换算法。假设分配给该程序的存储块数M分别为3和4时，求出在防问过程中发生的缺页次数和缺率，比较所得结果，从中得到什么启发？101第五章

设备管理一、

I/O系统的组成

1、I/O系统的结构102（1）

设备①独占设备——在一段时间内只允许一个用户访问的设备。②共享设备——在一段时间内允许多个用户访问的设备。③

虚拟设备——将一台独占物理设备变换为若干台逻辑设备。103（2）设备控制器①是CPU与I/O设备之间的接口，它接收从CPU发来的命令，并控制I/O设备工作。②设备控制器是可编址设备。当用于控制多台设备时，则具有多个地址。104（3）通道

●通道控制方式的引入①DMA方式显著地减少了CPU的干预。②当CPU要完成一组相关的读（或写）操作及有关控制时，只需向I/O通道发送一条I／O指令。③通道接到该指令后，通过执行通道程序便可完成CPU指定的I／O任务。④可实现CPU、通道和I／O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。⑤而当我们需要一次去读多个数据块且将它们分别传送到不同的内存区域，或者相反时；则须由CPU分别发出多条I／O指令及进行多次中断处理，才能完成。105●通道分类：①字节多路通道106②数组选择通道——按数组方式进行数据传送，但在一段时间内只能为一台设备占用，执行一道通道程序。③数组多路通道——按数组方式进行数据传送，但能为多台设备占用，高速的进行数据传送。107二、

I/O控制方式1、程序I/O方式（查询方式）(P203或P151）2、中断驱动方式(P203或P152）3、DMA方式(P203或P153）4、I/O通道控制方式方式(P203或P154）

通道是通过执行通道程序，并与设备控制器共同实现对I／O设备的控制的。通道程序是由一系列通道指令（或称为通道命令）所构成的。通道又称为特殊的处理机。108三、

缓冲管理●

引入缓冲原因（见P207或P155）（1）缓和CPU与I／O设备间速度不匹配的矛盾。

（2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制。（3）提高CPU和I／O设备之间的并行性。

例如：

单缓冲、

双缓冲、

循环缓冲、

缓冲池缓冲技术是以空间换取时间，而且只能在设备使用不均衡时起到平滑作用。109

四、

设备分配设备管理是通过一些数据结构来实现对其设备进行管理和控制的。1。

设备控制表、通道控制表、系统设备表、控制器控制表2、设备分配中应考虑的若干因素（1）设备的固有属性：独享设备、共享设备、虚拟设备

（2）设备的分配算法：FIFO、优先级高者优先（3）设备分配中的安全性3、设备固有属性不同，其分配算法不同4、SPOOLING技术可将一台物理设备虚拟为多台逻辑设备，可为多个用户所共享。

SPOOLing技术的核心思想是：在快速辅助存储设备中建立I/O缓冲区用于缓存从慢速输入设备流入内存的数据或缓存从内存流向慢速输出设备的数据。110五、设备处理1、设备处理程序又称为设备驱动程序，它是I/O进程与设备控制器之间的通信程序。

①初始化I/O设备

②

设备与进程之间的数据传送

③

当数据传完之后，将产生中断信号将它换醒，进入中断处理过程。2、中断处理过程（见P224或P171）3、用户请求设备使用的是逻辑设备名。由系统通过逻辑设备表实现逻辑设备到物理设备的映射。当更换物理设备时，用户的程序不用改，仅修改逻辑设备表。111磁盘存储器管理一、

早期磁盘调度算法

1、

先来先服务（见P261或P174）

2、

最短寻道时间优先（见P261或P174

3、

扫描法（见P262或P175）

4、

循环扫描法（见P262或P175）

112第六章

文件系统113

一、

文件和文件系统的基本概念

1、

数据项——>记录——>文件（见P228或P182图）

2、

文件系统模型（见P229或P184图）

3、

文件的操作（见P231或P185）

二、文件逻辑结构

1、

顺序文件（见P234或P187）

优点：可以快速实现批量存取，可存储在磁带上缺点：增删困难

2、

索引文件（见P235或P189）

优点：实现直接存取、快速缺点：增加空间开销

114三、

外存分配方法1.

连续分配——将文件信息存放在连续编号的物理块中。（见P264图9-6或P192）

优点：结构简单，存取速度快。

缺点：长度事先确定，随后不允许增加长度。2、

链接分配——将文件信息存放在非连续编号的物理块中。(见P265图9-7或P194）

优点：插入、删除方便，文件长度可变。

缺点：查找困难。3、

索引分配（见P267、图9-10或P195）

优点：可以随机存取。

缺点：增加空间的开销。115四、

目录管理

1、

对文件目录管理要求（见P236或P198）

2、

文件控制块与文件目录（见P237或P198）

3、

单级文件目录（见P239或P201）

缺点：查找速度慢、不允许重名、不便于实现文件共享

4、

两级目录和多级目录（见P240或P201）

l

当前目录——工作目录

l

优点：

①检查速度快

②

不同目录可以重名

③

不同用户可使用不同名字，来访问系统中的同一个共享文件。116●索引结点的引入在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（即其中的文件名与指定要查找的文件名相匹配）时，才需从该目录项中读出该文件的物理地址。而其它一些对该文件进行描述的信息，在检索目录时一概不用，显然，这些信息在检索目录时，不需调入内存。为此，在有的系统中，如UNIX系统，便采用了把文件名与文件描述信息分开的办法，亦即，使文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点。在文件目录中的每个目录项，仅由文件名和指向该文件所对应的i结点的指针所构成。

117

五、空闲存储空间的管理方法

1、空闲表法（见P270或P205）

2、空闲链表法（见P271或P206）

3、位示图法（见P271或P206）

4、成组链接法（见P272、或P207）118第七章

操作系统接口

119

用户与操作系统的接口

操作系统

用户处理结果输出返回命令接口图形接口程序接口120

●用户接口可以多种形式呈现在用户面前：①一种是联机命令形式，直接提供给用户在终端上使用；②一种是系统调用形式，提供给用户在编程时使用。人们通常把上述两种形式分别称为联机命令接口和程序接口。一、

命令接口

命令接口由

命令解释程序对用户键入的命令进行解释，并转入相应的命令处理程序去执行。二、

程序接口

1、系统调用——就是用户在程序中调用操作系统所提供的一些子功能。

2、系统调用在本质上是应用程序请求OS内核完成某功能时的一种过程调用，但它是一种特殊的过程调用，它与一般的过程调用有下述几方面的明显差别：

121（1）运行在不同的系统状态。一般的过程调用，其调用程序和被调用程序都运行在相同的状态——系统态或用户态；而系统调用与一般调用的最大区别就在于：调用程序是运行在用户态，而被调用程序是运行在系统态。（2）通过软中断进入。由于一般的过程调用并不涉及到系统状态的转换，故可直接由调用过程转向被调用过程。但在运行系统调用时，由于调用和被调用过程是工作在不同的系统状态，因而不允许由调用过程直接转向被调用过程。通常都是通过软中断机制（既访管指令），先由用户态转换为系统态，经核心分析后，才能转向相应的系统调用处理子程序。122（3）返回问题。在采用了抢占式（剥夺）调度方式的系统中，在被调用过程执行完后，要对系统中所有要求运行的进程做优先权分析。当调用进程仍具有最高优先级时，才返回到调用进程继续执行；否则，将引起重新调度，以便让优先权最高的进程优先执行。此时，将把调用进程放入就绪队列。（4）嵌套调用。系统调用也可以嵌套进行，即在一个被调用过程的执行期间，还可以利用系统调用命令去调用另一个系统调用。当然，每个系统对嵌套调用的深度都有一定的限制，例如最大深度为6。

123三、

图形用户接口

①窗口是作为用户与应用程序之间的交互接口

②应用程序可通过窗口向用户展示系统所提供的各种服务及其需要用户输入的信息。

③用户可通过窗口去查看和操作应用程序或文档。

124研究生入学试题分析125

2000年操作系统入学试题

一、

单选题（每小题1分，共7分）1、线程是进程的实体，意味着（）

①线程在进程中是唯一的

②线程可以使用进程中的资源

③线程在运行中不能中断

④在同一进程中的多个线程具有不同的地址空间

2、检测死锁的算法是在（）

①程序中申请资源时使用②死锁出现之后使用

③死锁即将出现时使用 ④定时检查系统状态时使用

3、在下列问题中，哪一个不是设备中应考虑的问题（）

①设备的固有属性 ②与设备无关性

③安全性 ④及时性1264、在下列哪一个不是外存分配方式（）

①连续分配 ②链接分配

③互斥分配 ④索引分配5、联想存储器就是（）

①快表 ②页表 ③段表 ④内存

6、磁盘为共享设备的主要原因是（）

①多个用户可同时访问磁盘

②磁盘空间可让多个用户共享

③磁盘可支持SPOOLING技术

④磁盘有多个磁头7、指出以下非临界资源（）

①变量②数据结构

③队列④纯代码127二、填空题（每小题1分，共6分）1、用户与操作系统的接口是：____和_______________。2、多处理机有两种结构：_____和________.3、I/O控制方式________，____和________。4、产生死锁的原因：______和_________。5、文件保护的方法有：_______，_________和___________。6、用于磁盘的主要调度算法有：__________，____________和____________。128

三、

判断改错题（每小题2分，共16分）

1、（ ）缓冲技术是以空间换时间，而且只能在设备使用均衡时起到平滑作用。

2、（ ）动态重定位与装入时动态链接在概念上是相同的。

3、（ ）在分时系统中采用虚拟存储技术可以改善响应时间。

4、（ ）在现代的分时系统中，逻辑处理机隐含了虚拟处理机的功能。

5、（ ）独享设备与共享设备的属性不同，其共享方式也不同。129

6、（ ）采用AND型信号量机制是为了防止系统的不安全。

7、（ ）如果一个站点既可以作为客户，又可以作为服务器向其它站点提供服务，称为客户/服务器模式。

8、（ ）设备处理程序是I/O进程与设备控制器之间的通信程序。

130四、问答题（每小题7分，共21分）1、

为什么在页式存储管理中实现程序共享时，必须对共享程序给出相同的页号，而段式存储管理系统中实现程序共享时，共享段的段号是否一定要相同？如相同，为什么相同？如不相同，为什么不相同？131进程到达就绪队列的时间执行时间P118P224P339P4452、

假定一个操作系统的进程调度采用抢占式短进程优先调度策略（单CPU），系统中各进程到达的时间如下表所示。请给出各进程的调度次序，并计算平均周转时间和平均代权周转时间。注：表中的时间均为基本单位时间。1320102030p1p2p3p418-1=176-2=427-3=2411-4=7133

2001年操作系统入学试题一、单项选择题（每小题1分，共10分）

1.进程被阻塞以后，代表进程在阻塞队列的是它的(

)

①文件控制块②进程控制块

③作业控制块④设备控制块

2.在以下哪种状态下，作业已获得虚处理机。（） ①提交状态