操作系统引论

计算机系统（紧挨着硬件的软件）

硬件：CPU、内存、外存等
软件：系统软件（主要是操作系统）、支撑软件、应用软件

操作系统分类：

单道批处理程序
多道程序设计技术
分时系统
实时系统
多处理机系统
- 单用户单任务 – MSDOS
- 单用户多任务 – Windows
- 多用户多任务 – Unix、Linux
网路系统
分布式系统
嵌入式系统

系统资源使用特性

资源共享&资源竞争

操作系统的定义

操作系统是一个大型的程序系统，它负责计算机系统软、硬件资源的分配；控制和协调并发活动；提供用户接口，使用户获得良好的工作环境。

操作系统功能

资源管理
- 进程管理：进程和线程的管理和调度
- 存储管理：对内存进行分配、保护、扩充及地址映射
- 设备管理：接收用户程序的I/O请求，分配设备，启动设备
- 文件管理：文件的存取、信息的共享与保护、文件存储空间管理
用户接口
- 命令接口（CLI）：普通用户与os的接口
- 图形接口（GUI）
- 程序接口（系统功能调用）（API）：应用程序与os的接口，在应用程序中使用系统调用，带有一定功能号的 “访管指令”

操作系统的特征

并发：OS重要特征，宏观上同时发生，微观交替进行
共享：系统内资源多个并发执行的进程共同使用
异步：竞争资源导致进程不可预知
虚拟：一个物理实体变为若干个逻辑对应物

处理机的特权级

目的：保护操作系统

管态&目态：

管态（系统态、核心态）：操作系统执行时机器所处的状态，又称处理机的特权级。
- 处理机可使用全部指令(包括一组特权指令)
- 使用全部系统资源(包括整个存储区域)
目态(用户态)：用户程序执行时机器所处的状态。
- 禁止使用特权指令
- 不能直接取用资源与改变机器状态
- 只允许用户程序访问自己的存储区域。
  转换：访管中断

中断

中断: 打断当前程序，去做更紧急，更重要的事
中断处理方式：

保存现场
确定中断源
转入中断服务程序（ISP）
处理中断
恢复现场
继续执行原程序

中断分类：
（1）按中断功能分类

（2）按中断方式分类

（3）按中断来源分类

进程管理

进程概述

一个程序的一次运行过程
定义：可并发执行的程序在一个数据集合上的一次运行过程，是系统进行资源分配和调度的一个独立单位

特征：

动态性：进程最基本的特征
并发性：程序在建立进程后并发运行
独立性：是系统进行资源分配和调度的独立单位
异步性：进程以不可预知的速度向前推进

程序 VS 进程：

从定义上看，进程是程序处理数据的过程，而程序是一组指令的有序集合
进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性
从进程结构特性上看，它包含程序、数据（栈）和PCB
进程和程序并非一一对应：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可执行多个程序

进程的状态及变迁

进程状态：

就绪状态：进程分配到资源，等待CPU执行
运行状态：分配到CPU，在CPU上执行
阻塞状态：正在执行的进程由于等待某事件而暂时无法继续执行

变迁：

例题：

变迁4的发生会引起变迁3的发生
变迁4表示当前运行进程的时间片用完了 -> 就绪
操作系统需要从就绪队列中调度一个进程运行，于是发生变迁3（就绪 -> 运行）来选出下一个进程

进程控制

进程创建

1	create(name,priority)

创建一个新进程，建立进程的PCB结构并为其分配资源

进程撤销

kill(Pid)

回收进程资源

进程阻塞与唤醒

阻塞：

sleep()

唤醒：

wakeup()

Linux进程管理

task_struct //进程描述符
do_fork()  //进程创建
执行exec()系列函数
do_exit()  //进程终止
do_wait()  //等待子进程结束
wait_event*()  //进程睡眠
wake_up()  //进程唤醒

task_struct()
进程调度：

prio  //进程的动态优先级，取值范围[0,139]
static_prio  //进程的静态优先级，取值范围[0,139]
normal_prio  //常规动态优先级
rt_priority //实时进程优先级，取值范围[0,99]
run_list  //记录进程在就绪队列中的位置
sched_class  //进程所采用的调度器类

地址空间及文件系统信息：

mm  //进程用户地址空间描述符
active_mm  //指向进程最近最常使用的地址空间
fs  //表示进程与文件系统的联系
files  //记录进程当前打开的文件
stack  //指向进程内核栈的指针

进程创建
接口：

1
2

fork()  //创建一个子进程，父子进程拥有各自独立的地址空间（写时复制），父子进程并发执行
vfork()  //创建一个子进程，父子进程共享地址空间，子进程先执行，父进程阻塞

写时复制：若父子进程内容一致则以只读方式共享同一份拷贝，若其中一方需要有其他自己的写入时，父子进程拥有自己真正的拷贝

实现函数：
do_fork(): 负责处理系统调用传入的参数，调用copy_process()创建新进程，然后将新进程设置为可调度状态并返回子进程PID
copy_process(): 创建新进程时负责复制父进程的各项资源和状态，生成新的task_struct()

Exec
execl() execle() execlp() execv() execvp()
执行成功则覆盖调用进程的程序空间，子进程会被覆盖

1	exec(文件名，参数表，环境变量表)

进程终止
exec()
wait()系统调用
让父进程阻塞，直到某个子进程终止，并回收该子进程的资源

1	pid_t wait(int *status)

status: 获取子进程的退出状态（成功返回PID，失败返回-1）

进程睡眠
两种阻塞状态
TASK_UNINTERRUPTIBLE（不可中断睡眠）
TASK_INTERRUPTIBLE（可中断睡眠）

wait_event*()系列函数会在进程不满足时进入睡眠状态，直到条件成立或被唤醒

进程唤醒
wake_up()

进程同步

进程互斥：多个进程访问共享资源时，只能一个进程进入临界区

进程同步：并发进程在一些关键点上可能需要互相等待或互通消息

解决互斥问题

禁止中断（只能用于单处理机）
利用TSL指令实现互斥：检测并上锁
利用swap指令实现互斥：交换两个变量的值
Peterson算法（只适用于两个进程）
turn表示轮到谁进入临界区
面包店算法
锁机制
信号量机制
- 整型信号量机制
- 记录型
- 信号量集机制：一次可申请多类资源，每类可申请多个

进程调度

高级（作业调度）：外存调度到内存，决定谁调入内存
低级（进程调度）：选择一个进程放进CPU，选择谁调用CPU
中级（对换）：控制内存资源、系统压力缓解

功能：CPU调度+CPU切换

方式：

抢占：重新分配CPU给其他进程运行
- 时间片原则
- 优先权原则
- 还需要运行的时间
非抢占：占用CPU直到该进程终止或等待

周转时间/带权周转时间：
周转时间：从作业进入系统时到作业全部运行完出系统的时间
带权周转时间：作业的周转时间与执行时间之比

栗子：

进程调度算法：

先来先服务（FCFS）
周转时间 = 完成时间 - 提交时间
带权周转时间 = 周转时间 / 执行时间
短作业优先（SJF）
- 非抢占式（按估计运行时间）
  
  A先到达提交时间，所以先A，后面看执行时间最短的（题目只会给前两列）
- 抢占式
  - 按估计运行时间抢占
  - 按剩余运行时间抢占（谁更短谁先执行）
高响应比优先调度算法（HRRF）

执行完后算响应比高的
优先级
动态改变思路：
进程使用CPU超过一定数值时，降低优先级
进程I/O操作后，增加优先级
进程等待时间超过一定数值时，提高优先级

栗子：
先按优先级，相同则看谁先进入谁先

时间片轮转调度算法（交互型）

栗子：
Linux公平调度算法（CFS）
谁用CPU的时间少谁先
通过进程的weight来决定时间片分配，权重越大获得CPU的时间越多
时间片占比 = 这个进程的权重/所有进程总权重

进程通信

共享存储器系统通信
开拓一片共享区域进行通信
消息传递系统通信
- 直接通信：send()/receive()
- 间接通信：利用共享信箱作为中间实体实现信息交换
管道通信
管道：用于连接发送进程和接收进程以实现他们通信的共享文件
fd[1] -> 写入
fd[0] -> 读取
单向通信
套接字通信

死锁

定义：每个进程都在等待被其他进程占有的资源，且该资源不会被释放
产生原因:

竞争资源
请求和释放资源的时机不当

产生死锁的必要条件

互斥
请求和保持
不剥夺
环路等待
有一个不满足就不会死锁

处理死锁

预防死锁

破坏占有且等待条件
- 静态分配资源：一次性把所有资源都分好，避免中途再申请；
- 要求在没有资源时才可申请资源
破坏不可剥夺条件
破坏循环等待条件

避免死锁

安全状态

能否找到一个合适的顺序使系统无法构成死锁

银行家算法

若分配后处于安全状态则真分配

变量	含义
Max[1..n,1..m]	每个进程最多有多少资源
Allocation[1..n,1..m]	当前分配给进程的资源数
Need[1..n,1..m]	每个进程还需要多少(Need = Max - Allocation)
Available[m]	系统当前可用资源数
Request[m]	某进程提出的资源请求向量
Finish[1..n]	系统是否有足够资源分配给进程
work[m]	系统可提供给进程继续运行所需的各类资源数目

栗子：

（1）

（2）

（3）

（4）

死锁检测

资源分配图：

死锁解除

剥夺：强行抢回资源
撤销：终止某些进程，释放它的资源

进程 & 线程

进程：

系统拥有资源的独立单位
独立调度和分派的基本单位

进程 VS 线程

线程状态：

线程实现机制：

用户级线程（ULT）：线程管理完全由用户程序（线程库）实现，操作系统不知道线程的存在1
内核级线程（KLT）：每个线程都有操作系统内核来管理，线程调度、创建、销毁都靠内核
组合方式

资源管理功能，分配方式（静态和动态），虚拟资源

资源管理功能

处理器管理、内存管理、设备管理、文件管理、网络资源管理

分配方式

静态：程序运行之前或刚运行就一次性把需要的资源都分配好，执行过程中不再更改
动态：根据实际需要随时申请和释放

虚拟资源

让多个程序互不干扰、灵活共享

存储器管理

存储器的层次体系结构

存储器管理功能

地址映射

逻辑地址 -> 物理地址

	静态地址映射	动态地址映射
映射时间	程序运行前完成	不可变
是否可变	程序运行时完成	可变
特点	逻辑地址 = 物理地址偏移量	映射关系由操作系统+硬件动态决定

主存分配

存储保护

界地址保护
- 上下寄存器保护（下界寄存器<= 物理地址 <=上界寄存器）
存储键保护
- 把主存分为若干存储块，每块分配一个存储键，程序运行时有访问键，只有匹配的程序才可访问对应内存

主存扩充

原因：主存容量不够
可行性：局部性特征（时间局部性、空间局部性）
实现方法（虚拟存储）：
（1）程序的全部代码和数据存放在辅存中
（2）程序当前执行所涉及的那部分程序代码放入主存中
（3）程序执行时，当所需信息不在主存，由操作系统和硬件配合来从辅存中调入信息，程序继续执行。

虚拟存储器

存储器管理方式分类

大小不等
- 分区
- 分段
大小相等
- 分页
段页式存储
虚拟存储器

动态分区分配

分配过程

找到一块空闲块
若大小相等，则直接摘除；比要求大小大，则一部分分出去剩下为空闲
否则不能满足要求

放置策略&特点

首次适应算法
依次
地址开始优先
最佳适应算法
优先分配小空闲区，即存储空间递增
最坏适应算法
优先分配大空闲区，即存储空间递减

栗子：

分区回收算法

相邻则合并
不相邻则创建新节点

碎片问题及拼接技术

存在太小的空闲区，利用拼接技术将其拼接为大空闲区

页式存储管理

页面：将进程逻辑空间分为若干等长区域
页面大小是2的幂
缺页中断：进程访问的页面不在内存中（未被加载进内存时）

逻辑地址结构

页表（页号 - 页框号的映射关系）

页框：把内存分成了不同的块
块号就是页框号

地址变换机构

进程（逻辑地址） -> 内存（物理地址）

快表的地址变换机构

若快表未命中，则查页表

多级页表

原理：分层查找

例题

1 2	逻辑地址 = 页号 + 页内偏移量物理地址 = 物理页框号*页面大小 + 页内偏移量

分段存储管理方式

物理地址 = 段基址 + 偏移量

段式地址变换机构

段表寄存器：存放段表的起始地址和段表长度
越界检查
- 逻辑地址的段号与段表长度比较
- 段内地址与段表中保存的段长比较

分段 VS 分页

例题

越界检查
需为RW / E

（2）存取控制不符合
（3）段内地址超出段长，越界中断

段页式存储管理方式

先分段后分页

地址转换机构

虚拟存储器

请求调入功能和置换功能，利用外存空间从逻辑上扩充内存容量

请求分页存储管理方式

页面置换算法：

FIFO（先进先出）
先淘汰最先进入系统驻留主存时间最长的页
OPT（最佳置换算法）
找之后未出现的页面或离得最远的页面置换
LRU（最近最久未使用置换算法）
向前看留存时间最久的out
Clock算法
- 页面被访问是为1
- 淘汰页面时若为0则换出，为1则变0，继续检查下一个页面
- 换入新页面后，页面的访问位置为1，指针指向下一个页面

例题：
FIFO
OPT
LRU
Clock算法

抖动

刚刚换出的页面又要换入主存刚刚换入的页面又要换出主存（频繁的页面调度行为）
全局置换策略

预防

采取局部置换策略
引入工作集概念
挂起若干进程，降低多道程序度

设备管理

I/O设备分类

块设备：以数据块为单位来传送数据的设备
- 磁盘
字符设备：以单个字符为单位来传送信息的设备
- 终端、打印机
网络设备

I/O通道：设备与内存直接进行数据交换

I/O系统结构
总线型：

通道型：

I/O控制方式

程序I/O方式

中断驱动I/O控制方式

直接存储器访问（DMA）

基本单位是数据块
在设备和内存之间直接进行
在DMA控制器的控制下完成

I/O通道控制方式

CPU对I/O干预更小

缓冲管理

缓和CPU与I/O设备间速度不匹配的矛盾

单缓冲

处理一块数据平均用时Max(T,C)+M

双缓冲

处理一块数据平均用时Max(T,C+M)

循环缓冲区

多个大小相等的缓冲区链接成一个循环队列

缓冲池

I/O软件

层次：

设备独立性

用户程序独立于具体物理设备的一种特性

提高设备分配的灵活性
容易实现I/O重定向

SPOOLing技术

需要多道程序技术支持
定义：SPOOLing（假脱机）技术是操作系统中一种输入/输出管理技术，通过磁盘等中间存储设备，实现对慢速外设（如打印机）I/O 操作的缓冲和排队，从而实现 I/O 与 CPU 的异步执行和资源共享。

优点：

提高资源利用率（CPU 不再空等 I/O）
支持多用户共享外设（如多个用户共享一个打印机）
实现 I/O 并发（多个 I/O 设备任务异步执行）
提供作业排队/管理能力

共享打印机

看似共享，实则交替

文件管理

文件分类

普通文件
目录文件
设备文件
Linux中查看

文件物理结构

连续文件

适用于顺序存取、随机存取且文件不经常修改
将文件中的信息顺序地存放到一组相邻地磁盘块中

链接文件

适用于顺序访问、经常性修改

隐式链接
显式链接

索引文件

顺序or随机

单级索引
多级索引
混合索引（Unix、Linux）
0~9 -> 存直接数据块

更适合存放在磁盘上
磁带更适合顺序文件

文件存取

顺序存取
随机存取

目录管理

要求

“按名存取”
提高目录检索速度
允许文件重名
允许文件共享

定义

一组文件控制块地有序集合

FCB内容

（1）基本信息
（2）存取控制信息
（3）使用信息
eg. Windows98(FAT32)包含基本目录项和长文件目录项

索引节点引入原因

磁盘索引节点
内存索引节点
栗子：

未引入索引节点前（FCB直接存在目录项中）：
求块数 –> （FCB字节数*文件数）/块大小

引入索引节点后（目录项只保存文件名+索引节点号）：
求块数 –> (文件名大小+索引编号大小)*文件数/块大小

栗2：

目录结构

单级

需要检索整张表

两级

允许文件重名
不同用户可以使用不同的文件名来访问系统中的同一个共享文件

树级

绝对路径&相对路径

文件存储空间管理

空闲表法

空闲链表法

空闲盘块链：

空闲盘区链：

位示图法

成组链接法：Unix

从第2组开始讲每组的总块数及相应的块号存在前一组最末块中

文件共享

共享索引节点法

硬链接

1 2	ln 共享文件名新文件名 ln /C/C2/C21 /B/B2/B21

符号链接法

软链接（多个文件名指向同一个文件内容）

1 2	ln -s 共享文件名新文件名 ln -s /C/C2/C21 /B/B2/B21

对比

对比点	符号链接（软链接）	共享索引节点（硬链接）
是否是独立文件	是，内容是路径	否，是另一个目录项
删除原文件后	链接失效（悬挂）	仍然存在且可用
是否可跨文件系统	可以	不可以
是否可链接目录	可以（需特殊权限）	不可以（一般限制）
inode 是否相同	不同	相同
使用场景	快捷方式、跨系统引用等	多文件名共享同一文件数据

磁盘存储器管理

磁头 -> 磁道 -> 扇区

扇区编址方式

CHS（柱面/磁头/扇区）
LBA（相对扇区号）

存储容量 = 磁头数 * 磁道数 * 每道扇区数 * 每扇区字节数

磁盘调度算法

移臂调度算法：

FCFS（先来先服务）
SSTF（最短寻道时间优先算法）
SCAN（扫描算法）(电梯算法)
由当前磁头移动方向决定
C-SCAN（循环扫描算法）
单向循环
到最开始选择的方向的头后，从另一个方向选择与现在同方向的继续循环，上述例题中376之后选择4
N-Step-SCAN（N步扫描算法）
FSCAN

旋转调度算法

大题计算

信号量

互斥 = 1
同步 = 0

页

逻辑地址 = 页号 + 页内偏移量
物理地址 = 物理页框号*页面大小 + 页内偏移量

页表

一页可存页表项 = 每页大小/页表项大小
页表项位数 = 每级页表表示的几位页号

索引

引入原因：提高文件管理的效率和灵活性

块数 = 容量max/块大小
索引表项 = 块数位数的字节
索引表项数= 索引表区/索引表项
可支持单个文件最大长度 = 索引表项数*磁盘块大小

未引入索引节点前（FCB直接存在目录项中）
求块数 -> (FCB字节数*文件数)/块大小

引入索引节点后（目录项只保存文件名 + 索引节点）
求块数 -> （文件名大小 + 索引编号大小）*文件数/块大小

2^x -> 块号 x -> 索引表需要的位数

FAT

FAT大小 = 盘块数*每块表项位数
位示图大小 = 盘块数/8