计算机操作系统期末复习资料.docx
《计算机操作系统期末复习资料.docx》由会员分享，可在线阅读，更多相关《计算机操作系统期末复习资料.docx（37页珍藏版）》请在冰点文库上搜索。
计算机操作系统期末复习资料
第一章
什么是OS，它在计算机系统中处在什么位置？
加载在硬件上的第一层软件，是硬件功能的首次延伸；
是系统资源的管理机构；是人、机之间的接口。
OS的发展过程----几类典型操作系统（多道批处理、分时、实时），每类操作系统的原理、特征（优缺点）
多道批处理系统：
原理：
20世纪60年代中期引入多道程序设计技术，由此形成了多道批处理系统。
在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。
特征（优缺点）：
（1）资源利用率高
（2）系统吞吐量大
（3）平均周转时间长
（4）无交互能力
分时系统：
原理：
分时系统是指在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。
特征（优缺点）：
（1）多路性
（2）独立性
（3）及时性
（4）交互性
实时系统：
原理：
实时系统是指系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。
特征（优缺点）：
（1）多路性
（2）独立性
（3）及时性
（4）交互性
（5）可靠性
OS的基本特性（并发、共享、虚拟、异步）----其中“并发”是最重要的特性
并发性、共享性、虚拟性和异步性四个基本特征；最基本的特征是并发性。
OS的主要功能----资源管理器和用户接口
资源管理功能：
处理机管理
存储器管理
设备管理
文件管理
操作系统和用户之间的接口：
用户接口：
联机用户接口，脱机用户接口和图形用户接口
程序接口：
该接口是为用户程序在执行中访问系统资源而设置的，它是由一组系统调用组成。
试说明推动多道批处理系统形成和发展的主要动力是什么？
主要动力来源于四个方面的社会需求与技术发展：
（1）不断提高计算机资源的利用率；
（2）方便用户；
（3）器件的不断更新换代；
（4）计算机体系结构的不断发展。
第二章
进程的概念，进程与程序（作业）的区别
进程是操作系统结构的基础；是一个正在执行的程序；计算机中正在运行的程序实例；可以分配给处理器并由处理器执行的一个实体。
进程实体：
为使程序（含数据）能独立运行，应为之配置一进程控制块，即PCB；而由程序段、相关的数据段和PCB三个部分便构成了进程实体。
进程的实质是进程实体的一次执行过程。
进程和程序区别：
（1）进程是一个动态概念，强调执行的过程，每个进程中包含了程序段和数据段两个部分，以及进程控制块PCB；
而程序是一个静态概念，程序是指令的有序集合，无执行含义；
（2）进程具有并行特征（独立性，异步性），程序则没有；
（3）一个进程可以执行多个程序（如Linux中通过exec调用），同一程序的多次执行将产生多个不同的进程。
同一个程序的一次执行也可产生多个进程（如在程序中多次调用Linux中的fork）。
进程和作业的区别在于：
一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。
作业是用户需要计算机完成某项任务，而要求计算机所做工作的集合。
一个作业的完成要经过作业提交、作业收容、作业执行和作业完成四个阶段。
而进程是已提交完毕的程序所执行过程的描述，是资源分配的基本单位。
其主要区别关系如下：
（1）作业是用户向计算机提交任务的任务实体。
在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行；而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。
任一进程，只要它被创建，总有相应的部分存在于内存中；
（2）一个作业可由多个进程组成，且必须至少由一个进程组成，但反过来不成立；
（3）作业的概念主要用在批处理系统中，像UNIX这样的分时系统中，则没有作业的概念；而进程的概念则用在几乎所有的多道程序系统中。
什么是PCB，PCB包含的主要信息，PCB的作用
为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB（ProcessControlBlock）。
PCB中主要包括下述四方面的信息：
进程标识符：
内部标识符，外部标识符；
处理机状态；
进程调度信息；
进程控制信息。
PCB的作用：
①PCB是系统只为每个进程定义的一个数据结构，是为了使程序（含数据）能独立运行，为之配置的一进程控制块；
②PCB、程序段和相关的数据段三部分构成了进程实体，创建进程，实质上是创建进程和实体中的PCB，而撤销进程，实质上是撤销进程的PCB；PCB是为了保证程序的并发执行；
③PCB使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。
进程的3种基本状态，状态间的转换以及引起状态转换的原因
进程的三种基本状态：
就绪状态，执行状态，阻塞状态
还存在两种比较常见的进程状态，即创建状态和终止状态
创建→就绪：
在当前系统的性能和内存容量均允许的情况下，完成对进程创建的必要操作，
相应的系统进程将进程的状态转换成活动就绪状态
执行→终止：
当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，
或是被其他有终止权的进程所终结，进程即进终止状态
（1）就绪→执行
处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
（2）执行→就绪
处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，
于是进程从执行状态转变成就绪状态。
（时间片用完）
（3）执行→阻塞
正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
（I/O请求）
（4）阻塞→就绪
处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。
（I/O完成）
什么是临界资源
临界资源是指每次仅允许一个进程访问的资源。
进程间的两种相互制约关系（--同步、互斥--）的概念（是进程间的低级通信）
进程同步（直接相互制约关系）：
它主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。
为进程之间的直接制约关系。
在多道环境下，这种进程间在执行次序上的协调是必不可少的。
举例：
有输入进程A通过单缓冲向进程B提供数据。
当缓冲空时，计算进程因不能获得所需数据而阻塞，当进程A把数据输入缓冲区后，便唤醒进程B；反之，当缓冲区已满时，进程A因没有缓冲区放数据而阻塞，进程B将缓冲区数据取走后便唤醒A。
进程互斥（间接相互制约关系）：
它主要源于资源共享，是进程之间的间接制约关系。
在多道系统中，每次只允许一个进程访问的资源称为临界资源，进程互斥就是保证每次只有一个进程使用临界资源。
举例：
有两进程A和B，如果A提出打印请求，系统已把唯一的一台打印机分配给了进程B，则进程A只能阻塞；一旦B释放打印机，A才由阻塞改为就绪。
什么是信号量
信号量是Dijkstra提出的用于解决进程同步的有效工具。
信号量是一个数据结构以及对其的操作。
除初始化外，仅能通过两个标准的原子操作wait（S）和signal（S）来访问。
两个语句在执行到一半的时候不能被中断。
什么是P操作、什么是V操作（P、V操作的处理流程，以记录型信号量为例）
P（S）：
wait（S）
每次wait操作，意味着进程请求一个单位的该类资源，使系统可供分配的该类资源数减少一个。
①将信号量S的值减1，即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）每个程序中用户实现互斥的P,V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。
若有多个分支，要认真检查其成对性。
（2）P,V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
（3）互斥信号量得初值一般为1
其中信号量S用于互斥，初值为1。
利用信号量和PV操作实现进程同步
PV操作是典型的同步机制之一。
用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。
用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。
使用PV操作实现进程同步时应该注意的是：
（1）分析进程间的制约关系，确定信号量种类。
在保持进程间有正确的同步关系情况下，哪个进程先执行，那些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置那些信号量。
（2）信号量的初值与相应资源的数量有关，也与P,V操作在程序代码中出现的位置有关。
（3）同一信号量的P,V操作要成对出现，但他们分别在不同的进程代码中。
什么是进程的（高级）通信，类型
进程通信，是指进程之间的信息交换，其所交换的信息量少者是一个状态或数值，多者则是成千上万个字节。
高级进程通信，是指用户可直接利用操作系统所提供的一组通信命令高效地传送大量数据的一种通信方式。
三大类：
（1）共享存储器系统
a、基于共享数据结构的通信方式
b、基于共享存储区得通信方式
（2）消息传递系统
（3）管道通信系统。
消息传递通信的两种实现方法
（1）直接通信方式
发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。
（2）间接通信方式
进程之间的通信需要通过作为共享数据结构的实体。
在操作系统为什么引入进程的概念？
它会产生什么样的影响？
为了使程序在多道程序环境下并发执行。
并对并发执行的程序加以控制和描述，在操作系统为什么引入进程的概念。
影响：
使程序的并发执行得意实行。
为什么说PCB是进程存在的唯一标志？
因为：
①在调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存地址，找到其程序和数据；进程在执行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也都需要访问PCB：
当进程由于某种原因而暂停执行时，又需将器断点的处理机环境保存在PCB中。
可见，在进程的整个生命期中，系统总是通过PCB对进程进行控制的，亦即系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的。
所以PCB是进程存在的唯一标志。
线程的概念和属性
线程：
是"进程"中某个单一顺序的控制流，也被称为轻量进程（lightweightprocesses）。
线程具有以下属性：
1）轻型实体。
2）独立调度和分派的基本单位。
3）可并发执行。
4）共享进程资源。
试写出相应的程序来描述图所示的前驱图。
进程管理相关内容
进程管理相关内容
第一个图：
Vara,b,c,d,e,f,g,h;
semaphore:
=0,0,0,0,0,0,0,0;
beginparbegin
beginS1;signal（a）;signal（b）;end;
beginwait（a）;S2;signal（c）;signal（d）;end;
beginwait（b）;S3;signal（e）;end;
beginwait（c）;S4;signal（f）;end;
beginwait（d）;S5;signal（g）;end;
beginwait（e）;S6;signal（h）;end;
beginwait（f）;wait（g）;wait（h）;S7;end;
parendend
第二个图：
Vara,b,c,d,e,f,g,h,i,j;
semaphore:
=0,0,0,0,0,0,0,0,0,0;
beginparbegin
beginS1;signal（a）;signal（b）;end;
beginwait（a）;S2;signal（c）;signal（d）;end;
beginwait（b）;S3;signal（e）;signal（f）;end;
beginwait（c）;S4;signal（g）;end;
beginwait（d）;S5;signal（h）;end;
beginwait（e）;S6;signal（i）;end;
beginwait（f）;S7;signal（j）;end;
beginwait（g）;wait（h）;wait（i）;wait（j）;S8;end;
parendend
在生产者-消费者问题中，如果将两个wait操作即wait（full）和wait（mutex）互换位置，或者将signal（mutex）与signal（full）互换位置，结果会如何？
varmutex,empty,full:
semaphore:
=1,n,0;
buffer:
array[0,...,n-1]ofitem;
in,out:
integer:
=0,0;
begin
parbegin
producer:
begin
repeat
.
.
produceaniteminnextp;
.
.
wait（empty）;
wait（mutex）;
buffer（in）:
=nextp;
in:
=（in+1）modn;
/*******************/
signal（full）;
signal（mutex）;
/*******************/
untilfalse;
end
consumer:
begin
repeat
/******************/
wait（mutex）;
wait（full）;
/******************/
nextc:
=buffer（out）;
out:
=（out+1）modn;
signal（mutex）;
signal（empty）;
consumetheiteminnextc;
untilfalse;
end
parend
end
a.wait（full）和wait（mutex）互换位置后，因为mutex在这儿是全局变量，执行完wait（mutex），则mutex
赋值为0，倘若full也为0，则该生产者进程就会转入进程链表进行等待，而生产者进程会因全局变量
mutex为0而进行等待，使full始终为0，这样就形成了死锁.
b.而signal（mutex）与signal（full）互换位置后，从逻辑上来说应该是一样的.
试利用记录性信号量写出一个不会出现死锁的哲学家进餐问题的算法。
规定在拿到左侧的筷子后，先检查右面的筷子是否可用。
如果不可用，则先放下左侧筷子，
等一段时间再重复整个过程。
分析：
当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷
子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此
这样永远重复下去。
对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，
所有的哲学家都吃不上饭。
（2）描述一种没有人饿死（永远拿不到筷子）算法。
考虑了四种实现的方式（A、B、C、D）：
A．原理：
至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释
放出他所使用过的两支筷子,从而可使更多的哲学家进餐。
以下将room作为信号量，只允
许4个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入
餐厅的哲学家进入room的等待队列，根据FIFO的原则，总会进入到餐厅就餐，因此不会
出现饿死和死锁的现象。
伪码：
semaphorechopstick[5]={1，1，1，1，1};
semaphoreroom=4;
voidphilosopher（inti）
{
while（true）
{
think（）;
wait（room）;//请求进入房间进餐
wait（chopstick[i]）;//请求左手边的筷子
wait（chopstick[（i+1）%5]）;//请求右手边的筷子
eat（）;
signal（chopstick[（i+1）%5]）;//释放右手边的筷子
signal（chopstick[i]）;//释放左手边的筷子
signal（room）;//退出房间释放信号量room
}
}
B．原理：
仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。
方法1：
利用AND型信号量机制实现：
根据课程讲述，在一个原语中，将一段代码同时需
要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。
当
某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足FIFO的要求，
因此不会出现饥饿的情形。
伪码：
semaphorechopstick[5]={1，1，1，1，1};
voidphilosopher（intI）
{
while（true）
{
think（）;
Swait（chopstick[（I+1）]%5,chopstick[I]）;
eat（）;
Ssignal（chopstick[（I+1）]%5,chopstick[I]）;
}
}
方法2：
利用信号量的保护机制实现。
通过信号量mutex对eat（）之前的取左侧和右侧筷
子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。
伪码：
semaphoremutex=1;
semaphorechopstick[5]={1，1，1，1，1};
voidphilosopher（intI）
{
while（true）
{
think（）;
wait（mutex）;
wait（chopstick[（I+1）]%5）;
wait（chopstick[I]）;
signal（mutex）;
eat（）;
signal（chopstick[（I+1）]%5）;
signal（chopstick[I]）;
}
}
第三章
进程调度的功能：
1）保存处理剂的现场信息；2）按某种算法选取进程；3）把处理机分配给进程。
对于本章内的基本调度算法：
算法思想、就绪队列的组织、是抢占还是非抢占
FCFS先来先服务调度算法
算法思想：
当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。
在进程调度中采用FCFS算法时，则每次调度是从就绪对垒中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。
该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
FCFS是非抢占式的调度算法。
短作业（进程）优先调度算法
算法思想：
短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
而短进程优先（SPF）调度算法则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
短作业调度算法是非抢占式的调度算法。
非抢占式优先权调度算法和抢占式优先权调度算法
算法思想：
非抢占式优先权调度算法：
系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进程。
抢占式优先权调度算法：
系统同样是把处理机分配给优先权最高的进程，使之执行。
但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。
静态优先权和动态优先权
算法思想：
静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。
动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的。
高响应比优先调度算法
算法思想：
为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然后寄回分配到处理机。
该优先权的变化规律可描述为：
优先权=（等待时间+要求服务时间）/要求服务事件
基于时间片的轮转调度算法
算法思想：
系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。
多级反馈队列调度算法
算法思想：
设置多个就绪队列，并为各个队列赋予不同的优先级。
第一个队列的优先级最高，第二个队列次之。
当一个新进程进入内存后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。
如果一个时间片后进程尚未完成，调度程序便将该进程转入第二个队列的末尾，再同样地按FCFS原则等待调度执行。
当一个长作业从第一个队列一次降到第n个队列后，在第n队列中便采取按时间片轮转的方式运行。
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。
典型的动态优先权调度调度算法：
高响应比优先度调度算法；典型的实时调度算法：
最低松弛度优先调度算法；时间片轮转法中，时间片取值的影响
时间片取值的影响：
如果选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销；反之，如果选择太长的时间片，使得每个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，无法满足交互式用户的需求。
如何确定时间片的大小：
时间片应略大于一次典型的交互需要的时间。
这样可使大多数进程在一个时间片内完成。
一般应考虑三个因素：
系统对相应时间的要求、就绪队列中进程的数目和系统的处理能力。
什么是死锁，死锁产生的原因和必要条件
所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。
产生死锁的原因：
（1）竞争资源。
（2）进程间推进顺序非法。
产生死锁的必要条件：
1）互斥条件；2）请求和保持条件；3）不剥夺条件；4）环路等待条件。
什么是安全状态、不安全状态，它与死锁间的关系
所谓安全状态，只系统能按某种进程顺序（P1,P2,···,Pn）（称序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的完成。
如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
死锁的预防、避免、
升级会员 