华南理工大学操作系统期末考试卷考点整理

华南理工大学操作系统期末考试卷考点整理第一章

1.操作系统

扩展的机器

资源管理

操作系统是由程序模块组成的系统软件，它能够以尽量有效、合理的方式管理计算机底层硬件资源、规划计算机工作流程、控制程序的执行、提供各种服务功能，为用户提供计算机抽象接口，使得用户能够方便、灵活的使用计算机，计算机系统得以高效运行。

2.操作系统的特征

并发

共享

虚拟

异步性

3.操作系统的功能

处理机管理

存储管理

设备管理

信息管理

用户接口

4. 操作系统的设计原则

可维护性：改错性维护、适应性维护、完善性维护。

可靠性：正确性、稳健性。

可理解性：易于理解，以方便测试、维护和交流。

性能：有效地使用系统资源，尽可能快地响应用户请求。

5.操作系统结构

1）单体系统：主过程，服务过程，实用过程

?特点：模块由众多服务过程（模块接口）组成，可以随意调用其他模块中的服务过程。

?优点：具有一定灵活性，在运行中的高效率。

?缺点：功能划分和模块接口难保正确和合理，模块之间的依赖关系（功能调用关系）复杂，降低了模块之间的相对独立性，不利于修改。

2）层次式系统：(5)操作员(4)用户程序(3)I/O管理(2)操作员-IPC(1)存储器和磁鼓管理(0)处理器的分配和多道程序设计

·优点：功能明确，调用关系清晰（高层对低层单向依赖，调用有序性），有利于保证设计和实现的正确性；低层和高层可分别实现（便于扩充）；高层错误不会影响到低层；避免递归调用。·缺点：降低了运行效率。

3）客户/服务器模型：把操作系统分成若干分别完成一组特定功能的服务进程，等待客户提出请求；而系统内核只实现操作系统的基本功能(如：虚拟存储、消息传递)。

优点：

?良好的扩充性：只需添加支持新功能的服务进程即可。

?可靠性好：调用关系明确，执行转移不易混乱。

?便于网络服务，实现分布式处理：以同样的调用形式，在下层可通过核心中的网络传送到远方服务器上。

缺点：

?消息传递比直接调用效率要低一些 (但可以通过提高硬件性能来补偿 )。

4）微内核(micro-kernel)：将更多操作系统功能放在核心之外，作为独立的服务进程运行。

第二章

进程的特征

?动态性：进程具有动态的地址空间（数量和内容），地址空间上包括：

–代码（指令执行和CPU状态的改变）

–数据（变量的生成和赋值）

–系统控制信息（进程控制块的生成和删除）

?独立性：各进程的地址空间相互独立，除非采用进程间通信手段；

?并发性、异步性："虚拟"

?结构化：代码段、数据段和核心段（在地址空间中）；程序文件中通常也划分了代码段和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）

进程与程序的区别

?进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。

?进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。

?进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。

?进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

PCB：进程控制块

引入线程的目的是简化线程间的通信，以小的开销来提高进程内的并发程度。

?线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。

–线程的创建时间比进程短；

–线程的终止时间比进程短；

–同进程内的线程切换时间比进程短；

–由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信

进程和线程的比较

?地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享－－某进程内的线程在其他进程不可见

?通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信－－需要进程同步和互斥手段的辅助，以保证数据的一致性

?调度：线程上下文切换比进程上下文切换要快得多；

进程间的关系

?完全无关（异步）：不同进程间无任何关联

?使用共享数据（互斥）：有效保护各个进程的正确运行

?存在先后顺序（同步）：保证进程运行顺序的正确

1.导致进程创建的事件

1)系统初始化

2)执行进程创建系统调用

3)用户请求创建一个新进程

4)初始化一个批处理作业

2. 中断发生后操作系统最底层的工作步骤

1)硬件压入堆栈程序计数器等。

2)硬件从中断向量装入新的程序计数器。

3)汇编语言过程保存寄存器值

4)汇编语言过程设置新的堆栈

5)C中断服务例程运行（典型地读和缓冲输入）

6)调度程序决定下一个将运行的进程。

7)C过程返回至汇编代码。

8)汇编语言过程开始运行新的当前进程

3. 避免竞争条件的关键是不允许多于一个进程同时读写共享数据。

竞争条件：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件。

临界区：对共享内存进行访问的程序片段称作临界区

4.避免竞争条件解决方案的四个条件

1)互斥原则：不允许两个进程同时在临界区

2)通用原则：对处理的速度和cpu的数量不应当有任何假设

3)有效性原则：运行于临界区外的进程不能阻塞其他进程

4)合理性原则：进程不应当无休止地等待临界区，无法进入应放弃CPU资源

4．互斥解决

1)屏蔽中断：则上下文切换不会发生。因此，允许用户禁止中断是不明智的。但是，但有时禁止

中断是很方便的 (甚至是必需的)（写、读之间可能会有）

2)锁变量：设共享（锁）变量，当要进入，测得锁为0方可，并设置为1，否则等到变为0。（当退

出没有置为0，会出现违背原则1）

3)严格轮换法：进程分别为0或者1，turn的值也为0或1，相同时进入（违背了条件3。因为进

程必须严格按顺序进入临界区）

4)Peterson解法：要进入置为自己的turn，同则进入，不同等待。（满足4个）

5)TSL指令：使用TSL指令，进入置1，不允许其他，直到退出置0。

5.IPC机制三种模型

?忙等待模型（只解决互斥问题）

–进程进入临界区时进行严格的检查

?睡眠和唤醒模型（互斥与同步）

–通过改变进程的状态来实现互斥和同步

?消息传递模型（复杂的IPC机制）

–以公共的通信机制来控制进程状态变化，实现同步和互斥

5.调度算法的评价标准

1)公平性 - 每一个进程得到公平的调度时间。

2)有效性–保证CPU忙碌且在执行有效的工作。

3)响应时间–对交互式用户最小化其响应时间。

4)运行时间–对批处理作业，最小化其运行时间。

5)吞吐量–对批处理作业，最大化每小时完成的作业数。

6. 调度算法的目标

1)所有系统

- 公平

- 策略强制执行

- 平衡

2)批处理系统

- 吞吐量

- 周转时间

- CPU利用率

3)交互式系统

- 响应时间

- 均衡性

4)实时系统

- 满足截止时间

- 可预测性

7.批处理系统中的调度

1)先来先服务（FCFS）

2)最短作业优先（SJR）

两种方案：

非抢占式–一旦进程获得 CPU，它将不能被抢占，直到主动放弃CPU。

抢占式–系统中的正在运行的进程永远是优先级最高的。

SJF 是最优的–对所有进程，系统的平均等待时间最小。

3)最短剩余时间优先

8. 交互式系统的调度

1)轮转调度（RR）

2)优先级调度

3)多级队列调度

每一个就绪队列赋予一个不同的优先级类

就绪队列分为多个队列：

前台 (交互式作业)

后台 (批处理作业)

每一个队列有自己的调度算法，

前台– RR

后台– FCFS

4)最短进程优先（老化算法）

a = 估计是采用的权重，当前估计值为：

T1 = a*T0 + (1-a) *T1

这里T0是先前的估计值，T1是当前的运行时间。

5)保证调度

假定将 CPU的时间分为n份

计算比率 = 实际占用CPU的时间/ 整个CPU时间

执行比率最小的进程

6)彩票调度（随机）

7)公平共享调度

每个用户分配CPU的一部分，调度器以一种强制的方式选择进程。

9.实时系统中的调度

1)调度器必须保证在任务的死线之前执行完任务。

2)硬实时和软实时

3)可调度的实时系统

假定m 个周期事件

事件 i 发生的周期是 Pi ，需要 Ci 处理时间

则满足下面条件时，系统时可调度的

10.调度机制和调度策略

1)调度机制和调度策略分离

2)实现机制在内核：算法参数化

3)用户进程设置策略：用户设置参数

8.批处理系统中的调度：三级调度

接纳调度决定哪一个作业被接纳到系统中。

内存调度决定哪一个进程应该装入内存，哪一个应当放在磁盘。

它也决定同时有多少个进程在内存中，这称之为多道程序度。

CPU调度实际选择内存中合适的进程运行。

第三章

1. CPU利用率 = 1 - p n

这里，内存中有n个进程，每个进程花费比例p的时间等待I/O.

CPU利用率是n的函数，称之为多道程序的度

2. 多道程序引入了两个问题–重定位和保护.

重定位–不能确定程序装在内存的什么地方

代码不应当指定变量的绝对地址

必须保证程序不会访问其他进程的分区

保护–使用基址和界限值

相对地址加上基址映射为物理地址

相对地址大于界限值则产生错误

3. 内存限制的两种解决方案: 动态内存管理

（设计思想：为进程动态分配内存，将进程动态调入内存

分类：基于交换技术：将进程完整的调入内存，运行一段时间后，调出内存。

基于虚拟存储器：进程只需要比程序空间小的内存就可以正常运行。分页和分段）

交换把一个进程在需要时装入内存，不需要时写入磁盘

虚拟内存允许程序甚至在只有一部分在内存时就可运行。

交换可能会在内存中制造出多个空闲区, 内存紧缩技术通过移动一些进程，把多个空闲区合并为一个。

4. 两种记录内存使用情况的方式：位示图和链表。

位示图的问题是找到连续的0位是一个较慢的操作。

5. 问题: 程序太大不能全部装入内存

解决方法:

程序员把程序分为多片，称之为覆盖–工作量太大

虚拟内存– OS只保留程序的一部分放在内存

分页是实现虚拟内存的一种技术.

虚地址是程序产生的地址.

MMU (内存管理单元) 把虚地址转换为物理地址.

6. 命中率= a

有效访问时间 (EAT)

EAT = ? (t + ?) + (1 – ?) (2t + ?)

= ? t + ? ? + 2t + ? - 2?t - ? ?

= (2 – ?) t + ?

7.页面置换算法

1) 最优页面置换算法：替换最远的将来不会用到的页面

2) 最近未使用（NRU ）页面置换算法：淘汰一个没有被访问已修改，好过频繁访问未修改。访问R

修改M （有置1，周期置0）

3) FIFO 页面置换算法

4) 第二次机会页面置换算法：检查最老，R=0淘汰，R=1置0放到最新，全查完无，用FIFO

5) 时钟页面置换算法：第二次变环形

6) 最近最少使用(LRU) 页面置换算法：访问+1，选最小，周期置0

N 个页框：k*k 矩阵，访问k 页框，k 行置1，k 列置0，选行值最小的页

软件实现：

7) 最不经常使用（NFU ）：修改NFU ：老化NFU-每次时钟中断：往右移，竖着在左边加入，结束时选

行值最小

8) 工作集页面置换算法：? ? w (k, t) ? 在t 时刻，工作集窗口包含有k 个页面的访问

检查R 位，1置0，0&t>e ，淘汰，0&t<=e ，记下最后时间，若无1多0弃最久

9) 工作集时钟（WSClock ）页面置换算法：工作集变成环形

8. 由于页表和内部碎片造成的开销

s = 平均进程大小（字节）

p = 页面大小 （字节）

e = 页表项大小 2s e p overhead p ?=+（+内部碎片） 当最佳：2p se =

9. 实现方面的问题与分页有关的操作系统

与调页有关的事件

1. 进程创建

确定程序的大小

创建页表

2. 进程执行

MMU 为新进程复位

TLB 刷新

3. 页故障时

确定虚地址是发生故障

换出不需要的页，换入需要的页。

4. 进程结束时

释放页表,页

10.缺页中断处理

1) 硬件陷入内核

2) 保存通用寄存器

3) OS 确定需要哪一个虚页

4) OS 检查地址的有效性，查找页帧

5) 如果选择的页帧是脏的，写回到磁盘

6)OS 装入新页

7)更新页表

8)被中断的指令重新开始执行

9)被打断的进程得到调度

10)恢复寄存器

11)程序继续

11. 内存管理系统可分为三个部分：

底层的MMU处理器

页故障处理器（内核的一部分）

运行在用户空间的外部页面调度程序

第四章

1.文件的实现

1)连续分配

2)链表分配

3)在内存中采用表的链表分配

4)i节点

2.改善文件系统性能

1)高速缓存

2)块提前读

3)减少磁盘臂振动

影响文件系统安全性的主要因素

系统漏洞——提高设计水平进行规避

操作失误——建立防护机制进行保护

恶意攻击——实施安全策略进行遏制

文件系统的可靠性设计

?坏块管理

–硬件实现与软件实现：坏块表和备份扇区?备份机制

–交叉备份和增量存储

?一致性检查

–块一致性坚持和文件一致性检查?磁盘访问性能

?高速缓存

第五章

1.精确中断4个特性

1)PC保存在一个已知的地方

2)PC所指向的指令之前的所有指令已经完全执行

3)PC所指向的指令之后的所有指令都没有执行

4)PC所指向的指令的执行状态是已知的

2.I/O管理的任务和目标

?根据用户请求，控制各类I/O设备实现用户的目标

?向用户提供方便的I/O设备接口，屏蔽底层硬件细节差别?利用各种技术，提高I/O设备的运行效率

?实现对I/O设备的管理和保护

O软件目标

?设备独立性

–程序可以访问任何 I/O 设备

–不必提前指定设备 (软盘, 硬盘或 CD-ROM)?统一命名

–以一个字符串或整数的形式命名一个文件或设备

–不依赖于具体的机器

?错误处理

–处理尽可能接近硬件

?同步与异步传输

–块传输与中断驱动

?缓冲

–来自设备的数据并不直接存放到目的地?可共享的和独占的设备

–磁盘是可共享的

–磁带则不是

3.实现I/O的三种方式

1)程序控制I/O

2)中断驱动I/O

3)使用DMA的I/O

4)I/O通道机制

O软件系统的层次及功能

用户级IO软件：产生I/O请求；对I/O进行格式化；假脱机

与设备无关的操作系统软件：命名、保护、分块、缓冲、分配

设备驱动程序：设置设备寄存器；检查状态

中断处理程序：当I/O完成时唤醒驱动程序

硬件：执行I/O操作

5.中断处理

1)保存没有被中断硬件保存的所有寄存器（包括PWS）

2)为中断服务过程设置上下文，可能包括设置TLB、MMU和页表

3)为中断服务过程设置栈

4)应答中断控制器, 允许中断

5)复制寄存器

6)执行服务过程

7)选择下一次运行的进程

8)为下一个要执行的进程设置MMU 上下文

9)装入新进程的寄存器

10)开始运行新进程

6.与设备无关的I/O软件

1)设备驱动程序的统一接口

2)缓冲

3)错误报告

4)分配和释放专用设备

5)提供与设备无关的块大小

7. 读或写一个磁盘块的时间由3因素决定

寻道时间（主）

旋转延迟

实际传输时间

8.磁盘臂调度算法

FCFS

SSF（最短寻道优先）

电梯算法：一个方向走完后换方向

9.错误处理

用备用扇区替换坏扇区

移动所有扇区以回避坏扇区

10.稳定存储器

稳定写

稳定读

崩溃恢复

第六章

1.资源分为：

可抢占的资源：把进程的资源(例如内存)剥夺后不会导致严重错误

不可抢占的资源：把进程的资源(例如CD刻录机)剥夺后将导致严重错误2. 使用资源时发生的事件

请求资源

使用资源

释放资源

3. 死锁的四个必要条件

1.互斥条件

?每一个资源分配给一个进程或是可用的

2.占有和等待条件

?进程占有资源并请求其他资源

3.不剥夺条件

?先前得到的资源不可强制被剥夺

4.环路条件

? 2 个以上的进程形成了一个链

?每一个进程都在等待被链中的下一个进程占有的资源4.处理死锁的策略

1)忽略该问题

2)检测死锁并恢复

3)仔细对资源进行分配，动态地避免死锁

4)通过破坏引起死锁的四个必要条件之一，防止死锁的产生

5.从死锁中恢复

?抢占式恢复

–抢占其他进程的资源

–依赖于资源的属性

?回滚式恢复

–周期性地检查进程

–使用保存的状态

–如果发生死锁，则重启进程

?杀死进程恢复

–最粗糙但是最简单打破死锁的方法

–杀死锁链中的一个进程

–其它进程得到资源

–选择可以重新执行的进程

6．死锁防止

1)破坏互斥条件：有些设备(比如打印机) 可被spooled（假脱机）

2)破坏占有和等待条件：在开始时就请求全部资源

3)破坏不可抢占条件：这并不是一个可行的方案

4)破坏环路等待条件：对所有资源进行编号，请求必须按照编号的顺序。

7.死锁的避免

资源轨迹图

安全状态和不安全状态：银行家算法

8.死锁的检测

单个：有向图是否有环路

多个：矩阵：类似银行家