操作系统

定义

• 是应用程序与硬件的中间层
• 管理各种软硬件资源
• 解决资源访问冲突，确保资源公平高效的使用

特征

• 并发
• 共享
• 虚拟
• 异步

演进

原因

• 计算机各种硬件资源的进步，使得操作系统必须作出改变，从而可以更好的发挥硬件的效能
• 软件设计思想的进步

步伐

• 单用户系统
• 批处理系统
• 多道程序系统
• 分时
• 个人计算机
• 分布式计算机

内存管理

os-ram

CPU内部有寄存器和多级缓存，CPU和磁盘等外设之间有内存。

计算机通过对存储分级，是为了在一定性价比的情况下，使得CPU访问存储的速度尽可能快。

进程的地址

os-process-memory

• 抽象

  通过抽象出逻辑地址，使得进程看到的地址是连续的

• 保护

  独立地址空间

• 共享

  进程间可以访问相同的内存

• 虚拟化

  进程可以获得高于计算机可以提供的内存

内存管理的方式

• 重定位

  由于程序在每次运行时，加载到内存的地址都是不一样的，所以程序无法在编译时确定某个变量的内存地址。如果在程序运行时加上基地址，进程中的变量地址为基地址加偏移，那么在程序加载运行的时候，只需要改变进程的基地址地址，就可以动态的把整个进程的地址作出控制。

• 分段

  由于程序的逻辑结构，在每个结构内访问另外一个结构的的地址的可能非常低，例如代码段的内存，不大可能会访问数据段的地址。因此如果把程序的逻辑地址空间做划分，分成几个小段，那么在分配内存的时候，就可以不必分配一片大而连续的内存地址。

• 分页

  在通过对进程分配一大段连续的物理内存，对操作系统的压力会非常大，有可能导致大量的外碎片，而且如果对物理内存进行连续内存整理，会产生非常大的开销。此时如果把物理内存按页管理，在分配给进程时，通过组合多个页来构成进程的逻辑地址空间，可以解决外碎片和连续内存面对的问题。

• 虚拟存储

  由于物理内存是有限的，如果操作系统上运行了若干个进程，那么，通过虚拟化的手段，每个进程看到的逻辑地址空间，都是一片大的内存空间，有可能大于物理内存。可以通过内外存的置换算法，来实现内存空间的虚拟化。

进程的地址生成

• 编译时

  如果起始地址已知，则在编译时写死在执行文件中，此时如果改变起始地址，则需要重新编译

• 加载时

  如果起始地址未知，编译器生成可重定位代码，在加载时，由操作系统生成绝对地址

• 执行时

  在执行代码的过程中，代码的内存地址空间可以移动。此时地址转换硬件（页表）支持

连续内存分配

给进程分配一块指定大小的连续物理内存区域

内存碎片

由于程序是动态运行的，在运行的每个时刻，对内存的要求都是不一样的，如果每次分配时，都按最大要求来分配，那么会导致程序在不是高峰时刻，造成内存资源的浪费，而导致内存碎片

外部碎片

物理内存分配多个块后，有可能导致块与块之间存在小的块，随着内存分配的进行下去，会导致越来越多的这样的小块，而无法利用。

分配策略

• 最先匹配
• 最佳匹配
• 最差匹配

碎片整理

通过调整进程占用的内存位置，以减少分区碎片

条件

所有的应用程序可以动态重定位

时机

被移动的进程，需要处于就绪态或者等待态才能移动。

分区对换

os-swap-process

如果计算机资源只能满足一个进程处于内存中，那么可以通过分区对换技术，把多个进程在内存和外存之间来回切换，交替使用CPU，来实现多道程序的目的。

伙伴系统

通过把内存划分为2^n大小，来分配内存

非连续内存分配

连续分配的缺点

• 物理内存必须连续
• 存在外碎片和内碎片
• 难以动态修改
• 内存利用率低

非连续分配的设计目标

• 提高内存利用率和挂历灵活顶
• 允许程序使用非连续的内存地址空间
• 允许共享代码与数据
• 支持动态加载和动态链接

如果解决

• 如何实现虚拟地址和物理地址的转换
  • 软件实现：灵活，开销大
  • 硬件实现：够用，开销小
• 如果选择非连续块的大小
  • 段
  • 页

段式存储

把程序分成多个段，段与段之间交互少，使得可以分散在内存的不连续区域。通过段加偏移来实现。

段：堆/栈/数据段/代码段

页式存储

• 页帧

  物理页面(2^n)

• 页面

  逻辑页面(2^n)

• 页面到页帧

  它们大小相等。通过页表来实现关联。通过MMU/TLB来进行运算

页表

• 每个页面对应一个页表项

• 随着进程运行状态而动态变化

• 包括

  • 存在位

    是否存在物理页面与之关联

  • 修改位

    页面是否修改，用于是否把页面从内存刷新到磁盘或者用于优化置换算法的作用

  • 引用位

    有是否被引用，用于置换算法的策略

问题

• 性能不好，每次访问页面需要先访问页表，再访问数据。
• 页表可能非常大，而占据了大量的内存空间

如何解决

• 缓存页表： 由于访问的邻近性，可以使用CPU中高速缓存来解决二次访问内存的问题
• 间接访问：页表太大可以通过多级页表来下降页表的大小。这是由于大多数程序在运行时，并不需要访问正片内存空间，这就没必要为进程建立整个内存空间的页表映射，此时可以通过建立多级页表，动态修改页表的方法，来生成页表。从而达到降低页表的内存使用量

反置页表

段页式存储

通过在页前加上段，从而实现段页式存储访问

虚拟存储

由于对存储的要求越来越高，而硬件资源无法从价格和存储大小上跟上需求，这引出了虚拟存储的概念，让计算机把存储虚拟成可以支持比内存更大的地址空间，来满足更高的内存要求

手工

覆盖

os-memory-cover

由于程序在运行的过程中，没有必要在每个时刻都加载所有的程序到内存进行计算，这样程序员可以通过手工把程序划分成上图类似的结构，在程序运行的过程中，动态的加载和卸载模块，实现在有限内存中跑更大的程序的目的。

缺点：

• 需要程序员划分模块
• 增加程序复杂度

交换

由于CPU在某一时刻可以处理的程序数是一定的，那么必然有大量的程序是处于非运行状态，此时，可以暂时把不运行的程序整个换出到外存中。从而腾出更多的空间，给运行中的程序。

需要程序支持动态重定位的功能

虚拟存储技术的目标

os-memory-close

• 只把部分程序放在内存中
• 操作系统自动完成内外存切换
• 使得可以运行比物理内存大的程序

局部性原理

• 时间局部性：一条指令或数据在一次访问和下一次访问会集中在一个短时间内
• 空间局部性：访问一条指令/数据，跟访问此指令/数据的邻近区域会发生在一个较小的区域内
• 分支局部性：一条跳转指令的两次执行，很可能跳到同一个内存位置

虚拟存储的原理

• 只加载当前指令的部分载入内存
• 在执行到没有加载到内存的指令/数据时，发生缺页请求，把相关页面加载到内存
• 把暂时不用的页面换出内存

实现方式

• 虚拟页式存储
• 虚拟段式存储

需要的支持

• 硬件：页式或短时存储中的地址转换机制
• 操作系统：内存和外存页面的换入换出

虚拟页式存储管理

• 在页式存储的基础上，增加请求调页和页面置换

置换算法

功能

• 当出现缺页异常时，调入新页面
• 当内存满时，换出页面

设计目标

• 尽可能减少页面的换入换出次数

页面锁定

• 操作系统的关键部分
• 要求响应速度的代码和数据
• 页面的锁定标志位

算法分类

局部页面置换算法

• 页面仅限于进程内的页面
• 最优算法，先进先出算法，最久未使用算法，时钟算法，最不常用算法

全局页面置换算法

• 页面范围时全局的
• 工作集算法，缺页率算法

算法

最优页面置换算法（OPT）

置换在未来最长时间不访问的页面

特征

• 缺页最少
• 由于无法预知未来，所以无法实现

先进先出算法

选择内存驻留时间最长的页面进行置换

特征

• 简单
• 低效

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

选择最长时间没有被使用的页面进行置换

是OPT的一种近似

时钟置换算法

是LRU和FIFO的折中

把页面用一个环连起来

每个页面有一个访问位，如果访问过则为1

顺时针扫描页面，发现访问位为0，则置换，为1则赋值为0

最不常用算法（LFU）

统计每个页面的访问次数，置换访问次数最小的页面

Balady现象

当分配物理页面数增加时，缺页次数不降反升的现象

LRU/FIFO/Clock比较

• LRU性能较好，但系统开销较大
• FIFO开销小，会发生Belady现象
• Clock是它们的折中

全局置换算法

• 为进程分配可变数目的物理页面

os-memory-cpu

随着进程数的增加，CPU的利用率会不断的上升

当进程数达到一定规模后，系统的缺页率会陡然上升

导致CPU利用率急速下降

缺页率置换算法

通过监控进程的缺页率，设置缺页率的阈值

如果高于阈值，则分配更多的物理页面

如果低于阈值，则分配更少的物理页面

使得进程的缺页率稳定在一定的区间

进程

进程是一个程序的动态执行

os-process

进程控制块PCB

是进程在操作系统的唯一标志

内容

• 进程标志信息

• 处理及现场保存

  如寄存器

• 进程控制信息

  如进程占用的内存地址，各个段的起始位置

  处理状态，进程间通讯的标志

数据结构

• 链表：把所有的PCB用链表串起来
• 索引：通过索引来组织PCB

状态

• 创建

• 就绪

• 运行

• 等待

• 退出

• 挂起

  把进程的映像换出到外存中，减少内存的占用，宝库奥就绪挂起和等待挂起

多线程

引入原因

• 多进程共享数据比较困难，多数需要系统调用完成
• 由于进程设计资源的管理，所以它的创建，销毁，切换的开销大

设计特性

• 实体间并发执行
• 共享相同的地址空间

进程与线程的比较

• 进程是资源分配的单位
• 线程是CPU调度的单位
• 线程的创建时间比进程短
• 线程的终止时间比进程短
• 线程的切换时间比进程短
• 线程在数据共享更方便和高效
• 线程安全性低

用户线程

不需要操作系统支持，在用户态通过函数库，实现线程功能的支持

优点

• 不需要经过操作系统
• 开销小

缺点

• 一个线程阻塞，会导致整个进程进入等待
• 除非当前线程主动放弃运行，否则其他线程无法使用CPU
• 多个线程共享进程的时间片

内核线程

操作系统实现线程机制，内核完成创建，终止和管理功能

优点

• 一个线程阻塞不会影响其他线程的运行

缺点

• 开销大

进程切换

• 暂停当前运行进程，从运行态变为其他状态
• 调度另一个进程，从就绪态变为运行态

要求

• 切换前，保存进程上下文
• 切换后，恢复进程上下文
• 快速切换

上下文包括寄存器，CPU状态，内存地址空间

进程创建

• fork：通过复制进程的所有上下文，并创建出不同pid的子进程
• exec：通过覆盖进程的内存空间的内容，创建出新的进程

处理机调度

进程切换

• 保存进程的执行上下文
• 恢复下一个进程的上下文

调度

• 从就绪队列中挑选下一个占用CPU运行的进程
• 从多个可用CPU中挑选一个运行新进程的CPU

策略

• 依据什么原则挑选进程，线程和CPU
• 什么时候调度
  • 进程从运行态变为等待
  • 进程终止
  • 进程主动放弃CPU
  • 中断发生，使得高优先级进程从等待变为就绪
  • 进程时间片用完

算法的准则

• CPU使用率：CPU忙的时间百分比

• 吞吐量：单位时间内完成的进程数

• 周转时间：进程从初始化到结束的总时间，包括等待时间

• 等待时间：进程在就绪队列的总时间

• 响应时间：从提交到响应花费的总时间

  对于UI方面的应用，会比较多考虑响应时间

• 资源分配公平性

在设计调度算法时，需要结合操作系统的使用需求，而对上述的准则作出不同比例的调整，因为计算机的资源是有限的，而这些准则在一定程度上存在矛盾，所以必须作出一些妥协，最大程度的满足使用者的需求

算法

先来先服务算法

短进程有限算法

最高响应比算法

通过计算等待时间和执行时间，可以得到响应比

时间片轮转算法

多级反馈队列算法

对不同的进程，使用不同的队列，不同的队列使用不同的算法来管理

公平共享调度算法

主要考量资源的公平性，有针对不同用户的公平，也有针对不同进程的公平。

实时调度

进程的正确性依赖时间和功能两方面

硬实时

错过任务的时限会导致灾难性的后果

在设计时必须考虑最坏情况下也能满足时限

多处理机调度

对称多处理机调度

• 每个处理机有自己的调度程度

静态进程分配

• 进程固定分配到一个固定的CPU
• 处理机有自己的队列
• 调度开销小
• 处理机之间负载不均匀

动态进程分配

• 进程在执行中可以分配到任意空闲的处理机
• 所有处理机共享一个就绪队列
• 调度开销大
• 负载均匀

优先级反置

os-cpu-revert

T1占有了资源

T2等待T1的资源

T3优先级比T1高而获得执行

导致T2优先级高，却需要等待

优先级继承

如果进程占有了资源，如果有更高优先级的进程在等待，则提高进程的优先级，保证在占用资源的期间，可以快速执行而释放资源

同步互斥

由于CPU在执行程度时，在很多时候会在不同进程/线程间切换运行，如果它们之间含有共享变量，那么有可能导致不确定和诡异不正确的结果，此时需要引入同步互斥，来把某段不可分割的代码封装成原子操作，却道结果的正确性

方法

禁用硬件中断

没有中断，没有上下文切换，因此没有并发

缺点：粒度太大，临界区如果太长，会导致其他进程处饥饿状态

硬件原子锁支持

bool test_and_set(bool *value) {
    bool orig = *value;
    *value = true;
    return orig;
}

/* shared variable */
bool lock = false;
 
/* arbitrations */
while (test_and_set(&lock));
// critical section ...
lock = false;

硬件引入testandset原子操作，这可以为上层应用提供原子机制，使得如果实现自旋锁，可以写一个循环，并不断的检测共享变量lock；如果实现线程切换，可以引入test失败，则进入等待状态，释放锁时，把所有等待锁的线程变为就绪状态，然后取竞争锁。

linux称为惊群

信号量

是进程/线程间的一种资源同步机制。

通过设定资源数量，再通过P（减一），V（加一）操作，实现资源信息的同步。

条件变量

死锁

处理方法

• 死锁预防

  确保系统永远不会进入死锁状态

  • 互斥

    把互斥的资源封装成同时访问

  • 持有并等待

    请求资源时，不允许持有其他资源

    仅允许再进程开始时一次性把所有资源申请到

  • 非抢占

    如果不能马上分配到资源，则释放所有资源

  • 循环等待

    对资源排序，进程按顺序请求资源

• 死锁避免

  使用前，只允许不会出现死锁的进程申请锁

  • 银行家算法

• 死锁检测与恢复

  通过周期性的检查，判断系统是否处于死锁状态，并进行恢复

  类似银行家算法，判断资源的持有状态，通过是否能最后把所有进程都能得到资源并执行完毕，来判断是否有死锁

由于处理死锁的消耗非常大，一般的操作系统不处理死锁，而是把死锁的处理交给应用程序

进程间通讯

进程间通过内核关联一片共享资源，操作共享资源，达到信息沟通的目的。

分类

• 同步
• 异步
• 阻塞
• 非阻塞
• 有限缓冲
• 无限缓冲
• 无缓冲

信号

通过软件中断来支持

操作如下

• 捕获
• 忽略
• 屏蔽

进程拥有默认的信号处理函数，操作系统会对信号处理函数注册，并在接收到外部程序对此进程的信号的时候，产生中断，并调用进程空间的信号处理函数，来处理信号。

进程可以通过注册信号处理函数，来覆盖系统默认的处理函数

管道

子进程继承父进程的文件描述符，通过在0，1描述符上，打开管道描述符，父子进程之间就可以进行读写操作。

在父子进程消亡后，管道资源自动释放

消息队列

资源的消亡跟进程不关联。

多个进程可以共享同一个消息队列

共享内存

进程间通过操作系统，开辟一片内存空间，并在进程内部的进程空间进行内存映射，进程可以通过读写映射的内存，达到通信的目的。

但是在读写的过程中，需要引入同步控制，防止错误的数据读写

文件系统

是操作系统中管理持久化数据的子系统。提供数据存储和访问功能。

需要考虑的问题

• 分配文件磁盘空间
  • 管理文件块
  • 管理空闲空间
  • 分配算法
• 管理文件集合
  • 定位
  • 命名
  • 文件系统结构
• 数据可靠与安全
  • 安全
  • 持久化保存
  • 避免系统崩溃，媒体错误，攻击

文件描述符

是操作系统识别打开文件的标志。

它包含

• 文件指针
• 最后一次的读写位
• 文件打开的次数
• 磁盘中的位置
• 缓存数据的信息
• 访问的权限

视图

用户视图

用户一般关系可视化的内容

系统视图

系统一般不关心文件的内容，它一般把文件为字节序列的集合

文件的访问模式

• 顺序访问
• 随机访问
• 索引访问

一致性

对于共享的文件，在多用户下，如何保证文件访问的一致性。

• 需要加入同步机制
• 写入内容只有在文件关闭时可见
• 读写锁
• unix把一致性的控制交给了应用程序来保证

目录

目录是一种特殊的文件，它的内容是它下面的文件列表。

Unix系统呈现树状结构

操作

• 搜索文件
• 创建文件
• 删除文件
• 列目录
• 重命名文件
• 遍历路径

操作系统只允许内核修改目录

• 确保映射的完整性
• 应用程序通过系统调用访问目录

数据结构

• 线性列表
• 哈希表

文件别名

• 硬链接：多个文件项指向一个文件。
• 软链接：以快捷方式指向其他文件

虚拟文件系统VFS

对不同的文件系统提供一个统一的访问接口。

文件分配

由于系统中的文件，大部分是小文件，有少数大文件。

所以在设置文件块的分配时，需要同时兼顾在小文件时能用尽量少的空间来存放，对于大文件需要比较快的访问到文件。

UFS的设计，通过对于建立多级索引，初始的索引用一级索引链接到数据块，如果一级索引用完，则用二级索引/三级索引来链接数据块。

冗余磁盘阵列RAID

为了提高磁盘的吞吐量和可靠可用性

• RAID-0

  把一个文件分块存储在多个磁盘上，那么在读文件时，就可以并行的读，来提高读的速度

• RAID-1

  采用镜像的方法，把一个文件，从一个磁盘同步到另外一个磁盘，来提高可靠性

• RAID-4

  一个文件分块存到不同的磁盘上，最后一个磁盘存校验和，如果其中一个磁盘错误，可以通过校验和恢复错误

• RAID-5

  RAID-4的校验和只会存在一个磁盘上，而RAID-5会分散的存在各个磁盘中

• RAID-6

  通过引入两个不同校验和块，使得可以允许最多两个磁盘错误。

在实际应用中，会用多种RAID的技术组合使用

IO系统

类型

• 字符设备

  以字节为单位顺序访问

• 块设备

  通过文件系统接口/内存映射文件/原始IO接口访问

• 网络设备

  格式化报文交换

访问方式

• 同步
• 异步

通过中断来通知操作系统

CPU与设备的通讯方式

• 轮询
• 中断
• DMA

读写

• IO指令

  通过IO端口访问

• 内存映射IO

  通过把设备映射到内存，CPU直接读写内存以完成读写操作

磁盘调度

通过在一定时间段内，对磁盘的读写序号排序，以环式的方法，扫描磁盘读写，可以达到最优性能