1.引论
- OS的目标：方便性、有效性、可扩充性
- OS的作用：作为用户与计算机硬件系统之间的接口，作为计算机系统资源的管理者
-
发展过程
- 单道批处理系统：一次只调入一个作业到内存中运行，资源利用率低
- 多道批处理系统：多个作业同时在主存中运行，资源利用率高
- 分时系统：一台计算机连接多个终端，人机交互、共享主机
- 实时系统：及时响应外部事件的请求
- 基本特征：并发、共享、虚拟、异步
- OS的结构：无结构操作系统 - 模块化结构OS - 分层式结构OS
2.进程管理
1.基本概念
- 程序的顺序执行：顺序性、封闭性、可再现性
- 程序的并发执行：间断性、失去封闭性、不可再现性
- 进程：是进程实体的运行过程，是系统进行资源分配和调度的独立单位
- 进程实体：程序段 + 数据段 + PCB
- 创建、撤销进程的实质就是创建、撤销 PCB
PCB中的信息：
（1）进程标识符 （2）处理机状态 （3）进程调度信息 （4）进程控制信息
PCB的组织方式：
（1）线性方式 （2）链接方式 （3）索引方式
2.进程控制
3.进程同步
- 进程同步的原则：空闲让进、忙则等待、有限等待、让权等待
- 生产者-消费者问题：
要先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能会引起死锁
单生产者单消费者、多缓冲：不能简化
多生产者多消费者、单缓冲：去掉mutex
单生产者单消费者、单缓冲：去掉mutex
缓冲区无限大：去掉empty信号量
允许生产者写时，消费者可读：为生产者和消费者各设置一个mutex - 读者-写者问题：
4.进程通信
- 共享存储器系统
- 管道通信系统
- 消息传递系统
3.处理机调度和死锁
高级调度（作业调度）：后备队列（外存）→ 就绪队列（内存）
低级调度（进程调度）：就绪队列（内存）→ CPU
中级调度（内存调度）：就绪队列（内存）\leftrightarrow 挂起队列（外存）
进程调度算法：
（1）先来先服务算法（FCFS）
（2）短进程优先调度算法(SJF)
（3）优先权优先调度算法(FPF)
（4）高响应比优先调度算法：既考虑作业的等待时间，又考虑了作业的运行时间，实现了动态优先级
（5）轮转调度算法（RR）
（6）多级反馈队列调度算法（MFQ）
实时调度算法：
（1）最早截止时间优先调度算法(EDF)
（2）最低松弛度优先调度算法(LLF)： 任务紧急程度越高，优先级越高
优先级倒置：
当低优先级进程阻塞高优先级进程，让低优先级进程继承被它被阻塞进程的优先级
死锁的产生：
可抢占性资源不会引起死锁，例如CPU、主存；
竞争不可抢占性资源才会引起死锁
预防死锁：
（1）破坏互斥条件：不可能做到
（2）破坏请求保持条件：进程创建时，一次申请所有资源，成功则运行，否则阻塞。
（3）破坏不可抢占条件：进程申请资源时，成功则运行，否则释放所有资源后阻塞
（4）破坏循环等待条件：为所有资源编号，进程申请资源时必须按序申请资源
避免死锁：
系统处于安全状态，不会死锁；
系统处于不安全状态，可能死锁；
银行家算法 安全性算法
检测死锁：资源分配图 不可完全简化→死锁
解除死锁：最小生成树算法
4.存储器管理
连续分配-存储管理方式：
（1）单一连续分配：用户区内存只有一道用户程序
（2）固定分区分配：用户区划分成若干固定大小的区域，每个分区只装有一道用户程序
（3）动态分区分配：程序装入时动态划分区域，运行结束时撤销分区
空闲分区表 + 空闲分区链
首次适应（FF）,循环首次适应（NF）,最佳适应（BF）,最坏适应（WF）
（4）动态可重定位分配：
紧凑：拼接内存碎片
分页-存储管理方式：
页和块大小相等，会产生内部碎片
分段-存储管理方式：
不会产生内部碎片
段页式-存储管理方式：
一张段表，每个段对应一张页表
5.设备管理
I/O系统的基本组成结构：I/O设备、设备控制器、I/O通道
独占设备：指在一段时间内只允许一个用户(进程)使用的设备。
共享设备：指在一段时间内允许多个进程同时访问的设备。
虚拟设备：指通过某种技术将一*占设备变换为能供若干个用户共享的设备。
什么是设备独立性？
用户程序独立于具体使用的物理设备
设备独立性如何实现？
逻辑设备到物理设备的映射。
程序执行时，使用逻辑设备表（LUT）完成逻辑设备到物理设备的映射，每个用户配备一张LUT
SPOOLing技术:
提高了I/O操作的速度
将独占设备改造为共享设备
实现了虚拟设备功能
磁盘的工作特点和I/O时间构成：
T = Ts（寻道时间）+ Tr（旋转延迟时间）+ Tt（传输时间）
= Ts + 1/2r + b/rN
磁盘调度算法和演进的内部逻辑:
(1) 先来先服务调度算法（FCFS）
(2) 最短寻道时间优先调度算法（SSTF）
(3) 扫描算法（SCAN）
(4) 循环扫描算法（CSCAN）
提高磁盘I/O效率的办法：磁盘高速缓存、提前读、延迟写、优化物理块分布
6.文件管理
文件：文件是指由创建者所定义的、具有文件名的若干相关元素的集合
有结构文件：由若干记录构成的文件；
无结构文件：由字节/字符组成的文件；
文件操作：打开文件，读写文件等操作，关闭文件
文件系统模型：文件系统接口、对对象操纵和管理的软件集合、对象及其属性
逻辑文件：从用户观点出发看到的文件。其结构为文件的逻辑结构，是用户可以直接处理的数据及其结构，独立于文件的物理特性，又称文件组织。
物理文件：从系统角度出发看到的文件。其结构为文件的存储结构/物理结构，是指文件在外存上的存储组织形式，与存储介质的存储性能、外存分配形式密切相关。
逻辑文件到物理文件的映射：文件目录
文件的逻辑结构：顺序文件、索引文件、索引顺序文件、直接（Hash）文件
文件的物理结构（外存分配方式）：连续分配、链接分配、索引分配
文件存储空间的管理：
空闲表法
空闲链表法
位示图法
成组链接法(UNIX)
文件共享：
基于索引结点的共享
基于符号链的共享
事务机制：
原子性(Atomic)