第一章 操作系统引论

操作系统功能：

1. 资源管理：协调、管理计算机的软、硬件资源，提高其利用率。

2. 用户角度：为用户提供使用计算机的环境和服务。

操作系统特征：1.并发性：指两个或多个事件在同一时间间隔内发生。

2.共享性：资源可供内存中多个并发执行的进程(线程)共同使用

3.虚拟性：是指通过某种技术把一个物理实体变为若干个逻辑上的对应物

在操作系统中，虚拟的实现主要是通过分时使用的方法。

4.异步性：进程是以人们不可预知的速度向前推进，此即进程的异步性

客户/服务器模式的优点：

1.提高了系统的灵活性和可扩充性

2.提高了OS的可靠性

3.可运行于分布式系统中

微内核的基本功能：

进程管理、进程间通信、存储器管理、 低级I/O功能。

第二章 进程

程序和进程区别： 程序是静止的，进程是动态的，进程包括程序和程序处理的对象

程序顺序执行：顺序性，封闭性，可再现性

程序并发执行：间断性，无封闭性，可再现性

进程： 1.进程是可并发执行的程序的一次执行过程；

2.是系统进行资源分配和调度的一个独立的基本单位和实体；

3.是一个动态的概念。

进程的特征： 1.动态性：

进程是程序的一次执行过程具有生命期；

它可以由系统创建并独立地执行，直至完成而被撤消

2.并发性；

3.独立性；

4.异步性；

进程的基本状态：

1.执行状态；

2.就绪状态；

3.阻塞状态；

进程控制块PCB： 记录和描述进程的动态特性，描述进程的执行情况和状态变化。

　　　 是进程存在的唯一标识。

进程运行状态： 1.系统态 （核心态，管态） 具有较高的访问权，可访问核心模块。

2.用户态 （目态 ） 限制访问权

进程间的约束关系：

1.互斥关系

进程之间由于竞争使用共享资源而产生的相互约束的关系。

这种因共享资源而产生的制约关系称为进程的互斥。— 间接相互制约关系

2.同步关系

并发执行进程之间通过在执行时序上的某种限制而达到相互合作的这种约束 关系称为进程的同步 — 直接相互制约关系

临界资源：凡是以互斥方式使用的共享资源都称为临界资源。临界资源具有一次只允许一个进程使用的属性。

临界区：每个进程互斥访问临界资源的那段代码称为临界区。

进程通信： 直接通信：发送进程通过收、发原语直接将消息发送到接受进程的消息缓冲区。

间接通信:发送进程将消息发送到电子邮箱，接受进程再从中取出消息。

P操作（wait 原语）[P-≥]

S.value ：= S.Value - 1；

若 S.Value ≥ 0 进程继续执行。

若 S.Value < 0 进程阻塞

V操作（Signal原语）[V+>]

S.value ：= S.Value + 1；

若 S.Value > 0 进程继续执行。

若 S.Value ≤ 0 进程就绪

第三章 调度与死锁

进程调度的方式：

1.非抢占式（非剥夺式）：

进程 一旦被调度 ，就一直占有CPU，直到完成或因发生某事件而被阻塞（I/O请求）。

2.抢占式（剥夺式）

进程未执行完，可由调度程序剥夺其CPU，另分配给别的进程。

抢占的原因有：优先级、时间片、短进程等

进程调度的功能：1.记录系统中所有进程的执行情况

2.确定分配处理机的原则（调度算法）

3.分配处理机给进程

4.回收处理机、进行进程上下文切换

调度算法：1.先来先服务（FCFS）算法

　　　 2.最短CPU运行期优先（SCBF）算法

　　　 3.最高优先权（HPF）算法

　　　 4.时间片轮转（RR）算法

　　　 5.多级反馈队列算法

产生死锁原因： 1.竞争资源

2.进程推进顺序不当

产生死锁的必要条件：

1.互斥条件： 进程互斥使用临界资源

2.不剥夺条件： 资源只能由占有它的进程释放，不能被其它进程剥夺

3.请求保持条件： 进程在申请新资源的同时，保持对某些资源的占有。

4.环路等待条件：存在循环等待链，在链中每个进程在等待它的前一进程所持有的资源。

解决死锁的方法：

1.预防死锁:限制并发进程对于资源的需求，破坏产生死锁的必要条件。严格限制死锁的发生。

2.避免死锁:在资源的动态分配过程中，采用某种算法防止系统进入不安全状态，避免死锁发生。

3.检测与解除死锁对资源的分配不加限制，系统定时运行“死锁检测”程序，如检测到死锁，设法加以解除。

死锁解除的方法：

(1) 撤消陷于死锁的全部进程。

(2) 逐个撤消陷于死锁的进程，直到死锁不存在。

(3) 从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。

第四章 存储器管理

静态重定位：将逻辑地址转换为物理地址的过程，也称为地址变换或地址映射。

动态重定位：在作业运行过程中进行地址转换，将程序的地址（逻辑地址）转换为内存的物理地址。进程在内存中的地址是可变的，并可动态申请内存空间。

存储管理的基本功能：分配和去配，抽象和影射，隔离和共享，存储扩充。

程序的装入：1、绝对装入方式

　　 直接用物理地址编制程序。

2、可重定位装入方式（静态重定位）

　　 重定位——将逻辑地址转换为物理地址的过程，也称为地址变换或地址映射。

3、动态运行时装入方式（动态重定位）

在作业运行过程中进行地址转换，将程序的地址（逻辑地址）转换为内存的物理地址。进程在内存中的地址是可变的，并可动态申请内存空间。

连续分配存储管理方式：

1、 固定分区分配

　　分区长度和个数将不再变化。建立内存分配表记录分区分配的情况。

2、 动态分区分配

　　根据用户实际需要，动态的分配连续空间。建立已分配分区表及未分配分区表。

　 回收分区采用拼接技术,紧凑技术

分区分配算法：

1.首次适应算法FF

未分配分区按地址从小到大排列。分配时顺序查找，选择第一个满足要求的分区进行分配。

2.最差适应算法

按空闲区大小升序排列，分配时顺序查找，选择第一个满足要求的最小分区进行分配。

3.最佳适应算法BF

按空闲区大小升序排列，分配时顺序查找，选择第一个满足要求的最小分区进行分配。

离散分配存储管理方式：

1、页式存储管理　　

2、段式存储管理　

3、段页式存储管理

实存管理方案的主要问题：

1、要求作业一次装入，造成内存资源的浪费。

2、用户编程的地址空间（逻辑空间）不能超过实际的内存空间，无法运行很大的应用程序。

请求分页式存储管理：

在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，再根据进程需要，装入其他页面：当内存空间已满，而又需要装入其他页面时，就需根据某种算法淘汰某个页面，重新装入新的页面

虚拟存储管理的基本思想：

１、用大容量的外存来对内存空间进行逻辑扩充扩充，为用户提供一个比实际内存空间大得多的虚拟内存空间。

２、基于程序的局部性原理，采用 “部分装入”、“部分交换” 的策略。

分页管理内存分配：

将地址空间连续划分为大小相等的页面，将内存空间也划分为与页面大小相等的物理块（页框），

作业的页面部分装入，不连续存放。仅存在很少的页内零头。

页面置换算法： 1.FIFO算法：

　　 是一种最简单的淘汰算法，首先淘汰在内存中驻留时间最长的页面。

2.LRU（Least Recently Used）算法：

即最近最久不使用页面的淘汰算法

第五章 设备管理

I/O系统应该由以下部分组成： 1.I/O设备 2.设备控制器 3.总线或通道

I/O控制方式：1.程序直接控制 2.中断控制方式 3.DMA控制方式 4.通道控制方式

为什么引入缓冲技术：

1.缓解CPU与外设速度不匹配的问题。

2.减少CPU中断响应次数，放宽响应时间。

3.提高CPU与I/O设备，I/O设备之间的并行操作能力。

缓冲技术的基本思想：

在内存中开辟一个或多个专用区域（缓冲区），作为CPU 与I/O设备间信息的集散地。

缓冲区的组织：1.单缓冲区（single buffer）2.双缓冲区（double buffer）

3.循环缓冲（circular buffer）

当输入与输出的速度基本相配时，采用双缓冲能获得较好的效果。

但若两者的速度相差较大，双缓冲效果则不够理想。

4.缓冲池（buffer pool）

缓冲池的组成 ：1.空闲缓冲区2.装满输入数据的缓冲区3.装满输出数据的缓冲区

缓冲池的工作方式 ：

1.收容输入（hin）工作方式（输入进程需要输入数据时）

2.提取输入（sin）工作方式（计算进程需要输入数据时）

3.收容输出（hout）工作方式（计算进程需要输出数据时)

4.提取输出（sout）工作方式（输出进程需要输出数据时）

输入输出设备 缓冲池 用户程序

收容：数据流向为输入输出设备与用户程序到缓冲池

提取：数据流向为缓冲池到输入输出设备与用户程序

输入：从左向右流动

输出：从右向左流动

虚拟设备管理基本思想： 用大容量的快速设备（磁盘）模拟慢速度的

独占设备，把一台物理上的独占设备变为逻辑上的多台共享设备。

SPOOLing（虚拟设备技术）系统的组成:

1.输入井、输出井; 2.输入进程、输出进程; 3.I/O缓冲区

驱动程序执行步骤：

1、服务请求校验 确定请求的操作，检验硬件支持。

2、确认设备状态 确定设备（状态寄存器）是否可用。

3、启动I/O请求 若确认设备状态可用，启动I/O。

4、中断处理 CPU处理I/O过程的中断。驱动程序应保存处

理器的当前状态，以便进程重新执行。

5、I/O请求完成 驱动程序识别I/O完成，将控制返回IOCS，

将被中断的进程置为就绪。

磁盘的访问时间：

1.寻道时间Ts (Seek Time)

Ts = m*n + S 　m —常数（一般0.2，高速小于0.1）

　　　　　　S — 磁盘启动时间 n — 磁头移动磁道数

2.旋转延时Tr (Rotational Delay)

Tr ＝1/(2r) r— 磁盘每秒转数。

3.数据传输时间Tt (Transfer Time)

　　 Tt = b/ rN 　　 b-每次所读/写的字节数 N-每个磁道上的字节数

常用的调度算法：

1 先来先服务（FCFS）按照申请服务的先后次序。未考虑寻道优化。

优点：公平、简单，每个进程的请求都能依次得到处理。

缺点：未对寻道进行优化，平均寻道时间可能较长。

FCFS算法仅适用于请求磁盘I/O的进程数目较少的场合。

⑵ 最短寻道优先算法（SSTF）优先选择离磁头最近的请求。未考虑磁头来回摆动。

可能出现老进程的“饥饿”现象。

⑶ 扫描算法（SCAN）(电梯法)既考虑请求与磁头的距离，又考虑磁头移动的方向；

⑷ 循环扫描算法（C-SCAN）

规定磁头单向移动，即将最小磁道号与最大磁道号构成循环，进行循环扫描。

提高磁盘I/O速度的技术：

⑴磁盘高速缓存（Disk Cache)

把磁盘I/O缓冲区叫做磁盘高速缓存（Disk Cache），磁盘I/O缓冲区仍然是内存中的一个区域。其工作原理类似Cache Memory。

⑵提前读（Read Ahead)与延后写（Write Postponing） ⑶RAID技术

第六章 文件系统

文件结构：1.逻辑结构2.物理结构

外存分配方法：

1、  连续分配——将文件信息存放在连续编号的物理块中。

优点：结构简单，存取速度快。

缺点：长度事先确定，随后不允许增加长度。

2、  链接分配——将文件信息存放在非连续编号的物理块中。

优点：插入、删除方便，文件长度可变。

缺点：查找困难。

3、  索引文件 优点：可以随机存取。缺点：增加空间的开销。

文件控制块（FCB）：是用于控制和描述文件的数据结构

1.基本信息：文件名、文件物理位置、文件的逻辑结构、文件的物理结构。

2.存取控制信息：用户的存取控制权（S、O、G、W）。

3.使用信息：文件建立、修改的日期时间，当前使用信息。

索引结点：为了提高检索的速度，减少所需内存空间，将文件的描述信息单独构成一个数据结构—索引结点。

空闲存储空间的管理方法：1、空闲表法2、空闲链表法3、位示图法4、成组链接法

多种资源的银行家算法:?

可变分区存储管理

1.可变式分区是指在作业装入时，依据它对内存空间实际的需求量来划分内存的分区，

因此，每个分区的尺寸与进入它的作业大小相同。

2.它能有效解决固定式分区的内部碎片问题，是一种较为实用的存储管理方法。

3.因为在系统运行过程中，内存中分区的数目和大小都是可变的，所以这种可变式分区也称为动态分区。

操作系统知识点整理