🌈 个人主页：十二月的猫-CSDN博客
🔥 系列专栏： 🏀操作系统

💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光 

目录

前言

简答题

一、对 CPU、内存、外设并发的操作系统有哪些措施？

二、 根据操作系统对资源和进程的管理，写出中断有哪些方面的作用

三、 描述系统调用的工作机制及其参数传递方法。

四、画出进程的状态图，并说明状态变化的原因

五、程序从外存调入内存，在调入、执行、结束过程中发生了什么，又是怎么解决的。

六、用户级线程和内核级线程是什么？相对的各自有什么优点

七、 多队列调度算法和多级反馈队列调度算法的基本思想，比较这两个算法的好坏

八、根据进程的到达和执行时间，画出相应算法的甘特图，并求出平均等待时间​编辑

 九、临界区设计的基本要求；信号量是怎么设计来满足这些要求的？  

 十、写出下面程序的输出结果，并解释这样输出的原因

十一、两个进程 T1 和 T2 并发执行，共享变量 x，初值为 1，T1 使 x+1，T2 使 x-1，过程如下。问两个 进程结束后 x 有多少种可能取值？有哪些方法使结果唯一？选取一种方法修改下面的程序，保证两进程结束后结果唯一

十二、简述阻塞、饥饿、死锁、死循环的区别

十三、CPU 是进程运行必需的资源，为什么进程不会因等待 CPU 而发生死锁？

十四、 简述银行家算法避免死锁的过程（包括变量定义、安全判别算法等）

十五、 简述死锁预防、死锁避免并比较区别。

总结

---

前言

本系列题目均选自山东大学往年考题，供大家复习参考。一定要在复习完基础知识后（最好把书本都看一遍，这样子知识体系才是完善的），再来参考这个练习题。

两个不可取：一、不可不复习知识点，光做题；二、不可只复习知识点，不复习

猫猫祝大家都能取得好成绩呀~~~

简答题

一、对 CPU、内存、外设并发的操作系统有哪些措施？

进程存在调度算法：FCFS、SJF、LRU、近似LRU等

内存存在管理策略：内存的调度就是两种：一、直接全部调度进来；二、请求调页技术。所以没有什么算法对应。但是内存如何组织管理有许多策略，例如：连续分配；分段；分页等

 对CPU并发的措施：（让CPU并发执行多道程序的措施/机制） 

• 进程调度：CPU通过进程调度算法等实现进程调度机制，从而让CPU能够并发处理多道程序，形成分时系统
• 进程同步与通信：CPU能够同时并发允许多道程序还依赖于进程同步与通信的机制，通过同步与通信在保证进程运行安全性的前提下又实现了并发运行

对内存并发的措施：（让内存能够同时处理多个进程的内存信息）

• 虚拟内存技术：通过虚拟内存、请求调页的技术使得内存能够同时给多个进程使用，从而提高内存的并发性
• 内存管理策略：内存管理策略，包括分页、分段、连续存储等策略保证内存在并发时能够较好的对进程对应的内存进行管理

对外设并发的措施：（让外设I/O等能够并发运行）

• I/O子系统与缓冲区管理：通过I/O子系统统一对各自外设I/O设备进行管理，实现这些外设能够同时运行，而不会发生冲突。同时存在缓冲区解决了I/O和 CPU运行速度不匹配问题以及安全性问题
• 中断机制：每当I/O处理结束后，能够向CPU发送中断信号，通过操作系统的控制通知CPU来处理。从而实现外设能够并发运行不会冲突

二、 根据操作系统对资源和进程的管理，写出中断有哪些方面的作用

1、分析中断的作用，首先要知道中断有哪些

2、知道中断的类型后再从资源和进程的角度看每种中断的作用 

中断有两种类型，分别是trap和interrupt，其中trap 又分为主动陷入内核和error被动陷入内核。

主动陷入内核是程序员写的程序选择主动陷入内核，可能是为了查看系统运行的信息从而对软件进行调试等，或者是调用一些系统调用为完成某些功能

error被动陷入内核是软件在运行中由于一些错误主动被陷入内核。这个陷入内核的中断是对计算机的一种保护，防止资源被浪费或恶意进程抢占资源等

interrupt陷入内核是由于外界硬件原因陷入内核，这种中断实现了外设I/O等和CPU的交互，让操作系统能够统一调配CPU的资源

三、 描述系统调用的工作机制及其参数传递方法。

工作机制=工作流程+技术保证

系统调用的工作机制：

1. 触发系统调用：由应用程序调用系统函数，系统函数是包装好的库函数，就会触发系统调用
2. 切换到内核模式：系统调用函数通知内核，内核引发中断并从用户态切换到内核态
3. 找到系统调用函数：内核根据系统调用库函数，通过索引表找到对应的实现函数
4. 参数传递：通过寄存器、堆栈、组合等方式将应用程序提供的参数传递给系统调用
5. 执行系统调用：操作系统根据参数执行完系统调用函数，并将结果返回给应用程序
6. 恢复用户态：最后，操作系统将CPU由内核态转为用户态，执行下一条语句

参数传递方式：

• 寄存器传递：可以通过各自寄存器来实现参数的传递
• 堆栈传递：将参数通过程序压入堆栈，操作系统再从堆栈中取出
• 内存块和表中：应用程序将参数存入内存的块和表中，操作系统通过块的地址来获得参数

传递的参数内存大小由小到大 

四、画出进程的状态图，并说明状态变化的原因

  

五、程序从外存调入内存，在调入、执行、结束过程中发生了什么，又是怎么解决的。

由于是从外存调入内存，所以在调入的过程中，可以不完全调入——存在挂起状态 

因此，比起上一题多了两种状态：就绪挂起、阻塞挂起（运行时不可能挂起）

就绪挂起：有三个状态能指向它（新的、运行、阻塞挂起）

  

六、用户级线程和内核级线程是什么？相对的各自有什么优点

用户级线程：完全由用户创建并管理的线程。这种线程的创建、切换、同步、通信等操作都不需要系统调用来实现，仅仅需要用户级线程库。线程管理在用户空间进行，效率较高

内核级线程：完全由内核创建并管理的线程。应用程序不能创建也不能管理这类线程，仅仅能使用该线程的编程接口。对于内核来说是可见的，所以在一个线程被阻塞后，可以立即调用另一个线程继续执行，并发能力强

七、 多队列调度算法和多级反馈队列调度算法的基本思想，比较这两个算法的好坏

多级队列算法：存在多个队列。每个队列的优先级、调度算法不同，进程属于哪一队列是一开始固定的，后面不能更改。优点是低调度开销，缺点是不够灵活。

多级反馈队列算法：在多级队列算法基础上增加了反馈机制，能够通过反馈调整进程属于哪个队列。缺点是调度设计复杂开销大，优点是比较灵活，并且可以避免老化。

一、两者都会在一开始根据进程的属性、特点、类型等来确定该进程属于哪一级队列

二、低优先级队列时间片更长；高优先级队列时间片更短

多队列调度：多级队列调度算法将就绪队列分成多个独立队列，根据进程的属性，如内存大小、 进程优先级、进程类型，一个进程被永久地分配到一个队列。每个队列都有自己的调度算法。 此外，队列之间通常采用固定优先级抢占调度，每个队列与更低队列相比都有绝对的优先级。 或者在队列之间划分时间片。优点是低调度开销，缺点是不够灵活。

 多级反馈队列调度：允许进程在队列之间移动。根据不同 CPU 区间的特点以区分进程。如果进 程使用过多 CPU 时间会被转移到更低优先级队列。在较低优先级队列中等待时间过长的进程会 被转移到更高优先级队列。这种形式的老化可以阻止饥饿。最通用的 CPU 调度算法，可被配置 以适应系统设计，但是最复杂。

八、根据进程的到达和执行时间，画出相应算法的甘特图，并求出平均等待时间

（1）轮转法调度（时间片大小为 2）

（2）高响应比

  

 九、临界区设计的基本要求；信号量是怎么设计来满足这些要求的？  

临界区设计基本要求：

• 互斥：只要有一个进程在临界区中，其他进程不能进入临界区
• 进步：如果没有进程在临界区中，则要允许进程进入临界区
• 有限等待：一个请求加入临界区的进程可以在有限时间内加入临界区

信号量：

• 信号量设计中，设计互斥信号量初始值为1。当有进程进入临界区时（进入临界区条件是信号量>0)，会将信号量减1，后面其他进程无法进入临界区。在该进程退出临界区后会让信号量加1。
• 如果没有进程在临界区，那么信号量一定为1，此时请求的进程一定能够进入临界区
• 一旦有进程退出临界区，就会释放临界区资源，此时一定有一个请求进程能够进入临界区，满足有限等待

 十、写出下面程序的输出结果，并解释这样输出的原因

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
int a = 0;
int main() {pid_t pid = fork();if (pid == 0) {a = 2;printf("child leaving\n");} else {wait(NULL);printf("a=%d\n", a);}return 0;
}

输出结果：

child leaving

a=0 

程序 fork()了一次，产生一个子进程。父进程和子进程并行运行，直到父进程执行 wait(NULL)， 即 wait(0)。wait(0)表示父进程会被阻塞，直到子进程的状态发生变化，即从运行态到终止态， 才会被唤醒。所以先输出子进程运行结果，后输出父进程运行结果。由于子进程执行 a=2 时发 生写时复制，父子进程有独立的数据段，父进程输出 0 不变

十一、两个进程 T1 和 T2 并发执行，共享变量 x，初值为 1，T1 使 x+1，T2 使 x-1，过程如下。问两个 进程结束后 x 有多少种可能取值？有哪些方法使结果唯一？选取一种方法修改下面的程序，保证两进程结束后结果唯一

结果为0，1，2

保证结果唯一就是要让对x这个临界区资源的访问是限制的，不会出现race condition（竞争条件）

方法有：1、信号量；2、test and set；3、compare and swap 

十二、简述阻塞、饥饿、死锁、死循环的区别

阻塞：阻塞是进程的一种状态，是进程在等待某一事件（I/O事件）而暂停运行。进程由运行状态变为阻塞状态，是进程自身的一种主动行为，处于阻塞状态的进程可能发生死锁或饥饿也可能顺利向前

饥饿：饥饿是指一个进程始终得不到资源。饥饿的进程可以是就绪态（始终得不到CPU的调度），也可以是阻塞态（始终得不到I/O设备的响应）。是进程的一种被动发生的行为

死锁：死锁是进程彼此想要对方手中的资源，同时又占有自己手中的资源而导致的进程无法推进。是一种错误分配资源导致的结果

死循环：可能是程序员故意设计的结构，也可能是不小心设计的

区别与联系：

1、饥饿、死锁、死循环都是进程无法顺利向前推进的现象（故意设计的死循环除外）。阻塞可能无法推进也可能可以推进

2、死锁和饥饿问题是由于操作系统分配资源不合理导致的，而死循环是由代码逻辑的错误导致的。阻塞则是某些事件导致的

3、死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题

十三、CPU 是进程运行必需的资源，为什么进程不会因等待 CPU 而发生死锁？

CPU资源是可以被抢占的，因为CPU和内存类似都可以恢复原先的数据、状态等。所以它不满足死锁的非抢占必要条件，因此不会发生死锁

十四、 简述银行家算法避免死锁的过程（包括变量定义、安全判别算法等）

银行家算法包括两个部分：银行家算法本身+安全判别算法 

算法程序=变量定义+初始化+算法流程

安全判别算法：(确定计算机系统是否处于安全状态）（作用于判断一个系统快照是否安全）

1. 定义finish[n]、need[n]、available[m]分别表示进程是否完成、进程需要的资源数目、目前可用的各资源的资源量。其中n表示进程数，m表示资源类型数目
2. 初始化：将finish都设置为false，并对need和available进行初始化处理
3. 寻找是否存在need<=available的进程（即将可用资源分配给该进程，进程可以完成），如果存在则让该进程获得所有资源并运行结束，然后释放资源即allocation（该进程原占有资源）+available。并将其finish设置为true
4. 判断finish是否都是true，如果是则算法结束找到安全序列，系统是安全状态；如果存在false，则循环第三步。直到finish存在false但是第三步中找不到满足条件的进程，则说明系统不是安全状态

银行家算法：

1. 定义allocation[n][m]，need[n][m]，available[m]，n为进程数，m为资源类型数
2. 初始化这三个变量
3. 如果有进程request资源，先检查这个request是否合理。如果request>need则出错，内核将杀死这个进程，如果request<=need则执行步骤4
4. 判断request和available大小。如果request>available则无法分配、无视请求；如果request<=available则执行步骤5
5. 按照需求request假分配，修改当前的need、available、allocation，并运行安全判别算法，如果修改后状态安全，则允许分配，否则不允许分配

十五、 简述死锁预防、死锁避免并比较区别。

死锁预防是一组方法，需要确定至少一个必要条件不成立。

死锁避免要求操作系统事先得到有关进程申请使用资源的额外信息。当进程申请资源时，若发现满足该资源的请求可能导致死锁发生，则拒绝该申请。

比较：两种方法都不允许死锁发生。动态的死锁避免会因为追踪当前资源分配成本增加运行成本，但是相对于静态的死锁预防方法它对资源的限制更少，允许更多的并发使用资源（例如CPU资源用时，I/O资源也在用），所以系统吞吐量大于死锁预防。

总结

如果觉得对你有帮助，辛苦友友点个赞哦~

知识来源：操作系统概念（黑宝书）、山东大学高晓程老师PPT及课上讲解、山东大学操作系统往年题、部分考研题。不要私下外传