if smonkeycount=0 then V(mutex);
V(smutex);
end;
process northj (j=1,2,3,…)
begin
P(nmutex);
if nmonkeycount=0 then P(mutex);
nmonkeycount :=nmonkeycount+1;
V(nmutex);
Cross the cordage;
P(nmutex);
nmonkeycount :=nmonkeycount-1;
if nmonkeycount=0 then V(mutex);
V(nmutex);
end;
coend.
五、在分页式存储管理中，什么叫快表，说明其工作原理和过程，画出具有快表的地址变换机构。（10分）
解：有了快表后，绝对地址形成的过程是：当调度程序选中某进程时，从该进程的PCB中读出页表的始址和长度，并装入页表控制寄存器。当处理器给出逻辑地址后，其中的页号若大于控制寄存器中的长度，表示访问越界并发越界中断。否则，由地址转换机构自动把页号送入快表，若该页已登记在快表中，并且符合访问权限，则由块号和单元号形成绝对地址；若快表中查不到对应页号，则再查主存中的页表而形成绝对地址，同时将该页登记到快表中。当快表填满后，又要在快表中登记新页时，则需在快表中按一定策略淘汰一个旧的登记项，最简单的策略是“先进先出”，总是淘汰最先登记的那一页。
中科院计算所（软件所）2001年硕士入学操作系统试题参考答案
一、填空题（15分）
1.在引进线程的操作系统中，调度和分派的基本单位是（ 线程 ），拥有资源的单位是（ 进程 ）。
2.高级进程通信机制主要有三种，电子邮件属于（ 信箱通信 ）。
3.一个计算机有6台可互换使用磁带机，由N个进程竞争使用，每个进程在一段有限的时间内需要独占两台磁带机进行使用，N最多为（ 5 ）时系统一定不会出现死锁。
4.请求分页系统中一个进程的访问踪迹为：0，2，1，3，0，2，4，0，2，1，3，4，利用FIFO算法，当进程使用三个页框时缺页（ 9 ）次，使用四个页框时缺页（10 ）次（缺页次数含初始调入次数）。
5.现代网络操作系统中，系统向程序提供了基于SOCKET的TCP/IP接口，在操作系统的核心中实现了TCP/IP协议的几个基本层次为（网络层IP/ICMP 、TCP/UDP ），SOCKET接口属于操作系统提供用户接口的（ 网络编程 ）接口。
6.一个32位虚拟地址被分成a，b，c，d四个域，a，b，c用于一个三级页表系统，d是页内偏移地址，页面数为（ 2a+b+c ）。
7．某虚拟存储器中的用户空间共有32个页面，每页1KB，内存16KB。假定某时刻系统为用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，虚拟地址0A6F对应的物理地址是（226F）。
8．某计算机系统执行一条指令需要10ns，一次缺页需要额外的20ms，若每1000 000条指令发生一次缺页，则指令的平均执行时间为（ 30 ）ns。
注：一次缺页需要额外的20ms=20×1000，000ns，即每条指令多化20ns。
9．程序段S1，S2，S3，S4之间存在下面的前驱关系：Sl→S2，S2→S3，S1→S4，可以并发执行的段为（S2/S4，S3/S4 ）。
10．在UNIX中存储器管理由其（内存管理 ）子系统负责。
11．在UNIX文件目录中的每一个目录项由两部分组成，即文件名和（索引节点号inode）。
12．在UNIX中进程映像包括三个部分，其中数据区数据在（proc指出的数据段中）。
二、简答题（15分）
- 试比较操作系统中原语与事务两个概念的异同。
答：原语(primitive)是操作系统内核中实现某种功能的不可中断的过程。这—过程中的操作要么全做，要么全不做，应当是原子操作。
事务(transaction)用于分布操作系统中进程同步控制，事务是一个操作序列，含在其中的操作，要么全完成，要么全未完成。分布式系统中的并发控制较为复杂，借助事务对同步的细节进行隐蔽与抽象，提高分布式编程效率。
- 简述操作系统虚拟性特征在设备管理中的体现。
答：虚拟性是指操作系统中的一种管理技术，它是把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。显然，前者是实际存在的而后者是虚构假想的。在设备管理中，通进Spooling技术可把物理上的一台独占设备变成逻辑上的多台虚拟设备，从而，使用方便，提高了独占设备的利用率。
- 试说明多级反馈队列调度算法的基本思想，为什么它是目前公认的较好的一种进程调度算法（与FCFS，SJF，优先级调度相比）。
答： FCFS、SJF和优先级调度算法仅对某一类作业有利，相比之下，它能全面满足不同类型作业的需求，较好实现公平性与资源利用率之间的平衡。对交互型作业，由于通常较短，这些作业在第一队列规定的时间片内完成，可使用户感到满意；对短批作业，开始时在第一队列中执行一个时间片就可完成，便可与交互型作业一样获得快速晌应，否则通常也仅需在第二、第三队列中各执行一个时间片即可完成，其周转时间仍较短；对长批作业，它们依次在第一至第n个队列中轮番执行，不必担心长时间得不到处理。
- 在UNIX的存储管理中，当需要将内存中的某页换出时，系统需要做哪些工作？系统核心专门配置了哪些数据结构。
答：UNIX基本采用LRU算法，换页细节略。
UNIX存储管理的数据结构有：1)每个进程的进程区表PPRT(Per Process Region Table)----用于当进程从逻辑空间转换为物理空间时们地址映射(包括正文段、数据段和栈段)。PPRT中除含有进程所在区的说明信息外，还含有指向进程页表的指针。2)进程页表具体指明进程页在内存的位置。3)磁盘块描述表—它的每一表项与一个页表项对应，以记录各页面的磁盘拷贝所在的磁盘块号。4)页面数据表--它的每一表项描述内存中一个物理页框，
三、分析编程题（10分）
若某机房有两台打印机。其中一台尽量满足系统打印要求，只有当系统不需要时才可以被一般用户共享。另一台打印机直接作为网络共享打印机，供一般用户使用。
（1）请给出用SPOOLing技术实现的系统组成；（3分）
（2）使用记录型信号量机制实现对这两台打印机使用过程的管理，要求写出需要设计的数据结构和算法。（7分）９
解：
- 开出足够大的输出井，设计一个输出井管理程序，一个缓输出程序(后台打印程序)。
- 两台打印机可供系统和用户程序使用，根据题意，设立3个并发进程完成两台打印机的使用。一是输出井管理程序，二是系统打印进程，二是网络打印进程。为此，输出井中设立了两个缓冲队列，分别存放系统打印作业和网络打印作业，且两个队列分别需要互斥使用。同时，系统打印进程还要与网络打印进程通信，以决定一般用户可否使用系统使用的打印机。
var S1,S2:semaphore;
sys-pcount,net-pcount:integer;
S1,S2:=1; /*系统/网络打印队列互斥信号量
Sys-pcount:=0;net-pcount:=1;
cobegin
process buffer-manage /*打印缓冲区管理进程
begin
接收一个打印作业;
if(系统打印作业)
P(S1);
放入系统打印队列;
sys-pcount:=sys-pcount+1;
V(S1);
Else
P(S2);
放入网络打印队列;
net-pcount:=net-pcount+1;
V(S2);
end;
process system-print
begin
P(S1);
If(sys-pcount>0)
取系统打印队列的一个打印作业打印;
sys-pcount:=sys-pcount-1;
else
P(S2);
取网络打印队列的一个打印作业打印;
net-pcount:=net-pcount-1;
V(S2);
V(S1);
end;
process user-print
begin
P(S2);
If(net-pcount<>0)
取网络打印队列的一个打印作业打印;
net-pcount:=net-pcount-1;
V(S2);
end;
coend.
中山大学操作系统2001硕士入学试题考答案
一、解释下列名词（6分）
(1)临界区 (2)挂起 (3)快表
(1) 临界区 进程中涉及代表共享资源的共享变量的程序段称临界区。。
(2) 挂起 为达到平滑系统操作负荷，或满足用户程序调试等目的，而新引入的一种进程状态称”挂起”态。被挂起的进程，对换到磁盘镜像区中，释放它所占有的某些资源，不难看出，可以把一个挂起进程等同于不在主存的进程，因此，挂起的进程将不参与低级调度直到系统资源充裕后它们被对换进主存。
(3) 快表 存分页式存储管理中，为了提高运算速度，通常都在MMU中设置一个专用的高速缓冲存储器，用来存放最近访问的部分页表，这种高速存储器称为相联存储器，也称TLB（Translation Lookaside Buffer），它成为分页式存储管理的一个重要组成部分。存放在相联存储器中的页表称快表。
二、试述信号量及其意义。（3分）
答：信号量是荷兰Dijksatra提出来的一种进程同步工具，该工具包括信号量及P、V两个操作。两个或多个进程通过samephore展开交互，一个进程在某个特殊点上停止执行直到获得交互进程发来相应信息为止。这样一来，任何复杂的进程交互要求可得到满足。在操作系统中，信号量用以表示物理资源的实体，它是一个与队列有关的整型变量，除赋初值外，信号量仅能由同步原语P、V对其进行操作，没有任何其他方法可以检查和操作信号量。信号量的物理意义如下
若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦即等于s所代表的实际还可以使用的物理资源数。
若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s等待队列的进程数。
通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作。
三、试述系统功能调用的实现原理。（4分）
答：系统调用是为了扩充机器功能、增强系统能力、方便用户使用而在内核中建立的过程(函数)。用户程序或其他系统程序通过系统调用就可以访问系统资源，调用操作系统功能，它是用户程序或其他系统程序获得操作系统服务的唯一途径。
每个操作系统都提供几十到几百条系统调用。在操作系统中，实现系统调用功能的机制称陷入或异常处理机制，由于系统调用而引起处理器中断的机器指令称访管指令（supervisor），陷入指令（trap）或异常中断指令（interrupt）。在操作系统中，每个系统调用都事先规定了编号，称功能号，在访管或陷入指令中必须指明对应系统调用的功能号，在大多数情况下，还附带有传递给内部处理程序的参数。
系统调用的实现有以下几点：一是编写系统调用处理程序；二是设计一张系统调用入口地址表，每个入口地址都指向一个系统调用的处理程序，有的系统还包含系统调用自带参数的个数；三是陷入处理机制，需开辟现场保护区，以保存发生系统调用时的处理器现场。
四、为什么段式管理有段内越界，而页式管理不会发生页内越界问题。（3分）
答：段式管理中，段地址是二维的，即段号与段内位移，采用动态可变分区方式进行管理。内存保护也采用基址+限长方式，因而，地址转换时要进行越界访问保护。当产生越界时，或作出错处理，或可以动态扩充该段的长度。页式管理中，作业的逻辑地址由页号+页内位移组成，页面长度规定后，页内位移也就限定了，始终不会超过页长，故不会产生越界问题。
五、UNIX系统如何用9位二进制位实现文件的保护的？（3分）
答：UNIX中把用户分为文件主、同组用户、其他用户三类，分别定义存取权限可读r、可写w、可执行x，目录项中的文件属性共有1+9位：
-rwxrwxrwx
其中：
第1位：表示文件是普通文件(-)，还是目录文件(d)、符号链接文件(l)、设备文件(b/c)。
第2-4位：表示文件主对文件的存取权限。
第5-7位：表示同组用户对文件的存取权限。
第8-10位：表示其他用户对文件的存取权限。
如一个文件的属性是-rwxr-x--x，表示该文件是普通文件，文件主对它可读、可写、可执行；同组用户对它可读、可执行；其他用户对它只可执行。
六、试扼要叙述进程与线程的区别。（3分）
答：多线程环境中进程是操作系统中进行保护和资源分配的基本单位。线程是操作系统进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。线程是进程的组成部分，每个进程内允许包含多个并发执行的控制流，这就是多线程。
七、在一个虚拟分页存储管理系统中，把内存分成大小为512B的块。设有一个用户要把512×512的数组置为全“0”。在分页时把数组的元素每一行放在一页中。假定分给用户可用来存放数组信息的工作区只有一块（只能放数组中的一行元素）。有人编写了两个不同的程序来实现数组的初始化：
（1）var A:array [1..512] of array [1..512]of integer;
for i=1 to 512 do
for j:=1 to 512 do
A[i:j] :=0;
（2）var A:array[1..512]of array [1..52]of integer;
for j := to 512 do
for i：=1 to 512 do
A[i，j]：=0；
分别就两个程序的执行过程计算缺页次数。（4分）
解：因数组按行存放，即A[1,1] A[1,512]，
A[1,512] A[512,512]
故(1)为512次 (2)为512×512次
八、假定磁盘的存取臂现在处于6#柱面上，有如表请求者等待访问磁盘，试列出最省时间的响应顺序。（3分）
|
序号 |
柱面号 |
磁道号 |
块号 |
|
1 |
7 |
6 |
3 |
|
2 |
5 |
5 |
6 |
|
3 |
15 |
20 |
6 |
|
4 |
7 |
4 |
4 |
|
5 |
20 |
9 |
3 |
|
6 |
5 |
15 |
2 |
解：当前移动臂在6号柱面，根据访问顺序，可采用序号次序：6→2→1→4→3→5。
注意，序号2和6中，6的块号小，故先做。序号1和4中，6的块号小，故先做。(只要符合柱面6→5→7→15→20均对)
九、在一个盒子里，混装了相等数量的黑棋子和白棋子，现要用自动分拣系统把黑棋子和白棋子分开，该系统由两个并发执行的进程P1和P2组成，其中进程P1专门拣黑子，进程P2专门拣白子。规定两个进程轮流拣子且每个进程每次只拣一个子。当一个进程在拣子时不允许另一个进程去拣子，并设P1先拣。请用P，V操作管理这两个并发进程，使其能正确实现上述功能。（4分）
答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一般性，若令先拣白子。
var S1,S2:semaphore;
S1:=1;S2:=0;
cobegin
{
process P1
begin
repeat
P(S1);
拣白子
V(S2);
until false;
end
process P2
begin
repeat
P(S2);
拣黑子
V(S1);
until false;
end
}
coend.
西北工业大学2000年研究生入学考试题参考答案
一、（本题共12分，每空1分）填空、选择题：
1．（B）
2．13，15
3．起始块号，总块数
4．1，4，1
5．（D）
6．（C）
7．逻辑地址（2，88）对应的物理地址是90+88=178；逻辑地址（4，100）由于段内地址100超过段长96，所以产生越界中断。
二、（本题共30分，每小题5分）
1．现代计算机系统一般都采用基于多道程序设计的技术。通常多道程序设计是指在主存中同时存放多道用户作业，使它们都处于执行的开始点和结束点之间。多道程序设计的特点如下：
（1）多道。主存中有多道程序，它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。
（2）宏观上并行。从宏观上看，它们在同时执行。
（3）微观上串行。从微观上看，它们在交替、穿插地执行。
因为中断是激活操作系统的手段，只有通过中断技术才能使CPU从一个作业的处理转到另一个作业的处理，而通道使得主机与外设可以并行工作，所以直到出现中断和通道技术后，多道程序概念才变为有用。
2．分时系统与实时系统的主要区别是：
（1）系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很强的系统；而实时系统则大多数都是具有某种特殊用途的专用系统。
（2）响应时间的长短不同。分时系统的响应时间通常为秒级，而实时系统的响应时间通常为毫秒级甚至微秒级。
（3）交互性的强弱不同。分时系统的交互性强，而实时系统的交互性弱。
设计适用于实时环境的操作系统的主要困难是：
