【操作系统】复习题目&解析&拓展
[c-downbtn type=“default” url=“https://todo.lthero.cn/source/operating_system/chapter2.md” pwd=""]md下载[/c-downbtn]
操作系统复习题目&解析&拓展
选择题
1、下列不属于引起创建进程的事件的是：（ ）
A.用户登录 B.新数据尚未到达 C.作业调度 D.提供服务
创建进程的引起事件
用户登录：
用户登录成功，系统为用户创建一个进程
作业调度：
调度某个作业到内存时，会为作业创建进程
提供服务：
运行中的用户程序提出某个请求后，系统专门创建一个进程，用来提供服务
应用请求：
用户进程已经创建的进程，如某个用户进程创建同进程的线程
2、整型信号量机制未遵循同步机构中的（ ）。
A.空闲让进 B.忙则等待 C.让权等待 D.有限等待
整形&记录型信号量
整形信号量：
wait(S){
while (S<=0);
S=S-1;
}
signal(S){
S=S+1;
}
wait(申请资源操作)，如果S<=0，就会一直申请（一直while），直到得到了资源；但这不遵守“让权等待”
记录型信号量：
记录型信号量，由于采用记录型的数据结构而得此名字，数据结构如下：
typedef struct{
int value;
struct process *L;
} semaphore;
wait操作如下：
void wait (semaphore S) { //相当于申请资源
S.value–;
if(S.value<0) {
add this process to S.L;
block(S.L);
}
}
当信号量S<=0时，会将当前申请的进程添加到“申请链表”，进行自我阻塞，放弃处理机，遵循了“让权等待”
3、对一个正在执行的进程，如果因时间片完而被暂停执行，它应从执行状态转变为（ ）状态。
A.静止阻塞 B.活动阻塞 C.静止就绪 D.活动就绪
只有被挂起的进程，才会进入“静止XX”
原来的执行-就绪-阻塞，变成了执行-活动就绪-活动阻塞，但三者的转换关系不变。只是添加挂起功能，多出了静止阻塞和静止就绪
4、下列指标中，主要用来评价分时系统性能的是：（ ）。
A.周转时间 B.开始截止时间的保证 C.响应时间 D.完成截止时间的保证
分时&实时系统
分时系统
是指在一个系统中多个用户分时地使用同一台计算机。
有较强的交互性，对响应时间要求低
实时系统
是指计算机_及时_响应外部事件地请求并在规定时限内完成对该事件地处理，控制所有实时外设和实时任务协调一致地运行。
较弱的交互性，对响应时间要求高
实时&分时系统的主要区别：
（1）分时系统的目标是提供一种通用性很强的系统，有较强的交互能力；而实时系统则大都是具有特殊用途的专用系统，交互能力略差。
（2）分时系统对响应时间虽有要求，但一般来说，响应时间由人所能承受的等待时间来确定；而实时系统对响应时间要求很高，一般由控制系统或信息处理磁头所能接受的延迟时间来决定。
5、某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台。当N的取值不超过（ ）时，系统不会发生死锁。
A.4 B.5 C.6 D.7
判断死锁计算公式
w*(n-1)+1<=m
即可满足要求。其中，w为每个进程要求资源数目；n为进程数目；m为资源总数
6、在下列进程状态转换中，绝对不可能发生的状态转换是（ ）。
A.就绪→执行 B.执行→就绪 C.就绪→阻塞 D.执行→阻塞
进程三种基本状态
就绪
拥有除了cpu外的全部条件，只缺少cpu；
阻塞
不仅缺少cpu，还缺少其它资源，如I/O
执行
就绪状态得到cpu后变成执行状态；执行的时间片用完后，只会变成就绪状态，等待下次分配处理机
7、下列算法中不适合作业调度的是（ ）算法。
A.先来先服务 B.短作业优先 C.优先级调度 D.时间片轮转
作业与进程
作业：
作业是用户向计算机提交任务的任务实体。用户提交作业后，系统将它放入外存的作业等待队列中
进程：
进程是完成用户任务的执行实体。是向系统申请分配资源的基本单位
一个作业可以由多个进程组成，而且必须至少由一个进程组成；
作业与进程的区别
作业主要用在批处理系统
进程用在多道程序系统，是进行资源分配的单位
作业调度算法：
-
先来先服务算法（FCFS）
-
短作业优先算法（SJF）
-
优先级调度算法（PSA）
-
高响应比优先调度算法（HRRN）
进程调度算法：
-
轮转调度算法
-
优先级调度算法
-
多队列调度算法
-
多级反馈队列调度算法
-
基于公平原则的调度算法
时间片轮转算法分配的是处理机资源，在不考虑线程的系统中，进程是获取资源并被独立调度的最小单位。
时间片轮转是针对进程的算法
8、所谓临界区是指（ ）。
A.一个寄存器 B.一个缓冲区 C.一段数据区 D.一段程序
临界区&临界资源
临界区
每个进程中“访问临界资源的那段程序”叫临界区，“那段程序”叫临界区。
每个进程进入临界区前，先对想访问的临界资源进行检查，如果该资源未被访问，则进程可以进入自己的临界区，并将此资源设置为被访问标志。如果该资源正在被访问，进程则必须等待。
临界资源
每次只能被一个进程访问的资源，如打印机、输入机
进程进入临界区的调度规则
-
如果有很多进程要求进入空闲临界区，一次只能进入一个进程
-
任何时候，处于临界区的进程不得超过一个
-
进入临界区的进程要在有限时间内退出
-
如果进程不能进入自己的临界区，应该让出cpu
9、单道批处理系统和多道批处理系统共同的缺点是：（ ）。
A.无交互性 B.自动性 C.无序性 D.平均周转时间长
单道批&多道批处理
单道批
内存中仅有一道程序运行，可以看成是串行的
多道批
1.概念 内存中存放多道程序，当某道程序因某种原因如执行I/O操作时而不能继续运行放弃CPU时，操作系统便调度另一程序运行，这样CPU就尽量忙碌，达到提高系统效率的目的。
-
当A进程申请I/O时，操作系统启动I/O（蓝线）。
-
随后，A进入I/O操作(磁盘操作)；cpu处理B进程
-
当B进程也申请I/O操作时(磁带操作)，操作系统启动I/O（蓝线）。
-
此时A的I/O还没结束，此时cpu处于空闲状态。
-
当A的I/O完成后，操作系统调度A进程（蓝线），cpu处理A进程
-
A进程处理完成，此时恰好，B的I/O操作完成，操作系统调度B进程（蓝线），cpu处理B进程。
判断题目
10、并行性是指若干事件在同一时刻发生。（）
√
并行性&同时性&并发性
并行性是指计算机系统具有可以同时进行运算或操作的特性，在同一时刻完成两种或两种以上工作。
它包括 同时性与并发性两种含义。
同时性
指两个或两个以上事件在同一时刻发生。
并发性
指两个或两个以上事件在同一时段发生。
并发性与并行性区别
注意：并发性与并行性不同，
并发指同一个时间段内，多个进程可以同时运行。事实是cpu在某段时间内在不同进程内反复切换
并行指的是两个或两个以上的事件或活动在同一时刻发生
11、信号量的初值一定为1。（ ）
×
反例：在生产者—消费者问题中，资源信号量full的初值应为0
当信号量的计数为 0 时，所有资源都在使用中。之后，需要使用资源的进程将会阻塞，直到计数大于 0。
当信号量为负数时，负数的值就是当前正在等待的进程数目
12、中级调度的调度对象是作业（ ）
×
三种调度方式
低级调度
又称为进程调度、短程调度，它决定就绪队列中的哪个进程将获得处理机 ，然后由分派程序执行把处理机分配给该进程的操作。 在批处理，分时，实时三类系统中，必须有低级调度，因而是一种最基本的调度。
中级调度
又称为中程调度，引入中级调度的主要目的是为了提高内存的利用率和系统的吞吐量。 内存中不能有太多的进程，把进程从内存移到外存，当内存有足够空间时，再将合适的进程换入内存，等待进程调度 。 中级调度实际上就是存储器管理 中的对调功能。
高级调度
又称为作业调度，高级调度的主要功能是根据某种算法，把外存上处于后被作业队列中的那些作业调入内存，也就是说它们的调度对象是作业。
13、并发和共享是OS的两个最基本的特征。（）
√
操作系统的基本特征
并发性
用户程序与用户程序并发执行；系统程序与用户程序并发执行；
共享性
资源共享
随机性
一个设备可以在任何时刻向cpu发出中断请求，系统无法知道程序在什么时间做什么事
虚拟性
将一个物理实体对应成若干个逻辑体
异步性
同一个程序多次运行可能得到不同结果；程序的运行时间、顺序也不确定；外部输入的请求也无法确定
名词解释
14、临界资源
指每次只能被一个进程占用的资源
15、死锁
一个进程中，每个进程都在无限等待被其它进程占用的资源
16、进程
是程序在数据集合上的一次运行过程，进程是分配资源和接受调度的基本单位
17、wait原语操作
在申请资源时，进行wait操作；如果资源被占用，进程需要阻塞自己
综合
18、某系统T0时刻的资源分配情况如下所示
（1）该状态是否安全？
存在一个安全序列A=>C=>E=>D=>B
| 进程 | WORK | ALLOCATION | NEED | WORK+ALLC |
|---|---|---|---|---|
| A | 1 2 0 | 3 1 1 | 1 0 0 | 4 3 1 |
| C | 4 3 1 | 1 1 0 | 3 0 0 | 5 4 1 |
| E | 5 4 1 | 0 0 0 | 2 1 0 | 5 4 1 |
| D | 5 4 1 | 1 0 1 | 0 1 0 | 6 4 2 |
| B | 6 4 2 | 0 0 0 | 0 1 2 | 6 4 2 |
19、假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示
忽略I/O以及其它开销时间，若分别按先来先服务（FCFS）、非抢占的短进程优先（SPF）调度算法进行CPU调度。请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。
(1)先来先服务
周转时间=完成时间-到达时间
带权周转时间=周转时间/服务时间
| 进程 | 到达时间 | 服务时间 | 开始时间 | 完成时间 | 周转时间 | 带权周转 |
|---|---|---|---|---|---|---|
| A | 0 | 4 | 0 | 4 | 4 | 1 |
| B | 1 | 3 | 4 | 7 | 6 | 2 |
| C | 2 | 5 | 7 | 12 | 10 | 2 |
| D | 3 | 2 | 12 | 14 | 11 | 5.5 |
| E | 4 | 4 | 14 | 18 | 14 | 3.5 |
平时周转时间：(4+6+10+11+14)/5
平时带权周转时间：(1+2+2+5.5+3.5)/5
(2)短进程优先
| 进程 | 到达时间 | 服务时间 | 开始时间 | 完成时间 | 周转时间 | 带权周转 |
|---|---|---|---|---|---|---|
| A | 0 | 4 | 0 | 4 | 4 | 1 |
| D | 3 | 2 | 4 | 6 | 3 | 1.5 |
| B | 1 | 3 | 6 | 9 | 8 | 2.67 |
| E | 4 | 4 | 9 | 13 | 9 | 2.25 |
| C | 2 | 5 | 13 | 18 | 16 | 3.2 |
平时周转时间：(4+3+8+9+13)/5
平时带权周转时间：(1+1.5+2.67+2.25+3.2)/5
20、利用记录型信号量写出解决生产者-消费者问题的算法。
P()指wait操作（荷兰语proberen，测试）；
V()指signal操作 （荷兰语verhogen，增加）；
记录型结构如下：
typedef struct{
int value;
struct process *L;
} semaphore;
代码：
semaphore mutex=1,empty=n,full=0;
producer{
while(true){
P(empty);//减少empty，如果empty不为空，说明需要生产"empty"个数目
P(mutex);//加锁
生产者生产;
V(mutex);//解锁
V(full);//增加full
}
}
consumer{
while(true){
P(full);//减少full,如果full不为空，则可以消耗"full"个数
P(mutex);//加锁
消费者消费;
V(mutex);//解锁
V(empty);//增加empty
}
}
21、利用记录型型号量写出三个进程之间的同步算法。
爸爸进程负责去空盘子里面放水果，每次只能放一个水果，并且水果只能是苹果或者香蕉，如果是苹果，通知女儿进程取走吃掉；如果是香蕉通知儿子进程取走吃掉。
结构体：
struct {
int value;
struct process *L;
}semaphore;
代码：
1 | semaphore plate=1,apple=0,banana=0,empty=1; |
爸爸进程负责去空盘子里面放苹果，母亲进程负责去空盘子里面放香蕉。女儿进程取苹果吃掉；儿子进程取香蕉吃掉。
方法1：
father进程和daughter进程必须连续执行，mother进程和son进程必须连续执行。
如果先执行父亲进程，那么会保证后续只能由女儿进程执行。因为母亲进程因为拿不到盘子而阻塞，儿子进程因为没有香蕉而阻塞。
1 |
|
方法2
传统方法，相当于使用两组Full和Empty变量，因为刚开始盘子为空，儿子和女儿进程会被阻塞。一定是父亲或母亲进程运行，只有其中一个进程锁住盘子并成功放了水果，并成功唤醒了孩子进程再放开盘子。
这个方法相对上面的方法1要麻烦些。
1 | semaphore plate=1,apple_full=0,banana_full=0,apple_empty=1,banana_empty=1; |
