操作系统—CPU调度与内存管理

忘是亡心i 2021-11-05 07:02 783阅读 0赞

## CPU调度与内存管理 ##

### 1.CPU调度算法 ###

#### 1>先来先服务调度算法 (FCFS): ####

就是按照各个作业进入系统的自然次序来调度作业. 这种调度算法的优点是实现简单, 公平. 其缺点是没有考虑到系统中各种资源的综合使用情况, 往往使短作业的用户不满意, 因为短作业等待处理的时间可能比实际运行时间长得多

#### 2>短作业优先调度算法 (SPF) : ####

就是优先调度并处理短作业, 所谓短是指作业的运行时间短. 而在作业未投入运行时, 并不能知道它实际的运行时间的长短, 因此需要用户在提交作业同时提交作业运行时间的估计值

#### 3>最高响应比优先算法(HRN) : ####

FCFS可能造成短作业用户不满, 短作业优先可能使得长作业用户不满, 于是提出HRN, 选择响应比最高的作业运行. 响应比 = 1+作业等待时间/作业处理时间

#### 4>基于优先数调度算法(HPF) : ####

每一个作业规定一个表示该作业优先级别的整数, 当需要将新的作业由输入并调入内存处理时, 优先选择优先数最高的作业

#### 5.时间片轮转调度算法 ####

时间片轮转调度算法主要用于分时系统, 在这种算法中, 系统将所有的就绪进程按到达时间的先后次序排成一个队列, 进程调度程序总是选择从就绪队列中第一个进程执行, 即先来先服务的原则, 但仅能运行一个时间片, 如100ms, 在使用完一个时间片后, 即使进程并为完成其运行, 它也必须释放处理机给下一个就绪的进程, 而被剥夺的进程返回到就绪队列的末尾重新排队, 等候再次运行

### 2.内存管理方式 ###

#### 1>页存储 ####

为了便于在内存中找到进程的每个页面所对应的物理块, 系统**为每个进程建立一张页表**, 记录页面在内存中对应的物理块号, 页表一般放在内存中. 在配置了页表后, 在进程执行时, 通过查找该表, 即可找到每页在内存中的物理块好. 页表的作用是实现从页号到物理块号的映射, 这种是页存储

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]

#### 2>段存储 ####

将用户程序地址空间分成若干个大小不等的段, 每段可以定义一组相对完整的逻辑信息. 存储分配时, 以段为单位, 段与段在内存中可以不相邻, 实现了离散分配, 这就是段存储管理方式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 1]

#### 3>段页存储 ####

作业的地址空间首先被分成若干个逻辑分段, 每段都有自己的段号, 然后再将每段分成若干个大小相等的页. 对于贮存空间也分成大小相等的页, 主页的分配以页为单位, 这就是段页存储的管理方式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 2]

### 3.页面置换算法 ###

#### 1>概念 ####

缺页中断 : 缺页中断就是要访问的页不在主存, 需要**操作系统将其调入主存之后再进行访问**

页面置换算法 : 在地址映射的过程中, 若在页面中发现要访问的页面不在内存中, 则产生缺页中断. 当发生缺页中断时, 如果操作系统没有空闲页面, 则操作系统必须在内存中选择一个页面将其移出内存, 以便为即将调入的页面让出空间. 而选**择淘汰哪一页的规则叫做页面置换算法**

#### 2>OPT最优页面置换算法 ####

寻找在将来的时间段内, 最晚被访问到的页面, 然后将其置换(无法预知未来, 不现实)

#### 3>先进先出只算算法(FIFO) ####

最简单的页面置换算法就是先入先出置换算法, 这种算法的实质是, 总是选择在主存中停留时间最久的一页置换, 即先进入内存的页, 先退出内存

#### 4>最近最久未使用(LRU)算法 ####

它的实质是, 当需要置换一页时, 选择在最近一段时间里最久没有使用过的页面予以置换. 这种算法就是最近最久未使用算法

LRU算法是经常采用的页面置换算法, 并被认为是非常好的, 但是存在如何实现它的问题. LRU算法需要硬件的支持, 其问题是怎么确定最近最后使用时间的顺序.对此有两种可行的办法 :

*  1.计数器. 最简单的情况是使每个页表项对应一个使用时间字段, 并给CPU增加一个逻辑时钟或计数器. 每次存储访问, 该时钟都加1. **每当访问一个页面时, 时钟寄存器的内容就被复制到响应页表项使用时间字段里**. 这样我们就可以时钟保留着每个页面最后访问的"时间". 在置换页面时, 选择该时间最小的页面. 这样做, 不仅要查页表, 而且当页表改变时, 要维护这个页表中的时间, 还要维护时钟值溢出的问题
 *  2.栈. 用一个栈保留页号, 每当访问一个页面时, 就把它从栈中取出来放在栈顶上, 这样, 栈顶总是放着目前使用最多的页, 而栈底放着目前最少使用的页, 由于要从栈的中间移走一项, 所以要用具有头尾指针的双向链表连起来. 在最坏的情况下, 移走一页并把它放在栈顶需要改动6个指针. 每次修改都要有开销, 但需要置换哪个页面却可以直接得到, 用不着查找. 因为尾指针指向栈底, 其中有被置换页

#### 5>时钟(CLOCK)置换算法 ####

简单的CLOCK算法是给每一帧关联一个附加位, 称之为使用位. 当某一页首次装入内存时, 该帧的使用位为1; 当该页随后再被访问时, 它的使用位也被置为1. 对于页替换算法, 用于替换的候选帧集合看做一个循环缓冲区, 并且有一个指针与之相关联. 当某一页被替换时, 该指针被设置成指向缓冲区的下一帧. 当遇到需要替换一页时, 操作系统扫描缓冲区, 以查找使用位置为0的一帧. 每当遇到一个使用位为1的帧时, 操作系统就将该位重新置为0; 如果在这个过程开始时, 缓冲区中所有帧的使用为均为0, 则选择遇到的第一个帧替换. 如果所有帧的使用位均为1, 则指针在缓冲区中完整的循环一周, 把所有的使用位都置为0, 并且停留在最初的位置上, 替换该帧中的页. 由于算法循环地检查各页面的情况, 故称为CLOCK算法, 又称最近未使用算法

CLOCK算法的性能比较接近LRU, 而通过增加使用的位数目, 可以使得CLOCK算法更加搞笑. 在使用位的基础上再增加一个修改位, 则得到改进型的CLOCK置换算法. 这样,每一帧都处于下面四种情况之一

*  最近未被访问, 也未被修改(u=0, m=0)
 *  最近被访问, 但未被修改(u=1, m=0)
 *  最近未被访问, 但被修改(u=0, m=1)
 *  最近被访问, 被修改(u=1, m=1)

算法执行如下操作步骤 :

*  1.从指针的当前位置开始, 扫描帧缓冲区. 在这次扫描过程中, 对使用位不做任何修改. 选择遇到的第一个帧(u=0, m=0)用于替换
 *  2.如果步骤1失败, 则重新扫描, 查找(u=0,m=1)的帧. 选择遇到的第一个这样的帧用于替换. 在这次扫描过沉重, 对每个跳过的帧, 将它的使用位设置成0
 *  3.如果步骤2失败, 指针回到它的最初位置, 并且集合中所有帧的使用位均为0. 重复第一部和第二步, 就可以找到供替换的帧

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]: /images/20211104/155cfcc99e1541b6b9b20155f9031585.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 1]: /images/20211104/f919295fcd1c49c6b0850bc3ec15a261.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 2]: /images/20211104/27573c9e543c421da3b5bab5da478d49.png