保持多个工作在内存中并且在各个工作之间复用CPU，由顺序执行变成了多道程序的交替执行
多道系统只是为了让CPU一直处于工作状态，当目前程序出现I/O请求即暂时不再使用CPU时，CPU才去运行另一道程序。多道批处理系统的目的是为了解决人机矛盾及CPU和I/O设备速度不匹配的矛盾，提高系统的有效性（包括资源利用率和吞吐量），并不提供人机交互能力。
定时中断用于工作对CPU的复用
程序运行公平性更好，提高短作业的速度
分时系统是实现人机交互的系统。
个人计算机：每个用户一个系统
分布式计算机：每个用户多个系统
计算机系统的演变
MS-DOS
在最小的空间，设计用于提供大部分功能（1981-1994）
UNIX操作系统与C语言
ucore也是分层结构，本课程涉及到的部分（红线部分）
分层结构层次越来越复杂，会导致效率的下降
尽可能把内核功能移到用户空间
用户模块间的通信使用消息传递
好处：灵活安全
缺点：性能下降
让内核分配机器的物理资源给多个应用程序，并让每个程序决定如何处理这些资源。
（原来操作系统的功能是由用户态的函数库来提供）
程序能链接到操作系统库（libOS）实现操作系统抽象
保护与控制分离
负责把真实的硬件虚拟成若干个虚拟的硬件，虚拟机管理器决定每个虚拟机可以使用哪些硬件资源
启动时计算机内存和磁盘布局
ROM只读存储
实模式只有20位，地址空间为1mb
加载程序的内存地址空间
BIOS系统调用
BIOS以中断调用的方式，提供了基本的I/O功能
只能在x86的实模式下访问
CPU初始化
BIOS初始化
主引导记录MBR格式
为了解决多分区启动问题，选择其中一个分区启动
最多四个分区
分区引导扇区格式
加载程序（BootLoader）
BIOS
UEFI
统一可扩展固定接口
可信度检查
为什么需要中断、异常和系统调用？
中断和异常希望解决的问题
系统调用希望解决的问题
内核的进入与退出
系统调用（systemrecall）
异常（exception）
中断（hardwareinterrupt）
源头
响应方式
处理机制
这里的中断是指三种形式的总称
硬件处理
内核软件
硬件中断服务例程可被打断
异常服务例程可被打断
异常服务例程可嵌套
系统调用的实现
函数调用和系统调用的不同之处
开销大于函数调用
中断、异常和系统调用开销
ucore中库函数read()的功能是读文件
库函数read()的参数和返回值
库函数read()使用示例
read函数实现
内存管理方式
实现高度依赖硬件
物理地址空间——硬件支持的地址空间
逻辑地址空间——在CPU运行的进程看到的地址
编译->汇编->链接->程序加载（重定位）
地址生成时机和限制
给进程分配一块不小于指定大小的连续的物理内存区域（重定位）
空闲内存不能被利用
外部碎片：分配单元之间的未被使用内存
内部碎片：分配单元内部的未被使用内存，取决于分配单元大小是否要取整
动态分区分配
操作系统需要维护的数据结构
找到第一个满足的就行
原理&实现
优点
缺点
遍历一个最佳的
找到最大空闲空间
通过调整进程占用的分区位置来减少或避免分区碎片
碎片紧凑（compaction）
分区对换（swapin/out）
通过抢占并回收处于等待状态进程的分区，以增大可用内存空间
需要解决的问题？
开销大
buddysystem
整个可分配的分区大小为\(2^u\)，需要的分区大小\(s\)
数据结构
分配过程
释放过程
合并条件
用于做内核的分配
例子
提高内存利用效率和管理灵活性
需要解决的问题
进程的段地址空间由多个段组成
段式存储的目的：更细粒度和灵活的分离与共享
段内需要连续，段之间不连续
段的概念
段访问
逻辑地址由二元组(s,addr)表示
段访问的硬件实现
页帧（帧、物理页面，Frame，PageFrame）
计算实例
页面（页、逻辑页面，Page）
页面到页帧
转换过程
页表转换实例
性能问题
translationlook-asideBuffer
缓存近期访问的页表项
通过间接引用将页号分成k级
实例
减少页表存储空间
大地址空间（64-bits）系统，多级页表变得繁琐
页寄存器和反置页面的思路
页寄存器
pageregisters
物理帧直接与页寄存器关联
每个物理帧与一个页寄存器（pageregister）关联，寄存器内容包括：
页寄存器示例
页寄存器中的地址转换
用快表缓存页表项后的页寄存器搜索步骤
快表的限制
反置页表
所有的进程共同使用一张页表，这张页表中的条目的数量和内存中物理的页框的数量是一样的。
反置页表中每个条目拥有以下字段：
基于Hash映射值查找对应页表项中的帧号
段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到存储方面有优势
在段式存储管理基础上，给每个段加一级页表
通过指向相同的页表基地址，实现进程间的段共享
程序规模的增长速度远远大于存储器容量的增长速度
理想的存储器
实际存储器
存储抽象
计算机系统时常出现内存空间不够用
虚拟存储技术的目标
只把部分程序放到内存中，从而运行比物理内存大的程序
实现进程在内存与外存之间的交换，从而获取更多的空闲内存空间
在较小的可用内存中运行较大的程序
依据程序逻辑结构，将程序划分为若干功能相对独立的模块，将不会同时执行的模块共享同一块内存区域。
示例
增加正在运行或需要运行的程序的内存
覆盖
交换
principleoflocality
程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域
将不常用的部分内存块暂存到外存
原理
实现方式
基本特征
支持技术
在页式存储管理的基础上，增加请求调页和页面置换
思路
虚拟页式存储中的地址转换
页表项结构
虚拟页式存储示例
X86页表结构
处理流程
外存管理
虚拟页式存储管理的性能
当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面
设计目标
页面锁定（framelocking）
评价方法
分类
算法实现
算法特征
算法示例
First-In,First-out,FIFO
特征
LeastRecentlyUsed,LRU
算法思路
LRU算法的可能实现方法
页面链表
活动页面栈
Clock
仅对页面的访问情况进行大致统计
算法
算法是LRU和FIFO的折中
改进的Clock算法
减少修改页的缺页处理开销
LFULeastFrequentlyUsed
缺页时，置换访问次数最少的页面
LRU和LFU区别
采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象
原因
思考
哪些算法没有此现象？
FIFO有，LRU没有此现象
FIFO算法示例
三个页，缺页次数9
四个页，缺页次数10
LRU算法和FIFO本质上都是先进先出的思路
LRU可退化成FIFO
LRU算法性能好，但系统开销较大
FIFO算法系统开销较小，会发生Belady现象
Clock算法是它们的折中
对于未被访问的页面，Clock和LRU算法的表现以一样好
对于被访问过的页面，Clock算法不能记录准确访问顺序，而LRU可以
给进程分配可变数目的物理页面
CPU利用率与并发进程数的关系
CPU利用率与并发进程存在相互促进与制约的关系
工作集
一个进程当前正在使用的逻辑页面集合，可表示位二元函数\(W(t,\Delta)\)
工作集的变化
常驻集
在当前时刻，进程实际驻留在内存当中的页面集合
工作集与常驻集的关系
缺页率与常驻集的关系
窗口大小x
实现方法
PFF，Page-Fault-Frequency
缺页率（pagefaultrate）
通过调节常驻集大小，使每个进程的缺页率保持一个合理的范围内
缺页率置换算法示例
窗口大小为2
抖动问题（thrashing）
产生抖动的原因
操作系统需在并发水平和缺页率之间达到一个平衡
负载控制
通过调节并发进程数（MPL）来进行系统负载控制
进程是指一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程
进程包含了正在运行的一个程序的所有状态信息
进程与程序的联系
进程与程序的区别
PCB，ProcessControlBlock
操作系统管理控制进程运行所用的信息集合
使用流程
进程控制信息
进程控制块的组织
链表
同一状态的进程其PCB成一链表，多个状态对应多个不同的链表
索引表
同一状态的进程归入一个索引表（由索引指向PCB）
多个状态对应多个不同的索引表
进程的生命周期划分
处于挂起状态的进程映像在磁盘上，目的是减少进程占用内存
在外存时的状态转换
单进程播放
多进程实现
解决思路
在进程内部增加一类实体，满足以下特性：
这种实体就是线程（Thread）
线程是进程的一部分，描述指令流执行状态。它是进程中的指令执行流的最小单元，是CPU调度的基本单位。
线程的处理机调度角色：线程描述在进程资源环境中的指令流执行状态
进程和线程的关系
线程=进程-共享资源
线程的优点
线程的缺点
不同操作系统对线程的支持
路由器就是单进程多线程系统
线程的三种实现方式
概念
由一组用户级的线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度等。
不足
进程由内核通过系统调用实现的线程机制，由内核完成线程的创建、终止和管理。
内核支持的用户线程。一个进程可有一个或多个轻量级进程，每个轻权进程由一个单独的内核线程来支持。
用户线程和内核线程的对应关系
（进程切换）上下文切换
进程切换的要求
进程生命周期的信息
进程控制块PCB：内核的进程状态记录
Windows进程创建API：CreateProcess（filename）
Unix进程创建系统调用：fork/exec
fork的地址空间复制
fork使用示例
代码
程序加载和执行系统调用exec()
wait()系统调用用于父进程等待子进程的结束
wait()系统调用的功能
程序的有序终止exit()
CPU资源的时分复用
调度时机
调度策略
确定如何从就绪队列中选择下一个执行进程
调度策略要解决的问题
调度算法
处理机资源的使用模式
吞吐量与延迟
处理机调度策略的吞吐量目标
处理机调度策略的公平性目标
FCFS：FirstComeFirstServed
依据进程进入就绪状态的先后顺序排列
先来先服务算法的特征
SPN
HRRN
选择就绪队列中响应比R值最高的进程
RR，Round-Robin
MQ
MLFQ
FSS，FairShareScheduling
FSS控制用户对系统资源的访问
实时操作系统的定义
实时操作系统的性能指标
实时操作系统的特性
实时任务
周期实时任务
一系列相似的任务
硬时限和软时限
可调度性
可调度表示一个实时操作系统能够满足任务时限要求
（RM，RateMonotonic）
（EDF，EarilestDeadlineFirst）
对称多处理器（SMP，Symmetricmultiprocessing）调度
对称多处理器的进程分配
priorityinversion
例如：有优先级为A、B和C三个任务，优先级A>B>C，任务A，B处于挂起状态，等待某一事件发生，任务C正在运行，此时任务C开始使用某一共享资源S。在使用中，任务A等待事件到来，任务A转为就绪态，因为它比任务C优先级高，所以立即执行。当任务A要使用共享资源S时，由于其正在被任务C使用，因此任务A被挂起，任务C开始运行。如果此时任务B等待事件到来，则任务B转为就绪态。由于任务B优先级比任务C高，因此任务B开始运行，直到其运行完毕，任务C才开始运行。直到任务C释放共享资源S后，任务A才得以执行。在这种情况下，优先级发生了翻转，任务B先于任务A运行。
PriorityInheritance
占用资源的低优先级进程继承申请资源的高优先级进程的优先级
priorityceilingprotocol
占有资源进程的优先级和所有可能申请该资源的进程的最高优先级相同
独立进程：不和其他进程共享资源或状态
并发进程：在多个进程间有资源共享
并发进程的正确性
进程并发执行的好处
进程需要与计算机中的其他进程和设备进行协作
可能导致的错误
AtomicOperation
原子操作是一次不存在任何中断或失败的操作
操作系统利用同步机制在并发执行的同时，保证一些操作是原子操作
操作系统和现实生活的问题类比
例如：家庭采购协调
如何保证家庭协调的成功和高效
方案一
分析
面包还是买多了
方案二
先留便签，后检查面包和便签
会导致不会有人买面包
方案三
为便签增加标识，以区别不同人的便签
还是会导致有人不买
方案四
两个人采用不同的处理流程
方案五
利用两个原子操作实现一个锁（lock）
进程的交互关系：相互感知程度
临界区（CriticalSection）：进程中访问临界资源的一段需要互斥执行的代码
进入区（entrysection）：
退出区（exitsection）：
剩余区（remaindersection）
不同的临界区实现机制的比较
第一次尝试
满足“忙则等待”，但是有时不满足“空闲则入”
第二次尝试
不满足忙则等待
第三次尝试
满足忙则等待，不满足空闲则入
Eisenberg和McGuire
硬件提供了一些同步原语
操作系统提供更高级的变成抽象来简化进程同步
锁是一个抽象数据结构
使用锁来控制临界区访问
现代CPU体系结构都提供一些特殊的原子操作指令
使用TS指令实现自旋锁（spinlock）
无忙等待锁
schedule()放弃占用CPU，让CPU调度其他进程
wakeup(t)唤醒线程，占用资源
原子操作指令锁的特征
并发问题
同步概念
确保同步正确的方法
基本同步方法
semaphore：信号量
信号量是操作系统提供的一种协调共享资源访问的方法
由Dijkstra在20世纪60年代提出，早期的操作系统的主要同步机制
信号是一种抽象的数据类型
信号量与铁路的类比
信号量是被保护的整数变量
P()可能阻塞，V()不会阻塞
通常假定信号量是“公平的”
自旋锁不能实现先进先出
信号量分类
信号量的使用
有界缓冲区的生产者-消费者问题描述
问题分析
用信号量描述每个约束
PV操作不能调换，检查缓冲区是否有空地和占有缓冲区的操作不能调换
因为一旦先占有缓冲区，那就无法释放缓冲区，导致死锁现象
阻塞不代表会释放资源，资源的释放是通过对变量的加减来进行的。
使用信号量的困难
Moniter
管程是一种多线程互斥访问共享资源的程序结构
管程的使用
条件变量（ConditionVariable）
wait操作中会释放对资源的占用，进程返回回来之后还会再次占据lock
因为wait会释放对资源的占用，所以检查缓冲区和资源的占用的顺序可用调换，不会造成死锁的现象
Hansen管程：主要用于真实OS、Java中
Hoare管程：主要见于教材中
问题描述：
问题描述
用信号量解决读者-写者问题
用管程解决读者-写者问题
写者优先
判断AW+WW是因为采用了Hansen管程，在返回途中可能被写操作抢先了
由于竞争资源或通信关系，两个或更多线程在执行中出现，永远相互等待只能由其他进程引发的事件
死锁示例
进程访问资源的流程
资源分类
资源分配图
描述资源和进程间的分配和占用关系的有向图
出现死锁的必要条件
死锁预防（DeadlockPrevention）
死锁避免（DeadlockAvoidance）
死锁检测和恢复（DeadlockDetection&Recover）
由应用进程处理死锁
限制申请方式
预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。
利用额外的先验信息，在分配资源时判断是否会出现死锁，只在不会死锁时分配资源
系统资源分配的安全状态
安全状态与死锁的关系
银行家算法是一个避免死锁产生的算法。以银行借贷分配策略为基础，判断并保证系统处于安全状态
n=线程数量，m=资源类型数量
安全状态判断算法
当前的剩余资源是否可以满足其中一个线程的未来需要
遍历完成实际是找到一个安全序列
银行家算法
判断示例
不安全的
检测算法
检测示例
算法使用
死锁恢复：进程终止
死锁恢复：资源抢占
IPC，Inter-ProcessCommunication
通信方式
同步与异步通信
阻塞通信
非阻塞通信
缓冲方式
信号的定义
进程间的软件中断通知和处理机制
信号的接收处理
信号的实现
使用示例
进程间基于内存文件的通信机制
进程不知道（或不关心）的另一端
管道示例
消息队列是由操作系统维护的以字节序列为基本单位的间接通信机制
消息队列的系统调用
共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制
进程
线程
共享内存系统调用
文件系统是操作系统中管理持久性数据的子系统，提供数据存储和访问功能。
文件是具有符号名，由字节序列构成的数据项集合
文件系统的功能
文件属性
文件头：文件系统元数据中的文件信息
文件访问模式
内核跟踪进程打开的所有文件
操作系统在打开文件表中维护的打开文件状态和信息
文件的用户视图和系统视图
文件的用户视图
系统访问接口
操作系统的文件视图
用户视图到系统视图的转换
进程读文件
进程写文件
文件系统中的基本操作单位是数据块
访问模式
索引文件示例
文件内部结构
文件共享和访问控制
语义一致性
目录操作
典型目录操作
操作系统应该只允许内核修改目录
目录实现
文件别名
两个或多个文件名关联同一个文件
硬链接：多个文件项指向一个文件
软链接：以”快捷方式“指向其他文件
若删除文件，硬链接的文件还是会在，软链接的文件就不在了