操作系统总结

一、概述

并发和并行

  • 并发: 一个处理器同时处理多个任务, 这里的同时是宏观概念, 指的是在某个时间段内这些任务交替执行
  • 并行: 多个处理器或者是多核的处理器同时处理多个不同的任务, 这里的同时就是同一时刻真正的一块儿执行多个任务

共享

共享是指系统中的资源可以被多个并发进程共同使用, 有两种共享方式：互斥共享和同时共享
互斥共享的资源称为临界资源，例如打印机等，在同一时间只允许一个进程访问，需要用同步机制来实现对临界资源的访问

虚拟

虚拟技术把一个物理实体转换为多个逻辑实体, 主要有两种虚拟技术：时分复用技术和空分复用技术。 例如多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占有处理器，每次只执行一小个时间片并快速切换

同步和异步

  • 同步就是整个处理过程顺序执行，当各个过程都执行完毕，并返回结果。是一种线性执行的方式，执行的流程不能跨越。一般用于流程性比较强的程序，比如用户登录，需要对用户验证完成后才能登录系统。

  • 异步则是只是发送了调用的指令，调用者无需等待被调用的方法完全执行完毕；而是继续执行下面的流程。是一种并行处理的方式，不必等待一个程序执行完，可以执行其它的任务，比如页面数据加载过程，不需要等所有数据获取后再显示页面。

内核态和用户态

  • 内核态：cpu可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu也可以将自己从一个程序切换到另一个程序。

  • 用户态：只能受限的访问内存，且不允许访问外围设备，占用cpu的能力被剥夺，cpu资源可以被其他程序获取

  • 用户态切换到内核态的3种方式: 系统调用、异常、外围设备的中断

二、进程与线程

进程

进程是一个正在执行程序的示例，拥有自己的程序计数器和内部状态，是系统进行资源分配和调度的一个独立单位。进程控制块 (Process Control Block， PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作

线程

线程是独立调度的基本单位。 一个进程中可以有多个线程，它们共享进程资源。就拿浏览器来说，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件

区别

  • 拥有资源
    进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源
  • 调度
    线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换
  • 系统开销
    由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小
  • 通信方面
    进程间通信 (IPC) 需要进程同步和互斥手段的辅助，以保证数据的一致性。而线程间可以通过直接读/写同一进程中的数据段（如全局变量）来进行通信

进程的状态

  • 就绪态 就是获取了出cpu外的所有资源，只要处理器分配资源就可以马上执行。

  • 运行态 就是获得了处理器分配的资源，程序开始执行。

  • 阻塞态 当程序条件不够时候，需要等待条件满足时候才能执行，如等待i/o操作时候，此刻的状态就叫阻塞态。

线程的状态

  • 新建（New）：线程在进程内派生出来，它即可由进程派生，也可由线程派生。

  • 阻塞（Block）：如果一个线程在执行过程中需要等待某个事件发生，则被阻塞。

  • 激活（Unblock）：如果阻塞线程的事件发生，则该线程被激活并进入就绪队列。

  • 调度（Schedule）：选择一个就绪线程进入执行状态。

  • 结束（Finish）：如果一个线程执行结束，它的寄存器上下文以及堆栈内容等将被释放

线程的实现方式

  • 在用户空间中实现线程
    用户级线程指不需要内核支持而在用户程序中实现的线程，其不依赖于操作系统核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。不需要用户态/核心态切换，速度快，操作系统内核不知道多线程的存在，因此一个线程阻塞将使得整个进程（包括它的所有线程）阻塞。由于这里的处理器时间片分配是以进程为基本单位，所以每个线程执行的时间相对减少。

  • 在内核中实现线程
    内核级线程由操作系统内核创建和撤销。内核维护进程及线程的上下文信息以及线程切换。一个内核线程由于I/O操作而阻塞，不会影响其它线程的运行。

  • 在用户空间中实现线程的优势

    1. 可以在不支持线程的操作系统中实现。
    2. 创建和销毁线程、线程切换代价等线程管理的代价比内核线程少得多
    3. 允许每个进程定制自己的调度算法，线程管理比较灵活
    4. 线程能够利用的表空间和堆栈空间比内核级线程多

  • 在用户空间中实现线程的缺点

    1. 同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起。
    2. 页面失效也会导致整个进程都会被挂起。
    3. 内核线程的优缺点刚好跟用户线程相反。实际上，操作系统可以使用混合的方式来实现线程

协程

协程，英文Coroutines，是一种比线程更加轻量级的存在。正如一个进程可以拥有多个线程一样，一个线程也可以拥有多个协程。 最重要的是，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。 这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。其本质是用户空间下的线程。（即不存在上下文切换，用户与内核地址空间切换，但协程是在单线程中运行）

协程的应用

  • Lua从5.0版本开始使用协程，通过扩展库coroutine来实现。

  • Python可以通过 yield/send 的方式实现协程。在python 3.5以后，async/await 成为了更好的替代方案。

  • Go语言对协程的实现非常强大而简洁，可以轻松创建成百上千个协程并发执行。

  • Java语言并没有对协程的原生支持，但是某些开源框架模拟出了协程的功能，Kilim框架的源码

疑问和思考

  • 网上关于进程和线程状态的介绍太杂, 不太能理解这两者的关系, 目前在我理解看来, 其实进程应该也包括新建和结束, 这就和线程其实是一样的, 而且我认为只有运行, 就绪, 阻塞这三种算是基本状态, 其他比如新建结束, 唤醒等应该只能算作是切换状态的操作
  • 在Java的线程还多了一种等待(Waiting)状态, 其实只是把阻塞状态更细化分成了BLOCKED和WAITING两种, 区别在于等待是主动等待, 阻塞是被动阻塞, 就是说等待的状态下只有主动去唤醒它才能进入就绪状态, 而阻塞的情况下线程本身一直在争抢锁, 一旦抢到了不需要别人主动去唤醒它自己就会切换到就绪状态

参考链接

三、进程间通信方式

管道

管道是连接两个一个读进程和一个写进程之间用于实现数据交换的一个共享文件

  • 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端，只有同时有读端和写端，管道才有存在意义
  • 当读端发现管道为空的时候需要睡眠等待，直到有数据时候被唤醒，相应的写端也是在管道已满的时候等待直到被唤醒
  • 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中
  • 互斥：统一时刻只能有一个进程对管道进行读写；
  • 包括无名管道和有名管道两种，前者用于父进程和子进程间的通信，后者用于运行于同一台机器上的任意两个进程间的通信

消息队列

是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。

  • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级
  • 消息队列独立于发送与接收进程, 进程终止时，消息队列及其内容并不会被删除
  • 消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取

信号(signal)

一种比较复杂的通信方式，用于通知接收进程某个事件已经发生, 是进程间通信机制中唯一的异步通信机制

信号量（semaphore）

与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

  • 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存
  • 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作
  • 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
  • 支持信号量组
  • 注意⚠️: 信号量和信号不是一个概念, 两者区别很大

共享内存（Shared Memory）

指两个或多个进程共享一个给定的存储区。

  • 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取
  • 因为多个进程可以同时操作，所以需要进行同步
  • 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问

套接字

套接字也是一种进程间通信机制，可以实现不同主机间的进程通信。一个套接口可以看做是进程间通信的端点，每个套接口的名字是唯一的，其他进程可以访问，连接和进行数据通信

总结

  • 管道：速度慢，容量有限
  • 消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
  • 信号量：不能传递复杂消息，只能用来同步
  • 共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存

四、同步机制

背景

  • 多进程（线程）并发执行会出现进程间相互制约的情况发生，例如两个进程需要：
    1. 共享唯一的硬件设备
    2. 共享同一块内存区域
    3. 一个进程的运行依赖另一进程对共享资源的执行结果

如果多个进程间存在时序关系，需要协同工作以完成一项任务，则称为同步；如果不满足协同的条件，而知识因为共享具有排他性资源时所产生的关系称为互斥, 互斥是一种特殊的同步

  • 对于同步机制，需要遵循以下四个规则
    1. 空闲则入：没有进程/线程在临界区时，任何进程可以进入；
    2. 忙则等待：有进程/线程在临界区时，其他进程均不能进入临界区；
    3. 有限等待：等待进入临界区的进程/线程不能无限期等待；
    4. 让权等待（可选）：不能进入临界区的进程/线程，应该释放 CPU，如转换到阻塞态

信号量

  • 信号量和PV原语操作是有Dijkstra发明的，它是最为广泛的互斥方法之一

  • 信号量和PV操作原理：

    1. 当进程想要进入共享区时，首先执行P操作，S-1
    2. 当进程想要退出共享区时，执行V操作，S+1
    3. 进程进出共享区的操作，是原子操作（执行过程不允许被中断）

  • 缺陷: 程序的易读性相对较差，对于信号量的管理也分散在各个参与对象中，因此有可能引起死锁，进程饿死等问题

管程(进程同步独有)

  • 管程是对Semaphore机制的延伸和改善，是一种更简单的同步手段
  • 管程是可以被多个进程/线程安全访问的对象或模块
  • 管程汇总的方法是受到Mutex保护的，意味着同一时刻只允许一个访问者来使用它们
  • 特性: 安全性、互斥性、共享性

临界区（线程同步）

通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问
在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占

互斥

互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享
互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享

事件（线程同步）

通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作

进程和线程之间同步机制的差异

  • 信号量、管程、互斥是进程的同步机制，而信号量、互斥也可用于线程的同步，但管程只在进程同步中被用到；

  • 线程的同步除了信号量、互斥外，还有临界区、事件，没有看到说将这两种方式作为进程的同步方式（不知道）；

经典同步问题

  • 生产者-消费者问题
  • 哲学家就餐问题
  • 读者-写者问题

具体参考:

参考链接

五、死锁

死锁是指多个进程在运行过程中，因为争夺资源而造成的一种僵局，如果没有外力推进，处于僵局中的进程就无法继续执行

产生死锁的原因

  • 系统资源不足。
  • 进程运行推进的顺序不当。
  • 资源分配不当等

产生死锁的四个必要条件

  • 互斥条件:进程对所分配的资源进行排他性的使用
  • 请求和保持条件：进程被阻塞的时候并不释放锁申请到的资源
  • 不可剥夺条件：进程对于已经申请到的资源在使用完成之前不可以被剥夺
  • 环路等待条件：发生死锁的时候存在的一个 进程-资源 环形等待链

死锁处理

  • 预防死锁：破坏产生死锁的4个必要条件中的一个或者多个；实现起来比较简单，但是如果限制过于严格会降低系统资源利用率以及吞吐量
  • 避免死锁：在资源的动态分配中，防止系统进入不安全状态(可能产生死锁的状态)-如银行家算法, 参考银行家算法
  • 检测死锁：允许系统运行过程中产生死锁，在死锁发生之后，采用一定的算法进行检测，并确定与死锁相关的资源和进程，采取相关方法清除检测到的死锁。实现难度大
  • 解除死锁：与死锁检测配合，将系统从死锁中解脱出来（撤销进程或者剥夺资源）。对检测到的和死锁相关的进程以及资源，通过撤销或者挂起的方式，释放一些资源并将其分配给处于阻塞状态的进程，使其转变为就绪态。实现难度大

六、调度算法

先来先服务FCFS

既可以作为作业调度算法也可以作为进程调度算法；按作业或者进程到达的先后顺序依次调度；因此对于长作业比较有利。

短作业优先SPF

作业调度算法，算法从就绪队列中选择估计时间最短的作业进行处理，直到得出结果或者无法继续执行；缺点：不利于长作业；未考虑作业的重要性；运行时间是预估的，并不靠谱。

高优先权优先HRRF

既可以作为作业调度也可以作为进程调度算法；调度作业时，从就绪队列中选择优先级最高的作业进行处理；由于涉及到了优先级，因此可以分为抢占式和非抢占式；而且优先级的确定也可以分为静态优先级（事先根据进程类型，进程对资源的需求，用户要求等方面确定一个固定值）；动态优先级（随进程的推进或者等待时间而增加或者减少）。

最高响应比优先HRN

FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。

时间片轮转

按到达的先后对进程放入队列中，然后给队首进程分配CPU时间片，时间片用完之后计时器发出中断，暂停当前进程并将其放到队列尾部，循环。

多级反馈队列

目前公认较好的调度算法；设置多个就绪队列并为每个队列设置不同的优先级，第一个队列优先级最高，其余依次递减。优先级越高的队列分配的时间片越短，进程到达之后按FCFS放入第一个队列，如果调度执行后没有完成，那么放到第二个队列尾部等待调度，如果第二次调度仍然没有完成，放入第三队列尾部…。只有当前一个队列为空的时候才会去调度下一个队列的进程

七、内存管理

基本知识

链接

生成装入模块形成完整逻辑地址
三种链接方式：

  • 静态链接: 装入前链接
  • 装入时动态链接: 运行前边装入边链接
  • 运行时动态链接: 运行时需要才装入并链接

目的：确定完整的逻辑地址

装入

装入内存形成物理地址

三种装入方式：

  • 绝对装入：编译时产生绝对地址，单道程序环境
  • 静态重定位：装入时将逻辑地址转化为物理地址，多道批处理操作系统
  • 动态重定位：运行时将逻辑地址转化为物理地址，需要设置定位寄存器，现代操作系统

目的：确定最终的物理地址

碎片

  • 内部碎片（已分配），分配给某进程的内存区域中，而之有些部分没有用上
  • 外部碎片（未分配），内存中某些空闲分区由于太小而难以利用

连续分配管理方式

  • 单一连续分配: 内存分为系统区和用户区，只能有一道用户程序（无外部碎片，有内部碎片）
  • 固定分区分配: 将整个用户空间划分若干个固定大小的分区，分区大小可相等也可不相等，每个分区只能装入一道作业，分区说明表进行管理（无外部碎片，有内部碎片）
  • 动态分区分配: 根据进程的大小动态地建立分区，使用空闲分区表或空闲分区链进行管理，动态分区算法选择合适的空闲分区分配（有外部碎片，无内部碎片）

动态分区分配算法

首次适应算法（FF）

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

循环首次适应算法（NF）

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

最佳适应算法（BF）

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

最坏适应算法（WF）

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

非连续分配管理方式

基本分页存储管理

基本分页存储管理中不具备页面置换功能(即没有实现虚拟内存的功能)，因此需要整个程序的所有页面都装入内存之后才可以运行。因为程序数据存储在不同的页面中，而页面又离散的分布在内存中，因此需要一个页表来记录逻辑地址和实际存储地址之间的映射关系，以实现从页号到物理块号的映射。由于页表也是存储在内存中的，因此和不适用分页管理的存储方式相比，访问分页系统中内存数据需要两次的内存访问(一次是从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址；第二次就是根据第一次得到的物理地址访问内存取出数据)。

为了减少两次访问内存导致的效率影响，分页管理中引入了快表(或者联想寄存器)机制(联想到缓存机制)，包含快表机制的内存管理中，当要访问内存数据的时候，首先将页号在快表中查询，如果查找到说明要访问的页表项在快表中，那么直接从快表中读取相应的物理块号；如果没有找到，那么访问内存中的页表，从页表中得到物理地址，同时将页表中的该映射表项添加到快表中，可能存在快表换出算法

优缺点:没有外部碎片，内存利用率高。但各页中内容没有关联，不利于编程和共享

补充概念：

  • 页框=页帧=内存块=物理块=物理页面（内存分区）
  • 页=页面（进程逻辑地址空间分区）
  • 页面和页框一一对应（页表，页表项由“页号”和“块号”组成，页号不占用内存空间）
  • 页表长度是指这个页表中总共有几个页表项，即总共有几个页；
  • 页表项长度是指每个页表项占多大的存储空间；
  • 页面大小是指一个页面占多大的存储空间

基本分段存储管理

把程序按内容或过程（函数）关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应一个二维线形虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址影射机构把段式虚拟地址转换为实际内存物理地址

  • 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每段有段名且每段从0开始编址；

  • 逻辑地址结构：段号和段内地址（段内偏移量）；

  • 内存分配规则：以段为单位进行分配，每个段在内存中占据连续的空间，各段不相邻 ；

  • 段表中的段表项由段号（隐含的，不占存储空间）、段长、基地址组成；

  • 与页表地址转换的不同之处在于增加了还要根据段表中记录的段长来检查段内地址是否越界

优缺点:

  • 可以针对不同类型的段采取不同的保护
  • 可以按段为单位来进行共享，包括通过动态链接进行代码共享
  • 不会产生内部碎片，但会产生外部碎片，内存利用率比分页低

分段和分页的区别

  • 页是信息的物理单位，是出于系统内存利用率的角度提出的离散分配机制；段是信息的逻辑单位，每个段含有一组意义完整的信息，是出于用户角度提出的内存管理机制。
  • 页的大小是固定的，由系统决定；段的大小是不确定的，由用户决定。
  • 分页的逻辑地址结构是一维的（偏移量），分段是二维的（段名+偏移量）

段页式存储管理

  • 将进程按逻辑模块分段后再将每个段分页，不会产生外部碎片，只会产生少量内部碎片；
  • 逻辑地址结构（二维）：段号、页号、页内偏移地址 + 页号、页面存放的块号；

地址变换：由逻辑地址得到短号、页号、页内偏移量–>段号与段表寄存器中的段长度比较，检查是否越界–>由段表始址、段号找到对应段表项–>根据段表中记录的页表长度，检查页号是否越界–>由段表中的页表地址、页号查询页表项–>由块号和页内偏移得到物理地址–>访问目标单元

简单来说, 流程就是3次访存: 查段表 –> 查页表 –> 访问目标单元(设置了快表的话可以做到1次访存)

内存空间的扩充

覆盖技术

覆盖技术包含一个固定区（区内程序段在运行过程中不会调入调出）和若干覆盖区（区内程序段在运行过程中需要调入和调出），对用户不透明增加用户编程负担，是在同一个程序或者进程中进行的

交换技术

交换技术是内存紧张时，换出某些进程以腾出内存空间，再换入某些进程，而外存磁盘分为文件区和对换区，换出的进程放在对换区，是在不同进程（或作业）之间的

虚拟存储技术(虚拟内存)

  • 虚拟内存使用的原理：局部性原理(联想到Mysql中利用B树作为索引的数据结构原因)
    1. 时间局部性：现在访问的指令和数据在不久后会被访问
    2. 空间局部性：现在访问的内存单元周围的内存空间，很可能在不久后会被访问
    3. 高速缓存技术：使用频繁的数据放到更高速的存储器中

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器

  • 虚拟内存的定义：程序不需要全部装入即可运行，运行时动态调入，若内存不够则进行置换

  • 虚拟内存的特征

    1. 多次性：无需在作业运行时一次性全部装入内存，而是允许被分为多次调入内存
    2. 对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入和换出
    3. 虚拟性：逻辑上扩充内存容量，用户看到的内存容量远大于实际容量

  • 虚拟内存技术的实现: 请求分页存储管理，请求分段存储管理，请求段页式存储管理

  • 使用虚拟内存的代价

    1. 虚存的管理需要建立很多数据结构，占用额外内存。
    2. 虚拟地址到物理地址的转换，增加了指令执行时间。
    3. 页式的换入换出需要磁盘I/O，耗费时间。
    4. 如果一页中只有部分数据，浪费内存

页面置换算法

最优页面置换算法(OPT)

只具有理论意义的算法，用来评价其他页面置换算法。置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去。

先进先出置换算法(FIFO)

由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最早进入的页面放在表头；当发生缺页中断时，淘汰表头的页面并将新调入的页面追加到表尾。简单粗暴的一种置换算法，没有考虑页面访问频率信息。

最近最少使用算法(LRU)

算法赋予每个页面一个访问字段，用来记录上次页面被访问到现在所经历的时间t，每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现)。

时钟置换算法(也被称为最近未使用算法NRU)

页面设置一个访问位，页面被访问的时候访问位设置为1；并将所有页面保存在一个循环队列中，表针指向最老的页面。页面置换的时候，如果当前指针所指页面访问为为0，那么置换，否则将其置为0，循环直到遇到一个访问为位0的页面。

改进型Clock算法

在Clock算法的基础上添加一个修改位，替换时根究访问位和修改位综合判断。优先替换访问为何修改位都是0的页面，其次是访问位为0修改位为1的页面。

最少使用算法(LFU)

设置寄存器记录页面被访问次数，每次置换的时候置换当前访问次数最少的。存在问题是该访问寄存器并不能真正反映当前页面访问次数，因为访问速度比较快，所以在更新寄存器的时间间隔内访问1次和访问100次都是一样的。另外，LFU和LRU是很类似的，支持硬件也是一样的，但是区分两者的关键在于一个以时间为标准，一个以次数为标准(例如对于寄存器 pa 001111 和pb 111000，两个页面，如果采用LRU，那么被淘汰的是pa，如果采用LFU那么被淘汰的是pb)。

页面缓冲算法(PBA)

置换的时候，页面无论是否被修改过，都不被置换到磁盘，而是先暂留在内存中的页面链表(已修改页面链表和未修改页面链表，也可以不区分)里面，当其再次被访问的时候可以直接从这些链表中取出而不必进行磁盘IO，当链表中已修改也难数目达到一定数量之后，进行依次写磁盘操作(相当于将多次IO合并为一次)

页面分配策略

驻留集：是指请求分页存储管理中给进程分配的物理块的集合（即是系统给进程分配的物理块数）

固定分配局部置换：进程运行前就分配号驻留集，缺页时只能换出进程自己的某一页

可变分配全局置换：只要缺页就分配新的物理块，可能来自空闲物理块，也可能需换出别的进程页面

可变分配局部置换：根据发生缺页的频率来动态地增加或减少进程的物理块

何时调入页面：预调页策略（运行前）；请求调页策略（运行时）

何处调用页面：UNIX方式：第一次使用的页面都从文件区调入，调出的页面都写回对换区，再次使用时从对换区调入

抖动（颠簸）现象：由于分配给进程的物理块不够导致，刚刚换出的页面马上又换入主存，刚刚换入的页面马上就要换出主存——>如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；否则终止该进程或者增加驻留集大小

工作集：是指在某段时间间隔里，进程实际访问页面的集合（驻留集大小一般不小于工作集大小来防止抖动现象）

补充:

  • 缺页中断（或页错误）: 当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失部分装入物理内存并重新执行失败的指令
    一道计算缺页中断的例题
  • Belady异常：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象

八、文件系统

磁盘调度算法

  1. 先来先服务（FCFS）
  2. 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题
  3. 扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。
  4. 循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求
  5. NStepSCAN算法: N步SCAN算法将磁盘请求队列分成若干个长度为N的子序列，磁盘调度按FCFS算法依次处理这里子队列，而每个子队列的内部是根据SCAN算法进行处理的。当N很大的时候，算法接近于SCAN算法，当N=1时，退化成FCFS算法。N步SCAN算法可以有效避免“磁臂粘着”的现象

九、IO模型

参考: 操作系统中的I/O，及高性能IO模型

设备之间的IO

  • 轮询方式
    CPU主动在各种设备中轮询检查状态，有数据就IO
  • 中断方式
    设备有数据的时候，发出中断，由CPU决定要不要响应中断，然后中断，去处理设备的IO。CPU不用经常轮询设备状态。被动接收中断就行
  • 直接内存存取（DMA）访问方式
    如果1个字节的数据中断一次，传1KB的数据得中断1024次，太浪费CPU时间，于是有了DMA方式，CPU只需要把开头和结束的地址告诉DMA，中间由DMA完成数据IO。CPU从字节干预解放到数据块的干预
  • 通道控制方式
    DMA方式只能控制一个设备的一块数据，多块数据还是要CPU干预多次。于是有了通道来控制IO，它比DMA更强大，能控制多块数据，多个设备的IO，更加解放了CPU参与IO过程

用户进程间的IO

  • 阻塞
    用户线程调用某些系统函数去内核取数据，直到数据到达内核cache前，该线程处于阻塞状态，等待数据到达

  • 非阻塞
    用户线程去取数据，不管内核cache有没有数据，都直接返回，可能拿到数据，也可能拿不到，不会使线程进入阻塞态

  • IO多路复用
    多路就是一个线程管理多路IO，线程还是被阻塞调用，其中一路或几路IO有数据了就返回。需要线程遍历全部IO，判断是哪个IO有数据。
    例如 socket 的 select() 函数，线程调用 select() 进入阻塞态，任何一个IO有数据了，线程就退出阻塞态，获得机会继续执行。

  • 信号驱动IO
    给一个IO注册一个信号和信号触发的回调函数，一旦信号被触发，回调函数里读取数据。
    例如给 socket 注册一个“可读”的信号，当数据来了，可读的时候，信号被触发，执行回调函数从内核cache复制数据到用户空间

  • 异步IO
    异步IO中，操作系统完成了数据从内核到用户空间的拷贝后，以信号的方式通知用户线程可以下一步操作。省去了用户线程阻塞下来拷贝数据的过程

select，epoll，kqueue 原理

  • select
    select 管理多个 socket，select 收到一个来自网卡 IO 中断就返回，不知道这个中断对应是哪个 socket fd 的。需要用户线程遍历判断
  • epoll
    epoll 收到一个 IO 中断，会去查找这个中断对应哪个 socket fd。
    epoll 中建立一个红黑树（平衡二叉树的一种），红黑树查找很高效。
    用户注册感兴趣的 socket 事件，就是把这个 socket fd 插入到红黑树中，用中断号做key，可以理解为（中断号，socket fd）的二元组。
    用户移除事件就是，删除树上的某个节点。

然后收到一个IO中断，epoll 把网卡数据拷贝到内核cache，根据中断号在红黑树中查找对应的 fd，把 fd 加入到就绪链表中，准备返回给用户线程。用户直接得到就绪的 fd

  • kqueue
    收到 socket IO 中断去哈希表中查找对应的 socket fd，再把它放到一个链表里，返回。
    用户注册一个感兴趣的事件，就是往哈希表中添加一个 fd

参考链接