Pocon's Blog
0%

操作系统期末复习

发表于 更新于 分类于

第一章 操作系统引论

操作系统定义

**一组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用地程序的集合.**

操作系统是对（软件+硬件）计算机资源 进行管理的 软件

操作系统是配置在计算机硬件上的第一层软件，是对计算机硬件的首次扩充。所有的计算机软件都必须在操作系统的支持下才能运行。

发展流程

无操作系统的计算机

人工操作

用户独占全机，CPU等待人工装带、卸带，CPU处理快但IO慢

脱机处理

用户先将程序和数据的纸带装入输入机，再在外围机的控制下把纸带上的结果通过相应的输出设备输出。

同时思考下后续讲到的IO设备的假脱机SPOOLing技术。磁盘中开辟了输入井和输出井，内存开辟了输入缓冲区和输出缓冲区

批处理系统

用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行，交互能力差

简单来说，就是用户将若干作业提交给计算机系统集中处理的操作系统

单道批处理

监督程序将磁盘上的第一个作业装入内存，并把运行控制权交给该作业；当该作业处理完成时，又把控制权还给监督程序将第二个作业调入内存

缺点

系统中的资源得不到充分的利用，IO过程中CPU空闲（CPU和IO设备使用忙闲不均）

多道批处理

image-20260119142744266

经过两次调度

  • 作业先放在外存上，形成一个后备队列

  • 作业调度程序按照作业调度算法从后备队列选择若干作业调入内存

  • 内存中按照进程调度算法共享CPU和系统中的各种资源
  • 通过中断技术（外中断）使得CPU和IO并行
优点

资源利用率高、系统吞吐量大

缺点

没有交互能力（作业执行时用户无法干涉）、平均周转时间长

分时系统

多个用户同时使用计算机，人机交互性较强，具有每个用户独立使用计算机的独占性。关键问题是：及时接收、及时处理

简单来说，就是允许多个用户以交互的方式使用计算机的操作系统

实时系统

能对控制对象做出及时反应，可靠性高，相应及时，但资源利用率低

例

信息查询系统（飞机、火车订票系统），工业（武器）控制系统，多媒体系统，嵌入式系统

基本特性

并发和共享式操作系统两个最基本的特征，两者之间互为存在的条件。

并发

宏观上同时执行，微观上分时交替执行。

并发 vs 并行：并行是指两个或多个事件在同一时刻发生，并发是指两个或多个事件在同一时间间隔发生（分时）

程序并发执行的特征
  • 间断性
  • 失去封闭性：多个程序共享资源，且速度不同
  • 不可再现性

共享

互斥共享

比如打印机、磁带机

同时访问

这里的同时也是，宏观上的，微观上交替地对该资源进行访问（分时共享）

虚拟

把一个物理上的实体变成若干逻辑上的对应物。比如说虚拟处理器、虚拟设备技术

虚拟技术分类：时分复用技术、空分复用技术

异步

操作系统基本结构

无结构

此时的OS是为数众多的一组过程的集合

模块化结构

按其功能精心地划分为若干个具有一定独立性和大小的模块。

分层式结构

通过自底向上法铺设中间层。类比计网分层结构

微内核结构

三项关键技术
  • 采用面向对象技术
  • 基于客户/服务器模式
  • 应用机制与策略分离原理

第二章 进程的描述与控制

程序

静态的。而进程是动态的

特征

顺序性

每一个操作必须在下一个操作开始之前结束。进程是程序的一次顺序执行。

封闭性

程序运行时独占全机资源，资源的状态只有本程序能够改变；程序与程序之间相互独立，执行时独占全机资源

并发性破坏了封闭性。

可再现性

只要初始条件和运行环境相同，当程序重复执行时，都将获得相同的结果。

程序并发执行的特征

  • 间断性
  • 失去封闭性
  • 不可再现性

进程

进程的定义

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

如何体现独立性？每个进程拥有一个独立的私有的地址空间，不同进程的地址空间不能相互访问。

线程 vs 进程：线程本身不具有资源，其地址和进程共享，所以同一进程中的各个线程的地址空间相同。

进程是接受计算机资源的基本单位（未引入线程）

不管是否支持线程，进程都是资源分配的基本单位；引入线程后，线程是处理及调度的基本单位。

内核级线程是处理及调度和分派的单位

一个进程映像是程序+相关数据段+PCB

  • 是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是动态的，而程序是静态的。
  • 程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。

进程的特性

  • 动态性：由创建而生，由调度而执行，由撤销而亡
  • 并发性：多个进程实体同存与内存中，并发执行
  • 独立性：资源分配和调度的独立单位
  • 异步性：不同进程按各自独立的，不可预知速度执行

进程和操作系统都具有：并发性和异步性

进程控制块PCB

是进程存在的唯一标志。记录了操作系统所需的，用于描述进程当前情况以及控制进程运行的全部信息。

内容

进程标识符、处理机状态、进程调度信息、进程控制信息

进程控制块的组织方式

链接方式

  • 把具有同一状态的PCB链接成一个队列

  • 包含就绪队列、若干阻塞队列、空队列

索引方式
  • 系统根据所有进程的状态建立相应的索引表
  • 就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中

进程的基本状态及转换

我们通过原语来控制进程。

image-20251215220223347

复杂一点的话参考

image-20260115164830074

进程同步

定义

使并发执行的诸进程之间有效地共享资源和相互合作，从而使程序的执行具有可再现性。

两种制约关系

直接相互制约（同步关系）

源于进程间的合作

间接相互制约（互斥关系）

源于进程对资源的共享

临界资源

定义

一段时间内只允许一个进程访问的资源。必须采用“互斥方法访问”。

一个进程正在访问临界资源，另一个要访问该资源的进程必须等待

**临界区：访问临界资源的代码段**，可以进一步分为进入区和退出区 ### 进程同步应该遵循的规则 解决临界区问题的进程同步应遵守的4条准则 #### 空闲让进 无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区 #### 忙则等待 当有进程进入临界区时，表明临界资源正被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问 #### 有限等待 对要求访问临界资源的进程，应保证有限的时间内能进入自己的临界区，以免陷入 **死等** 状态 #### 让权等待 当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入 **忙等** 状态 ## 信号量机制 ### 整形信号量——不符合让权等待 - 以**整形变量S**作为信号量 - 使用wait(S) 和 Signal(S) 来访问。这是两个原子操作（P、V） #### 实现 
1
2
3
4
wait(S): while S<=0 do no-op
		S := S-1;
		
signal(S): S := S + 1;
由于是原子操作，所以自加自减不会交替执行 #### 缺陷 当 S<0的时候会不停检查，**不符合让权等待原则** ### 记录型信号量——会造成死锁 - 用一个**整形变量value**表示资源的数目 - 用一个**链表L将**等待访问该资源的进程组成**阻塞队列** #### 实现 ##### 数据结构 
1
2
3
4
type semaphore = record
	value : integer;
	L : list of process;
end
##### P、V 操作 image-20260108221504633 #### 缺陷 image-20260108222634090 这里就是一个经典的循环等待，狗咬狗死不放手的现象了。死锁了。所以在**多种共享资源条件下，容易造成死锁** ### AND型信号量——一次性全分配 - 一次性分配进程执行过程中所需要的全部资源，使用完过后再一并释放 - 即使只有一个资源无法分配，其他的资源也都不分配 - **要么全分配，要么一个都不分配**（你要的全拿走） 直观上来说，记录型信号量不是只有涉及到多种资源分配的时候才死锁吗，那我们把多种资源绑定在一起，成一族资源（Cluster）就好了， #### 实现 image-20260108223050972 #### 缺陷 - 如果一次要申请**N个同类资源**，就要使用N次**重复**的命令，效率低。 - 无法满足 当资源低于某个**下限值**的时候，便不分配 - 循环调用多个P、V操作**可能造成死锁**。比如甲乙各占10个A资源，但是20个A才能运行 ### 信号量集 - 每次分配之前，必须测试该资源的数量，看其是否大于其下限值（最大可分配值） - 除**信号量S**外，还设置资源的**需求量d**，和资源的**下限值t** #### 实现 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Swait(S1, t1, d1
	  S2, t2, d2...
	  )
	if Si >= ti and ... and Sn >= tn then
		for i:=1 to n do
			Si := Si - di;
        end for;
    else
    	//将进程阻塞，放入第一个发现si < ti的等待队列中
    end if;
    

Ssignal(S1, d1,
		S1, d2...
		)
	for i:=1 to n do
		Si := Si + di;
		//将Si等待队列中的进程转入就绪队列
    end for;
#### 其中特殊使用（必考）
Swait(S, d, d)

只有一个信号量，每次分d份资源。当资源数少于d的时候，不给分配

Swait(S, 1, 1)

退化成一般记录型信号量（S>1） 或 互斥型信号量（S=1）

Swait(S, 1, 0)

作为开关。 S >= 1便可执行后续代码，S = 0 后阻止任何程序执行该段代码。

信号量的两种应用

利用信号量实现进程互斥

image-20260108224837180

注意
  • P、V在同一个程序中成对出现
  • 首先定义信号量。如果单纯互斥，设置信号量=1即可。如果实现访问有限数量的共享资源，那么信号量=资源数量

利用信号量实现前趋关系

var mutex: semaphore := 0

image-20260108225126015

注意

  • 信号量初始值一定是0

  • signal在前趋步骤集合的末尾，wait在后继部分的开头

例子

image-20260108230124026

image-20260108230134126

三大问题

生产者-消费者问题

经典版

一组生产者进程和消费者进程共享一个初值为空，大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区时临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

分析

临界资源：仓库

约束条件：仓库满的时候生产者阻塞，仓库空的时候消费者阻塞

环形缓冲区

这里我们类似于循环队列，使用了in 和 out两个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
samephore mutex = 1;
Item buffer[n];	
int int,out,count = 0;

//生产者
while(1){
	wait(mutex);
	if(count < n){
		count++;
		buffer[in] = item_put;
		in = (in+1) % n
	}
	signal(mutex)
}

//消费者
while(1){
	wait(mutex)
    if(count>0){
        count--;
        item_get = buffer[out];
        out = (out+1) % n;
    }
	signal(mutex)
}
一般做法

一般我们还是使用full empty两个信号量。其中full代表有多少位置以及有货物了，empty表示多少个位置是空的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
semaphore full = 0;
semaphore empty = n;
semaphore mutex = 1;

//生产者
while(1){
	wait(empty)
	wait(mutex)
	//放货物
	signal(mutex)
	signal(full)
}

//消费者
while(1){
	wait(full)
	wait(mutex)
	//取货物
	signal(full)
	signal(empty)
}

注意顺序，如果我们先wait mutex的话，会发生死锁。

这里我们用的记录型信号量，同样我们可以使用AND型信号量，Swait(…)，里面的顺序要对~~!

进阶版

桌上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出

分析

相对于传统派，维新派可以这样解构。盘子就是buffer，且容量为1，有两类商品-消费者。并且由于容量只有1，所以一定只存在 放水果-吃水果-放水果-吃水果…..这样的过程。

做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
semaphore mutex = 1;
semaphore orange, apple = 0;

//爸爸
while(1){
	wait(plate)
	//放苹果
	signal(apple)
}

//女儿
while(1){
	wait(apple)
	//eat apple
	signal(plate)
}

//妈妈
//儿子 略

哲学家进餐问题

一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他们。只有在哲学家饥饿的时候，才试图拿起左、右两根筷子（一根、一根拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考

image-20260115224607862

注意一下这个安排的顺序

实现

很简单啊。有的时候还会多一个临界资源：碗

然后这里的话我们强制加一个条件：先拿左筷子，再拿右筷子

1
2
3
4
5
6
7
8
9
10
semaphore chopstick[5] = {1,1,1,1,1};
Pi(){
	while(1){
		wait(chopstick[i]);
		wait(chopstick[(i+1)%5]);
		//eat
		signal(chopstick[i]);
		signal(chopstick[(i+1)%5]);
	}
}

但这样有个严重的问题，就是如果所有人同时先拿起左边的筷子怎么办？会发生死锁。

我们可以加上以下限制条件

  • 最多允许4名哲学家同时进餐
  • 当且仅当一名哲学家左右两边的筷子都可用的时候才允许抓起筷子
    • 加互斥锁
    • 用AND信号量
  • 对哲学家顺序标号，要求奇数号哲学家先左后右；偶数号哲学家先右后左

信号量集解决死锁（孩子们这是我押的题）

1
2
3
4
5
6
7
8
9
10
11
semaphore chopstick[5] = {1,1,1,1,1}
Pi{
	while(1){
		//别吵我在思考
		Swait(chopstick[i],1,1,
			  chopstick[(i+1)%5],1,1);
		//吃饭
		Ssignal(chopstick[i], 1, 1
				chopstick[i+1]%5, 1, 1);
	}
}

这里信号量集退化成了互斥的AND信号量。破坏的请求保持条件

往年有这样子考

image-20260119151615713

image-20260119151648909

读者-写者问题

有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任意一个写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出

分析

参考下数据库。读锁和读锁相容，其他组合（读写，写写）都是互斥的。

而仅仅在文件上加一个互斥锁实现读写、写写互斥是不太行的，因为有一个功能是所有读者都消失了我们才能开始写，所以我们需要一个计数器。并且这个计数器也是临界资源需要一个额外的互斥锁。

总之，读者-写者的关键就是有一个互斥访问的count计数器

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int count = 0;	//当前读者数量
semaphore mutex = 1;	//给count加锁
semaphore rw = 1;		//读写互斥锁

writer(){
	while(1){
		wait(rw);
		//writing
		signal(rw);
	}
}

reader(){
	while(1){
		wait(mutex);
		if(count == 0)
			wait(rw); //等着写完或者不让写
		count++;
		signal(mutex)
		//reading
		wait(mutex)
		count--;
		if(count == 0)
			signal(rw);
		signal(mutex);
	}
}

这里读进程是优先的，这样可能导致写进程饥饿。如果我们想要能够有写进程请求访问，这是应禁止后续读进程的请求，这个时候就再加一个互斥锁就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
writer(){
	while(1){
		wait(r);	//我要写了，不准读了
		wait(rw);	//没人读我就开写了
		//writing
		signal(rw);	//我写完了
		signal(r);	//你们有读的权限了
	}
}

reader(){
	while(1){
		wait(r);	//我有权限读吗
		wait(mutex);
		if(count == 0)
			wait(rw);	//说明还有人在你关闭权限之前就在读了，你要等他们读完才能开始写
        count++;
        signal(mutex);
        //reading
        wait(mutex);
        count --;
        if(count == 0)
        	signal(rw);	//钉子户走了，可以开始写了
        signal(mutex);
	}
}

王源问题

假设一个系统有三个吸烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无线地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料地抽烟者卷一根烟并抽掉它，并给供应者告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int num=0;	//存储随机数
semaphore offer1, offer2, offer3 = 0;
semaphore finish = 0;

Offer(){
	while(1){
		num = (num+1)%3;
		if(num == 0)
			signal(offer1);	//烟草 + 纸
        if(num == 1)
    		signal(offer2);	//烟草 + 胶水
        if(num == 2)
    		signal(offer3);	//纸 + 胶水
        wait(finish);
	}
}

P1(){
	while(1){
		wait(offer1)
		//卷烟，抽了
		signal(finish)
	}
}
P2、P3 略

独木桥问题

image-20260115225340786

image-20260115225358512

分析

有点像读者-写者的变种。我们通过一个互斥信号量实现桥上只有一种方向的人，只有一种方向的人都走完了，下一类人才能开走，所以需要一个计数器count，并且这个count也是一个临界资源需要加锁。并且一共有两种方向，也就需要两个count和两个count锁了。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
semaphore eastMutex, westMutex = 1
semaphore bridge = 1
int eastCount, westCount = 0

东方：
while（1）{
	wait(eastMutex);
	if(eastCount == 0) 
		wait(brigde);
    eastCount++;
	signal(eastMutex);
	//上桥
	//下桥
	wait(eastMutex);
    eastCount--;
	if(eastCount == 0) 
		signal(brigde);
	signal(eastMutex);
}

西方：
while（1）{
	wait(westMutex);
	if(westCount == 1)  
		wait(brigde);
    westCount++;
	signal(westMutex);
	//上桥
	//下桥
	wait(westMutex);
    westCount--;
	if(westCount == 0)
		signal(bridge);
	signal(westMutex);
}

第三章 处理及调度与死锁

处理机调度的层次

**按照运行频率从高到底来说：低级调度 > 中级调度 > 高级调度**

image-20260108231001553

高级：作业调度

中级：内存调度

低级：进程调度

调度算法

相关指标计算

CPU利用率
吞吐量

单位时间内CPU完成作业的数量

周转时间
平均周转时间
平均带权周转时间

所以也可以看出带权周转时间严格不小于1

先来先服务（FCFS）

  • 有利于长作业（进程），不利于短作业（进程）
  • 有利于CPU繁忙型作业（进程），不利于I/O繁忙型作业（进程）
  • 属于不可剥夺算法

Screenshot_2026-01-08-23-16-54-573_com.orion.notein

短作业优先（SJF）

  • 哪个估计运行时间最短，先运行哪个。由于是估计，所以不一定能真正做到短作业优先调度
  • 对长作业不利
  • 不能保证紧迫性作业会被及时处理
  • SPJ调度算法的平均等待时间、平均周转时间最少

Screenshot_2026-01-08-23-21-18-861_com.orion.notein

优先级调度算法（PSA）

非抢占式

一旦选择了优先权最高的进程执行，直到它结束或阻塞后，才选另一个执行

抢占式

若出现优先权更高的，则让出CPU

  • 支持PSA的有：优先权原则，时间片原则，短作业有限原则
静态优先级

优先级在创建进程时决定，且在进程的整个运行期间保持不变。

动态优先级

进程运行过程中，根据进程情况的变化动态调整优先级

高相应比优先权调度算法（HRRN）

  • 同时考虑到了短、长作业

动态优先权

时间片轮转调度算法

分时系统的原则，主要目的是使得多个交互的用户能够得到及时相应，能够与计算机进行交互。

注意时间片不能太长也不能太短。太长成了FCFS，太短调度和上下文切换频繁。所以时间片大小主要取 略大于一次典型交互所需要的时间

时间片轮转调度算法是绝对可抢占的

多队列调度算法

多级反馈队列调度算法

例题

image-20260119152408292

image-20260119152635712

image-20260119154032350

死锁

image-20260109210358112

定义

多个进程在运行过程中，因争夺资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进

四个必要条件

互斥条件

一段时间内某资源仅为一个进程所占有

请求和保持条件

进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有。

不剥夺条件

进程所获得的资源在未使用之前，不能被其他进程强行夺走。只能主动释放

循环等待条件

链中每个进程已获得的资源同时被链中下一个进程所请求。

预防死锁

破坏不剥夺条件

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

缺点

反复地申请和释放资源会增加系统开销，降低系统吞吐量

破坏请求并保持条件

采用预先静态分配方法，即进程在运行前一次申请完它所需要地全部资源，在它资源未满足之前，不把它到投入运行。一旦投入运行，这些资源就一直归它所有，不再提出其他资源请求。

缺点

系统资源被严重浪费，而且还会导致”饥饿现象“

破坏循环等待条件

采用顺序资源分配法。首先给系统中地资源编号，规定每个进程必须按编号地递增的顺序请求资源。同类资源一次申请完。

缺点

限制了新类型设备加入，浪费，编程不友好

避免死锁

安全状态

定义

系统能按某种进程推进顺序（P1，P2，…，Pn）为每个进程 Pi 分配所需的资源，直至满足每个进程对资源的最大需求。

如果系统没有找到一个安全序列，则称系统为不安全状态

注意

并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。

银行家算法（重点必考大题）

  1. 若 Request <= Need，则继续；否则报错，因为所需要的资源数已经超过它所宣布的最大值
  2. 若 Request <= Available，则继续；否则报错，因为尚无足够资源，需要等待（阻塞）
  3. 系统试探把资源分配给进程P，并修改下面数据结构中的数值。下面略了
  4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程P，以完成本次分配；否则将本次的试探分配作废，恢复原来的分配状态，让进程P等待。
例题

image-20260119154050098

当前A、B、C、D资源剩余分别为：1，5，2，0

image-20260119154223540

image-20260119155754414

检测死锁

资源分配图

Screenshot_2026-01-09-21-07-46-432_com.orion.notein

死锁定理

S为死锁的条件是 当且仅当 资源分配图无法化简

例题

image-20260119154126874

解除死锁

资源剥夺法

挂起某些死锁进程，并抢占它们的资源，将这些资源分配给死锁进程

撤销进程法

强制撤销部分甚至全部死锁进程并剥夺这些进程的资源

进程回退法

让一个或多个进程回退到足以回避死锁的地步，进程回退时资源释放资源而非被剥夺，要求系统保持进程的历史信息，设置还原点。

第四章 存储器管理

程序的链接

静态链接

在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。这里形成的就是可执行文件。将几个目标模块装配成一个装入模块时，需要解决两个问题：①修改相对位置，编译后的所有目标模块都是从0开始的相对地址，当链接成一个装入模块时要修改相对地址。②变换外部调用符号，将每个模块中的所用的外部符号也都变换为相对地址

装入时动态链接

将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。优点是便于修改和更新，便于实现对目标模块的共享

运行时动态链接

对某些目标模块的链接，是在程序执行中需要改目标模块时才进行的。凡在执行过程中未用到的目标模块，都不会被调入内存和被链接到装入模块上。优点是能加快程序的装入过程，还可节省大量的内存空间。

程序的装入（记一下这三种类型的名字）

绝对装入

只适用于单道程序环境。编译时将产生绝对地址的目标代码，程序逻辑地址和实际内存地址完全相同。

可重定位装入

在多道程序环境下，多个目标模块的起始地址通常都从0开始，程序中的其他地址都是相对于起始地址的，此时应采用可重定位装入方式。根据内存的当前情况，及那个装入模块转入内存的适当位置。在装入时对目标程序中指令和数据地址的修改过程称为重定位。

当一个作业装入内存是，必须给它分分配要求的全部内存空间，若没有足够的内存，则无法装入。此外，作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。所以也称为静态重定位。静态的含义是：不能实现进程在内存中位置的移动

动态运行时装入

也成为动态重定位。只有动态重定位才能在运行中移动进程在内存中的位置。

连续分配（有外部碎片可紧凑）

单一连续分配

内存分为系统区和用户区，系统区一般在低地址。用户内存中只有一道用户程序。

优点

无外部碎片，无需进行内存保护

缺点

只能用于单用户、单任务的操作系统。有内部碎片，存储器的利用率极低

固定分区分配

是一种多道程序存储管理方式

我们建立一个分区使用表，分区大小可以相同也可以不同。我们只需要修改分区表中的状态（已分配/未分配）即可。

优点

无外部碎片

缺点

有内部碎片

动态分区分配（必考）

系统中的大小和数目是可变的

随着时间的推移，内存中会产生越来越多的外部碎片

具体这里的算法很简单我就懒得写了，我只写特点。但是这里至少考一个填空或者简答题吧。要学会画图分析，而且记得画图画大一点哈哈

要解决的三个问题：数据结构、分区分配算法、分区分配操作

动态分区分配的数据结构

空闲分区表

设置一张空闲分区表，用于记录空闲分区的情况。注意只记录空闲分区（为什么这里有三个感叹号，是因为要出判断题吗）

image-20260119200738573

空闲分区链

image-20260119200729233

算法

首次适应算法

低地址部分出现很多小的空闲分区(外部碎片)

邻近适应算法

尾部出现很多外部碎片

最佳适应算法

按空闲分区从小到大进行排序。会产生最多的外部碎片

最坏适应算法

按空闲分区从大到小进行排序。会很快导致没有可用的大内存块

空闲分区合并

四种情况，也很简单，依旧也是必考。记得要合并就好，像开心消消乐一样。

例题

image-20260119155858016

分页存储管理

分页管理从计算机的角度考虑设计的，目的是提高内存的利用率，提升计算机的性能

逻辑地址

6627e508cad8e3c48e8fa95096c69deb

0~11为页内地址，所以页面大小为$2^{12}$，每页4KB；12~31为页号，所以一共有 $2^{20}$ = 1M 页

页表

页表记录了页号到物理块号的映射关系

image-20260116092157351

地址表换机构

image-20260116092235757

在系统中通常有一个页表寄存器，存放页表在内存的其起始地址F和页表长度M。进程未执行时，页表的始址和页表长度存放在本进程的PCB中，当进程被调度执行时，才将页表始址和页表长度装入页表寄存器中。

逻辑地址到物理地址（很大概率考）

设页面大小为 L， 逻辑地址 A 到物理地址 E 的变换过程如下

  1. 计算页号 P (P = A/L)， 计算页内偏移（W = A%L）
  2. 比较页号P和页表长度M，若P>M则产生越界中断，否则继续执行
  3. 若表中页号P对应的页表项地址 = 页表始址 F + 页号P *页表项长度，取出该页表项内容b，即为物理块号。
  4. 计算 E = b * L + W

用十进制给出和十六进制（二进制）给出的计算过程稍微有些不同。

例题

9050460093b7d8f5f544c67e48c98bc8

image-20260119161345876

image-20260119161851587

image-20260119162048757

image-20260119161952860

特性

两次访问内存

第一次访问页表，确定所存取的数据或指令的物理地址

第二次根据该地址取数据或指令

页式管理中的地址空间是一维的

页式管理只需要给出一个整数就能确定对应的物理地址，因为页面大小 L 是固定的

快表

快表是一个具有并行查找能力的高速缓冲寄存器，又称为相联存储区（TLB），用来存放当前访问的若干页表项，以加速地址变换的过程。

分段存储管理

分段管理考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要

分段

按照用户进程中的自然段划分逻辑空间。参考ELF文件格式

image-20260116094146171

同样的，我们以此来得到段数量和最大段长

段表

同样也实现了逻辑空间和内存空间的映射。不过这里相比页表显示给出了段长，因为段长是不固定的而页面大小是固定的

image-20260116094231445

地址变换机构

image-20260116094415243

系统中设置了段表寄存器，用于存放段表始址 F 和段表长度 M。从逻辑地址A到物理地址E之间的地址变换过程如下：

  1. 从逻辑地址 A 中取出前几位为段号 S，后几位为段内偏移量 W
  2. 比较段号 S 和段表长度 M，若 S >= M则产生越界中断，否则继续执行
  3. 段号 S 对应的段表项地址 = 段表始址 F + 段号 S * 段表项长度，取出该表项的前几位得到段长C。若段内偏移量 >= C，则产生越界中断。
  4. 取出段表项中该段的始址b，计算 E = b + W，用得到的物理地址E去访问内存。

特性

只需要一次访存
分段管理的地址空间是二维的

段页

作业的地址空间首先被分为若干逻辑段，每段都有自己的段号，然后将每段分成若干大小的页。（先分段，再分页）

三次访存

第五章 虚拟存储器

虚拟存储器概述

局部性原理

时间局部性：程序中的某条指令一旦执行，则不久后该指令很可能再次被访问

空间局部性：一旦程序访问了某个存储单元，则不久后其附近的存储单元也将被访问

定义

具有请求调入功能和置换功能，能从逻辑上扩充内存容量的一种存储器系统

虚存大小

一个虚拟存储器的最大容量是由计算机的地址结构确定的

若CPU给出的有效地址长度为20位，则程序可以寻址的范围为1M，即虚存的容量：1M。

在多道程序环境下，一个计算机系统可以为每一个用户建立一个虚拟存储器

特征

多次性、对换性、虚拟性（逻辑容量由内存容量和外存容量之和决定，最大容量由地址结构决定）

请求分页存储管理方式

它在进本分页系统的基础上增加了请求调页、页面置换两大功能所形成的页式虚拟存储系统。所以主要的硬件支持有：页表机制、缺页中断机构和地址变换机构

请求页表机制

记一下相比传统页表里多出了这几项

image-20260113143735197

页面置换算法（必考）

要会算缺页次数，缺页率

最佳置换算法

先进先出置换算法

belady现象

最近最久未使用算法

利用了移位寄存器和栈来实现

写题规范

image-20260119163001935

例题

image-20260119164824322

请求分段存储管理方式

略

请求段页式存储管理方式

每道程序都有一个段表和一组页表

第六章 输入输出系统

层次结构

image-20260113152331855

设备驱动程序的作用：启动指定设备

分类

按数据传输单位分类

块设备

速率高，可寻址，DMA方式。主要有磁盘

流设备

速率低，不可寻址，中断驱动方式。主要有键盘

IO接口

image-20260113152534247

和CPU这边，有三类信号线：数据线、地址线、控制线</font>

和设备这边，有三类信号：数据、状态、控制</font>

IO逻辑实现对设备的控制。IO通过一组控制线与CPU交互

IO控制方式

IO控制分为四类：程序直接控制、中断控制、DMA方式、通道控制（通道是一种特殊的处理机，通过执行通道程序来控制IO操作，与CPU共享内存）

程序直接控制方式

CPU一直检测输没输完，是忙等

中断驱动方式

中断（外中断） vs 陷入（内中断）

中断是指CPU对IO设备发来的中断信号的一种响应

陷入时另外一种由CPU内部事件引发的中断

  1. 进程要启动I/O设备时，由CPU向该设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。

  2. 设备控制器按照命令要求去控制指定设备。

  3. 设备处理完数据后，便产生一个中断信号。此时，CPU便转而处理该信号。

这个时候CPU和IO设备是并行的，但每次传送以字节为单位

DMA方式

  1. CPU将IO任务委托给DMA部件

  2. DMA将数据直接读取或写入主存，不经过CPU寄存器

  3. IO数据传输完成后，DMA向CPU发中断信号

这个是或每次传送至少一个数据块，传送的数据从设备直接送入内存。仅在传送一个或多个数据块的开始和结束时，才需CPU干预

通道控制方式

IO通道：具有独立控制逻辑、可执行通道程序，能与主机并行工作的专用处理器。在主机和设备之间，承担IO处理工作。通道没有自己的内存，和CPU共享内存

CPU只需向通道发送一条I/O指令。通道在收到该指令后，便从内存中取出本次要执行的通道程序，然后执行该通道程序，仅当通道完成了规定的I/O任务后，才向CPU发中断信号

设备分配与回收

设备分配是指根据用户的IO请求分配所需的设备。分配的总原则是充分发挥设备的使用效果，尽可能地让设备忙碌，又要避免由于不合理的分配方法造成进程死锁。

设备分配的数据结构

设备控制表DCT

一个设备控制表就表征一个设备，而这个控制表中的表项就是设备的各个属性。凡因请求本设备而未得到满足的进程，应将其PCB按某种策略排成一个设备请求队列，设备队列的队首指针指向该请求队列队首PCB

Screenshot_2026-01-19-19-29-58-630_com.orion.notein

COCT、CHCT、SDT

  • COCT：控制器控制表。OS为每一个控制器设置一张记录其情况的控制表
  • CHCT：通道控制表。每个通道都配有一张控制表
  • SDT：系统设备表。这个是系统范围的数据结构，记录了系统中全部设备的情况。每个设备占一个表目。

逻辑设备名到物理设备名的映射

设备独立性是指程序独立于具体使用的物理设备。为了实现设备独立性，在系统中设立了一张逻辑设备表LUT，用于将 逻辑设备名 映射为 物理设备名。LUT表项包括逻辑设备名、物理设备名和设备驱动程序入口地址。

当进程用逻辑设备名来请求分配设备时，系统为它分配一台响应的物理设备，并在LUT中加你了一个表目，当以后进程再利用该逻辑设备名请求IO操作时，系统通过LUT来寻找对应的物理设备和驱动程序。

分配方式

从设备地特性来看，使用以下三种使用方式的设备分别为：独占设备、共享设备和虚拟设备。

独占式使用设备

进程分配到独占设备后，便由其独占，直至该进程释放该设备

分时式共享使用设备

略

SPOOLing技术

简单来说：通过一个进程将设备输入的数据暂存到磁盘上；用另一个进程把暂存到磁盘上的数据传送到设备上。这样便可在主机的直接控制下，实现脱机输入/输出功能。此时外围操作于CPU对数据的处理同时进行，这种在联机情况下实现的同时外围操作成为SPOOLing。

在多道程序（SPOOLing系统必须建立在具有多道程序功能的OS上，并且应有高速随机外存的支持，这通常是采用磁盘存储技术来实现）下，用一程序来模拟外围控制机，实现将数据从磁盘传送到低速的输出设备上，从而可在主机的直接控制下，实现脱机输入、输出功能。进而实现外围操作与CPU对数据的处理同时进行。这种在联机情况下实现的同时外围操作成为SPOOLING技术，是对脱机输入、输出工作的模拟，是操作系统中采用的一项将独占设备改造成为共享设备的技术。

image-20260113160927362

  • 输入井、输出井：磁盘上的两块大存储区，用于暂存输入、输出的数据
  • 输入缓冲区、输出缓冲区：位于内存中，作用时缓和CPU、设备之间的速度差异
  • 输入进程：利用输入缓冲区为中介，把输入设备的数据存入输入井
  • 输出进程：将用户数据存入输出井，设备空闲时，再将输出井中的数据利用输出缓冲区送入设备

SPOOLing打印过程

  1. 进程请求打印

    1. 由输出进程在输出井中申请一块空闲磁盘区，并将要打印的数据存入其中。

    2. 输出进程为该进程申请一张空白的请求打印表，并将打印请求填入其中，再将该表挂到请求打印队列（假脱机文件队列）上。

    到这里用户进程而言打印任务已经完成

  2. 如果打印机空闲，输出进程从请求打印队列取出第一张请求打印表

  3. 根据表中的要求将数据，从输出井传送到输出缓冲区，再由打印机进行打印

  4. 打印完后，输出进程再查看请求打印队列中是否还有等待打印的请求表

  5. 若有，再取出第一张表，并根据要求打印。如此下去，直至队列为空，输出进程才将自己阻塞起来。仅当下次再有打印请求时，输出进程才被唤醒

SPOOLing特点

  • 提高了IO速度
  • 实现了虚拟设备功能
  • 将独占设备改造为共享设备

缓冲技术

引入缓冲区的原因

  • 缓和CPU和IO设备之间速度不匹配的矛盾
  • 减少对CPU中断的频率，放宽对CPU中断响应时间的限制
  • 解决数据粒度不匹配的问题
  • **提高CPU和IO设备之间的并行性**

磁盘

磁盘盘面上的数据存储在一组同心圆中，称为磁道。每个磁道和磁头一样宽，一个盘面上有上千个磁道。磁道又划分为几百个扇区，每个扇区固定存储大小，一个扇区称为一个盘块。

磁盘调度算法（必考大题）

FCFS

优点是公平

Screenshot_2026-01-16-10-17-25-079_com.orion.notein

SSTF

性能比FCFS号，但会产生饥饿现象

SCAN

寻道性能比较好，可以避免饥饿现象

顺着方向-反着方向-….

Screenshot_2026-01-16-10-18-24-464_com.orion.notein

CSCAN

消除了对两端磁道请求的不公平

左-右———-左-右

Screenshot_2026-01-16-10-19-16-501_com.orion.notein

RAID-廉价磁盘冗余阵列

概述

核心功能：并行交叉存取

目的：提高对磁盘的访问速度

方法：将每个数据块分成若干个子块，分别存储在各个不同磁盘的相应位置上

优点：并行存取

RAID0——并联增加速度

并联，容量等于所有磁盘总和，速度等于所有磁盘速度的倍数

优点

简单，实现成本最低

缺点

没有提供冗余或错误修复能力。任务一块磁盘出现故障，整个系统出现故障，可靠性为单独一块硬盘的1/N

RAID1——镜像冗余可靠性

也称为磁盘镜像。原理是把一个磁盘的数据镜像到另一个磁盘上实现冗余容错。

磁盘利用率为50%，可靠性很高。但是同一时间内只能向一块磁盘内写入数据。

RAID 10

至少四个硬盘（两个并联增加速度，两个作为镜像）

第七章 文件管理

文件的基本概念

文件是以硬盘为载体存储在计算机上的信息集合。在系统运行是，计算机以进程为基本单位进行资源的调度和分配；而在用户进行的输入、输出中，则以文件为基本单位

文件的属性

除了文件数据，操作系统还会保存与文件相关的信息，这些附加信息称为文件属性或文件元数据。

文件控制块

**操作系统通过文件控制块（FCB）来维护文件元数据**。FCB包含了**文件基本信息**（文件名、物理位置、逻辑结构..），存储控制信息、使用信息 FCB的有序集合称为**文件目录**。一个文件目录也被视为一个文件，称为**目录文件** #### 索引结点 文件目录通常存放在磁盘上，在查找目录的过程中，我们用给定的文件名逐一比较。这些操作都在内存中进行，由于元数据的冗余导致占用内存过大，所以我们将**文件名和文件描述信息分开**，使**文件描述信息单独形成一个称为索引结点的数据结构，简称 i结点。** ### 文件的逻辑结构

无结构文件

流式文件，以字节为单位。

有结构文件

顺序文件

文件中的记录一个接一个的顺序排列，记录通常是定长的。一类是串结构，一般按存入时间先后排序，必须从头开始检索；一类是顺序结构，所有记录按关键字排序，可以折半查找

顺序文件在批量操作效率高，但是需要增删改单个记录时效率低

索引文件

索引表按关键字排序，索引表本身也是个定长记录的顺序文件。索引文件实现了随机检索。

image-20260116103847633

索引顺序文件

索引顺序文件及那个顺序文件中所有记录分为若干个组，为顺序文件建立一张索引表，在索引表中为每组中的第一条记录建立一个索引项

image-20260116104513020

直接文件或散列文件

给定记录的键值或通过散列函数转换的键值决定记录的物理地址。没有顺序的特性。有很高的存取速度。

文件的物理结构

连续分配

image-20260116104947911

支持顺序访问和直接访问

链接分配

隐式链接

image-20260116105028095

显式链接

显式链接是指把用于连接文件各物理块的指针，从每个物理块的末尾中提取出来，显式地放在内存地一张链接表。该表在磁盘中仅设置一张，称为文件分配表（FAT）

image-20260116105042155

索引分配

混合索引分配

目录

目录的基本概念

FCB地有序集合就是文件目录，一个FCB就是一个文件目录项，文件目录作为一个文件就是目录文件。

目录的基本要求

  • 在用户所需要的文件名和文件之间提供一种映射：要实现按名存取
  • 提高目录的检索速度
  • 允许多个用户共享一个文件
  • 允许不同用户对不同文件采用相同给的名字

目录结构

单级目录

两级目录

树形目录结构

image-20260116105611560

当前目录：因为使用全路径名访问文件太麻烦，又因为运行时访问的文件大多局限于某个范围。所以，可为每个进程设置一个当前目录

进程对各个文件的访问都相当于对于当前目录进行的

相对路径名：从当前目录开始直到数据文件为止所构成的路径名

绝地路径名：从树根开始的路径名

目录查询

线性检索法

Hash法

文件共享

硬链接和软链接，类比一下静态链接和动态链接。软链接就像是快捷方式

基于索引结点的共享方式（硬链接）

文件的物理地址及其他的文件属性等信息，不再放在目录项中，而是放在索引结点中。

image-20260116105810610

索引结点还有一个链接计数count，当且仅当count=0时才删除该文件

image-20260116105939880

利用符号链实现文件共享（软链接）

系统创建一个LINK类型的新文件，，并将该文件写入用户目录中。在新文件中只包含被链接文件的路径名。这样的链接方式被称为符号链接

在利用符号链方式实现文件共享时, 只有文件主才拥有指向其索引结点的指针。而共享该文件的其他用户只有该文件的路径名,并不拥有指向其索引结点的指针。这样就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件主把一个共享文件删除后,若其他用户又试图通 过符号链去访问它时,则会访问失败,于是将符号链删除,此时不会产生任何影响。