操作系统复习.docx
《操作系统复习.docx》由会员分享，可在线阅读，更多相关《操作系统复习.docx（24页珍藏版）》请在冰点文库上搜索。
操作系统复习
进程有哪些状态？
并简要描述这些状态的变迁关系？
引起各种状态转换的典型事件分别是什么？
UNIX操作系统的SHELL是负责的模块，管道通信
位示图的作用
文件目录，文件系统的目的，文件的逻辑结构和物理结构，文件的存取控制。
段与页，页表项的含义
管程的叙述
重定位的有关描述、通道（通道又称为I/O处理机，它能完成内存和外设之间的信息传输），与CPU并行工作。
、抖动与颠簸，缓冲技术
并发并行串行的辨析
在某分页储管理系统中，设一进程有8页的逻辑空间，每页有1024字节，它们被映射到32块的物理内存储器中，那么，逻辑地址的有效位是位，物理地址至少是位。
设备独立（无关）性
采用SPOOLing技术的目的是
缓冲技术中的缓冲池在
1、CPU调度即调度是从队列中选择一个进程,并把CPU分配给他。
3．设系统中有三类资源R1、R2、R3和R4，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：
资源
进程
最大需求量
R1R2R3R4
已分配资源量
R1R2R3R4
剩余资源量
R1R2R3R4
P1
P2
P3
P4
P5
8641
4331
10132
3331
5463
1211
3111
4132
3220
1131
2113
（1）系统是否处于安全状态？
若是，则给出进程安全序列。
（2）如果进程P5申请1个资源R1、1个资源R2、1个资源R3和2个资源R4，能否实施分配？
为什么？
段式地址转换
5操作系统与用户的接口有哪些？
操作系统与用户的接口有两类接口：
作业控制一级接口和程序一级接口，所有计算机用户都是通过这些接口和操作系统联系。
作业控制一级的接口主要使用操作系统提供的各种命令和菜单方式直接控制作业运行。
用户可以用作业控制语言写出控制作业执行的作业说明书，也可以从键盘上输入操作控制命令，操作系统可根据控制说明书或命令要求对作业进行控制执行。
程序一级的接口是给用户在编制程序时使用计算机资源提供的一种手段——系统调用（由系统提供系统调用命令）。
用户在编制程序时使用这些系统调用命令请求操作系统提供服务。
第三章进程管理
1程序顺序、并发执行的主要特征各是什么？
（1）异步性。
程序每次运行的时间是不确定的，其整个运行过程呈现不连续状态，并按照各自独立的不可预知的速度向前推进。
当现行执行程序需要等待某个事件（如输入/输出操作完成）时，系统将把CPU控制权转交给其它程序，当所等待的事件发生后，在以后的某个时刻，该程序可以再次获得CPU。
在分时系统中，时间片中断将导致现行程序中断执行，待以后某个时刻，该程序可以再次获得另一个时间片。
（2）失去封闭性。
由于运行程序之间的资源共享，程序在运行期间受到其它运行程序的影响，程序顺序执行时的封闭性不再保持。
例如程序在执行过程中，当申请的资源得不到满足时，它必须等待；当运行中程序的资源被其它程序强行使用，或者强行使用了其它运行程序的资源，会导致程序异常终止。
（3）不可再现性。
并发执行的程序由于某些原因，程序每次运行的过程和结果是不确定的。
这与程序顺序执行的可再现性恰好相反。
即使程序运行的初始条件和运行环境都不改变，也会因运行的时刻不同，而得到不同的运行结果。
从运行的过程来看，也不可能通过重复操作来再现程序的运行轨迹。
2什么是进程？
进程与程序之间有什么关系？
进程是一个具有一定独立功能的、可并发执行的程序关于某个数据集合的一次运行活动。
区别：
∙进程是程序的一次执行活动，属于动态概念，程序是指令的集合，它是进程运行的静态描述文本。
∙程序可作为软件资料长期保存，而进程是程序的一次执行过程，是暂时的。
进
程具有生命周期。
（3）一个进程可以执行一个或几个程序；反之，同一个程序可能由几个进程同时执行。
（4）进程具有并发性，它能真实地描述并发执行的活动，而程序不具备这种特征。
（5）进程具有创建其它进程的功能，程序不具备这种功能。
（6）进程是一个独立的运行单位，也是系统进行资源分配和调度的一个独立单位
3操作系统中为什么引入进程？
在操作系统中引入进程概念，是为了实现多个程序的并发执行。
传统的程序不能与其他程序并发执行，只有在为之创建进程后，才能与其他程序（进程）并发执行。
这是因为并发执行的程序是“停停走走”地执行，只有在为它创建进程后，在它停下时，方能将其现场信息保存在它的PCB中，等待下次被调度执行时，再从PCB中恢复CPU现场而继续执行，而传统的程序却无法满足以上要求。
4什么是进程控制块？
有何作用？
为什么说PCB是进程存在的惟一标志？
进程包括三个部分：
程序、数据集合和进程控制块（PCB）。
5什么是线程？
它与进程的区别是什么？
线程：
也叫轻量级的进程，它是一个基于进程的运行单位，它可以不占有资源，一个进程可以有一个线程或者多个线程（至少一个），这些线程共享此进程的代码、Data和部分管理信息，但是每个线程都有它自己的PC、Stack和其他。
线程与进程的区别主要表现在以下几个方面：
地址空间和资源不同：
进程间相互独立；同一进程的各个线程之间却共享它们。
通信不同：
进程间可以使用IPC通信，线程之间可以直接读写进程数据段来进行通信；但是需要进程同步和互斥手段的辅助，以保证数据的一致性。
调度和切换不同：
线程上下文切换比进程上下文的切换要快得多。
6什么是原语？
原语是机器指令的延伸，是由若干机器指令构成用以完成特定功能的一段程序，是一个不可中断的过程，即是不可分割执行的整体。
有以下基本原语：
4、假定某移动臂磁盘上，刚刚处理了访问143号柱面的请求，目前正在为访问125号柱面的请求服务，同时有若干请求者在等待服务，它们依次访问的柱面号为86，147，91，177，94，150，102，175，130
请回答下列问题：
（1）分别计算采用先来先服务、最短寻道时间优先和电梯（SCAN）算法的平均寻道长度。
（2）写出SCAN算法的调度次序（服务次序）。
5、在一个请求页式存储系统中，一个程序的页面走向为4，3，2，1，4，3，5，4，3，2,1，5，并采用LRU页面置换算法。
假设分配给该程序的存储块数M分别为3和4时，求出在防问过程中发生的缺页次数和缺率。
答：
M=3缺页次数=10缺率=10/12=5/6
M=4缺页次数=8缺率=8/12=2/3
两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥。
进程间的互相合作的协同工作关系、有前后次序的等待关系称为进程同步。
10什么是信号量？
其值的意义是什么？
信号量是一个仅能由同步原语进行操作的整型变量，用来实现进程之间的互斥和同步。
信号量值为0时，说明没有资源可用，为正整数n表示有n个同类资源可用，为负整数m则表示有|m|个进程被堵塞在该临界资源外
11写出P、V操作的定义
有三个进程PA、PB和PC写作解决打印问题：
PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一次记录。
缓冲区的大小和一个记录大小一样。
请用P、V操作来保证文件的正确打印。
分析：
本题的第一部分是检查考生对基本概念的记忆与理解，在本题的分数中占的比较小，是解答本题的基础。
题目的第二部分时一个典型的生产者—消费者问题，其中的难点在于PB既是生产者优势消费者，处理不好可能造成同步错误或死锁。
P、V操作可用下面的伪码进行描述：
PROCEDUREP（S）
BEGIN
Lockoutinterrupts;
S:
=S-1;
IFS<0THEN
BEGIN
Status（q）:
=blockeda;
Insert（Q,q）;
Unlockinterrupts;
Scheduler;
END
ELSEunlockinterrupts
END
PROCEDUREV（S）
BEGIN
Lockoutinterrupts;
S:
=S+1;
IFS<=0THEN
BEGIN
Remove（Q,R）;
Status（R）:
=readya;
Insert（RL,R）;
Length（RL）:
=length（RL）:
=length（RL）+1;
END
Unlockinterrupts;
END
三个进程的流程为：
BETGINintegermutex1,mutex2,avail1,full1,avial2,full2;
Mutex1:
=1;
Mutex2:
=1;
Avial1:
=1;
Avial2:
=1;
Full1:
=0;
Full2:
=0;
COBEGIN
PA:
BIGIN
L1:
readfromdisk;
P（avial1）;
P（mutex1）;
Puttobuffer1;
V（full1）;
V（mutex1）;
GotoL1;
END
PB:
BIGIN
L2:
P（full1）;
P（mutex1）;
Getfrombuffer1;
V（avial1）;
V（mutex1）;
P（avial2）;
P（mutex2）;
Puttobuffer2;
V（full2）;
V（mutex2）;
GotoL2;
END
PC:
BIGIN
L3:
P（full2）;
P（mutex2）;
Getfrombuffer2;
V（avial2）;
V（mutex2）
GotoL3;
END
COEND
END
程序中mutex1和mutex2是两个公用信号量，同于控制进程对缓冲区1和缓冲区2这两个临界资源的访问的互斥。
Avial1、full1、avial2和full2分别对应于连个缓冲区，其中avial1初值为1，表示可以利用的缓冲区数目为1；full的初值为0，表示存在于缓冲区内的数据的个数为0。
通过对这两组私用信号量的P、V操作，就实现了进程的同步。
13设有一个具有N个信息元素的环形缓冲区，A进程顺序地把信息写入缓冲区，B进程一次地从缓冲区独处信息。
回答下列问题：
∙叙述A、B两进程的相互制约关系。
∙判别下列用P、V操作表示同步算法是否正确？
如不正确，试说明理由，并修改成正确算法。
VARbuffer:
ARRAY0..N-1OFT;
In,out:
0…N-1;
VARS1,S2:
Semaphore;
S1:
=0;S2：
=N；
In：
=out：
=0；
PROCEDUREA：
BEGIN
REPEAT
生产数据m；
P（S2）；
Buffer（in）:
=m；
In:
=（in+1）MODN；
V（S1）；
Forever
END
PROCEDUREB：
BEGIN
REPEAT
V（S2）;
m;=buffer（out）;
消费m;
Out:
=（out+1）MODN;
P（S1）;
forever
END
分析：
本题目是一个标准的生产者—消费者问题。
题中所给的算法与标准算法不同，但考生不能因此就说这个算法不正确。
考生须仔细分析试题中所给出的算法。
在本题中，进程B在使用缓冲区前（读缓冲区）无需进行任何P操作，即进程B不会因任何原因被阻塞。
这与题目中控制要求不相符。
因此这个算法实现是错误的。
此外，对缓冲区的访问也没有用互斥信号量进行控制。
∙A和B两进程的相互制约关系如下：
当缓冲区满是，A进程不可以写，必须等待；当缓冲区空时，B进程不可以读，必须等待。
该算法有错，它对读进程进入临界区末加限制。
当缓冲区为空时，也可以进入临界区读信息。
当存在多个读进程和多个写进程时，还需要引入一个信号量S0以防止同时读或同时写。
改进后的算法如下：
VARbuffer:
ARRAY0..N-1OFT;
In,out:
0…N-1;
VARS0,S1,S2:
Semaphore;
S0:
=1;S1:
=0;S2:
=N;
In:
=out:
=0;
PROCEDUREA:
BEGIN
REPEAT
生产数m;
P（S2）;
P（S0）;
Buffer（in）:
=m;
In:
=（in+1）MODN;
V（S0）;
V（S1）;
Forever
END
PROCEDUREB:
BEGIN
REPEAT
P（S1）;
P（S0）;
m;=buffer（out）;
out:
=（out+1）MODN;
V（S0）
V（S2）;
消费m;
forever
END
14某操作系统将消息缓冲通信作为进程之间的基本通信手段。
Send和Receive分别为发送消息和接收消息原语。
请设计一种方案，用Send和Receive原语来实现基于信号量的P、V操作。
分析：
本题是一个关于P、V操作的实现的问题。
在不同的平台上，P、V操作可以有不同的实现方式。
但各种实现方式都需要实现P、V操作原语的语义。
在本立体中，要通过消息发送与接收来完成P、V操作，需要考生对P、V操作的原理有较深刻的理解，并能合理利用消息传递函数的功能。
本题的关键在于P、V操作原来的语义是对变量（信号量）的加减操作，是由一个进程对一个变量的操作，而消息传递需要两个进程来完成。
因此，改为由消息传递来完成后，如何将一个进程完成的工作转化为两个进程完成的工作，是用Send和Receive原语来实现基于信号量的P、V操作的关键一步。
为了生产两个进程的互操作，我们第一个同步进程，这样，所有的操作均由调用P、V操作的进程和同步进程用Send和Receive原语来完成。
解决了这一步后，实现算法就不难写了。
所有县号量由一个叫同步进程的进程来管理，对应每个信号量设置一个计数器（记录信号量的值）和一个等待进程链表。
P、V操作通过调用P和V过程将信号量S和操作作为消息发给同步进程，然后作揖个Receive等待同步进程的回答。
同步进程接收到消息后，看所要求的操作能否完成。
P操作当S的值为0时，同步进程八调用者推入队列，不发回消息，则调用者处于等待状态；V操作总能完成，所以发回一条空消息给调用者，将其解冻。
同时检查S的值是否为1和相应等待队列空否。
若S为1，且队列不空，则从队列中移出一个进程，向它发送一个空消息，将它解冻。
15设有8个程序prog1,prog2,…prog8。
它们在并发系统中执行时有如图2.1所示的制约关系,使用P、V操作实现这些程序间的同步。
分析：
本题目是用来检查考生对使用P、V操作实现进程间同步的掌握情况。
一般地，若要求进程B在进程A之后方可执行时，只需在进程P操作，而在进程A执行完成时对同一信号量进行V操作即可。
本题要求列出8个进程（程序）的控制关系，使题目显得较为复杂。
但当对进程间的同步理解透彻后，应不难写出对应的程序。
解这一类问题还应注意的一点是，要看清图示的制约关系，不要漏掉或多处制约条件。
程序间的同步如下所示：
BEGIN
Integers13,s14,s15,s23,s24,s25;
Integers36,s48,s57,s68,s78;
s13:
=0;s14:
=0;s15:
=0;
s23:
=0;s24:
=0;s25:
=0;
s36:
=0;
s48:
=0;
s57:
=0;
s68:
=0;
s78:
=0;
COBEGIN
prog1：
BEGIN
doallwork;
V（s13）;
V（s14）;
V（s15）;
END
prog2：
BEGIN
doallwork;
V（s23）;
V（s24）;
V（s25）;
END
prog3：
BEGIN
V（s13）;
V（s23）;
doallwork;
V（s36）;
END
prog4：
BEGIN
P（s14）;
P（s24）;
doallwork;
V（48）;
END
prog5：
BEGIN
P（s15）;
P（s25）;
Doallwork;
V（57）;
END
prog6：
BEGIN
P（s36）;
Doallwork;
V（s68）;
END
prog7：
BEGIN
P（s57）;
Doallwork;
V（s78）;
END
Prog8：
BEGIN
P（s48）;
P（s68）;
P（s78）;
Doallwork;
END
COEND
END
16在公共汽车上，司机和售票员的工作流程如下图所示。
为保证乘客的安全，司机和售票员应协调工作：
停车后才能开门，关车门后才能行车。
用PV操作来实现他们之间的协调。
在汽车行驶的过程中，司机活动与售票员活动之间的同步关系为：
售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。
因此司机启动车辆的动作必须与售票员关车门的动作取得，售票员开车门的动作也必须与司机停车取得同步。
在本题中，应设置两个信号量：
S1、S2。
S1表示是否允许司机启动汽车，其初值为0；S2表示是否允许售票员开门，其初值为0。
用P、V原语描述如下：
ints1=0;
ints2=0;
main（）
{
parbegin
driver（）;
busman（）;
parend
}
driver（）
{
while
（1）
{
p（s1）;
启动车辆；
正常行车；
到站停车；
v（s2）;
}
}
Busman（）
{
while
（1）
{
关车门；
v（s1）;
售票；
p（s2）;
开车门；
上下乘客；
}
}
17有一只铁笼子，只能装一只动物。
猎手向笼子中放入老虎，农民向笼子中放入猪，动物园等待取笼中老虎，饭店等待取笼中的猪。
假设开始笼子是空的，试用PV操作写出能同步执行的程序。
设置猎人和农民的公用信号量为mutex=1;
设置猎人的私用信号量为s=0;
设置农民的私用信号量为d=0;
18什么是线程？
为什么要引入线程？
线程，指进程内一个相对独立的并具有可调度特性的执行单元。
在引入线程的操作系统中，线程是进程中的一个实体，是系统被独立调度的基本单位。
线程自己基本不拥有系统资源，只拥有一些在运行过程中必不可少的资源，比如：
程序计数器、寄存器和栈。
线程可与它同属一个进程和其他线程共享进程所拥有的全部资源。
由于进程是一个资源拥有者，因而在进程的创建、撤消和切换中，系统必须为之付出较大的时空开销。
也因为如此，在系统中所设置的进程数目不宜太多，进程切换的频率也不宜太高，这就限制了并发程度的进一步提高。
操作系统引入线程的目的，主要是为了提高系统的执行效率，减少处理机空转时间和调度切换时间以及便于系统管理，使操作系统具有更好的并发性。
19进程和线程是什么关系？
进程和线程的关系进程作为独立的实体，它为线程提供运行的资源并构成静态环境。
线程是处理机调度的基本单位。
第四章处理机调度
2处理机调度分成哪几级？
说明每一级调度的含义。
【解答】
处理机调度按调度的层次可以划分为高级调度、中级调度和低级调度三种。
（1）高级调度（highlevelscheduling）。
高级调度又称为作业调度或长程调度，它决定从外存的后备队列中的选出哪些作业调入内存，并为它建立一个或多个就绪进程，准备执行。
但在分时系统和实时系统中没有作业的概念，目的是缩短响应时间或满足用户需求的截止时间，高级调度也就取消了。
（2）中级调度（intermediatelevelscheduling）。
中级调度也叫做中程调度。
在有些系统中，特别是分时系统和具有虚拟存储器的系统中，会增加一级中级调度。
其主要任务是在内存和外存交换区之间换出被阻塞的进程，换进被选中要执行的进程，从而达到扩充内存容量的目的。
（3）低级调度（lowlevelscheduling）。
低级调度也叫进程调度或短程调度。
进程调度的任务是按照调度算法从就绪进程队列中选择一个来执行。
执行进程调度的程序称为分派程序（dispatcher）。
分派程序的执行频率很高，可能一秒钟要执行好几次，因此需要常驻内存。
3进程调度的时机有哪些？
【解答】
一般来说，进程调度的时机与引起调度的原因及调度的方式有关。
通常在下面几种情况下会产生进程调度：
（1）正在执行的进程正常结束执行或因发生某种事件而不能继续运行下去，需要重新调度一个进程执行。
（2）执行中的进程因提出I/O请求而暂停执行时，要重新调度。
（3）在进程通信或同步过程中，执行了某种原语操作，如P、V操作等，要重新调度。
（4）在可剥夺式调度中，有一个比当前运行进程优先权更高的进程进入就绪队列时，为保证其立即获得CPU，要重新调度。
（5）分时系统中，时间片用完，要重新调度。
4试评价各种调度算法的优劣。
【解答】
特性
调度算法
调度方式
吞吐量
响应时间
系统开销
对进程的影响
FCFS
非剥夺
不定
可能很高，尤其是进程执行时间变化很大时
最小
对倾向于I/O的进程不利
SJF
非剥夺
高
对短进程提供好的响应时间
可能高
对长进程不利
HRN
非剥夺
高
提供较好的响应时间
可能高
平衡性好
RR
剥夺（时间片）
时间片很小时，吞吐量可能很低
对短进程提供好的响应时间
低
公平对待
HPF
剥夺（到达时）
高
提供较好的响应时间
可能高
对长进程不利
多级反馈队列
剥夺（时间片）
不定
不定
可能高
有利于倾向I/O的进程
5RR算法一般是在什么系统中采用？
为什么？
多级反馈队列调度的作用是什么？
【解答】
轮转算法是用于进程调度一种剥夺式的算法，出于公平性考虑，想做到让每个进程的等待时间与占用CPU的时间成正比。
轮转算法将CPU的处理时间分成大小相等的时间片，轮流地为每个就绪进程一次分配一个时间片。
每个时间片的长度一般在毫秒级，例如100ms。
RR算法一般用在分时系统中，通过轮转调度，系统能够及时响应每个用户，让用户感觉到系统好象是在专门为他服务。
多级反馈队列就是综合了FCFS，RR和HPF的一种调度算法。
多级反馈队列顾名思义有多个作业队列，多级反馈队列算法允许一个作业从一个队列移到另外的队列。
这种策略基于以下考虑：
①为提高系统吞吐量和降低作业平均等待时间而照顾短作业。
②为得到较好的输入输出设备利用率和对交互用户的及时响应而照顾输入输出型作业。
③在作业运行过程中，按作业运行情况来动态地考虑作业的性质（I/O型作业还是计算型作业）。
并且要尽可能快地决定出作业当时的运行性质（以I/O为主还是以计算为主），同时进行相应的调度。
∙这样一来，如果某作业所需CPU时间过长，则它将被移入低优先级队列，这种调度策略让偏重I/O的作业和交互式作业进入高优先级队列。
类似地，在低优先级队列中等待时间较长的作业，将移入高优先级队列。
6设在单道批处理系统中有四道作业，它们提交的时刻及运行时间如下：
作业号
提交时刻（h）
运行时间（h）
1
8.0
1.0
2
8.5
0.5
3
9.0
0.2
4
9.1
0.1
请分别给出在算法FCFS、SJF和HRN中这组作业的调度
升级会员 