期末考试

1. 试说明操作系统与硬件、其他系统软件以及用户之间的关系。

• 操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充，其主要作用是管理硬件设备，提高它们的利用率和系统吞吐量，并为用户和应用程序提供一个简单的接口，以便于用户和应用程序使用硬件设备。

2. OS具有哪几大特征？它们之间有何关系？

• OS具有并发、共享、虚拟和异步这四个基本特征。它们之间的关系包含以下几个方面。
  • 并发和共享是OS最基本的特征。为了提高计算机资源的利用率，OS必然要采用多道程序设计技术，使多个程序共享系统的资源、并发地执行。
  • 并发性和共享性互为存在的条件。一方面，资源的共享是以程序（进程）的并发执行为条件的，若系统不允许程序并发执行，就不会存在资源共享问题；另一方面，若系统不能对资源共享实施有效管理，协调好各进程对共享资源的访问，则必将影响程序的并发执行，甚至会使程序无法并发执行。
  • 虚拟性以并发性和共享性为前提。为了使并发进程能更方便、更有效地共享资源，OS常采用多种虚拟技术在逻辑上增加CPU和设备的数量以及存储器的容量，从而解决并发进程对有限系统资源的共享问题。
  • 异步性是并发性和共享性的必然结果。OS允许多个并发进程共享资源、相互合作，使得每个进程的运行过程受到了其他进程的制约，不再 ”一气呵成“，这必然会导致异步这一特征的产生。

3. 在操作系统中为什么要引入进程概念？它会产生什么样的影响？

• 在OS中引入进程，是为了实现多个程序的并发执行。传统的程序与其他程序并发执行时，执行结果不可再现，因此，传统的程序不能与其他程序并发执行，只有在为之创建进程后，其才能与其他程序（进程）并发执行。这是因为并发执行程序”停停走走“地执行，只有在为它创建进程后，在它停下时，方能将其CPU现场信息保存在它的PCB（Processing Control Block，进程控制块）中，待下次被调度执行时再从PCB中恢复CPU现场而继续执行，但传统的程序却无法满足上述要求。
• 建立进程所带来的好处是多个程序能并发执行，这极大地提高了资源利用率和系统吞吐量。但管理进程也须付出一定的代价，包括PCB及协调各运行机构所占用的内存空间开销，以及为进行进程间的切换、同步与通信等所付出的时间开销。

4. PCB的作用是什么？为什么说PCB是进程存在的唯一标志？

• PCB的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，即一个能与其他进程并发执行的进程。
• 当一个程序（含数据）配置了PCB后，就表示它已是一个能在多道程序环境下独立运行的、合法的基本单位了，即具有了取得OS服务的权利，如打开文件系统中的文件，请求使用系统中的 I/O设备，以及与其他相关进程进行通信等。因此，当系统创建一个新进程的同时，就会为它建立一个PCB。进程结束时系统又会回收其PCB，进程也随之消防。系统是通过PCB来感知进程的存在的。

5. 桌上有个能盛得下五个水果的空盘子。爸爸不停地向盘中放苹果或桔子，儿子不停地从盘中取出桔子享用，女儿不停地从盘中取出苹果享用。规定三人不能同时从盘子中取放水果。请回答和解决以下问题：

⑴ 进程同步应遵循的准则是什么？

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

⑵ 什么是临界资源？

• 一次仅允许一个进程使用的资源

⑶ 从参考选项中，选择正确选项序号，填入用信号量实现爸爸、儿子、女儿这三个循环进程同步的算法的空白处。（信号量机制实现进程同步）

semaphore empty=5, orange=0, apple=0, mutex=1;

爸爸、儿子、女儿的算法分别为：

//1-3-4-6-8
Dad(){
    while(1){
        __a__; 1-wait(empty)
        __b__; 3-wait(mutex);
        将水果放入盘中;
        __c__; 4-signal(mutex);
        if (放入的是桔子) {
            __d__; 6-signal(orange);
        }
        else{
            __e__; 8-signal(apple)
        }
    }
}
//5-3-4-2
Son(){
    while(1){
        __f__; 5-wait(orange);
        __g__; 3-wait(mutex);
        从盘中取一个桔子;
        __h__; 4-signal(mutex);
        __i__; 2-signal(empty);
        享用桔子;
    }
}
//7-3-4-2
Daughter(){
    while(1){
        __j__; 7-wait(apple);
        __k__; 3-wait(mutex);
        从盘中取一个苹果;
        __l__; 4-signal(mutex);
        __m__; 2-signal(empty);
        享用苹果;
    }
}
参考选项：
① wait(empty);      ② signal(empty);
③ wait(mutex);      ④ signal(mutex);
⑤ wait(orange);     ⑥ signal(orange);
⑦ wait(apple);      ⑧ signal(apple).

==6. 嗜睡的理发师问题。一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。请回答和解决以下问题：=

⑴ 什么是进程同步？

• 异步环境下的一组并发进程因直接制约而互相发送消息、互相合作、互相等待，使得各进程按一定的速度执行的过程，称为进程同步。

⑵ 什么是临界区？

• 指的是一个访问共用资源（例如：共用设备或是共用存储器）的程序片段，而这些共用资源又无法同时被多个线程访问的特性。

⑶ 从参考选项中，选择正确选项序号，填入用信号量实现这一同步问题算法的空白处。

为解决上述问题，需设置一个整型变量count用来对理发店的顾客进行计数，并需设置7个信号量，其中：mutex用来实现顾客进程对count变量的互斥访问，其初值为1；sofa是对应于等候室中N张沙发的资源信号量，其初值为N；empty表示是否有空闲的理发椅，其初值为1；full表示理发椅上是否有等待理发的顾客，其初值为0；cut用来等待理发的完成，其初值为0；payment表示用来等待付费，其初值为0；receipt用来等待收费，其初值为0。
算法：
int count;
semaphore mutex = 1,empty = 1,full = 0;(cut = 0, sofa = N)
semaphore payment = 0, receipt = 0;
guest(){
    __a__; 1-wait(mutex)
    if (count >= N){ 
        __b__; 2-signal(mutex)
        离开理发店;exit shop
    } else{
        count++;
        __c__; 2-signal(mutex)
        在沙发中就座;sit on sofa
        __d__; 3-wait(empty)//等待理发椅变空
        离开沙发,坐到理发椅上;get up from sofa / sit on the baber_chair
        __e__; 6-signal(full) //若理发师阻塞，则唤醒理发师。若未阻塞，则将full由0->1,理发师申请理发时即可通过。
        理发;wait(cut)
        付费;pay;
        __f__; 8-signal(payment)//若理发师阻塞，则唤醒理发师告知其已经付费，若未阻塞，则将payment由0->1,理发师申请付费时即可通过
        __g__; 9-wait(receipt)//测试理发师收费是否完成，没有则阻塞
        离开理发椅 get up from the baber_chair;
        __h__; 4-signal(empty) //释放理发椅
        __i__; 1-wait(mutex) //对count临界资源操作,用mutex完成互斥
        count--; //理发店顾客减一
        __j__; 2-signal(mutex)
        离开理发店;exit shop
    }
}
Barber(){
    while (1){
        __k__; 5-wait(full)//如没顾客就在此睡觉
        替顾客理发;cut hair signal(cut);
        __l__; 7-wait(payment)//等待顾客付费
        收费;accept payment
        __m__; 10-signal(receipt)//通知顾客收费完成
    }
}
参考选项:
    ① wait(mutex)   ② signal(mutex)
    ③ wait(empty)   ④ signal(empty)
    ⑤ wait(full)    ⑥ signal(full)
    ⑦ wait(payment) ⑧ signal(payment)
    ⑨ wait(receipt) ⑩ signal(receipt)

7. 有5个待运行作业为A、B、C、D、E，各自估计运行时间为9、6、3、5、x（未定），试问采用哪种运行次序可以使平均响应时间最短？

• 由于五个待运行的作业不包含运行优先级这一属性，故考虑采用短作业优先调度算法，使得平均响应时间最短
• 由于x的值是未定的，故有以下的几种分类讨论情况：
  • 当 时，运行次序为：x，3，5，6，9。E C D B A
  • 当 时，运行次序为：3，x，5，6，9。C E D B A
  • 当 时，运行次序为：3，5，x，6，9。C D E B A
  • 当 时，运行次序为：3，5，6，x，9。C D B E A
  • 当 时，运行次序为：3，5，6，9，x。C D B A E

8. 假设有5道作业，它们的提交时间及运行时间由下表给出：

若采用FCFS和SJF两种调度算法，指出作业以单道串行方式运行时的被调度顺序及平均周转时间。

• 周转时间 = 完成时间 - 提交时间
• FCFS：First come first service. 先来先服务调度算法。
  • 被调度顺序：1 -> 2 -> 3 -> 4 -> 5。
  • 平均周转时间：（2时 + 2时55分 + 3时20分 + 1时50分 + 1时40分）/ 5 = 11时45分 / 5 = 2时21分 | 作业 | 提交时间 | 运行时间 | 开始时间 | 等待时间 | 完成时间 | 周转时间 | | —- | —- | —- | —- | —- | —- | —- | | 1 | 10 | 2 | 10 | 0 | 12:00 | 2时 | | 2 | 10:05 | 1 | 12 | 1时55分 | 13:00 | 2时55分 | | 3 | 10:25 | 0.75 | 13 | 2时35分 | 13:45 | 3时20分 | | 4 | 12:25 | 0.5 | 13:45 | 1时20分 | 14:15 | 1时50分 | | 5 | 12:50 | 0.25 | 14:15 | 1时25分 | 14:30 | 1时40分 |

• SJF：Short job first. 短作业优先调度算法。从后备队列中选择一个
  • 被调度顺序：1 -> 3 -> 4 -> 5 -> 2
  • 平均周转时间：（2时 + 4时25分 + 2时20分 + 50分 + 40分）/ 5 = 10时15分 = 2时3分 | 作业 | 提交时间 | 运行时间 | 开始时间 | 等待时间 | 完成时间 | 周转时间 | | —- | —- | —- | —- | —- | —- | —- | | 1 | 10 | 2 | 10 | 0 | 12:00 | 2时 | | 2 | 10:05 | 1 | 13:30 | 3时25分 | 14:30 | 4时25分 | | 3 | 10:25 | 0.75 | 12:00 | 1时35分 | 12:45 | 2时20分 | | 4 | 12:25 | 0.5 | 12:45 | 20分 | 13:15 | 50分 | | 5 | 12:50 | 0.25 | 13:15 | 25分 | 13:30 | 40分 |

9. 产生死锁的必要条件有哪些？

• 互斥条件
• 请求和保持条件
• 不可抢占条件
• 循环等待条件

10. 什么是死锁？产生死锁的原因有哪些？

• 死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法向前推进。
• 产生死锁的原因：
  • 竞争不可抢占性资源
  • 竞争可消耗资源
  • 进程间推进顺序不当

11. 在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页次数(假设开始执行时主存中没有页面)，并比较所得结果。

(1) 最佳置换法(OPT)

• 分配的物理块为3时，缺页次数为7。 | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 4 | 4 | 4 | 4 | | | 4 | | | 2 | 1 | | | | 3 | 3 | 3 | | | 3 | | | 3 | 3 | | | | | 2 | 1 | | | 5 | | | 5 | 5 | |

• 分配的物理块为4时，缺页次数为6。 | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 4 | 4 | 4 | 4 | | | 4 | | | | 1 | | | | 3 | 3 | 3 | | | 3 | | | | 3 | | | | | 2 | 2 | | | 2 | | | | 2 | | | | | | 1 | | | 5 | | | | 5 | |

• 对OPT法来说，增加分配给作业的物理块数时，可降低缺页次数。

(2) 先进先出法(FIFO)

• 分配的物理块为3时，缺页次数为9。 | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 4 | 4 | 4 | 1 | 1 | 1 | 5 | | | 5 | 5 | | | | 3 | 3 | 3 | 4 | 4 | 4 | | | 2 | 2 | | | | | 2 | 2 | 2 | 3 | 3 | | | 3 | 1 | |

• 分配的物理块为4时，缺页次数为10。 | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 4 | 4 | 4 | 4 | | | 5 | 5 | 5 | 5 | 1 | 1 | | | 3 | 3 | 3 | | | 3 | 4 | 4 | 4 | 4 | 5 | | | | 2 | 2 | | | 2 | 2 | 3 | 3 | 3 | 3 | | | | | 1 | | | 1 | 1 | 1 | 2 | 2 | 2 |

• 对FIFO法来说，当增加分配给作业的物理块数时，反而会导致缺页次数的增加。

12. 考虑一个请求调页系统，它采用全局置换策略和平均分配内存块的算法（即，若有m个内存块和n个进程，则每个进程分别分得m/n个内存块）。如果在该系统中测得如下的CPU和对换盘利用率，请问能否用增加多道程序的度数来增加CPU的利用率？为什么？

（1）CPU的利用率为13%，盘利用率为97%；

• 这种情况表示系统在进行频繁的页面置换，导致绝大部分时间被花在页面置换上。此时，增加多道程序的度数会进一步增加缺页率，使系统性能进一步恶化。故，不能用增加多道程序的度数来增加CPU的利用率，反而应减少内存中的作业道数。

（2）CPU的利用率为87%，盘利用率为3%；

• 在这种情况下，CPU 的利用率已相当高，但对盘的利用率却相当低，这表示运行进程的缺页率很低，可以适当增加多道程序的度数来增加 CPU 利用率。

（3） CPU的利用率为13%，盘利用率为3%.

• 在这种情况下，CPU 的利用率相当低，而且对换盘的利用率也非常低，表示内存中可运行的程序数不足，此时，应该增加多道程序的度数来增加 CPU 的利用率。

13. 若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。

（1）先来先服务算法 FCFS（first come first service）

• FISO算法下，移动臂的移动次序及移动的柱面数。

柱面:         40 -> 20 -> 44 -> 40 -> 04 -> 80 -> 12 -> 76
移动的柱面数:    (20)  (24)  (04)  (36)  (76)  (68)  (64)
一共移动的柱面数: 20 + 24 + 04 + 36 + 76 + 68 + 64 = 292 个柱面
所耗时间: 292 * 3 ms = 876 ms

（2）最短寻找时间优先算法 SSTF（shortest seek time first）

• SSTF算法下，移动臂的移动次序及移动的柱面数。

柱面:         40 -> 44 -> 20 -> 12 -> 04 -> 76 -> 80
移动的柱面数:    (04)  (24)  (08)  (08)  (72)  (04) 
一共移动的柱面数: 04 + 24 + 08 + 08 + 72 + 04 = 120个柱面
所耗时间: 120 * 3 ms = 360 ms

14. 假定一个磁盘有200个柱面，编号为0-199，在完成了磁道125处的请求后，当前正在磁道143处为一个请求服务。若请求队列的先后顺序为：86，147，91，177，94，150，102、175，130，试分别采用FCFS〔先来先服务），SSTF(最短寻道时间优先)和SCAN(扫描)算法完成上述请求，写出磁头移动时的顺序，并计算存取臂移动总量。

• 采用 FCFS 算法调度时，磁头移动的顺序是： 143→86→147→91→177→94→150→102→175→130 。磁头移动总量是 565（柱面）。
• 采用 SSTF 算法调度时，磁头移动的顺序是： 143→147→150→130→102→94→91→86→175→177 。磁头移动总量是 163（柱面）。
• 采用 SCAN 算法调度时，磁头移动的顺序是： 143→147→150→175→177→130→102→94→91→86 。磁头移动总量是 125(柱面)。（4 分）

15. 一个比较完善的文件系统应具备哪些功能？

• 对文件存储空间的管理、目录管理、文件的读写管理以及文件的共享与保护

16. 在树型目录结构中，利用链接方式共享文件有何好处？OS为用户提供了哪些类型的接口？

• 利用链接方式共享文件主要有以下几方面的好处：
  • 方便用户。这种共享方式，允许用户按自己的方式将共享文件组织到某个子目录下，并赋予它新 的文件名，从而使用户更方便地管理和使用共享文件。
  • 防止共享文件被删除。每次链接时，系统将对索引结点中的链接计数字段进行加 1 操作，而删 除时，必须先对它进行减 1 操作，只有当计数字段的值为 0 时，共享文件才被真正删除，因此可避免用 户要共享的文件被删除的现象。
  • 加快检索速度。为了加快检索文件的速度，一般系统都引入了当前目录的概念。用户设置了工作 目录后，若共享文件已被链接到该工作目录，则系统无需再去逐级检索树型目录，从而加快检索速度。
• OS 向用户提供了两类接口，即用户接口和程序接口。

17.选择题

1. 从下面关于并发性的论述中，选出一条正确的论述。C

A.并发性是指若干事件在同一时刻发生。

B.并发性是指若干事件在不同时刻发生。

C.并发性是指若干事件在同一时间间隔内发生。

D.并发性是指若干事件在不同时间间隔内发生。

2.从下面的叙述中选出4条正确的论述。CDFG

A.一个进程的状态发生改变总会引起其他一些进程的状态发生变化。不一定

B.进程被挂起(suspend)后，状态变为阻塞状态。

C.信号量的初值不能为负数。

D.线程是CPU调度的基本单位，但不是资源分配的基本单位。

E.在进程对应的代码中使用wait、signal操作后，可以防止系统发生死锁。

F.管程每次只允许一个进程进入。

G. wait、signal操作可以解决一切互斥问题。

H.程序的顺序执行具有不可再现性。

3. 从下面的叙述中选出一条正确的叙述。C

A.操作系统的一个重要概念是进程，不同进程所执行的代码也不同。

B.操作系统通过PCB来控制和管理进程，用户进程可从PCB中读出与本身运行状态相关的信息。

C.当进程由执行状态变为就绪状态时，CPU现场信息必须被保存在PCB中。

D.当进程申请CPU得不到满足时，它将处于阻塞状态。

4. 从下面关于安全状态和非安全状态的论述中，选出一条正确的论述。D

A.安全状态是没有死锁的状态，非安全状态是有死锁的状态。

B.安全状态是可能有死锁的状态，非安全状态也可能有死锁的状态。

C.安全状态是可能没有死锁的状态，非安全状态是有死锁的状态。

D.安全状态是没有死锁的状态，非安全状态是可能有死锁的状态。

5. 从下面的叙述中选出一条正确的叙述。B

A.父进程创建了子进程，因此父进程运行完了子进程才能运行。

B.父进程和子进程可以并发执行。

C.撤销子进程时应同时撤销父进程。

D.撤销父进程时应同时撤销子进程。

6. 从下面关于进程的叙述中，选出一条错误的叙述。D

A.进程是动态的概念。

B.进程执行需要CPU。

C.进程是有生命期的。

D.进程是指令的集合。

7. 从下面关于临界资源的论述中，选出一条正确的论述。C

A.对临界资源不能实现共享。

B.只要能使程序并发执行则这些程序就可共享临界资源。

C.为临界资源配上相应的设备控制块后就可共享临界资源。

D.对临界资源采取互斥访问方式就可共享临界资源。

8. 从下面关于临界资源的叙述中，选出一条正确的论述。A

A.临界资源是共享资源。

B.临界资源是任意共享资源。

C.临界资源是互斥资源。

D.临界资源是同时共享资源。

18.试说明低级（进程）调度的主要功能。

• 保存处理机的现场信息
• 按某种算法选取进程
• 把处理器分配给进程

19.在锁同步机构中，系统提供在一个锁位w上的两个原语操作lock(w)和unlock(w)如下：

上锁原语（lock(w)）       开锁原语（unlock(w)）
算法：lock               算法：unlock
输入：锁变量w             输入：锁变量w
输出：无                 输出：无
{                      {
   test:                   w=0; /*开锁*/
   if(w==1)            }
   goto test; /*测试锁位的值*/
   else w=1; /*上锁*/
}

在上述的原语操作中，goto语句使执行lock(w)原语的进程要循环测试而占用处理机时间（称为“忙等待”），请使用“阻塞-唤醒”机制改进上锁原语（lock(w)）和开锁原语（unlock(w)），以提高处理机的效率。

解: 改进后的上锁原语
上锁原语（lock(w)）       
算法：lock               
输入：锁变量w             
输出：无                 
{
    while(w == 1){
        保护现行进程的CPU现场;
        将现行进程的PCB插入w的等待队列;
        置该进程为“等待”状态;
        转进程调度;
    }
    w = 1;
}
开锁原语（unlock(w)）
算法：unlock               
输入：锁变量w             
输出：无
{
    if(w等待队列不空){
        移出等待队列首元素;
        将该进程的PCB插入就绪队列;
        置该进程为“就绪状态”;
    }
    w = 0;
}

20.进程之间存在着哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？

• 进程之间存在着直接制约和间接制约两种制约关系
  其中直接制约（同步）是由于进程间的相互合作而引起的
  而间接制约（互斥）则是由于进程间共享临界资源而引起的。

⑴ 若干同学去图书馆借书；

• 间接制约，书是临界资源

⑵ 两队举行篮球比赛；

• 间接制约，篮球是临界资源

⑶ 流水线生产的各道工序；

• 直接制约

⑷ 商品生产和社会消费。

• 直接制约

21.在什么情况下需要进行重定位？为什么要引入动态重定位？

• 链接地址跟运行地址不同的情况下
• 为了满足程序的这种需要

22.根据文件的组织方式，可把有结构文件分为哪几类？

• 顺序文件
• 索引文件
• 索引顺序文件

23.引起进程调度的因素有哪些？

• 正在执行的进程执行完毕
• 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等状态
• 执行中进程调用了阻塞原语操作，并且因为资源不足而被阻塞，或调用了唤醒原语操作激活了等待资源的进程
• 在分时系统中时间片已经用完
• 就绪对列中的某个进程的优先级高于当前运行进程的优先级。

24.利用信号量实现两个进程互斥。

semaphore mutex = 1;
P1(){
    ...
    P(mutux);
    临界区代码段...
    V(mutux);
    ...
}
P2(){
    ...
    P(mutux);
    临界区代码段...
    V(mutux);
    ...
}

25. 什么是操作系统?它的主要功能是什么?

• 控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口和环境的程序集合。
• 主要功能
  • 处理机管理
  • 存储器管理
  • 设备管理
  • 文件管理
  • 接口管理

26. 某系统采用分页存储管理方法，页面大小为4KB，允许用户虚地址空间最大为16页，允许物理主存最多为512个主存块。试问该系统虚地址寄存器和物理地址寄存器的长度各是多少位？作必要说明。

• 页面大小为4KB = 字节，所以页内偏移量占12位。由于物理块大小等于页面大小，所以物理块大小为字节，物理块位数占12位。
• 允许用户虚地址空间最大为16页=页，即页号占4位
• 允许系统物理内存最多为512个内存块=个内存块，即内存块位数占9位。
• 虚地址寄存器位数=页号位数+页内偏移量位数=4+12=16位
• 物理地址寄存器位数=物理块位数+内存块位数=12+9=21位。

27.I/O系统的基本功能是什么？

• 隐藏物理设备的细节
• 与设备的无关性
• 提高处理机和I/O设备的利用率
• 对I/O设备进行控制
• 确保对设备的正确共享
• 错误处理。

28. 试说明资源的静态分配策略能防止死锁的原因。

• 资源静态分配策略要求每个过程在开始执行前申请所需的全部资源，仅在系统为之分配了所需的全部资源后，该进程才开始执行。这样，进程在执行过程中不再申请资源，从而破坏了死锁的四个必要条件之一占有并等待条件，从而防止死锁的发生。

29. 在一请求分页系统中，某程序在一个时间段内有如下的存储器引用：12、351、190、90、430、30、550（以上数字为虚存的逻辑地址）。假定内存中每块的大小为100B，系统分配给该程序的主存块数为3块。回答以下问题：（题中数字为十进制数）（20分）

(1) 对于以上的存储器引用序列，给出其页面走向。

• 页面大小与每块的大小相等，即 100B，所以 12、351、190、90、430、30、550 逻辑地址的页 号序列为 0、3、1、0、4、0、5。对应的页面走向为: 0、3、1、0、4、0、5。

(2) 设程序开始运行时，已装入第0页，在先进先出页面置换算法(FIFO) 和最久未使用页面置换算法（LRU）下，分别画出每次访问时该程序的主存页面情况，并给出缺页中断次数。

• FIFO 先进先出页面置换算法，缺页中断次数为5。 | 页面走向 | 0 | 3 | 1 | 0 | 4 | 0 | 5 | | —- | —- | —- | —- | —- | —- | —- | —- | | 物理块0 | 0 | 0 | 0 | | 4 | 4 | 4 | | 物理块1 | | 3 | 3 | | 3 | 0 | 0 | | 物理块2 | | | 1 | | 1 | 1 | 5 | | 是否缺页 | | √ | √ | | √ | √ | √ |

• LRU 最久未使用页面置换算，缺页中断次数为5。 | 页面走向 | 0 | 3 | 1 | 0 | 4 | 0 | 5 | | —- | —- | —- | —- | —- | —- | —- | —- | | 物理块0 | 0 | 0 | 0 | | 0 | | 0 | | 物理块1 | | 3 | 3 | | 4 | | 4 | | 物理块2 | | | 1 | | 1 | | 5 | | 是否缺页 | | √ | √ | | √ | | √ |

30. 字符显示式命令接口和图形化命令接口分别有什么优缺点？

• 字符显示式命令接口的优点是功能强速度快灵活性好屏幕开销少；缺点是显示不直观难学难记。
• 图形化用户接口的优点是显示直观操作简便易学；缺点是实现的代码规模大对内外存容量、CPU速度和显示器的要求较高。

31. 试比较进程调度与作业调度的不同点。

• 作业调度是宏观调度，它决定了哪一个作业能进入主存。进程调度是微观调度，它决定各作业中的哪一个进程占有中央处理机。
• 作业调度是选符合条件的收容态作业装入内存。进程调度是从就绪态进程中选一个占用处理机。

32. 试比较进程和程序的区别。

• 进程是动态的，而程序是静态的；
• 进程有一定的生命期，而程序是指令的集合，本身无“运动”的含义。没有建立进程的程序不能作为一个独立单位得到操作系统的认可。
• 一个程序可以对应多个进程，但一个进程只能对应一个程序。
• 进程和程序的组成不同。从静态角度看，进程由程序、数据和进程控制块（PCB）三部分组成，而程序是一组有序的指令集合。

33. 什么是物理设备？什么是逻辑设备？两者之间有什么区别和联系？

• 物理设备是实际存在的，逻辑设备是依靠物理设备存在的。没有物理设备不可能存在逻辑设备，但有物理设备不一定有逻辑设备。

34. 用户在使用文件之前必须要做打开文件的操作，为什么？

• “打开” 是指系统将指定文件中的属性（包括该文件在外存中的物理位置）从外存中复制到内存中已打开文件表的一个表目中，并将该表目的编号（或称索引号）返回给用户。“打开”就是在用户和指定文件之间建立起一个连接。此后，用户通过该连接可直接得到文件信息，避免了再次通过目录检索文件，即当用户再次向系统发出文件操作请求时，系统可根据用户提供的索引号直接在已打开文件表中查找到文件信息。这样不仅节省了检索开销，而且提高了文件操作速度。如果用户不再对该文件实施操作，则可以利用“关闭”系统调用来关闭此文件，即断开此连接，此时，OS将会把该文件从已打开文件表的表目中删除。

35. 什么是文件的逻辑结构？逻辑文件有哪几种组织方式？

• ① 文件的逻辑结构是指从用户的角度出发所观察到的文件组织形式，也就是用户可以直接处理的数据及其结构。
• ② 逻辑文件根据其结构可分为两种：一种是无结构的流式文件，是指文件信息由一串字符流构成；另一种是有结构的记录式文件，是指将文件信息按照在逻辑上独立的含义划分为信息单位，每个信息单位称为一个逻辑记录（简称记录）。

36. SPOOLing（假脱机系统）由哪几部分组成？以打印机为例，说明如何利用SPOOLing技术实现多个进程对打印机的共享。

• SPOOLing系统由磁盘上的输入井和输出井、内存中的输入缓冲区和输出缓冲区、输入进程和输出进程以及井管理程序组成。

• 采用SPOOLing技术共享打印机时，对所有提出输出请求的用户进程，系统接受它们的请求时，并不真正分配打印机，而是由SPOOLing管理进程做两件事情：

  • ① 在输出井中为它申请一空闲缓冲区、并将要打印的数据送入其中

  • ② 为用户进程申请一张空白的用户打印请求表，并将用户的打印请求填入表中，再将该表挂到SPOOLing文件队列上。

    至此，用户进程认为打印过程已经完成，而不必等待真正的慢速的打印过程完成。当打印机空闲时，SPOOLing打印进程将从SPOOLing文件队列的队首取出一张打印请求表，根据表中的要求将要打印的数据从输出井并传送到内存输出缓冲区，再由打印机进行输出打印。打印完成后，再处理SPOOLing文件队列中的下一个请求表，直至队列为空。这样，虽然系统中只有一台打印机，但系统并未将它分配给任何进程，而只是为每个提出打印请求的进程再输出井中分配一个存储区（相当于一个逻辑设备）。使每个进程都感觉自己独占一台打印机，从而实现了多个进程对打印机的共享。

37. 在创建一个进程时，OS需要完成的主要工作有哪些？

• OS发现请求创建新进程事件后，首先，调用进程创建原语；其次，申请一个空白PCB，并向该PCB中填写用于控制和管理进程的信息；再次，为该进程分配运行时所需的资源；最后，把该进程的PCB转入就绪状态并插入就绪队列中。

38. 什么是“抖动”？产生“抖动”的原因是什么？

• ① “抖动”是指刚被换出的页很快被访问，须重新调入，因此须再选一页调出，而此时被换出的页很快又要被访问，因而又须将它调入，如此频繁地更换页面，使得系统把大部分时间用在了页面的换进/换出上，而几乎不能完成任何有效的工作，我们称这一现象为“抖动”。
• 产生“抖动”的根本原因是同时在系统中运行的进程太多，分配给每个进程的物理块太少，其不能满足进程正常运行的基本要求，致使每个进程在运行时会频繁换页。

39. 3个进程P1、P2、P3互斥地使用一个包含N（N＞0）个单元的缓冲区，P1每次用produce()生成一个正整数，并用put()将其送入缓冲区的某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数，并用countodd()统计奇数的个数；P3每次用geteven()从该缓冲区中取出一个偶数，并用counteven()统计偶数的个数。用信号量机制实现这3个进程的同步与互斥，请回答和解决以下问题：(答案全部写在答题纸上)

⑴ 什么是进程同步？（4分）

• 异步环境下的一组并发进程因直接制约而互相发送消息、互相合作、互相等待，使得各进程按一定的速度执行的过程，称为进程同步。

⑵ 什么是临界区？

• 指的是一个访问共用资源（例如：共用设备或是共用存储器）的程序片段，而这些共用资源又无法同时被多个线程访问的特性。

⑶ 从参考选项中，选择正确选项序号，填入用信号量实现这一同步问题算法的空白处。（13分）

算法: 定义资源信号量 empty、odd、even,用于控制生产者与消费者之间的同步,
其中,empty表示空缓冲区的数目,odd表示缓冲区中奇数的个数,even表示缓冲区中偶数的个数;
定义互斥信号量mutex,用于实现进程对缓冲区的互斥访问。伪代码描述如下:
3 1 2 8 6
5 1 2 4 
7 1 2 4
semaphore empyu = N, even = 0, odd = 0,mutex = 1;
P1
while(1){
    x = produce();
    __a__; 3-P(empty)
    __b__; 1-P(mutex)
    put(x);
    __c__; 2-V(mutex)
    if(x % 2 == 0){
        __d__; 8-V(even)
    } else{
        __e__; 6-V(odd)
    }
}
P2
while(1){
    __f__; 5-P(odd)
    __g__; 1-P(mutex)
    getodd();
    countodd();
    __h__; 2-V(mutex)
    __i__; 4-V(empty)
}
P3
while(1){
    __j__; 7-P(even)
    __k__; 1-P(mutex)
    geteven();
    counteven();
    __l__; 2-V(mutex)
    __m__; 4-V(empty)
}
参考选项：
① P(mutex)  ②V(mutex)
③ P(empty)  ④V(empty)
⑤ P(odd)    ⑥V(odd)
⑦ P(even)   ⑧V(even)

40. 在多道批处理系统中，是否并发的进程越多，资源利用率越好？为什么？

• 多道批处理系统中，并不是系统中并发的进程越多，资料利用率越好。若系统中并发的进程过多，会导致系统在多个进程之间频繁切换，造成系统的性能下降，增大开销，从而降低资源利用率。

41. 磁盘请求服务队列中要访问的磁道分别为38，6，37，100，14，124，65，67，磁头上次访问了20磁道，当前处于30磁道上，试采用FCFS、SSTF（shortest seek time first，最短寻道时间优先）和SCAN调度算法，分别计算磁头移动的磁道数。

（1）先来先服务算法 FCFS（first come first service）

• FCFS算法下，磁头移动的磁道数 391 道。

磁头移动顺序:  30 -> 38 -> 6 -> 37 -> 100 -> 14 -> 124 -> 65 -> 67
移动的磁道数:    (08)  (32)  (31)  (63)  (86)  (110)  (59)  (02)
移动的总磁道数: 08 + 32 + 31 + 63 + 86 + 110 + 59 + 02 = 391 道

（2）最短寻找时间优先算法 SSTF（shortest seek time first）

• SSTF算法下，磁头移动的磁道数 158 道。

磁头移动顺序:  30 -> 37 -> 38 -> 14 -> 06 -> 65 -> 67 -> 100 -> 124
移动的磁道数:    (07)  (01)  (24)  (08)  (59)  (02)  (33)  (24)
移动的总磁道数: 07 + 01 + 24 + 08 + 59 + 02 + 33 + 24 = 158 道

（3）SCAN调度（又称电梯调度算法）

磁头移动顺序:  30 -> 37 -> 38 -> 65 -> 67 -> 100 -> 124 -> 14 -> 06
移动的磁道数:    (07)  (01)  (27)  (02)  (33)  (24)  (110)  (8)
移动的总磁道数: 07 + 01 + 27 + 02 + 33 + 24 + 110 + 8 = 212 道

42. 已知某分页系统，内存容量为64KB，页面大小为1KB，对一个4页大的作业，其0，1，2，3页分别被分配到内存的2，4，6，7块中，将十进制的逻辑地址1023，2500，3500，4500转换为物理地址。

• 对上述逻辑地址，可首先计算出它们的页号和页内地址（逻辑地址除以页面大小，得到的商为页号，余数为页内地址），然后通过页表将其转换成对应的物理地址。
  • 逻辑地址 1023。，1023 % 1k = 1023。因此页号为0，页内地址为1023，查页表找到对应的物理块号为2。故物理地址为2 × 1K + 1023 = 3071
  • 逻辑地址 2500。，2500 % 1k = 452。因此页号为2，页内地址为452，查页表找到对应的物理块号为6。故物理地址为6 × 1K + 452= 6596
  • 逻辑地址 3500。，3500 % 1k = 428。因此页号为3，页内地址为428，查页表找到对应的物理块号为7。故物理地址为7 × 1K + 428= 7596
  • 逻辑地址 4500。，4500 % 1k = 404。因此页号为4，页内地址为404，因页号大于页表长度，故产生越界中断。