2019-11-26 13:32 已编辑英特尔中国公司_SSE

关注

操作系统期末复习

学习资料：老师的PPT、作业、计算机操作系统（第四版）汤子瀛、汤小丹等，加自己的另一篇总结

学习计划：每天复习1章内容+例题+习题+总复习PPT的主要内容

学习时长：距离考试10天，学习计划8天，留1~2天总复习 19年1月1号复习完了zzz，超出预期的速度

考试：概念忘记，可以用例子来解释

第一章概论

操作系统的基本概念

概念：操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充，主要作用是管理设备，提高它们的利用率和系统的吞吐量，并为用户和应用程序提供一个接口
目标：方便性、可扩充性、开放性、有效性（提高系统资源的利用率，系统的吞吐量）
作用：计算机和用户的接口、资源管理、资源抽象（封装）

操作系统的发展过程

单道：内存中仅有一道程序
- 优点：自动、顺序、单道
- 缺点：系统资源得不到充分利用
多道：内存中按调度算法执行程序
- 优点：资源利用率高、系统吞吐量达
- 缺点：平均周转时间长、无交互能力
分时：一台主机上有多个终端，时间片轮转法
- 优点：多路性、独立性、及时性、交互性
实时：系统的正确性，取决于逻辑结果和产生结果的时间，允许抢占。最大特点是响应快
分时和实时的区别
- 多路性、独立性、及时性、交互性、可靠性

操作系统的基本特性

并发
- 并行并发、进程、线程
共享
- 互斥共享、同时访问（实质是交替访问）

操作系统的虚拟技术

时分复用技术：利用处理机空闲时间，转去为其他用户服务
- 虚拟处理机技术：多道程序设计技术
- 虚拟设备技术：将一个IO设备虚拟为多个IO设备，并分配给每一个用户
空分复用技术：利用存储器空闲时间，转去为其他程序服务
- 虚拟内存
- 虚拟存储器技术
异步性：每次运行过程不可预知

操作系统的管理功能

进程控制：创建、撤销进程
进程同步：让多个进程协调进行
进程通信
调度

第二章进程管理

前驱图的定义
- 定义：DAG图，描述进程执行的先后顺序
程序顺序执行的特征
- 顺序性、封闭性、可再现性
PCB定义
- 定义：为每个进程配置的进程控制块，描述进程的基本情况和活动过程
进程控制-进程状态转换（重点）
信号量、临界区定义
- 临界区：并发进程中，每个进程访问临界资源的代码称为临界区
- 信号量
  - 整型信号量：开一个整型变量S
  - 记录型信号量：整型信号未实现“让权等待”，多定义一个变量list,来存储让权了的进程
  - AND型信号量：多个进程共用多个临界区资源
同步机制应遵循的准则
- 空闲让进、忙则等待、有限等待、让权等待

经典同步问题（重点）

有限缓冲区
- 代码：循环队列，in=(in+1)%n,out=(out+1)%n，临界区资源counter(全局变量)

生产者-消费者问题

记录型信号解决，代码

int in=0,out=0;
item buffer[n];
auto mutex=1,empty=n,full=0;
void producer{
    while(1){
        new temp;
        wait(empty);
        wait(mutex);
        buffer[in]=temp;
        in=(in+1)%n;
        signal(mutex);
        signal(full);
    }
}

void consumer(){
    while(1){
        wait(full);
        wait(mutex);
        int good=buffer[out];
        out=(out+1)%n;
        signal(mutex);
        signal(empty);
    }
}

AND型信号解决：利用Swait()代替两个连续的wait，即只有资源都空闲的时候才执行
管程解决，代码：写一个类，封装了put和get两个函数

哲学家进餐问题

记录型信号量解决会死锁，直接写AND型，代码：

int statu[5]={1,1,1,1,1};
while(1){
    Swait(statu[i],statu[(i+1)%n]) //对于第i位哲学家来说
    do ... sth ...
    Ssignal(statu[i],statu[(i+1)%n]) //对于第i位哲学家来说
}

读者-写者问题：同一时刻只允许一个进程读，不允许读+读 / 写+写 / 写+读

第三章调度与死锁

低级、中级、高级调度定义

高级调度：又称长程调度或作业调度，调度对象是作业，功能是用某种调度算法决定就绪队列中那几个作业调入内存
中级调度：又称内存调度，目的是为了提升吞吐率和资源利用率，功能是将外存中的程序块调入内存，并加入就绪队列
低级调度：又称进程调度或短程调度，调度对象是进程，功能是用算法决定哪个进程获得处理机
总结：高级调度→哪些作业调入内存；中级调度→外存到内存；低级调度→哪个进程获得处理机
作业，是一个总任务，而进程是作业的各个子任务。高级调度做作业分配，中级调度和低级调度面向进程，分别决定了哪些进程允许进入内存和哪些进程允许获得处理机（处理机包括CPU和主存储器）

调度规则

CPU利用率、吞吐量、周转时间（完成时间-到达时间）、平均周转时间（）、带权周转时间（周转时间/真实执行时间，）、平均带权周转时间（）、等待时间、响应时间

算法（重点）

先来先服务
短作业优先
优先级调度
时间片轮转法

死锁定义

若干个进程在争夺资源，最后陷入无限期的阻塞和等待中

死锁条件

互斥
不剥夺
请求与保持
循环等待

死锁避免方法-银行家算法（重点）

贪心首先完成能完成的

死锁预防、解除方法

预防：打破除了互斥的其他三个条件
解除：抢占资源、终止进程

第四章存储器管理

连续分配

概念：为了能将程序装入内存，必须为它分配一定大小的内存空间，连续分配方式是最早出现的存储器分配方式
类型
- 单一连续分配：系统分为用户区和系统区
- 固定分区分配
- 动态分区分配：首次适应（先找到先用）、最坏适应（找到最大的用）、最佳适应算法（找到最小的用）
- 动态可重定位分配算法：紧凑（去除小碎片，相当于平移）、重定位（重定位寄存器存在进程在内存的首地址）

基本分页式（重点）

物理地址和逻辑地址的区别
- 逻辑地址：理解为虚拟地址，包括了偏移量
- 物理地址：数据真实存放的地方
页表定义及作用
- 定义：为了能在内存中找到每个页面对应的物理块
- 作用：实现从页号到物理块号的地址映射
地址变换机构
- 基本地址变换机构：比下图少了个快表的部分
- 具有快表的地址变换机构：实质上快表先建立了一个映射表，节约了去页表找页号的时间，相当于预处理

基本分段式

段表作用：逻辑段到物理内存区的映射
地址变换机构：段表寄存器

分段式和分页式的区别

分页管理
- 没有外碎片，但会产生内碎片（页可能填不满）
- 一维地址
- 主要用于实现虚拟内存
- 以页为单位，大小静态
分段管理
- 没有内碎片，但会有外碎片
- 二维地址
- 以段为单位，大小动态

段页式的实现过程

程序分成若干个段，每个段对应一个页表

虚拟存储器

定义：具有调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
页面置换算法
- 最佳置换算法
- 先进先出算法
- 最近最少使用算法
- 最少使用次数算法

第五章输入输出系统

缓冲管理

缓冲区作用
- 缓和CPU和IO设备速度不匹配的矛盾
- 提高CPU和IO设备之间的并行性
- 减少CPU的中断频率，放宽对CPU中断响应时间的限制
- 解决数据粒度（数据单元大小）不匹配的问题
单缓冲
双缓冲（缓冲对换）：减少了用户响应时间
循环缓冲区
- 三个指针
  - nextg：指向装了数据的空缓存区
  - nexti：空缓存区
  - Current：正在使用的缓存区
- 使用
  - Getbuf，装载和读取数据
  - Releasebuf，释放缓存区
缓冲池
- 组成：emq,inq,outq
- 工作方式
  - 收容收入Getbuf（emq）
  - 提取输入Getbuf（inq）
  - 收容输出Getbuf（enq）
  - 提取输出Getbuf（outq）
SPOOLING系统（重点）
- 假脱机技术：利用专门的外围机，当需要用数据的时候，可以直接从磁盘读入 (我感觉就是一个缓存区吧。
- 组成
  - 输入井和输出井：模拟输入的磁盘
  - 输入缓冲区和输出缓冲区：输入缓冲区，在给输入井之前，先放缓冲区缓一缓
  - 输入进程和输出进程：模拟外围机，从外部输入数据到缓冲区
  - 井管理程序：用于控制作业与磁盘井之间信息的交换