操作系统

操作系统笔记

Posted by jiang on June 26, 2018

操作系统概述

  • 用户态 目态 内核态 管态 包括系统调用类指令和一些针对时钟、中断和原语的操作指令
  • 时钟管理 中断机制 原语
  • 中断 外中断
  • 异常 内中断
  • 用户态到内核态 用户堆栈=>内核堆栈 访管指令用户态执行
  • 内核态到用户态 特权指令内核态执行

进程管理

  • 概念:多道程序下,允许多个程序并发执行,此时听它们将失去封闭性,并具有间断性,不可再现性特征,为此引入进程概念,以便更好描述和控制程序并发执行,实现操作系统的并发性与共享性(最基本的两个特征)。
  • PCB(process control block)描述进程的基本情况和运行状态,进而控制和管理进程。进程存在的唯一标志。
  • 进程映像(程序段,相关数据段,PCB)
  • 定义:
    1. 程序的一次执行过程
    2. 程序与数据在处理机上顺序执行时发生的活动
    3. 系统进行资源分配和调度的独立单元
  • 特征:
    1. 动态性 生命周期(创建 活动 暂停 终止)基本特征
    2. 并发性
    3. 独立性
    4. 异步性
    5. 结构性
  • 进程状态
    1. 运行状态
    2. 就绪状态(等待cpu)被动
    3. 阻塞状态(等待状态)等待IOor资源 主动
    4. 创建状态
    5. 结束状态
  • 进程切换
    1. 保存cpu上下文(程序计数器、其他寄存器)
    2. 更新PCB信息
    3. 把进程PCB移入相应队列,就绪、阻塞队列
    4. 选择另一个进程执行,更新其PCB
    5. 更新内存管理的数据结构
    6. 恢复cpu上下文
  • 进程的组织
    1. PCB 1.1 进程描述信息(UID,PID)
      1.2 进程控制与管理信息(优先级,当前状态、入口地址、cpu占用时间、信号量、外存地址)
      1.3 资源分配清单(代码段指针、数据段指针、堆栈指针、文件描述符、鼠标、键盘)
      1.4 处理机相关信息(通用、地址、控制、标志、状态寄存器值、状态字)
    2. 程序段 能被进程调度程序调度到到cpu执行的代码段
    3. 数据段
  • 进程的通信
    1. 共享存储 基于数据结构 基于存储区 操作系统提供共享存储空间与同步互斥工具PV,数据交换用户安排读/写完成
    2. 消息传递 直接通信 接受进程消息缓冲队列;间接通信 中间实体 信箱 信箱通信方式
    3. 管道通信 链接一个读进程与写进程以实现他们通信的一个共享文件,pipe文件。
       3.1 互斥 同步 确定对方存在
       3.2 限制管道大小
       3.3 读进程可能比写进程快 阻塞 解决文件结束返回问题
       3.4 管道读数据是一次性操作 一但读取就抛弃
       3.5 半双工通信 某一时刻只能单向传输 全双工需要两个管道
  • 线程
    1. 概念:减少时空开销,轻量级进程,cpu基本执行单元 ,程序执行流的最小单元
    2. 结构:线程ID,程序计数器,寄存器集合,堆栈,线程不拥有系统资源。
    3. 比较:调度。拥有资源、并发、系统开销、地址空间与其他资源、通信
    4. 线程控制块 TCB 阻塞态,就绪态,运行态
    5. 实现方式:用户级线程ULT,内核级线程KLT
    6. 多线程模型:
       6.1 一对一 资源开销大 并发强
       6.2 多对一 用户空间效率高 易阻塞
       6.3 多对多 用户线程>=内核线程

处理机调度

  1. 调度层次
    1.1 作业调度 高级调度 内存与辅存之间调度
    1.2 中级调度 内存调度 提高内存利用率与系统吞吐量 挂起 移至外存 就绪 等待
    1.3 进程调度 低级调度 就绪队列=>分配处理机 频率最高
  2. 不能进行调度与切换的情况
    2.1 处理中断
    2.2 进程在操作系统内核程序临界区中
    2.3 其他需要完全屏蔽中断的原子操作 加锁 解锁 中断现场保护 恢复
  3. 可以调度与切换
    3.1 引发调度条件,当前进程无法继续运行 非剥夺调度 批处理系统 不适用分时系统和大多数实时系统
    3.2 中断处理结束或自陷处理结束后 剥夺调度 优先权 短进程优先 时间片原则
  4. 调度准则
    4.1 CPU利用率
    4.2 系统吞吐量 单位时间内cpu完成作业数量
    4.3 周转时间 作业完成时间-作业提交时间
    4.4 平均周转时间 (w1+w2+…+wn)/n 带权周转 = 作业周转时间/作业实际运行时间 平均带权时间=(q1+q2+…+qn)/n
    4.5 等待时间 调度算法不影响cpu执行作业或IO时间,等待时间评价算法优劣
    4.6 响应时间 从用户提交到系统首次生产响应的时间
  5. 调度算法
1
2
3
4
5
6
7
8
9
10
11
5.1 先来先服务 FCFS 不可剥夺调度 简单 效率低 长作业有利 有利于CPU繁忙作业 进程与作业调度  
5.2 短作业优先 SJF 长作业不利 饥饿 未考虑作业紧迫度 作业与进程调度  
5.3 优先级调度  适用作业调度与进程调度  
    5.3.1 是否抢占正在执行的进程 非剥夺式优先级:不让高优先级进程 剥夺式高优先级:让出处理机  
    5.3.2 进程创建后是否可以改变优先级 静态优先级(进程类型 进程对资源的要求 用户要求) 动态优先级(cpu时间长短 就绪进程等待cpu时长)   
5.4 高响应比优先 FCFS与SJF的综合平衡 响应比=(等待时间+要求服务时间)/要求服务时间  
    5.4.1 等待时间相同 要求服务时间越短响应比越高 有利于短作业  
    5.4.2 要求服务时间相同 等待时间越长 响应比越高 先来先服务  
    5.4.3 长作业 等待时间越长 响应比越高 克服饥饿状态  
5.5 时间片轮询 分时操作系统 (系统响应时间 就绪队列进程数目 系统处理能力)  
5.6 多级反馈队列调度 综合算法 终端作业用户:短进程优先 短批处理作业用户:周转时间短 长批处理作业用户:不会长期得不到执行

进程同步

  • 概念:多道程序下,进程是并发执行的,为了协调进程间的制约关系,引入同步概念。
  • 临界资源:虽然多个进程可以共享系统中的各种资源,但许多资源一次只能为一个进程使用。这种资源叫临界资源
1
2
3
4
5
6
do{
    entry section     //进入区
    critical section  //临界区
    exit section      //退出区
    remainder section //剩余区
}while(true)
  • 同步 直接制约关系
  • 互斥 间接制约关系
  • 同步机制 空闲让进 忙则等待 有限等待 让权等待
  • 临界区互斥基本方法 软件实现

  • 单标志法 违背空闲让进
1
2
3
4
5
6
7
8
9
10
//p1
while(turn!=0);
critical section;
turn=1;
remainder section;
//p2
while(turn!=1);
critical section;
turn =0;
remainder section;
  • 双标志法先检查 违背忙则等待
1
2
3
4
5
6
7
8
9
10
11
12
//p1
while(flag[j]);
flag[i]=true;
critical section;
flag[i]=false;
remainder section;
//p2
while(flag[i]);
flag[j]=true;
critical section;
flag[j]=false;
remainder section;
  • 双标志法后检查 饥饿现象
1
2
3
4
5
6
7
8
9
10
11
12
//p1
flag[i]=true;
while(flag[j]);
critical section;
flag[i]=false;
remainder section;
//p2
flag[j]=true;
while(flag[i]);
critical section;
flag[j]=false;
remainder section;
  • peterson Algorithm 单标与双标后检查结合
1
2
3
4
5
6
7
8
9
10
11
12
13
//p1 
flag[i]=true;turn=j;
while(flag[j]&&turn==j);
critical section;
flag[i]=false;
remainder section;

//p2
flag[j]=ture;turn=i;
while(flag[i]&&turn==i);
critical section;
flag[j]=false;
remainder section;
  • 临界区互斥基本方法 硬件实现 元方法
1
2
3
4
//中断屏蔽 限制了处理器的能力 
关中断;
临界区;
开中断;
  • 指令
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//硬件指令 任意进程数量 简单 支持多个临界区 耗费处理机时间 不能实现让权等待 饥饿现象

//TestAndSet指令
boolean TestAndTest(boolean *lock){
    boolean old;
    old=*lock;
    *lock=true;
    return old;
}
//TestAndSet互斥
while TestAndSet(&lock);
进程临界代码段;
lock=false;
进程其他代码;

//Swap指令
Swap(boolean *a,boolean *b){
    boolean temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
//Swap互斥
key =true;
while(key!=false);
Swap(&lock,key);
进入临界区;
lock=false;
其他代码段;
  • 信号量 wait(S) P;signal(S) V;同步互斥问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//1.整形信号量
wait(S){
   while(S<=0); //忙等 违背让权等待
   S-=1;
}

signal(S){
   S+=1;
}
//2.记录型信号量
typeof struct {
    int value;
    struct process *L;
} semaphore;

//PV
void wait(semaphore S){
    S.value--;
    if(S.value<0){
        add this process to S.L;
        block(S.L);//让权等待
    }
}

void signal(semaphore S){
    S.value++;
    if(S.value<=0){
        remove a process P from S.L;
        wakeup(P);
    }
}

//3.信号量实现同步
semaphore S = 0;
P1(){
    x;
    V(S);
}
P2(){
    P(S);
    y;
}
//4.信号量实现进程互斥
semaphore S=1;
P1(){
    P(S);
    进程P1进入临界区;
    V(S);
}

P2(){
    P(S);
    进程P2进入临界区;
    V(S);
}

//5.信号量实现前驱关系
semaphore a1 = a2 = b1=b2=c=d=e=0;
S1(){
    V(a1);V(a2);
}
S2(){
    P(a1);
    ...;
    V(b1);V(b2);
}
S3(){
    P(a2);
    ...;
    V(c);
}
S4(){
    P(b1);
    ...;
    V(d);
}
S5(){
    P(b2);
    ...;
    V(e);
}
S6(){
    P(c);
    P(d);
    P(e);
}
  • 管程 一组数据以及定义在这组数据之上的操作组成的软件模块 抽象类
1
2
3
语言成分
编译时自动添加
无需程序员关注
  • 生产者–消费者问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;
producer(){
    while(1){
        proudce an item in nextp;
        P(empty);
        P(mutex);
        add nextp to buffer;
        V(mutex);
        V(full);
    }
}
consumer(){
    while(1){
        P(full);
        P(mutex);
        remove an item from buffer;
        V(mutex);
        V(empty);
        consume the item;
    }
}
  • 双 生产者–消费者问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
semaphore plate=1,apple=0,orange=0;
dad(){
    while(1){
        prepare an apple;
        P(plate);
        put the apple on the plate;
        V(apple);
    }
}

mom(){
    while(1){
        prepare an orange;
        P(plate);
        put the orange on the plate;
        V(orange);
    }
}

son(){
    while(1){
        P(orange);
        take the orange on the plate;
        V(plate);
    }
}

daughter(){
    while(1){
        P(apple);
        take the apple on the plate;
        V(plate);
    }
}

  • 读者–写着问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//读优先 写进程饿死
int count=0;
semaphore mutex = 1;
semaphore rw = 1;
writer(){
    while(1){
        P(rw);
        writing;
        V(rw);
    }
}
reader(){
    while(1){
        P(mutex);
        if(count==0) P(rw);
        count++;
        V(mutex);
        reading;
        P(mutex);
        count--;
        if(count==0) V(rw);
        V(mutex);
    }
}

// 读写公平法
int count=0;
semaphore mutex = 1;
semaphore rw = 1;
semaphore w=1;
writer(){
    while(1){
        P(w)
        P(rw);
        writing;
        V(rw);
        P(w);
    }
}
reader(){
    while(1){
        P(mutex);
        if(count==0) P(rw);
        count++;
        V(mutex);
        reading;
        P(mutex);
        count--;
        if(count==0) V(rw);
        V(mutex);
    }
}

  • 哲学家进餐问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1;
Pi(){
    do(){
        P(mutex);
        P(chopstick[i]);
        P(chopstick[i+1]%5);
        V(mutex);
        eat;
        P(chopstick[i]);
        P(chopstick[i+1]%5);
        think;
    } while(1);
}
  • 吸烟者问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int random;
semaphore offer1=0;
semaphore offer2=0;
semaphore offer3=0;
semaphore finish=0;
P1(){
    while(1){
        random = 任意随机整数;
        random = random%3;
        if(random==0){
            V(offer1);
        }else if(random==1){
            V(offer2);
        }else{
            V(offer3);
        }
        任意两种材料放在桌上;
        P(finish);
    }
}

P2(){
    while(1){
        P(offer3);
        拿起胶水和纸;
        V(finish);
    }
}

P3(){
    while(1){
        P(offer2);
        拿起胶水和烟草;
        V(finish);
    }
}

P4(){
    while(1){
        P(offer1);
        拿起烟草和纸;
        V(finish);
    }
}

死锁

  • 定义:多个进程因竞争资源而造成的一种僵局,相互等待。
  • 原因:系统资源的竞争 进程推进顺序非法 条件(互斥条件 不剥夺条件 请求和保持条件 循环等待条件)
  • 处理策略:预防死锁 避免死锁
  • 系统安全状态
  • 银行家算法(避免死锁) 核心–安全性算法
1
2
3
4
1.Max-Allocation = Need
2.Need与Available对比,找出比Available小的行
3.P1 Avaliable+=P1
4.重复第一步
  • 死锁检测 资源分配图
  • 死锁定理 S为死锁的条件当且仅当S的状态的资源分配图是不可完全简化的。
  • 死锁解除 1)资源剥夺 2)撤销进程 3)进程回退法

内存管理

  • 功能:内存空间分配与回收 地址转换 内存空间的扩充 存储保护
  • 内存保护:重定位寄存器(基址寄存器) 界地址寄存器(限长寄存器)
1
cpu=> 小于界地址寄存器=>加上重定位寄存器=>物理内存地址
  • 覆盖与交换
  • 分配方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1. 单一连续分配 系统区 用户区 简单 单用户 单任务操作系统 内部碎片 利用率低
2. 固定分区分配 多道程序 内部碎片
3. 动态分区分配 外部碎片 连续分配
3.1 首次适应算法 顺序查找 大小满足
3.2 最佳适应算法 空闲分区容量递增链表
3.3 最坏适应算法 空闲分区容量递减链表
3.4 邻近适应算法 循环首次适应
4. 基本分页存储管理方式 不会产生外部碎片 **地址空间是一维的** 为计算机设计
- 页帧 2的整数幂 太小页面多 表过长 增加转换开销 
- 帧大 碎片多 [页号P|页内偏移量W]
**- 基本地址变换机构?**
- cpu快表 内存慢表 局部性原理 
- 二级页表 顶级页表最多只能有1个页面
5. 基本分段存储管理方式 为用户与程序设计 段内要求连续 段间不要求连续 编译程序完成 
- 段表
**- 地址变换机构?**
- 需要段号和段内偏移 二维
6. 段页式内存管理方式 页式提高内存利用率,段式反应程序的逻辑结构并有利于段共享
**- 段页式系统地址变换机构?**

虚拟内存管理

  • 局部性原理 时空局限性 一段程序执行不久后可能再次访问 一段内存访问不久后附近单元也再次访问
  • 页表机制 [页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址]
  • 缺页中断机构 一条指令执行期间=>内部中断 可能多次中断
  • 地址变换机构

页面置换算法

  • 最佳置换算法 OPT
  • 先进先出置换 FIFO 弊端:Belady异常 物理块数增大也故障数不减反增现象。
  • 最近最久未使用 LRU 堆栈支持
  • 最近未用算法 NRU clock算法 循环扫描缓冲区 使用位、修改位
1
2
3
4
5
6
7
//CLOCK
使用位 u=0
//改进的CLOCK
未被访问&未被修改 u=0 m=0
已被访问&未被修改 u=1 m=0
未被访问&已被修改 u=0 m=1
已被访问&已被修改 u=1 m=1
  • 页面分配策略
1
2
3
1. 固定分配局部置换
2. 可变分配全局置换
3. 可变分配局部置换
  • 调页时机 预调页策略 运行期 请求调页策略 运行期
  • 何处调页 对换空间(连续) 文件区(离散) unix方式
  • 抖动 频繁的页面调度行为
  • 工作集模型原理:让操作系统跟踪每个进程的工作集,并为进程分配大于其工作集的物理块。
  • 地址翻译

文件管理

  • 在系统运行时,计算机以进程为基本单位进行资源调度与分配;用户进行输入输出中,以文件为基本单位
  • 数据项 记录 结构文件 无结构文件 流式文件
  • 文件属性 名称 标识符 类型 位置 大小 保护 时间日期用户标识
  • 基本操作 创建文件 写文件 读文件 文件重定位 删除文件 截断文件
  • 文件打开 文件指针 文件打开计数 文件磁盘位置 访问权限
  • 文件逻辑结构
1
2
1.无结构文件 流式文件 字节为单位
2.有结构文件 顺序文件 索引文件 索引顺序文件 直接文件与散列文件 
  • 文件控制块和索引节点
1
2
3
4
- FCB 基本信息 存取控制信息 使用信息 
- 索引节点 
磁盘索引节点:文件主标识符 文件类型 存取权限 物理地址 文件长度
文件链接计数 文件存取时间 文件打开时:索引节点编号、状态、访问计数、逻辑设备号、链接指针 
  • 目录结构
1
2
3
4
5
6
7
8
9
搜索
创建文件
删除文件
显示目录
修改目录
单级目录结构 
二级目录结构 主文件目录MFD 用户文件目录UFD
多级目录结构 
五环图目录结构 文件共享
  • 文件共享
1
2
1. 基于索引结点的共享方式 硬链接 当count=0系统负责删除文件 
2. 利用符号链接实现文件共享 软连接 增加查找开销
  • 文件保护
1
2
访问类型:读 写 执行 添加 删除 列表清单
访问控制:ACL 拥有者 组 其他 口令和密码
  • 文件系统层次结构
1
2
3
4
5
6
7
用户调用接口
文件目录系统
存取控制验证
逻辑文件系统与文件信息缓冲区
物理文件系统
分配模块
设备管理程序模块
  • 目录实现 线性列表 哈希表
  • 文件分配方式
1
2
3
连续分配 
链接分配 文件分配表FAT 
索引分配
  • 索引块 链接方案 多层索引 混和索引
  • 文件存储空间管理
1
2
3
4
5
1. 文件区与目录区FCB
2. 空闲表法 连续分配方式
3. 空闲链表法 
4. 位示图
5. 成组链接法 unix 大型文件系统 

磁盘组织与管理

  • 寻找时间Ts
1
2
Ts = m*n+s
m磁盘驱动器,约为0.2ms 跨越n条磁道的时间 启动磁臂的时间s
  • 延迟时间Tr
1
2
Tr = 1/2r 
r磁盘的旋转速度
  • 传输时间Tt
1
2
Tt = b/rN
每次读/写的字节数b,r为磁盘每秒的转数,N为一个磁道上的字节数
  • 总平均存取时间Ta
1
Ta = Ts + 1/2r + b/rN
  • 磁盘调度算法
1
2
3
4
1.先来先服务 FCFS
2.最短寻找时间优先 SSTF 饥饿 
3.扫描算法SCAN 电梯算法 局部性方面不如FSFC和SSTF 磁道距离最近对象 LOOk
4.循环扫描C-SCAN C-LOOK
  • 磁盘管理
1
2
3
1. 磁盘初始化 每个扇区数据结构 头部 数据区域 尾部
2. 引导块 自举程序(初始化cpu 寄存器 设备控制器 内存)
3. 坏块 IDE手动处理 FAT磁盘会标明 SCSI磁盘坏块链表 不去使用操作系统是不能修复坏块的

IO管理

  • IO设备:人机交互类外部设备 存储设备 网络通信设备
  • IO控制方式
1
2
3
4
5
6
7
1.程序直接控制方式 循环测试 效率低 简单 一直占用CPU
2.中断驱动方式 占用CPU 数据在存储器与IO设备之间传输必须经过CPU
3.DMA 解放CPU
CPU=>DMA=>内存=>CPU
4.通道控制方式 通道与CPU共享内存 

  • IO子系统的层次
1
2
3
4
5
1.用户层IO软件
2.设备独立性软件
3.设备驱动程序
4.中断处理程序
5.硬件设备
  • IO核心子系统服务:IO调度 缓冲与高速缓存 设备分配与回收 假脱机 设备保护 差错处理
  • IO调度 请求队列
  • 高速缓存与缓冲区
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
1.磁盘高速缓存
2.缓冲区 硬件缓冲器成本高 缓冲区非空不能写入 写满后读出
- 单缓冲
- 双缓冲
- 循环缓冲
- 缓冲池
3.设备分配与回收
- 独占式使用设备
- 分时式共享设备
- SPOOLING方式使用外部设备 假脱机技术 空间换时间
4.设备分配数据结构
- 设备控制表 DCT
- 控制器控制表 COCT
- 通道控制表 CHCT
- 系统设备表 SDT
5.设备分配策略
- 静态分配
- 动态分配
- 先请求先分配
- 高优先级先分配
6.安全分配方式 不安全分配方式
7.逻辑设备到物理设备映射 逻辑设备表LUT
8.SPOOLING cpu高速性与IO设备低速性 外围控制机 打印机 将独占设备改成共享设备
- 输入井 输出井 
- 输入缓冲区 输出缓冲区
- 输入进程 输出进程