进程

并发

特征：间断性、失去封闭性、不可再现性

进程描述

1、定义：

程序的一次执行、程序及数据在处理机上的活动、是系统分配和调度的独立单位

2、特征：动态性、并发性、独立性、异步性

3、状态：

就绪、执行、阻塞

挂起（变活动为静止）：静止就绪：在激活前不执行、静止阻塞：在得到条件前不会变为静止就绪。

4、PCB

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

定义：作为独立运行基本单位标志；能实现间断性运行方式；提供进程管理所需要信息；提供进程调度所需要信息；实现与其他进程的同步与通信

进程控制

状态转换：

1、更新PCB信息

2、PCB加入合适队列

3、分配/回收资源

进程切换：

1、将运行环境存PCB

2、PCB入响应队列

3、选另一个进程运行，更新PCB

4、根据PCB恢复进程运行环境。

使用原语：block原语（阻塞）wakeup原语（唤醒）

挂起原语：suspend、active

进程同步（重点）

机制：硬件同步、信号量、管程（不常用）

间接相互制约：访问相同资源

直接相互制约：源自进程间的合作，进程需要另一进程结果时发生。

1、生产者——消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

semaphore empty = n缓冲区剩余空间,full = 0缓冲区已写入空间,mutex = 1缓冲区访问;

void producer(){
	wait(empty);
	wait(mutex);
	//同时：使用and信号量
	wait(empty,mutex);
	//使用信号量集
	wait(empty,1,1,mutex,1,1)//信号量类型,至少为多少,需要多少（分配后为信号量-需要）
	...生产...
	buffer[in] = 产物;
	in = (in+1)%n; //缓冲区是一个循环缓冲区
	signal(mutex);
	signam(full);
}
void customer(){
	wait(full);//等到有东西
	wait(mutex);
	...消费...
	消费 = buffer[out];
	out = (out+1)%n; //缓冲区是一个循环缓冲区
	signal(mutex);
	signam(empty);//腾出空间
}

2、读者——写者问题

1
2
3
4
5
6
7
8
9
10
11
12

semaphore L = Rn mutex = 1;//最多支持Rn读者
reader(){
wait(RN,1,1);
wait(mutex,1,0);//不影响其他读者读
...
signal(RN,1);
}
writer(){
wait(mutex,1,1；L,Rn,0);//写时不允许读，要求读者信号量数RN
...
signal(mutex,1)
}

3、哲♂学♂家问题

1
2
3
4
5
6
7
8
9
10

//使用and信号量防止死锁：

void Van(){
	...Boy next door!...
	...Change the boss of gym...
	
	Swait(chopstick[(i+1)%5],chopstick[i]);//只有同时获得筷子，才进餐，否则不要占用筷子。
	...eat...
	Ssignal(chopstick[(i+1)%5],chopstick[i]);
}

进程消息传递、线程（不是重点）

直接消息传递：

1
2
3
4
5
6
7
8
9

//缓冲区
struct buffer{
int sender;
int size;
string message;
struct buffer *next;//指向下一个缓冲区指针
}

//太难了，你要考我认了

作业调度

平均周转时间Ti:从作业提交到完成消耗的时间

$1/n(\sum\limits_{i=1}^nT_i)$

平均带权周转时间：其中Ts为系统为其提供的时间

$1/n(\sum\limits_{i=1}^nT_i/T_s)$

高响应比优先算法：

$P=\frac{Wait\ time+need\ time}{need \ time}$

$R_p = \frac{Response\ time}{need\ time}$

表示的意思：作业等待时间相同时，要求时间越短越优先，而要求时间相同时，等待时间越长越优先。对于长作业，优先级会随着等待时间增加逐步提高。

进程调度

1、非抢占：进程不会被更高优先级的进程抢占

2、抢占方式：

优先级高的进程可以剥夺当前进程的运行

轮转调度：

将所有进程排成一个就绪队列，每隔一段时间产生一次中断，将CPU分给队首进程。如果当前进程运行完毕，直接进行调度，如果没有完成，重新排到队尾。

优先级调度：

非抢占：将处理机分配给优先级最高进程后，便运行到结束

抢占：运行过程中如果有优先级更高的就绪进程，则停止原进程执行，将处理机分配给更优先进程。

多级反馈队列：

分多个队列，第i+1个队列的时间片长度是i的两倍，但是优先级更低。如果第i队列的进程没有完成，就入第i+1队列的队尾，以此类推，直至完成。系统只有在完成i队列进程后（i队列空闲），才开始处理i+1队列进程，如果此时有更高优先级队列有新进程加入，则停止处理，先处理优先级更高进程。

实时调度

最早截止时间优先：

截止时间越早，优先级越高，其他同抢占式。

最低松弛度优先：

优先级取决于松弛程度

松弛程度 = 完成时间（比如200ms内）-需要时间（比如需要执行100ms）

松弛度越低，优先级越高。

死锁问题

产生死锁必要条件：

1、互斥条件：资源排他性使用

2、请求和保持条件：进程请求新的资源，又对已经有的资源保持不放

3、不可抢占条件：资源没使用完不能抢占

4、循环等待条件：存在进程—资源循环链。

处理方法：预防死锁，避免死锁，检测死锁，解除死锁

预防死锁

破坏除互斥条件以外的所有条件。

避免死锁：系统安全状态

银行家算法：找出一个安全序列

初始表：

Max Need Allocation Available

分配表：

Work Allocation Need Work+Allocation Finish

银行家算法：

1）检测进程需要的资源数是否超过宣布最大值

2）检测系统是否还有足够资源

3）试分配资源

4）进行安全性检查算法，安全再分配

安全性检查算法：

1）有足够资源时，Finish = true

2）从进程集合中找到一个进程未完成，但是可完成

3）进程完成后释放资源，跳回2

4）Finish全为true，安全。

存储器

连续分配方式：

固定分区分配：

将内存分为几个固定分区，分区大小相等或不相等

动态分区分配：

需要数据结构：空闲分区表、空闲分区链

分配算法：

首次适应算法：找到一个适应大小的空间就分配

循环首次适应算法：不是每次从链首，是从上一个找到的接下来找

最佳适应：

总能将能满足要求，又最小的分区分配出去

最坏适应：

总是挑最大的空闲区分配

分配操作：

分配：分配一个分区，剩余空间太小，就不切割，剩余空间大，就切割。

回收操作：将回收的空间和空闲的空间合并

伙伴系统：

无论已分配还是空闲，大小都是$2^n$，分配长度n空间时找一个值，$2^{i-1}<=n<=2^i$，如果找不到，就找更大的，但是要将该分区分为两份，以此类推。

紧凑：

将小作业移动，使其相邻接，将原来的分散空闲小分区拼成大的。

分页存储管理方式：

将进程的逻辑地址分成若干页，地址为页号、位移量（页内地址）。

页表：记录进程相应页对应内存中的物理块的一块表。

访问内存有效时间：有快表的情况

$EAT = a\cdot\lambda+(t+\lambda)\cdot(1-a)+t$

其中，lambda为查找快表时间，a为命中率，t为访问内存时间（说明：如果不在快表内，那么很显然需要访问两次内存，一次找地址，一次是访问数据）

两级和多级页表：

将页表放在某一物理块，外层页表记录的就是页表在哪个物理块，页表记录的就是页和物理块的对应关系。

地址变换：以页号为索引检索页表，找到在哪一页，然后将页表始址和页号与页表项长度的乘积相加，从页表中得到这一页的物理块号，与页内地址拼接得到物理地址。

虚拟存储

请求分页存储方式

当需要访问的页不在内存，便产生缺页中断（第一次调入也算缺页中断），然后将页面调入内存。

页面置换算法

1、最佳算法：被淘汰的页面是以后永不使用或是未来最长时间不会访问的页面。（理想算法）

2、FIFO算法：被淘汰的页面是最先进入的页面

3、LRU算法：被淘汰的页面是最近最久未使用的页面。（记录一个页面自从上次被访问经过的时间，调出是淘汰t最大的）

4、LFU算法：被淘汰的页面是最近使用最少的页面

5、Clock算法：将页面链接为一个循环队列，设置一个访问位，某页被访问时设为1，当这个页面被检查时，如果是1，就置0，如果是0，就换出。

I/O 系统

磁盘调度

1、先来先服务：仅仅适用于请求磁盘I/O较少场合

2、最短寻道时间优先：寻道所需时间最短的I/O请求先服务

3、扫描算法：磁盘磁头不停外向移动，处理请求，直至没有更外磁道的请求再内向移动，处理请求，直到没有更内磁道请求再外向移动。

4、循环扫描算法：磁头移到最外磁道后立刻回到最里的欲访问磁道，这样可以大大降低请求的等待时间

NStepSCAN和FSCAN算法：

NStepSCAN：将请求分为N个子队列，对于每个子队列，用SCAN算法，对于不同子队列，用FCFS算法。

FSCAN算法：对于当前请求的队列，用SCAN算法处理，而将在扫描期间的新请求，推迟到下一次扫描时再处理。

文件目录

文件控制块：包括文件名、拓展名、属性、时间日期、第一块号、盘块数等

索引结点：将文件名与文件描述信息分开，使文件描述信息单独成为一个称为索引结点的数据结构。这样就可以只检索文件名，而在检索时忽视其他信息，减少内存占用。

文件目录的类型

单级文件目录：只有一级文件目录，存放所有文件。

两级文件目录：每个用户拥有自己的用户目录。

树形目录：将文件称为树叶，将目录称为结点。应允许一个目录文件中的目录项，既可以做目录文件的FCB，也可以做数据文件的FCB。

磁盘存储器管理

组织方式：

连续组织方式:为每一个文件分配一组相邻接的盘块。

链接组织方式

1、隐式链接：在文件系统的每个目录项都设置一个指向文件第一个盘块的最后一个盘块的指针，每个盘块中都有一个指向下一个盘块的指针。

2、显式链接：将用于链接文件各物理块的指针显式地放在内存的一块链接表，整个磁盘只有一张。（这个表是文件分配表FAT）

索引组织方式

单级索引：每个文件分配一个索引块，将分配给这个文件的所有盘块号记录在这个索引块中。

多级索引：当一个索引块满事，再分配一个索引块，然后记录接下来分配的盘块，最后再为这些索引块建立一个索引，称为一级索引，多级以此类推。

增量式索引组织方式：在索引结点中设置数个直接地址项，一次间接地址项，多次间接地址项。其中一次间接地址块是索引块。

文件存储空间管理

空闲表法：连续分配方式使用，记录空闲区域的第一空闲盘块号、空闲盘块数。

空闲链表法：分为空闲盘块链和空闲盘区链，就是将空闲盘块和空闲盘区拉成一条链表。

位示图法：

用m*n个位构成示图，0未分配，1已分配。

分配时：找到一个空闲的map[i,j],分配后改为map[i,j] = 1，盘块：b=n(i-1)+j。

回收时：回收b号盘块，修改map[i,j] = 0；

其中$i=(b-1)\ DIV\ n+1$ ; $j=(b-1)\ MOD\ n+1$（整除、模）

成组链接法：

建立空闲盘块号栈，组织如下

其中N还作为栈顶指针，100代表还有100个空闲块，其指向S.free(99)

S.free(0)是栈底（第一个盘块），除存储数据外，后一组的盘块总数N和该组具有的盘块号也被记录于前一组的此处。

至于第一组，其分配叫做“空闲盘块号栈”

最后一组仅有99个空闲盘块，因为S.free(0)=0代表没有后续盘块，作为空闲盘块链的结束标志。