操作系统期末复习

zstu 浙江理工大学 2023学年第1学期操作系统

带参考标记 ※ 的章节建议优先阅读

带星号 * 的章节或许可以暂时略过

考前关键词速记

定义：操作系统是指控制和管理整个计算机系统的硬件和软件资源，合理的组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。
特征：并发 共享 虚拟 异步
功能：处理机管理 存储器管理 设备管理 文件管理 接口管理
接口：命令 程序

单道：内存只有一道作业，CPU处理只一个
多道：内存有多道作业，在CPU中交替运行

分时：用户共享主机 人机交互
同时性 交互性 独立性 及时性
时间片轮转调度

实时：在时间限制内完成紧急任务，不需要时间片排队
硬实时 软实时
最早截止时间优先调度、最低松弛度优先调度

顺序执行：顺序、封闭、可再现
并发执行：间断、失去封闭、不可再现

进程是程序的执行过程，是系统进行资源分配和调度的独立单位
特征：动态 并发 独立 异步
状态：创建 就绪 执行 阻塞 终止

活动就绪--挂起--静止就绪
活动阻塞--挂起--静止阻塞

进程控制块PCB组织方式：线性、链接、索引
执行、就绪、阻塞、（空闲）队列指针

创建：分配进程号、申请PCB、分配资源、初始化PCB、插入就绪队列
阻塞：找到PCB，保护现场，插入等待队列，下处理机
唤醒：找到PCB，移出等待队列，插入就绪队列

进程通信：共享存储、消息传递、管道

线程：是独立调度的基本单位；也可并发；不拥有系统资源；共享进程的资源；切换开销小；支持多处理机

低级 中级 高级调度：进程 内存 作业

周转 = 完成 - 到达
带权周转 = 周转/运行 >= 1
响应比 = 1 + 等待/要求运行

只有时间片轮转、多级反馈队列是抢占的
先来先服务 FCFS
短作业优先 SJF
高响应比优先 HRRN
时间片轮转 RR
多级反馈队列 FB

RR：当一个时间片结束时，刚好有新任务到达，那么在队列中，新任务在被剥夺时间片任务的前面

最早截止时间优先包括抢占式和非抢占式
开始截止时间不是Deadline，在开始截止时间前开始任务即可
如果任务错过，那么该任务就取消

最低松弛度：抢占式
两任务松弛度一样时，选择先到的那个（先来先服务）

死锁
原因：竞争资源、进程顺序非法、信号量使用不当
条件：互斥、不剥夺、请求并保持、循环等待

资源分配图
框：一类资源
圆圈：进程
框内圆圈数：资源数
要求几个资源就画几条分配边
进程出去的边为请求，进来的为已分配

银行家算法：
Process Work Need Allocation Work+=Allocation Finish
Allocation 已分配的资源
Need 还需要的资源
Work 系统剩余资源

进程同步 临界区准则：空闲让进、忙则等待、有限等待、让权等待

信号量 semaphore 不要忘记while循环

编译、链接、装入
绝对装入、可重定位装入、动态运行时装入
静态链接、装入时动态链接、运行时动态链接

内存分配：单一连续分配、固定分区分配、动态分区分配、动态重定位分区分配（紧凑）
首次适应：空闲分区 地址递增
邻近适应：地址递增，从上次查找结束位置查找
最佳适应：最小的满足要求的
最坏适应：最大的满足要求的

分页存储 地址变换机构
【页表寄存器：页表起始地址、页表长度】【越界中断】【逻辑地址：页号、页内偏移量】
【页表：页号->块号】【物理地址：块号、页内偏移量、物理地址】
页表起始地址+页号=页号
页表长度 < 页号 => 越界中断
块号 指向 物理地址
偏移量 指向 物理地址

页号=逻辑地址/页面大小
偏移量=逻辑地址%页面大小

请求分页 页表：状态位（是否调入内存）、访问次数、修改位、外存地址
内存分配策略：固定分配局部置换、可变分配全局置换、可变分配局部置换
一个程序的内存分配是固定/可变的，发生页面置换时仅限于自己的帧内/全局

页面置换算法：
最佳OPT，先进先出FIFO，最近最久未使用LRU，最少使用LFU，时钟置换CLOCK

请求分段 段表：比分页增加存取方式（权限）、增补位（是否有动态增长）

共享和保护功能

设备控制表 控制器控制表 通道控制表 系统设备表

安全分配：进程发出IO请求后就阻塞
逻辑设备表：逻辑设备名、物理设备名、驱动程序地址

SPOOLing：
缓冲区申请空闲块、暂存打印数据
申请空白用户请求打印表、填入打印数据、加入假脱机文件队列

缓冲区的目的：
缓和CPU与IO速度不匹配、减少中断、解决数据粒度不匹配、提高并行
单缓冲、双缓冲、循环缓冲、缓冲池

磁盘调度：先来先服务FCFS
最短寻道时间优先 SSTF
扫描 SCAN 循环扫描 C-SCAN

磁盘访问时间＝寻道时间＋旋转延迟时间＋数据传输时间

文件、记录、数据项

文件系统层次结构：文件系统接口、对对象进行操纵和管理的软件集合、对象及其属性
对象：文件、目录、磁盘存储空间
软件集合：IO控制、基本文件系统、文件组织模块、逻辑文件系统
接口：命令、程序

打开文件表：文件指针、计数、磁盘位置、权限
无结构文件、顺序、索引、索引顺序（分块查找）、哈希
文件控制块 FCB：基本信息、权限、使用信息
磁盘索引结点、内存索引结点
单级目录、两级、树形、无环图
线性检索、哈希

外存：连续分配、隐式链接（单链表）、显式链接 文件分配表 FAT、索引分配、混合索引分配
FAT的表项与全部磁盘块一一对应
FAT表项的长度取半个字节(4bit)的整数倍

文件存储空间：空闲表、空闲链表（空闲盘块链、空闲盘区链）、位示图、成组链接

第 1 章操作系统概述

1.1 概念

1.1.1 定义 ※

1.1.2 特征 ※

并发和共享是最基本的特征

1.1.3 目标和功能 ※

接口分为命令接口和程序接口

命令接口分为联机（交互式）、脱机（批处理）

程序接口由系统调用组成

1.2 发展历程

1.2.1 手工

1.2.2 批处理 ※

1.2.3 分时 ※

1.2.4 实时 ※

题目

单道批处理系统和多道批处理系统的区别

分时操作系统和实时操作系统的区别

第 2 章进程的描述与控制

2.1 前驱图和程序执行

2.1.1 前驱图

2.1.2 程序顺序执行

顺序性、封闭性、可再现性

2.1.3 程序并发执行

间断性、失去封闭性、不可再现性

2.2 进程的描述

2.2.1 进程的定义与特征

特征：动态性、并发性、独立性、异步性

2.2.2 进程的状态与转换 ※

2.2.3 挂起操作*

就绪、阻塞状态可以被挂起

2.2.4 进程管理中的数据结构

PCB 进程控制块

组织方式

线性、链接、索引

2.3 进程控制

2.3.1 进程的创建

2.3.2 进程的终止

2.3.3 进程的阻塞和唤醒 ※

阻塞：找到PCB，保护现场，将PCB插入等待队列，下处理机

唤醒：找到PCB，移出等待队列，插入就绪队列

2.3.4 进程的挂起和激活*

2.4 进程通信

2.4.1 进程通信的类型

共享存储

消息传递

管道

客户机-服务器系统

套接字（socket）

远程过程调用（RPC）

2.5 线程

2.5.1 线程的引入

2.5.2 线程与进程的比较 ※

2.5.3 线程状态与线程控制块*

2.6 线程的实现*

2.6.1 线程的实现方式*

用户级线程

内核级线程

组合方式

2.6.3 线程的创建和终止*

第 3 章处理机调度与死锁

3.1 处理机调度概述

3.1.1 处理机调度的层次 ※

越底层越低级

低级调度：进程

中级调度：内存

高级调度：作业

3.1.3 进程调度

3.1.4 性能指标 ※

3.2 调度算法 ※

只有与时间片轮转相关的算法是抢占的

3.2.1 先来先服务 FCFS ※

First Come First Serve

非抢占式

简单、低效、长作业有利、CPU繁忙型有利

3.2.2 短作业优先 SJF ※

Short Job First

默认非抢占式

短作业有利，饥饿

3.2.3 优先级 ※

Priority-Scheduling

高响应比优先 Highest Response Ratio Next

非抢占式

短作业有利，不饥饿

3.2.4 时间片轮转 ※

Round Robin

抢占式

注意就绪队列的排序方法是先来先服务

当一个时间片结束时，刚好有新任务到达，那么在队列中，新任务在被剥夺时间片任务的前面

3.2.5 多级队列

Multileved Queue

3.2.6 多级反馈队列

Multileved Feedback Queue, FB

题目

假设一个系统中有5个进程，它们达到时间和服务时间如图所示，忽略I/O及其他开销时间，若分别按先来先服务（FCFS）、非抢占式及抢占式短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片大小为1）、 ~~多反馈队列调度算法（FB，第i及队列的时间片=2i-1）~~ 进行CPU调度，请给出各进程的完成时间、周转时间、等待时间、带权周转时间。

3.3 实时调度

3.3.3 最早截止时间优先 ※

开始截止时间不是Deadline，在开始截止时间前开始任务即可

如果任务错过，那么该任务就取消

抢占式、非抢占式都有

3.3.4 最低松弛度优先 ※

抢占式

两任务松弛度一样时，选择先到的那个（先来先服务）

题目

对下面的5个非周期性实时任务，按最早开始截止时间优先调度算法应如何进行CPU调度？

若有3个周期性任务，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为10ms；任务C要求每50ms执行一次，执行时间为15ms，应如何按最低松弛度优先算法对它们进行CPU调度？

3.5 死锁

3.5.1 资源问题

可重用资源：eg 设备、文件

可消耗资源：eg 进程间通信的信息

可抢占资源：eg 处理机、内存

不可抢占资源：eg 磁带机、打印机

3.5.2 死锁产生的原因

3.5.3 死锁的定义、条件和处理 ※

3.5.4 资源分配图 ※

3.6 死锁预防

3.7 死锁避免

3.7.1 系统安全状态 ※

3.7.2 银行家算法 ※

安全性算法

题目

Allocation 已分配的资源

Need 还需要的资源

Work 系统剩余资源

P2提出Request的意思是要求系统立即给它Request的资源

（1）该状态是否安全？
（2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

在银行家算法中,若出现下面的资源分配情况：

Process          Allocation           Need             Available
PO               0 0 3 2            0 0 1 2             1 6 2 2
P1               1 0 0 0            1 6 5 0
P2               1 3 5 4            2 3 5 6
P3               0 0 3 2            0 6 5 2
P4               0 0 1 4            0 6 5 6

(1)该状态是否安全?

(2)若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？

(3)如果系统立即满足P2的上述请求，请问，系统是否立即进入死锁状态?

(1)是，可以找到安全序列{P0,P3,P1,P2,P4}

(2)P2发出请求向量Request(1,2,2,2)后,系统按银行家算法进行检查:

①Request’(1,2,2,2) <=Need2(2,3,5,6)

②Request‘(1,2,2,2)<=Available(1,5,2,2)

③系统先假定可为P2分配资源并修改

Available=(0,3,0,0)

Allocation’=(2,5,7,6)

Need‘=(1,1,3,4)

④进行安全性检查:此时对所有的进程,条件Need_i<=Available(0,3,0,0)都不成立,即Available不能满足任何进程的请求,故系统进入不安全状态。

此时当进程P2提出请求Request(1,2,2,2)后,系统不能将资源分配给它。

(3)并没有马上进入死锁，因为上述进程没有申请新资源并因得不到资源而阻塞。只有当提出新的请求并导致所有没有执行完的多个进程因得不到资源而阻塞时，才死锁。

3.8 死锁的检测与解除

3.8.1 死锁的检测 ※

3.8.2 死锁的解除

第 4 章进程同步

4.1 进程同步的基本概念

4.1.1 进程同步概念的引入

4.1.2 临界区问题

4.2 软件同步机制

4.3 硬件同步机制

4.4 信号量机制

4.4.1 信号量机制介绍 ※

整形

记录型

AND型

信号量集

4.4.2 信号量的应用 ※

4.5 管程*

管程的定义

条件变量

4.6 经典的进程同步问题

4.6.1 生产者-消费者问题 ※

4.6.2 哲学家进餐问题 ※

4.6.3 读者-写者问题 ※

题目

试用记录型信号量写出一个不会死锁的哲学家进餐问题的算法。

semaphore chopsticks[]={1,1,1,1,1};
semaphore maxNum=4;
void philosopher(int i){
    while(true){
        wait(maxNum);
    	wait(chopsticks[i]);
    	wait(chopsticks[(i+1)%5]);
    	进餐();
    	signal(chopsticks[i]);
    	signal(chopsticks[(i+1)%5]);
    	signal(maxNum);
        思考();
    }
}

嗜睡的理发师问题：一个理发店由一个有N张沙发的等候室和—个放一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当—个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。试用信号量实现这一同步问题。

int sofaUsed=0;
semaphore sofaUsedMutex=0;
semaphore wake = 0;
semaphore beginPay=0, endPay=0;
semaphore cutRoom=0;

void customer(){
	wait(sofaUsedMutex);//等待修改sofaUsed
    if(sofaUsed>=N){
        signal(sofaUsedMutex);
        离开理发店;
    }else{
        sofaUsed++;
        signal(sofaUsedMutex);
        
        wait(cutRoom);//等待进入理发室
        wait(sofaUsedMutex); sofaUsed--; signal(sofaUsedMutex);
        signal(wake);//唤醒理发师
        理发;
        signal(beginPay);//通知理发师,我付费了
        wait(endPay);//等待理发师收费
        signal(cutRoom);//离开理发室
        
        离开理发店;
    }
}

void barber(){
    while(true){
        wait(wake);//等待唤醒
    	给顾客理发;
    	wait(beginPay);//等待顾客付费
    	signal(endPay);//通知顾客已收费
    }
}

某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。

(2)根据所定义的信号量，把应执行的wait/signal操作填入下面空中，以保证进程能够正确地并发执行。

parbegin  pmcess  PI(I＝1,2,....)
    begin
    (_______)
    进入售票厅
    购票
    退出； 
    (_______)
    end；
parend;

答：

(1) 定义一信号量S，初始值为20。

S>0时s的值表示可继续进入售票厅的人数

S＝0时表示售票厅中已有20名顾客

S<0则|S|值为等待进入售票厅的人数

(2) 上框为P(S)、下框为V(S)

semaphore plate=1, apple=0, orange=0;
void father(){
	while(true){
        wait(plate);//等待获取盘子
        放苹果;
        signal(apple);//通知吃苹果
    }
}
void mother(){
	while(true){
        wait(plate);
        xxx;
        signal(banana);
    }
}
void son(){
    while(true){
        wait(orange);//等待吃橘子
        吃橘子;
        signal(plate);//通知父母拿盘子
    }
}
void daughter(){
    while(true){
        wait(apple);
        xxx;
        signal(plate);
    }
}

有P1，P2，…，Pm等m个生产者进程和CA，CB两个消费者进程。它们共享可存放一个产品的缓冲区BUFFER。序号为奇数的生产者进程生产的产品供CA消费，而序号为偶数的生产者进程生产的产品供CB消费，CA或CB一旦取出产品，则各生产者均有权申请向BUFFER存放产品。试用PV操作正确实现进程的并发执行.

semaphore buffCA=0, buffCB=0, buff=1;

void P(int i){
	while(true){
        生产;
        wait(buff);
        将产品放入缓冲区;
        if(i%2==1) signal(buffCA);
        else signal(buffCB);
    }
}

void CA(){
    while(true){
        wait(buffCA);
        从缓冲区取出产品;
        signal(buff);
        消费;
    }
}

void CB(){
    while(true){
        wait(buffCB);
        从缓冲区取出产品;
        signal(buff);
        消费;
    }
}

第 5 章存储器管理

5.1 存储器的层次结构

5.2 程序的装入与链接

5.2.1 地址绑定和内存保护

5.2.2 程序的装入

5.2.3 程序的链接

5.3 对换与覆盖

5.3.3 进程的换出和换入

5.4 连续分配存储管理方式

5.4.1 单一连续分配

5.4.2 固定分区分配

5.4.3 动态分区分配 ※

5.4.4 动态重定位分区分配

题目

某系统采用动态分区分配方式管理内存，内存空间为640K，高端40K用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业l申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K、作业6释放60K，请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况。

实际过程不用那么复杂，草稿纸上模拟一下算法，很快能得出答案

Screenshot_2024_01_04_18_55_39_15_8b7aa5be40a89c6a7df806c347da652a

Screenshot_2024_01_04_18_55_48_90_8b7aa5be40a89c6a7df806c347da652a

5.5 分页存储管理方式

5.5.1 分页存储管理的基本方法 ※

5.5.2 地址变换机构 ※

5.5.3 引入快表后的内存有效访问时间*

5.5.4 两级页表和多级页表

题目

已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。

(1)将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。

(2)以十进制的逻辑地址1023为例画出地址变换过程图。

5.6 分段存储管理方式

5.6.1 分段存储管理方式的引入

5.6.2 分段系统的基本原理 ※

5.6.3 信息共享

题目

Screenshot_2024_01_04_19_27_04_76_8b7aa5be40a89c6a7df806c347da652a

5.7 段页式存储管理方式

第 6 章虚拟存储器

6.1 虚拟存储器概述

6.1.1 传统存储器和局部性原理

6.1.2 虚拟存储器的定义和特征

6.1.3 虚拟存储器的实现方法

6.2 请求分页存储管理方式

6.2.1 请求分页中的硬件支持

6.2.2 请求分页中的内存分配

6.2.3 页面调入策略

6.3 页面置换算法

6.3.1 最佳先进先出 ※

6.3.2 最近最久未使用最少使用 ※

6.3.3 Clock 页面置换算法

6.3.5 请求分页系统的内存有效访问时间

题目

在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M为3时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时访问过程中所发生的缺页次数和缺页率，并比较所得的结果。

在这里插入图片描述

FIFO：共发生 9次缺页中断缺页率=9/12=75%
LRU：共发生 10次缺页中断缺页率=10/12=83.3%
OPT：共发生 7次缺页中断缺页率=7/12=58.3%

6.4 抖动与工作集

6.4.1 抖动

6.4.2 工作集

6.5 请求分段存储管理方式

6.5.1 请求分段中的硬件支持

6.5.2 共享和保护

第 7 章输入/输出系统

7.5 与设备无关的I/O软件

7.5.3 设备分配与回收 ※

题目

简述设备分配与回收过程。

Screenshot_2024_01_04_23_59_43_07_a6a4b4a15f5a4604d9f3d59bae0c772c

7.5.4 逻辑设备名映射到物理设备名 ※

7.6 用户层的I/O软件

7.6.2 假脱机系统 SPOOLing ※

题目

以打印机为例说明SPOOLing的工作原理，系统如何利用SPOOLing技术将打印机模拟为虚拟打印机。

7.7 缓冲区管理

7.7.1 缓存和缓冲

7.7.2 单缓冲双缓冲 ※

7.7.3 环形缓冲 ※

7.7.4 缓冲池 ※

7.8 磁盘性能和调度

7.8.1 概述

7.8.2 先来先服务最短寻道时间优先 ※

7.8.3 扫描循环扫描 ※

题目

假设磁盘有200个磁道，磁道请求对列中是一些随机请求，它们按照到达的次序分别处于55、58、39、18、90、160、150、38、184号磁道上，当前磁头在100号磁道上，并向磁道号增加的方向上移动。请给出按FCFS、SSTF、SCAN及CSCAN算法进行磁盘调度时满足请求的次序，并计算出它们的平均寻道长度。

Screenshot_2024_01_04_21_14_23_14_a6a4b4a15f5a4604d9f3d59bae0c772c