CAUTION

程序并发时[注意不是进程并发时]会引入新的特性：

1. 间断性：程序的运行会走走停停，相互受限制
2. 失去封闭性：由于资源被共享，失去了封闭性
3. 不可再现性：由于失去封闭性，程序也就不总是能够被再现。

于是引入进程。

进程#

TIP

进程是具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个单位。

$PCB(Process \ Control \ Block)$#

系统利用进程控制块($Process \ Control \ Block$)来描述进程的基本情况和活动过程，进而控制和管理进程。

程序段、相关的数据段和PCB三部分构成了进程实体。

$PCB$的作用#

1. $PCB$能够为进程提供作为独立运行基本单位的标志，系统利用$PCB$感知进程的存在。

2. 保存运行所必要的现场信息，保证能够”走走停停”地运行，比如进程独享的堆栈段，$CPU$需要用到的运行现场信息。

3. 保存进程的信息，比如进程名，进程状态，指向内存/外村中进程数据部分的指针，资源清单等。

4. 提供用于进程调度的信息，比如运行时长、优先级等。

5. 提供一些信号量，用于进程之间的通信和同步。

$PCB$中的信息#

1. 进程标识符：一般有外部标识符(便于用户访问[进程名])，内部标识符(进程号)
2. 处理机状态信息： 通用寄存器、指令计数器、程序状态字、用户栈指针
3. 进程调度信息：进程状态、进程优先级、进程运行时间、事件
4. 进程控制信息：程序内存/外存地址、数据内存/外存地址，信号量、消息队列，资源清单，$next\_PCB$指针等

进程的状态#

进程具有：

1. 动态性：强调过程。从创建进程到进程消亡的这个过程。
2. 并发性
3. 独立性
4. 异步性

TIP

进程具有7种状态，创建、活动就绪、静止就绪、活动阻塞、静止阻塞、执行、终止。

进程的创建#

OS可以通过内核提供的$Create$原语创建一个新的进程。

进程创建的过程#

1. 申请空白的$PCB$
2. 为进程分配必要的资源：内存、文件、I/O设备等
3. 初始化$PCB$
4. 如果进程可以被$OS$接受，则将进程插入就绪队列中去

CAUTION

进程可以创建其他进程，在一些$OS$中[比如$Unix$]，称为父进程和子进程，但在$Windows$中所有进程都是平级的，只要有句柄$handle$就能控制其他进程。

进程的终止#

进程终止的事件#

1. 正常运行完毕
2. 发生错误：程序越界。非法指令等
3. 外界终止：其他进程$kill$了进程

进程终止的过程#

1. 根据被终止进程的标识符，找到对应的$PCB$
2. 终止该进程，把进程的状态设置为终止
3. 终止子孙进程
4. 归还资源
5. 移除释放$PCB$

进程的同步#

TIP

为了多个进程可以有条不紊地运行，保留可再现性，必须引入进程同步机制。

使用同一种临界资源(间接制约)和进程之间本身存在的制约关系(如生产者-消费者关系)都会导致进程阻塞。

临界区是访问临界资源的那部分代码。

进入区是检查临界资源是否被占用的那部分代码。

退出区是恢复临界资源被占用标志的那部分代码。

硬件同步方法#

1. 关中断#

在每次测试锁之前就关中断，这样处理机就不会响应调度中断，也就不会调度到其他进程上了。

2. 利用$Test-and-Set$指令实现互斥#

3. 利用$Swap$指令实现互斥#

实际上都是用一个测试量不断和lock交换值来完成测试锁：

do{
    key = True;
    do{					// 进入区，测试锁
        swap(&key,&lock);
    }while(key);
    ... // 临界区
    lock = False; 		//退出区
}while(True);

信号量机制$Semaphores$#

1. 记录型信号量#

一个整型量$S.value$用来表示资源数目和一个队列$S.list$用来链接因该信号量不足而阻塞的进程，且仅能通过2个原子操作$wait(S)$、$signal(S)$来访问$S$。这两个操作也被叫做P操作、V操作。

struct Semaphore{		//记录型信号量
	int value;
	struct blcock_list list;
}

wait(Semaphore* S)		//P操作
{
	S->value--;
    if(S->value < 0)	block(S->list);
}

signal(Semaphore* S)	//V操作
{
    S->value++;
    if(S->value <= 0)	wakeup(S->list);
}

2. $AND$型信号量#

有时，单个进程需要访问多种临界资源。$AND$同步机制的基本思想是：将进程在整个运行过程中需要用到的所有资源，一次性全部地分配给进程。到最后再一齐释放。把各个信号量**“AND”**在一起。

Swait(S1,S2,...,Sn)
{
    while(True)
    {
        if(S1 >= 1 && S2 >= 1 && ... && Sn >= 1){
            S1--;
            S2--;
            ...
            Sn--;
            break;										//满足要求
        }else{
            block(Si.list); where Si is the first semaphore that is less than 1.
        }
    }
}

Ssignal(S1,S2,...,Sn)
{
    for(int i=1;i<=n;i++){
        Si++;
        wakeup **all** process in Si->list;			// 不用判断Si，因为未预先减
    }
}

3. 信号量集#

有时进程会对某一种临界资源，请求不止一个，也希望对临界资源的数量有所保护，当临界资源小于一定量时，就不再分配这种资源了。于是引入信号量集。

Swait(S1,t1,d1)
{
	while(True)
	{
		if(S1 >= t1)			// 只有当信号量满足数量要求时，才分配
		{
			S1 -= d1;			// 每次减小d1个
            break;
		}
        else{
            block(S1.list);
        }
	}
}

4. 管程机制#

像各种计算机资源被使用数据结构抽象地描述特性，也可以用抽象数据结构表示系统中的共享资源，对这些共享资源的操作都被定义为一个个在这个数据结构上的过程。进程对共享资源的申请、释放和其他操作都需要经过这个数据结构的过程来完成。

代表共享资源的数据结构和在该数据结构之上的这组过程合起来构成了一个资源管理模块，也就是管程。

如果管程中没有其他的机制，继续沿用信号量机制，能保证多个进程可以不同时访问同一临界资源，但是被阻塞的进程不会立即释放管程，所以其他需要调用管程的进程只能等待，不满足让权等待，因此加入条件变量机制。

condition x,y声明了条件$x$和$y$，也是用x.wait和x.signal

经典的同步问题#

1. 生产者-消费者问题#

TIP

生产者需要empty这一信号量有剩余，消费者需要full这一信号量有剩余。另外缓冲区也是临界资源，因此需要mutex来控制缓冲区。操作缓冲区前，需要请求mutex

int in = 0,out = 0;
item buffer[n];			//缓冲区
semaphore mutex = 1, empty = n, full = 0;

void producer() {
    do{
        produce an item in nextp;
        //进入区
        wait(empty);			//先wait资源型信号量
        wait(mutex);			//再wait互斥信号量
        
        //临界区
        buffer[in] = nextp;
        in = (in + 1) % n;
        //退出区
        signal(mutex);
        signal(full);
    }while(true);
}

void consumer(){
    do{
        wait(full);				//先资源型
        wait(mutex);			
        
        put buffer[out] in nextc;
        out = (out + 1) % n;
        
        signal(mutex);
        signal(empty);
        
        consume nextc;
    }while(true);
}

2. 哲学家进餐问题#

CAUTION

如果每一个哲学家都先请求它左边的筷子，就有可能产生死锁。

TIP

解决方案有：

1. 规定：最多只有$n-1$位哲学家可以拿起左边的筷子
2. 规定：只有当左右筷子都可用时，才能拿起筷子(AND)
3. 规定：$n$为奇数，奇数号哲学家先拿左边的，偶数号哲学家先拿右边的。$n$为偶数则反过来

TIP

证明$n(n>1,1只筷子肯定不行)$为奇数时，**奇数号哲学家先拿左边的，偶数号哲学家先拿右边[i号哲学家先拿$(i+1)$号筷子]的。**一定可行：

设哲学家为$1\sim n$号，筷子为$1\sim n$号。

假设此时没有一个哲学家可以拿起两双筷子。

$i$号哲学家先拿的一定都是奇数号筷子

原因：奇数$i$号哲学家先拿$i$号筷子，偶数$i$号哲学家($2\le i <n$)拿$i+1$号($3\le i \le n$)号筷子。成立

所以奇数号筷子会被争抢完。

偶数号筷子一定没人能拿起。

原因：能拿起，则一定有一个哲学家能够拿起两双筷子，与假设矛盾。

但每一个被拿起的奇数号筷子$i$，有可能是被：

1. $i$号哲学家拿起，而$(i+1)$号筷子是空闲的($1\le i \le n-1$)，有人可以拿起两只筷子，与假设矛盾
2. $i-1$号哲学家拿起，而$i-1$号筷子也是空闲的($2\le i \le n-1$)，该哲学家也可以拿起两只筷子，与假设矛盾

故没有一个时刻，任何一个哲学家都不能拿起两只筷子(死锁)。

3. 读者-写者问题#

进程的通信#

进程通信的类型#

1. 共享存储器系统#

1. 共享数据结构：不同的进程在共享的缓冲区中存取信息，效率低。
2. 共享存储区 ：不同进程在内存中的共享存储区中存/取信息。

2. 管道通信系统#

管道实际上就是一个共享文件。

发送进程就往该文件里以字符流的形式输入数据，而接受进程则应该读入共享文件中的字符流。

为了实现管道，必须做到：

1. 互斥，读者-写者同步
2. 同步，只有当文件未满时才可输入，只有当文件中有数据时才可读出
3. 只有当对方在线时，管道才有意义。

3. 消息传递系统#

以一种格式化的消息为单位，利用操作系统提供的一组通信命令（原语），使得消息在进程之间进行传递，完成数据交换。

也分为：

1. 直接通信： 发送进程通过操作系统提供的原语操作，直接把消息发送给接收进程。

   通过操作系统提供的send原语和receive原语实现

   • 对称寻址，send和receive都要带上进程名参数
   • 非对称寻址，receive不需要带上进程标识，可以接收来自任意进程的消息

2. 间接通信：发送进程和接收进程通过中间件（信箱）进行消息的发送和接收，完成通信。

   • 借助信箱，send和receive原语都要带上mailbox指定信箱。

4. 服务器-客户机系统#

1. 基于$Socket$的实现
   • 基于文件的实现：一个$Socket$对应一个文件
   • 基于网络的实现
2. 远程过程调用/远程方法调用(存根)

线程#

引入线程(Threads)的操作系统中，进程不再作为调度/独立运行的基本单位，只作为拥有资源的基本单位。而线程作为独立运行的基本单位。

线程的实现方式#

内核支持线程$KST$#

客户进程和内核进程实际上都是依赖于内核提供的服务来工作，有的线程也是基于内核的支持而运行的，这种线程叫做内核支持线程$KST$

用户级线程$ULT$#

用户级线程完全在用户空间中实现，用户级线程的实现、创建等操作完全不需要内核的支持，与内核完全无关！

CAUTION

值得说明的是，对于设置了用户级线程的系统，调度也还是以进程为单位进行的。

管理用户级线程时，也无需切换到内核态。都是由父进程自己管理自己的子线程。

用户级线程都运行在一个中间系统上，中间系统有2种不同的实现：

1. 运行时系统：一个管理线程的操作的集合，这些操作的过程/函数都处于用户空间，因此调度时无需切换到内核态。

2. 内核控制线程/轻量型线程($LWP$)：每个用户线程都会和某一个内核控制线程相连接，$LWP$又和对应的一个$KST$相连接，于是用户线程就可以通过$LWP$访问内核。[$LWP$也是一种$KST$，可以进行线程层级的调度。]