「操作系统」操作系统笔记

第一章

简答题

三种基本的OS

分时操作系统: 同时性，独立性，及时性，交互性

实时操作系统：提供及时响应和高可靠性

批处理操作系统：批量集中处理、多道程序运行、作业脱机工作

第二章处理器调度作业

简答题

处理器两种最基本的状态

用户态：只能运行用户程序，非特权指令

核心态：运行系统指令和全部程序

什么是中断

​ 中断指在程序执行的过程遇到急需处理的事件中，暂时中止现行程序在CPU上的运行，转而执行相应的事件处理程序，待处理完成后再返回断电或调度其他程序执行的过程。

进程的状态转换

我们需要掌握的进程状态有：

1. 创建态
2. 就绪态
3. 运行态
4. 阻塞态
5. 终止态

需要掌握状态的转化关系：

例题：请填空

解：

例题：在一单处理器系统中若 有5个用户进程在非管态的某一时刻处于运行状态的用户进程最多有填空1个,最 少有[填空2]个处于就绪状 态的用户进程最多有[填空3 个处于等待状态的用户进程 最多有[填空4]个在想从科协退休之后去哪里坐

答案：1;0;4;5

三态模型是什么？三种状态在什么时候发生转换？

答：三态模型包括：运行态、就绪态与等待态

当进程被调度的时候就绪态转换为运行态

当时间片到的时候或者被处理机抢占时运行态转化为等待态

当进程用“系统调用”的方式申请资源或者请求等待某个事件发生的时候运行态转为等待态

当申请的资源被分配或者等待的事件发生时进程从等待态转换为就绪态

进程控制块（PCB）的作用

​ PCB是进程的唯一表示，它使得一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位。OS是根据PCB来对并发执行的进程进行控制和管理的。

进程调度算法的比较

先来先服务算法（FCFS）：

1. 比较有利于长作业，不利于短作业
2. 有利于CPU繁忙行的作业，不利于I/O繁忙型的作业

最短作业优先算法

1. 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间
2. 对长作业非常不利，可能出现长时间得不到执行
3. 未能根据作业的紧迫程度来划分执行的优先级
4. 难以准确估计作业的执行时间，从而影响调度性能
5. 存在饥饿现象

最高响应比优先算法（HRRF）：

HRRF既考虑作业的等待时间也考虑作业的运行时间，既能够照顾短作业又不会使长作业的等待时间过长，改善了调度性能

时间片轮转算法：

轮转策略可以防止哪些很少使用外围设备的进程过长的占用处理器，让外围设备的那些进程没有机会去启动外围设备。

计算题

进程调度算法

非交互系统的策略

1. 先到先得算法（FCFS First Come First Server）
2. 短作业优先算法（SPF Shortest Process First）
3. 高响应比优先算法（HRRN）

$响应比 = \frac{等待时间+作业处理时间}{作业处理时间}$

交互系统的策略

1. 时间片轮转算法
2. 优先级调度算法

例题：在某个计算机系统中有一台输入机和一台打印机,现有两道程序投
入运行,且程序A先开始运行,程序B后开始运行。程序A的运行轨迹为:计算50ms、打印100Ms,再计算 50Ms,打印100Ms,结束。程序B的运行轨迹为:计算50Ms、输入 80ms,再计算100Ms,结束。试说明
(1)两道程序运行时,cpu是否存 在空闲等待? 若是,求出等待的时间长短(单位ms)。
(2)程序A、B哪个有等待cpu的情况? 若有,求出等待的时间长短。

解：

17有三个作业A、B、C,它们分别单独运行时的CPU和I/O占用时间如下图所示:

现在请考虑三个作业同时开始执行。系统中的资源有一个CPU和两台输入/输出设备(I/O1和I/O2)同时运行。三个作业的优先级为A最高,B次之,C最低,旦低优先级的进程开始占用CPU,则高优先级进程也要等待 其结束方可占用CPU。请问
最早结束的作业是[填空1 最后结束的作业是[填空2]? 计算这段时间CPU的利用率。(三个作业全部结束为止,精确 到两位小数)[填空3]?

答：B;A;85.70;

例题：在单CPU和两台IO(I,I2)设备的多道程序设计环境下,同时投入三个作业运行。它们的执行轨迹如下:
Jobl: 12(30ms), CPU(10ms) 1(30ms)、CPU(1Oms);
Job2: Il(20ms)、CPU(20ms)、2(40ms);
Job3: CPU(30ms), II(20ms)
如果CPU、I1和I2都能并行工作,优先级从高到低为Job1、Job2和Job3, 优先级高的作业可以抢占优先级低的作业的CPU。试求:
(1) 每个作业从投入到完成分 别 所需的时间。Job1是多少? Job2是多少? 空21Job3是多少? 填空3](单位ms)
(2) 设备利用率。Il是多少?I2是多少? (精确到小数后一位)

解：

例题：有5个进程P1,P2,P3,P4,P5依次且同时到达就绪队列,它们的优先数和需要的处理器时间 如下表所示。(数字越大,优先 级越高)

忽略进程调度等所花费的时间,请 回答下列问题
(1)写出分别采用“先来先服务” 和“非抢占式的优先数”调度算法 时选中进程执行的次序。(按调度次序填写进程,如P1P223P4P5,中间无需间
隔)先来先服务:[填空1]; 非抢占式的优先数:「填空2]
(2)分别计算出在两种算法下各进程在就绪队列中的平均等待时间 先来先服务:「填空3]; 非抢占式的优先数:「填空4]

答：P1P2P3P4P5；P4P1P3P5P2；9.6；8.6

例题：有一个具有两道作业的批处理系统, 作业调度采用短作业优先的调度算法,进程 调度采用以优先数为基础的抢占式调度算法 如下表所示的作业序列,作业优先数即为进程优先数,优先数越小优先级越小。 1)请完成下表的1-22的填空(周转时间取整数, 带权周转时间精确到小数点后1位)。

答：从进程提交到进程完成的时间间隔为周转时间.

.

例题：假设某多道程序设计系统中有供用户使用的内存100K.打印机1台。系统采用可变分区方式管理内存对打印机采用静态分配并假设输入输出操作的时间忽略不计;采用最短剩余时间优先的进程调度算法,进程剩余执行时间相同时采用先来先服务算法;进 程调度时机选择在执行进程结束时或有新进程到达时。现有一进程序列如下假设系统优先分配内存的低地址区域,且不许移动己在主存中的进程,请:
(1)给出进程调度算法选中进程的次序[填空1]。(按调度次序填写进程号,中 间无需间隔符,如12345)
(2)全部进程执行结束所用的时间是多少?

答案：12435，47

第三章 内存

简答题

OPT算法为什么无法实现？

答： 因为我们无法预测一个程序的未来如何运行

计算题

内存地址分配算法

1. 最先适应算法

​ 通俗来讲就是：把进程尽量往低地址空闲区域放，放不下的话在更加地址慢慢升高。每一次存放，都从最低地址开始寻找满足的空闲区域，直至最高地址。即每次存放都从0开始。

2. 下次适应算法

​ 该算法是在FF算法的基础上进行改进的，大体上与FF算法相似，而不同点就是：

1. FF算法每次存储都是从0开始寻找符合要求的空闲区域；

2. NF算法每次存储都是接着上次分配区域的下一个地址；

3. 最佳适应算法

​ 该算法和FF算法相似，每当进程申请空间的时候，系统都是从头部开始查找。空闲区域是从小到大记录的，每次查找都从最小的开始，直到查找的满足要求的最小空闲区域。

4. 最坏适应算法

​ 该算法与BF算法相反，BF是用最小的空闲区域来存储东西，而WF是用最大的空闲区域来存储。

例题：给定主存空闲分区,按地址从小到大为:100KB、500KB、
200KB、30KB和600KB,编号分另为1-5。现有用户进程依次分别为
212KB、417KB、112KB和426KB:
(1)分别采用最先适应、最优适应 、最坏适应算法和下次适应算法将它们装入到主存的那个分区?

答：

页面置换算法

页面置换算法：

1. 最佳置换算法（OPT）

2. 先进先出算法（FIFO）

3. 最近最久未使用算法（LRU）

   选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。

4. 时钟置换算法（Clock）

例题：一个请求页式存储管理系统使用FIFO、OPT和LRU页面置换
算法,如果一个作业的页面走向为：

（1）2、3、2、1、5、2、4、5、3、2、5、2

当分配给该作业的物理块数分别为M=3和M=4时,试计算访问过程中发生的缺页中断次数F。

答案：9;6;7;6;5;6

例题：在一个请求分页式系统中 假如一个作业共有5个页面, 其页面调度次序为:1,4,3, 1,2,5,1,4,2,1,4,5。 若分配给改作业的主存块数为
3,分别采用 FIFO、LRU、Clock页面置换算法,试计算 访问过程中所发生的缺页中断 次数和缺页中断率。(保留小数点后1位)

答：9；75.0；8；66.7；8；75.0

例题：一个程序要将100×100数 组置初值0。现假设分配给该 程序的主存块数有三块,程序 固定占用一块,页面的大小为 每页100个字,数组中每一行 元素存放在一页中。开始时, 第一页数据已经调入主存。若
采用 FIFO算法,则下列两种对数组的初始化程序段引起缺页 中断次数各是多少?

.

答案：9999；99

根据页表结构进行计算

​ 熟悉一级二级页表的结构掌握如下计算知识点：

1. 逻辑地址与物理地址的转换

​ 物理地址 = 页面始址+页内偏移量

​ 页号 = 逻辑地址 // 页面长度

​ 页内偏移量 = 逻辑地址%页面长度

2. 根据逻辑地址结构计算页表的大小、页表最大占用
3. 数据访问时间
4. 计算访问了几次内存

例题：某计算机主存按字节编址,逻辑地址和物理地址都是32位, 页表项大小为4字节。请回答下列问题。若使用一级页表的分页存储管理方式,逻辑地址结构为：

(1)页的大小是多少KB?
(2)页表最大占用多少MB?

答案：4；4

解析：页内偏移量为12位说明页的大小为：$2^{12}$B = 4KB

一共有20位的页号，也就说最多有$2^{20}$个页表项

页表最多占用：$2^{20}$ * 4B = 4MB

例题：某系统采用二级页表的分页存 储管理方式,系统按字节编址 虚拟地址格式为: 页目录号(10位)|页表索引(10位) 页内位移(12位)

请问:

1.页框的大小为多少KB？进程的虚拟地址空间大小为多少K个页面?
2.若页目录表项和页表项均占4B,则一个进程的页目录表和页表共占多少页?
3.若某指令周期内访问的虚地址是01000000H和01112048H,则进行地址转换时共访问了多少个二级页表？

答案：4;1024;1025;1

解析：

（1）页框的大小为：$2^{12}$B = 4KB, 虚拟地址有$2^{10} * 2^{10}$ = 1024K个页面

（2）页目录表大小为$2^{10} * 4$ = 4KB ，页表大小为$2^{10} * 2^{10} * 4B$ = 1024KB 一种占1025页（一页4KB）

（3）二级页表是前10位，两个地址的前10位都是0000000100 ，一共只访问了1个二级页表

例题：假定某采用分页式存储管理的系统中,主存容量为1MB,被分成256块,块号为0,1,2,…255。某作业的地址空间占4页,其页号为0,1,2,3,被分配到主存的第2,4,1,5块中。请问:

(1)主存地址应该用多少位来表示?
(2)作业每一页的长度为多少? 逻辑地址中的页内地址(单元号)应该用多少位来表示?
(3)把作业中每一页分到的主存块中的起始地址填入下表。

.

页表地址转换

例题：在页式存储管理系統中,页面大小为2048个字节,将一个由4个页面(页号为0-3组成的程序装入内存中,该 进程的页表如下表所示：

对于下面的逻辑地址,请按西表过算出对应的(物理地)给逻辑地转换的过程：
(1)4000(十进制) (2)2019H(十六进制)

.

例题：在页式虚拟存储管理系统中，用户编程空间为32个页，页面大小为1KB，内存空间为16KB。如果应用程序有10页长，且已知页号为0-3的页已依次分得页框号为4、7、8、10的页框，尝试把逻辑地址0AC5H和1AC5H转化为对应的物理地址。

.

快表时间消耗

例题：某一级页式存储管理系统，假设其页面全部存储在内存当中。

1. 若访问内存的时间为120ns，那么访问一个数据的时间是多少？
2. 若增加一个快表，无论命中与否均需要20ns的开销，假设快表的命中率为80%，则此时访问一个数据的平均时间是多少？

.

解析：

（1）访问页表需要访问一个内存，访问页表中的地址需要再需要再访问一次内存，一共访问两次内存

（2）如果快表命中则需要20ns+120ns=140ns，如果不命中则需要240ns+20ns=260ns。则访问一个数据的平均时间需要（260+140）/ 2 = 200ns

段式存储

例题：给定段表如下图,给定地 址为段号和位移数,试求出对应的主存物理地址,(如越界则填越界中断)。

答案：649；1727；2301；越界中断；1994

解析：如果段长 > 位移数则可以用段首地址加上位移数即可

第四章 设备管理

计算题

硬盘调度算法

1. 先来先服务算法（FIFO）

2. 最短寻道优先算法（SSTF）

​ 优先处理与当前磁道最近的

3. 电梯算法

​ 从头扫描到最后一个柱面再返回

4. 扫描算法（SCAN）

​ 不管最后柱面的位置，到达末尾后再回来（不撞南墙不回头类型）

5. LOCK调度算法

6. 循环扫描调度算法

例题：假设磁盘存取臂目前出于8号柱面上,刚刚访问了6号柱面,对应以下的请求访 问序列: 9,7,15,18,20, 3,则按照SCAN算法和电梯算法,计算上述两种算法中磁头的移动距离。(设柱面号为0-99) SCAN填空1] 电梯调度算法 [填空2]

答案：187；29

例题：磁头的当前位置为100磁 道,磁头正向磁道号增加的方向移动。现有一磁盘读写 请求队列:23,376,205,132.19,61.190, 398 29,4,18,40。若采用先来先服务、最短寻道时间优 先和扫描算法,试计算出各 种算法中移臂所经过的柱面：

(1) 先来先服务算法[填空 1]

(2) 最短寻道时间优先[填空2]

(3) 扫描算法[填空3]

答案：1596; 700; 692

如磁盘的每个磁道分成9个块现有一文件共有A、B、… 共9个记录,每个记录的大小与块的大小相等,设磁 盘转速为27ms/转,每读出 块后需要2ms的处理时间。 若忽略其他辅助时间,试问 ：

1. 如果顺序存放这些记录并顺序读取, 处理该文件要多少ms？
2. 如果要顺序读取该文件, 记录如何存放处理时间最短ms？

答案：245；53

解析：对于第一道题需要注意在2ms的处理时间中磁道还是在继续行走的，并不是停下来的。对于第二题每次都寻找与当前磁头最近的即可。

第五章 文件管理

简答题

文件目录结构有几种，各有什么优点？

答：

1. 一级目录结构

缺点：文件重名和文件共享问题难以解决

2. 树状目录结构

优点：

(1) 较好地反应现实世界中具有层次关系答数据集合，确切地反应系统内部文件的分支结构

(2) 不同文件可以重名（只要不位于同一末端子目录中即可）

(3) 易于规定不同层次或子目录中文件的不同存取权限。

计算题

例题：设有一个包含1000个记录的索引文件,每个记录正好占用一个物理块, 而一个物理块 可以存放10个索引表目。建立索引时,一个物理块应有一个索引表目(即:无直接地址项)。 该文件至少应该建立(填空1) 级索引? 索引应占(填空2)个物理块? 该文件总共占用多少([填空3]) 物理块 ?

答案：3；111；1111

例题：设某文件为链接文件由5个逻辑记录组成,每个逻辑记录的大小与磁盘块大小相等,均为512字节,并依次存放在50、121、75、 80、63号磁盘块上。若要存取文件的第1569逻辑字节处 的信息, 问要访问哪一个磁盘块?[填空],该磁盘块第几个字节?[填空2]

答案：80；33

解析：1569/512得到商为:3, 余数为:33。所以,访问的是 80磁盘块的第33个字节。

例题： 【2018统考真题】某文件系统采用索引结点存放文件的属性和地址信息, 蔟大小为4KB。每个文件索引结点占64B, 有11个地址项, 其中直接地址项8个, 一级二级和三级间接地址项各1个,每个地址项长度为4B。请回答下列问题：

问题1: 该文件系统能支持的最大文件长度是多少?「填空1]KB+[填空2]MB+[填空3]GB+[填空4]TB

问题2: 文件系统用1M(1M=2^20)个簇存放文件索引结点, 用512M个簇存放文件数据。若一个图像文件的大小为5600B,则该文件系统最多能存放多少填空M个这样的图像文件？

问题3: 若文件F1的大小为6KB, 文件F2的大小为40KB,则该文系统获取F1和F2最后一个蔟的族号需要的时间是否相同？

答案：32；4；4；4；64；不同

解析：

问题一：直接地址项可以存储：4KB * 8 = 32KB

每个簇能够存储的地址项有4KB/4B = 1024个

一级地址可以存储：1024 * 4KB = 4MB

二级地址可以存储：1024 * 4MB = 4GB

三级地址可以存储：1024 * 4GB = 4TB

问题二：1M个簇可以存放：1M * 4KB / 64B = 64M个文件索引节点

一个图像5600B占两个簇，对于512M个簇来说最多可以存放512M/2 = 256M个簇，但是文件系统中只有64M个文件索引文件，所以最多只能存储64M这样的图像文件。

问题三：直接地址项能够存储32KB，由于F1的大小只有6KB所以文件可以直接从直接地址中读出，F2的大小32KB需要从一级索引去读取。故两个文件的读取时间不一样。

例题如果一个索引节点为128B, 指针长4B, 状态信息占用68B, 而每块大小为8KB问在索引节点中有多大空间给指针?使用直接、一次间接、二次间接和三次间接指针分别可表示多大的文件?
(1) 直接指针表示多少B？
(2) 一次间接指针表示多少MB？
(3) 二次间接指针表示多少GB?
(4) 三次间接指针表示多少TB?

答案：98304;16;8;16

解析：索引节点为128B，状态信息占用68B，留给指针的有128B-68B=60B的大小。一个索引块中一共有60/4 = 15 个指针。一级指针有15-3 = 12个；12 * 8KB = 96KB = 98304B

一块中可以存储8KB/4B = 2048个盘块指针，一次间接指针可以表示2048*8KB = 16MB

二次间接指针可以存储：2048 * 2048 * 8KB = 2048 * 16MB = 32GB

三次间接指针可以存储：2048 * 32GB = 64TB

例题：某文件系统中, 每块大小为2KB, 每块地址用4B表示, 地址结构采用UINX系统方案,即:10个直接地址(addr[0]~addr[9]) 一级索引(addr[10])、二级索引 (addr[11]和三级索引(addr[12]) 地址各一个。试转换下列文件的字节偏移量为物理地址 (计算它们对应于索引节点的第几号地址项, 块内偏移量是多少?)
(1) 12345位于Addr[填空1]中, 偏移量为[填空2]
(2) 450000位于Addr[填空3]中, 偏移量为[填空4]

答案：6; 57; 10; 1488

解析：10个直接地址可以存储10*2KB = 20KB = 20480B

故12345在直接地址的储存范围内：

12345 // 2048 = 6

12345 % 2048 = 57

一块可以存储2KB/4B = 512个指针, 一级地址一共可以存储512*2KB = 1MB > 450000B, 存储在Addr[10]中

450000 % 2048 = 1488

.

例题：某文件系统中, 每块大小为2KB, 每块地址用4B表示,地址结构采用下述方案10个直接地址, 两个一级索引地址和一个二级索引地址试求

(1) 该系统能管理的最大文件是多少[填空1]KB?

(2) 若有一个逻辑大小为256MB的文件,采用上述方式存储在外存,请问该文件占用多少个盘块[填空2]?

答案：526356; 131329;

解析：（1）一块中一共可以存储2KB/4B = 512个地址；

直接地址可以存储10 * 2KB = 20KB

两个一级地址可以存储2 * 512 * 2KB = 2048KB

一个二级地址可以存储512 * 1024KB = 524288KB

最大文件大小为：20 + 2048 + 524288 = 526356 KB

（2）计算这种题目的思路是：文件占用的盘块数 = 储存占用的盘块 + 索引盘块

256MB的文件需要占用256MB / 2KB = 128K个盘块（储存盘块）

一个一级地址可以索引512个盘块，两个一级地址可以索引1024个盘块

二级地址也就需要所以索引128K - 10 - 2*512 个盘块

（128K -10 - 2*512）/ 512 = 254（向上取整）

那么一共就需要2（两个一级地址索引盘块）+1（二级索引地址盘块）+254（二级地址中的一级索引盘块） = 257

一共需要：128K + 257 = 131329个盘块

需要注意的是：有的同学（比如我）可能会把最后的结果加上一个10，这是由于没有理解地址和储存之间的关系导致的。直接地址就是存储在地址当中的，不需要额外的去找盘块给它存储。所以计算索引盘块的时候不需要加上它；

例题：一个大小为64MB+40KB的 文件,按照UNIX多级索引存储,盘块大小为4KB,采用4字节编址,地扯结构中共有 10个直接地址,一次间接地址、二次间接地址和三次间接地址各一个, 请问该文件 共需占用多少个索引盘块[填空1]?如果是61MB的文件呢[填空2 ] ?

答案：17；17

解析：一个盘块可以存储4KB/4B = 1024个地址；

10个直接地址可以存储：10 * 4KB = 40KB

一次间接地址可以存储： 1024 * 4KB = 4MB

二次间接地址可以存储： 1024 * 4MB = 4GB

该文件存储一共需要（64MB + 40KB）/ 4KB = 16K + 10个盘块

一次间接地址可以索引1K个地址

二次间接地址需要(16K + 10 -1K - 10) / 1024 = 15个索引盘块

一共需要15+1+1 = 17个索引盘块

61MB也同理进行计算可以得到需要17个索引盘块

第六章 并发程序设计

简答题

计算题

进程资源分配

进程编程

生产者消费者进程

系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者 进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据) 生产者、消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。

只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。 缓冲区是临界资源,各进程必须互斥地访问。

PV操作题目分析步骤:
1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3.设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。(互斥信号量初值一般为 1,同步信号量的初始值要看对应资源的初始值是多少)

死锁