操作系统

发表于 2022-03-02 更新于 2022-04-18

操作系统实验

操作系统概览

什么是操作系统

用户角度： 操作系统是一个 控制软件：

管理应用程序。
为应用程序提供服务。
杀死应用程序。

对内角度： 操作系统用于资源管理：

管理外设、分配资源。

操作系统是硬件之上、应用程序之下的层次结构。
操作系统位于应用软件之下，为应用软件提供服务支撑。

外壳（shell） 内核（kernel）。

内核空间是操作系统内核访问的区域，独立于普通的应用程序，是受保护的内存空间。

用户空间是普通应用程序可访问的内存区域。

操作系统包含什么

硬件资源三大块：CPU、内存、磁盘。

CPU： CPU调度、进程线程。
内存： 物理内存管理、虚拟内存管理（在有限物理内存之上为应用提供内存）。MMU
文件系统： disk过于底层，不方便上层应用。所以我们做出文件系统管理。
中断处理与设备驱动： 驱动实现操作系统。

OS Kernel的特征：

1.并发
并发：在一段时间内多个程序运行，需要OS管理和调度。
并行：在一个时间点上共同运行（因此只有一个CPU无法完成并行）。

2.共享
是“同时”访问还是互斥共享，根据情况而定。

3.虚拟
把硬件虚拟化。比如：把CPU虚拟化为进程，把磁盘虚拟化为文件，内存虚拟化为地址空间。
利用多道程序设计技术，让每个用户都觉得有一个计算机专门为他服务。

4.异步
程序执行不是一贯到底，而是走走停停，向前推进速度不可预知。
但只要运行环境相同，OS需要保证程序运行的结果也相同。
（异步双方不需要共同的时钟，也就是接收方不知道发送方什么时候发送，所以在发送的信息中就要有提示接收方开始接收的信息，如开始位，同时在结束时有停止位。）

操作系统的启动

通电之后，如何启动。

DISK： 存放OS
BIOS： 基本I/O处理系统。（检查各种外设）

在DISK上，还存在Bootloader，用于加载OS。

开始加电时，BIOS从CS:IP（图示为x86）这个地址开始执行，之后完成一系列工作，包括：

POST（加电自检）：寻找显卡和执行BIOS等。

BIOS加载Bootloader

Bootloader放在硬盘的第一个主引导扇区（512字节）。BIOS从硬盘的第一个扇区寻找，一下便找到Bootloader，Bootloader再负责加载OS。之后，由Bootloader将操作系统的代码和数据从硬盘加载到内存中。之后，控制权交给到OS。（跳转到OS的地址）

操作系统的interface（系统调用、异常、中断）

定义

系统调用（来源于应用程序的请求）

应用程序主动向操作系统发出请求
异常（来源于不良的应用程序）

非法指令或其他坏的处理状态（如：内存出错）
中断（来源于外设）

来自不同的硬件设备的计时器和网络的中断

处理时间

异常：同步（知道什么时候产生，比如除以0）
中断：异步（不知道什么时候产生）
系统调用：异步或同步（返回过程可能是异步的，即系统处理完之后再告诉应用程序，应用程序再切回）

响应

异常：杀死或重新执行意想不到的应用程序指令。
中断：持续，对用户应用程序是透明的（见不到）。
系统调用：等待和持续。

终端和异常处理机制

中断、异常都有针对软硬件的处理过程。对中断和异常进行编号（中断表），编号对应特定地址，跳到处理历程，解决问题。
但是，中断打断了一个程序的正常执行，因此要设置保护与恢复机制。

中断
硬件： 1. 设置中断标记（CPU初始化），将内部、外部事件设置中断标记。 2. 产生中断号（中断事件ID），发给OS，OS来找到对应的处理历程。

软件：

1. 保存当前处理状态（保存被打断的执行现场。由OS完成）。

2. 中断服务程序处理；

3. 清除中断标记；

4. 恢复之前保存的处理状态。因此，应用程序完全不用感知到中断的产生。

异常：异常编号
1. 保存现场
2. 异常处理
  
  2.1. 杀死产生了异常的程序
  
  2.2. 重新执行异常指令
3. 恢复现场
系统调用
1. 应用程序需要操作系统提供服务，而这些服务无法由应用程序直接执行，而需要操作系统执行，这就需要操作系统提供接口，这些接口就叫做系统调用接口。
2. 程序访问主要是通过高层次的API接口而不是直接进行系统调用。

一旦执行系统调用之后，用户态会转换为内核态

程序的用户态是指级别比较低的状态；
操作系统的内核态是等级最高的状态。可以控制整个计算机系统。

函数调用和系统调用是不同的。

函数调用：

ESP是栈指针寄存器，存储着栈顶的地址
EBP存储着栈底的地址
EIP是返回地址
栈空间主要通过这两个地址确定

结束func1，返回主程序过程类似。

函数调用是在一个栈空间完成函数之间参数的传递。

应用程序发出系统调用之后，应用程序、操作系统、内核都有自己的堆栈，要切换堆栈（操作系统堆栈与其不同，需要开销。即系统调用开销大于函数调用，但好处是安全、可靠），也要实现由用户态到内核态的转换。系统处理完之后，要把数据从内核空间拷贝到用户空间，接着实现状态转换。

（TLB（快表）：TLB是Translation Lookaside Buffer的简称，可翻译为“地址转换后援缓冲器。简而言之就是页表的Cache)

为什么应用程序不能直接访问外设呢？（必须要经过操作系统？）

在计算机运行中，内核是被信任的第三方。
只有内核可以执行特权指令。
为了方便应用程序。

计算机的体系结构及内存分层体系

计算机基本硬件结构

内存

内存的层次结构

主存：物理内存

操作系统需要完成的一些事情

MMU: 内存管理单元（memory management unit)

抽象
保护
共享（进程间的数据传递机制）
虚拟化

在操作系统中管理内存的不同方法

程序重定位
分段
分页
虚拟内存
按需分页虚拟内存

地址空间和地址生成

几个问题：

               1. 什么是地址空间？逻辑地址空间和物理地址空间的区别？
               2. 地址空间是怎么生成的？什么时候生成逻辑地址空间？什么时候生成物理地址空间？
               1. OS如何保护不同的地址之间不受干扰？

地址空间

物理地址空间：主存、磁盘

逻辑地址空间：一个程序所看到的地址空间。所有的逻辑空间最终都落到物理空间内。

e.g.

编译和汇编阶段，地址都是以变量名代表。

.c .s .o .exe程序都是放在硬盘之中，最后的程序在内存中运行。可以看到运行时产生了内存偏移。

逻辑地址生成阶段，基本上不需要OS的参与。

即使程序放在内存中了，但其实还是逻辑地址，并不是物理地址。

CPU查找逻辑地址和物理地址的映射

当CPU需要执行某条指令的时候：

 1. ALU需要知道指令的内容，需要发出请求，请求中所带的参数就是逻辑地址
 2. MMU会去查找逻辑地址映射表中是否存在逻辑地址对应的物理地址。
 3. 如果有，那么完成。如果没有，那么会产生处理过程，去内存中找（MMU没有）。如果找到了，CPU控制器会给主存发出请求，获取某一物理地址的内容。
 4. 主存会把内存的内容通过总线传给CPU，之后CPU开始执行。

在这个过程中，OS所做的操作就是需要在这些操作之前把映射关系建立好。

OS需要确保不同程序的地址不受干扰。加以限制和约束（如图）。

连续内存分配

内存碎片

无法进一步利用的空间。
外碎片： 分配单元间的碎片；
内碎片： 分配单元内没有使用的碎片

分区的动态分配

首次适配算法

碰到第一个能满足需求的空块，那么就分配。如图，需求400 byte，那么从低地址到高地址，可以看到第一块1K的就满足要求。

需求：

按地址排序的空闲块列表。

重分配需要检查，看自由分区能合并于相邻的空闲分区。

最优分配算法

最差适配算法

压缩式碎片整理（紧致算法）

重置程序以合并孔洞
要求所有程序是动态可重置的
问题？
- 何时重置
- 开销

交换式碎片整理

利用起硬盘，将等待中的程序所占用的内存放到硬盘上。

问题：哪些程序进行交换？开销？（后续虚存管理会提及）

非连续内存分配

分段（更好的分离和共享）

程序的分段地址空间
分段寻址方案

分段访问方案

段访问机制

操作系统在正式寻址之前建立段表

分页（目前cpu主要采取机制）

分页地址空间
页寻址方案

分页需要一个页号和一个页内偏移。

和分段机制的区别：段的尺寸是可变的，页的大小是固定不变的。

划分物理内存到固定大小的帧（frame）
- 大小是2的幂
划分逻辑地址空间至相同大小的页（page）
- 大小是2的幂
建立方案转换逻辑地址为物理地址（pages to frames）
- 页表
- MMU/TLB（TLB叫快表）

2^S 一帧的大小 f为帧号 o是页内偏移

逻辑地址空间一般大于物理地址空间（存不下的会使用虚拟内存）

页表

页表概述
转换后备缓冲区
二级/多级页表（时间换空间）
反向页表

逻辑地址大小为64KB，物理地址大小为32KB

（4，0）-> 可以找到第四页100，页帧号均为0，说明不存在。产生内存访问异常。

（3，1023)->可以找到第三页011，页帧号为00100，页帧内偏移和页偏移相同为1023，可以得到（4，1023）

分页机制的性能问题

1）访问一个内存单元需要两次内存访问：一次用于获取页表项，一次用于访问数据

2）页表可能非常大。如64位及其如果每页1024字节，那么一个页表的大小为（2^64 /2^10 = 2^54），这是不合理的。每个程序都有自己的页表，那么页表也非常大。

可以使用缓存（caching） ， 间接（indirecting）访问 两种方法来解决

TLB（Translation Look-aside Buffer）

把经常访问的页表项放到TLB中

为了减少TLB的缺失，要注意程序的局部性。

二级页表

页表基寄存器（PTBR）指向页表. 页表长度寄存器（PTLR）指示页表的大小

一级页表存的是二级页表的起始地址

二级页表可以节省空间

e.g. 页面的大小为4KB，每个页表项为4B，所以每个页面中可以存放1K个（1024）个页表项，因此每1K个连续的页表项为一组，每组刚好占一个页面，这样就需要为离散的页表再建立一张页表，称为页目录表。

32位的逻辑地址空间，页表项大小为4B，页面大小4KB，则页内地址占12位将页表分为分为1024个表，每个表中包含1024个页表项，形成二级页表。二级页表结构的逻辑地址结构如下图：

多级页表

反向页表

以物理页号来查找逻辑页号

页容量只与物理页地址大小相关。好处是节省空间

问题：如何根据page frame号查找page号？

基于关联内存的方案（设计成本太大）

基于哈希（hash）查找的方案

page frame number （hash）-> page number

虚拟内存

起因（程序规模的增长远大于存储器容量的增长）
覆盖技术
交换技术
虚存技术
- 目标
- 程序局部性原理
- 基本概念
- 基本特征
- 虚拟页式内存管理

把一些希望通过OS的管理把不常用的数据放在硬盘，常用的数据放在内存中，这样使得有限的内存能够存放常用的代码和数据。这种管理方式需要CPU（硬件）、MMU（硬件）、OS内核协同管理之下可以实现。

覆盖技术

e.g.

A在常驻区（固定区），把相互之间没有调用关系的程序放到同一个区，在需要调用前，再调入覆盖区，替换掉覆盖区原有的段。

注：另一种覆盖方法

A占一个分区20K

B、E和F 共用一个分区50K

C和D 共用一个分区30K

覆盖技术的缺点：

由程序员来把一个大的程序划分为若干个小地功能模块，并确定各个模块之间的覆盖关系，费时费力，增加了编程复杂度。
覆盖模块由外存装入内存，实际上是以时间来换取空间。

交换技术

交换技术的问题：

何时发生交换？因为内存和外存的读写速度差异太大，因此频繁的交换会造成巨大的开销，只当内存空间不够或有危险的时候换出。
如何划分硬盘，交换区的大小？
程序换入时的重定位。换出后和换入时的内存地址一定要是一样吗？可以采取动态地址映射来解决。

覆盖和交换的比较

交换发生在内存的程序之间，覆盖发生在运行中的程序之内。

虚存技术

虚存技术的目标：

像覆盖技术那样，不是把程序的所有内容都放在内存中，但是是自动执行的，无需程序员干涉；
像交换技术那样，实现进程在内存与外存之间的交换，但是不是以一个程序为粒度，而是以页为粒度。

e.g.

4byte x 1024 = 4k，正好是一页

以页或段

虚存技术--虚拟页式内存管理

有效存储器访问时间（effective memory access time）

EAT = 访存时间 * 页表命中几率 + page fault处理时间 * page fault概率

页面置换算法（局部页面置换算法）

最佳页面置换算法（OPT）
先进先出算法
最近最久未使用算法
时钟页面置换算法

OPT以时间来记录，替换掉距离下一次访问最长时间内不被访问的页面

FIFO（队列），产生的缺页多

LRU是OPT的一个近似，LRU向之前看，OPT向后看

LRU算法需要记录每个页面使用时间的先后顺序，开销比较大。

二次机会法（改进型CLOCK置换算法），在使用位的基础上再增加一个修改位。

最近未被访问，也未被修改（u=0,m=0）
最近被访问，但未被修改（u=1,m=0）
最近未被访问，但被修改（u=0,m=1）
最近被访问，被修改（u=1,m=1）

计数器（寄存器的开销太大），每次寻找计数值最小的页面，开销也很大。

LFU存在的问题：一个页面在进程开始时使用的很多，但以后就不用了

页面置换算法（全局页面置换算法）

局部页替换算法的问题
工作集模型
工作集页置换算法
缺页率页面置换算法
抖动问题

局部页面置换算法问题

物理页帧大小对于置换算法性能影响极大。实际情况中，程序是分段进行的，物理页帧可变的，那该如何进行物理页帧大小分配？

工作集：一个进程当前正在使用的逻辑页面集合

工作集页置换算法

t=-2，访问page e

t=-1，访问page d

t=0，访问page a；那么time0，初始化有三个页面

t=1，page c产生缺页，然后加入了page c， t=2时，未产生缺页，但是因为 τ = 4，所以要拿出page e。在拿出page e时候要判断该页是否修改过，若修改过那么需要进行内存和硬盘的同步。

缺页率页面置换算法

程序的编写，局部性影响缺页率。

若运行的程序的缺页率过高。则通过增加工作集来分配更多的物理页面:若运行的程序的缺页率过低，则通过减少工作集来减少它的物理页面数。力图使运行的每个程序的缺页率保持在一个合理的范围内。

抖动问题

进程

进程的定义

一个具有一定独立功能的程序在一个数据集合上一次动态执行过程

进程的组成

进程的特点

动态性：可动态地创建、结束进程。
并发性：进程可以被独立调度并占用处理机运行。
独立性：不同进程的工作不相互影响。（页表等手段加以访问空间限制）
制约性：因访问共享数据/资源或进程间同步而产生制约。

进程控制结构

描述进程的数据结构：PCB（Process Control Block）。PCB是进程存在的唯一标志。

进程状态

进程的生命期管理
进程状态变化模型
进程挂起模型

进程的生命期管理

创建—运行—等待—唤醒—结束

进程创建

引起进程创建的3个主要事件：

系统初始化时；
用户请求创建一个新进程；
正在运行的进程执行了创建进程的系统调用。

进程运行

内核选择一个就绪进程，让它占用处理机并执行。如何选择？此类问题将在调度算法中讨论。

进程等待

在以下情况下，进程等待（阻塞）：

请求并等待系统服务，无法马上完成；
启动某种操作，无法马上完成；
需要的数据没有到达。

进程只能自己阻塞自己，因为只用进程自身才能知道何时需要等待某种事件的发生。

进程唤醒
进程唤醒的原因：

被阻塞进程需要的资源可以被满足。
被阻塞进程等待的事件到达。
将该进程的PCB插入到就绪队列。
进程只能被别的进程或者操作系统唤醒。

进程结束
在以下四种情况下，进程结束：

正常退出（自愿的）；
错误退出（自愿的）；
致命错误（强制性的）；
被其他进程所杀（强制性的）。

进程状态变化模型

进程挂起模型

定义：进程没有占用内存空间。处在挂起状态的进程映像在磁盘上。

线程

定义：线程是进程当中的一条执行流程。

TCB（thread control block）

需要有各自独立的寄存器、堆栈，但是能共享代码段、数据段、网络资源等等，

线程的创建和终止时间较短是因为不需要去考虑资源的创建和释放问题。
线程的切换时间不需要切换内存管理所需要的页表，而进程需要切换页表，这一操作开销很大。

线程实现

用户线程和内核线程的关系

1对1
1对多
多对多

操作系统看不到TCB，OS只能看到进程信息，看不到进程内的线程信息。所以说整个线程的调度和管理主要是由线程库（用户级的线程库）管理，OS不直接参与。

用户线程：

内核线程：

一个PCB管理了一个TCB的list，但是在具体的线程调度时，还是TCB进行

轻量级进程

定义：是内核支持的用户线程。一个进程可有一个或多个轻量级进程，每个量级进程由一个单独的内核线程来支持。

内核线程
内核线程只运行在内核态，不受用户态上下文的拖累。

处理器竞争：可以在全系统范围内竞争处理器资源；
使用资源：唯一使用的资源是内核栈和上下文切换时保持寄存器的空间
调度：调度的开销可能和进程自身差不多昂贵
同步效率：资源的同步和数据共享比整个进程的数据同步和共享要低一些。

轻量级进程
轻量级进程(LWP)是建立在内核之上并由内核支持的用户线程，它是内核线程的高度抽象，每一个轻量级进程都与一个特定的内核线程关联。内核线程只能由内核管理并像普通进程一样被调度。

轻量级进程由clone()系统调用创建，参数是CLONE_VM，即与父进程是共享进程地址空间和系统资源。

与普通进程区别：LWP只有一个最小的执行上下文和调度程序所需的统计信息。

处理器竞争：因与特定内核线程关联，因此可以在全系统范围内竞争处理器资源
使用资源：与父进程共享进程地址空间
调度：像普通进程一样调度

用户线程
用户线程是完全建立在用户空间的线程库，用户线程的创建、调度、同步和销毁全又库函数在用户空间完成，不需要内核的帮助。因此这种线程是极其低消耗和高效的。

处理器竞争：单纯的用户线程是建立在用户空间，其对内核是透明的，因此其所属进程单独参与处理器的竞争，而进程的所有线程参与竞争该进程的资源。
使用资源：与所属进程共享进程地址空间和系统资源。
调度：由在用户空间实现的线程库，在所属进程内进行调度

上下文切换

进程控制

创建进程

加载和执行进程

等待和终止进程

协程补充

进程： 进程是一个具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统资源分配和独立运行的最小单位；
线程： 线程是进程的一个执行单元，是任务调度和系统执行的最小单位；
协程： 协程是一种用户态的轻量级线程，协程的调度完全由用户控制。

进程与线程的区别

1、根本区别：进程是操作系统资源分配和独立运行的最小单位；线程是任务调度和系统执行的最小单位。
2、地址空间区别：每个进程都有独立的地址空间，一个进程崩溃不影响其它进程；一个进程中的多个线程共享该进程的地址空间，一个线程的非法操作会使整个进程崩溃。
3、上下文切换开销区别：每个进程有独立的代码和数据空间，进程之间上下文切换开销较大；线程组共享代码和数据空间，线程之间切换的开销较小。

当系统线程较少的时候没有什么问题，但是当线程数量非常多的时候，却产生了问题。一是系统线程会占用非常多的内存空间，二是过多的线程切换会占用大量的系统时间。

协程运行在线程之上，当一个协程执行完成后，可以选择主动让出，让另一个协程运行在当前线程之上。协程并没有增加线程数量，只是在线程的基础之上通过分时复用的方式运行多个协程，而且协程的切换在用户态完成，切换的代价比线程从用户态到内核态的代价小很多。

实际上协程并不是什么银弹，协程只有在等待IO的过程中才能重复利用线程，上面我们已经讲过了，线程在等待IO的过程中会陷入阻塞状态，意识到问题没有？

假设协程运行在线程之上，并且协程调用了一个阻塞IO操作，这时候会发生什么？实际上操作系统并不知道协程的存在，它只知道线程，因此在协程调用阻塞IO操作的时候，操作系统会让线程进入阻塞状态，当前的协程和其它绑定在该线程之上的协程都会陷入阻塞而得不到调度，这往往是不能接受的。

因此在协程中不能调用导致线程阻塞的操作。也就是说，协程只有和异步IO结合起来，才能发挥最大的威力。

那么如何处理在协程中调用阻塞IO的操作呢？一般有2种处理方式：

在调用阻塞IO操作的时候，重新启动一个线程去执行这个操作，等执行完成后，协程再去读取结果。这其实和多线程没有太大区别。
对系统的IO进行封装，改成异步调用的方式，这需要大量的工作，最好寄希望于编程语言原生支持。
（https://zhuanlan.zhihu.com/p/172471249）

调度

上下文切换
- 切换CPU的当前任务，从一个进程/线程到另一个。
- 保存当前进程/线程在PCB/TCB中的执行上下文（CPU状态）。
- 读取下一个进程/线程的上下文。
CPU调度
- 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程。
- 调度程序：挑选进程/线程的内核函数（通过一些调度策略）
- 什么时候进行调度？

调度准则

CPU使用率

CPU处于忙状态所占时间的百分比。

吞吐量

在单位时间内完成的进程数量。

周转时间

一个进程从初始化到结束， 所花费的时间。

等待时间

进程在就绪队列中的时间。

响应时间

从一个请求被提交到第一次产生响应 所花费的时间。

调度算法

FCFS 先来先服务
SPN(SJF) SRT 短进程优先（短作业优先）短剩余时间
- 可以是抢占的（SRT）或者是不可抢占的（SPN）
HRRN 最高响应比优先
Round Robin 轮循（时间片轮转调度算法）
Multilevel Feedback Queues 多级反馈队列
- 是时间片轮转调度算法和优先级调度算法的综合和发展，动态调整进程优先级和时间片大小。
Fair Share Scheduling 公平共享调度

实时调度

实时调度所面对的系统为Real Time System（实时系统）。

对于实时系统：

时间约束的及时性（deadlines）很重要；
速度和平均性能相对不重要；
时间约束的可预测性是其主要特性。

实时系统可分为：

强实时系统：需要在保证的时间内完成重要的任务，必须完成；
弱实时系统：要求重要的进程的优先级更高，尽量完成，并非必须。

比如视频掉帧，就是弱实时系统的体现。

多处理器调度与优先反转

如何避免优先级反转：

优先级继承

优先级天花板

进程同步

进程之间的交互会造成共享资源的访问。

next_pid保存的是当前最大的进程ID。但是这种方法，在两个进程并行时，会产生冲突。

所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch

临界资源

一次仅允许一个进程使用的资源称为临界资源。

临界区

临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域。

互斥

当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源。

死锁

两个或以上的进程，在相互等待完成任务，而最终没法将自身任务进行下去。

饥饿（starvation）

一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行。

实现临界区互斥的基本方法

硬件实现方法

禁用中断（中断屏蔽）

当一个进程在使用处理机执行它的临界区代码时，防止其他进程进入临界区进行访问的最简单方法是，禁止一切中断发生。因为CPU只在发生中断时引起进程切换，但是在多CPU情况下，中断屏蔽不可使用，因为其他CPU还能访问临界区。
软件方法

1. 单标志法

2. 双标志法先检查

3. 双标志发后检查

4. Peterson’s Algorithm

P82

更高级的抽象

test-and-set是不允许执行中断的

信号量

消费者问题需要引入同步和互斥操作。

P,V操作的顺序有影响，P操作能够产生阻塞。若Deposit交换前两个P操作，即先做mutex->P()，在执行emptyBuffers->p()，若生产者非常快，把fullbuffer填满了，那么下一个操作会执行mutex->P()，没问题，在下一个操作对emptyBuffer执行P操作，此时因为buffer满了，那么emptyBuffer为0，导致挂起，在此之后，消费者是没法执行操作的。陷入了死锁。