操作系统

作者: 谭英智 | 来源:发表于2020-10-05 14:31 被阅读0次

定义

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

特征

并发
共享
虚拟
异步

演进

原因

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

步伐

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

内存管理

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把一致性的控制交给了应用程序来保证

虚拟文件系统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直接读写内存以完成读写操作

磁盘调度

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