计算机操作系统复习提纲

Jun 18, 2017 | Document | 阅读

基本概念

并发-同一时间段
并行-同一时刻

OS

特征：并发、共享、虚拟、异步
定义：配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。
目的方便性、有效性、可扩充性、开放性
作用作为用户和计算机系统之间的接口；OS计算机资源管理者；对计算机资源的抽象

处理机调度

高级调度

长程调度，作业调度作业外存后备队列的作业调入内存

中级调度

短程调度，进程调度进程内存进程队列调入CPU

低级调度

内存调度进程存储管理器的对换功能

作业管理

批处理系统作业管理

先来先服务（FCFS）
短作业优先（SJF）
优先级调度算法（PSA）
高响应比优先调度算法（HRRN）：优先级=（等待时间+要求服务时间）/要求服务时间等于戴荃周转时间

优先级倒置

起因
解决办法

进程管理

进程与线程

进程：重型进程。是进程实体运行过程，占有系统资源，是系统进行调度的独立单位。
PCB: 进程控制块。1、进程标识符 2、处理机状态 3、进程调度信息 4、进程控制信息 5、PCB组织信息
特征：动态性、并发性、独立性、异步性
五种状态：创建、就绪、运行、阻塞、终止

线程：轻型进程、进程元。不占用资源，是分派和调度的基本单元。是可运行的基本单元。
TCB

进程调度

非抢占式
抢占式优先权原则、短进程优先、时间片原则

调度算法原则

资源利用率： CPU利用率=（CPU工作时间）/（CPU有效工作时间+等待时间）
公平性：每个进程都获得合理的CPU时间
平衡性：使各个资源或者内外设备，都处于忙碌状态，保持资源使用的平衡性。
策略强制执行：有安全策略的准确执行，不惜延迟某些工作。

实时调度

最早截止时间优先（EDF）：非抢占式和抢占式
最低松弛度优先（LLF）：松弛度=截止时间-本身运行时间-当前时间松弛度为0时进行抢占。

进程同步与互斥

进程同步

对多个相关进程在执行次序上进行协调，使并发执行的诸进程能按照一定的规则共享系统资源，并很好的合作，从而使程序执行有再现性。

生产者和消费者问题
「• proceducer:
• wait(empty); • wait(mutex);
• 。。。。。
• signal(mutex); • signal(full);
」

「• consumer:
• wait(full); • wait(mutex);
• 。。。。。
• signal(mutex); • signal(empty);
」

直接相互制约关系

间接相互制约关系

临界资源

互斥

• Mutex=1
• 临界区互斥访问
• wait(mutex)和signal(mutex)

临界区

临界资源，还称软件临界资源，多个进程必须互斥地对临界资源进行访问。把在每个进程中访问临界资源的那段代码称为临界区
进程中除上述进入区、临界区及退出区之外的其它部分的代码，在这里都称为剩余区。这样，可把一个访问临界资源的循环进程描述如下:
「进入区
临界区
退出区
剩余区」

信号量

表示资源数量的S

PV操作

P -> Wait(S–)
V -> Signal(S++)

AND同步机制

• 基本思想是:将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。
• Swait(S1，S2，…，Sn)

进程控制块PCB

死锁

定义

有一组进程，该组中任意一个进程都在等待该组其他进程占有的资源，但是由于不能满足资源条件而永久的等待下去。

原因

多个进程对于资源的抢夺（不可抢占资源、可消耗资源），不合法的对资源进行申请和释放的顺序。

四个条件

互斥条件：进程对该资源只能互斥的访问，即在一段时间内只允许一个进程访问该资源。

请求和保持条件：进程已经获得某些资源时，请求新的资源，新资源被其他进程占据，此进程阻塞，保持对已有资源的占有

不可抢占：进程已经获得的资源只能由该进程自己释放，不可被抢占

循环等待：发生死锁时，进程-资源形成一个循环链，数学描述

预防

第一种协议：统一申请所有资源

第二种协议：分段的统一申请部分资源，申请前释放已占有的资源。

破坏不可抢占原则

避免

银行家算法：

解除

资源分配图

P -> R 资源请求
R -> P 资源分配
圆圈指向圆圈

存储管理

页式存储管理

它含有两部分:前一部分为页号P，后一部分为位移量W(或称为页内地址)。图中的地址长度为32位，其中0~11位为页内地址，即每页的大小为4 KB;12~31 位为页号，地址空间最多允许有1 M页。

逻辑页物理块

基本的地址变换机构：逻辑地址->越界终端->页表寄存器->页表->物理地址
有块表的地址变换机构：逻辑地址->块表->越界终端->页表寄存器->页表->物理地址

虚拟存储技术

虚拟存储器：具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种虚拟存储系统。
– 请求、置换：
请求页表机制：页号+物理块号+状态位+访问字段+修改位+外存地址

– 逻辑扩展内存

页面置换算法

– 最佳置换算法：不可实现
– 先进先出置换算法：顾名思义
– 最近最久未使用(LRU)置换算法：

最少使用置换算法(LUR):

设备管理

设备独立性

设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配释放等，同时为设备管理和数据传送提供必要的存储空间。

I/O软件组成

I/O软件的层次结构

虚拟设备

通道技术

假脱机技术

在联机情况下实现的同时外围操作的技术位SPOOLing。
多道程序技术一种一道模拟外围机输入，一道模拟外围机输出。

四部分

输入井、输出井：磁盘上，高速外存
输入缓冲区、输出缓冲区：内存上，缓和CPU和磁盘之间速度不匹配
输入进程、输出进程：顾名思义
井管理程序：用于控制作业与磁盘井之间的信息交换

缓冲技术

原因：

缓和CPU与I/O设备的速度不匹配问题

减少对CPU的中断频率

数据粒度不匹配问题
单缓冲区
T: 数据传入缓冲区的时间
M: 缓冲区数据传到用户区的时间
C: CPU处理数据的时间

效率为MAX(C,T)+M

双缓冲区

Nextg: 消费进程下一个可用的缓冲区
Nexti: I/O进程下一个可用的缓冲区
Current: 消费进程当期使用的缓冲区

Nexti 追上 Nextg : 输入进程速度大于计算进程
Nextg 追上 Nexti : 计算进程速度大于输入进程

缓冲区工作方式

emq: 空队列
inq: 输入队列
outq: 输出队列
house 收容 s
hin: 收容输入 GetBuff(emq) 装载 PutBuff(inq,hin)
sin: 提取输入 GetBuff(inq) 计算 PutBuff(emq,sin)
hout: 收容输出 GetBuff(emq) 装载 PutBuff(outq,hout)
sout: 提取输出 GetBuff(outq) 输出 PutBuff(emq,sout)

磁盘调度

磁盘定位

三维定位：盘片+磁道+扇区

磁盘调度算法

先来先服务（FCFS）：
最短寻到时间优先(SSTF): 剩下读写操作中寻道最短为先。
扫描算法(SCAN): 从里扫到外，最里到最外。
循环扫描算法(CSCAN): 最小磁道号与最大磁道号构成循环。从里到外，从离到外。

经典问题