深圳大学2015年操作系统复习提纲-吴少滨整理 - 图文

7.实时调度

（1）非抢占式调度算法：a.非抢占式时间片轮转调度算法 b.非抢占式优先调度算法 （2）抢占式调度算法：

a.基于时间终端的抢占式优先权调度算法 b.立即抢占的优先权调度算法

8.常用实时调度算法

（1）最早截止时间优先（EDF）算法 P101 根据任务的开始截止时间确定任务的优先级 开始截止时间越早，优先级越高

（2）最低松弛度优先（LLF）算法

松弛度（LF）=完成时间-处理时间-当前时间

例：任务A要求每20ms执行一次，执行时间10ms

任务B要求每50ms执行一次，执行时间25ms

t1( 0):LF(A1)=20-10-0 =10ms t2(10): LF(A2)=40-10-10=20ms LF(B1)=50-25-0 =25ms

9.死锁：指多个线程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前前进。

10.死锁的原因：

（1）竞争资源：当两个或以上进程需要两个或以上资源 （2）进程间推进顺序非法：请求和释放资源的顺序不当

11.产生死锁的必要条件

（1）互斥条件 （2）请求和保持条件 （3）不剥夺条件 （4）环路等待条件

12.预防死锁的方法

（1）摒弃“请求和保持”条件 （2）摒弃“不剥夺条件” （3）摒弃“环路等待”条件

13.银行家算法

14.资源分配图

第三章作业

P109 PPT126

PPT115

第四章

1.程序的装入

（1）绝对装入方式：将模块装入到内存中事先指定的位置，逻辑地址与物理地址相同 （2）可重定位装入方式：从0开始，逻辑地址与物理地址不同 （3）动态运行时装入方式：内存的物理地址可发生改变

2.程序的链接：静态链接、装入时动态链接、运行时动态链接

3.存储器管理的目的

为用户使用存储器提供方便

⑴.用户只需在自己的逻辑空间内编程，不需要了解自己将放在内存中的物理位置，也不需

要了解其它用户程序在内存中的物理位置

⑵.为用户提供充分大的存储空间（虚存管理）

充分发挥内存的利用率：让尽量多的用户程序调入内存运行

4.存储器管理的内容：

（1）内存分配：静态分配和动态分配

（2）地址映射：绝对映射、静态映射、动态映射

（3）内存保护：a.保护内存不被非法访问b.不非法访问其它用户（包括系统）内存 （4）内存扩充：在逻辑上扩充内存的空间

5连续分配方式 （1）单一连续分配

一个用户程序独占连续的内存用户区 只能用于单用户、单任务的OS中 系统分两个内存区：系统区和用户区

（2）固定分区分配：划分多个区域可供多用户、多任务使用 ①划分分区方法

a.分区大小相等：简单，大程序装不下，小程序浪费、

b.分区大小不等：将内存区分成多个较小的分区、适量的中等分区和少量的大分区 适应性强，特别大的程序可能仍装不下 ②内存分配：

a.首次适应算法(FF)：按序选择第一个满足要求的内存区

b.最佳适应算法(BF)：仅当与程序大小相当的分区空闲时才予分配

（3）动态分区分配

优点：可以按照用户进程实际大小，动态地分配内存空间，提高内存的使用效率 缺点：不管采用何种算法，都必将产生小的、不可利用的空闲分区（碎片） ①分配所用的数据结构 a.空闲分区表 b.空闲分区（双向）链表 ②回收操作

无相邻空闲分区自己建立一个新表项

回收区与相邻的空闲分区合并以前一个空闲分区地址的首址为新空闲分区的首址 ③分配算法

a.首次适应算法（FF）：