操作系统总结

2018年07月05日 407点热度 0人点赞 0条评论

简介

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

本次上机实践的内容包括了:银行家算法、处理机调度算法(RRHRRN)、存储器管理算法(FFNFBFWF)、虚拟存储器管理算法(FIFOLRU、改进型Clock)、磁盘调度算法(FCFSSSTFSCANCSCANNStepSCAN)、用线程实现算盘抽奖以及模拟Linux指令的文件系统。

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

代码在macOS HighSierra 10.13.4上进行开发,使用Intellij IDEAVscode进行编写,整个项目已在GitHub上开源,项目地址

银行家算法

介绍

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

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

数据结构

  • 可利用资源向量$Available$:一个含有$m$个元素的数组,每一个元素代表了该类资源的可利用数目,每项都会随着资源的分配和回收而动态地改变。
  • 最大需求矩阵$Max$:一个$n\times m$的矩阵,定义了每一类资源分配给每个进程的最大资源数。$Max[i][j]=k$代表了进程$i$需要$j$类型的资源的最大数目为$k$。
  • 分配矩阵$Allocation$:一个$n\times m$的矩阵,代表了当前每个资源分配给每个进程的资源数。$Allocation[i][j]=k$代表了进程$i$当前获得$j$类资源的个数为$k$。
  • 需求矩阵$Need$:一个$n\times m$的矩阵,代表每个进程尚需需要的各类资源的数目,$Need[i][j]=k$代表进程$i$还需要$j$类资源$k$个才能完成任务。
  • 其中三个矩阵存在如下关系:

$$Need[i][j]=Max[i][j]-Allocation[i][j]$$

算法流程

  1. 进程$i$请求$j$类资源$k$,则$Request_i[j]=k$。
  2. 如果$Request_i[j]\leqslant{Need[i][j]}$,则跳转至(3),否则报错,因为当前请求资源已经超过事先申明的最大值。
  3. 如果$Request_i[j]\leqslant{Available[i][j]}$,则跳转至(4),否则表示当前没有足够的资源,需要等待。
  4. 假设资源已经把资源分配给了进程,那么矩阵中的元素值将发生变化:$$Availabe[i]=Availabe[i]-Request_i[j] \\ Allocation[i][j]=Allocation[i][j]+Request_i[j] \\ Need[i][j]=Need[i][j]-Request_i[j]$$
  5. 系统执行安全算法,如果此次资源分配后系统处于安全状态,则可以分配,否则,本次分配作废,退回到原来的状态,让进程继续等待。

安全算法

  1. 设置两个向量$Work$和$Finish$。
  2. $Work$向量有$m$个元素,表示系统可提供给进程继续运行的资源数目,在执行安全算法开始前,先让$Work=Available$。
  3. $Finish$向量也含有$m$个元素,算法执行前先让$Finish[i]=false$,当有足够的资源分配给进程时候,让对应的$Finish[i]=true$。
  4. 在进程集合中寻找如下条件的进程:
    1. $Finish[i]=false$
    2. $Need[i][j]\leqslant{Work[j]}$
    3. 如果找到,则继续执行
  5. 当进程获得资源后,可顺利执行,直到完成,因此释放出分配给它的资源:
    1. $Work[j]=Work[j]+Allocation[i][j]$
    2. $Finish[i]=true$
    3. 跳转到(4)
  6. 如果所有进程的$Finish[i]=true$都满足,则系统处于安全状态,否则,处于不安全状态。

处理机管理

介绍

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

轮转调度法(RR)

基本原理

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

进程切换时机

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

时间片大小选取

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

特殊情况下的调度顺序

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

高响应比优先调度法(HRRN

介绍

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

优先级

高响应比优先法为每个进程引入了一个动态的优先级,这个优先级会随着等待时间的增加而变化,这样使得长作业的优先级在等待过程中不断累加,等待足够的时间后,必然有机会获得处理机,优先级公式如下:$$priority=\frac{waitTime+serviceTime}{serviceTime}=\frac{responseTime}{serviceTime}$$

特点

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

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

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

存储器管理

介绍

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

数据结构

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

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

算法流程

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

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

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

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

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

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

动态区分配算法

首次适应算法(FF

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

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

循环首次适应算法(NF

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

最佳适应算法(BF

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

最坏适应算法(WF

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

虚拟存储器管理

介绍

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

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

数据结构

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

置换算法

先进先出算法(FIFO)

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

最少使用算法(LRU)

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

改进型的Clock置换算法

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

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

  1. $A=0,M=0$,没有被访问也没有被修改,最佳的淘汰页。
  2. $A=0,M=1$,没有被访问过,但被修改过,并不是很好的淘汰页。
  3. $A=1,M=0$,被访问过,但没有被修改过,该页面有可能再被访问。
  4. $A=1,M=1$,已经被访问且修改过,有可能再被访问。

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

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

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

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

磁盘调度算法

介绍

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

调度算法

先来先服务(FCFS

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

最短寻道时间优先(SSTF

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

扫描算法(SCAN

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

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

循环扫描算法(CSCAN

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

NStepSCAN算法

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

Plus

文章评论