简答题
1、什么是抖动现象？产生抖动的原因是什么
- 抖动（又称颠簸）是指刚被淘汰的页面又立即需要访问，因而又要将其调入内存，调入内存不久再被淘汰，淘汰不久又再被调入，如此反复。
- 产生抖动的根本原因：系统中同时运行的程序太多，导致分配给每个程序的物理块太少，不能满足程序正常运行的基本要求，使得程序运行时频繁地出现缺页。
2、简述什么是原语？
- 原语是指具有特定功能的、执行过程中不可被中断的指令集合。
- 原语是一个不可分割的基本单位，它只能顺序执行，不能并发执行。
- 在操作系统中，某些被进程调用的操作，如队列操作、对信号量的操作、检查启动外设操作等，一旦开始执行，就不能被中断，否则就会出现操作错误，造成系统混乱。所以，这些操作都要用原语来实现。原语是操作系统核心（不是由进程，而是由一组程序模块组成）的一个组成部分，并且常驻内存，通常在管态下执行。
3、什么是可变分区存储管理？常用的可变分区分配算法有哪些？
- 可变分区是指系统不预先划分固定区域，而是程序或作业装入内存时，根据程序或作业的实际需要动态地划分内容空间。
- 常用算法由首次适应算法（FF）、循环首次适应算法（NF）、最佳适应算法（BF）、最坏适应算法（WF）。
4、简述产生死锁的原因及必要条件。
- 产生死锁的原因可归结为两点：1. 争资源。 2. 进程推进顺序非法。
- 在具备下述四个必要条件时，就会产生死锁：
- 互斥条件
- 请求和保持条件
- 不剥夺条件
- 环路等待条件
5、什么是线程？试说明线程与进程的关系。
- 在引入线程的OS中，线程是进程中的一个实体，是被系统调度和分派的基本单位。
- 进程和线程既区别、又联系。进程是任务调度的单位，也是系统资源的分配单位；而线程是进程中的一条执行路径，当系统支持多线程处理时，线程是任务调度的单位，但不是系统资源的分配单位。每个进程至少有一个执行线程。
6、在操作系统的存储管理中，为什么要进行地址转换？
- 由于用户程序中使用的地址是逻辑地址，而程序在内存被执行时必须将逻辑地址转换为机器可以识别的物理地址。
7、衡量一个处理机调度算法优劣的主要标准？
- 资源利用率、吞吐率、公平性、响应时间、周转时间。
选择题和填空题
复习范围
- 进程的状态和描述（包含挂起状态，进程状态的转换）
- P V 操作
- 多级反馈队列调度算法
- 段页式存储管理、页式存储管理系统（地址转换）
- 哲学家进餐问题
- 缓存技术，虚拟存储技术、交换技术
- 磁盘驱动调度算法度算法
- 文件系统目录
部分题目
- 文件系统采用多级目录结构后，对于不同级目录下的文件，其文件名可以相同，也可以不同。
- 在分页存储管理系统中，从页号到物理块号的地址映射是通过页表实现的。
- 下列与进程调度有关的因素中，在设计多级反馈队列调度算法时需要考虑的是（ A、就绪队列的数量 B、就绪队列的优先级 C、各就绪队列的调度算法 D、进程在就绪队列间的迁移条件）。
计算题
1、磁盘调度
某移动磁盘的柱面由外向里从0开始顺序编号，假定当前磁头停在100号柱面，而且移动方向是向外的，现有一个请求队列在等待访问磁盘，访问的柱面号分别为190、10、160、80、90、125、30、20、140、25。请写出分别采用最短寻找时间优先和电梯调度算法处理上述请求的次序。
最短寻道时间优先算法（SSTF）：
磁道 10 20 25 30 80 90 125 140 160 190 次序 10 9 8 7 2 1 3 4 5 6 其要求访问的磁道与当前磁头所在的磁道距离最近。
该题中先从小到大左到右排序，将磁头与左右两边磁道相比，最短者优先排序，排序后磁头改变，选择离磁头最近的访问。
电梯调度算法（扫描算法SCAN）：
磁道 10 20 25 30 80 90 125 140 160 190 次序 6 5 4 3 2 1 7 8 9 10 1.首先自里向外访问，下一个对象是其欲访问的磁道既在当前磁道之外，又是距离最近的；
2.直至无更外的磁道需要访问时，才将磁臂换向为自外向里移动；
3.下一个访问的磁道在当前位置内为距离最近者；直至再无更里面的磁道要访问。
该题中由于题目给出了是有外向里的，所以电梯是往下走的，先走到头在反向上去。
2、缺页算法
有个一虚拟存储系统, 每个进程在内存占有3页数据区,刚开始时数据区为空. 有以下访页序列：1，0，2，2，1，7，6，7，0，1，2，0，3，0，4，5 试给出下列情形下的缺页次数:
FIFO算法：先进先出：总是淘汰在内存中停留时间最长（年龄最老）的一页，即先进入内存的页，先被换出。
1 0 2 2 1 7 6 7 0 1 2 0 3 0 4 5 1 1 1 1 1 1 0 2 2 7 6 0 0 1 2 3 0 2 0 0 0 0 2 7 7 6 0 1 1 2 3 0 4 3 2 2 2 7 6 6 0 1 2 2 3 0 4 5 缺页 √ √ √ √ √ √ √ √ √ √ √ √ OPT算法：最佳置换算法（Optimal Replacement, OPT）其实质是：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。
1 0 2 2 1 7 6 7 0 1 2 0 3 0 4 5 1 1 1 1 1 1 1 6 6 6 6 2 2 3 3 4 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 2 2 7 7 7 7 1 1 1 1 1 1 1 缺页 √ √ √ √ √ √ √ √ √ √ 缺页次数：10
LRU算法：最近最少使用算法：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。
1 0 2 2 1 7 6 7 0 1 2 0 3 0 4 5 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 0 0 0 0 7 7 7 7 7 2 2 2 2 4 4 3 2 2 2 2 6 6 6 1 1 1 3 3 3 5 缺页 √ √ √ √ √ √ √ √ √ √ √ 缺页次数：11
3、页式存储管理
设有一个页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页为2048字节，内存总共有8个物理块，问逻辑地址至少应该为多少位?内存空间为多大?
逻辑地址=页号+页内地址数
答:因为逻辑地址空间最大为16页，共需要4位二进制表示页号( 16=24);每页为2048字节，需要11位表示页内地址(2048=211)。因此逻辑地址至少为15位。
因为物理块大小与页面相同，故块内地址需11位表示;又因为内存中有8个物理块，需要3位（8=23）表示块号。因此物理地址需要14位表示，即内存空间大小为214=16KB。
4、调度算法
假设有三道作业，它们的提交时间及运行时间由下表给出
| 作业 | 提交时刻 | 运行时间 |
|---|---|---|
| 1 | 10:00 | 2h（120min） |
| 2 | 10:10 | 1h（min） |
| 3 | 10:25 | 25min |
采用非多道程序设计，“FCFS”作业调度算法。分别计算平均周转时间和平均带权周转时间。
| 作业 | 提交时刻 | 运行时间 | 开始时刻 | 完成时刻 | 周转时间（h） | 带权周转（h） |
|---|---|---|---|---|---|---|
| 1 | 10:00 | 2h | 10:00 | 12:00 | 2 | 1 |
| 2 | 10:10 | 1h | 12:00 | 13:00 | 2.83 | 2.83 |
| 3 | 10:25 | 25min | 13:00 | 13:25 | 3 | 7.14 |
周转时间：完成时刻 – 到达时间（提交时刻）
带权周转：周转时间/服务时间（运行时间）
平均周转时间：（2+2.83+3）÷3=2.61
平均带权周转时间：（1+2.83+7.14）÷3=3.66
