进程同步

生产者-消费者问题

分析：

  1. 生产者消费者共享一个初始为空，大小为n的缓冲区
  2. 缓冲区没满时，生产者才能将产品放入缓冲区，否则等待
  3. 缓冲区不为空时，消费者才能取出产品，否则等待
  4. 缓冲区是临界资源，进程必须互斥访问（wait(mutex)和signal(mutex)成队出现）
  5. 多个P操作的顺序不能颠倒，应先执行对资源信号量的P操作，再执行对互斥信号量的P操作，否则可能会引起进程死锁，V操作可以颠倒
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
//生产者-消费者 伪代码
semophore empty = n; //空闲缓冲区的数量
semophore full = 0;  //产品数量、非空缓冲区的数量
semophore mutex = 1;  //互斥信号量，确保同时只有一个进程运行

producer {
    while( true ) {
	    生产产品
        P( empty );  // 等待缓冲区有空闲位置， 在使用PV操作时，条件变量需要在互斥锁之前
        P( mutex );  // 保证在product时不会有其他线程访问缓冲区

        // product
        buf.push( item, in );  // 将新资源放到buf[in]位置 
        in = ( in + 1 ) % 10;
        
        V( mutex );  // 唤醒的顺序可以不同
        V( items );  // 通知consumer缓冲区有资源可以取走
    }
}

consumer {
    while( true ) {
        P( full );  // 等待缓冲区有资源可以使用
        P( mutex );  // 保证在consume时不会有其他线程访问缓冲区

        // consume
        buf.pop( out );  // 将buf[out]位置的的资源取走
        out = ( out + 1 ) % 10;

        V( mutex );  // 唤醒的顺序可以不同
        V( empty );  // 通知缓冲区有空闲位置
    }
}

读者写者问题

分析：

  1. 读者和写者， 共享一组数据区
  2. 允许多个读者同时执行读操作
  3. 不允许读者、写者同时操作
  4. 不允许多个写者同时操作
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
36
37
38
39
40
semophore wmutex=1;  //对文件互斥访问
semophore rmutex=1;  //实现对readcount变量的互斥访问
int readcount =0;  //记录正在读的进程数量

void reader(){
	do(){
		P(w)
		P(rmutex);  
		if(readcount==0)  //如果当前没有读进程
			P(wmutex);    //将写进程占用
		readcount++;      //读进程数+1
		V(rmutex);        //释放写进程
		···
		读操作
		···
		P(rmutex);        
		readcount--;
		if(readcount ==0)
			V(wmutex);
		V(rmutex);    
	}while(TRUE)
}
首个读者：获取wmutex，阻止写者访问文件。 
后续读者：直接递增readcount，共享读权限。  
最后一个读者退出：释放wmutex，允许写者访问。

void writer() {
	do{
		P(wmutex);
		写操作
		V(wmutex);
	}while(TRUE)
}
必须等待所有读者完成（即 `wmutex` 可用），才能获取锁并写入。

void main(){
	cobegin;
	reader();writer();
	coend;   
}

防止写进程饥饿添加fair信号量保证写优先

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
36
37
38
39
40
41
42
43
semophore wmutex=1;  //对文件互斥访问
semophore rmutex=1;  //实现对readcount变量的互斥访问
int readcount =0;  //记录正在读的进程数量
semophore fair = 1;
void reader(){
	do(){
		P(fair);
		P(rmutex);  
		if(readcount==0)  //如果当前没有读进程
			P(wmutex);    //将写进程占用
		readcount++;      //读进程数+1
		V(rmutex);        //释放写进程
		V(fair);
		···
		读操作
		···
		P(rmutex);        
		readcount--;
		if(readcount ==0)
			V(wmutex);
		V(rmutex);    
	}while(TRUE)
}
首个读者：获取wmutex，阻止写者访问文件。 
后续读者：直接递增readcount，共享读权限。  
最后一个读者退出：释放wmutex，允许写者访问。

void writer() {
	do{
		P(fair);
		P(wmutex);
		写操作
		V(wmutex);
		V(fair);
	}while(TRUE)
}
必须等待所有读者完成（即 `wmutex` 可用），才能获取锁并写入。

void main(){
	cobegin;
	reader();writer();
	coend;   
}

哲学家进餐问题

分析：

  1. 需要同时持有两根筷子才能进餐
  2. 先取左边的筷子
1
2
3
4
5
6
7
8
9
10
11
12
13
chopstick[5]={1,1,1,1,1};
do{
	P(chopstick[i]);
	P(chopsick[(i+1)%5];
	···
	进餐
	···
	V(chopstick[i]);
	V(chopstick[(i+1)%5]);
	···
	思考
	···
}

当所有哲学家同时拿起左边的筷子时以上代码会引起死锁，下面为改进方法

  1. 最多允许四位哲学家同时拿左边的筷子，保证至少一名哲学家能够进餐，设置初始值为4的信号量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semophore chopstick[5]={1,1,1,1,1};
semophore r=4;
do{
	···
	思考
	···
	P(r);
	P(chopstick[i]);
	P(chopstick[(i+1)%5];
	···
	进餐
	···
	V(chopstick[i]);
	V(chopstick[(i+1)%5]);
	V(r);
	think();
	
}

内存管理

内存管理基本原理和功能

内存管理四大功能：

  1. 内存空间的分配和回收：由操作系统完成对主存的分配和回收
  2. 地址转换：使逻辑地址转换为物理地址
  3. 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存
  4. 存储保护：保证各道作业在各自的存储空间内运行，互不干扰

程序的装入和链接：

  1. 编译：将源代码编译为若干目标模块
  2. 链接：将编译后的一组目标模块和所需的库函数链接在一起，形成完整装入模块
  3. 装入：由装入程序将装入模块装入内存运行

程序链接的方式：

  1. 静态链接：在程序运行之前，先将各目标模块及他们所需的库函数链接成一个可执行程序，此后不再拆开
  2. 装入时动态链接：编译后所得的一组目标模块在装入时，边装入边链接
  3. 运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。便于修改和更新以及实现对目标模块的共享

装入内存的方式：

  1. 绝对装入：在编译时即知道程序将装入的内存具体地址，则编译程序将产生绝对地址的目标代码。而后将程序和数据装入内存，只适用于单道程序环境
  2. 可重定位装入：在多道程序环境中，多个目标模块的起始地址均为0开始。装入内存时，通过所分配的内存起始地址加上程序内的相对地址进行地址的动态变换，一次完成，又称为静态重定位。（必须一次性全部装入，运行期间不能动态扩充和移动）
  3. 动态运行时装入：装入模块装入内存后并不立即进行地址转换，而是等到程序执行时才进行。需要重定位寄存器的支持（可以将程序分哦到不连续的存储区中，程序运行前只需要装入部分代码，运行期间根据需要动态分配内存，便于程序段的共享，可以向用户提供一个比存储空间大得 多的地址空间）

逻辑地址空间与物理地址空间：

  1. 逻辑地址空间：程序编译后的每个模块都是以0开始编址，称为目标模块的逻辑地址。当链接为一个完整的可执行目标程序时，链接程序将按顺序以0开始编址，构造统一的逻辑地址空间。
  2. 物理地址空间：内存中物理单元的集合，是地址转换的最终地址，当装入程序将可执行代码装入内存中时，必须将逻辑地址转化为物理地址。

覆盖与交换

用于扩充内存

覆盖

基本思想：将程序分为多个段（多个模块）
常用的段常驻内存，不常用的段在需要时调入内存把内存划分为一个固定区和若干个覆盖区，固定区存放用户程序经常活跃的部。分，调入后就不再调出除非运行结束），其余部分按调用关系分段，将即将访问的段放在覆盖区，需要用到时调入内存，用不到时调出内存。其他放在外存，在需要调用前，系统将其调入覆盖区，替换原有的段。

交换

基本思想：把处于等待状态的进程或者被CPU剥夺运行权限的进程从内存移出到辅存，这一过程称为换出；把准备好竞争CPU的进程从辅存移到内存，这一过程称为换入。
暂时换出外存等待的进程状态为挂起状态（挂起态）。
挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

连续分配管理方式

单一连续分配：

内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统系统区相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

固定分区分配：

最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。

动态分区分配：

动态分区分配又称可变分区分配，是一种动态划分内存的分区方法。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区。系统分区的大小和数目是可变的。
两种常用的数据结构：空闲分区表和空闲分区链

  1. 空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息。
  2. 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息。

动态分区分配算法

  1. 首次适应算法（First Fit）：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。
  2. 最佳适应算法（Best Fit）：空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区。缺点：外部碎片多
  3. 最坏/大适应算法（Worst Fit）：空闲分区以容量递减的次序链接，找到第一个能满足要求的空闲分区，即挑选出最大的分区。缺点：不利于后续大进程的使用
  4. 邻近适应算法（Next Fit）：又称循环首次适应算法。同1，不同之处是，分配内存时从上次查找结束的位置开始继续查找

非连续分配方式

分页存储管理方式

1.基本分页管理方式

分页存储管理方式又分为基本分页存储管理方式和请求分页存储管理方式。

  1. 基本分页存储管理方式
    算法思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。
  2. 分页存储管理的基本概念：
    1. 页面和页面大小：进程中的块称为页(Page)，内存中的块称为页框(Page Frame，或页帧)。外存也以同样的单位进行划分，直接称为块(Block)。
    2. 地址结构：地址长度为32位，其中0~11位为页内偏移量/页内地址，每页大小为4kb；12~21位为页号，地址空间最多允许2^20页
    3. 页框/块的大小尽量设置为2的整数倍，若不足，需补齐
31~12 11~0
页号P 页内偏移量W
地址结构

物理地址=起始地址+页内偏移量
起始地址=块号*页面号/页框大小
页号=逻辑地址/页面长度(取整)
页内偏移量=逻辑地址%页面长度(取余)

页表，记录块号

页号(实际不记录，
数组编号即为页号)		 块号
0 3
1 1
2 2
3 0

例题：如何求页表项需要多少字节
若物理内存为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？

  1. 4GB=2^32 B, 4KB=2^12 B
  2. 2^32 / 2^12 = 2^20，至少需要20个二进制位，至少需要3字节即24位
  3. 内存块号为0~2^20 -1