《操作系统原理》习题及参考答案

2
中 中断
正常的中断屏蔽码
改变后的中断屏蔽码
断 优先
源 级 D1 D2 D3 D4 D5 D1 D2 D3 D4 D5
D1 1
1
1
1
1
1
1
0
0
00
D2 2
0
1
1
1
1
1
1
0
00
D3 3
0
0
1
1
1
1
1
1来自百度文库
00
D4 4
0
0
0
1
1
1
1
1
11
D5 5
0
0
0
0
1
1
1
1
01
(1)当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实际 上中断处理的先后次序是什么？ (2)当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实 际上中断处理的先后次序是什么？ (3)如果采用改变后的中断屏蔽码， D1、D2、D3、D4 和 D5 同时请求中断时，画出处理器 响应各中断源的中断请求和实际运行中断服务程序过程的示意图。 解： (1) 当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是 D1、D2、 D3、D4、D5。 实际上中断处理的先后次序是 D1、D2、D3、D4、D5。 (2) 当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是 D1、D2、 D3、D4、D5。 实际上中断处理的先后次序是 D4、D5、D3、D2、D1。 (3) 如果采用改变后的中断屏蔽码， D1、D2、D3、D4 和 D5 同时请求中断时，处理器响 应各中断源的中断请求和实际运行中断服务程序过程如下图所示：
１５． 设一个飞机航班售票系统有 n 个售票处，每个售票处通过终端访问系统的公共数据 区。假定公共数据区中的一些单元 Aj(j=1,2,3,…)分别存放某月某日某次航班的余票数。 用 P1,P2,…,Pn 表示个售票处为旅客服务时的处理进程； R1, R2, R3…, Rn 为各进程执 行时所用的工作单元。用 PV 操作和信号量保证售票系统的正确并发执行。
２．设有三个进程 A、B、C，进程 A 需 8 毫秒处理时间，B 需 2 毫秒处理时间，C 需 24 毫 秒处理时间，分别考虑在就绪队列中的顺序为 ABC 时及 CBA 时，用先来先服务算法 进行调度时的平均等待时间。
解：当顺序为 ABC 时： Wa=0 Wb=8 Wc=10 Mw=(0+8+10)/3=6 ms 当顺序为 CBA 时： Wc=0 Wb=24 Wc=26 Mw=(0+24+26)/3=17 ms
C
9:00(9.0)
1
14.4
15.4
6.4
6.4
１２． 什么是进程同步？ 解：进程同步是指并发进程之间存在一种直接制约关系，一个进程的执行依赖另一个进程 的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。
１３． 设有两个优先级相同的进程 P1、P2 如下。令信号量 S1、S2 的初值均为 0，试问
执行结果： PID before fork():2000 parent process PID:2000 child process PID:2001
８．什么是进程？简述进程与程序、线程的区别和联系。 解：进程是一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基 本单位。 进程与程序的区别和联系是： 1) 进程是一个动态概念，程序是一个静态概念。 2) 进程具有并行特征，程序没有并行特征。
进入输入 需运行时 开始运行 完成时间 周转时间 带权周转
井时间 间（小时） 时间
时间
A B C 解：
8:00
6.4
8:24
3.2
9:00
1
先来先服务算法：
作业号
进入输入 需运行时 开始运行 完成时间 周转时间 带权周转
井时间 间（小时） 时间
时间
A
8:00(8.0)
6.4
8.0
14.4
6.4
1
B
8:24(8.4)
解：（1）设信号量 S2:=0; S3:=0; S4:=0;
P1:
P2:
P3:
……..
P(S2)
P(S3)
……..
……..
……..
V(S2)
…….
…….
V(S3)
V(S4)
V(S4)
（2）设信号量 S3:=0; S4:=0; S5:=0; S6:=0;
P1: …….. …….. …….. V(S3)
解：
z 实现 A、B 进程间同步应设置 2 个信号量 S1, S2. 信号量 S1 表示缓冲区是否 为空；信号量 S2 表示缓冲区是否为满。
z S1 的初值为 1；S2 的初值为 0. z 同步算法 Begin mutex: semaphore; Aj: integer; mutex:=1; S2:=0; Cobegin
3.2
14.4
17.6
9.2
2.9
C
9:00(9.0)
1
17.6
18.6
9.6
9.6
短作业优先算法：
作业号
进入输入 需运行时 开始运行 完成时间 周转时间 带权周转
井时间 间（小时） 时间
时间
A
8:00(8.0)
6.4
8.0
14.4
6.4
1
5
B
8:24(8.4)
3.2
15.4
18.6
10.2
3.2
4
3) 进程是竞争计算机系统资源的基本单位。 4) 不同的进程可以包含同一程序，只要该程序所对应的数据集不同。 进程和线程的区别和联系是： 1) 线程是进程的一个组成部分。 2) 进程的多线程都在进程的地址空间活动。 3) 资源是分给进程的，而不是线程的。 4) 调度的基本单位是线程。 5) 线程在执行过程中，需要同步。
① CPU 检查响应中断的条件是否满足。 ② 如果 CPU 响应中断，则 CPU 关中断，使其进入不可再次响应中断的状态。 ③ 保存被中断的现场。 ④ 分析中断原因，调用中断处理子程序。 ⑤ 执行中断处理子程序。 ⑥ 退出中断，恢复被中断进程的现场或调度新进程占据处理器。 ⑦ 开中断，CPU 继续执行。 ５．有 5 个中断源 D1、D2、D3、D4 和 D5，它们的中断优先级从高到低依次是 1-5 级别。 这些中断源的中断优先级、正常情况下的中断屏蔽码和改变后的中断屏蔽码如下表所 示。每个中断源有 5 位中断屏蔽码，其中 0 表示该中断源开放，1 表示该中断源被屏蔽。
《操作系统原理》
习题及参考答案
１．操作系统的定义。操作系统的五大基本功能。网络操作系统相对单机操作系统还应具备 什么功能？
解：操作系统是计算机系统的一种系统软件，由它统一管理计算机系统中的软硬件资源， 合理地组织工作流程，以便有效地为用户提供一个功能强大、使用方便的工作环境，从而 在计算机与用户之间起到接口的作用。操作系统的五大基本功能是：处理机管理、存储器 管理、设备管理、文件系统管理和用户接口。网络操作系统还应具备的功能：网络通信、 资源共享、网络服务、网络用户接口。
9
3
16
0
0
P2 y:=z+y
9
19
16
0
0
所以 x=9,y=19,z=16
②假设 P2 先执行，P1 后执行：
x
y
z
S1
S2
P2 y:=1
1
0
0
P2 y:=y+2
3
0
0
P2 V(S1)
3
1
0
P2 z:=2*y+1
3
7
1
0
P2 P(S2)
3
7
1
-1
P1 x:=0
0
3
7
1
-1
P1 x:=x+2
2
3
7
1
1
总的执行时间为 180ms.如果单道执行这三个程序共需 80+100+80=260ms.所以节约 260－ 180ms.
(2) 若处理机调度程序每次进行程序状态转换的时间为 1ms，这三道程序的执行时间如下 图所示：
总共花费 180+6=186ms. ４．系统调用（陷入）处理过程。
解：系统调用（陷入）处理过程和中断处理过程是一样的，只是中断源是执行了访管指令 （MS DOS 的 INT 或 UNIX 的 trap）。
x
y
z
S1
S2
P1 x:=0
0
0
0
P1 x:=x+2
2
0
0
0
P1 P(S1)
2
-1
0
P2 y:= 1
2
1
-1
0
P2 y:=y+2
2
3
0
-1
0
P2 V(S1)
2
3
0
0
0
P2 z:=2*y+1
2
3
7
0
0
P2 P(S2)
2
3
7
0
-1
P1 x:=x+z
9
3
7
0
-1
P1 V(S2)
9
3
7
0
0
P1 z:=x+z
１１． 对于下列三个作业，采用不可抢占的调度方式：先来先服务算法和短作业优先算法，
当第一个作业进入系统后开始调度，填写下面的表格。
先来先服务算法：
作业号
进入输入 需运行时 开始运行 完成时间 周转时间 带权周转
井时间 间（小时） 时间
时间
A
8:00
6.4
B
8:24
3.2
C
9:00
1
短作业优先算法：
作业号
６．进程有哪几种基本状态？作业有哪几种基本状态？画出作业进程基本状态关系图。 解：进程有三种基本状态：就绪态、运行态、等待态。作业有四种基本状态：输入态（提
交态）、后备态（收容态）、执行态、完成态。
3
７．系统调用 fork()工作过程。 （1） 为子进程在 proc 结构表中分配一个空项； （2） 为子进程赋一个唯一的 PID （3） 复制父进程上下文的逻辑副本。 （4） 增加与父进程相关联的有关文件系统的进程引用技术。 （5） 对父进程返回子进程的 PID，对子进程返回为 0. 语法：pid = fork(); 一个 fork()系统调用程序实例 #include <stdio.h> #include <sys/typex.h> #include <unisd.h>
１０． 处理机调度的目的是什么？有哪几种类型？每种调度的主要任务是什么？ 解：处理机调度的目的是使处理机在满足系统要求的响应时间、吞吐量和处理机利用率的 前提下及时地运行进程。调度有 4 种类型：长程调度：决定欲增加执行的进程池；中程调 度：决定增加部分或全部位于内存中进程数；短程调度：决定哪个就绪进程被处理机执行； I/O 调度：决定哪个进程未完成的 I/O 请求可被 I/O 设备处理。
９．常用的进程调度算法和作业调度算法有哪些？哪些适用于作业调度？哪些适用于进程 调度？
解：常用的作业调度算法有：先来先服务算法（FCFS）、最短作业优先算法（SJF）、最高响 应比优先算法（HRRN）、优先级调度算法、均衡调度算法等。 常用的进程调度算法有：先来先服务算法（FCFS）、优先级调度算法、时间片轮转调度算法 （RR）、分级调度算法、多级反馈轮转算法（MultiLevel Feedback Queue）等。
P1、P2 并发执行结束后 x=? y=? z=? 写出并发执行的细节。（10 分）
进程 P1
进程 P2
x:=0; x:=x+2; P(S1); x:=x+z; V(S2); z:=x+z;
y:=1; y:=y+2; V(S1); z:=2*y+1; P(S2); y:=z+y;
解：①假设 P1 先执行，P2 后执行：
main() {
pid_t val;
printf("PID before fork():%d",(int)getpid()); val = fork(); if (val != 0)
printf("parent process PID:%d\n",(int)getpid()); else
printf("child process PID:%d\n",(int)getpid()); }
P2: …….. …….. ……. V(S3)
P3: P(S3) P(S3) …….. V(S4) V(S5) V(S6)
P4: P(S4) P(S4) …….. …….
P4: P(S4) ……. …….. …….
P5: P(S5) ……. …….. …….
P6: P(S6) ……. …….. …….
-1
P1 P(S1)
2
3
7
0
-1
P1 x:=x+z
9
3
7
0
-1
P1 V(S2)
9
3
7
0
0
P1 z:=x+z
9
3
16
0
0
P2 y:=z+y
9
19
16
0
0
所以 x=9,y=19,z=16
6
１４． 利用 PV 操作，怎样才能保证进程 Pi 能按下面两图的次序正确执行，其中 S 表示 开始，F 表示结束。
３．设在内存中有三道程序：A、B、C，并按照 A、B、C 的优先次序运行，其内部计算和
I/O 操作时间由下图给出。
程序 A
程序 B
程序 C
计算 30ms
计算 60ms
计算 20ms
I/O 40ms
I/O 30ms
I/O 40ms
计算 10ms
计算 10ms
计算 20ms
要求： （1）试画出按多道程序运行的时间关系图（调度程序的执行时间忽略不计）。完成这三道 程序共花多少时间？比单道运行节省多少时间？ （2）若处理机调度程序每次进行程序状态转换的时间为 1ms，试画出在处理机调度程序管 理下各程序状态转换的时间关系图。完成这三道程序共花多少时间？ 解： (1)在调度程序执行时间忽略不计的情况下，这三道程序的执行时间如下图所示：