搜索
一、进程调度•如何从就绪队列中选择一个进程使其运行？•从就绪队列中按一定的策略选择一个进程，使其占有处理机。•进程调度的时机–正在运行的进程运行完毕。–正在执行的进程被阻塞，加入等待队列–时间片到–高优先级的进程进入就绪队列进程调度的评价指标•进程的等待时间•CPU的利用率•系统资源的利用率•响应时间•周转时间一般用平均周转时间来衡量一个调度算法的好坏。1、先来先服务法•根据进程到达就绪队列的次序，总是选择先到达的进程运行。•优点：公平性；管理简单（队列）。•看右边表格中的例子：•由于进程到达的随机性，可能使系统中的短作业等待时间长。作业CPU时间156224352、时间片轮转法（RR）•时间片：系统允许进程一次使用处理机的最长时间。•回忆：分时系统的工作原理。•工作原理：就绪队列中的进程，每次最多使用一个时间片。•硬件支持：计时器。时间片到，发生“计时中断”。•问题：时间片的大小如何确定？时间片的长短•就绪队列长短：越长，时间片越短。•响应时间的要求：•计算机的性能•进程切换的系统开销：一个进程让出处理机，另一个进程占有处理机。3、进程调度算法-优先数调度法•总是从就绪队列中选择优先级最高的进程。•问题1：优先数如何确定？–进程类别：系统进程，用户进程，前台，后台等–进程运行时间–作业的优先级等优先数调度法•问题2：当一个更高优先级的进程到达就绪队列时，如何处理？–抢占式–非抢占式：一旦分配CPU，就一直占用，直到主动放弃为止。•问题3：如果一个低优先级的进程在就绪队列中等待太长时间？–动态优先数：进程的优先级随系统情况不断变化。多级轮转调度法•时间片轮转与优先数结合。•按优先级将作业排成不同的队列。•先按优先级调度，优先级相同的，按时间片轮转。•前台作业与后台作业–交互式作业–批处理作业二、可变分区存储管理原理在作业要求装入主存时，根据作业的大小从空闲内存区中“切出”一片连续的区域。分区的大小和个数是不确定的•初始时，系统中只有一个连续的用户区域，随着作业的到达和撤消，用户区就被划分为若干个大小不等的区域。内存OS作业A作业B作业C可变分区存储管理的原理空闲区的管理•空闲分区表•序号起始地址大小状态•注意：这里的状态是指该表目的状态，其值表示该表目是空闲还是已使用。•空闲分区链空闲区大小；下一空闲区起始地址……1、内存分配与回收•（1）最先适应分配算法•空闲分区表按地址从小到大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。分配算法内存分配与回收作业请求LP=1是否越界？Y不能分配状态为空闲？NP=P+1长度≥LNY长度=L状态置为“空表目”YN起始地址=起始地址+L长度=长度-L最先适应分配算法•（2）最优适应分配算法•原理：将空闲区按大小从小到大排列，将满足需求的最小的空闲区分配给作业。•好处：为了更好地满足大作业的需求。•缺点：这样切下的空闲区容易变成“碎片”。•算法流程与最先适配法相同。分配算法•（3）最坏适配算法•从满足需求的最大的空闲区中为作业分配空间。•空闲分区表按大小从大到小排列。•优点：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。•缺点：但对大作业不利。•其流程为：分配算法用户作业请求Ｌ取分区表的第一个表项长度≥ＬＹ起始地址＝起始地址＋Ｌ长度＝长度－Ｌ长度＝ＬＮＹ状态置空表目不能分配如何判断待回收区是否与空闲区相连？–地址+长度=下一空闲区首地址空闲区的管理：为了便于空闲区的合并，采用链接结构。•按地址从小到大排序。•第一块和最后一块的情况。注意回收算法１、待回收区：其起始地址为Ａ，长度为Ｌ。２、上空闲区和下空闲区３、可能的四种情况：（１）上下都不空。（２）上空，下不空。（３）下空，上不空。（４）上下都为空。待回收区作业区作业区上下都不空待回收区作业区上空下不空在空闲分区表中找一个空表目，将其内容填入。上空闲区：大小＝大小＋Ｌ待回收区作业区待回收区下空上不空下空闲区：起始地址=A大小=大小+L上下都为空上空闲区：长度=长度+L+下空闲区起址不变。注意•如何判断待回收区是否与空闲区相连？地址+长度=下一空闲区首地址•空闲区的管理：为了便于空闲区的合并，采用链接结构。•按地址从小到大排序。•第一块和最后一块的情况。可变分区存在的问题及解决办法•碎片问题：一些很小的内存区域。•移动技术–将离散的碎片集合在一起。–不是任何时候都可以移动。–移动技术需要很大的系统开销。•保护问题–界地址法：基址和长度寄存器。三、页式存储管理“等分”内存把内存划分为大小相同的“块”把用户作业空间划分为大小相同的“页”页和块的大小相同在把作业加载到内存时，页和页之间不再连续。但页内连续。也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要时再加载。基本原理页式主存空间的分配与回收•用户需求：需要多少块？•内存空闲块的管理：位示图。•位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态：•0：空闲；1：已分配。主存分配•块号与字号、字长的关系：系统的字长一定，内存块从0开始编号，则有：•块号=字号*字长+位号•字号=[块号/字长]（取整的意思）•位号=块号MOD字长用户作业请求：块数B扫描位示图，查找为0的位空闲块数≥BN无法分配计算块号建立页表页号块号071122321页表•根据页号查页表，得到块号。•根据块号和页内地址计算物理地址1、页面调度先进先出法（FIFO）：将最先调入内存的页调出内存最近最久未使用算法（LRU：leastrecentlyused）：将最近一段时间内没有用过的页调出内存。实现这种算法的一种方法是在页表中为每一页增加一个‘引用位’标志，记录该页面自上次被访问以来所经历的时间，每访问一次都应重新计时。当需要替换时，检查每页的引用位，从中选出计时值最大的那一页调出。四、页式虚拟存储技术最近最不经常使用算法（LFU）：最近一段时间内使用次数最少的页调出内存。为每一个在内存的页设置一个计数器，选择计数器中的值最小的调出。•注意：LRU、LFU之间的区别。例题有一个分页式虚拟存储管理系统，每个进程在内存有3页数据区、1页程序区，刚开始时数据区为空。现有一个进程有以下访问序列：1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系统采用：（1）最近最少使用（LRU）淘汰算法（2）先进先出（FIFO）淘汰算法请计算缺页次数和发生缺页中断后的淘汰页号。分析•（1）采用FIFO方法•将内存中的页按进入的先后次序排队，后来的加入队尾，先来的先出去。访问队列：154123215424351154423315422351内存155422315442351154423155423缺页中断页面替换154231543答案：缺页中断的次数为12次，页面替换的次序是：154231543。FIFO方法访问队列：154123215424351154423335422351内存155122215442351141112155443缺页中断页面替换54321524答案：缺页中断的次数为11次，页面替换的次序是：54321524LRU算法五、磁盘空间的管理1、空闲空间的管理（1）位示图：用一个位来表示一个块。如果字长为32位，则字号、位号、块号之间的关系是：块号=字号*字长+位号字号=[块号/字长]位号=块号MOD字长（2）空闲空间链：在空闲块中利用几个字节，存放下一空闲块的块号。2成组链接法假设初始化时系统已把专用块读入内存L单元开始的区域中，分配和回收的算法如下：（1）分配一个空闲块查L单元内容（即空闲块数）；当空闲块数1时；i＝L＋空闲块数（把i作为主存地址）；从i单元得到一空闲块号；把该块分配给申请者；空闲块数减1。当空闲块数＝1时取出L＋1单元内容（一组的第一块块号）；其值＝0，无空闲块，申请者等待；不等于零把该块内容复制到专用块，并将该块分配给申请者；把专用块内容读到主存L开始的区域。（2）归还一空闲块（即把归还的块号加到空闲块链中）取L单元的空闲块数；当空闲块数100时空闲块数加1；j＝L＋空闲块数（把j作为主存地址）；归还块号填入j单元。当空闲块数＝100时把主存中登记的信息写入归还块中；把归还块号填入L＋1单元；将L单元置成1。磁盘空间管理（3）空闲空间表首块号长度必须连续分配。七、磁盘调度•磁盘是共享设备，可以同时为多个进程服务。•目前的磁盘都是活动磁头，因此读写时间包括：–查找时间：磁头移动到正确的磁道的时间。–延迟时间（等待时间）：磁头等待盘片旋转到正确的扇区下的时间。–传输时间：数据从磁盘读到内存的时间。•在上述三个时间中，查找时间、延迟时间可以通过调度策略来改善。•移臂调度和旋转调度。1、移臂调度•将移动臂移动到指定柱面的调度。•影响寻找时间的长短。•当有若干个设备读写请求时，应该先响应哪一个？•原则：尽量避免移动臂频繁地来回移动。•先来先服务•最短查找时间优先•电梯法引例：假定一个活动磁盘有200个磁道，编号为0~199。当前磁头正在54道上服务，并且刚刚完成了39道上的请求。现有如下的磁盘访问请求序列（磁道号）：86、147、91、173、95、148、101、26、169、80、129、22试给出采用下列移臂调度算法后移动臂移动的顺序和移动总量（总磁道数）。（1）先来先服务法（2）最短寻找时间优先（3）电梯法移臂调度的评价•寻找时间越短越好。•寻找时间与移动臂移动的磁道数成正比。•因此，我们用移动臂移动的磁道数来评价某一个移臂调度的策略的好坏。移臂调度策略•先来先服务：根据请求的到达先后次序，响应请求。17316914814712910195918680542622磁头移动的顺序为：86、147、91、173、95、148、101、26、169、80、129、22磁头的移动总量为：（86-54）+（147-86）+（147-91）+（173-91）+（173-95）+（148-95）+（148-101）+（101-26）+（169-26）+（169-80）+（129-80）+（129-22）=872最短查找时间优先•从当前位置开始，响应磁头移动距离最短的请求。•也就是离当前位置最近的请求。•注意：它不考虑移动臂移动的方向。首先从访问队列中找离54磁道最近的访问请求，结果是80，再从剩下的访问请求中找离80最近的，是86………。直到所有访问请求响应完为止。17316914814712910195918680542622磁头移动次序为：80、86、91、95、101、129、147、148、169、173、26、22磁头移动的总磁道数为：（80-54）+（86-80）+（91-86）+（95-91）+（101-95）+（129-101）+（147-129）+（148-147）+（169-148）+（173-169）+（173-26）+（26-22）=270电梯法•沿着当前磁头移动的方向，响应进程的请求。当该方向上无请求时，磁头就改变方向。•因此，一定要知道当前磁头的移动方向。从题意可知：磁头的移动方向为从外向内移动，也就是从0向199的移动。根据电梯法的调度原理，磁头的移动如下图所示：17316914814712910195918680542622磁头移动次序为：80、86、91、95、101、129、147、148、169、173、26、22磁头移动的总磁道数为：（80-54）+（86-80）+（91-86）+（95-91）+（101-95）+（129-101）+（147-129）+（148-147）+（169-148）+（173-169）+（173-26）+（26-22）=270旋转调度•移动臂定位后，有多个访问者等待访问该柱面时。•使延迟时间最短。•根据延迟时间来决定调度次序的调度。•三种情况：–（1）同一磁道上的不同扇区。–（2）不同磁道上的不同扇区。–（3）不同磁道上的具有相同编号的扇区。–对（1）（2）总是对先到达磁头位置下的