重磅干货,第一时间送达 这不是一篇教你如何创建一个操作系统的文章,相反,这是一篇指导性文章,教你从几个方面来理解操作系统。首先你需要知道你为什么要看这篇文章以及为什么要学习操作系统。 高清大图见文末 搞清楚几个问题首先你要搞明白你学习操作系统的目的是什么?操作系统的重要性如何?学习操作系统会给我带来什么?下面我会从这几个方面为你回答下。 操作系统也是一种软件,但是操作系统是一种非常复杂的软件。操作系统提供了几种抽象模型
这些抽象和我们的日常开发息息相关。搞清楚了操作系统是如何抽象的,才能培养我们的抽象性思维和开发思路。 很多问题都和操作系统相关,操作系统是解决这些问题的基础。如果你不学习操作系统,可能会想着从框架层面来解决,那是你了解的还不够深入,当你学习了操作系统后,能够培养你的全局性思维。 学习操作系统我们能够有效的解决 学习操作系统的重点不是让你从头制造一个操作系统,而是告诉你「操作系统是如何工作的」,能够让你对计算机底层有所了解,打实你的基础。 相信你一定清楚什么是编程 「Data structures + Algorithms = Programming」 操作系统内部会涉及到众多的数据结构和算法描述,能够让你了解算法的基础上,让你编写更优秀的程序。 我认为可以把计算机比作一栋楼 计算机的底层相当于就是楼的根基,计算机应用相当于就是楼的外形,而操作系统就相当于是告诉你大楼的构造原理,编写高质量的软件就相当于是告诉你构建一个稳定的房子。 认识操作系统在了解操作系统前,你需要先知道一下什么是计算机系统:现代计算机系统由「一个或多个处理器、主存、打印机、键盘、鼠标、显示器、网络接口以及各种输入/输出设备构成的系统」。这些都属于 所以计算机科学家在硬件的基础之上,安装了一层软件,这层软件能够根据用户输入的指令达到控制硬件的效果,从而满足用户的需求,这样的软件称为 上面一个操作系统的简化图,最底层是硬件,硬件包括「芯片、电路板、磁盘、键盘、显示器」等我们上面提到的设备,在硬件之上是软件。大部分计算机有两种运行模式: 在大概了解到操作系统之后,我们先来认识一下硬件都有哪些 计算机硬件计算机硬件是计算机的重要组成部分,其中包含了 5 个重要的组成部分:「运算器、控制器、存储器、输入设备、输出设备」。
❝
这五部分也是冯诺伊曼的体系结构,它认为计算机必须具有如下功能: 把需要的程序和数据送至计算机中。必须具有长期记忆程序、数据、中间结果及最终运算结果的能力。能够完成各种算术、逻辑运算和数据传送等数据加工处理的能力。能够根据需要控制程序走向,并能根据指令控制机器的各部件协调操作。能够按照要求将处理结果输出给用户。 下面是一张 intel 家族产品图,是一个详细的计算机硬件分类,我们在根据图中涉及到硬件进行介绍
下面是 CPU 可能执行简单操作的几个步骤
❝
进程和线程关于进程和线程,你需要理解下面这张脑图中的重点 进程操作系统中最核心的概念就是 在多道程序处理的系统中,CPU 会在 进程模型一个进程就是一个正在执行的程序的实例,进程也包括程序计数器、寄存器和变量的当前值。从概念上来说,每个进程都有各自的虚拟 CPU,但是实际情况是 CPU 会在各个进程之间进行来回切换。 如上图所示,这是一个具有 4 个程序的多道处理程序,在进程不断切换的过程中,程序计数器也在不同的变化。 在上图中,这 4 道程序被抽象为 4 个拥有各自控制流程(即每个自己的程序计数器)的进程,并且每个程序都独立的运行。当然,实际上只有一个物理程序计数器,每个程序要运行时,其逻辑程序计数器会装载到物理程序计数器中。当程序运行结束后,其物理程序计数器就会是真正的程序计数器,然后再把它放回进程的逻辑计数器中。 从下图我们可以看到,在观察足够长的一段时间后,所有的进程都运行了,「但在任何一个给定的瞬间仅有一个进程真正运行」。 因此,当我们说一个 CPU 只能真正一次运行一个进程的时候,即使有 2 个核(或 CPU),「每一个核也只能一次运行一个线程」。 由于 CPU 会在各个进程之间来回快速切换,所以每个进程在 CPU 中的运行时间是无法确定的。并且当同一个进程再次在 CPU 中运行时,其在 CPU 内部的运行时间往往也是不固定的。 这里的关键思想是 进程的创建操作系统需要一些方式来创建进程。下面是一些创建进程的方式
从技术上讲,在所有这些情况下,让现有流程执行流程是通过创建系统调用来创建新流程的。该进程可能是正在运行的用户进程,是从键盘或鼠标调用的系统进程或批处理程序。这些就是系统调用创建新进程的过程。该系统调用告诉操作系统创建一个新进程,并直接或间接指示在其中运行哪个程序。 在 UNIX 中,仅有一个系统调用来创建一个新的进程,这个系统调用就是 在 Windows 中,情况正相反,一个简单的 Win32 功能调用 进程的终止进程在创建之后,它就开始运行并做完成任务。然而,没有什么事儿是永不停歇的,包括进程也一样。进程早晚会发生终止,但是通常是由于以下情况触发的
进程的层次结构在一些系统中,当一个进程创建了其他进程后,父进程和子进程就会以某种方式进行关联。子进程它自己就会创建更多进程,从而形成一个进程层次结构。 UNIX 进程体系在 UNIX 中,进程和它的所有子进程以及子进程的子进程共同组成一个进程组。当用户从键盘中发出一个信号后,该信号被发送给当前与键盘相关的进程组中的所有成员(它们通常是在当前窗口创建的所有活动进程)。每个进程可以分别捕获该信号、忽略该信号或采取默认的动作,即被信号 kill 掉。整个操作系统中所有的进程都隶属于一个单个以 init 为根的进程树。 Windows 进程体系相反,Windows 中没有进程层次的概念,Windows 中所有进程都是平等的,唯一类似于层次结构的是在创建进程的时候,父进程得到一个特别的令牌(称为句柄),该句柄可以用来控制子进程。然而,这个令牌可能也会移交给别的操作系统,这样就不存在层次结构了。而在 UNIX 中,进程不能剥夺其子进程的 进程状态尽管每个进程是一个独立的实体,有其自己的程序计数器和内部状态,但是,进程之间仍然需要相互帮助。当一个进程开始运行时,它可能会经历下面这几种状态 图中会涉及三种状态
进程的实现操作系统为了执行进程间的切换,会维护着一张表,这张表就是 下面展示了一个典型系统中的关键字段 典型的进程表表项中的一些字段 第一列内容与 现在我们应该对进程表有个大致的了解了,就可以在对单个 CPU 上如何运行多个顺序进程的错觉做更多的解释。与每一 I/O 类相关联的是一个称作 当中断结束后,操作系统会调用一个 C 程序来处理中断剩下的工作。在完成剩下的工作后,会使某些进程就绪,接着调用调度程序,决定随后运行哪个进程。然后将控制权转移给一段汇编语言代码,为当前的进程装入寄存器值以及内存映射并启动该进程运行,下面显示了中断处理和调度的过程。
一个进程在执行过程中可能被中断数千次,但关键每次中断后,被中断的进程都返回到与中断发生前完全相同的状态。 线程在传统的操作系统中,每个进程都有一个地址空间和一个控制线程。事实上,这是大部分进程的定义。不过,在许多情况下,经常存在同一地址空间中运行多个控制线程的情形,这些线程就像是分离的进程。下面我们就着重探讨一下什么是线程 线程的使用或许这个疑问也是你的疑问,为什么要在进程的基础上再创建一个线程的概念,准确的说,这其实是进程模型和线程模型的讨论,回答这个问题,可能需要分三步来回答
经典的线程模型进程中拥有一个执行的线程,通常简写为 下图我们可以看到三个传统的进程,每个进程有自己的地址空间和单个控制线程。每个线程都在不同的地址空间中运行 下图中,我们可以看到有一个进程三个线程的情况。每个线程都在相同的地址空间中运行。 线程不像是进程那样具备较强的独立性。同一个进程中的所有线程都会有完全一样的地址空间,这意味着它们也共享同样的全局变量。由于每个线程都可以访问进程地址空间内每个内存地址,「因此一个线程可以读取、写入甚至擦除另一个线程的堆栈」。线程之间除了共享同一内存空间外,还具有如下不同的内容 上图左边的是同一个进程中 「线程之间的状态转换和进程之间的状态转换是一样的」。 每个线程都会有自己的堆栈,如下图所示 线程系统调用进程通常会从当前的某个单线程开始,然后这个线程通过调用一个库函数(比如 当一个线程完成工作后,可以通过调用一个函数(比如 另一个常见的线程是调用 POSIX 线程
它允许程序控制时间上重叠的多个不同的工作流程。每个工作流程都称为一个线程,可以通过调用 POSIX Threads API 来实现对这些流程的创建和控制。可以把它理解为线程的标准。 ❝
所有的 Pthreads 都有特定的属性,每一个都含有标识符、一组寄存器(包括程序计数器)和一组存储在结构中的属性。这个属性包括堆栈大小、调度参数以及其他线程需要的项目。 线程实现主要有三种实现方式
下面我们分开讨论一下 在用户空间中实现线程第一种方法是把整个线程包放在用户空间中,内核对线程一无所知,它不知道线程的存在。所有的这类实现都有同样的通用结构 在用户空间中实现多线程 线程在运行时系统之上运行,运行时系统是管理线程过程的集合,包括前面提到的四个过程:pthread_create, pthread_exit, pthread_join 和 pthread_yield。 在内核中实现线程当某个线程希望创建一个新线程或撤销一个已有线程时,它会进行一个系统调用,这个系统调用通过对线程表的更新来完成线程创建或销毁工作。 在内核中实现多线程 内核中的线程表持有每个线程的寄存器、状态和其他信息。这些信息和用户空间中的线程信息相同,但是位置却被放在了内核中而不是用户空间中。另外,内核还维护了一张进程表用来跟踪系统状态。 所有能够阻塞的调用都会通过系统调用的方式来实现,当一个线程阻塞时,内核可以进行选择,是运行在同一个进程中的另一个线程(如果有就绪线程的话)还是运行一个另一个进程中的线程。但是在用户实现中,运行时系统始终运行自己的线程,直到内核剥夺它的 CPU 时间片(或者没有可运行的线程存在了)为止。 混合实现结合用户空间和内核空间的优点,设计人员采用了一种 用户线程与内核线程的多路复用 在这种模型中,编程人员可以自由控制用户线程和内核线程的数量,具有很大的灵活度。采用这种方法,内核只识别内核级线程,并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。 进程间通信进程是需要频繁的和其他进程进行交流的。下面我们会一起讨论有关 下面我们分别对其进行概述 信号 signal信号是 UNIX 系统最先开始使用的进程间通信机制,因为 Linux 是继承于 UNIX 的,所以 Linux 也支持信号机制,通过向一个或多个进程发送 你可以在 Linux 系统上输入 进程可以选择忽略发送过来的信号,但是有两个是不能忽略的: 操作系统会中断目标程序的进程来向其发送信号、在任何非原子指令中,执行都可以中断,如果进程已经注册了新号处理程序,那么就执行进程,如果没有注册,将采用默认处理的方式。 管道 pipeLinux 系统中的进程可以通过建立管道 pipe 进行通信 在两个进程之间,可以建立一个通道,一个进程向这个通道里写入字节流,另一个进程从这个管道中读取字节流。管道是同步的,当进程尝试从空管道读取数据时,该进程会被阻塞,直到有可用数据为止。shell 中的 sort <f | head 它会创建两个进程,一个是 sort,一个是 head,sort,会在这两个应用程序之间建立一个管道使得 sort 进程的标准输出作为 head 程序的标准输入。sort 进程产生的输出就不用写到文件中了,如果管道满了系统会停止 sort 以等待 head 读出数据 管道实际上就是 共享内存 shared memory两个进程之间还可以通过共享内存进行进程间通信,其中两个或者多个进程可以访问公共内存空间。两个进程的共享工作是通过共享内存完成的,一个进程所作的修改可以对另一个进程可见(很像线程间的通信)。 在使用共享内存前,需要经过一系列的调用流程,流程如下
先入先出队列 FIFO先入先出队列 FIFO 通常被称为 写入的第一个字节是读取的第一个字节,写入的第二个字节是读取的第二个字节,依此类推。 消息队列 Message Queue一听到消息队列这个名词你可能不知道是什么意思,消息队列是用来描述内核寻址空间内的内部链接列表。可以按几种不同的方式将消息按顺序发送到队列并从队列中检索消息。每个消息队列由 IPC 标识符唯一标识。消息队列有两种模式,一种是 套接字 Socket还有一种管理两个进程间通信的是使用 套接字有以下几种分类
调度当一个计算机是多道程序设计系统时,会频繁的有很多进程或者线程来同时竞争 CPU 时间片。当两个或两个以上的进程/线程处于就绪状态时,就会发生这种情况。如果只有一个 CPU 可用,那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做 调度算法的分类毫无疑问,不同的环境下需要不同的调度算法。之所以出现这种情况,是因为不同的应用程序和不同的操作系统有不同的目标。也就是说,在不同的系统中,调度程序的优化也是不同的。这里有必要划分出三种环境
批处理中的调度现在让我们把目光从一般性的调度转换为特定的调度算法。下面我们会探讨在批处理中的调度。 先来先服务最简单的非抢占式调度算法的设计就是 这个算法的强大之处在于易于理解和编程,在这个算法中,一个单链表记录了所有就绪进程。要选取一个进程运行,只要从该队列的头部移走一个进程即可;要添加一个新的作业或者阻塞一个进程,只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。 最短作业优先批处理中,第二种调度算法是 ❝ 最短剩余时间优先最短作业优先的抢占式版本被称作为 交互式系统中的调度交互式系统中在个人计算机、服务器和其他系统中都是很常用的,所以有必要来探讨一下交互式调度 轮询调度一种最古老、最简单、最公平并且最广泛使用的算法就是 优先级调度轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。例如,在一所大学中的等级制度,首先是院长,然后是教授、秘书、后勤人员,最后是学生。这种将外部情况考虑在内就实现了 它的基本思想很明确,每个进程都被赋予一个优先级,优先级高的进程优先运行。 多级队列最早使用优先级调度的系统是 最短进程优先最短进程优先是根据进程过去的行为进行推测,并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 可以看到,在三轮过后,T0 在新的估计值中所占比重下降至 1/8。 保证调度一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是:若用户工作时有 n 个用户登录,则每个用户将获得 CPU 处理能力的 1/n。类似地,在一个有 n 个进程运行的单用户系统中,若所有的进程都等价,则每个进程将获得 1/n 的 CPU 时间。 彩票调度对用户进行承诺并在随后兑现承诺是一件好事,不过很难实现。但是存在着一种简单的方式,有一种既可以给出预测结果而又有一种比较简单的实现方式的算法,就是 其基本思想是为进程提供各种系统资源(例如 CPU 时间)的彩票。当做出一个调度决策的时候,就随机抽出一张彩票,拥有彩票的进程将获得该资源。在应用到 CPU 调度时,系统可以每秒持有 50 次抽奖,每个中奖者将获得比如 20 毫秒的 CPU 时间作为奖励。 公平分享调度到目前为止,我们假设被调度的都是各个进程自身,而不用考虑该进程的拥有者是谁。结果是,如果用户 1 启动了 9 个进程,而用户 2 启动了一个进程,使用轮转或相同优先级调度算法,那么用户 1 将得到 90 % 的 CPU 时间,而用户 2 将之得到 10 % 的 CPU 时间。 为了阻止这种情况的出现,一些系统在调度前会把进程的拥有者考虑在内。在这种模型下,每个用户都会分配一些CPU 时间,而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证,那么无论一个用户有多少个进程,都将获得相同的 CPU 份额。 实时系统中的调度
实时系统中的事件可以按照响应方式进一步分类为 只有满足这个条件的实时系统称为 下面我们来了解一下内存管理,你需要知道的知识点如下 地址空间如果要使多个应用程序同时运行在内存中,必须要解决两个问题: 还有一种更好的方式是创造一个存储器抽象: 基址寄存器和变址寄存器最简单的办法是使用
每当进程引用内存以获取指令或读取、写入数据时,CPU 都会自动将 交换技术在程序运行过程中,经常会出现内存不足的问题。 针对上面内存不足的问题,提出了两种处理方式:最简单的一种方式就是 交换过程下面是一个交换过程 刚开始的时候,只有进程 A 在内存中,然后从创建进程 B 和进程 C 或者从磁盘中把它们换入内存,然后在图 d 中,A 被换出内存到磁盘中,最后 A 重新进来。因为图 g 中的进程 A 现在到了不同的位置,所以在装载过程中需要被重新定位,或者在交换程序时通过软件来执行;或者在程序执行期间通过硬件来重定位。基址寄存器和变址寄存器就适用于这种情况。 交换在内存创建了多个 空闲内存管理在进行内存动态分配时,操作系统必须对其进行管理。大致上说,有两种监控内存使用的方式
使用位图的存储管理使用位图方法时,内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位,0 表示空闲, 1 表示占用(或者相反)。一块内存区域和其对应的位图如下
使用链表进行管理另一种记录内存使用情况的方法是,维护一个记录已分配内存段和空闲内存段的链表,段会包含进程或者是两个进程的空闲区域。可用上面的图 c 「来表示内存的使用情况」。链表中的每一项都可以代表一个 当按照地址顺序在链表中存放进程和空闲区时,有几种算法可以为创建的进程(或者从磁盘中换入的进程)分配内存。我们先假设内存管理器知道应该分配多少内存,最简单的算法是使用 首次适配的一个小的变体是 另外一个著名的并且广泛使用的算法是 虚拟内存尽管基址寄存器和变址寄存器用来创建地址空间的抽象,但是这有一个其他的问题需要解决: 分页大部分使用虚拟内存的系统中都会使用一种
这条指令时,它会把内存地址为 1000 的内存单元的内容复制到 REG 中(或者相反,这取决于计算机)。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。 这些程序生成的地址被称为 下面这幅图展示了这种映射是如何工作的 页表给出虚拟地址与物理内存地址之间的映射关系。每一页起始于 4096 的倍数位置,结束于 4095 的位置,所以 4K 到 8K 实际为 4096 - 8191 ,8K - 12K 就是 8192 - 12287 在这个例子中,我们可能有一个 16 位地址的计算机,地址从 0 - 64 K - 1,这些是 页表虚拟页号可作为页表的索引用来找到虚拟页中的内容。由页表项可以找到页框号(如果有的话)。然后把页框号拼接到偏移量的高位端,以替换掉虚拟页号,形成物理地址。 因此,页表的目的是把虚拟页映射到页框中。从数学上说,页表是一个函数,它的参数是虚拟页号,结果是物理页框号。 通过这个函数可以把虚拟地址中的虚拟页转换为页框,从而形成物理地址。 页表项的结构下面我们探讨一下页表项的具体结构,上面你知道了页表项的大致构成,是由页框号和在/不在位构成的,现在我们来具体探讨一下页表项的构成 页表项的结构是与机器相关的,但是不同机器上的页表项大致相同。上面是一个页表项的构成,不同计算机的页表项可能不同,但是一般来说都是 32 位的。页表项中最重要的字段就是
最后一位用于禁止该页面被高速缓存,这个功能对于映射到设备寄存器还是内存中起到了关键作用。通过这一位可以禁用高速缓存。具有独立的 I/O 空间而不是用内存映射 I/O 的机器来说,并不需要这一位。 页面置换算法下面我们就来探讨一下有哪些页面置换算法。 最优页面置换算法最优的页面置换算法的工作流程如下:在缺页中断发生时,这些页面之一将在下一条指令(包含该指令的页面)上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。 最优化的页面算法表明应该标记最大的页面。如果一个页面在 800 万条指令内不会被使用,另外一个页面在 600 万条指令内不会被使用,则置换前一个页面,从而把需要调入这个页面而发生的缺页中断推迟。计算机也像人类一样,会把不愿意做的事情尽可能的往后拖。 这个算法最大的问题时无法实现。当缺页中断发生时,操作系统无法知道各个页面的下一次将在什么时候被访问。这种算法在实际过程中根本不会使用。 最近未使用页面置换算法为了能够让操作系统收集页面使用信息,大部分使用虚拟地址的计算机都有两个状态位,R 和 M,来和每个页面进行关联。「每当引用页面(读入或写入)时都设置 R,写入(即修改)页面时设置 M」,这些位包含在每个页表项中,就像下面所示 因为每次访问时都会更新这些位,因此由 如果硬件没有这些位,那么可以使用操作系统的 可以用 R 位和 M 位来构造一个简单的页面置换算法:当启动一个进程时,操作系统将其所有页面的两个位都设置为 0。R 位定期的被清零(在每个时钟中断)。用来将最近未引用的页面和已引用的页面分开。 当出现缺页中断后,操作系统会检查所有的页面,并根据它们的 R 位和 M 位将当前值分为四类:
尽管看起来好像无法实现第一类页面,但是当第三类页面的 R 位被时钟中断清除时,它们就会发生。时钟中断不会清除 M 位,因为需要这个信息才能知道是否写回磁盘中。清除 R 但不清除 M 会导致出现一类页面。
先进先出页面置换算法另一种开销较小的方式是使用 第二次机会页面置换算法我们上面学到的 FIFO 链表页面有个 这种算法叫做 a)按照先进先出的方法排列的页面;b)在时刻 20 处发生缺页异常中断并且 A 的 R 位已经设置时的页面链表。 假设缺页异常发生在时刻 20 处,这时最老的页面是 A ,它是在 0 时刻到达的。如果 A 的 R 位是 0,那么它将被淘汰出内存,或者把它写回磁盘(如果它已经被修改过),或者只是简单的放弃(如果它是未被修改过)。另一方面,如果它的 R 位已经设置了,则将 A 放到链表的尾部并且重新设置 寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过,该算法就会被简化为单纯的 时钟页面置换算法一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中,一个表针指向最老的页面。如下图所示 当缺页错误出现时,算法首先检查表针指向的页面,如果它的 R 位是 0 就淘汰该页面,并把新的页面插入到这个位置,然后把表针向前移动一位;如果 R 位是 1 就清除 R 位并把表针前移一个位置。重复这个过程直到找到了一个 R 位为 0 的页面位置。了解这个算法的工作方式,就明白为什么它被称为 最近最少使用页面置换算法在前面几条指令中频繁使用的页面和可能在后面的几条指令中被使用。反过来说,已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这个思想揭示了一个可以实现的算法:在缺页中断时,置换未使用时间最长的页面。这个策略称为 虽然 LRU 在理论上是可以实现的,但是从长远看来代价比较高。为了完全实现 LRU,会在内存中维护一个所有页面的链表,最频繁使用的页位于表头,最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表。在链表中找到一个页面,删除它,然后把它移动到表头是一个非常耗时的操作,即使使用 用软件模拟 LRU尽管上面的 LRU 算法在原则上是可以实现的,「但是很少有机器能够拥有那些特殊的硬件」。上面是硬件的实现方式,那么现在考虑要用 只需要对 NFU 做一个简单的修改就可以让它模拟 LRU,这个修改有两个步骤
修改以后的算法称为 我们假设在第一个时钟周期内页面 0 - 5 的 R 位依次是 1,0,1,0,1,1,(也就是页面 0 是 1,页面 1 是 0,页面 2 是 1 这样类推)。也就是说,「在 0 个时钟周期到 1 个时钟周期之间,0,2,4,5 都被引用了」,从而把它们的 R 位设置为 1,剩下的设置为 0 。在相关的六个计数器被右移之后 R 位被添加到 ❝ 当缺页异常出现时,将 这个算法与 LRU 算法有两个重要的区别:看一下上图中的 工作集时钟页面置换算法当缺页异常发生后,需要扫描整个页表才能确定被淘汰的页面,因此基本工作集算法还是比较浪费时间的。一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息,这种算法称为 与时钟算法一样,所需的数据结构是一个以页框为元素的循环列表,就像下面这样 工作集时钟页面置换算法的操作:a) 和 b) 给出 R = 1 时所发生的情形;c) 和 d) 给出 R = 0 的例子 最初的时候,该表是空的。当装入第一个页面后,把它加载到该表中。随着更多的页面的加入,它们形成一个环形结构。每个表项包含来自基本工作集算法的上次使用时间,以及 R 位(已标明)和 M 位(未标明)。 与时钟算法一样,在每个缺页异常时,首先检查指针指向的页面。如果 R 位被是设置为 1,该页面在当前时钟周期内就被使用过,那么该页面就不适合被淘汰。然后把该页面的 R 位置为 0,指针指向下一个页面,并重复该算法。该事件序列化后的状态参见图 b。 现在考虑指针指向的页面 R = 0 时会发生什么,参见图 c,如果页面的使用期限大于 t 并且页面为被访问过,那么这个页面就不会在工作集中,并且在磁盘上会有一个此页面的副本。申请重新调入一个新的页面,并把新的页面放在其中,如图 d 所示。另一方面,如果页面被修改过,就不能重新申请页面,因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换,指针继续向前走,算法继续对下一个页面进行操作。毕竟,有可能存在一个老的,没有被修改过的页面可以立即使用。 原则上来说,所有的页面都有可能因为 那么就有个问题,指针会绕一圈回到原点的,如果回到原点,它的起始点会发生什么?这里有两种情况:
在第一种情况中,指针仅仅是不停的移动,寻找一个未被修改过的页面。由于已经调度了一个或者多个写操作,最终会有某个写操作完成,它的页面会被标记为未修改。置换遇到的第一个未被修改过的页面,这个页面不一定是第一个被调度写操作的页面,因为硬盘驱动程序为了优化性能可能会把写操作重排序。 对于第二种情况,所有的页面都在工作集中,否则将至少调度了一个写操作。由于缺乏额外的信息,最简单的方法就是置换一个未被修改的页面来使用,扫描中需要记录未被修改的页面的位置,如果不存在未被修改的页面,就选定当前页面并把它写回磁盘。 页面置换算法小结我们到现在已经研究了各种页面置换算法,现在我们来一个简单的总结,算法的总结归纳如下
总之,「最好的算法是老化算法和WSClock算法」。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法,但实际上这两个可能是最重要的。 下面来聊一聊文件系统,你需要知道下面这些知识点 文件文件命名文件是一种抽象机制,它提供了一种方式用来存储信息以及在后面进行读取。可能任何一种机制最重要的特性就是管理对象的命名方式。在创建一个文件后,它会给文件一个命名。当进程终止时,文件会继续存在,并且其他进程可以使用 文件命名规则对于不同的操作系统来说是不一样的,但是所有现代操作系统都允许使用 1 - 8 个字母的字符串作为合法文件名。 某些文件区分大小写字母,而大多数则不区分。 许多操作系统支持两部分的文件名,它们之间用
在 UNIX 系统中,文件扩展名只是一种约定,操作系统并不强制采用。 文件结构文件的构造有多种方式。下图列出了常用的三种构造方式 三种不同的文件。a) 字节序列 。b) 记录序列。c) 树 上图中的 a 是一种无结构的字节序列,操作系统不关心序列的内容是什么,操作系统能看到的就是 图 b 表示在文件结构上的第一部改进。在这个模型中,文件是具有固定长度记录的序列,每个记录都有其内部结构。把文件作为记录序列的核心思想是:「读操作返回一个记录,而写操作重写或者追加一个记录」。第三种文件结构如上图 c 所示。在这种组织结构中,文件由一颗 文件类型很多操作系统支持多种文件类型。例如,UNIX(同样包括 OS X)和 Windows 都具有常规的文件和目录。除此之外,UNIX 还具有 文件访问早期的操作系统只有一种访问方式: 在使用磁盘来存储文件时,可以不按照顺序读取文件中的字节或者记录,或者按照关键字而不是位置来访问记录。这种能够以任意次序进行读取的称为 随机访问文件对许多应用程序来说都必不可少,例如,数据库系统。如果乘客打电话预定某航班机票,订票程序必须能够直接访问航班记录,而不必先读取其他航班的成千上万条记录。 有两种方法可以指示从何处开始读取文件。第一种方法是直接使用 文件属性文件包括文件名和数据。除此之外,所有的操作系统还会保存其他与文件相关的信息,如文件创建的日期和时间、文件大小。我们可以称这些为文件的 文件操作使用文件的目的是用来存储信息并方便以后的检索。对于存储和检索,不同的系统提供了不同的操作。以下是与文件有关的最常用的一些系统调用:
目录文件系统通常提供 一级目录系统目录系统最简单的形式是有一个能够包含所有文件的目录。这种目录被称为 该目录中有四个文件。这种设计的优点在于简单,并且能够快速定位文件,毕竟只有一个地方可以检索。这种目录组织形式现在一般用于简单的嵌入式设备(如数码相机和某些便携式音乐播放器)上使用。 层次目录系统对于简单的应用而言,一般都用单层目录方式,但是这种组织形式并不适合于现代计算机,因为现代计算机含有成千上万个文件和文件夹。如果都放在根目录下,查找起来会非常困难。为了解决这一问题,出现了 根目录含有目录 A、B 和 C ,分别属于不同的用户,其中两个用户个字创建了 路径名当目录树组织文件系统时,需要有某种方法指明文件名。常用的方法有两种,第一种方式是每个文件都会用一个 另外一种指定文件名的方法是 目录操作不同文件中管理目录的系统调用的差别比管理文件的系统调用差别大。为了了解这些系统调用有哪些以及它们怎样工作,下面给出一个例子(取自 UNIX)。
文件系统的实现文件系统布局文件系统存储在 当计算机开始引 boot 时,BIOS 读入并执行 MBR。 引导块MBR 做的第一件事就是 除了从引导块开始之外,磁盘分区的布局是随着文件系统的不同而变化的。通常文件系统会包含一些属性,如下 超级块紧跟在引导块后面的是
在计算机启动或者文件系统首次使用时,超级块会被读入内存。 空闲空间块接着是文件系统中 「BitMap 位图或者 Bit vector 位向量」 位图或位向量是一系列位或位的集合,其中每个位对应一个磁盘块,该位可以采用两个值:0和1,0表示已分配该块,而1表示一个空闲块。下图中的磁盘上给定的磁盘块实例(分配了绿色块)可以用16位的位图表示为:0000111000000110。 「使用链表进行管理」 在这种方法中,空闲磁盘块链接在一起,即一个空闲块包含指向下一个空闲块的指针。第一个磁盘块的块号存储在磁盘上的单独位置,也缓存在内存中。 碎片这里不得不提一个叫做 inode然后在后面是一个 有一种简单的方法可以找到它们 inode 节点主要包括了以下信息
文件分为两部分,索引节点和块。一旦创建后,每种类型的块数是固定的。你不能增加分区上 inode 的数量,也不能增加磁盘块的数量。 紧跟在 inode 后面的是根目录,它存放的是文件系统目录树的根部。最后,磁盘的其他部分存放了其他所有的目录和文件。 文件的实现最重要的问题是记录各个文件分别用到了哪些磁盘块。不同的系统采用了不同的方法。下面我们会探讨一下这些方式。分配背后的主要思想是
连续分配最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。因此,在具有 1KB 块的磁盘上,将为 50 KB 文件分配 50 个连续块。 上面展示了 40 个连续的内存块。从最左侧的 0 块开始。初始状态下,还没有装载文件,因此磁盘是空的。接着,从磁盘开始处(块 0 )处开始写入占用 4 块长度的内存 A 。然后是一个占用 6 块长度的内存 B,会直接在 A 的末尾开始写。 注意每个文件都会在新的文件块开始写,所以如果文件 A 只占用了 连续的磁盘空间分配有两个优点。
因此,连续的空间分配具有 不幸的是,连续空间分配也有很明显的不足。随着时间的推移,磁盘会变得很零碎。下图解释了这种现象 这里有两个文件 D 和 F 被删除了。当删除一个文件时,此文件所占用的块也随之释放,就会在磁盘空间中留下一些空闲块。磁盘并不会在这个位置挤压掉空闲块,因为这会复制空闲块之后的所有文件,可能会有上百万的块,这个量级就太大了。 链表分配第二种存储文件的方式是为每个文件构造磁盘块链表,每个文件都是磁盘块的链接列表,就像下面所示 每个块的第一个字作为指向下一块的指针,块的其他部分存放数据。如果上面这张图你看的不是很清楚的话,可以看看整个的链表分配方案 与连续分配方案不同,这一方法可以充分利用每个磁盘块。除了最后一个磁盘块外,不会因为磁盘碎片而浪费存储空间。同样,在目录项中,只要存储了第一个文件块,那么其他文件块也能够被找到。 另一方面,在链表的分配方案中,尽管顺序读取非常方便,但是随机访问却很困难(这也是数组和链表数据结构的一大区别)。 还有一个问题是,由于指针会占用一些字节,每个磁盘块实际存储数据的字节数并不再是 2 的整数次幂。虽然这个问题并不会很严重,但是这种方式降低了程序运行效率。许多程序都是以长度为 2 的整数次幂来读写磁盘,由于每个块的前几个字节被指针所使用,所以要读出一个完成的块大小信息,就需要当前块的信息和下一块的信息拼凑而成,因此就引发了查找和拼接的开销。 使用内存表进行链表分配由于连续分配和链表分配都有其不可忽视的缺点。所以提出了使用内存中的表来解决分配问题。取出每个磁盘块的指针字,把它们放在内存的一个表中,就可以解决上述链表的两个不足之处。下面是一个例子 上图表示了链表形成的磁盘块的内容。这两个图中都有两个文件,文件 A 依次使用了磁盘块地址 「4、7、 2、 10、 12」,文件 B 使用了「6、3、11 和 14」。也就是说,文件 A 从地址 4 处开始,顺着链表走就能找到文件 A 的全部磁盘块。同样,从第 6 块开始,顺着链走到最后,也能够找到文件 B 的全部磁盘块。你会发现,这两个链表都以不属于有效磁盘编号的特殊标记(-1)结束。内存中的这种表格称为 目录的实现文件只有打开后才能够被读取。在文件打开后,操作系统会使用用户提供的路径名来定位磁盘中的目录。目录项提供了查找文件磁盘块所需要的信息。根据系统的不同,提供的信息也不同,可能提供的信息是整个文件的磁盘地址,或者是第一个块的数量(两个链表方案)或 inode的数量。不过不管用那种情况,目录系统的主要功能就是 「将文件的 ASCII 码的名称映射到定位数据所需的信息上」。 共享文件当多个用户在同一个项目中工作时,他们通常需要共享文件。如果这个共享文件同时出现在多个用户目录下,那么他们协同工作起来就很方便。下面的这张图我们在上面提到过,但是有一个更改的地方,就是 「C 的一个文件也出现在了 B 的目录下」。 如果按照如上图的这种组织方式而言,那么 B 的目录与该共享文件的联系称为 日志结构文件系统技术的改变会给当前的文件系统带来压力。这种情况下,CPU 会变得越来越快,磁盘会变得越来越大并且越来越便宜(但不会越来越快)。内存容量也是以指数级增长。但是磁盘的寻道时间(除了固态盘,因为固态盘没有寻道时间)并没有获得提高。 为此,
另一方面,当时的文件系统不论是 UNIX 还是 FFS,都有大量的随机读写(在 FFS 中创建一个新文件至少需要5次随机写),因此成为整个系统的性能瓶颈。同时因为 在这种设计中,inode 甚至具有与 UNIX 中相同的结构,但是现在它们分散在整个日志中,而不是位于磁盘上的固定位置。所以,inode 很定位。为了能够找到 inode ,维护了一个由 inode 索引的 到目前为止,所有写入最初都缓存在 真实情况下的磁盘容量是有限的,所以最终日志会占满整个磁盘空间,这种情况下就会出现没有新的磁盘块被写入到日志中。幸运的是,许多现有段可能具有不再需要的块。例如,如果一个文件被覆盖了,那么它的 inode 将被指向新的块,但是旧的磁盘块仍在先前写入的段中占据着空间。 为了处理这个问题,LFS 有一个 日志文件系统虽然日志结构系统的设计很优雅,但是由于它们和现有的文件系统不相匹配,因此还没有广泛使用。不过,从日志文件结构系统衍生出来一种新的日志系统,叫做
虚拟文件系统UNIX 操作系统使用一种 还是那句经典的话,在计算机世界中,任何解决不了的问题都可以加个 文件系统的管理和优化能够使文件系统工作是一回事,能够使文件系统高效、稳定的工作是另一回事,下面我们就来探讨一下文件系统的管理和优化。 磁盘空间管理文件通常存在磁盘中,所以如何管理磁盘空间是一个操作系统的设计者需要考虑的问题。在文件上进行存有两种策略:「分配 n 个字节的连续磁盘空间;或者把文件拆分成多个并不一定连续的块」。在存储管理系统中,主要有 正如我们所看到的,按 块大小一旦把文件分为固定大小的块来存储,就会出现问题,块的大小是多少?按照「磁盘组织方式,扇区、磁道和柱面显然都可以作为分配单位」。在分页系统中,分页大小也是主要因素。 拥有大的块尺寸意味着每个文件,甚至 1 字节文件,都要占用一个柱面空间,也就是说小文件浪费了大量的磁盘空间。另一方面,小块意味着大部分文件将会跨越多个块,因此需要多次搜索和旋转延迟才能读取它们,从而降低了性能。因此,如果分配的块 记录空闲块一旦指定了块大小,下一个问题就是怎样跟踪空闲块。有两种方法被广泛采用,如下图所示 第一种方法是采用 另一种空闲空间管理的技术是 磁盘配额为了防止一些用户占用太多的磁盘空间,多用户操作通常提供一种 在用户打开一个文件时,操作系统会找到 第二张表包含了每个用户当前打开文件的配额记录,即使是其他人打开该文件也一样。如上图所示,该表的内容是从被打开文件的所有者的磁盘配额文件中提取出来的。当所有文件关闭时,该记录被写回配额文件。 当在打开文件表中建立一新表项时,会产生一个指向所有者配额记录的指针。每次向文件中添加一个块时,文件所有者所用数据块的总数也随之增加,并会同时增加 文件系统备份做文件备份很耗费时间而且也很浪费空间,这会引起下面几个问题。首先,是要「备份整个文件还是仅备份一部分呢」?一般来说,只是备份特定目录及其下的全部文件,而不是备份整个文件系统。 其次,对上次未修改过的文件再进行备份是一种浪费,因而产生了一种 稍微好一点的方式是只备份最近一次转储以来更改过的文件。当然,这种做法极大的缩减了转储时间,但恢复起来却更复杂,因为「最近的全面转储先要全部恢复,随后按逆序进行增量转储」。为了方便恢复,人们往往使用更复杂的转储模式。 第三,既然待转储的往往是海量数据,那么在将其写入磁带之前对文件进行压缩就很有必要。但是,如果在备份过程中出现了文件损坏的情况,就会导致破坏压缩算法,从而使整个磁带无法读取。所以在备份前是否进行文件压缩需慎重考虑。 第四,对正在使用的文件系统做备份是很难的。如果在转储过程中要添加,删除和修改文件和目录,则转储结果可能不一致。因此,因为转储过程中需要花费数个小时的时间,所以有必要在晚上将系统脱机进行备份,然而这种方式的接受程度并不高。所以,人们修改了转储算法,记下文件系统的 磁盘转储到备份磁盘上有两种方案:「物理转储和逻辑转储」。 第二个需要考虑的是「坏块的转储」。制造大型磁盘而没有瑕疵是不可能的,所以也会存在一些 然而,一些块在格式化后会变坏,在这种情况下操作系统可以检测到它们。通常情况下,它可以通过创建一个由所有坏块组成的 Windows 系统有 文件系统的一致性影响可靠性的一个因素是文件系统的一致性。许多文件系统读取磁盘块、修改磁盘块、再把它们写回磁盘。如果系统在所有块写入之前崩溃,文件系统就会处于一种 为了处理文件系统一致性问题,大部分计算机都会有应用程序来检查文件系统的一致性。例如,UNIX 有 可以进行两种一致性检查:「块的一致性检查和文件的一致性检查」。为了检查块的一致性,应用程序会建立两张表,每个包含一个计数器的块,最初设置为 0 。第一个表中的计数器跟踪该块在文件中出现的次数,第二张表中的计数器记录每个块在空闲列表、空闲位图中出现的频率。 文件系统性能访问磁盘的效率要比内存满的多,是时候又祭出这张图了 从内存读一个 32 位字大概是 10ns,从硬盘上读的速率大概是 100MB/S,对每个 32 位字来说,效率会慢了四倍,另外,还要加上 5 - 10 ms 的寻道时间等其他损耗,如果只访问一个字,内存要比磁盘快百万数量级。所以磁盘优化是很有必要的,下面我们会讨论几种优化方式 高速缓存最常用的减少磁盘访问次数的技术是使用 管理高速缓存有不同的算法,常用的算法是:检查全部的读请求,查看在高速缓存中是否有所需要的块。如果存在,可执行读操作而无须访问磁盘。如果检查块不再高速缓存中,那么首先把它读入高速缓存,再复制到所需的地方。之后,对同一个块的请求都通过 高速缓存的操作如下图所示 由于在高速缓存中有许多块,所以需要某种方法快速确定所需的块是否存在。常用方法是将设备和磁盘地址进行散列操作,然后,在散列表中查找结果。具有相同散列值的块在一个链表中连接在一起(这个数据结构是不是很像 HashMap?),这样就可以沿着冲突链查找其他块。 如果高速缓存 块提前读第二个明显提高文件系统的性能是,在需要用到块之前,试图 当然,块提前读取策略只适用于实际顺序读取的文件。对随机访问的文件,提前读丝毫不起作用。甚至还会造成阻碍。 减少磁盘臂运动高速缓存和块提前读并不是提高文件系统性能的唯一方法。另一种重要的技术是「把有可能顺序访问的块放在一起,当然最好是在同一个柱面上,从而减少磁盘臂的移动次数」。当写一个输出文件时,文件系统就必须按照要求一次一次地分配磁盘块。如果用位图来记录空闲块,并且整个位图在内存中,那么选择与前一块最近的空闲块是很容易的。如果用空闲表,并且链表的一部分存在磁盘上,要分配紧邻的空闲块就会困难很多。 磁盘碎片整理在初始安装操作系统后,文件就会被不断的创建和清除,于是磁盘会产生很多的碎片,在创建一个文件时,它使用的块会散布在整个磁盘上,降低性能。删除文件后,回收磁盘块,可能会造成空穴。 磁盘性能可以通过如下方式恢复:移动文件使它们相互挨着,并把所有的至少是大部分的空闲空间放在一个或多个大的连续区域内。Windows 有一个程序 磁盘碎片整理程序会在让文件系统上很好地运行。Linux 文件系统(特别是 ext2 和 ext3)由于其选择磁盘块的方式,在磁盘碎片整理上一般不会像 Windows 一样困难,因此很少需要手动的磁盘碎片整理。而且,固态硬盘并不受磁盘碎片的影响,事实上,在固态硬盘上做磁盘碎片整理反 下面我们来探讨一下 I/O 流程问题。 I/O 设备什么是 I/O 设备?I/O 设备又叫做输入/输出设备,它是人类用来和计算机进行通信的外部硬件。输入/输出设备能够向计算机
块设备块设备是一个能存储 与字符设备相比,块设备通常需要较少的引脚。 块设备的缺点基于给定固态存储器的块设备比基于相同类型的存储器的字节寻址要慢一些,因为必须在块的开头开始读取或写入。所以,要读取该块的任何部分,必须寻找到该块的开始,读取整个块,如果不使用该块,则将其丢弃。要写入块的一部分,必须寻找到块的开始,将整个块读入内存,修改数据,再次寻找到块的开头处,然后将整个块写回设备。 字符设备另一类 I/O 设备是 设备控制器设备控制器是处理 CPU 传入和传出信号的系统。设备通过插头和插座连接到计算机,并且插座连接到设备控制器。设备控制器从连接的设备处接收数据,并将其存储在控制器内部的一些 每个设备控制器都会有一个应用程序与之对应,设备控制器通过应用程序的接口通过中断与操作系统进行通信。设备控制器是硬件,而设备驱动程序是软件。 内存映射 I/O每个控制器都会有几个寄存器用来和 CPU 进行通信。通过写入这些寄存器,操作系统可以命令设备发送数据,接收数据、开启或者关闭设备等。通过从这些寄存器中读取信息,操作系统能够知道设备的状态,是否准备接受一个新命令等。 为了控制 那么问题来了,CPU 如何与设备寄存器和设备数据缓冲区进行通信呢?存在两个可选的方式。第一种方法是,每个控制寄存器都被分配一个 IN REG,PORT CPU 可以读取控制寄存器 PORT 的内容并将结果放在 CPU 寄存器 REG 中。类似的,使用
CPU 可以将 REG 的内容写到控制寄存器中。大多数早期计算机,包括几乎所有大型主机,如 IBM 360 及其所有后续机型,都是以这种方式工作的。 第二个方法是 PDP-11 引入的,它将「所有控制寄存器映射到内存空间」中。 直接内存访问无论一个 CPU 是否具有内存映射 I/O,它都需要寻址设备控制器以便与它们交换数据。CPU 可以从 I/O 控制器每次请求一个字节的数据,但是这么做会浪费 CPU 时间,所以经常会用到一种称为 现代操作系统实际更为复杂,但是原理是相同的。如果硬件有 DMA 工作原理首先 CPU 通过设置 DMA 控制器的寄存器对它进行编程,所以 DMA 控制器知道将什么数据传送到什么地方。DMA 控制器还要向磁盘控制器发出一个命令,通知它从磁盘读数据到其内部的缓冲区并检验校验和。当有效数据位于磁盘控制器的缓冲区中时,DMA 就可以开始了。 DMA 控制器通过在总线上发出一个 然后,DMA 控制器会增加内存地址并减少字节数量。如果字节数量仍然大于 0 ,就会循环步骤 2 - 步骤 4 ,直到字节计数变为 0 。此时,DMA 控制器会打断 CPU 并告诉它传输已经完成了。 重温中断在一台个人计算机体系结构中,中断结构会如下所示 当一个 I/O 设备完成它的工作后,它就会产生一个中断(默认操作系统已经开启中断),它通过在总线上声明已分配的信号来实现此目的。主板上的中断控制器芯片会检测到这个信号,然后执行中断操作。 精确中断和不精确中断使机器处于良好状态的中断称为
不满足以上要求的中断称为 IO 软件原理I/O 软件目标设备独立性I/O 软件设计一个很重要的目标就是 错误处理除了 同步和异步传输I/O 软件实现的第三个目标就是 同步传输中数据通常以块或帧的形式发送。发送方和接收方在数据传输之前应该具有 缓冲I/O 软件的最后一个问题是 共享和独占I/O 软件引起的最后一个问题就是共享设备和独占设备的问题。有些 I/O 设备能够被许多用户共同使用。一些设备比如磁盘,让多个用户使用一般不会产生什么问题,但是某些设备必须具有独占性,即只允许单个用户使用完成后才能让其他用户使用。 一共有三种控制 I/O 设备的方法
I/O 层次结构I/O 软件通常组织成四个层次,它们的大致结构如下图所示 下面我们具体的来探讨一下上面的层次结构 中断处理程序在计算机系统中,中断就像女人的脾气一样无时无刻都在产生,中断的出现往往是让人很不爽的。中断处理程序又被称为 中断处理程序负责处理中断发生时的所有操作,操作完成后阻塞,然后启动中断驱动程序来解决阻塞。通常会有三种通知方式,依赖于不同的具体实现
设备驱动程序每个连接到计算机的 I/O 设备都需要有某些特定设备的代码对其进行控制。这些提供 I/O 设备到设备控制器转换的过程的代码称为 设备控制器的主要功能有下面这些
在这种情况下,设备控制器会阻塞,直到中断来解除阻塞状态。还有一种情况是操作是可以无延迟的完成,所以驱动程序不需要阻塞。在第一种情况下,操作系统可能被中断唤醒;第二种情况下操作系统不会被休眠。 设备驱动程序必须是 与设备无关的 I/O 软件I/O 软件有两种,一种是我们上面介绍过的基于特定设备的,还有一种是 与设备无关的软件的基本功能是对所有设备执行公共的 I/O 功能,并且向用户层软件提供一个统一的接口。 缓冲无论是对于块设备还是字符设备来说,缓冲都是一个非常重要的考量标准。缓冲技术应用广泛,但它也有缺点。如果数据被缓冲次数太多,会影响性能。 错误处理在 I/O 中,出错是一种再正常不过的情况了。当出错发生时,操作系统必须尽可能处理这些错误。有一些错误是只有特定的设备才能处理,有一些是由框架进行处理,这些错误和特定的设备无关。 I/O 错误的一类是程序员 设备驱动程序统一接口我们在操作系统概述中说到,操作系统一个非常重要的功能就是屏蔽了硬件和软件的差异性,为硬件和软件提供了统一的标准,这个标准还体现在为设备驱动程序提供统一的接口,因为不同的硬件和厂商编写的设备驱动程序不同,所以如果为每个驱动程序都单独提供接口的话,这样没法搞,所以必须统一。 分配和释放一些设备例如打印机,它只能由一个进程来使用,这就需要操作系统根据实际情况判断是否能够对设备的请求进行检查,判断是否能够接受其他请求,一种比较简单直接的方式是在特殊文件上执行 设备无关的块不同的磁盘会具有不同的扇区大小,但是软件不会关心扇区大小,只管存储就是了。一些字符设备可以一次一个字节的交付数据,而其他的设备则以较大的单位交付数据,这些差异也可以隐藏起来。 用户空间的 I/O 软件虽然大部分 I/O 软件都在内核结构中,但是还有一些在用户空间实现的 I/O 软件,凡事没有绝对。一些 I/O 软件和库过程在用户空间存在,然后以提供系统调用的方式实现。 盘盘可以说是硬件里面比较简单的构造了,同时也是最重要的。下面我们从盘谈起,聊聊它的物理构造 盘硬件盘会有很多种类型。其中最简单的构造就是 磁盘为了组织和检索数据,会将磁盘组织成特定的结构,这些特定的结构就是「磁道、扇区和柱面」 磁盘被组织成柱面形式,每个盘用轴相连,每一个柱面包含若干磁道,每个磁道由若干扇区组成。软盘上大约每个磁道有 8 - 32 个扇区,硬盘上每条磁道上扇区的数量可达几百个,磁头大约是 1 - 16 个。 对于磁盘驱动程序来说,一个非常重要的特性就是控制器是否能够同时控制两个或者多个驱动器进行磁道寻址,这就是 RAIDRAID 称为 RAID 有不同的级别
磁盘格式化磁盘由一堆铝的、合金或玻璃的盘片组成,磁盘刚被创建出来后,没有任何信息。磁盘在使用前必须经过 前导码相当于是标示扇区的开始位置,通常以位模式开始,前导码还包括 磁盘臂调度算法下面我们来探讨一下关于影响磁盘读写的算法,一般情况下,影响磁盘快读写的时间由下面几个因素决定
这三种时间参数也是磁盘寻道的过程。一般情况下,寻道时间对总时间的影响最大,所以,有效的降低寻道时间能够提高磁盘的读取速度。 如果磁盘驱动程序每次接收一个请求并按照接收顺序完成请求,这种处理方式也就是 通常情况下,磁盘在进行寻道时,其他进程会产生其他的磁盘请求。磁盘驱动程序会维护一张表,表中会记录着柱面号当作索引,每个柱面未完成的请求会形成链表,链表头存放在表的相应表项中。 一种对先来先服务的算法改良的方案是使用 假如我们在对磁道 6 号进行寻址时,同时发生了对 11 , 2 , 4, 14, 8, 15, 3 的请求,如果采用先来先服务的原则,如下图所示 我们可以计算一下磁盘臂所跨越的磁盘数量为 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51,相当于是跨越了 51 次盘面,如果使用最短路径优先,我们来计算一下跨越的盘面 跨越的磁盘数量为 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ,相比 51 足足省了两倍的时间。 但是,最短路径优先的算法也不是完美无缺的,这种算法照样存在问题,那就是 这里有一个原型可以参考就是我们日常生活中的电梯,电梯使用一种 电梯算法需要维护一个 我们举个例子来描述一下电梯算法,比如各个柱面得到服务的顺序是 4,7,10,14,9,6,3,1 ,那么它的流程图如下 所以电梯算法需要跨越的盘面数量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22 电梯算法通常情况下不如 SSF 算法。 错误处理一般坏块有两种处理办法,一种是在控制器中进行处理;一种是在操作系统层面进行处理。 这两种方法经常替换使用,比如一个具有 30 个数据扇区和两个备用扇区的磁盘,其中扇区 4 是有瑕疵的。 控制器能做的事情就是将备用扇区之一重新映射。 还有一种处理方式是将所有的扇区都向上移动一个扇区 上面这这两种情况下控制器都必须知道哪个扇区,可以通过内部的表来跟踪这一信息,或者通过重写前导码来给出重新映射的扇区号。如果是重写前导码,那么涉及移动的方式必须重写后面所有的前导码,但是最终会提供良好的性能。 稳定存储器磁盘经常会出现错误,导致好的扇区会变成坏扇区,驱动程序也有可能挂掉。RAID 可以对扇区出错或者是驱动器崩溃提出保护,然而 RAID 却不能对坏数据中的写错误提供保护,也不能对写操作期间的崩溃提供保护,这样就会破坏原始数据。 我们期望磁盘能够准确无误的工作,但是事实情况是不可能的,但是我们能够知道的是,一个磁盘子系统具有如下特性:当一个写命令发给它时,磁盘要么正确地写数据,要么什么也不做,让现有的数据完整无误的保留。这样的系统称为 稳定存储器使用两个一对相同的磁盘,对应的块一同工作形成一个无差别的块。稳定存储器为了实现这个目的,定义了下面三种操作:
时钟
时钟硬件在计算机中有两种类型的时钟,这些时钟与现实生活中使用的时钟完全不一样。
这种时钟称为 时钟软件时钟硬件所做的工作只是根据已知的时间间隔产生中断,而其他的工作都是由
软定时器时钟软件也被称为可编程时钟,可以设置它以程序需要的任何速率引发中断。时钟软件触发的中断是一种硬中断,但是某些应用程序对于硬中断来说是不可接受的。 这时候就需要一种 软定时器因为不同的原因切换进入内核态的速率不同,原因主要有
死锁问题也是操作系统非常重要的一类问题 资源大部分的死锁都和资源有关,在进程对设备、文件具有独占性(排他性)时会产生死锁。我们把这类需要排他性使用的对象称为 可抢占资源和不可抢占资源 资源主要有可抢占资源和不可抢占资源。
死锁如果要对死锁进行一个定义的话,下面的定义比较贴切 「如果一组进程中的每个进程都在等待一个事件,而这个事件只能由该组中的另一个进程触发,这种情况会导致死锁」。 资源死锁的条件针对我们上面的描述,资源死锁可能出现的情况主要有
发生死锁时,上面的情况必须同时会发生。如果其中任意一个条件不会成立,死锁就不会发生。可以通过破坏其中任意一个条件来破坏死锁,下面这些破坏条件就是我们探讨的重点 死锁模型Holt 在 1972 年提出对死锁进行建模,建模的标准如下:
从资源节点到进程节点表示资源已经被进程占用,如下图所示 在上图中表示当前资源 R 正在被 A 进程所占用 由进程节点到资源节点的有向图表示当前进程正在请求资源,并且该进程已经被阻塞,处于等待这个资源的状态 在上图中,表示的含义是进程 B 正在请求资源 S 。Holt 认为,死锁的描述应该如下 这是一个死锁的过程,进程 C 等待资源 T 的释放,资源 T 却已经被进程 D 占用,进程 D 等待请求占用资源 U ,资源 U 却已经被线程 C 占用,从而形成环。 有四种处理死锁的策略:
下面我们分别介绍一下这四种方法 鸵鸟算法最简单的解决办法就是使用 死锁检测和恢复第二种技术是死锁的检测和恢复。这种解决方式不会尝试去阻止死锁的出现。相反,这种解决方案会希望死锁尽可能的出现,在监测到死锁出现后,对其进行恢复。下面我们就来探讨一下死锁的检测和恢复的几种方式 每种类型一个资源的死锁检测方式每种资源类型都有一个资源是什么意思?我们经常提到的打印机就是这样的,资源只有打印机,但是设备都不会超过一个。 可以通过构造一张资源分配表来检测这种错误,比如我们上面提到的 如果这张图包含了一个或一个以上的环,那么死锁就存在,处于这个环中任意一个进程都是死锁的进程。 每种类型多个资源的死锁检测方式如果有多种相同的资源存在,就需要采用另一种方法来检测死锁。可以通过构造一个矩阵来检测从 P1 -> Pn 这 n 个进程中的死锁。 现在我们提供一种基于矩阵的算法来检测从 P1 到 Pn 这 n 个进程中的死锁。假设资源类型为 m,E1 代表资源类型1,E2 表示资源类型 2 ,Ei 代表资源类型 i (1 <= i <= m)。E 表示的是 现在我们就需要构造两个数组:C 表示的是 一般来说,已分配资源 j 的数量加起来再和所有可供使用的资源数相加 = 该类资源的总数。 死锁的检测就是基于向量的比较。每个进程起初都是没有被标记过的,算法会开始对进程做标记,进程被标记后说明进程被执行了,不会进入死锁,当算法结束时,任何没有被标记过的进程都会被判定为死锁进程。 上面我们探讨了两种检测死锁的方式,那么现在你知道怎么检测后,你何时去做死锁检测呢?一般来说,有两个考量标准:
从死锁中恢复上面我们探讨了如何检测进程死锁,我们最终的目的肯定是想让程序能够正常的运行下去,所以针对检测出来的死锁,我们要对其进行恢复,下面我们会探讨几种死锁的恢复方式 通过抢占进行恢复在某些情况下,可能会临时将某个资源从它的持有者转移到另一个进程。比如在不通知原进程的情况下,将某个资源从进程中强制取走给其他进程使用,使用完后又送回。这种恢复方式一般比较困难而且有些简单粗暴,并不可取。 通过回滚进行恢复如果系统设计者和机器操作员知道有可能发生死锁,那么就可以定期检查流程。进程的检测点意味着进程的状态可以被写入到文件以便后面进行恢复。检测点不仅包含 为了进行恢复,要从上一个较早的检查点上开始,这样所需要资源的进程会回滚到上一个时间点,在这个时间点上,死锁进程还没有获取所需要的资源,可以在此时对其进行资源分配。 杀死进程恢复最简单有效的解决方案是直接杀死一个死锁进程。但是杀死一个进程可能照样行不通,这时候就需要杀死别的资源进行恢复。 另外一种方式是选择一个环外的进程作为牺牲品来释放进程资源。 死锁避免我们上面讨论的是如何检测出现死锁和如何恢复死锁,下面我们探讨几种规避死锁的方式 单个资源的银行家算法银行家算法是 Dijkstra 在 1965 年提出的一种调度算法,它本身是一种死锁的调度算法。它的模型是基于一个城镇中的银行家,银行家向城镇中的客户承诺了一定数量的贷款额度。算法要做的就是判断请求是否会进入一种不安全的状态。如果是,就拒绝请求,如果请求后系统是安全的,就接受该请求。 类似的,还有多个资源的银行家算法,读者可以自行了解。 破坏死锁死锁本质上是无法避免的,因为它需要获得未知的资源和请求,但是死锁是满足四个条件后才出现的,它们分别是
我们分别对这四个条件进行讨论,按理说破坏其中的任意一个条件就能够破坏死锁 破坏互斥条件我们首先考虑的就是「破坏互斥使用条件」。如果资源不被一个进程独占,那么死锁肯定不会产生。如果两个打印机同时使用一个资源会造成混乱,打印机的解决方式是使用 后台进程通常被编写为能够输出完整的文件后才能打印,假如两个进程都占用了假脱机空间的一半,而这两个进程都没有完成全部的输出,就会导致死锁。 因此,尽量做到尽可能少的进程可以请求资源。 破坏保持等待的条件第二种方式是如果我们能阻止持有资源的进程请求其他资源,我们就能够消除死锁。一种实现方式是让所有的进程开始执行前请求全部的资源。如果所需的资源可用,进程会完成资源的分配并运行到结束。如果有任何一个资源处于频繁分配的情况,那么没有分配到资源的进程就会等待。 很多进程「无法在执行完成前就知道到底需要多少资源」,如果知道的话,就可以使用银行家算法;还有一个问题是这样「无法合理有效利用资源」。 还有一种方式是进程在请求其他资源时,先释放所占用的资源,然后再尝试一次获取全部的资源。 破坏不可抢占条件破坏不可抢占条件也是可以的。可以通过虚拟化的方式来避免这种情况。 破坏循环等待条件现在就剩最后一个条件了,循环等待条件可以通过多种方法来破坏。一种方式是制定一个标准,一个进程在任何时候只能使用一种资源。如果需要另外一种资源,必须释放当前资源。对于需要将大文件从磁带复制到打印机的过程,此限制是不可接受的。 另一种方式是将所有的资源统一编号,如下图所示 进程可以在任何时间提出请求,但是所有的请求都必须按照资源的顺序提出。如果按照此分配规则的话,那么资源分配之间不会出现环。 尽管通过这种方式来消除死锁,但是编号的顺序不可能让每个进程都会接受。 其他问题下面我们来探讨一下其他问题,包括 「通信死锁、活锁是什么、饥饿问题和两阶段加锁」 两阶段加锁虽然很多情况下死锁的避免和预防都能处理,但是效果并不好。随着时间的推移,提出了很多优秀的算法用来处理死锁。例如在数据库系统中,一个经常发生的操作是请求锁住一些记录,然后更新所有锁定的记录。当同时有多个进程运行时,就会有死锁的风险。 一种解决方式是使用 如果在第一阶段某个进程所需要的记录已经被加锁,那么该进程会释放所有锁定的记录并重新开始第一阶段。从某种意义上来说,这种方法类似于预先请求所有必需的资源或者是在进行一些不可逆的操作之前请求所有的资源。 不过在一般的应用场景中,两阶段加锁的策略并不通用。如果一个进程缺少资源就会半途中断并重新开始的方式是不可接受的。 通信死锁我们上面一直讨论的是资源死锁,资源死锁是一种死锁类型,但并不是唯一类型,还有通信死锁,也就是两个或多个进程在发送消息时出现的死锁。进程 A 给进程 B 发了一条消息,然后进程 A 阻塞直到进程 B 返回响应。假设请求消息丢失了,那么进程 A 在一直等着回复,进程 B 也会阻塞等待请求消息到来,这时候就产生 尽管会产生死锁,但是这并不是一个资源死锁,因为 A 并没有占据 B 的资源。事实上,通信死锁并没有完全可见的资源。根据死锁的定义来说:每个进程因为等待其他进程引起的事件而产生阻塞,这就是一种死锁。相较于最常见的通信死锁,我们把上面这种情况称为 通信死锁不能通过调度的方式来避免,但是可以使用通信中一个非常重要的概念来避免: 但是并非所有网络通信发生的死锁都是通信死锁,也存在资源死锁,下面就是一个典型的资源死锁。 当一个数据包从主机进入路由器时,会被放入一个缓冲区,然后再传输到另外一个路由器,再到另一个,以此类推直到目的地。缓冲区都是资源并且数量有限。如下图所示,每个路由器都有 10 个缓冲区(实际上有很多)。 假如路由器 A 的所有数据需要发送到 B ,B 的所有数据包需要发送到 D,然后 D 的所有数据包需要发送到 A 。没有数据包可以移动,因为在另一端没有缓冲区可用,这就是一个典型的资源死锁。 活锁某些情况下,当进程意识到它不能获取所需要的下一个锁时,就会尝试礼貌的释放已经获得的锁,然后等待非常短的时间再次尝试获取。可以想像一下这个场景:当两个人在狭路相逢的时候,都想给对方让路,相同的步调会导致双方都无法前进。 现在假想有一对并行的进程用到了两个资源。它们分别尝试获取另一个锁失败后,两个进程都会释放自己持有的锁,再次进行尝试,这个过程会一直进行重复。很明显,这个过程中没有进程阻塞,但是进程仍然不会向下执行,这种状况我们称之为 饥饿与死锁和活锁的一个非常相似的问题是 我们假设打印机的分配方案是每次都会分配给最小文件的进程,那么要打印大文件的进程会永远得不到服务,导致进程饥饿,进程会无限制的推后,虽然它没有阻塞。 倒是多此一举,不仅没有提高性能,反而磨损了固态硬盘。所以碎片整理只会缩短固态硬盘的寿命。 重磅!程序员大白交流群-学术微信交流群已成立 额外赠送福利资源!邱锡鹏深度学习与神经网络,pytorch官方中文教程,利用Python进行数据分析,机器学习学习笔记,pandas官方文档中文版,effective java(中文版)等20项福利资源 获取方式:进入群后点开群公告即可领取下载链接 注意:请大家添加时修改备注为 [学校/公司 + 姓名 + 方向] 例如 —— 哈工大+张三+对话系统。 号主,微商请自觉绕道。谢谢!
|
|
来自: 西北望msm66g9f > 《编程》