应 用 题

1、 设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P、V操作写出这些进程使用打印机的算法。

2、判断下面的同步问题的算法是否正确？若有错，请指出错误原因并予以改正。

（1）设A、B两进程共用一个缓冲区Q，A向Q写入信息，B则从Q读出信息，算法框图如图所示。

　　　　　　注：信号量S的初值为0

（2）设A、B为两个并发进程，它们共享一临界资源。其运行临界区的算法框图如图所示。

　　　　　　注：信号量S1、S2的初值均为0

3、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问：

①系统要设几个进程来完成这个任务？各自的工作是什么？

②这些进程间有什么样的相互制约关系？

③用P、V操作写出这些进程的同步算法。

4、设有三个批作业JOB1、JOB2、JOB3，其到达时间、处理时间及完成时间如下：

作业 　　作业到达时间（时） 　　开始处理时间（时） 　　处理完成时间（时）

JOB1 　　　15 　　　　　　18 　　　　　　　22

JOB2 　　  18 　　　　　　21 　　　　　　　23

JOB3 　 　17 　　　　　　19 　　　 　　　　21

试计算：

（1）各个作业的周转时间；

（2）所有作业的平均周转时间；

5、假定在单CPU条件下有下列要执行的作业：

作业        运行时间     优先级

1           10           2

2           4            3

3           3            5

作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。

（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。

（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？

（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？

6、某段表内容如下：

段号        段首地址      段长度

0           120K          40K

1           760K          30K

2           480K          20K

3           370K          20K

一逻辑地址为（2，154）的实际物理地址是多少？

7、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号         物理块号

0            3

1            7

2            11

3            8

则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。

8、对于如下的页面访问序列：
1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

9、试以某航空公司为两旅行社a和b的顾客预订飞机票为例，说明互斥的含义。

10、试以生产者--消费者问题为例，用ＰＶ操作说明进程同步问题的实质。

11、在UNIX 系统中，其进程调度方式是什么？引起进程调度的时机有那些？

12、为什么要打开文件？叙述在UNIX文件系统，打开文件/home/user01/myfile的过程？

13、某一系统进程的资源分配“瞬间状态”为

             已分配资源矩阵       最多资源矩阵       可用资源向量

  P0          0  0  1  2           0  0  1  2         1  5   2  0

  P1          1  0  0  0           1  7  5  0

  P2          1  3  5  4           2  3  5  6

  P3          0  6  3  2           0  6  5  2

  P4          0  0  1  4           0  6  5  6

使用银行家算法回答：系统是否安全？如果进程P1要求(0，4，2，0)，系统能否立即满足进程的要求？

14、考虑一个请求分页系统，测得如下的时间利用率：

CPU：20%；分页磁盘：97.7%；其它外设：5%

下列措施中，哪个(些)可改善CPU的利用率？说明理由：

(1)更换速度更快的CPU (2)更换更大容量的分页磁盘 (3)增加内存中用户进程数 (4)挂起内存中的某个(些)用户进程

15、 对于一个利用快表且页表存于内存的分页系统，假定CPU一次访问时间为1us，访问快表的时间可以忽略不记。如果85%的地址影射可直接通过快表完成，那么进程完成一次内存读写的平均有效时间是多少？

16、用信号量和P，V操作描述读者-写者问题：即允许多个读者同时读一个共享对象，但绝不允许一个写者和其它进程同时访问共享对象。

17、什么为核心态、用户态、特权指令？下列哪些指令为特权指令？

（1)改变存储器管理寄存器（2）写程序计数器（3）读日历钟（4）设置日历钟      （5）改变处理器优先级（6）写指令寄存器

18、一个多级反馈队列的系统中，一个使用CPU较多的进程需要执行50秒。如果第一个队列时间片为5，并且较低一级的时间片是上一级的时间片的2倍，那么这个作业会被中断多少次？当他终止的时候，处于那一级队列？

18、一个多级反馈队列的系统中，一个使用CPU较多的进程需要执行50秒。如果第一个队列时间片为5，并且较低一级的时间片是上一级的时间片的2倍，那么这个作业会被中断多少次？当他终止的时候，处于那一级队列？
19、某计算机有32位虚地址空间，且页大小为1024字节。每个页表项长4个字节。因为每个页表都必须包含在一页中，所以使用多级页表，问共需要几级？

20、在某简单分页系统中，有224字节的物理内存，256页的逻辑地址空间并且页的大小为210字节，问逻辑地址为多少位？    

21、在某段页式系统中，虚地址空间包含了8个段，段长为229字节。硬件把每个段分成大小为256字节的页。问虚地址中有多少位可以用于指定：

    （a）段号？（b）页号？ （c）页内偏移量 （d）整个虚地址

22、已知某程序访问以下页面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、6、2、1、3、6、2，如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。（1）FIFO替换算法（2）LRU替换算法

23、某系统使用请求分页存储管理，如果页在内存中，满足一个内存请求需要200ns。如果页不在内存，如有空闲的页框或者没有修改的换出的页，则请求需要7ms。如果替换出的页已经被修改，则需要15ms，如果缺页率是5％，并且60％的时间用于修改要换出的页，问有效访问时间是多长？假设系统只运行一个进程且页交换时CPU空闲 。 

24、一个磁盘有19456个柱面，16个读写头，并且每个磁道有63个扇区。磁盘以5400rpm的速度旋转，在相邻的磁道之间寻道时间是2ms。假定读写头在磁道0上，则读整个磁盘需要多少时间？

25、在一个磁盘上，有1000个柱面，从0～999。假定最后服务的请求是在磁道756上，并且读写磁头正在向磁道0移动。在按照FIFO顺序排列的队列中包含了如下磁道上的请求：811、348、153、968、407、500。用下面的算法计算为了满足所有的磁盘队列中的请求，磁盘臂必须移的磁盘的数目。

（a）IFO （b）SSTF （c）SCAN

26、大多数操作系统通过在主存中高速缓存存某些重要的文件系统数据来改善系统性能，这样的操作系统要求计算机关机之后才能切断电源。为什么？

27、在某系统中，一个目录项可以存储至多13个磁盘块的地址。前10个地址指向文件的前10个块。第11个地址指向一个中间块。第12个地址指向一个二重间接块。第13个地址指向一个三重间接块。每一个间接块可以容纳256个指针。一个块的大小是1024个字节，那么一个文件可以达到多大？

28、什么是死锁？死锁预防的措施有哪些？为什么？

29、假设某系统有同类资源12个，有三个进程P1，P2，P3来共享，已知P1、P2、P3所需要资源总数分别为8，6，9，它们申请资源的次序和数量如表所示，系统采用银行家算法为它们分配资源。

（1）哪次申请分配会使系统进入不安全状态？

（2）执行完序号为6的申请后，各进程的状态和各进程已占用的资源数？

30、三个进程A、B、C，共享两个缓冲区B1和B2。缓冲区B1中可存放n件产品，缓冲区B2中可存放m件产品。进程A每次生产一件产品并将其存入缓冲区B1中；进程B每次从缓冲区B1中取出一件产品后再把它送到缓冲区B2中；进程C每次从缓冲区B2中取出一件产品去消费。为防止把产品存入已满的缓冲区，或从空的缓冲区取产品、或重复取产品，试用PV操作实现它们之间的制约。

31、中断

32、进程控制块（Process Control Block）

33、文件控制块（FCB）

34、系统调用

35、虚设备

36、通道（I/O处理机）

37、死锁

38、当前目录（工作目录，值班目录）

39、磁盘调度

40、进程有无如下状态转换，为什么？

        （1）等待—运行         （2）就绪—等待

41、简述段式存储管理基本思想。

42、在Windows 2000 Server中，如何实现某个班级所有用户对某个文件夹的读写访问。

43、试写出V（s）原语的主要操作步骤。

44、进程控制块（Process Control Block）

45、文件控制块（FCB）

46、磁盘调度

47. Windows 2000除具有通用操作系统功能外，还具有哪些作为网络操作系统的主要功能？

48. 一个含五个逻辑记录的文件，系统把它以链接结构的形式组织在磁盘上，每个记录占用一个磁盘块，现要求在第一记录和第二记录之间插入一个新记录，简述它的操作过程。

49．在Windows 2000 Server中，如何实现某个班级所有用户对某个文件夹的读写访问。

50、在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：

（1）按FIFO调度算法将产生 次缺页中断，依次淘汰的页号为 ，缺页中断率为 。

（2）按LRU调度算法将产生 次缺页中断，依次淘汰的页号为 ，缺页中断率为 。

51、假定在单CPU条件下有下列要执行的作业：

作业 运行时间 优先级

    1 10 2

2 4 3

3 3 5

作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。

（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。

（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？

（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？

52、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问：

　①系统要设几个进程来完成这个任务？各自的工作是什么？

　②这些进程间有什么样的相互制约关系？

　③用P、V操作写出这些进程的同步算法。

53、考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：

（1）逻辑地址需要多少位表示？（二进制）

（2）绝对地址需要多少位表示？（二进制）

54．某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号 物理块号

0 5

1 10

2 4

3 7

则逻辑地址0A5C(H)所对应的物理地址是什么？

55、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下：

段号 主存起始地址 段长度

0 120 40

1 760 30

2 480 20

3 370 20

计算逻辑地址（2，15），（0，60），（3，18）的绝对地址是多少？

注：括号中第一个元素为段号，第二个元素为段内地址。

56．对于如下的页面访问序列：

1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

57、设公共汽车上有一位司机和一位售票员，它们的活动如下：

司机： 售票员：

启动车辆 售票

正常行车 开车门

到站停车 关车门

请分析司机与售票员之间的同步关系，如何用PV操作实现。

答案

1、解：

因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完之后，另一个用户再打印。

   设三个进程分别为A、B和C。

   设一个互斥信号量mutex，其初值为1。

2、解：

① 这个算法不对。因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。

改正：

A、B两进程要同步使用缓冲区Q。为此，设立两个信号量：

   empty表示缓冲区Q为空，初值为1;

   full表示缓冲区Q为满，初值为0。

算法框图如图1所示。

② 这个算法不对。因为A、B两个进程是并发的，它们共享一个临界资源，所以二者应互斥地使用该临界资源，在进入临界区时不存在A先B后的时序关系，而是哪个进程先到一步就先进入自己的临界区。

改正：

A、B两个进程应互斥地进入临界区。为此，设立一个信号量：互斥信号量mutex，其初值为1。

   算法框图如图2所示。

3、解：

①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。

②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。

③信号量含义及初值：

B1full­—— 缓冲区B1满，初值为0；

B1empty——缓冲区B1空，初值为0；

B2full­—— 缓冲区B2满，初值为0；

B2empty——缓冲区B2空，初值为0；

4、解：

      作业           周转时间           等待时间

   JOB1             7                    3 

   JOB2             5                    3 

   JOB3             4                    2

所有作业的平均周转时间5.33

5、解：

   (1) 非抢占式优先级算法

    (2) 和（3）

6、解：480K+154。

7、解：

   逻辑地址0A5C(H)所对应的二进制表示形式是：  0000 1010 0101 1100

   所对应的页号是：  2  （十进制）

   查页表，得到物理块号是：  11 （十进制）

   拼接后，得到物理地址：  2E5C(H)

8、解：

   FIFO淘汰算法：

 内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页中断为10。（这似乎是一个奇怪的现象，同时也告诉我们，操作系统是一个复杂的机构，直观是靠不住的！）

LRU淘汰算法：

内存块为3时，缺页中断为10；内存块为4时，缺页中断为8。

9、答

某航空公司为两旅行社a和b的顾客预订飞机票，飞机票是互斥内容。假设为a订完了机票，b就不能再订票。

10、答

一个生产者，一个消费者和一个产品之间关系是典型的进程同步问题。设信号量s为仓库内产品，p-v操作配对进行缺一不可。生产者进程将产品放入仓库后通知消费者可用；消费者进程在得知仓库有产品时取走，然后告诉生产者可继续生产。

11、解

UNIX系统中，进程的调度采用多级反馈队列轮转调度方式。

引起进程调度的时机有：（1）当前进程的时间片用完，由核心将当前进程放入下一级的优先级队列的末尾，并调度另一进程运行；（2）在当前进程执行了sleep例程，进入睡眠状态而放弃处理机时；（3）进程通过核心执行了自我终止的系统调用exit时；（4）在执行完系统调用而返回到用户态时，如果此时系统中已出现了更高优先级的进程在等待运行，此时核心将剥夺当前进程的执行；（5）当核心完成中断处理，控制被返回到用户态而要执行原进程时，若有更高优先级的进程在等待运行，等等。

12解：

当用户要求对一个文件实施多次读/写或其他操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，在大多数OS中都引入了“打开”（open）这一文件系统调用，当用户第一次请求对某文件进行操作时，先利用open系统调用将该文件打开。

在UNIX文件系统，打开文件/home/user01/myfile的过程四步：

（1）检索目录
    核心先调用检索目录过程namei从根目录或从当前目录开始，沿目录树查找指名文件的索引结点。在查找时，利用线性检索法，将文件路径名中的各分量名，与相应目录文件中的文件名逐一进行比较。若未找到指名文件，或者该文件不允许存取，便做出错处理；否则，进入第二步。

（2）分配内在索引结点

如果该文件已被其他用户打开，此时只需对在第一步中所找到的i结点，执行其引用计数加1的操作；否则，应为被打开文件分配一内存i结点，并调用磁盘读过程将磁盘i结点的内容拷贝到内存 i 结点中，并设置i.count为1。

（3）分配文件表
     这是指为已打标开的文件分配一个文件表项,使文件表项中的 f. node指向内存索引结点。通常还将读写指针f.offset置为 0，以表示从头开始读／写此文件；置读写标志 f．flag，及将文件的引用计数f．count加 1，并记入该表项的首址fp。

（4）分配用户文件描述表项

在用户文件描述表中取得一空表项。若成功，便将fp填入该表项中，并把该表项的序号fd作为文件描述符，写入调用进程的U区中。

13解：

利用安全算法对该时刻资源分配情况进行分析，如下图所示：

   Work         Need     Allocation     Work+Allocation    Finish

  P0   1  5  2  0      0 0 0 0      0 0 1 2        1  5  3  2       true

  P2   1  5  3  2      1 0 0 2      1 3 5 4        2  8  8  6       true

  P3   2  8  8  6      0 0 2 0      0 6 3 2        2  14 11  8       true

  P4   2  14 11  8     0 6 4 2      0 0 1 4        2  14 12  12       true

  P1   2  14 12 12      0 7 5 0     1 0 0 0        3  14 12  12       true

由以上分析可知，在该时刻存在着一个安全序列{P0，P2，P3，P4，P1}，故系统是安全的。

如果进程P1要求（0，4，2，0），系统假定可为P1分配资源，由此形成的资源变化情况如图示：

 已分配资源矩阵    需求资源矩阵     最多资源矩阵       可用资源向量

  P1    1  4  2  0      0  3  3  0        1  7  5  0        1  1  0  0

利用安全算法对该时刻资源分配情况进行分析，如下图所示：

   Work         Need     Allocation     Work+Allocation     Finish

  P0   1  1  0  0      0 0 0 0      0 0 1 2        1  1  1  2        true

  P2   1  1  1  2      1 0 0 2      1 3 5 4        2  4  6  6        true

  P3   2  4  6  6      0 0 2 0      0 6 3 2        2  10  9  8       true

  P4  2  10  9  8      0 6 4 2      0 0 1 4        2  10 10  12       true

  P1  2  10 10  12     0 3 3 0      1 4 2 0        3  14 12  12       true

由以上分析可知，可找到一个安全序列{P0，P2，P3，P4，P1}，故系统能立即满足进程的要求。

14、解：

因为分页磁盘占95%，主要是考虑页表的存储问题，挂起某个进程，可扩大进程的存储空间；更换更大容量的分页磁盘，可增加页表的分页速度，从而改善CPU的利用率。所以应选择（2）和（4）。

15、解：

0.85*1μ+0.15*2μ=1.15μs

16、解：

var rmutex, wmutex:semaphore:=1,1;
readcount: integer:=0;

writer :
       begin
         repeat
           wait(wmutex);
           perform write operation;
           signal (wmutex);
         until false;
       end

reader:
       begin
         repeat
           wait(rmutex);
           if readcount=0 then wait(wmutex);
           readcount:=readcount+1;
           signal(rmutex);
             ┇
           Perform read operation;
             ┇
           wait(rmutex);
           readcount:=readcount-1;
           if readcount=0 then signal(wmutex);
           signal(rmutex);
         until false;
       end

17、答：

核心态是CPU运行操作系统代码。用户态是CPU运行用户程序代码的状态。通过系统调用、Trap、中断可以使得系统从用户态到核心态。特权指令指的是只能由操作系统而不是用户调用的指令。

（1）是。（2）否 （3）否 （4）是 （5）是 （6）否

18、答：

经过三次中断后，在第4个队列中终止运行

19、答：

因为一张页表只能包含1024/4=256个页表项。而页的大小为210，所以共需要32-10=22位来表示页号。而每一级页表只能处理22位中的8位，所以共需要3级。有两级页表有28个页表项，另一级只有26个页表项

20、答：18位
21答：

（a）3 （b）229/28＝221，因此为21页（c）8    （d）3＋21＋8 ＝ 32

22、解：

（1）FIFO算法总是淘汰最先进入内存页面，即选择在内存中驻留时间最长的页予以淘汰。算法如图所示：

缺页率=13/20=65%

（2）LRU算法是最近最久未使用的页面予以淘汰。算法如图所示：

缺页率=14/20=70%

23、解：

200ns内得到满足的访问占用全部访问的95％。5％的访问造成缺页，其中40%的需要7ms。因此，5％×40％＝2％的访问需要7ms。

    类似地，5％×60％＝3％的访问需要15ms。把所有的时间转换为us，

结果如下：

有效访问时间＝0.95×0.2 ＋ 0.02×7000＋0.03×15000

    有效访问时间＝590.19us

24、答：

（19456*16*1/5400+（19456-1）*2=3498ms

25、答：

（a）2182 （b）1023 （c）1724

26、答： 

如果电源突然切断，存储在磁盘上的文件系统可能还处在一个不一致的状态。例如，将空闲表中的一个块增加到一个文件的写操作结束之后将发生什么事情？假设磁盘中的文件的信息已经更新，记录了刚增加的块。但是假设常用的空闲表的信息被高速缓存存在主存中。虽然在主存中空闲表数据不再指向新增的块，但是磁盘上的空闲表信息仍然指向该块。如果系统的电源突然切断，当重启的时候，该块将既分配给了文件，又被包括在空闲表中。

27、答：

210×（10＋28＋216＋254）＝17247250432字节

28、解：

所谓死琐，是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。

死锁预防的措施有：（1）屏弃“请求和保持”条件，优点是简单、易于实现且很安全；（2）屏弃“不剥夺”条件，在采用这种方法预防死锁时，进程是在需要资源时才提出请求。这样，一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。这种预防死锁方法，实现起来比较复杂，且要付出很大代价。（3） 摒弃“环路等待”条件，在这种方法中规定，系统将所有的资源按类型进行线形排队，并赋予不同的序号。这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量，都有较明显的改善。

29、解：

（1）执行完前3次申请后，尚有2个资源空闲，若第4次P1再申请1个资源，则还有1个资源空闲，这个资源无论分给那个进程都会使系统进入不安全状态。若不执行第4次而执行第5次申请，则没有空闲资源，系统也会进入不安全状态。（2）执行完前3次申请后，再执行完序号为6的申请，则进程P1资源数为4，P2资源数为6，P3资源数为2，这样，P2有足够的资源而完成，可释放6个资源；于是可用资源增至6个；以后可将4个资源分配给进程P1，使之运行，待P1完成后，将释放8个资源，P3便能获得足够的资源，从而使P1、P2、P3每个进程都能顺利完成。

30、解：

A（R）、B（C）、C（P）。
（1）进程间关系为：A→B1→B→B2→C
A受B制约：当B未把B1信息取走，A不能输入下一信息。
C受B制约：当B未把B1信息送入B2，C不能打印B2信息。
B同时受A、C约束：把A未把信息写入B1；C未把B2信息印出，则B不能把B1信息送至B2。
（2）设四个信号量。它们初值均为零
     A私用信号量S1空。（为“0”表示B1空）
     B私用信号量S1满。（为“1”表示B1满）
     B私用信号量S2空。（为“0”表示B2空）
     C私用信号量S2满。（为“1”表示B2满）
PV原语同步算法如下：
  A ：  输入到B1→V（S1满）→P（S1空）过程循环往复
  B：   P（S1满）→B1的信息送入B2→V（S1空）→V（S2满）→P（S2空）过程循环往复
  C：   P（S2满）→B2的信息被打印→V（S2空）过程循环往复

（5）状态转换图如下：

31、答

中断是现代计算机系统中基本设施之一,它起着通讯联络作用,协调系统对各种外部事件的响应和处理.中断是实现多道程序的必要条件.

32、答

系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。

33、答

文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。文件控制块是文件存在的标志。

34、答

 用户程序中对操作系统的调用称为系统调用（system call）

35、答

 在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚设备。（将慢速的独占设备改造成多个用户可共享的设备，提高设备的利用率）

36、答

通道是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外部设备实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入，输出操作可与CPU并行操作。

37、答

  一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

38、答

  为了提高文件检索速度，文件系统向用户提供了一个当前正在使用的目录，称为当前目录。查找一个文件可从当前目录开始，使用部分路径名；当前目录可根据需要任意改变。当前目录一般存放在内存。

39、答

当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效。

40、解答：

        （1）不能：等待－就绪－运行

        （2）不能：就绪－运行－等待

41、答：

a、用户程序划分

  按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。

b、内存划分

  内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定。

c、内存分配

  以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。

d、管理

段表：它记录了段号，段的首（地）址和长度之间的关系。每一个程序设一个段表

空闲块管理：记录了空闲区起始地址和长度。

内存的分配算法：首先适配；最佳适配；最坏适配

42、答

（1）选择（或设置）一个主域域服务器。

（2）在域上首先定义班级为一个组，而班级所有成员都归属这个组。

（3）对文件夹进行共享设置，并添加班级组，其权限为安全控制。

（4）设置文件夹的安全性，添加班级组，其访问权限为选择性访问中的读写。

43、答

（1）S值加1；

（2）若S≤0，从等待S的队列中移出一个进程，由阻塞状态变为就绪状态，插入就绪队列，当前进程继续运行；

（3）若S>0，当前进程继续运行。

44、答

系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。

45、答

文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。文件控制块是文件存在的标志。

46、答

 当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效。

47、解答：

（1）实现网络中各节点机之间的通信；

（2）实现网络中的资源共享；

（3）提供多种网络服务软件；

（4）提供网络用户的应用程序接口。

48、答

答：从文件目录中找到该文件，按址读出第一个记录；（1.5分）

取出第一个记录块中指针，存放到新记录的指针位置；（1.5分）

把新记录占用的物理块号填入第一个记录的指针位置；（1.5分）

启动磁盘把第一个记录和新记录写到指字的磁盘块上。（1.5分）

49、答

（1）选择（或设置）一个主域域服务器。

（2）在域上首先定义班级为一个组，而班级所有成员都归属这个组。

（3）对文件夹进行共享设置，并添加班级组，其权限为安全控制。

（4）设置文件夹的安全性，添加班级组，其访问权限为选择性访问中的读写。

50、答

（1）按FIFO调度算法将产生5次缺页中断；依次淘汰的页号为：0，1，2；

缺页中断率为：5/10=50%

（2）按LRU调度算法将产生6次缺页中断；依次淘汰的页号为：2，0，1，3；

缺页中断率为：6/10=60%

51. 解：
(1) 非抢占式优先级算法
作业1 作业3 作业2
| | | | t
0 10 13 17

(2) 和（3）
作业 到达时间 运行时间 完成时间 周转时间 带权周转时间
1 0 10 10 10 1.0
2 1 4 17 16 4.0
3 2 3 13 11 3.7
平均周转时间 12.3
平均带权周转时间 2.9

52. 解：
①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。
　 ②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。
③信号量含义及初值：
B1full—— 缓冲区B1满，初值为0；
B1empty——缓冲区B1空，初值为0；
B2full—— 缓冲区B2满，初值为0；
B2empty——缓冲区B2空，初值为0；
R进程 C进程 P进程

输入信息写入缓冲区B1 P(B1full) P(B2full)
V(B1full) 从B1中取出信息 从B2中取出信息进行打印
P(B1empty) 加工信息 V(B2empty)
结果送入B2
V(B1empty)
V(B2full)
P(B2empty)

53、解：
因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。
（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。
（2）页的绝对地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。

54．解：125C（H） （要求写出计算步骤）
[分析]页式存储管理的逻辑地址分为两部分：页号和页内地址。
由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。
逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码 “000 10” 为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。

55、解：
段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址<段长度，检查地址是否越界；（3）若不越界，则绝对地址=该段的主存起始地址+段内地址。
逻辑地址（2，15）查段表得段长度为20，段内地址15<20，地址不越界，段号2查表得段首地址为480，于是绝对地址为480+15=495。
逻辑地址（0，60）查段表得段长度为40，段内地址60>40，地址越界，系统发出“地址越界”中断。
逻辑地址（3，18）查段表得段长度为20，段内地址18<20，地址不越界，段号3查表得段首地址为370，于是绝对地址=370+18=388。

56．解：
FIFO淘汰算法：
内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页中断为10。（这似乎是一个奇怪的现象，同时也告诉我们，操作系统是一个复杂的机构，直观是靠不住的！）
LRU淘汰算法：
内存块为3时，缺页中断为10；内存块为4时，缺页中断为8。
（具体计算过程省略，解答时请同学们写出计算过程。）

57、答：

为了安全起见，显然要求：关车门后才能启动车辆；到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1、S2分别表示可以开车和可以开门，S1的初值为1，S2的初值为0。用PV操作实现司机进程和售票员进程同步的算法描述如下：
司机： 售票员：
P（S1） 售票
启动车辆 P（S2）
正常行车 开车门
到站停车 关车门
V（S2） V（S1）

另外，程序中PV操作出现的顺序与信号量的初值设置有关，以本题为例，算法如下描述时，S1、S2的初值均应为0。
司机： 售票员：
正常行车 售票
到站停车 P（S2）
V（S2） 开车门
P（S1） 关车门
启动车辆 V（S1）

应 用 题

1、 设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P、V操作写出这些进程使用打印机的算法。

2、判断下面的同步问题的算法是否正确？若有错，请指出错误原因并予以改正。

（1）设A、B两进程共用一个缓冲区Q，A向Q写入信息，B则从Q读出信息，算法框图如图所示。

　　　　　　注：信号量S的初值为0

（2）设A、B为两个并发进程，它们共享一临界资源。其运行临界区的算法框图如图所示。

　　　　　　注：信号量S1、S2的初值均为0

3、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问：

①系统要设几个进程来完成这个任务？各自的工作是什么？

②这些进程间有什么样的相互制约关系？

③用P、V操作写出这些进程的同步算法。

4、设有三个批作业JOB1、JOB2、JOB3，其到达时间、处理时间及完成时间如下：

作业 　　作业到达时间（时） 　　开始处理时间（时） 　　处理完成时间（时）

JOB1 　　　15 　　　　　　18 　　　　　　　22

JOB2 　　  18 　　　　　　21 　　　　　　　23

JOB3 　 　17 　　　　　　19 　　　 　　　　21

试计算：

（1）各个作业的周转时间；

（2）所有作业的平均周转时间；

5、假定在单CPU条件下有下列要执行的作业：

作业        运行时间     优先级

1           10           2

2           4            3

3           3            5

作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。

（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。

（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？

（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？

6、某段表内容如下：

段号        段首地址      段长度

0           120K          40K

1           760K          30K

2           480K          20K

3           370K          20K

一逻辑地址为（2，154）的实际物理地址是多少？

7、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号         物理块号

0            3

1            7

2            11

3            8

则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。

8、对于如下的页面访问序列：
1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

9、试以某航空公司为两旅行社a和b的顾客预订飞机票为例，说明互斥的含义。

10、试以生产者--消费者问题为例，用ＰＶ操作说明进程同步问题的实质。

11、在UNIX 系统中，其进程调度方式是什么？引起进程调度的时机有那些？

12、为什么要打开文件？叙述在UNIX文件系统，打开文件/home/user01/myfile的过程？

13、某一系统进程的资源分配“瞬间状态”为

             已分配资源矩阵       最多资源矩阵       可用资源向量

  P0          0  0  1  2           0  0  1  2         1  5   2  0

  P1          1  0  0  0           1  7  5  0

  P2          1  3  5  4           2  3  5  6

  P3          0  6  3  2           0  6  5  2

  P4          0  0  1  4           0  6  5  6

使用银行家算法回答：系统是否安全？如果进程P1要求(0，4，2，0)，系统能否立即满足进程的要求？

14、考虑一个请求分页系统，测得如下的时间利用率：

CPU：20%；分页磁盘：97.7%；其它外设：5%

下列措施中，哪个(些)可改善CPU的利用率？说明理由：

(1)更换速度更快的CPU (2)更换更大容量的分页磁盘 (3)增加内存中用户进程数 (4)挂起内存中的某个(些)用户进程

15、 对于一个利用快表且页表存于内存的分页系统，假定CPU一次访问时间为1us，访问快表的时间可以忽略不记。如果85%的地址影射可直接通过快表完成，那么进程完成一次内存读写的平均有效时间是多少？

16、用信号量和P，V操作描述读者-写者问题：即允许多个读者同时读一个共享对象，但绝不允许一个写者和其它进程同时访问共享对象。

17、什么为核心态、用户态、特权指令？下列哪些指令为特权指令？

（1)改变存储器管理寄存器（2）写程序计数器（3）读日历钟（4）设置日历钟      （5）改变处理器优先级（6）写指令寄存器

18、一个多级反馈队列的系统中，一个使用CPU较多的进程需要执行50秒。如果第一个队列时间片为5，并且较低一级的时间片是上一级的时间片的2倍，那么这个作业会被中断多少次？当他终止的时候，处于那一级队列？

18、一个多级反馈队列的系统中，一个使用CPU较多的进程需要执行50秒。如果第一个队列时间片为5，并且较低一级的时间片是上一级的时间片的2倍，那么这个作业会被中断多少次？当他终止的时候，处于那一级队列？
19、某计算机有32位虚地址空间，且页大小为1024字节。每个页表项长4个字节。因为每个页表都必须包含在一页中，所以使用多级页表，问共需要几级？

20、在某简单分页系统中，有224字节的物理内存，256页的逻辑地址空间并且页的大小为210字节，问逻辑地址为多少位？    

21、在某段页式系统中，虚地址空间包含了8个段，段长为229字节。硬件把每个段分成大小为256字节的页。问虚地址中有多少位可以用于指定：

    （a）段号？（b）页号？ （c）页内偏移量 （d）整个虚地址

22、已知某程序访问以下页面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、6、2、1、3、6、2，如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。（1）FIFO替换算法（2）LRU替换算法

23、某系统使用请求分页存储管理，如果页在内存中，满足一个内存请求需要200ns。如果页不在内存，如有空闲的页框或者没有修改的换出的页，则请求需要7ms。如果替换出的页已经被修改，则需要15ms，如果缺页率是5％，并且60％的时间用于修改要换出的页，问有效访问时间是多长？假设系统只运行一个进程且页交换时CPU空闲 。 

24、一个磁盘有19456个柱面，16个读写头，并且每个磁道有63个扇区。磁盘以5400rpm的速度旋转，在相邻的磁道之间寻道时间是2ms。假定读写头在磁道0上，则读整个磁盘需要多少时间？

25、在一个磁盘上，有1000个柱面，从0～999。假定最后服务的请求是在磁道756上，并且读写磁头正在向磁道0移动。在按照FIFO顺序排列的队列中包含了如下磁道上的请求：811、348、153、968、407、500。用下面的算法计算为了满足所有的磁盘队列中的请求，磁盘臂必须移的磁盘的数目。

（a）IFO （b）SSTF （c）SCAN

26、大多数操作系统通过在主存中高速缓存存某些重要的文件系统数据来改善系统性能，这样的操作系统要求计算机关机之后才能切断电源。为什么？

27、在某系统中，一个目录项可以存储至多13个磁盘块的地址。前10个地址指向文件的前10个块。第11个地址指向一个中间块。第12个地址指向一个二重间接块。第13个地址指向一个三重间接块。每一个间接块可以容纳256个指针。一个块的大小是1024个字节，那么一个文件可以达到多大？

28、什么是死锁？死锁预防的措施有哪些？为什么？

29、假设某系统有同类资源12个，有三个进程P1，P2，P3来共享，已知P1、P2、P3所需要资源总数分别为8，6，9，它们申请资源的次序和数量如表所示，系统采用银行家算法为它们分配资源。

（1）哪次申请分配会使系统进入不安全状态？

（2）执行完序号为6的申请后，各进程的状态和各进程已占用的资源数？

30、三个进程A、B、C，共享两个缓冲区B1和B2。缓冲区B1中可存放n件产品，缓冲区B2中可存放m件产品。进程A每次生产一件产品并将其存入缓冲区B1中；进程B每次从缓冲区B1中取出一件产品后再把它送到缓冲区B2中；进程C每次从缓冲区B2中取出一件产品去消费。为防止把产品存入已满的缓冲区，或从空的缓冲区取产品、或重复取产品，试用PV操作实现它们之间的制约。

31、中断

32、进程控制块（Process Control Block）

33、文件控制块（FCB）

34、系统调用

35、虚设备

36、通道（I/O处理机）

37、死锁

38、当前目录（工作目录，值班目录）

39、磁盘调度

40、进程有无如下状态转换，为什么？

        （1）等待—运行         （2）就绪—等待

41、简述段式存储管理基本思想。

42、在Windows 2000 Server中，如何实现某个班级所有用户对某个文件夹的读写访问。

43、试写出V（s）原语的主要操作步骤。

44、进程控制块（Process Control Block）

45、文件控制块（FCB）

46、磁盘调度

47. Windows 2000除具有通用操作系统功能外，还具有哪些作为网络操作系统的主要功能？

48. 一个含五个逻辑记录的文件，系统把它以链接结构的形式组织在磁盘上，每个记录占用一个磁盘块，现要求在第一记录和第二记录之间插入一个新记录，简述它的操作过程。

49．在Windows 2000 Server中，如何实现某个班级所有用户对某个文件夹的读写访问。

50、在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：

（1）按FIFO调度算法将产生 次缺页中断，依次淘汰的页号为 ，缺页中断率为 。

（2）按LRU调度算法将产生 次缺页中断，依次淘汰的页号为 ，缺页中断率为 。

51、假定在单CPU条件下有下列要执行的作业：

作业 运行时间 优先级

    1 10 2

2 4 3

3 3 5

作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。

（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。

（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？

（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？

52、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问：

　①系统要设几个进程来完成这个任务？各自的工作是什么？

　②这些进程间有什么样的相互制约关系？

　③用P、V操作写出这些进程的同步算法。

53、考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：

（1）逻辑地址需要多少位表示？（二进制）

（2）绝对地址需要多少位表示？（二进制）

54．某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号 物理块号

0 5

1 10

2 4

3 7

则逻辑地址0A5C(H)所对应的物理地址是什么？

55、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下：

段号 主存起始地址 段长度

0 120 40

1 760 30

2 480 20

3 370 20

计算逻辑地址（2，15），（0，60），（3，18）的绝对地址是多少？

注：括号中第一个元素为段号，第二个元素为段内地址。

56．对于如下的页面访问序列：

1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5
当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

57、设公共汽车上有一位司机和一位售票员，它们的活动如下：

司机： 售票员：

启动车辆 售票

正常行车 开车门

到站停车 关车门

请分析司机与售票员之间的同步关系，如何用PV操作实现。

答案

1、解：

因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完之后，另一个用户再打印。

   设三个进程分别为A、B和C。

   设一个互斥信号量mutex，其初值为1。

2、解：

① 这个算法不对。因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。

改正：

A、B两进程要同步使用缓冲区Q。为此，设立两个信号量：

   empty表示缓冲区Q为空，初值为1;

   full表示缓冲区Q为满，初值为0。

算法框图如图1所示。

② 这个算法不对。因为A、B两个进程是并发的，它们共享一个临界资源，所以二者应互斥地使用该临界资源，在进入临界区时不存在A先B后的时序关系，而是哪个进程先到一步就先进入自己的临界区。

改正：

A、B两个进程应互斥地进入临界区。为此，设立一个信号量：互斥信号量mutex，其初值为1。

   算法框图如图2所示。

3、解：

①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。

②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。

③信号量含义及初值：

B1full­—— 缓冲区B1满，初值为0；

B1empty——缓冲区B1空，初值为0；

B2full­—— 缓冲区B2满，初值为0；

B2empty——缓冲区B2空，初值为0；

4、解：

      作业           周转时间           等待时间

   JOB1             7                    3 

   JOB2             5                    3 

   JOB3             4                    2

所有作业的平均周转时间5.33

5、解：

   (1) 非抢占式优先级算法

    (2) 和（3）

6、解：480K+154。

7、解：

   逻辑地址0A5C(H)所对应的二进制表示形式是：  0000 1010 0101 1100

   所对应的页号是：  2  （十进制）

   查页表，得到物理块号是：  11 （十进制）

   拼接后，得到物理地址：  2E5C(H)

8、解：

   FIFO淘汰算法：

 内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页中断为10。（这似乎是一个奇怪的现象，同时也告诉我们，操作系统是一个复杂的机构，直观是靠不住的！）

LRU淘汰算法：

内存块为3时，缺页中断为10；内存块为4时，缺页中断为8。

9、答

某航空公司为两旅行社a和b的顾客预订飞机票，飞机票是互斥内容。假设为a订完了机票，b就不能再订票。

10、答

一个生产者，一个消费者和一个产品之间关系是典型的进程同步问题。设信号量s为仓库内产品，p-v操作配对进行缺一不可。生产者进程将产品放入仓库后通知消费者可用；消费者进程在得知仓库有产品时取走，然后告诉生产者可继续生产。

11、解

UNIX系统中，进程的调度采用多级反馈队列轮转调度方式。

引起进程调度的时机有：（1）当前进程的时间片用完，由核心将当前进程放入下一级的优先级队列的末尾，并调度另一进程运行；（2）在当前进程执行了sleep例程，进入睡眠状态而放弃处理机时；（3）进程通过核心执行了自我终止的系统调用exit时；（4）在执行完系统调用而返回到用户态时，如果此时系统中已出现了更高优先级的进程在等待运行，此时核心将剥夺当前进程的执行；（5）当核心完成中断处理，控制被返回到用户态而要执行原进程时，若有更高优先级的进程在等待运行，等等。

12解：

当用户要求对一个文件实施多次读/写或其他操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，在大多数OS中都引入了“打开”（open）这一文件系统调用，当用户第一次请求对某文件进行操作时，先利用open系统调用将该文件打开。

在UNIX文件系统，打开文件/home/user01/myfile的过程四步：

（1）检索目录
    核心先调用检索目录过程namei从根目录或从当前目录开始，沿目录树查找指名文件的索引结点。在查找时，利用线性检索法，将文件路径名中的各分量名，与相应目录文件中的文件名逐一进行比较。若未找到指名文件，或者该文件不允许存取，便做出错处理；否则，进入第二步。

（2）分配内在索引结点

如果该文件已被其他用户打开，此时只需对在第一步中所找到的i结点，执行其引用计数加1的操作；否则，应为被打开文件分配一内存i结点，并调用磁盘读过程将磁盘i结点的内容拷贝到内存 i 结点中，并设置i.count为1。

（3）分配文件表
     这是指为已打标开的文件分配一个文件表项,使文件表项中的 f. node指向内存索引结点。通常还将读写指针f.offset置为 0，以表示从头开始读／写此文件；置读写标志 f．flag，及将文件的引用计数f．count加 1，并记入该表项的首址fp。

（4）分配用户文件描述表项

在用户文件描述表中取得一空表项。若成功，便将fp填入该表项中，并把该表项的序号fd作为文件描述符，写入调用进程的U区中。

13解：

利用安全算法对该时刻资源分配情况进行分析，如下图所示：

   Work         Need     Allocation     Work+Allocation    Finish

  P0   1  5  2  0      0 0 0 0      0 0 1 2        1  5  3  2       true

  P2   1  5  3  2      1 0 0 2      1 3 5 4        2  8  8  6       true

  P3   2  8  8  6      0 0 2 0      0 6 3 2        2  14 11  8       true

  P4   2  14 11  8     0 6 4 2      0 0 1 4        2  14 12  12       true

  P1   2  14 12 12      0 7 5 0     1 0 0 0        3  14 12  12       true

由以上分析可知，在该时刻存在着一个安全序列{P0，P2，P3，P4，P1}，故系统是安全的。

如果进程P1要求（0，4，2，0），系统假定可为P1分配资源，由此形成的资源变化情况如图示：

 已分配资源矩阵    需求资源矩阵     最多资源矩阵       可用资源向量

  P1    1  4  2  0      0  3  3  0        1  7  5  0        1  1  0  0

利用安全算法对该时刻资源分配情况进行分析，如下图所示：

   Work         Need     Allocation     Work+Allocation     Finish

  P0   1  1  0  0      0 0 0 0      0 0 1 2        1  1  1  2        true

  P2   1  1  1  2      1 0 0 2      1 3 5 4        2  4  6  6        true

  P3   2  4  6  6      0 0 2 0      0 6 3 2        2  10  9  8       true

  P4  2  10  9  8      0 6 4 2      0 0 1 4        2  10 10  12       true

  P1  2  10 10  12     0 3 3 0      1 4 2 0        3  14 12  12       true

由以上分析可知，可找到一个安全序列{P0，P2，P3，P4，P1}，故系统能立即满足进程的要求。

14、解：

因为分页磁盘占95%，主要是考虑页表的存储问题，挂起某个进程，可扩大进程的存储空间；更换更大容量的分页磁盘，可增加页表的分页速度，从而改善CPU的利用率。所以应选择（2）和（4）。

15、解：

0.85*1μ+0.15*2μ=1.15μs

16、解：

var rmutex, wmutex:semaphore:=1,1;
readcount: integer:=0;

writer :
       begin
         repeat
           wait(wmutex);
           perform write operation;
           signal (wmutex);
         until false;
       end

reader:
       begin
         repeat
           wait(rmutex);
           if readcount=0 then wait(wmutex);
           readcount:=readcount+1;
           signal(rmutex);
             ┇
           Perform read operation;
             ┇
           wait(rmutex);
           readcount:=readcount-1;
           if readcount=0 then signal(wmutex);
           signal(rmutex);
         until false;
       end

17、答：

核心态是CPU运行操作系统代码。用户态是CPU运行用户程序代码的状态。通过系统调用、Trap、中断可以使得系统从用户态到核心态。特权指令指的是只能由操作系统而不是用户调用的指令。

（1）是。（2）否 （3）否 （4）是 （5）是 （6）否

18、答：

经过三次中断后，在第4个队列中终止运行

19、答：

因为一张页表只能包含1024/4=256个页表项。而页的大小为210，所以共需要32-10=22位来表示页号。而每一级页表只能处理22位中的8位，所以共需要3级。有两级页表有28个页表项，另一级只有26个页表项

20、答：18位
21答：

（a）3 （b）229/28＝221，因此为21页（c）8    （d）3＋21＋8 ＝ 32

22、解：

（1）FIFO算法总是淘汰最先进入内存页面，即选择在内存中驻留时间最长的页予以淘汰。算法如图所示：

缺页率=13/20=65%

（2）LRU算法是最近最久未使用的页面予以淘汰。算法如图所示：

缺页率=14/20=70%

23、解：

200ns内得到满足的访问占用全部访问的95％。5％的访问造成缺页，其中40%的需要7ms。因此，5％×40％＝2％的访问需要7ms。

    类似地，5％×60％＝3％的访问需要15ms。把所有的时间转换为us，

结果如下：

有效访问时间＝0.95×0.2 ＋ 0.02×7000＋0.03×15000

    有效访问时间＝590.19us

24、答：

（19456*16*1/5400+（19456-1）*2=3498ms

25、答：

（a）2182 （b）1023 （c）1724

26、答： 

如果电源突然切断，存储在磁盘上的文件系统可能还处在一个不一致的状态。例如，将空闲表中的一个块增加到一个文件的写操作结束之后将发生什么事情？假设磁盘中的文件的信息已经更新，记录了刚增加的块。但是假设常用的空闲表的信息被高速缓存存在主存中。虽然在主存中空闲表数据不再指向新增的块，但是磁盘上的空闲表信息仍然指向该块。如果系统的电源突然切断，当重启的时候，该块将既分配给了文件，又被包括在空闲表中。

27、答：

210×（10＋28＋216＋254）＝17247250432字节

28、解：

所谓死琐，是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。

死锁预防的措施有：（1）屏弃“请求和保持”条件，优点是简单、易于实现且很安全；（2）屏弃“不剥夺”条件，在采用这种方法预防死锁时，进程是在需要资源时才提出请求。这样，一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。这种预防死锁方法，实现起来比较复杂，且要付出很大代价。（3） 摒弃“环路等待”条件，在这种方法中规定，系统将所有的资源按类型进行线形排队，并赋予不同的序号。这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量，都有较明显的改善。

29、解：

（1）执行完前3次申请后，尚有2个资源空闲，若第4次P1再申请1个资源，则还有1个资源空闲，这个资源无论分给那个进程都会使系统进入不安全状态。若不执行第4次而执行第5次申请，则没有空闲资源，系统也会进入不安全状态。（2）执行完前3次申请后，再执行完序号为6的申请，则进程P1资源数为4，P2资源数为6，P3资源数为2，这样，P2有足够的资源而完成，可释放6个资源；于是可用资源增至6个；以后可将4个资源分配给进程P1，使之运行，待P1完成后，将释放8个资源，P3便能获得足够的资源，从而使P1、P2、P3每个进程都能顺利完成。

30、解：

A（R）、B（C）、C（P）。
（1）进程间关系为：A→B1→B→B2→C
A受B制约：当B未把B1信息取走，A不能输入下一信息。
C受B制约：当B未把B1信息送入B2，C不能打印B2信息。
B同时受A、C约束：把A未把信息写入B1；C未把B2信息印出，则B不能把B1信息送至B2。
（2）设四个信号量。它们初值均为零
     A私用信号量S1空。（为“0”表示B1空）
     B私用信号量S1满。（为“1”表示B1满）
     B私用信号量S2空。（为“0”表示B2空）
     C私用信号量S2满。（为“1”表示B2满）
PV原语同步算法如下：
  A ：  输入到B1→V（S1满）→P（S1空）过程循环往复
  B：   P（S1满）→B1的信息送入B2→V（S1空）→V（S2满）→P（S2空）过程循环往复
  C：   P（S2满）→B2的信息被打印→V（S2空）过程循环往复

（5）状态转换图如下：

31、答

中断是现代计算机系统中基本设施之一,它起着通讯联络作用,协调系统对各种外部事件的响应和处理.中断是实现多道程序的必要条件.

32、答

系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。

33、答

文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。文件控制块是文件存在的标志。

34、答

 用户程序中对操作系统的调用称为系统调用（system call）

35、答

 在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚设备。（将慢速的独占设备改造成多个用户可共享的设备，提高设备的利用率）

36、答

通道是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外部设备实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入，输出操作可与CPU并行操作。

37、答

  一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

38、答

  为了提高文件检索速度，文件系统向用户提供了一个当前正在使用的目录，称为当前目录。查找一个文件可从当前目录开始，使用部分路径名；当前目录可根据需要任意改变。当前目录一般存放在内存。

39、答

当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效。

40、解答：

        （1）不能：等待－就绪－运行

        （2）不能：就绪－运行－等待

41、答：

a、用户程序划分

  按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。

b、内存划分

  内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定。

c、内存分配

  以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。

d、管理

段表：它记录了段号，段的首（地）址和长度之间的关系。每一个程序设一个段表

空闲块管理：记录了空闲区起始地址和长度。

内存的分配算法：首先适配；最佳适配；最坏适配

42、答

（1）选择（或设置）一个主域域服务器。

（2）在域上首先定义班级为一个组，而班级所有成员都归属这个组。

（3）对文件夹进行共享设置，并添加班级组，其权限为安全控制。

（4）设置文件夹的安全性，添加班级组，其访问权限为选择性访问中的读写。

43、答

（1）S值加1；

（2）若S≤0，从等待S的队列中移出一个进程，由阻塞状态变为就绪状态，插入就绪队列，当前进程继续运行；

（3）若S>0，当前进程继续运行。

44、答

系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。

45、答

文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。文件控制块是文件存在的标志。

46、答

 当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效。

47、解答：

（1）实现网络中各节点机之间的通信；

（2）实现网络中的资源共享；

（3）提供多种网络服务软件；

（4）提供网络用户的应用程序接口。

48、答

答：从文件目录中找到该文件，按址读出第一个记录；（1.5分）

取出第一个记录块中指针，存放到新记录的指针位置；（1.5分）

把新记录占用的物理块号填入第一个记录的指针位置；（1.5分）

启动磁盘把第一个记录和新记录写到指字的磁盘块上。（1.5分）

49、答

（1）选择（或设置）一个主域域服务器。

（2）在域上首先定义班级为一个组，而班级所有成员都归属这个组。

（3）对文件夹进行共享设置，并添加班级组，其权限为安全控制。

（4）设置文件夹的安全性，添加班级组，其访问权限为选择性访问中的读写。

50、答

（1）按FIFO调度算法将产生5次缺页中断；依次淘汰的页号为：0，1，2；

缺页中断率为：5/10=50%

（2）按LRU调度算法将产生6次缺页中断；依次淘汰的页号为：2，0，1，3；

缺页中断率为：6/10=60%

51. 解：
(1) 非抢占式优先级算法
作业1 作业3 作业2
| | | | t
0 10 13 17

(2) 和（3）
作业 到达时间 运行时间 完成时间 周转时间 带权周转时间
1 0 10 10 10 1.0
2 1 4 17 16 4.0
3 2 3 13 11 3.7
平均周转时间 12.3
平均带权周转时间 2.9

52. 解：
①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。
　 ②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。
③信号量含义及初值：
B1full—— 缓冲区B1满，初值为0；
B1empty——缓冲区B1空，初值为0；
B2full—— 缓冲区B2满，初值为0；
B2empty——缓冲区B2空，初值为0；
R进程 C进程 P进程

输入信息写入缓冲区B1 P(B1full) P(B2full)
V(B1full) 从B1中取出信息 从B2中取出信息进行打印
P(B1empty) 加工信息 V(B2empty)
结果送入B2
V(B1empty)
V(B2full)
P(B2empty)

53、解：
因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。
（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。
（2）页的绝对地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。

54．解：125C（H） （要求写出计算步骤）
[分析]页式存储管理的逻辑地址分为两部分：页号和页内地址。
由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。
逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码 “000 10” 为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。

55、解：
段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址<段长度，检查地址是否越界；（3）若不越界，则绝对地址=该段的主存起始地址+段内地址。
逻辑地址（2，15）查段表得段长度为20，段内地址15<20，地址不越界，段号2查表得段首地址为480，于是绝对地址为480+15=495。
逻辑地址（0，60）查段表得段长度为40，段内地址60>40，地址越界，系统发出“地址越界”中断。
逻辑地址（3，18）查段表得段长度为20，段内地址18<20，地址不越界，段号3查表得段首地址为370，于是绝对地址=370+18=388。

56．解：
FIFO淘汰算法：
内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页中断为10。（这似乎是一个奇怪的现象，同时也告诉我们，操作系统是一个复杂的机构，直观是靠不住的！）
LRU淘汰算法：
内存块为3时，缺页中断为10；内存块为4时，缺页中断为8。
（具体计算过程省略，解答时请同学们写出计算过程。）

57、答：

为了安全起见，显然要求：关车门后才能启动车辆；到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1、S2分别表示可以开车和可以开门，S1的初值为1，S2的初值为0。用PV操作实现司机进程和售票员进程同步的算法描述如下：
司机： 售票员：
P（S1） 售票
启动车辆 P（S2）
正常行车 开车门
到站停车 关车门
V（S2） V（S1）

另外，程序中PV操作出现的顺序与信号量的初值设置有关，以本题为例，算法如下描述时，S1、S2的初值均应为0。
司机： 售票员：
正常行车 售票
到站停车 P（S2）
V（S2） 开车门
P（S1） 关车门
启动车辆 V（S1）