计算机操作系统期末复习资料(共24页)

1、精选优质文档-倾情为你奉上第一章什么是OS，它在计算机系统中处在什么位置？加载在硬件上的第一层软件，是硬件功能的首次延伸；是系统资源的管理机构；是人、机之间的接口。OS的发展过程-几类典型操作系统(多道批处理、分时、实时)，每类操作系统的原理、特征(优缺点)多道批处理系统：原理： 20世纪60年代中期引入多道程序设计技术，由此形成了多道批处理系统。在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。特征（优缺点）：（1）资源利用率高（2）系统吞吐量大（3）平均周转时

2、间长（4）无交互能力分时系统：原理： 分时系统是指在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。特征（优缺点）：（1）多路性（2）独立性（3）及时性（4）交互性实时系统：原理： 实时系统是指系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。特征（优缺点）：（1）多路性（2）独立性（3）及时性（4）交互性（5）可靠性OS的基本特性(并发、共享、虚拟、异步)-其中“并发”是最重要的特性并发性、共享性、虚拟性和异步性四个基本特征；最基本的特征是并发性。 OS的主要功能-资

3、源管理器和用户接口资源管理功能：处理机管理存储器管理设备管理文件管理操作系统和用户之间的接口：用户接口：联机用户接口，脱机用户接口和图形用户接口程序接口：该接口是为用户程序在执行中访问系统资源而设置的，它是由一组系统调用组成。 试说明推动多道批处理系统形成和发展的主要动力是什么？主要动力来源于四个方面的社会需求与技术发展：（1）不断提高计算机资源的利用率；（2）方便用户；（3）器件的不断更新换代；（4）计算机体系结构的不断发展。 第二章 进程的概念，进程与程序(作业)的区别进程是操作系统结构的基础；是一个正在执行的程序；计算机中正在运行的程序实例；可以分配给处理器并由处理器执行的一个实体。进程

4、实体：为使程序（含数据）能独立运行，应为之配置一进程控制块，即PCB；而由程序段、相关的数据段和PCB三个部分便构成了进程实体。进程的实质是进程实体的一次执行过程。进程和程序区别：（1）进程是一个动态概念，强调执行的过程，每个进程中包含了程序段和数据段两个部分，以及进程控制块PCB； 而程序是一个静态概念，程序是指令的有序集合，无执行含义；（2）进程具有并行特征（独立性，异步性），程序则没有；（3）一个进程可以执行多个程序（如Linux中通过exec调用），同一程序的多次执行将产生多个不同的进程。同一个程序的一次执行也可产生多个进程（如在程序中多次调用Linux中的fork）。进程和作业的区别

5、在于： 一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成某项任务，而要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成四个阶段。而进程是已提交完毕的程序所执行过程的描述，是资源分配的基本单位。其主要区别关系如下：（1）作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行；而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中；（2）一个作业可由多个进程组成，且必须至少由一个进程组成，但反过来不成立；（3）

6、作业的概念主要用在批处理系统中，像UNIX这样的分时系统中，则没有作业的概念；而进程的概念则用在几乎所有的多道程序系统中。 什么是PCB，PCB包含的主要信息，PCB的作用为了描述和控制进程的运行，系统为每个进程定义了一个数据结构进程控制块PCB（Process Control Block）。PCB中主要包括下述四方面的信息：进程标识符：内部标识符，外部标识符；处理机状态；进程调度信息；进程控制信息。PCB的作用： PCB是系统只为每个进程定义的一个数据结构，是为了使程序（含数据）能独立运行，为之配置的一进程控制块； PCB、程序段和相关的数据段三部分构成了进程实体，创建进程，实质上是创建进程

7、和实体中的PCB，而撤销进程，实质上是撤销进程的PCB；PCB是为了保证程序的并发执行； PCB使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。进程的3种基本状态，状态间的转换以及引起状态转换的原因进程的三种基本状态：就绪状态，执行状态，阻塞状态还存在两种比较常见的进程状态，即创建状态和终止状态创建就绪：在当前系统的性能和内存容量均允许的情况下，完成对进程创建的必要操作， 相应的系统进程将进程的状态转换成活动就绪状态执行终止：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结， 或是被其他有终止权的进程所

8、终结，进程即进终止状态(1) 就绪执行处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。(2) 执行就绪处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。（时间片用完）(3) 执行阻塞正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。（I/O请求）(4) 阻塞就绪 处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。（I/O完成）什么是临界资源临界资源是指每次仅允许一个进程访问的资源。 进程间的两种相互制约关系（-同步、互斥-）的概念(是进

9、程间的低级通信）进程同步（直接相互制约关系）：它主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调是必不可少的。举例：有输入进程A 通过单缓冲向进程B 提供数据。当缓冲空时，计算进程因不能获得所需数据而阻塞，当进程A 把数据输入缓冲区后，便唤醒进程B；反之，当缓冲区已满时，进程A 因没有缓冲区放数据而阻塞，进程B 将缓冲区数据取走后便唤醒A。进程互斥（间接相互制约关系）：它主要源于资源共享，是进程之间的间接制约关系。在多道系统中，每次只允许一个进程访问的资源称为临界资源，进程互斥就是保证每次只有一个进程使用临

10、界资源。举例：有两进程A 和B，如果A 提出打印请求，系统已把唯一的一台打印机分配给了进程B，则进程A只能阻塞；一旦B释放打印机，A才由阻塞改为就绪。 什么是信号量 信号量是Dijkstra提出的用于解决进程同步的有效工具。信号量是一个数据结构以及对其的操作。除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。两个语句在执行到一半的时候不能被中断。 什么是P操作、什么是V操作(P、V操作的处理流程，以记录型信号量为例）专心-专注-专业P（S）：wait(S)每次wait操作，意味着进程请求一个单位的该类资源，使系统可供分配的该类资源数减少一个。 将信号量S的值减1，

11、即S.value:=S.value-1； 当S.value<0时，表示该类资源分配完毕，进程调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表中。V（S）：signal(S)每次signal操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个 将信号量S的值加1，即S.value:=S.value+1； 如果S.value<=0，表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将链表中的第一个等待进程唤醒。用信号量和P、V操作机制实现互斥和同步的方法，信号量取值的含义利用信号量和PV操作实现进程互斥时应该注意的是：（1

12、）每个程序中用户实现互斥的P,V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。（2）P,V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量得初值一般为1其中信号量S用于互斥，初值为1。利用信号量和PV操作实现进程同步PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。使用PV操作实现进程同步时应该注意的是：（1）分析进程间的制约关系，确定信

13、号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，那些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置那些信号量。（2）信号量的初值与相应资源的数量有关，也与P,V操作在程序代码中出现的位置有关。（3）同一信号量的P,V操作要成对出现，但他们分别在不同的进程代码中。什么是进程的(高级)通信，类型进程通信，是指进程之间的信息交换，其所交换的信息量少者是一个状态或数值，多者则是成千上万个字节。高级进程通信，是指用户可直接利用操作系统所提供的一组通信命令高效地传送大量数据的一种通信方式。三大类：（1）共享存储器系统a、 基于共享数据结构的通信方式b、基于共享存储区得通信方

14、式（2）消息传递系统（3）管道通信系统。 消息传递通信的两种实现方法（1）直接通信方式发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。（2）间接通信方式进程之间的通信需要通过作为共享数据结构的实体。 在操作系统为什么引入进程的概念？它会产生什么样的影响？ 为了使程序在多道程序环境下并发执行。并对并发执行的程序加以控制和描述，在操作系统为什么引入进程的概念。影响：使程序的并发执行得意实行。 为什么说PCB是进程存在的唯一标志？因为： 在调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存地址，找到其程序和数据；进程在执行

15、过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也都需要访问PCB：当进程由于某种原因而暂停执行时，又需将器断点的处理机环境保存在PCB中。可见，在进程的整个生命期中，系统总是通过PCB对进程进行控制的，亦即系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的。所以PCB是进程存在的唯一标志。线程的概念和属性线程：是"进程"中某个单一顺序的控制流，也被称为轻量进程（lightweight processes）。线程具有以下属性：1）轻型实体。2）独立调度和分派的基本单位。3）可并发执行。4）共享进程资源。 试写出相应的程序来描述图所示的前驱图。进程管理相

16、关内容进程管理相关内容第一个图：Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0, 0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); S6

17、; signal(h); end; begin wait(f); wait(g); wait(h); S7; end; parend end第二个图： Var a, b, c, d, e, f, g, h, i, j;semaphore:= 0, 0, 0, 0, 0, 0, 0,0,0, 0;begin parbeginbegin S1; signal(a); signal(b); end;begin wait(a); S2; signal(c); signal(d); end;begin wait(b); S3; signal(e); signal(f); end;begin wait(c

18、); S4; signal(g); end;begin wait(d); S5; signal(h); end;begin wait(e); S6; signal(i); end;begin wait(f); S7; signal(j); end;begin wait(g);wait(h); wait(i); wait(j); S8; end;parend end在生产者-消费者问题中，如果将两个wait操作即wait(full)和wait(mutex)互换位置，或者将signal(mutex)与signal（full）互换位置，结果会如何？var mutex,empty,full: sema

19、phore:=1,n,0;buffer: array0,.,n-1 of item;in,out: integer:=0,0;beginparbeginproducer: duce an item in nextp;.wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1) mod n;/* * */signal(full);signal(mutex);/* * */until false;endconsumer: beginrepeat/* * */wait(mutex);wait(full);/* * */nex

20、tc:=buffer(out);out:=(out+1) mod n;signal(mutex);signal(empty);consume the item in nextc;until false;endparendenda. wait(full)和wait(mutex)互换位置后，因为mutex在这儿是全局变量，执行完wait(mutex)，则mutex赋值为0，倘若full也为0，则该生产者进程就会转入进程链表进行等待，而生产者进程会因全局变量mutex为0而进行等待，使full始终为0，这样就形成了死锁.b. 而signal(mutex)与signal(full)互换位置后，从逻辑上

21、来说应该是一样的. 试利用记录性信号量写出一个不会出现死锁的哲学家进餐问题的算法。规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子，等一段时间再重复整个过程。分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子如此这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。(2) 描述一种没有人饿死（永远拿不到筷子）算法。考虑了四种实现的方式（A、B、C、D）：A原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家

22、能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。伪码：semaphore chopstick5=1，1，1，1，1;semaphore room=4;void philosopher(int i)while(true)think();wait(room); /请求进入房间进餐wait(chopsticki); /请求左手边的筷子wait(chopsti

23、ck(i+1)%5); /请求右手边的筷子eat();signal(chopstick(i+1)%5); /释放右手边的筷子signal(chopsticki); /释放左手边的筷子signal(room); /退出房间释放信号量roomB原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足FIFO 的要求，因此不会出现饥饿的情形。伪码：semaphore

24、chopstick5=1，1，1，1，1;void philosopher(int I)while(true)think();Swait(chopstick(I+1)%5,chopstickI);eat();Ssignal(chopstick(I+1)%5,chopstickI);方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。伪码：semaphore mutex = 1 ;semaphore chopstick5=1，1，1，1，1;void philosopher(int I)while(

25、true)think();wait(mutex);wait(chopstick(I+1)%5);wait(chopstickI);signal(mutex);eat();signal(chopstick(I+1)%5);signal(chopstickI); 第三章进程调度的功能：1）保存处理剂的现场信息；2）按某种算法选取进程；3）把处理机分配给进程。对于本章内的基本调度算法：算法思想、就绪队列的组织、是抢占还是非抢占FCFS先来先服务调度算法算法思想：当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放

26、入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪对垒中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS是非抢占式的调度算法。短作业（进程）优先调度算法算法思想：短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先（SPF）调度算法则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。短作业调度算法是非抢占式的调度算法。非抢占式优先权调度算法和抢占式优先权调度算

27、法算法思想：非抢占式优先权调度算法：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进程。抢占式优先权调度算法：系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。静态优先权和动态优先权算法思想：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的。高

28、响应比优先调度算法算法思想：为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然后寄回分配到处理机。该优先权的变化规律可描述为：优先权=（等待时间+要求服务时间）/ 要求服务事件基于时间片的轮转调度算法算法思想：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。多级反馈队列调度算法算法思想： 设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之。 当一个新进程进入内存后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。如果一个时间片后进

29、程尚未完成，调度程序便将该进程转入第二个队列的末尾，再同样地按FCFS原则等待调度执行。当一个长作业从第一个队列一次降到第n个队列后，在第n队列中便采取按时间片轮转的方式运行。 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。 典型的动态优先权调度调度算法：高响应比优先度调度算法；典型的实时调度算法：最低松弛度优先调度算法；时间片轮转法中，时间片取值的影响时间片取值的影响： 如果选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销；反之，如果选择太长的时间片，使得每个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，

30、无法满足交互式用户的需求。如何确定时间片的大小： 时间片应略大于一次典型的交互需要的时间。这样可使大多数进程在一个时间片内完成。一般应考虑三个因素：系统对相应时间的要求、就绪队列中进程的数目和系统的处理能力。 什么是死锁，死锁产生的原因和必要条件 所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。 产生死锁的原因：（1）竞争资源。（2）进程间推进顺序非法。 产生死锁的必要条件：1）互斥条件；2）请求和保持条件；3）不剥夺条件；4）环路等待条件。什么是安全状态、不安全状态，它与死锁间的关系 所谓安全状态，只系统能按某种进

31、程顺序（P1,P2,···,Pn）（称<P1,P2,···,Pn>序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的完成。 如果系统无法找到这样一个安全序列，则称系统处于不安全状态。死锁的预防、避免、检测与解除的含义1） 预防死锁。这是一种较简单的和直观的事先预防的方法。该方法是通过设置某些限制条件， 去破坏产生死锁的四个必要条件，来预防发生死锁。2） 避免死锁。该方法同样是属于事先预防的策略，但他并不须事先采取各种限制措施去破坏产生死锁的四个 必要条件，而是在资源的动

32、态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁。3） 检测死锁。这种方法并不须事先采取任何限制措施，也不必检查系统是否已经进入不安全区， 而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测死锁的发生， 并精确地确定与死锁有关的进程资源；然后，采取适当措施，从系统中将已发生的死锁清除掉。4）解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。死锁的避免-避免死锁的银行家算法，数据结构，算法思想银行家算法中的数据结构： 可利用资源向量 Available 最大需求矩阵Max 分配矩阵 Allocation 需求

33、矩阵 Need三个矩阵间存在下述关系：Needpi,j = Maxi,j Allocationi,j算法思想：（1）如果Request ij <= Needi,j，便转向步骤（2）； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Request ij <= Availablej，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的值：Availablej:=Availablej Request ij;Allocationi,j:=Allocationi,j + Request ij;Needi,j:

34、=Needi,j Request ij;（4） 系统执行安全性算法，减产此次算法分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性算法：（1）设置两个向量： 工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。 Finish，表示系统是否有足够的资源分配给进程，使之运行完成。开始时限做Finishi:=false；当有足够资源分配给进程时，再令Finishi:=true。（2）从进程集合中找到一个能满足下述条

35、件的进程： Finishi = false； Needi,j <= Workj；若找到，执行步骤（3），否则，执行步骤（4）（3） 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj:=Workj + Allocationi,j;Finishi:=true;go to step 2;（4） 如果所有进程的Finishi = true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。死锁的检测和解除-资源分配图，检测方法、解除方法资源分配图：系统死锁可利用资源分配图来描述。该图是由一组节点N和一组边E所组成的一个对偶G=(N1E)。用圆圈代表一

36、个进程，用方框代表一类资源。检查方法：我们可以利用把资源分配图加以简化的方法，来检查当系统处于S状态时是否为死锁状态。简化方法如下： 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。分配资源使Pi运行再释放全部资源，相当于小区Pi所求的请求边和分配边，使之成为孤立的结点。 Pi释放资源后，使其他进程获取资源运行。这样不断减缓资源分配图 在进程一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则成该图是可完全简化的。有关文件已经证明，所有的简化顺序，都将得到相同的不可简化图。S为死锁的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。解

37、除方法： 常用解除死锁的两种方法是： 剥夺资源； 撤销进程。 ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 6 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6 在银行家算法中，若出现下述资源分配情况：试问： 该状态是否安全？ 若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？该状态是安全的，因为存在一个安全序列< P0P3P4P1P2>。下表为该时刻的安全序列表。资源情况进程WorkNeedAllocationWork

38、+AllocationFinishP0P3P4P1P21 6 2 21 6 5 41 9 8 71 9 9 112 9 9 110 0 1 20 6 5 20 6 5 61 7 5 02 3 5 60 0 3 20 3 3 30 0 1 41 0 0 01 3 5 41 6 5 41 9 8 71 9 9 112 9 9 113 12 14 17truetruetruetruetrue若进程P2提出上述请求，系统不能将资源分配给它，因为分配之后系统将进入不安全状态。 P2请求资源：P2发出请求向量Request2（1，2，2，2），系统按银行家算法进行检查：Request2（1，2，2，2）N

39、eed2（2，3，5，6）；Request2（1，2，2，2）Available（1，6，2，2）；系统暂时先假定可为P2分配资源，并修改P2的有关数据，如下表：AllocationNeedAvailable2 5 7 61 1 3 40 4 0 0 可用资源Available（0，4，0，0）已不能满足任何进程的需要。第四章逻辑地址和物理地址的概念 逻辑地址（Logical Address）是指由程式产生的段偏移地址部分。 物理地址（Physical Address）是指CPU外部地址总线上的寻址物理内存地址信号，是地址变换的最终结果地址。 什么是地址重定位(地址变换)，变换的时机(静态地址

40、重定位和动态地址重定位) 地址重定位就是把程序中相对地址变换为绝对地址。通常是把在装入时对目标程序中指令和数据的修改过程称为重定位。有静态重定位和动态重定位两种重定位技术。 因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。 动态重定位，在运行过程中程序在内存中的位置可能经常要改变，此时就应采用动态运行时装入的方式。动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。 什么是虚拟

41、存储器：所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。引入的原因： 有的作业很大，要求的内存空间超过了内存总容量，不能装入内存，致使该作业无法运行。 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们运行，而将其他大量的作业驻留在外存上等待。 常规存储器管理方式：一次性；驻留性 局部性原理的提出：时间局限性；空间局限性。一个解决方式是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。虚存空间容量由什么因素决定

42、其容量由内存容量和外存容量之和决定。虚拟存储器有哪些特征？最本质的特征是什么？ 对换性，多次性，虚拟性三大特征。 虚拟性是最本质的特征对于分区、分页、分段、段页式(纯/请求)存储管理方式，掌握：1）基本思想2）存储管理使用的数据结构(空闲空间管理的/作业占用空间管理的)3）逻辑地址的格式，地址变换的时间(动态/静态)、方法4）存储分配和存储回收过程5）是否能实现虚拟存储；如果能，如何实现6）其他特点：是否存在碎片问题(原因)；是否能实现存储保护(如何实现)等7）请求分页式存储管理的页面置换过程和简单的页面置换算法何为静态链接？何谓装入时动态链接和运行时动态链接？ 静态链接是指在程序运行之前，先

43、将各自目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开的链接方式。 装入时动态链接是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的一种链接方式，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找相应的外部目标模块，把它装入内存中，并修改目标模块中的相对地址。 运行时动态链接是将对某些模块的链接推迟到程序执行时才进行链接，也就是，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。 第五章 I/O系统的组成(I/O设备、控制器、通道、总线) 设备分类情况，什么是虚拟设备，

44、引入的目的按设备的使用特性分类：存储设备；输入/输出设备按传输速率分类：低速设备；中速设备；高速设备按信息交换的单位分类：块设备；字符设备按设备的共享属性分类：独占设备；共享设备；虚拟设备虚拟设备：通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户（进程）同时使用。引入的目的：将慢速的独占设备改造成多个用户可共享的同类设备，提高设备的利用率 OS在设备管理中引入的相关技术：中断技术、DMA技术、通道技术、总线技术、缓冲技术、 Spooling技术(Spooling系统，可以用来实现虚拟设备)-组成和工作原理中断技术：组成：CPU，I/O控制器工作原理： CPU：向控制器发出I/O命令

45、，然后继续执行计算任务； I/O控制器：执行I/O命令，控制外部设备完成指定的I/O操作，然后向CPU发送中断信号； CPU：暂停正在执行的任务，处理I/O中断，完成后再返回，继续执行原来的任务。DMA技术：组成：CPU，内存，DMA控制器（主机与DMA控制器的接口；DMA控制器域块设备的接口；I/O控制逻辑；命令/状态寄存器CR；内存地址寄存器MAR；数据寄存器DR；数据计数器DC）工作原理：当处理器需要读/写一整块数据时，给DMA控制单元发送一条命令，包含：一次读或写的指令、I/O设备的地址、开始读或写的主存地址、需要传送的数据长度等；处理器发送完命令后就可处理其它事情；DMA控制器自己独

46、立管理整块数据的传送；当这个过程完成后，它会向处理器发一个中断请求。处理器只在一块数据开始传送和传送结束时关注一下I/O操作即可。通道技术：组成：每条通道指令包含的信息是：操作码、内存地址、计数、程序结束位、记录结束位。工作原理：把DMA方式中CPU以数据块为单位对读/写任务的干预，减少为以一次读/写任务及有关的控制和管理为单位的干预。 同时，又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。缓冲技术：组成：单缓冲，双缓冲，循环缓冲，缓冲池工作原理：在CPU与外设之间建立缓冲区，用于暂存CPU与外设间交换的数据，从而缓冲CPU与外设间速度不匹配的矛盾。Spo

47、oling技术组成：在磁盘上开辟输入井和输出井；在内存中开辟输入缓冲区和输出缓冲区；OS要有相关的管理进程：SPi，模拟脱机输入；SPo模拟脱机输出。工程原理：脱机输入和脱机输出在多道环境下，可以用OS的一道管理程序实现从I/O设备输入数据并存放到磁盘上，模拟脱机输入；用OS的另一道管理程序将磁盘上的数据输出到I/O设备上，模拟脱机输出；这种假脱机I/O操作称为Spooling技术。Spooling是一种虚拟设备技术、一种资源转换技术。 设备分配的原则，什么是设备独立性(与设备无关性)原则：要充分发挥设备的使用效率，尽可能地让设备忙碌，但又要避免由于不合理的分配方法造成进程死锁；设备独立性：即

48、应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中，使用逻辑设备名称来请求使用某类设备；而系统在实际执行时，还必须使用物理设备名称。因此，系统须具有将逻辑设备名称转换为某物理设备名称的功能，这非常类似于存储器管理中所介绍的逻辑地址和物理地址的概念。 什么是磁盘调度，磁盘调度的目标，磁盘调度算法(FCFS、SSTF、SCAN)的原理、优先考虑的因素磁盘调度：就是当有多个进程同时要求访问磁盘时，安排对磁道访问请求的执行顺序。磁盘调度的目标是：使磁盘的平均寻道时间最少。先来先服务FCFS：根据进程请求访问磁盘的先后次序进行调度。最短寻道时间优先SS

49、FT：要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。扫描算法SCAN：不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。 为什么要引入设备独立性？如何实现设备独立性？ 引入设备独立性，可使应用程序独立于具体的物理设备，是设备分配具有灵活性。另外容易实现I/O重定向。 为了实现设备独立性，必须在设备驱动程序之上设置一层设备独立性软件，用来执行所有I/O设备的公用操作，并向用户层软件提供统一接口。关键是系统中必须设置一张逻辑设备表LUT用来进行逻辑设备到物理设备的映射，其中每个表目中包含了逻辑设备名、物理设备名和设备驱动程序入口地址三项；当应用程序用

50、逻辑设备名请求分配I/O设备时，系统必须为它分配相应的物理设备，并在LUT中建立一个表目，以后进程利用该逻辑设备名请求I/O操作时，便可从LUT中得到物理设备名和驱动程序入口地址。（OS实现设备独立性的方法：设置设备独立性软件(P164)、配置逻辑设备表，实现逻辑设备到物理设备的映射。） 什么是虚拟设备？其实现所依赖的关键技术有哪些？ 虚拟设备是指通过虚拟技术，可将一台独占设备变换成若干台逻辑设备，供若干个用户（进程）同时使用。由于多台逻辑设备实际上并不存在，而只是给用户的一种感觉，因此被称为虚拟设备。其实现所依赖的关键技术是SPOOLing技术。 试说明Spooling系统的组成。 输入井和

51、输出井； 输入缓冲区和输出缓冲区； 输入进程SPi和输出进程SPo。第六章什么是文件的逻辑结构，记录式文件的逻辑结构有哪几种文件的逻辑结构：这是用用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。记录式文件的逻辑结构：1、有结构文件：记录的长度可分为定长和不定长两类：定长记录；变长记录根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件：顺序文件；索引文件；索引顺序文件。2、无结构文件：流式文件，其长度以字节为单位。 什么是文件的物理结构，文件的物理结构(外存分配方式)有哪几种，每一种文件物理结构的实现方法，需

52、要用到的数据结构，目录中如何记录文件地址又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。外存的分配方式：连续分配（P213）a.实现方式：为每个文件分配一组位置相邻接的盘块(物理地址连续的外存空间)，文件中的逻辑页被顺序地存放到相邻的物理盘块中。这保证了文件中的逻辑顺序与文件占用盘块顺序的一致性。这样物理结构的文件称为顺序文件。每个文件都从分配给它的一个盘块的第一个字节开始存放。b.记录文件地址：在文件的目录中，存放该文件的第一个记录所在的盘块号和文件的长度(共占多少块)链接分配（P215）a.实现方式：为每个文件分配一组位

53、置离散的盘块，每个盘块中存放文件的一个逻辑页。通过在每个盘块上设置一个指针，将属于同一个文件的盘块顺序地链接在一起，链接的顺序和文件的逻辑顺序一致。这样物理结构的文件称为链接文件。链接方式有隐式链接和显式链接两种。b.记录文件地址：显示链接：每个文件的第一个盘块的编号存放在文件目录中；文件的其他盘块的编号存放在FAT中；隐式链接：目录和FAT一起记录了哪些盘块分给了这个文件以及这些盘块中内容的逻辑顺序。索引分配（P221）a.实现方式： 为每个文件分配一组位置离散的盘块，为每个文件建立一个物理结构的索引表，记录分配给该文件的物理盘块，以及这些盘块和文件逻辑顺序的对应关系。建立一个文件时，要初始

54、化它的索引表，并将索引表的地址放到文件的目录中。打开一个文件时，文件的索引表也被同时读入内存。b.记录文件地址： 单级索引：每个文件一张索引表，这张索引表放在一个盘块中多级索引：对于一个长文件的索引表(内容同上，但单个盘块放不下)，可以将它存放在若干个离散的盘块中。 再为这些索引块建立一个索引表，存放在一个盘块中，这样就形成了一个文件的两级索引。混合索引：文件系统混合使用多种分配方式。文件的目录中可以存放不同形式的地址信息： ? 直接地址，文件数据的盘块号； ? 一次间接地址，文件索引块的盘块号； ? 二次间接地址，文件二级索引块的盘块号。 单级、两级和多级(树型)目录结构的构成，逐步能实现的功能(特点)单级目录结构：构成： 为整个文件系统建立一张目录表，每个文件占一个目录项。功能： 优点：简单且能实现目录管理的基本功能-按名存取。 缺点：(1)查找