三-操作系统

3-1操作系统分类

分类	特点
批处理操作系统	单道批：一次一个作业入内存，作业由程序、数据、作业说明书组成多道批：一次多个作业入内存，特点：多道、宏观上并行微观上串行
分时操作系统	采用时间片轮转的方式为多个用户提供服务，每个用户感觉独占系统特点：多路性、独立性、交互性和及时性
实时操作系统	实时控制系统和实时信息系统交互能力要求不高，可靠性要求高（规定时间内响应并处理）
网络操作系统	方便有效共享网络资源，提供服务软件和有关协议的集合主要的网络操作系统有： Unix、Linux、Windows server
分布式操作系统	任意两台计算机可以通过通信交换信息是网络操作系统的更高级形式，具有透明性、可靠性和高性能等特性
微机操作系统	Linux、Windows
嵌入式操作系统	运行在智能芯片环境中特点：微型化、可定制（针对硬件变化配置）、实时性、可靠性、易移植性 (HAL 和 BSP支持）

3-2进程

进程（process）是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块 PCB 和数据块部分组成

1.进程、程序、线程区别

1.1.进程VS程序

进程与程序的区别：进程是程序的一次执行过程，没有程序就没有进程。

程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡。

进程是系统进行资源分配和调度的独立单位，而程序不是。

进程	程序
程序的一次执行过程
动态的概念，它由创建而产生，完成任务后因撤销而消亡	静态的概念
系统进行资源分配和调度的独立单位

1.2.进程(process)VS进程(thread)

进程的 2 个基本属性：可拥有资源的独立单位；可独立调度和分配资源的基本单位。

例题

在支持多线程的操作系统中，假设进程 P 创建了 t1 、 t2 、t3 线程，那么()

A 、该进程的代码段不能被 tl1 、 t2 、 t3 共享

B 、该进程的全局变量只能被共享

C 、该进程中 t1 、 t2 、 t3 的栈指针不能被共享

D 、该进程中 t1的栈指针可以被 t2 、 t3 共享

答案：C

解析：A选项，代码段可以被共享；B选项，进程的全局变量还可以自己使用；D选项，进程自己的栈指针不能共享

2.进程状态模型

2.1.进程-三状态模型

运行：当一个进程在 CPU 上运行时。（单处理机处于运行态的进程只有一个）

就绪：一个进程获得了除 CPU 外的一切所需资源，一旦得到处理机即可运行。

等待(阻塞)：阻塞也称等待或睡眠状态，一个进程正在等待某一事件发生（例如请求I/O、等待I/O完成等）而暂时停止运行，此时即使把 CPU 分配给进程也无法运行，故称进程处于阻塞状态。

2.2进程-五状态模型

挂起原因：

(1) 进程过多，主存资源不足，此时必须将某些进程挂起，放到磁盘对换区，暂时不参与调度，以平衡系统负载， CPU 不分配时间片。

(2) 系统出现故障，或者是用户调试程序，也可能需要将进程挂起检查问题。

真题

在单处理机系统中，采用先来先服务调度算法。系统中有 4 个进程 P1 、 P2 、 P3 、 P4 （假设进程按此顺序到达），其中 P1为运行状态， P2 为就绪状态， P3 和 P4 为等待状态，且 P3 等待打印机， P4 等待扫描仪。若 P1（？），则 PI 、 P2 、 P3 和 P4 的状态应分别为（？）。

A 、时间片到 B 、释放了扫描仪 C 、释放了打印机 D 、已完成

A 、等待、就绪、等待和等待 B 、运行、就绪、运行和等待

C 、就绪、运行、等待和等待 D 、就绪、就绪、等待和运行

答案：A、C

解析：可直接看第二空，A选项，cpu一般会保持不断运行不同进程，而A缺少运行。B选项，有两个运行，不能同时运行两个。D选项，P4原为等待状态，即使等待事件完成，也只能转就绪状态，不可能为运行态

3.PCB

PCB: PCB 是进程存在的唯一标志。内容包含进程标识符、状态、位置信息、控制信息、队列指针（链接同一状态的进程）、优先级、现场保护区等。

进程通常由程序、数据集合、进程控制块 PCB 组成.PCB是一种数据结构，是进程存在的唯一标识.

4.进程存储方式

线性方式	把所有 PCB 组织在一张线性表中，每次查找是需要扫描全表
链接方式	把具有同一状态的 PCB, 用具中的链接字链接成一个队列，PCB 存储在一个连续的区域·
索引方式	同一状态的进程归入一个索引表，多个状态对应多个不同的索引表．

5.前驱图

前驱图是一个有向无循环图，由节点和有向边组成节点代表各程序段的操作，而节点间的有向边表示两个程序段操作之间存在的前趋关系。用于这种图可以描述多个程序或进程之间的执行顺序关系。

技巧：

并发图中某活动有后继就有 V 操作释放（增加）资源，有前驱就有 P 操作消耗资源
实现并发的信号量初值一般为 0 。有几个箭头就有几个信号量。

例题

前驱图是一个有向无环图，记为={ pi, pj ,pi 完成时间先于 pj 开始时间}。假设系统中进 P ：{ pl ， p2 ， p3 ，p4， p5 ， p6 ， p7 ， p8 }，且进程的前驱图如下。那么该前驱图可记为（ 1 ）图中〈 2 ）。

6.进程资源图

在如下所示的进程资源图中，（）

A 、 P1、 P2 、 P3 都是非阻塞节点，该图可以化简，所以是非死锁的

B 、 P1 、 P2 、 P3 都是阻塞节点，该图不可以化简，所以是死锁的

C 、 P1、 P2 是非阻塞节点， P3 是阻塞节点，该图不可以化简，所以是死锁的

D 、 P2 是阻塞节点， P1、 P3 是非阻塞节点，该图可以化简，所以是非死锁的

答案：D；

解析：

先看R1已给出2个资源（给P1、P3），即全部分配完，无空闲资源；R2给出2个资源（P2、P3），还剩1个空闲资源；

然后看进程申请箭头（即P->R），P1和P3指向的R2（R2现有1空闲资源），任意将其空闲资源给P1或P3都不会造成死锁；但P2指向R1（R1无空闲资源），无法分配资源，故P2为阻塞节点

3-3 PV操作

1.信号量

信号量是一类特殊的变量，程序对其访问都是原子操作，且只允许对它进行P(信号变量)和V(信号变量) 操作。

二元信号量：取值仅为“0”或“1”，主要用作实现互斥；
一般信号量：初值为可用物理资源的总数，用于进程间的协作同步问题
一个信号量可能被初始化为一个非负整数.
semWait 操作（P操作）使信号量减1。若值为负，则执行 semWait的进程被阻塞。否则进程继续执行。
semSignal操作（V操作）使信号量加1。若值小于或等于零，则被semWait操作阻塞的进程被解除阻塞

总而言之：P操作负责分配资源，没有资源的时候就等着（进入阻塞等待队列）。V操作负责释放资源，在阻塞队列不为空的时候唤醒某个进程进入临界区。

2.互斥问题：

临界资源(互斥资源):诸进程间需要互斥方式对其进行共享的资源。（进程中访问临界资源的那段代码称为临界区）

PS:

互斥信号量 S 的初值一般为非 0 。
访问权是一类特殊的互斥资源，同一时刻仅允许 1 个人用，则信号量初值为 1 。

进入临界区之前先执行 P 操作（可能阻塞当前进程）

离开临界区之后执行 V 操作（可能唤醒某个进程）

P 操作(锁操作-)：

将信号量 S 的值减 1 ，即S=S-1
如果 S >= 0 ，则该进程继续执行，否则该进程置为等待状态。

V 操作(释放操作+)：

将信号量S的值加 1 ，即 S=S+1
如果 S > 0 该进程继续执行；否则说明有等待队列中有等待进程，需要唤醒等待进程。

进程启动演示(进行P操作)

初始信号量mutex=1,三个进程启动,a进程使mutex=0,b进程使mutex=-1,c进程使mutex=-2

进程结束演示(进行v操作)

之后a进程结束,使mutex+1-->-1,mutex为负数,说明还有进程在等待

唤醒在等待的b进程

(以此类推…)

例题1

假设系统中有n个进程共享3台打印机，任一进程在任一时刻最多只能使用1台打印机。若用PV操作控制n个进程使用打印机，则相应信号量s 的取值范围为(1);若信号量S的值为-3,则系统中有(2)个进程等待使用打印机。

(1) A.0,-1,…,-(n-1) B.3,2,1,0,-1,…,-(n-3)

C.1,0,-1,…,-(n-1) D.2,1,0,-1,…,-(n-2)

(2) A.0 B.1 C.2 D.3

试题分析

试题(1)的正确答案为选项B。根据题意，假设系统中有n个进程共享3台打印机，意味着每次只允许3个进程进入互斥段，那么信号量的初值应为3。可见，根据排除法只有选项B中含有3。

试题(2)的正确答案为选项D。信号量S的物理意义为：当S≥0时，表示资源的可用数；当S<0 时，其绝对值表示等待资源的进程数。

参考答案： (1) B (2)D

例题2

假设铁路自动售票系统有 n 个售票终端，该系统为每个售票终端创建一个进程 Pi(i = 1，2，..，n）管理车票销售过程。假设Tj （ j = 1 ， 2 ，…，n）单元存放某日某趙车的车票剩余票数， Temp为Pi 进程的临时工作单元，×为某用户的购票张数。 Pi 进程的工作流程如下图所示，用 p 操作和 V 操作实现进程间的同步与互斥。初始化时系统应将信号量 S赋值为（？）图中 (a) 、(b) 和(c) 处应分别填入（？）。

A 、 n-1 B 、 0 C、1 D、 2

A 、 V(S)、 P(S) 和 P(s) B 、 P(S) 、 P(S) 和 V(S)

c 、 v(s) 、 v(s) 和 P(s) D、 P(S) 、 v(s) 和 v(s)

答案：C、D

3.同步问题

运行条件不满足时，能让进程暂停（在关键操作之前执行 P 操作）
运行条件满足时，能让进程继续（在关操作之后执行 V 操作）

规则:

不能向满缓冲区存产品
不能向空缓冲区取产品
每个时刻仅允许1 个生产者或消费者存或取1个产品

这里我们先实现前两个规则

int empty=5;    /*信号量：缓冲区中空位的个数，初值5*/
int full=0;  /*信号量：缓冲区中数据的个数，初值0*/

//生产者进程
procducer_i()    //i=1…m
{
while(TRUE)
{
    //生产一个数据；
    P(empty);
    //存一个数据到缓冲区；
    V(full);
}
}

//消费者进程
consumerj()        //j=1…k
{
while(TRUE){
    P(full);
    //从缓冲区取一个数据；
    V(empty);
    //消费数据；
}}

那么如何实现最后一个规则:

每个时刻仅允许1 个生产者或消费者存或取1个产品?

我们需要添加一个信号量mutex,表示缓冲区互斥使用，初值1,表示可用

int empty=5;    /*信号量：缓冲区中空位的个数，初值5*/
int full=0;  /*信号量：缓冲区中数据的个数，初值0*/
int mutex=1;  /*信号量：缓冲区互斥使用，初值1,可用*/

//生产者进程
procducer_i()    //i=1…m
{
while(TRUE)
{
    生产一个数据；
    P(empty);
    P(mutex);
    存一个数据到缓冲区；
    V(mutex);
    V(full);
}
}

//消费者进程
consumerj()        //j=1…k
{
while(TRUE){
    P(full);
    P(mutex);
    从缓冲区取一个数据；
    V(mutex);
    V(empty);
    消费数据；
}}

例题

进程P1、P2、P3 和P4 的前驱图如下所示

若用PV 操作控制进程P1～P4 并发执行的过程，则需要设置5个信号量S1、S2、S3、S4 和S5, 且信号量S1～S5 的初值都等于0。

下图中a、b 和c处应分别填写( );d、e 和f处应分别填写 ( ) 。

(1)

A.V(S1)V(S2)、P(S1)V(S3)和V(S4) B.P(S1)V(S2)、P(S1)P(S2)和V(S1)

C.V(S1)V(S2)、P(S1)P(S3)和V(S4) D.P(S1)P(S2)、V(S1)P(S3)和V(S2)

(2)

A.P(S2)、V(S3)V(S5)和P(S4)P(S5) B.V(S2)、P(S3)V(ss)和V(S4)P(S5)

C.P(S2)、V(S3)P(S5)和P(S4)V(S5) D.V(S2)、V(S3)P(S5)和P(S4)V(S5)

试题分析

因为P1是P2和P3的前驱，当P1执行完需通知P2和P3, 应采用 V(S1)V(S2)操作分别通知P2和P3, 故a处应填写V(S1)V(S2);又因为P2是P1和P3 的后继，当P2执行前应测试P1和P3是否执行完，应采用P(S1)P(S3)操作测试P1和P3是否执行完，故b处应填写P(S1)P(S3); 同理， P2 是P4 的前驱，当P2执行完应通知 P4, 应采用V(S4)操作分别通知P4, 故C处应填写V(S4)。

因为P3是P1的后继，当P3执行前应测试P1是否执行完，应采用P(S2)操作测试P1是否执行完，故d处应填写P(S2); 又因为 P3是P2和P4 的前驱，当P3执行完应通知P2和P4, 应采用V(S3)V(S5)操作通知P5, 故e处应填写V(S3)V(S5);P4 是P2 和 P3的后继，当P4执行前应测试P2和P3是否执行完，应采用P(S4)P(S5)操作测试P2和P3是否执行完，故f处应填写P(S4)P(S5)。

参考答案：C 、A

4.互斥和同步对比

	互斥	同步
资源信号量S	$S\neq0$(初始值一般为1)	$S=0$
PV操作顺序	先P后V	先V(生产者先生产)后P(消费者后使用)

5.死锁

所谓死锁，是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象。

死锁的四大条件：

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

进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果进程在等待一件不可能发生的事，则进程就死锁了。而如果多个进程产生死锁，就会造成系统死锁。

5.1.不发生死锁的最小资源数和可发生死锁最大资源数

$$
\textbf{可}发生死锁\textbf{最大资源数}：(w-1)m\ 系统\textbf{不可能}发生死锁的\textbf{最小资源数}：(w-1)m+1<=n \
w：每个进程需要的资源数\hspace{2em}m：总共的进程数
$$

例题1

系统有 5 个进程： A 、 B 、 C 、 D 、 E。这 5 个进程都需要 4个系统资源。如果系统至少有多少个资源，则不可能发生死锁。

答：(4-1)*5+1=16

某计算机系统中互斥资源 R 的可用数为 8 ，系统中有 3 个进程P1 、 P2 和 P3 竞争 R ，且每个进程都需要 i 个 R ，该系统可能会发生死锁的最小 i 值为（）

A、1 B、2 C、3 D、4

答：D，直接带入

3-5 存储管理

当内存太小不够用时，用辅存来支援内存
暂时不运行的模块换出到辅存上，必要时再换入内存

地址重定位

地址重定位是指将程序中的地址虚拟地址(逻辑地址)变换成内存的真实地址(物理地址)的过程。

逻辑地址

相对地址。
CPU所生成的地址。逻辑地址是内部和编程使用的、并不唯一。

物理地址

绝对地址。
加载到内存地址寄存器中的地址，内存单元的真正地址。

静态重定位：

绝对地址=相对地址+程序存放的内存起始地址

特点:

程序运行前就确定映射关系
程序装入后不能移动
程序占用连续的内存空间

动态重定位：

绝对地址=重定位寄存器的值 (BR)+ 逻辑地址寄存器的值 (VR)

特点:

程序占用的内存空间可动态变化
程序不要求连续的内存空间
便于多个进程共享代码

存储管理

存储管理的主要目的是解决多个用户使用主存的问题

分区存储管理
分页存储管理
分段存储管理
段页式存储管理
虚拟存储管理

分区存储管理

把主存的用户区划分成若干个区域，每个区域分配给一个用户作业使用，并限定它们只能在自己的区域中运行。

1.固定分区

固定分区法就是把内存固定划分为若干个大小不等的区域。分区划分的原理有一般系统操作员或操作系统决定。
系统对内存的管理和控制通过数据结构——分区说明表进行，分区说明表说明个分区号、分区大小、起始地址和是否空闲区。

2.动态分区法

在作业的处理过程中进行分区建立，其大小可随作业或进程对内存的要求而改变。

2.1最先适应分配算法

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

实现步骤：

空闲区地址由低到高排序

=>1.顺序查找各个空闲区，把第一个找到能容纳申请要求的内存区分配给申请者.（若空闲区比作业长度大，则分割该空闲区。一部分分配给作业一部分空闲。）

=>2.调整相应的空闲分区表和已分配分区表。

评价：性能一般但实现比较简单直接，易于释放时合并相邻空间分区。比较容易的满足大作业的需要。完成一次分配平均需要的搜索次数较大，影响了工作效率。

尽可能地利用存储器中低地址的空闲区，而尽量保存高地址的空闲区。

2.2最佳适应算法

算法思想：由于可变分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，优先使用更小的空闲区。

实现步骤：

空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区表，找到大小能够满足要求的第一个空闲分区。

评价：尽可能地保留了较大的空间。产生大量的不能被使用的很小的空闲区。因此这种方法会产生很多的外部碎片。所以该算法分配效果不一定是最佳的。

尽可能地利用存储器中空间小的空闲区，而尽量保存大的空闲区。

2.3最坏适应算法

算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时，优先使用最大的连续空闲区，这样分配后的空闲区就不会太小，更方便使用。

实现步骤：

空闲分区按照容量递减次序链接。每次分配内存时顺序查找空闲分区表，找到大小能满足要求的第一个空闲分区。

评价：分割后产生的空闲区一般仍可以供以后分配使用。工作一段时间后，不能满足大作业对空闲区的请求。

尽可能地利用存储器中空间大的空闲区。

2.4可重定位分区

允许已经分配的分区进行移动,使得已使用的内存分区连块,未使用的分区也连块

分页存储管理：

将程序与内存均划分为同样大小块，以页为单位将程序调入内存。

将一个程序进程的地址空间划分成若干个大小相等的区域,称为页。相应地,将主存空间划分成与页相同大小的若干个物理块,称为块或页框。

优缺点

优点：利用率高，碎片小，分配及管理简单
缺点：增加了系统开销；可能产生抖动现象

一般情况下,若题目未明确说明,则逻辑地址为32位,其中由右向左数:

0--11位为页内地址(即一共12位)

12--31位为页号(即一共20位)

物理地址相同,也是由右向左数:

0--11位为块内地址(即一共12位)

12--31位为块号(即一共20位)

注意!在逻辑地址上,内存存放在连续的逻辑地址上,实际上在物理地址上不一定连续的!

这里的逻辑地址与物理地址的转换,需要用到页表控制寄存器

页表控制寄存器

控制页表的处理,并由逻辑地址的页号,在页表中查找对应的物理块号

内存数据替换规则

先看访问位（近期未访问，0），后看修改位（未修改，0）

例题1

我们要取逻辑地址2100中存放的数据"5678".假设页和物理块的大小均为1024B

首先,我们通过逻辑地址整除页大小得到页号
$$
页号=逻辑地址/页大小(整除)\
2100/1024\
=2
$$
根据页表得到页号对应的物理块号为8

随后我们计算页内地址
$$
页内地址=逻辑地址\%页大小(取余)\
=2100\%1024 \
=52
$$
而页内地址=块内地址

所以,物理地址为
$$
物理地址=物理块号块大小+块内地址(页内地址)\ =81024+52\
=8244
$$

例题2

某计算机系统页面大小为4K, 若进程的页面变换表如下所示，逻辑地址为十六进制 1D16H。该地址经过变换后，其物理地址应为十六进制( )。

页号	物理块号
0	1
1	3
2	4
3	6

A.1024H B.3D16H C.4D16H D.6D16H

试题分析

页面大小为4K, 而4K=2^12, 因此逻辑地址的低12位对应页内地址，高位对应页号。题目中逻辑地址为十六进制1D16H, 一位十六进制数对应4位二进制数，3位十六进制数则对应12位二进制数，因此D16H为页内地址，页号为1。查页面变换表，页号1 对应的物理块号为3,将物理块号与页内地址D16H 拼接起来即可得到物理地址3D16H。

参考答案： B

例题3

某操作系统采用分页存储管理方式，下图给出了进程A和进程B的页表结构。如果物理页的大小为512字节，那么进程A逻辑地址为1111(十进制)的变量存放在()号物理内存页中。假设进程A的逻辑页4与进程B的逻辑页5要共享物理页8,那么应该在进程A页表的逻辑页4和进程B页表的逻辑页5对应的物理页处分别填( )。

进程A页表

逻辑页	物理页
0	9
1	2
2	4
3	6
4
5

进程B页表

逻辑页	物理页
0
1	3
2	5
3	7
4	2
5

物理页

0
1
2
3
4
5
6
7
8
9

A.9 B.2 C.4 D.6

A.4 、5 B.5 、4 C.5 、8 D.8 、8

试题分析

十进制1111转化为二进制10001010111。物理页的大小为512字节，这说明页内地址为9个二进制位，进程A的逻辑址中，右边的9位是页内地址，左边的2位是页号，即：10001010111。页号为二进制的10.即十进制的2,对应的物理页号为4.若A页表的透辑页4和进程B页表的透辑页5共享物理页8,则说明他们都对应物理页8.所以均填8。

参考答案： C、D

例题4-页式存储管理方案-重点!!

某系统采用请求页式存储管理方案，假设某进程有6个页面，系统给该进程分配了4个存储块，其页面变换表如下表所示，表中的状态位等于1和0分别表示页面在内存或不在内存。当该进程访问的第3号页面不在内存时，应该淘汰表中页面号为（10）的页面。

试题分析

请求页式存储管理方案中，当访问的页面不在内存时需要置换页面，最先置换访问位和修改位为00的，其次是访问位和修改位为01的，之后是访问位和修改位为10，最后才置换访问位和修改位为11的。

(没访问,没修改00-->没访问,有修改01-->有访问,没修改10-->有访问,有修改11)

因此，本题当该进程访问的页面3不在内存时，应该淘汰表中页号为4的页面。

分段管理

段式存储：按用户作业中的自然段（逻辑段，即相互相关的代码大小）来划分逻辑空间，然后调入内存，段的长度可以不一样。

优缺点

优点：多道程序共享内存，各段程序修改互不影响
缺点：内存利用率低，内存碎片浪费大

分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到主存的不同分区中。在系统中为每个进程建立一张段映射表，简称为“段表”。每个段在表中占有一个表项，在其中记录了该段在主存中的起始地址(又称为“基址”)和段的长度。进程在执行时，通过查段表来找到每个段所对应的主存区。

例题1

假设系统采用段式存储管理方法，进程P的段表如下所示。逻辑地址()不能转换为对应的物理地址；不能转换为对应的物理地址的原因是进行()。

段号	基地址	段长
0	1100	800
1	3310	50
2	5000	200
3	4100	580
4	2000	100

A.(0,790) 和(2,88) B.(1,30) 和(3,290)

C.(2,88) 和(4,98) D.(0,810) 和(4,120)

A. 除法运算时除数为零

B. 算术运算时有溢出

C. 逻辑地址到物理地址转换时地址越界

D. 物理地址到逻辑地址转换时地址越界

试题分析

给定段地址(x,y), 其中： x为段号，y为段内地址。将(x,y) 转换为物理地址的方法是：

根据段号x查段表→判断y<段长；如果小于段长，则物理地址=基地址+段内地址y, 否则地址越界。

因为段地址(0,810)中，0段的段长为800,段内地址810大于段长，故地址越界。段地址(4,120)中，4段的段长为100,段内地址120大于段长，故地址越界。

参考答案： D、C

段页式管理

段页式存储：段式与页式的综合体。先分段，再分页。 1 个程序有若干个段，每个段中可以有若干页，每个页的大小相同，但每个段的大小不同。

优缺点

优点：空间浪费小、存储共享容易、存储保护容易、能动态连接
缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

段页式系统的基本原理是先将整个主存划分成大小相等的存储块(页框), 将用户程序按程序的逻辑关系分为若干个段，再将每个段划分成若干页,以页框为单位离散分配。在段页式系统中，其地址结构由段号、段内页号和页内地址三部分组成。

虚拟存储

在前面介绍的存储管理方案中，必须为每个作业分配足够的空间，以便装入全部信息。当主存空间不能满足作业要求时，作业无法装入主存执行。如果一个作业只部分装入主存便可开始启动运行，其余部分暂时留在磁盘上，在需要时再装入主存，这样可以有效地利用主存空间。从用户角度看，该系统所具有的主存容量将比实际主存容量大得多，人们把这样的存储器称为虚拟存储器。

请求分页存储
请求分段存储
请求段页式存储

3-7设备管理

1.设备管理层次

硬件：完成具体的I/O 操作。
中断处理程序：I/O 完成后唤醒设备驱动程序
设备驱动程序：设置寄存器，检查设备状态
设备无关I/O 层：设备名解析、阻塞进程、分配缓冲区
用户级I/O 层：发出I/O调用。

2.缓冲区

工作方式		特点
程序控制(串行工作)	无条件传送	I/O端口总是准备好，cpu在需要时，随时直接利用访问相应的I/O端口。
	程序查询	CPU必须不停地测试I/O设备的状态端口。CPU与l/O设备是串行工作的。
中断		某个进程要启动某个设备时，CPU就向相应的设备控制器发出一条设备I/O启动指令，然后CPU又返回做原来的工作。CPU与l/O设备可以并行工作。
D M A ( 直接内存存取 )		通过DMA控制器直接进行批量数据交换，除了在数据传输开始和结束时，整个过程无须CPU的干预。

程序查询方式

需要CPU不断轮询各设备

中断方式

在平时执行主程序,需要时中断主程序,并处理其他指令,随后回复执行主程序处理

特点:

cpu与其他设备有一定的并行工作

DMA方式

该图中蓝色为中断方式数据传输,黄色是DMA方式数据传输

区别:

中断方式: 需要CPU在主存---IO设备之间进行控制

DMA方式: 在主存----ID设备之间添加了DMA接口,使得主存---IO设备交换数据可以绕过CPU控制,直接通过DMA接口进行数据交换

3-8文件存储管理

文件索引

直接索引:

通过索引节点,可以直接找到存放数据的物理盘块

特点:

每个索引节点都会指向一个物理盘块
能检索的数据范围很小(有多少索引节点,就只能检索多少物理盘块)

一级间接索引

每个索引节点都会指向一个下级索引,后面的索引才会指向真实的物理盘块

特点:

每个索引节点都会指向下一级索引,该级索引才指向真实的物理盘块
能检索的数据范围更大

二级,三级间接索引

类似于一级间接索引,区别是增设了更多级的间接索引

典型真题

某文件系统文件存储采用文件索引节点法。假设文件索引节点中有8个地址项iaddr[0]～iaddr[7], 每个地址项大小为4字节，其中地址项iaddr[0]~ iaddr[5] 为直接地址索引，iaddr[6] 是一级间接地址索引，iaddr[7] 是二级间接地址索引，磁盘索引块和磁盘数据块大小均为4KB。该文件系统可表示的单个文件最大长度是() KB。若要访问iclsClient.dll文件的逻辑块号分别为6、520和1030,则系统应分别采用()。

A.1030 B.65796 C.1049606 D.4198424

A. 直接地址索引、一级间接地址索引和二级间接地址索引

B. 直接地址索引、二级间接地址索引和二级间接地址索引

C. 一级间接地址索引、一级间接地址索引和二级间接地址索引

D. 一级间接地址索引、二级间接地址索引和二级间接地址索引

试题解析：

直接索引范围：6*4KB=24KB, 对应逻辑块号：0-5;*

依题意得:磁盘索引块为4KB,那么每一级索引的空间大小就是4KB,那么一级间接索引中就有4KB/4B=1024个结点,再乘上硬盘数据块的大小4KB得到

一级间接索引范围：(4KB/4B)4KB=4096KB, 对应逻辑块号：6-1029;

二级间接索引也与一级间接索引类似

二级间接索引范围：(4KB/4B)(4KB/4B)4KB=4194304KB,对应逻辑块号：1030及以上。

单个文件最大长度是：24KB+4096KB+4194304KB =4198424KB

参考答案： D、C

文件存储设备管理

位示图法

该方法是在外存上建立一张位示图 (Bitmap), 记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0和1 分别表示空闲和占用。

$$
所在行数（即字号，从0开始）=位示图编号//字长(即横坐标的总长度，如上图为15-0+1=16)\
$$
PS:此为地板除（向下取整，即10//3=3）

典型真题

某文件管理系统在磁盘上建立了位示图 (bitmap),记录磁盘的使用情况。若磁盘上物理块的编号依次为0、1、2、 …。系统中的字长为64位，字的编号依次为0、1、2、 …。字中的一位对应文件存储器上的一个物理块。取值0 和1分别表示空闲和占用。如下图所示。假设操作系统将256号物理块分配给某文件，那么该物理块的使用情况在位示图中编号为( )的字中描述，系统应该将 ( ) 。

A.3 B.4C.5 D.6

A.该字的0号位置“1”

B.该字的63号位置“1”

C.该字的0号位置“0”

D.该字的63号位置“0”

试题解析：

题考查位示图知识。

注意：此题的字号与位号均从0开始。

由于物理块从0开始，从0块到255块刚好占用了4个字(64*4=256),256块应该是第五个字(4号字)的0号位置。

参考答案： B、A

MSTG Blog

三-操作系统

3-1操作系统分类

3-2进程

1.进程、程序、线程区别

1.1.进程VS程序

1.2.进程(process)VS进程(thread)

例题

2.进程状态模型

2.1.进程-三状态模型

2.2进程-五状态模型

真题

3.PCB

4.进程存储方式

5.前驱图

例题

6.进程资源图

3-3 PV操作

1.信号量

2.互斥问题：

P 操作(锁操作-)：

V 操作(释放操作+)：

进程启动演示(进行P操作)

进程结束演示(进行v操作)

例题1

试题分析

例题2

3.同步问题

例题

试题分析

4.互斥和同步对比

5.死锁

5.1.不发生死锁的最小资源数 和 可发生死锁最大资源数

例题1

3-5 存储管理

地址重定位

逻辑地址

物理地址

静态重定位：

特点:

动态重定位：

特点:

存储管理

分区存储管理

1.固定分区

2.动态分区法

2.1最先适应分配算法

2.2最佳适应算法

2.3最坏适应算法

2.4可重定位分区

分页存储管理：

优缺点

页表控制寄存器

内存数据替换规则

例题1

例题2

试题分析

例题3

试题分析

例题4-页式存储管理方案-重点!!

试题分析

分段管理

优缺点

例题1

试题分析

段页式管理

优缺点

虚拟存储

3-7设备管理

1.设备管理层次

2.缓冲区

程序查询方式

中断方式

DMA方式

3-8文件存储管理

文件索引

直接索引:

特点:

一级间接索引

特点:

5.1.不发生死锁的最小资源数和可发生死锁最大资源数