概论

操作系统的任务

• 自顶向下：为应用开发人员提供简洁易用的资源抽象
• 自底向上：管理种类繁多、纷繁复杂的硬件资源

并发性，指两个或两个以上的事件或活动在同一时间间隔内发生

并行性，指两个或两个以上事件或活动在同一时刻发生，是并发的特例

操作系统的特征

并发性、共享性（系统中的资源可被多个并发执行的任务（作业）所使用，互斥or同时）、异步性（能处理随机事件）、虚拟性（是操作系统的一种管理技术）

系统调用

应用程序请求内核操作系统服务的过程

用户触发system call，之后跳转到系统的相应处理函数

系统调用提供进程管理、文件操作、内存管理、进程通信、信息维护等

内核

操作系统的基本元素：内核、进程（资源分配和调度的单位）、线程（调度的单位）

内核分为微内核、单内核

基本功能：中断处理、时钟管理、短程调度（分配处理器，完成保护和恢复现场）、原语管理（通信原语、IO设备原语等）

处理器管理

处理器

指令

特权指令：有关资源管理、只能由操作系统执行

（仅在内核态下执行）

处理器状态

内核态&用户态

用户态→内核态：系统调用、中断、异常

栈

用户栈：保存应用程序的子程序间相互调用的参数、返回值、返回点、子程序的局部变量

内核栈/系统栈：保存中断现场/保存操作系统持续间相互调用的参数、返回值、返回点、局部变量

栈指针只有一个

程序状态字PSW

存放在EFLAGS里，分为状态标志（OF、SF等）、控制标志（IF中断允许等）、系统标志（管理进程）

中断技术

中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。

• 请求系统服务—系统调用
• 实现并发工作
• 处理突发事件
• 满足实时要求

中断源分类

• 硬中断（硬件产生）（上半部分）

• 软中断（信号、软件中断）（下半部分）

• 外中断（中断、异步）
• 内中断（异常、同步）（错误、陷阱、终止）

硬、软中断的区别

硬中断是由外设引发的，由中断控制器提供中断号、可屏蔽、属于上半部分；

软中断是执行中断指令（int）产生的，不可屏蔽，属于下半部分；

中断、异常的区别

中断是异步的（指令间），异常是同步的（一条指令执行期间）

一般来说，中断处理程序提供的服务不是为当前进程所需的，而异常处理程序提供的服务是为当前进程所用

中断事件的产生

硬件故障中断、程序性中断（语法错误、逻辑错误、异常）、I/O中断、访管中断（通过陷入指令调用操作系统内核程序）、时钟中断

中断优先级

当产生高优先级的中断时，应屏蔽比它优先级低的所有中断源（不响应这些）

确保高优先级可以打断低优先级中断，反之不能

要防止同级中断互相干扰，屏蔽同级的中断

开中断后，系统就可以响应其他的中断了，关中断后，系统不响应其他的中断（除非优先级高）

响应及服务

• 发现中断源

• 保护现场

• 转向处理中断/异常事件的处理程序

• 恢复现场

处理流程

中断

1. 设备发出中断请求，中断控制器将中断号转换成中断向量存储I/O寄存器
2. CPU根据中断向量号在IDT（中断描述符表）中找到中断服务程序的入口地址
3. 保护现场：将CPU寄存器的值压入核心栈
4. 对中断控制器进行确认，设置中断源状态等
5. 提供服务
6. 退出，恢复现场

异常

1. 转向异常处理程序公共入口
2. 将硬件错误码和异常向量号存入当前进程PCB中
3. 判别异常产生于核心态还是用户态
4. 对于核心态，将简单地转向内核预定义服务程序处理，没有被处理的核心态异常是操作系统的致命错误
5. 对于用户态异常，终止当前进程运行,并给当前进程发信号
6. 从ret_from_exception处返回用户空间时，检查进程是否有信号等待处理，如果有则根据信号类型调用相应函数进行处理

Linux中断处理

快、慢

Linux将中断分为快中断和慢中断

慢中断分为上下部分，上半部分关中断、下半部分开中断；快中断关中断

下半部分实现方式

BH数组（只支持32个，只能同步）、任务队列（无法并行）、软中断（可并行）、小任务（基于软中断实现）、工作队列（如果下半部分需要阻塞、获取信号量或大量主存时）

IDT

每一个中断/异常对应一个表项（门描述符）

中断门：关中断的中断或异常处理

陷阱门：开中断的异常处理

系统门：系统调用

IDTR寄存器存放IDT的起始地址

进程和线程

进程

定义和属性

原理角度：支持程序执行的系统机制

实现角度：刻画运行程序的状态和系统动态变化状况的数据结构

主要目的：

• 刻画程序的并发性
• 解决资源的共享性

属性：

• 动态性：程序的一次执行过程
• 共享性：多个不同进程可执行同一程序
• 独立性：每个进程是独立的实体
• 结构性：分为数据块、代码块、控制块、核心栈
• 制约性：进程间相互制约
• 并发性：在时间上可重叠

描述和组成

进程状态转换

三态模型：

七态模型：

进程上下文

进程物理实体和支持进程运行的环境合称进程上下文，系统调度产生进程上下文切换

用户级上下文、寄存器上下文、系统级上下文

进程控制块PCB

含有：

• 标识信息：进程ID、进程名、进程组ID、用户组名等
• 现场信息：通用寄存器、控制寄存器内容、栈指针、程序状态字等
• 控制信息：进程优先级、时间片剩余量等，用于管理和控制调度

进程队列的方式

链接方式：链表等

索引方式：通过PCB号建立索引表

进程的控制

上下文切换

切换只能在内核态

切换时机：主动调度（例如执行write、read等）、被动调度（时间片用完等）

切换步骤：

• 保存被中断进程的处理器现场信息
• 修改被中断进程的进程控制块的有关信息，如进程状态等
• 把被中断进程的进程控制块加入有关队列
• 选择下一个占有处理器运行的进程
• 修改被选中进程的进程控制块的有关信息
• 根据被选中进程设置操作系统用到的地址转换和存储保护信息
• 根据被选中进程恢复处理器现场

处理器状态转换

用户态 $\rightleftharpoons $ 内核态

线程

为什么引入线程

减少进程并发执行时所付出的时空开销，使得并发粒度更细、并发性更好

进程与线程

• 进程：保护和资源分配的基本单位，无需频繁切换

• 线程：处理器调度和分配的基本单位，体量小（轻量级线程），频繁切换
• 同一进程中的所有线程共享进程获得的主存空间和资源

线程的组成与状态

组成

• 线程惟一标识符及线程状态信息；

• 未运行时保存的线程上下文

• 核心栈：核心态下工作时，保存参数，函数调用时的返回地址等；

• 私有存储区：用于存放线程局部变量及用户栈。

状态

运行、就绪、堵塞（无挂起）

线程的实现

用户级线程

用户程序来管理线程

优点：切换快，无需OS支持

缺点：管理程序堵塞导致所有线程被堵塞

内核级线程

内核完成

混合线程

处理器调度

层次

• 高级调度：在多道批处理程序中使用，控制道数
• 中级调度：外存与内存中的进程对换（“挂起”）
• 低级调度：决定哪个就绪进程/线程转为运行

*多道批处理系统：系统内可同时容纳多个作业，放在外存中组成后背队列，系统可以容纳道数个作业在内存中运行，在作业运行过程中无法被干预

*分时系统：把CPU的运行分成若干时间片分别处理

*实时系统：对收到的信号做出实时反应（及时性）

选择调度算法原则

资源利用率（CPU有效工作时间/CPU总的运行时间）

吞吐率：单位时间CPU处理作业的个数

公平性

响应时间

周转时间（批处理从提交作业到作业完成）

平均作业周转时间：

$T=(\sum_{i=1}^{n}t_i)/n$

带权周转时间：$w_i=t_i/t_k$，前者是周转时间，后者是所需运行时间

作业调度和低级调度算法

调度程序两项任务

调度：实现调度策略，组织和维护就绪进程队列

分派：实现调度机制，负责上下文切换等

作业是任务实体，进程是完成任务的执行实体

低级调度的类型

剥夺式（抢占式）：高优先级可剥夺低优先级，用于用户程序

非剥夺式：一直运行，直到完成/自我放弃，用于内核关键程序

算法

FIFO/FCFS

SJF

最短作业优先算法

缺点：难以估计时间，时间长的会饥饿

SRTF

最短剩余时间算法

剥夺式的SJF，即当前新进的如果更短就会抢占

HRRF

最高响应比优先算法

$响应比=1+\frac{作业等待时间}{作业处理时间}$

短作业响应比高，长作业随着等待响应比变高

优先级调度算法

静态/动态

RR

轮转调度，剥夺式

MLFQ

多级反馈队列，多个优先级队列，较高优先级分配较短时间片，同一队列按FCFS

彩票调度算法

为进程发放针对各种资源（如CPU时间）的彩票。调度程序随机选择一张彩票，持有该彩票的进程获得系统资源

可以给予某些进程更多彩票

Linux调度算法

V2.4

schedule()函数调度，将任务分为

• SCHED_OTHER普通类任务（非实时进程，基于优先级的时间片轮询）
• SCHED_FIFO先进先出实时类任务（实时进程，没有时间片）
• SCHED_RR轮转法实时类任务（实时抢占进程，定量时间片）

nice 静态优先级 -20~19 数越低分越高，决定counter初值

counter 时间片余额，每次时间中断-1，为0就让出处理器，处于等待状态的counter增加

rt_priority 实时进程优先级

weight=counter+20-nice，决定优先级

counter(子进程)=(counter(父进程)+1)/2

V2.6

调度时间恒定—常数时间

同步、通信、死锁

并发进程

进程具有顺序性，并发打破顺序性

顺序程序需要：顺序性、封闭性、确定性、可再现性

并发的实质是一个处理器在几个进程之间的多路复用

Bernstein条件：并发进程的无关性是进程的执行与时间无关的一个充分条件

临界区调度原则（Dijkstra）：

• 一次至多一个进程能够进入临界区内执行

• 如果已有进程在临界区，其他试图进入的进程应等待

• 进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入

信号量与PV操作

信号量

一种软件资源，只能由同步原语PV对其操作

公用信号量：初值为1，实现互斥

私有信号量：初值为0/正整数，用于并发进程同步，该信号拥有的进程可做P，其他做V

原语操作

P()

将信号量-1，若小于0，则等待

V()

信号量+1，结果不大于0（有等待的进程），则释放list中的一个进程

一般来说，互斥信号量上的P操作总在后面执行（不然会死锁）

管程

PV操作：共享资源的管理分散在各个进程，且难以防止有意无意的违法同步操作

共享性、安全性、互斥性

条件变量：只有在管程中才能被访问

wait()

挂起进程并释放管程，直至另一个进程执行了signal

signal()

如果有因为wait挂起的，释放之，否则相当于空操作

格式

Type XXMonitor = Monitor {
    Cond cond;
    int count = k;
    Define xxx;
    InterfaceModule IM;
    Procedure xxx() { 
        enter(IM);
        //调用signal(cond,IM)，wait(cond,IM) 
        //可能使用count
        leave(IM);
    }
}

Func A()
{
    XXMonitor.xxx()
}

死锁

死锁产生

同时保持：互斥条件（互斥使用某些资源）、占有和等待条件（请求不满足时占有）、不剥夺条件（资源只能被自愿释放）→循环等待条件

死锁防止

（破1）使资源可同时访问、（破2）静态分配资源、（破3）剥夺调度、（破4）层次分配，将资源分层次，同层次只能用一个

死锁避免——银行家算法

算法结构

允许前三个条件，通过合适的资源分配算法避免出现循环等待链

每个客户预先说明所要的最大资金量，若银行满足，客户需要在有限时间内归还

各类资源总数构成：$Resource=[R_1,R_2,…,R_m]$

各类资源当前可用构成：$Available=[V_1,…,V_m]$

所有进程对各类资源构成矩阵$Claim[i,j]$，$Claim[i,j]=k$ 表示进程i需要k个资源j

所有进程已占有资源构成$Allocation[i,j]$

所有进程目前尚需构成$Need[i,j]=Claim[i,j]-Allocation[i,j]$

所有进程当前申请构成$Request[i,j]$

当某进程要启动工作，且其需要资源i，必须满足所有进程对i的claim之和小于resource，即算法只考虑最坏情况

系统安全性

在时刻$T_0$是安全的，仅当存在进程序列$P_1,…,P_n$，对任意进程$P_k$满足：

$\forall i,Need[k,i]\le Available[i]+\sum_{j=1}^{k-1}Allocation[j,i]$

即，当前所需≤尚存+之前进程所占有

那么，只要按照该进程序列，就可完成任务而不会死锁

算法描述

试探性分配，看看能否满足需求

S1: 如果 Request[i, *]≦Need[i, *]，转步骤S2；否则，进程申请量超过最大需求量，出错处理

S2: 如果 Request[i, *]≦Available[i, *]，转步骤S3；否则，进程申请量超过当前可分配量，进程等待

S3:试探性分配资源

S4:测试，如果安全则执行，否则回收资源，进程等待

测试算法：

找到当前进程中可满足需求的，满足其需求并令其工作完成，释放资源，不断重复，如果最后所有进程可满足则安全

死锁检测和恢复

资源分配图：进程→资源：需要，资源→进程：进程占有

进程通信

信号通信机制

是一种软中断

用户输入调用内核/内核检测出错/进程系统调用→调用信号系统给另一个进程发送信号

管道通信机制

管道实质上是一个共享文件，通过write/read操作的阻塞与唤醒实现

write写后唤醒read阻塞的

write写满后如果还要写则阻塞，直到有read读

read读空时阻塞，直到有write写

匿名管道

半双工（数据向一个方向流动）

只能用于具有亲缘关系（有共同祖先）的进程通信

int pipe(int filedes[2])：0用于读，1用于写

有名管道

FIFO

共享内存通信机制

消息传递通信机制

send和recieve原语

文件系统

文件

文件系统的功能

1. 文件的按名存取
2. 文件目录的建立和维护
3. 实现逻辑文件到物理文件的转换
4. 文件存储空间的分配和管理
5. 数据保密、保护和共享
6. 提供一组用户使用的操作

文件的属性

基本属性（名字等）

类型属性（普通/目录、系统文件等）

保护属性（读、写、可执行、可更新、可删除、可改变等）

管理属性（最后修改时间）

文件的存取方法

顺序、直接（随机）、索引

文件的使用

操作/控制台命令

系统调用API

文件目录

树形结构

文件的全名为 目录路径+文件名

文件控制块

FCB，包括文件名+inode号

inode包括数据当前大小、数据块大小、数据块数、操作集、硬连接数等

文件的组织与存储

Unix多重索引结构

文件操作的实现

超级块：存放文件系统结构和管理信息，如inode表占了多少盘块、空闲盘块数等

索引节点区：存放inode表

数据区

用户打开文件表：表项的序号是文件描述符fd，内容是系统打开文件表的一个入口指针fp，通过其打开文件的活动inode

系统打开文件表：包括活动inode指针f_inode、f_count记录有几个fd链向此

活动inode表：i_ino指向磁盘inode区对应inode表，i_data指向文件位置

创建文件create

• 为新文件分配索引节点和活动索引节点，并把索引节点编号与文件分量名组成新目录项，记到目录中
• 在新文件所对应的活动索引节点中置初值，如置存取权限i_mode，连接计数i_nlink等
• 分配用户打开文件表项和系统打开文件表项，置表项初值

删除unlink

要有写权限

把指定文件对应的目录项从所在的目录文件中除去，同时将目录项中i_link分量减1，如果i_link为零，则还要将此文件占用的存储空间释放。

打开open

• 检索目录，把对应的外存索引节点复制到活动索引节点表中。

• 根据输入参数mode值核对权限，如果非法，则打开失败。

• 为文件分配用户已打开表项和系统已打开表项，并为表项设置初值。通过指针建立表项与活动索引节点间联系。最后，返回用户已打开文件表项的序号（即文件描述字）

关闭close

• 根据fd找到用户已打开文件表项，再找到系统已打开表项。释放用户已打开文件表项；

• 将系统已打开文件表项中的f_count减1，若非零，则还有进程共享此表项，直接返回；否则，释放此表项，并找到与之关联的活动索引节点；

• 将活动索引节点中的i_count减1，若非零，则还有用户进程正使用该文件，直接返回，否则，讲活动索引节点内容写回磁盘索引节点分区，并释放该活动索引节点。

读read

根据f_flag中的信息，检查读操作是否合法

根据当前位移量f_offset值，需读出的字节数，以及活动索引节点中i_addr指出的文件物理块存放地址，计算出相应的物理块地址，并读到缓冲区中

拷贝到bufp指向的用户主存区

返回读取的字节数

写write

随机访问lseek

指定位置

复制dup

文件系统的管理

物理块小→磁盘利用率高

物理块大→I/O效率高

存储管理

分页存储管理

页面：逻辑地址空间

页框：物理地址空间

页号+页内偏移

页面号—页表→页框号

快表TLB 加快翻译速度

页面保护方法 在页表项加入标志位

多级页表：将页表分页 dir+page+offset

最佳页面大小：$p=\sqrt{2Se}$

S是进程平均占用的大小，e是每个页表项占用的大小

分段式存储管理

方便定位

保护：DPL（描述符权限），RPL（请求权限）≥CPL（当前权限）（否则无意义）

每次检查max(RPL,CPL)≤DPL是否成立

虚拟存储管理

程序具有时间和空间局部性

MMU存储管理部件

页面替换算法

$缺页中断率f=不成功访问次数F/总访问次数A$

最佳页面替换算法OPT

OPT，需要知道距现在最长时间后访问的页，不现实

FIFO

改进：页面缓冲算法：维护修改页面队列和空闲页面队列

每次淘汰页时将其放在两个队列尾，修改页面队列有一定数量之和批量写回

LRU最近最少使用

“老化算法”：每个页有一个多位寄存器。页面被访问时最左边置1。隔一段时间右移。淘汰时找最小的

SCR第二次机会

FIFO+引用位，如果FIFO首最近有被使用就不换（淘汰时，把1置0并跳过，直到遇到0）

时钟页面替换Clock

引用位+修改位

①找第一个未引用（r=0）、未修改（m=0）的，②若无找r=0，m=1的并将r置0，③若无再执行①②

局部页面替换算法

最佳

不论发生缺页与否，算法在每一步要考虑引用串，如果该页面在时间间隔(t,t+τ)内未被再次引用，那么就移出页面；否则，该页被保留在进程的驻留集中，直到再次被引用

工作集置换算法

工作集模型：$(t-\Delta,t)$时刻内访问的页面集合称为工作集$W(t,\Delta)$

利用程序局部性

模拟工作集替换算法

时间戳、老化

缺页频率替换算法

如果本次缺页与前次缺页之间的时间超过临界值τ，那么，所有在这个时间间隔内没有引用的页面都被移出工作集

设备管理

I/O硬件

方式

中断方式

CPU与控制器和设备间有中断请求线、控制器有中断允许位

DMA直接存储器存取：I/O设备能直接与内存交换数据而不占用CPU，但只能一次读取一个数据块，且不能满足复杂的IO需求

通道方式（I/O处理器）

I/O设备控制器

把串行的位流装配成字节，存入控制器内部的缓冲区形成字节块

I/O软件

高效率&通用性

中断处理程序、设备驱动程序、独立于设备的I/O软件、用户空间的I/O软件

缓冲技术

CPU与设备间速度不匹配

单缓冲

设备—T时间→缓冲区—M时间→用户区—C时间→进程

max(C, T)＋M，通常M远小于C和T

双缓冲

交替使用两个缓冲区，一个满时转到另一个，然后满的这个输出

若C<T，一块数据的处理时间为T，可连续工作

若C>T，传输和处理时间为M+C，不用等待I/O操作

多缓冲

循环缓冲

驱动调度技术

存储设备的物理结构

顺序存取存储设备

e.g.磁带

严格依赖物理位置

随机存取存储设备

存取一个信息的时间几乎不依赖于其位置

磁盘是这种结构

磁盘结构

多个盘面，每个盘面有一个读写磁头，所有的读写磁头固定在唯一的移动臂上

一个盘面上读写磁头的轨迹称为磁道，所有磁道组成的圆柱称为柱面

一个磁道可划分为多个扇区

1. 移动臂横向移动至柱面号（“查找时间”，耗时较多）
2. 选择磁头号，等待指定扇区（扇区号）转到读写磁头下（“搜索延迟”）

越往里柱面号越大

容量与磁头数有关，但速度无关（多盘磁盘一次只能读写一个盘）

优化分布

读取需要处理时间，这段时间内磁盘还在转

搜查定位

FCFS

最短查找时间优先算法

总是执行查找时间最短的请求

扫描算法

移动臂不断扫描，遇到就服务

分步扫描

避免停在一个柱面，将其分为N个FIFO队列，对每个队列首采用扫描

电梯调度

LOOK算法，无请求就不动，有就按电梯的模式（每次找当前移动方向上与当前最近的）

循环扫描

从0到最大后直接返回0，无视中途的

提高磁盘的I/O速度

提前读：提前把下一块也读到缓冲区

延迟写：等申请到这块时再写

异步写：写进程无需等待写盘结束

Linux的I/O调度算法

电梯、时限和预期、公平排队

最后修改于2020/8/17