02323操作系统概论考前白皮书

*一章    操作系统简介

操作系统的资源管理功能：处理机管理、内存管理、设备管理和文件管理。

操作系统的发展：单批道处理系统、多批道处理系统、分时系统、实时系统。

操作系统的特征：并发，共享，虚拟，异步性

*二章    进程管理

进程的特征：并发性、动态性、独立性、异步性、结构特征

进程的 3 种基本状态：就绪态、执行态、阻塞态。

调用创建新进程的系统调用来创建进程的一般步骤如下。

申请空白 PCB。

为新进程分配资源。

初始化进程控制块。

将新进程插入就绪队列。

进程的阻塞与唤醒

表 2-1   进程的阻塞与唤醒

信号量机制：wait(s)表示 s=s-1，**(s)表示 s=s+1 6.线程的阻塞与唤醒

用户线程的阻塞过程：①停止该线程的执行，将该线程的状态改为阻塞态。

②将该线程控制块插入相应的线程阻塞队列。

③将该线程所属进程的状态改为阻塞态。

④将该线程所属进程的进程控制块插入相应的进程阻塞队列。

⑤将控制传递给进程调度程序，重新进行进程调度。 用户线程的唤醒过程：①将该线程所属进程的状态由阻塞改为就绪。

②将该线程所属进程的进程控制块从进程阻塞队列中移出。

③将该线程所属进程的进程控制块插入进程就绪队列。

④将该线程状态由阻塞改为就绪。

⑤将该线程的线程控制块从线程阻塞队列中移出。

⑥将该线程的线程控制块插入线程就绪队列。

内核线程的阻塞过程：①停止该线程的执行，将该线程的状态改为阻塞态。

②将该线程控制块插入相应的线程阻塞队列。

③将控制传递给线程调度程序，重新进行线程调度。 内核线程的唤醒过程：①将该线程状态由阻塞态改为就绪态。

②将该线程的线程控制块从线程阻塞队列中移出。

③将该线程的线程控制块插入线程就绪队列。

*三章    进程调度与死锁

在 Linux 内核中，进程调度功能的实现从调用内核函数 schedule（）开始。

选择调度方式和算法的若干准则

1  n    

T  n Ti

平均周转时间

i1    

 1  n T 

W

平均带权周转时间

调度算法

 i 

n i1 Ts 

先来先服务调度算法（FCFS）

FCFS 适合长进程，不利于短进程，短进程等待时间相对运行时间而言太长。FCFS 有利于 CPU 繁忙型进程（如科学计算），不利于 I/O 繁忙型进程（如多数的事务处理）。

短进程优先调度算法（SPF） 算法的缺陷：

①对长进程不利。如果系统中不断有短进程到来，长进程可能长时间得不到调度。

②不能**紧迫进程的及时处理，因为该算法不考虑进程的紧迫程度。

③进程的长短根据用户的估计而定，故不一定能真正做到短进程优先。

常用的几种实时调度算法：.较早截止时间优先 EDF 算法、较低松弛度优先 LLF 算法

松弛度用来表示一个实时进程的紧迫程度。如果一个进程的完成截止时间为 T，当前时间为 Tc，处理完该任务还需要的时间为 Ts，则松弛度 L 的计算式表示为 L=T-Tc-Ts

多处理器系统（MpS）的类型

对处理器系统有多种不同的分类方式，根据处理器的耦合程度，可以把多处理器系统分为紧密耦合多   处理器系统和松弛耦合多处理器系统；根据处理器结构是否相同，可以把多处理器系统分为对称多处理器   系统和非对称多处理器系统。

进程（线程）调度方式：自调度、成组调度、专用处理器分配。

死锁

概念：在多道程序系统中，多个进程可能竞争数量有限的资源。如果一个进程所申请的资源被其他处于阻塞状态的进程占有，该进程就会因为不能获得所申请的资源而被阻塞。若此时该进程恰好又占有了前述其他进程所需要的资源，那么这一组进程就可能因为等待释放自己所需要但被其他进程已占有的资源而无法向前推进。这种由于多个进程竞争共享资源而引起的进程不能向前推进的僵死状态称为死锁。

产生死锁的必要条件：互斥条件、请求和保持条件、不剥夺条件、环路等待条件。

注意：只有当上述 4 个条件同时满足时才会发生死锁。

处理死锁的基本方法

处理死锁的基本方法有预防死锁、避免死锁、检测并解除死锁和忽略死锁问题。

①死锁的预防：摒弃请求和保持条件、摒弃不剥夺条件、摒弃环路等待条件

②死锁的避免

a.系统的安全状态

不安全状态不一定是死锁状态，但当系统进入不安全状态之后，便可能进入死锁状态。反之，只要系   统处于安全状态，系统可避免进入死锁状态。因此，避免进程死锁的实质在于使系统处于安全状态。

③死锁定理：用于检测系统所处的资源分配状态 S 是否为死锁状态。

死锁定理为：S 为死锁状态的充分条件是当且仅当 S 状态的资源分配图是不可完全简化的。

*四章    内存管理

存储器的层次结构

图 4-1 存储器的层次结构

程序的链接方法：静态链接、动态链接

程序的装入

将一个用户的源程序变为一个可在内存中执行的程序，通常要经过编译、链接和装入 3 个阶段。

根据形成在内存中物理地址的时机不同，把程序的装入方式分为**装入方式、可重定位装入方式（静   态重定位）和动态运行时装入方式。

连续分配方式有 3 种类型：单一连续区分配方式、固定分区分配方式、动态分区分配方式。

动态分区分配算法：**适应算法 FF、循环**适应算法 NF、较佳适应算法 BF

内存回收流程：释放一块连续的内存区域，如果被释放区域与其他空闲区间相邻，则合并空闲区，   修改空闲分区链。

基本分页存储管理方式

页：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页。

页框：将物理内存空间分成与页大小相同的若干个存储块，称为页框或页帧。

基本分页的逻辑地址结构包含两部分：页号 p 和页内偏移量 W。若用 m 位表示逻辑地址，页大小为 2n 字节，则用低 n 位表示页内偏移量 W，用高 m-n 位表示页号 p。

若 A 为逻辑地址，L 为页大小，p 为页号，W 为页内偏移量，则有以下计算关系。

p=INT（A/L） W=MOD（A/L）

物理地址=页框大小 x 页框号+页内偏移量。

快表：也称转换后援缓冲（TLB），是为了提高 CPU 访存速度而采用的专用缓存，用来存放较近被访问过的页表项。

在 TLB 中找到某一个页号对应的页表项的百分比称为 TLB *率。当能在 TLB 中找到所需要的页表项时，有效访存时间等于一次访问 TLB 的时间加上一次访问内存的时间。当没有在 TLB 中找到所需要的页表项时，访存时间等于一次访问 TLB 的时间加上两次访问内存（一次访问内存页表，一次访问内存读写数据或指令）的时间。

基于分页的虚拟存储系统

虚拟存储技术的好处：提高内存利用率、提高多道程序度、把逻辑地址空间和物理地址空间分开，使程序员不用关心物理内存的容量对编程的限制。

主要特征。离散性、多次性、对换性、虚拟性。

页分配和置换策略：固定分配局部置换、可变分配全局置换、可变分配局部置换

分配算法

按比例分配算法：为进程分配的页框数=进程页数/所有进程页数的总和×页框数。

页置换算法

较佳置换算法

该算法选择以后永远不会被访问的页或者在未来较长时间内不再被访问的页作为换出页。因此,该算法主要用于理论研究。

**先出页置换算法（FIFO）

FIFO 是较简单的页置换算法。实现这种算法的一种方式是为每个页记录该页调入内存的时间，当选择换出页时，选择进入内存时间较早的页。

较近较久未使用 LRU 置换算法

LRU 置换算法是选择较近较久未使用的页换出。

对该访问序列采用 LRU 置换算法发生了 9 次置换，性能优于 FIFO 算法，但较较佳置换算法差。

抖动：多道程序度太高，使运行进程的大部分时间都用于进行页的换入、换出，而几乎不能完成任何有效工作的状态称为抖动。引起系统抖动的主要原因是系统中的进程数量太多，每个进程能分配到的   页框太少，以至于进程运行过程中频繁请求调页。

分段机制的引入：优点是方便编程、分段共享、分段保护、动态链接，以及存储空间的动态增长。

分页与分段的主要区别

分页和分段都属于离散分配方式，都要通过数据结构与硬件的配合来实现逻辑地址到物理地址的映   射，主要区别如下。

页是按物理单位划分的，分页的引入是为了提高内存的利用率和支持虚拟存储。而段是按逻辑单位划分的，一个段含有一组意义相对完整的信息。引入分段的目的是为了方便程序员编程。

页的大小是固定的。而段的大小不固定，取决于用户编写的程序和编译器。

分页的地址空间是一维的，程序员给出的地址只是一个助记符，已知的逻辑地址是一个数。分段的地址空间是二维的，程序员在标识一个逻辑地址时需要给出两个数：一个是段号，一个是段内偏移。

段页式存储管理：物理地址=页框号×页框大小+页内偏移 W