操作系统复习大连理工大学城市学院

针对城院操作系统的复习大纲，数据传输得基本单位是数据块、嗦传输得数据是从设备直接送人内存得，或者相反。

操作系统复习

第一章

操作系统目标

方便性

有效性

可扩充性

开放性

操作系统基本特征p22

并发

并行性

两个或多个事物在同一时刻发生

并发性

两个或多个事物在同一时间间隔内发生

引入进程

共享

互斥共享方式

打印机等，同一时间段内只能一个进程访问

同时访问方式

允许多个进程“同时”访问（微观上交替访问）

虚拟

异步

1.4操作系统主要功能

1.4.1处理机管理功能

进程控制

为作业创建进程、撤销已结束的进程、控制进程在运行中的转换状态

进程同步

进程通信

调度

作业调度

进程调度

1.4.2存储器管理功能

内存分配

内存保护

地址映射

内存扩充

请求调入功能

置换功能

1.4.3设备管理功能

缓冲管理

设备分配

设备处理

1.4.4文件管理功能

文件存储空间的管理

目录管理

文件的读/写管理和保护

1.5 OS结构设计

1.5.4 微内核OS结构

基本概念（特征）

为提高操作系统

正确性

灵活性

易维护性

可扩充性

足够小的内核

能实现最基本的功能，通常包含

与硬件处理紧密相关的部分

一些较基本的功能

客户和服务器之间的通信

基于客户/服务器模式

应用“机制与策略分离”原理

采用面向对象技术

微内核的基本功能

进程（线程）管理

低级存储器管理

中断和陷入处理

优点：

系统可扩展性提升

系统可靠性提升

可移植性强

提供了分布式系统的技术

融入了面向对象技术

第二章

进程的定义和特征

由程序段、相关的数据段、PCB三部分构成了进程实体，进程实体简称为进程。创建进程，实质上是创建进程实体中的PCB；撤销进程，实质上是撤销进程的PCB

进程的定义

进程是程序的一次执行

进程是一个程序及其数据在处理机上顺序执行时所发生的活动

进程时具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

进程的特征

动态性

并发性

独立性

异步性

进程的基本状态及转换

三种基本状态

就绪（Ready）状态

执行（Running）状态

阻塞（Block）状态

三种基本状态的转换p46

临界区p59

信号量机制

整型信号量

记录型信号量p62（代码记住）

S->value的初值表示系统中某资源的数目，故称为资源信号量

S.value--：系统中可分配的该类资源减少一个

S.value<0时，表示该类资源已分配完毕

S.value：系统中可供分配的该类资源数增加一个

若加一后仍是S.value<=0，则表示该信号量链表中仍有等待该资源的进程被堵塞

若S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥

p65两段代码

2.5.1 生产者消费者问题 P69代码

第三章

先来先服务、短作业优先、高响比优先

3.3 进程调度

3.3.1 进程调度的任务、机制和方式

进程调度的任务

保存处理机的现场信息

按某种算法选取进程

把处理器分配给进程

进程调度机制

排队器

分派器

上下文切换器

进程调度方式

非抢占方式

抢占方式

抢占优先原则

优先级高的抢占

短进程优先原则

更短时抢占

时间片原则

按时间片轮转运行

3.3.2 轮转调度算法（PR调度算法）p102

基本原理

进程切换时机

时间片大小的确定

小时间片，有利于短作业

大时间片，有利于长作业

3.3.3 优先级调度算法

把处理机分配给就绪队列中优先级最高的进程

优先级调度算法类型

非抢占式优先级调度算法

抢占式优先级调度算法

优先级类型

静态优先级

依据：

进程类型

进程对资源的需求

用户要求

动态优先级

3.3.4 多级队列调度算法

3.3.5 多级反馈队列

3.3.6 基于公平原则的调度算法

3.6 预防死锁

3.6.1 破坏“保持和请求”条件

第一种协议

所有进程在开始之前，必须一次性的申请其在整个运行过程中的全部资源

缺点：

资源被严重浪费，严重恶化了资源的利用率

使进程经常会发生饥饿现象

第二种协议

对第一种的改善

允许一个进程只获得运行初期所需资源后，便开始运行。进程运行过程中再逐步释放分配给自己的、且已用毕的全部资源，然后在请求新的所需资源

3.6.2 破坏“不可抢占”条件

当一个已经保持了某些不可被抢占的资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请

3.6.3 破坏“循环等待”条件

为每个资源类型赋予唯一的序号，在对系统所有资源类型进行线性排序后，便可采用这样的预防协议：规定每个进程必选按序号递增的顺序请求资源。

3.7 避免死锁

3.7.2 银行家算法避免死锁

算法中数据结构

银行家算法

安全性算法

进程与程序的区别与联系

(1). 进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序，离开程序的进程没有存在的意义。从静态角度看，进程是由程序、数据和进程控制块（PCB）三部分组成的。而程序是一组有许多指令集合，是一种静态的概念

(2). 进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定生命周期，是暂时存在的；而程序是一组代码的集合，是永久存在的，可长期保存

(3). 一个进程可以执行一个或几个程序，一个程序也可构成多个进程。进程可创建进程，而程序不可能形成新的程序

(4). 进程与程序的组成不同。进程是组成包括程序、数据和PCB

第四章

4.3 连续分配管理方式

4.3.1 单一连续分配

4.3.2 固定分区分配

划分方法

分区大小相等

分区大小不等

内存分配

4.3.3 动态分区分配（可变分区分配）

动态分区分配中的数据结构

动态分区分配算法

分区分配操作

分配分区

回收内存

4.3.4 基于顺序搜索的动态分区分配算法

1. 首次适应（first fit, FF）算法

2. 循环首次适应（next fit, NF）算法

3. 最佳适应（best fit, BF）算法

4. 最坏适应（worst fit, WF）算法

4.3.6 动态可重定位分区分配

1. 紧凑

2. 动态重定位

3. 动态重定位分区分配算法

4.5 分页存储管理方式

4.5.1 基本方法

1. 页面和物理块

2. 地址结构

31~12 页号P，11~0 位移量W

3. 页表

存储每个页面所对应的物理块的映射表

4.5.2 地址变换机构

将逻辑地址转换为物理地址

基本的地址变换机构

具有块表的地址变换机构

先访问块表，再访问普通页表

4.5.3 访问内存的有效时间

从进程发出访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据所花费的总时间

未引入块表

ETA=2t

第一次访问页表t+第二次访问内存时间t

引入块表

ETA=a*λ+(t+λ)(1-a)+t=2t+λ-t*a

λ：访问块表时间，a：块表命中率

4.5.4 两级或多级页表

两级页表

适合32位机器

多级页表

适合64位机器

4.5.5 反置页表

为每一个物理块设置一个页表项

地址变换

4.6 分段存储管理方式

基本原理

分段

段表

地址变换机构

分页和分段的主要区别

页是信息的物理单位

页大小固定且由系统决定

分页的用户程序地址空间是一维的

4.6.3 信息共享

分页系统中

分段系统中

4.6.4 段页式存储管理方案

基本原理

地址变换过程

第五章

5.3 页面置换算法

最佳(Optimal)置换算法

无法实现，用来评判其他算法

所选被淘汰页面将是以后用不使用的，或是在最长时间内不被访问的页面

先进先出（FIFO）页面置换算法

淘汰最先进入内存的页面，即选择在内存驻留时间最久的页面予以淘汰

最近最久未使用和最少使用置换算法算法

Clock算法

页面缓冲算法

第八章

8.1 外存的组织方式

连续组织（分配）方式

优点

顺序访问容易

顺序访问速度快

缺点

要求为一个文件分配连续的存储空间

必须事先知道文件的长度

不能灵活地删除和插入记录

对于那些动态增长的文件，很难为其分配空间

8.1.2链接组织方式

隐式链接

链表

显式链接

将所有指针存在一张表中

8.1.3 FAT技术

FAT12

FAT16

FAT32

NTFS文件组织方式

新特征

64位磁盘地址

支持长文件名

单个文件名255字符以内，全路径名为32767个字符

具有系统容错功能

保证系统中的数据唯一性

文件加密、文件压缩等

磁盘组织

以簇作为磁盘空间分配回收的基本单位，一个文件占用若干个簇，一个簇只属于一个文件。

文件的组织

索引组织方式

单级索引组织方式

多级索引方式

增量式索引方式

依据文件大小选择文件索引方式

8.2 文件存储空间管理

空闲表法

空闲链表法

位示图法

成组连表法

空闲盘块的组织

空闲盘块的分配与回收

第七章

7.2.1 文件逻辑结构的类型

按文件是否有结构分类

有结构文件

定长记录

变长记录

无结构文件

流式文件

按文件组织方式分类

顺序文件

索引文件

索引顺序文件

第六章

4.6.3 对I/O设备的控制方式

使用轮询的可编程I/O方式

使用中断的可编程I/O方式

直接存储器访问方式（DMA方式）

特点

数据传输的基本单位是数据块

所传输的数据是从设备直接送入内存的，或者相反

仅在传输一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传输是在控制器是控制之下完成的

I/O通道方式

将DMA方式的一个数据块升为一组数据块

6.7 缓冲区

6.7.1 缓冲的引入

缓和CPU与I/O设备间速度不匹配的矛盾

减少对CPU的中断频率，放宽对CPU中断响应事件的限制

解决数据粒度（数据单元大小）不匹配的问题

提高CPU和I/O设备之间的并行性

6.7.2 单缓冲区和双缓冲区

单缓冲区

6.7.3 环形缓冲区

Getbuf 用于找到下一个工作区C

Releasebuf 用于找到下一个空闲区R

6.7.4 缓冲池

空白缓冲队列emq

输入队列inq

输出队列outq

6.8 磁盘调度算法

6.8.2 早期的磁盘调度算法

先来先服务 FCFS

最短寻道时间优先 SSTF

基于扫描的磁盘调度算法

扫描（SCNA）算法

循环扫描（CSCAN）算法

3.