# 进程管理

# 进程状态转换图

#

# 前驱图

前驱图是一个有向无循环图，记为DAG。用于这种图可以描述多个程序或进程之间的执行顺序关系。

• 〇 表示一个程序、进程或是语句的结点。
• → 表示结点间的执行顺序。

# PV操作

临界资源：进程间需要互斥方式对其进行共享的资源 临界区：每个进程中访问临界资源的那段代码称为临界区 信号量：是一种特殊的变量

# 死锁问题

互斥，保持等待，不剥夺，环路等待

避免死锁的方法：

有序分配资源， 银行家算法

# 存储管理

分区存储组织，页式存储，段式存储，段页式存储

页面淘汰算法

最优（Optimal，OPT）算法 随机（RAND）算法 先进先出（FIFO）算法：有可能产生“抖动”与Belady奇异现象。

最近最少使用（LRU）算法：LRU的理论依据是“局部性原理”。要求较多硬件支持，成本高。 CLOCK算法：LRU近似算法。 简单CLOCK算法：循环队列，每页有访问位，淘汰访问位为0的页。 改进型CLOCK算法：同时考虑访问位与修改位。 时间局部性：刚被访问的内容，立即又被访问。 空间局部性：刚被访问的内容，临近的空间很快被访问。

程序访问具有时间局部性，即最近将要用的信息很可能是正在使用的信息

程序访问具有空间局部性，即最近将要用的信息很可能与正在使用的信息在存储空间上是相邻的

程序访问局部性是构成层次结构的存储系统的主要依据

存取方式

存储器中数据常用的存取方式有顺序存取、直接存取、随机存取和相联存取等4种。

（1）顺序存取：存储器的数据以记录的形式进行组织。对数据的访问必须按特定的线性顺序进行。磁带存储器采用顺序存取的方式。

（2）直接存取：与顺序存取相似，直接存取也使用一个共享的读写装置对所有的数据进行访问。但是，每个数据块都拥有唯一的地址标识，读写装置可以直接移动到目的数据块的所在位置进行访问。存取时间也是可变的。磁盘存储器采用直接存取的方式。

（3）随机存取：存储器的每一个可寻址单元都具有自己唯一的地址和读写装置，系统可以在相同的时间内对任意一个存储单元的数据进行访问，而与先前的访问序列无关。主存储器采用随机存取的方式。

（4）相联存取：相联存取也是一种随机存取的形式，但是选择某一单元进行读写是取决于其内容而不是其地址。与普通的随机存取方式一样，每个单元都有自己的读写装置，读写时间也是一个常数。使用相联存取方式，可以对所有的存储单元的特定位进行比较，选择符合条件的单元进行访问。为了提高地址映射的速度，Cache采取相联存取的方式。

# 文件管理

索引文件结构

位示图法

某文件管理系统在磁盘上建立了位示图（bitmap），记录磁盘的使用情况。

若磁盘上物理块的编号依次为：0、1、2、…；系统中的字长为32位，字的编号依次为：0、1、2、…，

字中的一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用，

如下图所示。假设操作系统将2053号物理块分配给某文件，那么该物理块的使用情况在位示图中编号为 64 ，系统应该将该字的位号5的位置“1"

2053号物理块对应字的编号是64号，前面的0-2047位已经占满，因此第64号字的第0位是2048，第1位是2049，第2位是2050，第3位2051，第4位2052，第5位2053。

# 设备管理

IO层级划分