操作系统总结

type

status

date

slug

summary

简介

操作系统（Operating System，OS）是配置在计算机硬件上的一层软件，是对硬件系统的首次扩充，其主要作用是管理好这些设备，提高它们的利用率和系统的吞吐量，并未用户和应用程序提供一个简单的接口，便于用户使用。OS是现代计算机系统中最为基本和重要的系统软件，而其他的注入编译程序，数据库管理系统等系统软件，以及大量的应用软件，都直接依赖于操作系统的支持，取得的它所提供的服务，事实上OS已经称为现代计算机系统、多处理机系统、计算机网络中都必须配置的系统软件。

本次上机实践的内容包括了：银行家算法、处理机调度算法（RR、HRRN）、存储器管理算法（FF、NF、BF、WF）、虚拟存储器管理算法（FIFO、LRU、改进型Clock）、磁盘调度算法（FCFS、SSTF、SCAN、CSCAN、NStepSCAN）、用线程实现算盘抽奖以及模拟Linux指令的文件系统。

其中，除了算盘抽奖使用了基于IOS平台的JSBox软件、采用JavaScript进行实现，其余的算法都是用Kotlin语言实现的，Kotlin是一款基于Java的现代多平台的静态编程语言，由JetBrains公司开发，与Java可以100%兼容，即可以运行在JVM上，也可以编译成JavaScript，其精简的语法可以使很多在C++和Java中很难实现的功能变得十分方便和优雅。

代码在macOS HighSierra 10.13.4上进行开发，使用IntelliJ IDEA和VS Code进行编写，整个项目已在GitHub上开源，项目地址。

银行家算法

介绍

银行家算法是Dijkstra设计的一种可以有效避免死锁的算法，它原本是为银行系统设计的，以确保银行在发放现金贷款的时，不会发生不能满足所有客户需要的请款，同样的，也可以用在操作系统上。

每个进程在进入系统时，得实现声明运行过程中所需的每种类型资源的最大数目，使其不超过系统所拥有的资源总量，进程动态地申请资源，系统在分配资源之前，先判断此次分配的安全性，如果此次分配会导致系统处于不安全状态，那么系统就不会将资源分配给它，进程只能等待。

数据结构

可利用资源向量：一个含有个元素的数组，每一个元素代表了该类资源的可利用数目，每项都会随着资源的分配和回收而动态地改变。

最大需求矩阵：一个的矩阵，定义了每一类资源分配给每个进程的最大资源数。代表了进程需要类型的资源的最大数目为。

分配矩阵：一个的矩阵，代表了当前每个资源分配给每个进程的资源数。代表了进程当前获得类资源的个数为。

需求矩阵：一个的矩阵，代表每个进程尚需需要的各类资源的数目，代表进程还需要类资源个才能完成任务。

其中三个矩阵存在如下关系：

算法流程

进程请求类资源，则。

如果，则跳转至（3），否则报错，因为当前请求资源已经超过事先申明的最大值。

如果，则跳转至（4）,否则表示当前没有足够的资源，需要等待。

假设资源已经把资源分配给了进程，那么矩阵中的元素值将发生变化：

系统执行安全算法，如果此次资源分配后系统处于安全状态，则可以分配，否则，本次分配作废，退回到原来的状态，让进程继续等待。

安全算法

设置两个向量和。

向量有个元素，表示系统可提供给进程继续运行的资源数目，在执行安全算法开始前，先让。

向量也含有个元素，算法执行前先让，当有足够的资源分配给进程时候，让对应的。

在进程集合中寻找如下条件的进程:

如果找到，则继续执行

当进程获得资源后，可顺利执行，直到完成，因此释放出分配给它的资源：

跳转到（4）

如果所有进程的都满足，则系统处于安全状态，否则，处于不安全状态。

处理机管理

介绍

进程调度是操作系统中必不可少的一种操作，调度的好坏直接决定了CPU的使用效率，这里主要实现了两种调度方式，轮转调度法（RR）和高响应比优先调度法（HRRN）。

轮转调度法（RR）

基本原理

系统根据FCFS策略，将所有就绪的进程排成一个就绪队列，系统根据一个设定好的时间片长度产生一次中断，激活系统中的调度程序，首先将CPU分配给队首进程，令其执行，如果该进程执行完或者时间片耗尽，那么激活调度程序，再次将CPU分配给队首的进程，如此循环，这样可以保证所有的进程在一个确定的时间片段内都能得到一次CPU的执行。

进程切换时机

时间片尚未用完，正在运行的进程已经执行完，则立即激活调度程序，将队首元素移出即可。一个时间片用完，直接激活调度程序，将进程从队首移出并放入队尾。

时间片大小选取

在轮转调度法中，时间片的大小对系统的性能有很大的影响，如果时间片很小，那么意味着会频繁进行进程调度，这会大大增加系统的开销，如果时间片太长，那么RR就会退化成FCFS算法，不利用短作业和交互式作业的需求。

特殊情况下的调度顺序

书上的情况是默认初始时刻进程都在就绪队列中然后CPU才开始运行的，然而在实际的操作系统中，CPU在处理进程的过程中，随时可能会有新的进程加入到就绪队列中，若在时刻，一个时间片结束且进程没有执行完毕，这时应该将从队首移出放入队尾，然而，如果这时同时有一个进程进入就绪队列，就会产生先将放入队尾还是先将放入队尾的问题，这个其实取决于具体的操作系统，不同的操作系统的实现是不一样的，在这里我选择的是先将放入队尾，再将放入队尾，这样可以保证后来的进程先执行。

高响应比优先调度法（HRRN）

介绍

FCFS算法只考虑了作业的等待时间，而忽视了运行时间，而SJF算法阈值相反，只考虑了运行时间而忽略了等待时间，因此，高响应比优先则兼顾了两者，既照顾了短作业，又能保证不让长作业的等待时间过长，在一定程度上改善了处理机调度的性能。

优先级

高响应比优先法为每个进程引入了一个动态的优先级，这个优先级会随着等待时间的增加而变化，这样使得长作业的优先级在等待过程中不断累加，等待足够的时间后，必然有机会获得处理机，优先级公式如下：

特点

如果作业的等待时间相同，则要求服务的时间越短，优先级越高，类似于SJF，有利于短作业。

如果作业的服务时间相同，则作业的优先权取决于等待时间，类似于FCFS算法。

对于长作业优先，随着等待时间的增加而增加，其优先级会相应地提高，也可以获得处理机，因此该算法实现了一个较好的折中。

存储器管理

介绍

为了将进程装入到内存中，必须为它分配一定大小的内存空间，其中，连续分配方式是最常见的一种方式。动态分区分配又叫可变分区分配，它根据实际进程的需要，动态地为它分配内存，这样可以有效避免内存的浪费。

数据结构

对于动态分区分配，存在两种数据结构来实现：空闲分区表和空闲分区链，这里我主要拿空闲分区表来实现，主要结构如下：

分区号	分区始址（KB）	分区大小（KB）	状态
1	85	50	空闲
2	155	32	空闲
3	275	70	空闲

算法流程

首先根据特定的内存分配算法从空闲分区中找到指定的分区，假设进程请求的内存大小为，空闲分区的大小为，若存在如下关系：（是事先规定的不能再切割的剩余分区的大小），说明剩余部分太小，不可再切割，则将整个空闲区都分配给进程，否则，便从空闲区中分出指定大小的内存给进程，剩余的部分仍然留在空闲区中。

当进程运行完毕释放内存时，系统根据释放内存的始址进行释放，可能会出现下面四种情况：

回收区与前一个空闲分区相邻接，将回收区和前一个分区合并，不必创建新表项。

回收区与后一个空闲分区相邻接，也将两个回收区合并，将回收区的首址作为新空闲区的首址。

回收的前后均与空闲区邻接，则将三个分区合并，使用的表项作为首址，取消的表项，大小为三者之和。

回收区既不与邻接，也不与邻接，为回收区单独建立一个新的表项，并根据首址插入到适当的位置。

动态区分配算法

首次适应算法（FF）

在分配内存时，从空闲分区表的头开始查找，直到找到第一个大小能够满足的空闲分区为止。

该算法实现简单，优先利用低地址的空闲分区，从而保留了高地址部分的大空闲分区，为后期的大作业分配大的内存空间创造了条件，缺点是低地址部分不断被划分，留下了很多难以利用的，很小的空闲分区，且每次查找都是从地址址部分开始查找，无疑会增加查找的开销。

循环首次适应算法（NF）

和首次适应算法所不同，在为进程分配内存空间时，不再是每次都从低地址开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，因此需要设置一个查询指针，用来指示下一次起始查询的空闲分区，如果最后一个空闲分区的大小仍然不能满足要求，则应该返回到第一个空闲分区。该算法使空闲分区二分内部得更均匀，适当减少了查找空闲分区时候的开销，但这样容易拆分大的空闲分区。

最佳适应算法（BF）

每次为作业分配内存的时候，总是把满足要求的，但又是最小的空闲分区分配给进程，即寻找一个空闲分区，使得的值最小，这样可以避免“大材小用”，但是容易产生细小的碎片。

最坏适应算法（WF）

和最佳适应算法相反，它总是为进程挑选满足要求的，但又是最大的空闲区分配给进程，即寻找一个空闲分区，使得的值最大，这样可以使产生碎片的可能性最小，对中小作业有利。

虚拟存储器管理

介绍

由于内存的大小是有限的，因此无法保证所有的作业都能装入内存中运行，如果扩充内存容量，那么无疑会增加成本，因此引入了虚拟存储器的概念。在虚拟存储器中，允许将一个作业分多次调入到内存中，以一种离散的方式分配内存，通常有分页和分段两种方式。

就拿分页式存储管理来说，首先将内存分成很多的物理块，然后在进程运行的过程中，如果对应的页面不在内存中，则需要把它们调入内存中，若内存中没有空闲空间，那么必须采取一定的置换算法，将某些物理块中的数据置换到磁盘中去，以腾出空间给其他页面。

数据结构

在这里，我采用的是一个反置页表，为每一个物理块设置了一个页表项，并按它们的物理块的编号进行排序，其中的内容是页号和其所对应的标识符。

置换算法

先进先出算法（FIFO）

该算法总是将最早进入内存的页面，即在内存中驻留时间最长的页面给置换出去，只需要给每个物理块设置一个时间变量，只要没有被置换出去就持续增长，然后每次替换反置页表中值最大的那一项即可，一旦某一个物理块的内容被替换，那么就将其中的页号数修改，并且令。改算法与进程实际运行的规律不适应，应为在进程中，有些页面需要经常被访问且它又是最早进入物理块的，采用FIFO算法并不能保证这些页面不被置换掉。

最少使用算法（LRU）

和FIFO类似，只不过LRU算法中，记录的不是页面在物理块中的驻留时间，而是记录一个页面自上次被访问所经历的时间，即每次访问一个页面后，都需要将该页面的置0，每次需要置换的时候，将最大的那个页面给淘汰出去，因此它能够将最近未被使用的页面给淘汰掉。

改进型的Clock置换算法

首先需要说一下Clock算法，为每个页设置一个访问位，如果某页被访问，则访问位置1，在选择页面进行淘汰时，只需检查访问位，如果是0，就将其换出，如果为1，则重新将它置0，暂不换出，如果检查到队列中的最后一个页面，访问位仍然为1，那么回到队首去检查第一个页面。

然后说一下改进型Clock算法，在将一个页面换出的时候，如果该页已经被修改过，需要将该页重新写回到磁盘上，因此对于修改过的页面，换出时所付出的开销比未修改过的页面大。因此在给页面设置访问位的同时还需要给其设定一个修改位，和的组合共有如下四种情况：

，没有被访问也没有被修改，最佳的淘汰页。

，没有被访问过，但被修改过，并不是很好的淘汰页。

，被访问过，但没有被修改过，该页面有可能再被访问。

，已经被访问且修改过，有可能再被访问。

然后描述一下具体的算法流程：

从指针当前位置开始扫描，如果遇到的页面，那么将其淘汰。

如果没有找到，那么寻找的页面，找到则将其淘汰，在这轮扫描的同时，将所有扫描过的页面的访问位都置0。

如果第二轮也没有找到，因为此时所有页面的访问位都为0，那么继续回到第一步，寻找的页面，如果没有找到，则跳到第二步寻找的页面，必然可以找到需要被淘汰的页面。

磁盘调度算法

介绍

为了减少对文件的访问时间，应该采用一种合适的磁盘调度算法，这样可以使各进程对磁盘的平均访问时间最小。由于在磁盘访问的过程中最主要的是寻道时间，因此，磁盘调度的优先目标是使平均寻道时间最少。

调度算法

先来先服务（FCFS）

根据进程请求访问磁盘的先后顺序进行调度，该算法公平、简单，每个进程都能依次得到处理，但由于为对寻道进行任何优化，因此会导致平均寻道时间过长。

最短寻道时间优先（SSTF）

该算法选择距离当前磁头所在磁道距离最近的磁道进行访问，因此每次的寻道时间最短，但并不能保证平均的寻道时间最短。可以看出，SSTF算法的平均寻道长度明显低于FCFS算法，因此性能较好。

扫描算法（SCAN）

SSTF算法是基于优先级的调度算法，因此就可能导致优先级低的进程发生“饥饿”现象，因为I/O总是访问距当前磁头最近的磁道，那么较远的一些磁道可能就会访问不到，因此需要对SSTF算法进行适当的修改，以防止出现这种“饥饿”现象。

SCAN算法不仅考虑欲访问磁道和当前磁道的距离，更优先考虑磁头的移动防线，例如，如果当前磁头正在向外移动，那么下一个应该访问的应该是离当前磁头最近的，且在其外侧的磁道，如果没有更外的磁道可以访问时，那么将移动方向改为由外向里，直到无更里的磁道需要访问，这样可以有效地避免饥饿现象。

循环扫描算法（CSCAN）

CSCAN算法规定磁头单向移动，例如只能从里向外移动，当磁头访问到最外的磁道后，立即返回到最里的磁道。即将最小的磁道号紧接着最大的磁道号构成循环。

NStepSCAN算法

N步SCAN算法将磁盘请求队列分成若干个长度为N的子序列，磁盘调度按FCFS算法依次处理这里子队列，而每个子队列的内部是根据SCAN算法进行处理的。当N很大的时候，算法接近于SCAN算法，当N=1时，退化成FCFS算法。N步SCAN算法可以有效避免“磁臂粘着”的现象。