第一章系统概论

1.1 什么是操作系统

用户 ——应用软件——操作系统——硬件
应用软件
系统软件：操作系统（最重要）
是资源管理器：控制所有的软件硬件资源
是用户与计算机之间的接口
（1）命令行
（2）图形窗口
（3）系统调用（程序调用，如库函数）
作用：提高计算机效率，方便用户使用，提高系统资源使用率，增强系统处理能力。

1.2.1 手工和批处理系统

手工
人机矛盾严重
批处理系统
自动运行，无交互性，吞吐量大
联机处理：
直接与外设相连，效率不高
脱机处理：
通过卫星机/外围机与外设相连
多道程序设计技术
多道程序相互交替运行，提高效率

1.2.2分时操作系统和实时操作系统

分时系统
采用时间片轮转
多路性
独占性：
交互型
及时性
实时系统
能够及时响应外部请求
及时响应
可靠安全
整体性强
交互会话能力较弱
产品级为多种操作系统综合

1.3操作系统功能

1 处理机管理（进程管理)

进程控制
进程同步
进程调度
进程通信

2 存储管理

内存分配
内存保护
地址映射
内存扩充

3 设备管理

缓存管理
设备分配
设备处理
设备独立性，虚拟设备

4 文件管理

文件存储空间管理
目录管理
读写管理
存取管理

5 用户接口

命令行
图形窗口
系统调用

1.4 操作系统特征

并发性
（1）并行性同一时刻发生
（2）并发性：同一时间间隔
宏观同时运行，微观一时间段交替运行
共享性
系统资源供多个并发程序使用
（1）互斥共享（打印机）
（2）同时访问（硬盘）
虚拟性
（1）虚拟处理器
（2）虚拟内存
（3）虚拟外部设备
不确定性（异步性）
多道程序共享系统资源
不可预知速度运行

第二章进程管理

2.1.1进程基本概念

并发执行
（1）间断性
（2）失去封闭性
（3）不可再现性
顺序执行
一个程序独占cpu运行直到得到最终结果
（1）顺序性
（2）封闭性（独占资源）
（1）可再现性（结果无关系）
程序执行活动不再一一对应，并发程序间存在制约关系
程序：静态
程序执行过程：动态

2.2.2 进程的定义

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

特性
动态性并发性结构特性独立性不确定性
进程和程序区别

进程	程序
动态性	静态性
并发执行	只能串行
资源调度基本单位	不是资源基本单位
一个进程执行一个或几个程序	一个程序可对应多个进程

2.2.3 进程的状态

进程三种状态

 就绪状态：已经得到处CPU之外的所有资源，等待调用
 运行状态：正在占用CPU
 阻塞状态：正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等），此时引起进程调度，操作系统把处理机分配给另外一个就绪的进程，而让受阻的进程处于暂停的状态，一般将这个暂停状态称为阻塞状态

状态转换

 就绪--运行
 运行--阻塞
 阻塞--就绪
 运行--就绪

挂起
原因：内存资源不足，进程全部阻塞，父进程要求等
活动就绪：内存中
静止就绪：外存中

2.2.4进程控制块

进程控制块是进程存在的唯一标志
包含; 表示信息，位置信息，状态信息，现场保护区，资源清单，队列指针等

常用的PCB组织方式

 （1）线性表：节省空间，执行慢
 （2）连接表
 （3）索引表：有数据冗余，查询效率最高

2.3 进程控制

进程由创建产生，调度执行，撤销而消亡
进程控制的主要职能：对进程进行创建，撤销，状态转换。
允许进程创建和控制另一个进程，前者为父进程，可形成树形进程家族。
原语：
进程控制由原语完成
由若干条指令组成，执行不可被中断
原语为操作系统的核心代码，常驻内存，且通常为管态。

进程的创建

 申请PCB空间
 分配资源
 信息填入PCB
 PCB插入到就绪队列

进程撤销

 查找PCB
 撤销子孙进程
 释放缓冲区
 释放工作空间和PCB

进程阻塞

 中断cpu
 进入阻塞队列
 cpu分配其他进程

进程唤醒

 找到进程标识
 脱离阻塞队列
 插入就绪队列

2.4.1进程同步和互斥

直接制约
间接制约
某段时间只能允许一个进程使用称为临界资源
访问临界资源代码为临界区
使用过程
进入区--临界区--退出区

遵循原则
空闲让进（不浪费）

 临界区空闲申请应立即进入

忙则等待（不争抢）

 已经进入临界区其他进程必须等待

有限等待（不死等）

 保证资源在有限时间内进入

让权等待（不忙等）

 当进程不能进入自己临界区，因立刻释放处理机

2.4.2 信号量和PV操作

含义
信号量：某种临界资源的数目（S）
PV操作：由原语构成，在信号量上定义了两个原子操作
P：申请资源
V：释放资源

进程A的程序
P（S）;
 将一项送入队列;
 V（S）;
/*S值的大小表示某类资源的数量。每执行一次V操作，意味着释放一个资源。
所以当S=-1时，表示等待队列中有1个等待进程。

利用PV操作解决同步代码

S1 S2为信号量，S1为像缓冲区输入，S2为像缓冲区取
1表示可，0表示否，S1初值为1，S2初值为0

进程A的程序
P（S1）;
 读取信息到缓冲区B;
 V（S2）;

进程2
P（S1）;
把缓冲区B信息输出;
V(S1);

2.4.3 生产者和消费者问题

设置两个指针生产者 i ，消费者 j

同步关系 -- 直接制约
当i追上j，生产者阻塞，等待消费者消费
当j大于i，消费者必须等待生产者生产
互斥关系 -- 间接制约
无论生产者与消费者只要在缓冲池内操作，必须与其他人互斥

问题解决

 公用信号量mutex;初值1；用于临界区互斥；
 生产者私用信号量empty；初值是n，指示空缓存数目；
 消费者私用信号量full初值0；指示满缓冲区数目；
 整形量i，j初值均为0，i指示缓冲区序号头，j指示满缓冲区头指针；

代码：

semaphore mutex = 1, empty = n, full = 0;
int i = j = 0;
item buffer[n];

void producter()
{
	while(1)
	{	
		produce next product;
		P(empty);
		P(mutex);
		buffer[i]= product;
		i = (i+1)%n;
		V(mutex);
		V(full);
	}
}

2.4.4 读写者问题

信号量设置
对于读者和写着，临界资源必须互斥，信号量wsem
计数器readcount 记录临界资源的读者个数
mutex保证对于计数器的访问互斥
算法实现

//读者优先
int readcount=0；
semaphore mutex=1，wsem=1；
void reader
{
	while(1)
	{
	P(mutex);
	readcount++;
	if(reeadcount==1);
	P(wsem);
	V(mutex);
	READ;
	P(mutex);
	readcount--;
	if(readcount==0);
	V(wsem);
	V(mutex);
	}
}

写者进程

void write()
{
	while(1)
	{
		P(wsem);
		WRITE;
		V(wsem);
	}
}

2.4.5 哲学家就餐问题

问题描述
当五个哲学家均拿起了每个人的左手叉等待右手叉，发生死锁。
解决方式
（1）最多允许四个哲学家就餐

semaphore fork[5]={1，1，1，1，1}；//叉子
semaphore room = 4;//位子
int i;
void philosopher(int i)
{
	while(1)
	{
		think();
		P(room);
		P(fork[i]);
		P(fork[(i+1)%5]);
		eat();
		V(fork[i]);
		V(fork[i+1]%5);
		V(room);
		
	}
}
void main()
{
for(i=0;i<5;i++)
parbegin(philosopher(i));
}

(2)将哲学家进行标号，奇数号必须先拿左边叉子，偶数号先拿右手；

2.5.1 进程通信

进程间的信息交换
同步与互斥是进程通信，交换信息量小，低级通信
高级通信
（1）共享存储

实现过程：

Linux中共享存储器：

2.5.2 消息通信

在这里插入图片描述
消息通信的原语 send（B，a）：B接收方进程名，a代表发送区首地址。

在这里插入图片描述
mq消息缓冲区队列

在这里插入图片描述
发送消息原语实现过程

//i代表缓冲区号
//j代表接收进程的PCB地址
//getBuff（）申请缓冲区函数
//putbuff（）释放缓冲区
void send(B,a)
{
	getBuff();
	i.sender = a.sender;
	i.size = a.size;
	i.text = a.text;
	i.next = 0;
	getid(PCB,B.j);
	insert(j.mp,i)
	V(j.mutex);
	V(j.sm); //通知接收方接受消息
}

接收原语

void receive(b)
{
	P(j.sm);
	P(j.mutex);
	remove(j.mq,i);
	V(j.mutex);
	b.sender=i.sender;
	b.size=i.size;
	b.text=i.text
	putbuff();
}

2.5.3 管道

共享文件通信（管道）

写进程-->共享文件-->读进程
pid = fork();
子进程进程号，大于0

在这里插入图片描述

2.6.1 进程调度算法

基本概念

在这里插入图片描述
2. 引起进程调度的原因

在这里插入图片描述
3. 选择调度方法的准则
面向用户准则：周转时间短，响应时间快，截止时间保证，优先权准则
面向系统准则：吞吐量高，处理及占用率高，各类资源均衡利用
4. 调度算法
（1）先来先服务
（2）时间片轮转调度（时间片长短很重要）
（3）短进程优先（照顾短小进程）
（4）高响应比优先法（相应比=等待时间/要求服务时间，既照顾了短小进程，又照顾了先来者）
（5）优先级法（静态/动态优先级，抢占/非抢占方式）

2.6.2 进程调度实例

在这里插入图片描述
（1）进程运行时序图

周转时间和带权周转时间

多级反馈队列调度算法

性能较高，但系统资源开销较大。

2.7.1 死锁的基本概念

死锁是多个进程竞争资源产生的一种僵持局面，必须有外力打破。（形成环路等待）
产生死锁的原因
系统提供资源不足，并发进程推进顺序不合法。
产生死锁的必要条件
a.互斥 b.不剥夺 c.请求保持 d.环路等待
死锁的预防

互斥性条件最难破坏
死锁的避免

2.7.2银行家算法

原则
银行家算法描述
安全性检查算法
（1）available[m]，m表示系统内资源类别数，available[j]=k表示可分配 j 类资源k个
（2）max[n，m]，n表示进程个数，m表示系统内类别数，max[i，j] = k表示 Pi 可申请 j 类资源 k 个
（3）allocation[n , m]，n ，m同上，allocation[i , j]=k表示 Pi已经分配 j 类资源 k 个
（4）need[n,m], need[i, j]=k 表示Pi 尚却 j类资源 k个
算法步骤
安全检查步骤

2.7.3 利用银行家算法防止死锁

利用银行家算法检测死锁

在这里插入图片描述

2.7.4 死锁的解除

1.消除死锁的方法
资源剥夺法，撤销进程法，进程回退法
Unix对系统死锁处理：鸵鸟算法

2.8 线程

比进程更小的能独立运行的基本单位，提高程序的并发执行程度。
线程的引入：进程太重

作为调度和分派的进本单位，不作为资源分配的基本单位。
线程与进程区别
线程的属性
线程的状态及转换
线程的调度

在这里插入图片描述
7. 线程的通信

8. 线程的实现

第三章存储管理

3.1 内存管理概述

多级存储体系
理想：大容量高速的持久性
多级储存器体系
存储管理的主要目的
存储管理的基本功能
（1）内存分配与回收

需要考虑：空闲区，置换，回收
（2）地址重定位
建立用户程序的逻辑地址与物理地址的对应关系
内存空间（物理空间） --物理地址
逻辑空间（虚空间） --逻辑地址

名空间：程序空间
a. 静态地址重定位

b. 动态地址重定位（广泛使用）

（3）存储保护

（4）虚拟存储器

3.3.1 固定分区和可变分区存储管理

固定分区存储管理

固定式分区内存分配示意图

在这里插入图片描述
可变分区存储管理

可变式分区内存分配示意图

在这里插入图片描述

3.3.2 分区适应算法

三种算法
首次适应算法（顺序）
最佳适应算法（由小到大）
最差适应算法（由大到小）

3.3.3 紧凑，覆盖，交换

最差和最佳
可变分区
基于可变分区的动态内存分配与回收
内存不足采取的方法

3.4.1 分页式存储管理思想

页式存储管理
分页式存储管理存储块的分配和回收
存储块的位图管理法

3.4.2 分页式存储管理的地址的重定位

分页存储管理的逻辑地址
实现过程
联想存储器

联想存储器重定位过程

3.5 分段式存储管理

分段式存储管理基本思想
地址重定位

转换过程

分段式重定位实例

3.6 段页式存储管理

段页式存储管理思想
段页式存储管理的实现
段页式存储管理地址的重定位

地址变换具体过程

在这里插入图片描述

3.7.1 虚拟存储器概念

基本概念
理论依据--局部性原理
实现思想

3.7.2 请求页式存储管理

基本概念
请求分页式存储管理
页面置换问题

3.7.3 页面置换算法

置换算法的原则
最优算法--OPT

先进先出算法--FIFO

最近最久未使用算法--LRU
LRU近似算法

算法流程

近似算法的缺点
时钟算法

在这里插入图片描述

如何解决抖动

第四章文件系统

4.1 文件管理概述

什么是文件
存储在外部存储介质上的，具有符号名的一组相关信息的集合。
1.1文件命名

1.2 文件的属性
文件物理位置
文件的拥有者
文件的权限
文件名
文件内部的标识
文件的类型，长度，时间
1.3 分类
用途划分：系统文件 / 库文件 / 用户文件
性质划分：普通文件 / 目录文件 / 特殊文件
保护级别：只读 / 读写 / 可执行 / 不保护
文件形式：源文件 / 目标文件 / 可执行文件
1.4 文件的操作
创建删除打开关闭读写截断读写定位
文件系统