3 2

10.40 10.20 12.80 13.80 2.40 3.60 4.8 3.6 平均周转时间T=(2+1.8+2.4+3.6)/4=2.45小时 平均带权周转时间W=(1+6+4.8+3.6)/4=3.85小时

作业五：存储管理

1、假定某页式虚拟系统中，页面大小为100个单元，某作业占有实页面数为M=3，它的访问地址（走向）序列为75，175，66，267，32，102，333，166，22，255，256（数字为虚存的逻辑地址）。（1）请指出这些单元对应的页面访问顺序序列；（2）按先来先服务（FIFO）页面淘汰算法求出缺页率f，并画出图表表示之；（3）按最近最久未使用（LRU）页面置换算法求出缺页率f，并画出图表表示之。 2、有系统其主存容量为1024K（字节），有6个作业同时到达，各作业要求主存量和运行时间如下表所示。假定系统初启时，将主存1024K按作业的编号顺序分给各道作业，并假定是多CPU下，分配到主存的作业都可以立即运行。请问： （1）1秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？ （2）2秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？ （3）在（2）后，此时有一个作业7要求进入主存，它需要主存量为30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情况。

作业编号 1 2 3 4 5 6

需主存量（K） 200 120 100 50 80 320 运行时间（s） 2 1 3 1 3 2 作业五解答过程：

1、（1）访问序列为0，1，0，2，0，1，3，1，0，2，2。 （2）FIFO：

页面 1 2 3 缺页 0 0 1 1 0 0 1 0 2 2 1 0 0 2 1 0 1 2 1 0 3 3 2 1 1 3 2 1 0 0 3 2 2 0 3 2 2 0 3 2 × × √ × √ √ × √ × √ √ 缺页率f=5/11=45.45%。 （3）LRU： 页面 1 2 3 缺页 0 0 1 1 0 0 0 1 2 2 0 1 0 0 2 1 1 1 0 2 3 3 1 0 1 1 3 0 0 0 1 3 2 2 0 1 2 2 0 1 × × √ × √ √ × √ √ × √ 缺页率f=5/11=45.45%。 2、（1）1秒后，主存空白区按首次适应和最佳适应算法的链接方式： 首次适应算法：120→50→154 200 最佳适应算法：50→120→154 120 （2）2秒后，主存空白区的链接方式： 100 首次适应算法：320→50→474 50 最佳适应算法：50→320→474 80 （3）2秒后，作业7要求进入主存： 320 首次适应算法：290→50→474 154（空闲） 最佳适应算法：20→320→474

作业六：文件管理

1、在UNIX系统中，为使文件的索引表较小又能允许组织大文件，采用直接索引与多次间接索引（多级索引）方式，给出一个文件的所有磁盘的块号，如下图。假设每个磁盘块大小为1024字节，并且每个间接块容纳256个块号，试问： （1）如某进程要读取某文件的字节偏移量为9000处的数据，应如何找到它所在的磁盘块及块内位移量？

（2）如想要存取350000处，又将如何？ 直接0 直接1 直接2 直接3 直接4 直接5 直接6 直接7 直接8 直接9 间接 间接 间接 4096 228 45423 401 702 11111 10 101 367 90 428 9156 824 9156 0 331 331 75 3333 3333 816 数据块 808 367 数据块 二次间址 一次间址 2、磁道（0-90道）的存取正在处理第55道的服务请求，对于磁盘访问序列（磁道号）：22、77、35、90、40、83、66，试问对以下的磁盘I/O请求调度算法而言，满足以上请求序列，磁头将如何移动，移动距离为多少？若每移动一个柱面需3ms，计算总共花费的寻道时间。 （1）先来先服务算法（FCFS） （2）最短查找时间优先调度（SSTF） （3）扫描调度（SCAN）（电梯调度算法） （4）循环扫描（C-SCAN）算法

3、如果磁道范围0-99，刚结束第50道的服务请求，对于磁道序列70，25，40，85，90，55，分别按第2题（1）-（4）四种磁道扫描方法，磁头将如何移动？

作业六解答过程：

1、（1）根据9000/1024=8.8，故该字节在文件索引8（从0开始计）直接块中，于是可从表目项中读出内容为367，即该字节在磁盘块号为367的盘块中；再根据9000mod1024=808，查表在367号磁盘块的808字节即为文件的9000字节。

（2）350000/1024=341.8，则该字节在文件的逻辑块号为341的块中，故可知它必在二次间接寻址中（因为直接+1次间接可寻256+10=266块）。根据(341-266)/256=75/256=0.29（整数部分为0），可知其在二次间接块中0的表目上，又因为75mod256=75，可知在一次间接75表目处，从题表中可分别读出表目项内容为331和3333，可知在磁盘块3333中。由350000mod1024=816，得出文件的350000字节是3333磁盘块的816字节。 2、（1）先来先服务算法（FCFS）：访问序列55→22→77→35→90→40→83→66

总移动柱面距离为：33+55+42+55+50+43+17=295，总寻道时间为3ms*295=885ms。 （2）最短查找时间优先调度（SSTF）：根据各个I/O请求的不同，总是为接近当前磁头位置的请求提供优先服务，也就是先执行查找时间最小的那个请求。由于查找时间正比于两个请求的柱面差值，所以磁头移动总是移到距当前最近的柱面上去。很明显，它比FCFS改善了磁盘的服务。从本质上讲，它是SJF短作业优先调度的形式。同样，可能导致某些请求长期得不到服务（被饿死）（当不断有I/O请求时）。 访问序列55→66→77→83→90→40→35→22

总移动柱面距离为：11+11+6+7+50+5+13=103，总寻道时间为3ms*103=309ms。 （3）扫描调度（SCAN）：由于I/O请求具有动态性质，所以可以采取扫描法。磁头从磁盘的一端出发，向另一端移动，扫过所有柱面，遇到请求就服务。直到移到另一端后，移动方向反过来，继续做下面的服务。

访问序列55→66→77→83→90→40→35→22

总移动柱面距离为：11+11+6+7+50+5+13=103，总寻道时间为3ms*103=309ms。

（4）循环扫描（C-SCAN）算法：它是SCAN扫描算法的变种，这是为了适应极大量存取请求而设计的。磁头臂总是从0号柱面至最大号柱面顺序扫描，到头后直接返回0号柱面重复进行，就像是循环至0号柱面一样（也可视为单向扫描）。在一个柱面上，磁头臂往往停留，待磁盘旋转一定圈数之后，再移向另一个柱面。为了在磁盘移动每一周时间内执行更多的存取，必须考虑旋转优化（考虑等待时间与传送时间）。

访问序列55→66→77→83→90→0→22→35→40

总移动柱面距离为：11+11+6+7+90+22+13+5=165，总寻道时间为3ms*165=495ms。