页面调度算法练习及答案

第四章页面调度算法
页面访问顺序为2 3 2 1 5 2 4 5 3 2 5 2，有三个物理页面，请画出OPT、LRU、FIFO、CLOCK 的页面置换顺序，并分别计算缺页次数。

注意CLOCK算法：先检查页面是否已经存在于物理页框中，（1）若在，仅把相应的页面访问位修改为1，查询指针不移动，其它页面的访问位的值不变；（2）若不在，则按照课本P153页图4-31的算法执行，一旦找到访问位为0的页面，则实行页面置换。

查询指针并不是每次都会循环重置所有页面的访问位，一旦找到合适的页面（访问位为0的页面），此次查询到此为止，查询指针不会继续向前移动。

注意：初始时，内存物理页面为空，所以，页面访问序列的前四项“2 3 2 1”会产生3次缺页中断，需要将此也计入缺页次数，所以每种置换算法的缺页次数
都应该在上图各自的结果的基础上加3次.。

时间片轮转调度练习题时间片轮转调度练习题时间片轮转调度是操作系统中常用的一种进程调度算法，它通过将CPU时间划分为固定长度的时间片，每个进程在一个时间片内执行一定的指令，然后切换到下一个进程。

这种调度算法能够公平地分配CPU时间，避免某个进程长时间占用CPU而导致其他进程无法运行。

下面我们来看几个关于时间片轮转调度的练习题。

1. 假设有三个进程P1、P2和P3，它们的到达时间分别是0、1和3，执行时间分别是4、2和3。

时间片长度为2。

请根据时间片轮转调度算法，计算每个进程的完成时间、周转时间和带权周转时间。

首先，按照到达时间的顺序，将进程排列为P1、P2和P3。

在第一个时间片内，P1执行2个单位时间，剩余执行时间为2。

然后，切换到P2执行2个单位时间，剩余执行时间为0。

接着，切换到P3执行2个单位时间，剩余执行时间为1。

再次切换到P1执行1个单位时间，剩余执行时间为1。

最后，切换到P3执行1个单位时间，剩余执行时间为0。

因此，P1的完成时间为5，P2的完成时间为4，P3的完成时间为6。

周转时间分别为5、3和3，带权周转时间分别为1.0、1.5和1.0。

2. 在一个时间片轮转调度算法中，如果所有进程的到达时间相同，执行时间也相同，那么它们的完成时间、周转时间和带权周转时间是否相同？为什么？如果所有进程的到达时间相同，执行时间也相同，那么它们的完成时间、周转时间和带权周转时间是相同的。

这是因为时间片轮转调度算法会依次执行每个进程，每个进程都会被分配相同的时间片。

由于所有进程的执行时间相同，它们会在同一个时间片内完成执行。

因此，它们的完成时间相同。

周转时间是指从进程到达时间到进程完成时间的时间间隔，由于所有进程的到达时间相同，所以周转时间也相同。

带权周转时间是指周转时间除以执行时间的比值，由于所有进程的执行时间相同，所以带权周转时间也相同。

3. 时间片轮转调度算法的优缺点是什么？它适用于什么样的场景？时间片轮转调度算法的优点是能够公平地分配CPU时间，避免某个进程长时间占用CPU而导致其他进程无法运行。

四、计算题1、某虚拟存储器的用户编程空间共32个页面，每页为1KB ，内存为16KB 。

假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：那么逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。

1．解：页式存储管理的逻辑地址分为两部分：页号和页内地址。

由条件“用户编程空间共32个页面〞，可知页号部分占5位；由“每页为1KB 〞，1K=210，可知内页地址占10位。

由“内存为16KB 〞，可知有16块，块号为4位。

逻辑地址0A5C 〔H 〕所对应的二进制表示形式是：000 1010 0101 1100，根据上面的分析，下划线部分为页内地址，编码 “000 10〞 为页号，表示该逻辑地址对应的页号为2。

查页表，得到物理块号是11〔十进制〕，即物理块地址为：10 11，拼接块内地址10 0101 1100，得10 1110 0101 1100，即2E5C 〔H 〕。

2、对于如下的页面访问序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5当内存块数量为3时，试问：使用FIFO 、LRU 置换算法产生的缺页中断是多少？写出依次产生缺页中断后应淘汰的页。

〔所有内存开场时都是空的，凡第一次用到的页面都产生一次缺页中断。

要求写出计算步骤。

〕2．解：采用先进先出〔FIFO 〕调度算法，页面调度过程如下：页面次序 1 2 3 4 1 2 5 1 2 3 4 5主存 页面 情况共产生缺页中断9次。

依次淘汰的页是1、2、3、4、1、2。

采用最近最少使用〔LRU 〕调度算法，页面调度过程如下：3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。

现有以下作业序列：96K 、20K 、200K 。

假设用首次适应算法和最正确适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的恳求，为什么?空闲分区表页面次序 1 2 3 4 1 2 5 1 2 3 4 5 主存 页面 情况3．解：假设采用最正确适应算法，在申请96K 存储区时，选中的是5号分区，5号分区大小与申请空间大d,-致，应从空闲分区表中删去该表项；接着申请20K 时，选中1号分区，分配后1号分区还剩下12K ；最后申请200K ，选中4号分区，分配后剩下18K 。

1.设某进程所需要的服务时间t=k ⨯q,k 为时间的个数,q 为时间长度且为常数.当t 为一定值时,令q →0,则有k →∞.从而服务时间为t 的进程的响应时间T 是t 的连续函数.对应于时间片调度方式RR,先来先服务方式FCFS 和线性优先级调度方式SRR,其响应时间函数分别为:Trr(t)=()λμμ-⨯tTfc(t)=()λμ-1Tsr(t)=()()()'11λμμλμ-⨯---t其中'λ=()λ⨯-ab1=r λ⨯取(μλ,)=(50,100),分别改变r 的值,计算Trr(t),Tfc(t)和Tsr(t),并画出其时间变化图.2.对实时系统的频率单调调度算法,对于由3个周期组成的实时任务序列,设每个周期为Ti(i=1,2,3),其相应任务的执行时间为C i(i=1,2,3).计算说明当进程执行时间与周期比之和为0.7时,能否保证用户所要求的时限(32=1.266).3.有5个批处理作业(A,B,C,D,E)几乎同时到达一个计算中心,估计运行时间分别为2,4,6,8,10分钟,它们的优先数分别为1,2,3,4,5(数值小的优先级低),在使用最高优先级优先调度算法时,计算作业的平均周转时间.解答：1.对(,λμ)=(50，100)T rr (t)=t,T fc (t)=1/50,T sr (t)=1/50-(1-100t)/(100-50t) 0r →时，T sr (t)→1/100+t 1r →时, T sr (t)→2t 图象如下：只有T sr (t)受r 值影响，且r 值增大，T sr (t)的斜率增大，y 截距由1/100趋向0，服务时间也增加。

题目：4.假定某页式管理系统,主存为64KB,分成16块,块号为0,1,2,3,4, ,15,设某作业有4页,其页号为0,1,2,3,被分别装入主存的2，4,1,6块,试问:(1)该作业的总长度是多少字节?(按十进)(2)写出该作业每一页在主存中的起始地址.(3)若给出逻辑地址[0,100],[1,50],[2,0],[3,60],请计算出相应的内存地址.(方括号内的第一个元素为页号,第二个元素为页内地址).5.有一个虚存系统,某进程内存占了3页,开始时内存为空, 执行如下访问页号顺序后:1,2,3,4,1,2,5,1,2,3,4,5.(1).采用先进先出(FIFO)淘汰算法,缺页次数是多少?(2).采用最近最少使用(LRU)淘汰算法,缺页次数是多少?6.有一只铁笼子,每次只能放入一只动物,猎人向笼中放入老虎,农民向笼中放入羊,野生动物园等待取笼中的老虎,饭店等待取笼中的羊,试用P.V操作写出能同步执行的程序.解答：4.解：(1)每块长度=64KB/16=4KB于是由题目可知，每页也是4KB。

调度算法考研题库及答案调度算法是操作系统中一个重要的概念，它决定了多任务环境下任务执行的顺序。

以下是一些调度算法的考研题目及其答案：1. 题目一：请简述什么是进程调度算法，并列举至少三种常见的进程调度算法。

答案：进程调度算法是操作系统用于决定哪个进程获得CPU资源的策略。

常见的进程调度算法包括：- 先来先服务（FCFS）调度算法：按照任务到达的顺序进行调度。

- 短作业优先（SJF）调度算法：优先调度预计执行时间较短的任务。

- 轮转（RR）调度算法：将CPU时间分配给所有任务，每个任务轮流执行固定的时间片。

2. 题目二：描述什么是死锁，并解释银行家算法是如何预防死锁的。

答案：死锁是指在多任务环境中，两个或多个进程在执行过程中因争夺资源而造成的一种僵局，此时这些进程无法继续执行。

银行家算法是一种预防死锁的算法，它通过分配资源前检查是否存在安全序列来决定是否分配资源，从而避免死锁的发生。

3. 题目三：解释什么是时间片轮转调度算法，并说明其优缺点。

答案：时间片轮转调度算法是一种CPU调度算法，它将CPU时间分割成固定长度的时间片，并轮流分配给就绪队列中的每个进程。

每个进程在获得CPU后只能执行一个时间片，时间片用完后，CPU将被分配给下一个进程。

优点包括简单易实现和响应时间可预测。

缺点是不适合I/O密集型任务，因为它们可能在时间片结束前不需要CPU。

4. 题目四：什么是优先级调度算法？请解释其工作原理。

答案：优先级调度算法是一种基于优先级的调度策略，每个进程都被赋予一个优先级值。

调度器总是选择最高优先级的进程来执行。

如果两个进程具有相同的优先级，它们将按照先来先服务的原则被调度。

这种算法适用于实时系统，可以确保高优先级的进程得到及时处理。

5. 题目五：描述什么是多级反馈队列调度算法，并简述其特点。

答案：多级反馈队列调度算法是一种动态的调度算法，它使用多个队列来管理进程，每个队列具有不同的优先级。

新创建的进程首先被放入低优先级的队列中。

1、试证明，短作业优先的作业调度算法可以得到最短的平均响应时间。

2、设有4道作业，它们的提交时间及执行时间如表所示：
表作业的提交时间和执行时间
作业号提交时间执行时间
1 10 2.0
2 10.2 1.0
3 10.
4 0.5
4 10.
5 0.3
均周转时间和平均带权周转时间，并指出它们的调度顺序。

（时间单位：小时，以十进制进行计算）。

3、设有4个作业J1、J2、J3、J4，它们的到达时间和计算时间如表所示。

若这4个作业在一台处理机上按单道方式运行，采用响应比高者优先调度算法，试写出各作业的执行顺序、各作业的周转时间及平均周转时间。

4、书上(P115 )第21,22题。

实验报告院（系）：数学与计算机科学学院专业班级：学号：姓名：实验地点：实验日期：年月日一、实验目的及要求通过本实验可以加深理解有关虚拟存储器的工作原理，进一步体会和了解页面替换算法的具体实现方法。

二、实验环境PC /Windows系统/Visual C++6.0三、实验内容①实现三种算法：先进先出；OPT；LRU②页面序列从指定的文本文件（TXT文件）中取出③输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数/*全局变量*/int mSIZE; /*物理块数*/int pSIZE; /*页面号引用串个数*/static int memery[10]={0}; /*物理块中的页号*/static int page[100]={0}; /*页面号引用串*/static int temp[100][10]={0}; /*辅助数组*//*置换算法函数*/void FIFO();void LRU();void OPT();/*辅助函数*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*先进先出页面置换算法*/void FIFO(){int memery[10]={0};int time[10]={0}; /*记录进入物理块的时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE) /*如果不在物理块中*/{count++; /*计算换出页*/max=time[0]<time[1]?0:1;for(m=2;m<mSIZE;m++)if(time[m]<time[max])max=m;memery[max]=page[i];time[max]=i; /*记录该页进入物理块的时间*/ for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++)你temp[i][j]=memery[j];}}compute();print(count);}/*最近最久未使用置换算法*/void LRU(){int memery[10]={0};int flag[10]={0}; /*记录页面的访问时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];flag[i]=i;for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;elseflag[j]=i; /*刷新该页的访问时间*/ }if(k==mSIZE) /*如果不在物理块中*/{count++; /*计算换出页*/ max=flag[0]<flag[1]?0:1;for(m=2;m<mSIZE;m++)if(flag[m]<flag[max])max=m;memery[max]=page[i];flag[max]=i; /*记录该页的访问时间*/ for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}elsefor(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}compute();print(count);}/*最佳置换算法*/void OPT(){int memery[10]={0};int next[10]={0}; /*记录下一次访问时间*/int i,j,k,l,m;int max; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE) /*如果不在物理块中*/{count++;/*得到物理快中各页下一次访问时间*/for(m=0;m<mSIZE;m++){for(l=i+1;l<pSIZE;l++)if(memery[m]==page[l])break;next[m]=l;}/*计算换出页*/max=next[0]>=next[1]?0:1;for(m=2;m<mSIZE;m++)if(next[m]>next[max])max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/ memery[max]=page[i];for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}elsefor(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}compute();print(count);}四、实验步骤页面置换：在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。

页面置换算法大题
页面置换算法是操作系统中的一种调度算法，用于解决内存管理中的问题。

它可以将内存中的页面（也就是存储单元）与外存中的页面进行交换，以实现内存空间的有效管理。

常见的页面置换算法有以下几种：
1. 先进先出（FIFO）算法：按照页面进入内存的先后顺序进
行置换，先进入内存的页面将先被置换出去。

这种算法简单直观，但是容易出现Belady异常，即页面置换频率增加导致缺
页率上升的现象。

2. 最近最久未使用（LRU）算法：根据页面最近的使用情况进行置换，最近使用过的页面会被保留在内存中，而最久未使用过的页面将会被置换出去。

这种算法相对较为复杂，需要记录每个页面最近的使用时间，并进行相应的计算。

3. 最不经常使用（LFU）算法：根据页面使用的频率进行置换，使用频率最低的页面将被置换出去。

该算法需要记录每个页面的使用次数并进行相应的计算。

4. 时钟（Clock）算法：通过维护一个类似于时钟的循环链表
结构，当需要进行页面置换时，顺时针遍历链表，找到一个未被访问过的页面进行置换。

这种算法相对简单，适合于硬件实现。

5. 最佳置换（OPT）算法：根据未来一段时间内每个页面的访
问情况进行置换，选择未来最久才会被访问的页面进行置换。

这种算法需要对未来一段时间内的页面访问情况进行预测，因此比较困难。

每种页面置换算法都有其优势和局限性，选择合适的页面置换算法需要根据具体的应用场景和需求来进行权衡和选择。

操作系统进程调度练习及答
案(总5页)
本页仅作为文档封面，使用时可以删除
This document is for reference only-rar21year.March
1 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销，若分别按先来先服务（FCFS）、非抢占式及抢占式的短进程优先（SPF）、高响应比优先、时间片轮转、多级反馈队列和立即抢占式多级反馈队列七种调度算法，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。

答：
2 在银行家算法中，若出现下列资源分配情况：
请问：
（1）此状态是否安全
（2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它
答：（1）安全，因为存在安全序列{P0,P3,P4,P1,P2}
（2）系统能分配资源，分析如下。

① Request(1,2,2,2) <= Need2(2,3,5,6);
② Request(1,2,2,2) <= Available2(1,3,5,4)改成Available2(1,6,2,2)；
③系统先假定可为P2分配资源，并修改Available2，Allocation2和Need2向量，
由此形成的资源变化情况如下图所示：
④再利用安全性算法检查此时系统是否安全。

如下图
由此进行的安全性检查得知，可以找到一个安全序列
{P2,P0,P1,P3,P4}。