操作系统期末复习

操作系统期末复习

2022年6月25日更新，第27题修正

1. 下列选项中,( C)不是操作系统关心的主要问题。A.管理计算机裸机B.设计、提供用户程序与计算机硬件系统的界面。C.高级程序设计语言的编译器D.管理计算机系统资源

操作系统的主要功能是管理计算机软硬件资源、扩充裸机以提供功能更加强大的扩充机器，并充当用户与硬件交互的中介

1. 顺序程序和并发程序的执行相比，( A)。A. 并发程序执行总体上执行时间快B.顺序程序执行总体上执行时间快C. 基本相同D. 有点不同
2. 用信号量操作 signal 操作唤醒一个等待进程时，被唤醒进程的状态为（ B）。A.等待B.就绪C.运行D.用户自己确定
3. 分页存储管理中，逻辑地址空间和物理地址空间的对应关系由（A）指出。A.页表B.快表C.段表D.变换表
4. 在缺页处理过程中，操作系统执行的操作不可能是（D）。A.修改页表B.磁盘 I/OC.分配页框（物理块）D.调用打印机驱动程序

缺页处理过程：

1. 系统陷入内核态，在堆栈中保存程序计数器
2. 启动一个汇编代码例程来保存通用寄存器及其它容易丢失的信息，以免操作系统被破坏
3. 当操作系统发现这是一个页面终端时，会查出发生页面中断的虚拟页面(也就是进程地址空间的页面)。
4. 检查虚拟地址的有效性以及保护位，如果保护位出现错误就杀死进程
5. 在操作系统中找出一个空闲的页框，如果没有空闲页框就通过页面置换算法查找到一个需要换出的页框（磁盘IO，分配页框）
6. 如果页框中的内容被修改了，那么需要将修改的内容保存到磁盘上，此时会引发一个磁盘调用，发生上下文切换。
7. 页框干净后，操作系统根据虚拟地址对应磁盘上的位置，将保持在磁盘上的页面内容复制到“干净”的页框中，此时会引起一个都磁盘调用，发生上下文切换
8. 当磁盘中的页面全部装入页框后，会向操作系统发送一个中断，操作系统会更新内存中的页表项（修改页表）
9. 恢复缺页中断前的状态，将程序指令器重新指向引起缺页中断的指令
10. 调度引起页面中断的进程，操作系统返回汇编代码例程
11. 汇编代码例程恢复线程，将之前保存在通信寄存器中的信息恢复

(在以上过程中，缺页中断发生了用户态与内核态之间的切换，虚拟地址与物理地址之间的转换)

1. 在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合 并，为此需修改空闲区表，空闲区数增加一个的情况是（A）。A.无上邻空闲区，也无下邻空闲区B.有上邻空闲区，但无下邻空闲区C.有下邻空闲区，但无上邻空闲区D.有上邻空闲区，也有下邻空闲区
2. 设有两个进程共享 3 个同类资源，为使系统不会死锁，每个进程可以申请的资源数目最多为（ C）。A.0 个B.1 个C.2 个D.3 个
3. 在采用时间片轮转调度算法的系统中,如果时间片选择过大，所有的进程都在一个时间片中完成或者阻塞，则 此时时间片轮转调度算法等效于（C）。A. 优先权调度算法B. 短作业优先调度算法C. 先来先服务调度算法D.长作业优先调度算法
4. 对磁盘进行移臂调度时，既考虑了减少寻找时间，又不频繁改变移动臂的移动方向的调度算法是（A）A. 电梯调度B. 最短寻找时间优先C. 先来先服务D. 优先级高者优先
5. (1)由不同容量、不同成本和不同访问时间的存储设备所构成的存储系统中，容量最小速度最快的设备是寄存器。(2)CPU 状态分为系统态和用户态 ，从用户态转换到系统态的唯一途径是系统调用。(3)设磁盘的转速为 3000r/min，盘面划分成 20 个扇区，则读取一个扇区的平均时间为 1ms。(4)如果文件系统中有两个文件重名，应采用的目录结构是二级目录或者多级目录。> > > > > 3000> > > r> > > /> > > m> > > i> > > n> > > => > > 50> > > r> > > /> > > s> > > > 3000r/min=50r/s> > > 3000r/min=50r/s> > 所以转一圈的时间是> > > > > 1> > > s> > > /> > > 50> > > => > > 20> > > m> > > s> > > > 1s/50=20ms> > > 1s/50=20ms> > 由于一圈可以读取20个扇区，故读取一个扇区只需要1ms
6. • 页式存储管理可以为内存提供 2 种保护方式，即存储保护键和地址越界保护。

页式管理的内存保护方式有两种，分别为越界保护和访问保护

越界保护

将页号与页表的长度进行比较，如果超出页表长度则越界

访问保护

在页表中为每个物理块设置保护位，表示有效或无效

1. • 成组链接法适用于大型文件系统，用于文件的逻辑组织。

成组链接法

如图，成组链接法是一种用来记录磁盘空闲盘块的方法，接下来详细介绍成组链接法

空闲盘块号栈

空闲盘块号栈是用来存放当前可用的一组空闲盘块的盘块号（一般最多包含100个号）以及栈中尚有的空闲盘块号数

     N
    
   
   
    N
   
  
 N。

同时

     N
    
   
   
    N
   
  
 N还会作为栈顶指针时延。

这个空闲盘块号数

     N
    
   
   
    N
   
  
 N放在图中最上面，也就是栈中栈底的元素上面一个空间

---

空闲盘块的组织方式

1. 在文件区中的所有空闲盘块被分成若干个组，每100个盘块作为一组。我们假设这一个盘上的2017999号盘块是用来存放文件的，也就是作为文件区，如图所示，那么我们的盘中每一组的盘块号分别为201300、301400、…7801-7900、79017999（注意一下，这里的最后一个盘块是79017999，而不是79018000,具体原因在后面解释）
2. 每个组的第一个空闲盘块的栈底(也就是图中的S.free)记录下一组盘块的盘块数量，然后每个组的第一个空闲盘块的下标0~99这100个下标中存放指向下一组每个盘块的指针(详细点说，也就是每一组盘块都拿出第一个盘块来存放下一组的信息，其他99个盘块都用来存放真实的信息，这里要注意的是，这个用来存放下一组信息的盘块也是空闲盘块，当下一组盘块全部用完时，这一个盘块也是可以被拿去使用的)
3. 对于倒数第二组盘块的第一个盘块(也就是最后一个存有下一组盘块信息的“索引”盘块),由于它的下一组说最后一组了，所以下一组的第一个盘块不用存储任何盘块组信息了，所以对于我们这个“最后一个索引盘块”，它指向的下一组可以不需要第一个盘块(因为第一个盘块都是用来存储盘块组信息的嘛)，直接从第二个盘块开始计数，因此最后一组就只有99个盘块了

由上，空闲盘块的组织方式的数据结构大致可以描述为下列结构体：

structDiskFreespace{//下一组的数量int nextGroupNum;//指向下一组的指针数组structDiskFreespace*nextGroup[100];}

空闲盘块的分配与回收

1. • 请求页式存储管理页面置换算法不当也会导致抖动现象。

所谓抖动现象，就是不停的有页面从外存换入内存或者从内存换到外存，那么就会出现许多进程排队等待页面换入换出的情况，这会大大增加磁盘的有效访问时间，导致许多进程都花费大量的时间执行进程换入换出操作，而无法执行其他有效的工作

1. • 操作系统中所谓“设备独立性”，是指用户程序与设备之间无关系。

设备独立性指的是应用程序中所使用的设备，不局限于使用某个具体的物理设备。

也就是我使用键盘的话，你不一定要局限我使用哪一家品牌的键盘，不管是哪一家的键盘，我都是即插即用

1. • 设备分配算法一般不采用先来先服务算法

设备分配算法一般采用先来先服务或者优先级高者优先

1. • 只要死锁发生，产生死锁的四个必要条件一定存在，反之不成立。

死锁发生的前提有四个，破坏其中任意一个都不会发生死锁

分别是以下四个前提：

1. 互斥条件进程被分配的资源只能供一个进程使用，如果其他进程请求该资源只能等待
2. 请求和保持条件进程至少已经占有一个资源，并且提出了新的资源请求
3. 不可抢占条件进程已获得的资源在使用完之前不能被抢占，只能由自己在使用完以后释放
4. 循环等待条件在发生死锁时，必然存在一个进程—资源的循环链，如下如

1. • 页面最佳置换算法是一种性能最好，且容易实现的算法。

页面最佳置换算法确实是一种性能最好的算法，但他由于需要预先知道后面进程要访问的页面，所以这是一种理论上的算法，目前无法实现

1. • 通道的引入是为了建立独立的 I/O 操作，提高 CPU 操作和处理器的并行性

在加入设备控制器后，已经能大大减少CPU对I/O的干预，但是当主机所配置的外设很多时，CPU的负担仍然很重。

因此引入了I/O通道设备以建立独立的I/O操作，不仅使得数据的传送能够独立于CPU，对I/O操作的组织、管理及其结束处理也能尽量独立，以保证CPU能够有更多的时间继续数据处理。

或者说，通道的引入是为了使得其中一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。

在设置了通道以后，CPU只需要向通道发送一条I/O指令，然后转而可以做其他事情。在通道收到指令以后，便从内存中取出此次要执行的通道程序，然后执行该通道程序，在通道完成IO以后会向CPU发送中断请求。

具体过程如下图：

1. 现实生活总有很多类似进程同步和互斥的例子，请举例说明进程同步和互斥的概念，要说明原因。

在火车进站的时候，一个站台只允许一个火车进入，这个时候火车就是进程，站台就是临界资源，在一个火车进入站台以后，其他火车就不能进入了，这就是进程互斥，当前一个火车出站以后，后一个火车才能进站，这就是进程同步。

因此，进程的互斥是为了防止多个进程同时访问临界区会造成许多问题，比如如果多个火车进入同一个站台，那么火车就很可能发送碰撞。其次，同步是为了能够使程序有序运行，比如上面的例子，使得火车能够有序进站出站。火车需要遵顼(进站->出站->进站)的顺序有序进行

1. 你学过的进程抢占式调度算法各有哪些？比较分析哪一种开销更大?

抢占式调度算法

时间片轮转调度算法、抢占式短进程优先调度算法、抢占式优先级调度算法、多级反馈队列调度算法、抢占式最早截止时间调度算法、最低松弛度调度算法

非抢占式调度算法

先来先服务、非抢占式短进程优先调度算法、高响应比优先调度算法、非抢占式最早截止时间调度算法

---

抢占式调度算法开销更大，因为抢占式调度算法需要进行上下文切换，那么大量的CPU时间都被浪费在了寄存器、内核栈以及虚拟内存等数据的保存和恢复上，缩短了程序真正运行的时间

1. 什么是虚拟设备？SPOOLing系统具体有哪几部分组成？请分析SPOOLing系统是如何实现虚拟设备的？

虚拟设备就是将一个物理上独占的设备分成逻辑上的多个设备，使得多个进程可以共享使用一个物理设备。

SPOOLing技术是对脱机输入/输出系统的模拟，它建立在通道技术和多道程序设计技术的基础上，以高速随机外存(大多数为磁盘)为后续存储器。

SPOOLing系统由输入井、输出井、输出缓冲区、输入缓冲区、输入进程、输出进程、井管理程序组成

1. 输入井和输出井输入井和输出井在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入时的磁盘设备，用于暂存I/O设备输入的数据。输出井时模拟脱机输出的磁盘设备，用于暂存用户程序的输出数据
2. 输入缓冲区和输出缓冲区是两个内存中的缓冲区，用于缓和CPU和磁盘之间速度不匹配的矛盾.输入缓冲区用来暂存输入设备送来的数据，然后再传送到输入井.输出缓冲区是用来暂存输出井送来的数据，以传送给输出设备.
3. 输入进程SPi和输出进程SPo这里由两个进程来模拟脱机I/O时的外围控制机。其中SPi模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区送入输入井，当CPU需要输入设备时，直接从输入井读入内存就行了。SPo模拟脱机输出时的外围控制机，把用户要求输出的数据从内存传送到输出井，待输出设备空闲时将输出井中的数据经过输出缓冲区输出至输出设备上
4. 井管理程序用于控制作业与磁盘井之间信息的交换。当作业执行过程中向某台设备发出启动输入或者输出操作请求时，操作系统调用井管理程序，由其控制从输入井读取信息或将信息输出至输出井

所以为什么要使用SPOOLing技术呢？

因为在计算机系统中，I/O设备的速度是非常低的(相对于CPU而言)，所以需要使用SPOOLing技术将数据存放到井中，这样在I/O设备进行I/O操作时，CPU可以不用管他们而继续执行自己的工作，等到数据准备好以后，CPU直接读取就行了，输出操作也是一样的，CPU通过通过缓冲区将数据放到井中，等输出设备准备好就行了。

说白了，SPOOLing技术就是一个类似于一个寄存柜，放数据的人放进去以后通知取件人拿就行了，于是转而干自己的其他事情，不需要一直等待

SPOOLing技术的特点

1. 提高了IO速度。从对于低速的I/O设备的操作变成对井的操作，如同统计操作，提高了I/O速度，解决了CPU与I/O设备所有大雨不匹配的矛盾
2. 将独占设备改造成共享设备。在SPOOLing系统中，实际上没有为任何进程分配设备，而是在井中为设备分配一个存储区和一张I/O请求表，这样所有进程的I/O请求都能被直接接受，这样就像是在使用一个共享设备了。
3. ==实现虚拟设备功能。==由于将独占设备改造成了共享设备。对于每个设备而言它们都会觉得自己独占了一个**(逻辑)**设备，但是宏观上是多个进程在使用一个设备。SPOOLing系统实现了将独占设备改造成若干个对应的逻辑设备的功能

SPOOLing技术是如何实现虚拟设备的？

当进程请求输出时，SPOOLing系统统一为他执行输出操作，但是并不是真正将设备分配给进程，而是：

1. 由输出进程在输出井中为之申请一个空闲磁盘块区，将要打印的数据送入其中
2. 输出进程再为用户进程申请一张空白的用户请求打印表，将用户的打印要求填入其中，再将该表挂到请求打印队列上

这样，对于用户进程来说，它就好像已经完成了输出操作，剩下的真正的输出工作交给输出进程就OK了。

1. 文件删除后能否恢复？为什么？如果能恢复，如何让文件彻底删除不能恢复？

文件删除后可以恢复，因为文件的删除过程只是找到文件的FCB，将其状态置为删除，而其他信息并没有改变。

要想彻底删除文件，则需要将原先文件在硬盘中的数据覆盖，并清空文件索引中的信息

1. 简述基本段式存储管理中地址转换过程

段式存储管理的地址转换过程如下：

1. 取出逻辑地址中的段号，与寄存器中的段表长度作比较，如果发现短号大于等于(这里应该是书上写错了，实际上段号应该从0开始)段表长度，则说明当前逻辑地址的段已经不在寄存器存储的段表的范围内了，那么就发生越界中断
2. 计算出段表项地址，计算公式为段表始址+段号S*段内地址长度，通过段表项地址读出段表项
3. 从段表项中读出该段段长SL，比较段内地址d和段长SL,如果d>=SL,则发出越界中断信号
4. 将找出的段表项中的基址与段内地址d相加，得出内存物理地址

1. 在一个请求分页系统中，已知某程序访问以下页面：0、1、4、3、0、2、6、5、1、2、3、2、1、2、6，如果 程序有 3 个页框可用，所有内存开始时都是空的，凡第一次用到的页面都会产生一次缺页中断。 要求：(1)采用 FIF0 先进先出置换算法，出现多少次缺页？求缺页率(要求写出计算过程)；FIFO：页面走向014302651232126物理页M0000333666222222物理页M111100055533333物理页M24442221111116缺页否√√√√√√√√√√√×××√缺页次数为：12缺页率= 12 15 = 80 % \frac{12}{15}=80% 1512​=80%(2)采用 LRU 最近最少使用置换算法，出现多少次缺页？求缺页率(要求写出计算过程)LRU：页面走向014302651232126物理页M0014302651232126物理页M101430265123212物理页M20143026511331缺页否√√√√√√√√√√√×××√缺页次数：12缺页率= 12 15 = 80 % \frac{12}{15}=80% 1512​=80%
2. 有 2 个人甲和乙共用一个账号，他们都可以用该账号到任何一家联网的银行自动存款或取款。假定银行的 服务系统有存款 save()和取款 take()两个并发进程组成，其规定每次存取款只能是 100 元。若进程的结构如 下：int amount=0; cobegin void save(){ int m1; m1 = amount; m1 = m1 + 100; amount = m1;} void take(){ int m2; m2 = amount; if(m2 >= 100){ m2 = m2 - 100; amount = m2; } else{ printf(“余额不足！\n”); }} coend

（1）你估计系统工作是会出现怎样的错误？说明原因。

假设是甲取款，乙存款可能出现如下几种错误：

1. 甲取走了100元，乙存了100元，但是最后余额是+100save()中m1刚读取完amount，take()中的m2也读取了amount，在甲的take()执行完后扣款完成变成-100，但是乙的save()后面才完成，余额就变成了+100
2. 甲取走了100元，乙存了100元，但是最后余额是-100save()中m1刚读取完amount，take()中的m2也读取了amount，在乙的save()执行完后存款完成变成+100，但是甲的take()后面才完成，余额就变成了-100
3. 甲乙都存款，但是最后余额凭空少了100元
4. 甲乙都取款，但是最后余额凭空多了100元

（2）假设开始时甲先存了 2 次钱，但在第 3 次存钱时，乙却正在取钱，则该账户上可能出现的余额是多少？ 正确的余额应该是多少？

可能出现的余额为100、200、300

正确的余额应该是200

1. 在某个采用虚拟分页内存管理方式的系统中，一个作业有 6 个页面。其中第 0、1、3、5，被分别装入到主存的 第 AH、13H、6BH、2EH 页框中，假定页面和页框大小均为 1024 字节，当作业在 CPU 上运行时，执行到其地址空间第 0F8E H 处遇到一条传送指令：MOV 08C5, 0B93（指令含义为：把逻辑地址 08C5 对应的数据传给逻辑地址 0B93 所对应的空间）。请完成以下问题(本题中所涉及的数字均为十六进制)：（1）画出页表并填写页表项内容：页号块号0AH113H36BH52EH（2）请模拟操作系统页式存储管理，转换出 0F8E H 及 MOV 指令中两个操作数 08C5 H, 0B93 H 的物理地址(用 十六进制表示)：1. 将0F8EH转化成物理地址： 0 F 8 E H = 0000111110001110 B 页 号 = 000011 B = 3 页 内 地 址 = 1110001110 B 0F8EH=0000111110001110B\ 页号=000011B=3 \页内地址=1110001110B 0F8EH=0000111110001110B页号=000011B=3页内地址=1110001110B页号3对应的块号为6BH即为 01101011 01101011 01101011,将其与页内地址直接拼接= 0001 ∣ 1010 ∣ 1111 ∣ 1000 ∣ 1110 B 0001|1010|1111|1000|1110B 0001∣1010∣1111∣1000∣1110B直接将其转化为16进制为 1 A F 8 E H 1AF8EH 1AF8EH1. 将08C5H转化为物理地址: 08 C 5 H = 0000100010100011 B 页 号 = 000010 B = 2 页 内 地 址 = 0010100011 B 08C5H=0000100010100011B \页号=000010B=2 \页内地址=0010100011B 08C5H=0000100010100011B页号=000010B=2页内地址=0010100011B 查找页表发现无此页，于是发生越界中断2. 将0B93H转化为物理地址 0 B 93 H = 0000101110010011 B 页 号 = 000010 B = 2 页 内 地 址 = 1110010011 B 0B93H=0000101110010011B\ 页号=000010B=2\ 页内地址=1110010011B 0B93H=0000101110010011B页号=000010B=2页内地址=1110010011B 查找页表无页号2，越界中断(3)如果当前只有第 0 页在快表(TLB) 中，则为了得到 0F8E H 处的指令，需要几次访问内存？具体过程如何？> ​ 首先计算出0F8EH的页号和页内地址：> > > > > > 0> > > F> > > 8> > > E> > > H> > > => > > 0000111110001110> > > B> > > > 页> > > 号> > > => > > 000011> > > B> > > => > > 3> > > > 页> > > 内> > > 地> > > 址> > > => > > 1110001110> > > B> > > > 0F8EH=0000111110001110B\ 页号=000011B=3\ 页内地址=1110001110B > > > 0F8EH=0000111110001110B页号=000011B=3页内地址=1110001110B> > > 1. 首先先用页号查找快表(快表不在内存，快表是一个高速缓冲寄存器)，发现没有命中。> 2. 访问页表寄存器(寄存器都不在内存中)，页号3<页表长度6，没有越界，所以取出页表始址，计算得到页表项地址： 页 表 始 址 + 页 号 × 页 表 项 长 度 页表始址+页号\times页表项长度 页表始址+页号×页表项长度> 3. 使用页表项地址访问页表(第一次访问内存)，取出对应的块号，将块号与页内地址拼接成物理地址> 4. 访问真正的物理地址，从物理地址中取出信息(第二次访问内存)> 5.
2. 某页式虚拟存储器的用户编程空间共32个页面，每页为2KB，内存为32KB。假定某一时刻用户作业有6页，页表 中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号07210515320(1)逻辑地址中，页号占多少位，页内位移占多少位？> 页号占> > > > > l> > > o> > > > g> > > 2> > > > (> > > 32> > > )> > > => > > 5> > > > log_2(32)=5> > > log2​(32)=5> > 页内位移占> > > > > l> > > o> > > > g> > > 2> > > > (> > > 2> > > ∗> > > 1024> > > )> > > => > > 11> > > > log_2(2*1024)=11> > > log2​(2∗1024)=11位(2)逻辑地址 0A5EH、0F8CH 所对应的物理地址是什么？> 1. 计算0A5EH的物理地址 0 A 5 E H = 0000101001011110 B 页 号 = 00001 B = 1 页 内 地 址 = 01001011110 B 0A5EH=0000101001011110B\ 页号=00001B=1\ 页内地址=01001011110B 0A5EH=0000101001011110B页号=00001B=1页内地址=01001011110B 查找页表发现无此页号，于是发生缺页中断> 2. 计算0F8CH的物理地址 0 F 8 C H = 0000111110001100 B 页 号 = 00001 B = 3 页 内 地 址 = 11110001100 B 0F8CH=0000111110001100B\ 页号=00001B=3\ 页内地址=11110001100B 0F8CH=0000111110001100B页号=00001B=3页内地址=11110001100B查找页表，找到页号3对应的块号为20，将其转化为二进制为 010100 B 010100B 010100B将其直接与页内地址拼接得到0101|0011|1000|1100B将其化为十六进制为538CH,故对应物理地址为538CH查找页表，发现无此页号，发生缺页中断
3. 在 UNIX 中，磁盘采用混合索引组织，索引节点 i 有 13 个地址项，其中有 10 个直接地址索引和一、二、三级间 接地址索引各一个，如果每个盘块有 512B 大小，每个盘块地址占用 4B，请计算：（1）每块可以存放多少个地址？> > > > > 512> > > /> > > 4> > > => > > 128> > > > 512/4=128> > > 512/4=128个（2）仅二次间接容量可以达到多大？> 128128512=> > > > > > 2> > > 7> > > > ∗> > > > 2> > > 7> > > > ∗> > > > 2> > > 9> > > > => > > > 2> > > 23> > > > B> > > => > > 8> > > M> > > B> > > > 2^72^72^9=2^{23}B=8MB> > > 27∗27∗29=223B=8MB（3）一个 2MB 的图片文件分别占用多少数据盘块？占用多少间接盘块？写 出计算过程。> > > > > 2> > > M> > > B> > > /> > > 512> > > B> > > => > > > > 2> > > 21> > > > > 2> > > 9> > > > > => > > > 2> > > 12> > > > => > > 4096> > > > 2MB/512B=\frac{2^{21}}{2^9}=2^{12}=4096> > > 2MB/512B=29221​=212=4096个数据盘块> > > > > > > 4096> > > >> > > 10> > > > 4096>10> > > 4096>10，占满10个直接地址> > > > > > > 4096> > > −> > > 10> > > >> > > 128> > > > 4096-10>128> > > 4096−10>128,占满了一级间接地址索引(需要一个一级间接盘块)> > > > > > > 4096> > > −> > > 10> > > −> > > 128> > > => > > 3958> > > <> > > 128> > > ∗> > > 128> > > => > > > 2> > > 14> > > > > 4096-10-128=3958<128*128=2^{14}> > > 4096−10−128=3958<128∗128=214,故二级间接地址索引可以存下剩余数据盘块> > > > > > > c> > > e> > > l> > > l> > > (> > > 3958> > > /> > > 128> > > )> > > => > > 31> > > > cell(3958/128)=31> > > cell(3958/128)=31(需要一个一级间接盘块,31个二级间接盘块)> > 故总共需要> > > > > 31> > > +> > > 1> > > +> > > 1> > > => > > 33> > > > 31+1+1=33> > > 31+1+1=33个间接盘块
4. 若系统中磁头停留在磁道号为 70 的磁道上，这时先后有 8 个进程提出了磁盘访问请求，要访问磁盘的磁道号 按申请到达的先后顺序依次为：45、68、28、90、50、30、80、48。移动臂的运动方向：沿磁道号递减方向移 动。若分别采用 FCFS 磁盘调度算法、SCAN 算法，则平均寻道长度各为多少？写出计算过程。1. FCFS磁盘调度算法：磁道号2830454850688090访问顺序36185274所以总寻道长度为 ( 70 − 45 ) + ( 68 − 45 ) + ( 68 − 28 ) + ( 90 − 28 ) + ( 90 − 50 ) + ( 50 − 30 ) + ( 80 − 30 ) + ( 80 − 48 ) = 25 + 23 + 40 + 62 + 40 + 20 + 50 + 32 = 292 (70-45)+(68-45)+(68-28)+(90-28)+(90-50)+(50-30)+(80-30)+(80-48)\=25+23+40+62+40+20+50+32=292 (70−45)+(68−45)+(68−28)+(90−28)+(90−50)+(50−30)+(80−30)+(80−48)=25+23+40+62+40+20+50+32=292故平均寻道长度为 292 / 8 = 36.5 292/8=36.5 292/8=36.52. SCAN算法磁道号2830454850688090访问顺序65432178故总寻道长度为 ( 70 − 28 ) + ( 90 − 28 ) = 104 (70-28)+(90-28)=104 (70−28)+(90−28)=104平均寻道长度为 104 / 8 = 13 104/8=13 104/8=13
5. 一个分页存储系统，页表放在内存，如果访问一次内存需要 200ns，则（1）访问要内存单元需要多少时间？> 访问内存单元时，需要先访问页表中的页表项以获得块号，再将块号与页内地址拼接，得到物理地址，再访问真正的物理地址，所以访问一个内存单元总共有两次访问内存，故> > > > > t> > > => > > 2> > > ∗> > > 200> > > n> > > s> > > => > > 400> > > n> > > s> > > > t=2200ns=400ns> > > t=2∗200ns=400ns（2） 如果系统引入联想寄存器，90%的页表项可以在快表中命中，设访问一次快表需要 10ns，则命中时访问一个内存单元需要多少时间？> 命中时访问时间只需要两个时间，一个是访问快表的时间10ns，一个是访问真实物理地址的时间为200ns，总共需要210ns（3）现有一作业有 6 页，页面大小 2KB，且第 0，1，2，5 页分别放在物理块 5，10，11， 15 中，求出逻辑地址 2F6BH 对应的物理地址> 首先将2F6BH转化为二进制为> > > > > 0010111101101011> > > B> > > > 0010111101101011B> > > 0010111101101011B> > 页面大小为2KB，所以页内地址长度为> > > > > l> > > o> > > > g> > > 2> > > > (> > > 2> > > ∗> > > 1024> > > )> > > => > > 11> > > > log_2(21024)=11> > > log2​(2∗1024)=11位，> > 因此页面号为逻辑地址去除后面11位为> > > > > 00101> > > B> > > => > > 5> > > > 00101B=5> > > 00101B=5> > 查找页表，发现页号5对应的块号为15> > 将15转化为2进制为> > > > > 01111> > > B> > > > 01111B> > > 01111B> > 将块号与页内地址拼接得到> > > > > 0111> > > ∣> > > 1111> > > ∣> > > 0110> > > ∣> > > 1011> > > B> > > > 0111|1111|0110|1011B> > > 0111∣1111∣0110∣1011B> > 转化为16进制为> > > > > 7> > > F> > > 6> > > B> > > H> > > > 7F6BH> > > 7F6BH> > 所以逻辑地址> > > > > 2> > > F> > > 6> > > B> > > H> > > > 2F6BH> > > 2F6BH对应的物理地址为7F6BH