一.多进程图像的引出

1.cpu管理的直观想法

2.多进程图像

多个进程同时存在于内存，可能会出现前一个进程的地址中的内容被第二个进程更改。这样显然是不合理的。

我们首先会想到，是否可以设置DPL的值，也就是将其设置为特权级别，这样进程之间就不能互相访问了，但这里忽略了一个问题，DPL的设置是针对操作系统而言的，进程的DPL都等于3，即用户级权限，依然可以互相访问，所以这种解决方式的思路是错误的。

那如何保证进程间不冲突呢？直观的解决方式，就是给进程上锁，限制对内存地址的读写。

映射表就是实现限制访问的那个利器。映射表的思路即是利用虚拟内存实现地址分离。

说到这里，我们发现，所谓的多进程图像，不单单是进程的管理，还涉及到内存的管理。

多进程如何合作

先看下面的例子——

假设有一段空闲的内存空间，两块进程都想利用这块内存空间，这样有可能会出现一块内存空间出现两个不完整的进程片段，也就是说，进程间是可以互相合作的，但合作的方式需要被协调。

那怎样协调呢，纸上得来终觉浅，要想觉知此事，不妨理解生产者-消费者实例——

生产者不断的产生数据放入缓冲区，而消费者从缓冲区中取出数据进行处理，当缓冲区已满的时候，生产者阻塞，当缓冲区为空的时候，消费者阻塞

我们会使用三种方式来实现生产者-消费者问题——

在下文的进程同步中会提及。。。

二.线程的引出与实现

从上一节我们知道多进程是操作系统的最基本，最核心的图像，多进程可以被组织，合作与切换。

多进程的组织是通过状态与队列来实现的

那么多进程是如何被切换的呢？且听我娓娓道来——

1.用户级线程

线程的引出

既然我们要了解的是进程间的切换，那为什么学习的却是线程呢？

首先我们先来看宏观上的进程切换：一个进程，也就是指令执行序列+资源，在发生外中断后，切换到另一个进程。在这期间，指令访问的内存地址是通过映射表来获取的。这个切换是由中断引起的，因而会进入内核态，会涉及到资源的分配。而资源的分配是浪费时间的，那么为了提高进程执行的效率，能否将资源与指令的执行分离开，实现不动资源而只切换指令序列呢？——

我们来看直观的表述——

这样就引出了轻巧级的进程——线程。

线程的价值

要回答线程是否实用，也就是要回答多个执行序列+一个地址空间的思想是否实用。

我门来看下面的例子——

这个网页呈现出来的是，首先文字被加载出来，接着图片被加载，最后全部内容都展示了出来。

实际上它的程序执行流程是多个线程从浏览器的缓冲区中读取同一份资源，程序执行展示文本的线程时，在此期间切换到展示图片的线程，过一段时间又切换回来，给用户更好的体验。

这里我描述的比较生涩，其实多线程的执行，一言以蔽之，其实就是编程时多条线路并发执行：

线程的切换

开局一张图：

可以看出，这里线程间的切换是通过一个叫做Yield的函数来实现的，所以我们的核心就在于写出yeild函数的实现——

要完成切换，就要保存上一个线程的状态，状态的保存是依赖栈来实现的，我们先从两个执行序列与一个栈讲起——

两个执行序列与一个栈

这张图到底表达了什么意思呢？

在函数B中调用Yield函数，这时需要将程序B的下一条指令的地址压栈，跳转后，在C函数中调用了D函数并压栈，在D函数中调用Yield函数，此时我们需要跳转204的位置，跳转后，PC指针指向了地址204，接着往下执行，遇到**}**后，弹栈并跳转，然后程序指针跳到404处。

嗯哼，是我剧本拿错了吗？的确，就是这么戏剧性，我要的是弹栈104并跳转，可没想调回404啊，死循环。。。

那么这是为什么呢？因为我们共用了一个栈！！！

所以我们很自然的需要从一个栈过渡到了两个栈。

两个执行序列与两个栈

现在线程切换的时候，首先yield函数需要切换栈，这里就需要一个能够保存当前线程栈状态的容器，也就是TCB。

我们最后在执行yield函数时，首先切换TCB，然后Yiled函数结束，继续往下执行**},也就是执行ret指令**

弹栈执行104，一个线程切换就这样有惊无险的完成了。

这里不需要jmp 204,因为Yield函数执行完后，就会默认往下顺序执行。

完成了两个栈，我们再将包含线程切换的ThreadCreate函数做初始化，并在其中关联TCB与栈。

这样，一个完整的进程就有了——

说到这里，我们就可以来回答这个小结为什么叫用户级线程，因为field是用户级应用程序。

整个用户级线程可以实现有序的切换了，那么为什么还要内核级线程呢？当然是因为它有其天生的限制，而从另一个角度来说，核心级线程是用户级线程的扩展。

用户级线程的缺点

当用户级线程在执行指令过程中发生中断，系统会切换到内核态，然后执行中断程序，在执行完后，因为权限已经改变，无法切换回用户级线程，用户级线程不再执行。

2.内核级线程

3.核心级线程实现实例

我们首先来回顾一下内核级线程的切换——

宏观的看，内核级线程由用户级线程的两个栈演变成了两套栈，它的的实现机制大致分为五步——

用户栈通过int中断指令跳转到内核栈
在内核栈中存储当前内核线程的状态，而内核栈又由线程控制块TCB1维护
通过Schedule函数完成内核级线程跳转
在内核栈中存储当前内核线程的状态，而内核栈又由线程控制块TCB2维护
由内核栈跳转回用户栈

下面我们将具体实现这个内核级线程：

这个故事首先从进入内核开始，也就是从某个中断开始，这里的系统调用案例我们选择fork(),fork()函数是用于创建进程的，而进程实质上是资源+指令序列，指令序列就是一系列的线程，所以我们使用fork函数，是可以完成内核级线程的切换的。

我们来看下面的例子——

中断入口

在main函数中调用了A函数，之后在A函数的执行中又调用了fork系统调用，fork系统调用会引起中断，在触发中断处理程序时，首先会将之前用户态的栈进行保存，也就是将SS,SP压栈，接着跳转fork的中断处理程序，也就是system_call函数——

在system_call中，首先会做寄存器的压栈，也就是准备切换，然后跳转sys_fork系统调用开始切换，在这个系统调用中，首先将当前线程的TCB置给ex，接着判断ex的状态，本质上是判断TCB的state**，如果非0的话，也就是处于阻塞状态。就需要执行schedule以完成切换，此外，当时间片用完以后，也需要进行切换。

中断出口

完成了切换，那怎样返回呢？通过中断出口，那中断出口做了什么呢？对应中断入口一系列的入栈，中断出口会做弹栈操作。

我们描述了中断入口和中断出口，那在中断的过程中做了什么事情呢？

在中断中首先找到要切换的线程，再切换到该线程。这里面会涉及到线程的调度与切换，线程的调度我们后面会提及，这里我们只看线程的切换——

中断过程——线程切换

线程的切换是通过switch_to来完成的，在函数中主要通过长跳转来实现线程跳转——

首先使用movw指令将CPU中寄存器的内容都写入到到TSS中，TSS也就是任务结构段，它是进程控制块PCB的一部分。

首先通过TR寄存器(类CS寄存器)找到位于GDT表中的TSS描述符，即指向TSS段的指针，最终通过TSS描述符定位到TSS段。

而长跳转做的无非就是通过TR寄存器找到另一个线程的TSS描述符，通过TSS描述符找到TSS段，并将寄存器中的的内容也加载到TSS段中。

但以TSS的方式实现跳转的效率是低下的，因为TSS中的长跳转需要对一系列寄存器操作。之后我们将采用KIN stack的方式完成切换。

参考linux进程切换与TSS结构blog.51cto.com/stonehorse/…

在上一小节的学习中，我们了解了线程的切换，接着我们将范围放大，来一起学习线程创建，即ThreaCreate函数

首先从sys_fork函数开始我们的求知之旅——

在sys_fork函数中，首先将用户态状态入栈，以便子进程调用，接着在sys_fork函数中调用copy_process，可以看到这个函数的参数有一长串，细心观察的话，会发现都是父进程压入栈中的内容，也就是子进程和父进程是共用一套用户栈的。

那么子进程创建的细节是怎样的呢？

首先申请了一页的内存空间，我们再来回顾一下它的渊源：开机时memmap初始化，将内存分以4k为最小单元的页，需要申请内核空间时，则选取memmap不等于0的的一页内存空间即可。

接着**创建TCB,**也就是从申请的内存起始开始往后一页的这段内存空间。

然后创建内核栈和用户栈，最终将TCB与栈相关联。

最后，我们只需要完成一系列的初始化即可，这里面值得关注的是ip的初始化，也就是从栈中取出中断后下一条指令的内存地址，另外还需要eax初始化为0，那么eax有什么用呢？

我们经常看到的一个判断：if(!fork()){子进程执行},这里判断的条件即是eax的值，如果eax等于0，子进程执行，反之，父进程执行。

明确了子进程的执行条件，我们来看子进程的具体执行的代码，也就是exec系统调用——

我们从父进程的shell进入子进程的执行，当子进程执行完后，需要返回，那它会返回到哪里呢？我们知道在跳转执行的结束，会执行指令iret，所以返回的地址取决于iret中ret指令弹栈的IP寄存器内容。那IP指向哪里呢？

IP指向的位置，或者说IP寄存器中地址取决于struct_exec系统调用的参数。在它的执行中，将ex寄存器中的a.entry方法的地址加载到ret中作为IP的指向地址，a.entry是可执行文件的入口地址，当它连接产生可执行文件时，会将文件中的内容，即磁盘中的内容写入到内存执行，子进程执行完毕！

4.操作系统的那棵树

系统调用就是一种软中断处理程序

在这一小节中，我们不看学习新的内容，因为旧的内容还一团乱麻。所以我们有必要将之前的知识点连点成线，让它从萌芽开始，随时光浸淫，最终长成参天大树。

即便操作系统这颗很庞大的参天大树也是要从一个很小的火光发散的。就如同李志军老师告诫我们的一样——

The mind is not a vessel that needs filling,but wood that needs ignitng

我们的大脑不是装满水的容器，而应该是点燃的火光。

所以我们接下来的内容我们将从一个很小，很具体，很有价值的IDEA开始——

我们要在屏幕上交错出现A和B

首先回顾一下线程切换的思路——

运转CPU-》CPU没有好好运转-》要让CPU好好运转，首先从A函数跳到B函数-》跳转时使用1个栈和1个yeild发生混乱-》试着使用两个栈和两个TCB-》这样可以运转没错，但只能在用户态运转是不合适的-》引入两套栈，即内核栈的切换

首先从用户代码开始——

main(){
    if(!fork()){while(1)printf("A");}
    if(!fork()){while(1)printf("B");}
    wait();
}
复制代码

我们再将其用汇编来表述——

main(){
	mov _NR_fork,%eax
	int 0x80
100: mov %eax,res
	cmp1,res,0
	jne 208
200: printf("A")
	jmp 200
208: ...
304: wait()
}
复制代码

接着复现执行int 0x80后的代码——

main(){
	mov _NR_fork,%eax
	int 0x80
100: mov %eax , res
	cmp1 res,0
}

set_system_gate(0x80,&system_call);
system_call:
	call sys_call_table(,%eax,4)
复制代码

首先将系统调用号赋给**_NR_fork**，触发中断0x80，进入system_call，在该系统调用中，跳转system_call_table,将1赋给eax,也就是当前内核进程为父进程，在其中调用sys_fork——

sys_fork:
	push1 ..
	call copy_process
	ret
复制代码

开始创建子进程，子进程的创建也就是对父进程的复制，即copy_process_

copy_process(... ,long eip,..){
	p = (PCB *)get_free_page();
        p->tss.esp0 = p+4k;
        p->tss.esp = esp;
        p->tss.eax = 0;
        p->tss.eip = eip;
}
复制代码

完成了PCB的创建与初始化，也就是完成了子进程的创建，接着ret返回到父进程，iret返回用户态。

然后接着调用main函数，不断的创建线程，接着执行main函数，就到了wait()函数，它的具体实现是——

sys_waitpid(){
	current -> state = TASK_INTERRUPTTIBLE;
        schedule();
}
复制代码

将当前线程的状态置为阻塞，开始切换——

shedule(){
    if((*p)->state == TASK_RUNNING &&  (*p)->counter > c)
        	c = (*p) -> counter,next = i;
    	   ...
               switch_to(next);
}
复制代码

如果当前状态为运行态，使用调度算法得到要切换的线程，进入切换——

切换以后，就可以打出B了，但我们需要的是交替执行，所以要从B再进入A，也就是要完成切换，而切换是在内核态完成的，而用户态需要使用中断才能进入内核，那使用哪个中断呢？

时钟中断！！！

void sched_int(void){
    set_intr_gate(0x20,&timer_interrupt)
}

void  _time_interrupt:
	call do_time
        
void do_time(...){
        if((--current -> counter >0)) 
            return ;
        current -> counter = 0;
        schedule();     
 }
复制代码

将中断类型码赋给系统调用time_interrupt,在其中跳转do_time,在do_time中判断当前线程的数目，如果大于0，不切换，否则调用schedule切换线程。

最终在schdule中调用switch_to。不断循环，完结~

三. CPU调度

在上面的描述中，一个线程的切换就这样丝滑地完成了，但我们总将CPU调度刻意的当做一个黑盒子，这是因为CPU调度的确是一个很揪心的任务，但了解它又能加深我们对系统设计设计的理解，因此，这节内容，我们就明知山有虎，偏向虎山行了——

1.cpu调度策略

当一个线程阻塞后，就要切换到另一个线程，那应该切换到哪一个线程呢？直观的说，我们需要尽可能快的完成任务。那如何衡量任务执行的效率呢？就连任务本身都有不同的类型，比如I/O型，CPU型，按照不同的分类角度，又有前台型任务和后台型任务。

我们只捉住它关键的几个点来设计一个调度算法——

周转时间短，从任务进入到任务结束，也就是尽可能快的完成任务。周转时间=等待时间+运行时间。
响应时间短，即从操作到响应的时间短
系统内耗少，即系统吞吐量大，执行任务多

我们来看符合某些点的具体的算法思想，并用上面的指标来衡量它：

FCFS

先来先服务是最直观的调度算法，但一个系统是复杂的，仅考虑到公平只会事倍功半。

假设有n个任务，每个任务的周转时间分别为Ti，则它的平均响应时间为**：T1+T2+T3+Tn/n**,它的第n个任务的响应周转为T1+T2+T3+…+Tn，假如说T1的时间比其他时间的加和还要大，这样显然周转时间有可能很长，非常不合理。

那能否在FCFC调度算法的前提下，根据任务的长短来决定执行的顺序呢？那我们来了解一下SJF——短作业优先调度算法

SJF

假设有n个任务，按短作业优先的原则，调度的结果分别是：P1,P2,P3…Pn,则它总的周转时间为n*P1+(n-1)*p2+….，这样它的周转时间显然得到显著的降低。

但假如我现在有一个很长的作业，但它又非常紧急，我是不是应该适当的根据优先级来调整执行的顺序呢？这就要谈及RR——轮转时间片调度算法。

RR

时间片轮转的思想是将作业再细分，然后CPU为每个作业分配时间片，接着来交错地执行任务的最小单元。

但这里同样面临问题，假如时间片大的话，响应时间长；时间片小的话，系统内耗大，吞吐量小

我们先来微笑地说句fuck~

那假如我们对周转时间和响应时间的需求同时存在，该怎么办呢？

设置优先级！同时我们也需要首先遵守一个原则，人们更关心计算机与人的交互时间，也就是前台任务执行快，所以我们首先按RR的原则来安排前台任务，接着按照SJF的原则来安排后台任务，这两类任务之间通过动态的优先级设置进行互相切换。

要满足上一小节的复杂指标，给我们的直观感受就是，这个实现的算法一定繁琐至极，但linux0.11中的schdule函数却很好地处理了这个问题——

2.一个实际的schedule函数

我们在开始之前，首先要明确时间片和优先级是有一定的关系的，时间片大的本身一定程度上优先级就高，能解决复杂问题的算法即便代码量少，但思想的深度却不会低。

下面我们言归正传，来看chedule函数的实现——

schele(void){
    while(1){
         int i = NR_TASKS;
    	  int c= -1;
         int next = 0;
   	       p = &tasks[NR_TASKS];
   	       while(i--){
    		if(*p -> state == TASK_RUNNING &&  *p -> counter > c){//加入当前作业的状态为就绪态且优先级大
            		c = *p -> counter;
                    	next = i;	
           }
     	}
        if(c){
            break;     //找到最大的counter
        }
        for(p = &LAST_TASK;p > &FIRST_TASK; p--){	//重新设置优先级
            (*p) -> counter = ((*p) -> counter >> 1) + *p ->priority;
        }
        switch_to(next);
    }
}
复制代码

在这个程序中，counter是关键，它兼顾了优先级与时间片——

//时间片
void do_time(){
    if(-- current -> counter >0)
        	return;
    current -> counter = 0;
    schedule();
}
复制代码

即时间片为0时，则切换时间片。在这里counter满足轮转调度，保证了响应。

而下面的程序中，counter又体现了优先级——

if(*p -> state == TASK_RUNNING &&  *p -> counter > c){//加入当前作业的状态为就绪态且优先级大
            c = *p -> counter;
            next = i;	
 }

for(p = &LAST_TASK;p > &FIRST_TASK; p--){	//重新设置优先级
            (*p) -> counter = ((*p) -> counter >> 1) + *p ->priority;
 }
复制代码

这里counter体现的是动态的优先级，表现出来的是阻塞后进程的优先级会高于非阻塞进程的优先级，也就是优先前台进程。

但值得注意的是，counter是否超出会响应时间的界，我们不妨来定量地看一下——

假设进程n开始响应时的时间为p,而进程n的响应时间(时间片)是p+p/2,同样可以类比得到第无穷个进程的响应时间为p+p/2+p/4+…+p/(2的无穷次方) < 2p

四. 进程同步和死锁

我们在上一章中学习到了线程间的切换是如何完成的，而进程等于资源+可执行的指令序列(线程),那要完成进程的切换，也就是进程的并发执行，岂不是只需要知道资源是如何被调度的就可以了，那么资源如何表示，又如何量化呢，在调度资源的过程中，会出现怎样的问题，又应该怎样解决呢？这一系列的问题，我们都将在下面的内容中找到答案——

1.进程同步与信号量

所谓进程的合作，就是多个进程来完成同一个任务，之前我们浅谈过生产者与消费者的实例，这里我们对它进行进一步的剖析——

对于生产者而言，它生产了一个资源并放入缓冲区，当缓冲区满的时候，就不再生产。

同样的，对于消费者而言，它消费来自缓冲区的资源，当缓冲区空的时候，它就不再消费。

从这种机制中，我们看出，首先需要一个放置资源的缓冲区——

#define BUFFER_SIZE 10
//声明资源的结构
typedef struct{} item;
//声明缓冲区的大小
item buffer[BUFFER_SIZE];
int in = out = counter = 0;

复制代码

其次，我们来看最直观的生产者与消费者进程模型

//生产者
while(true){
    while(counter == BUFFER_SIZE);
    buffer[in] = item;
    in =  (in + 1) % BUFFER_SIZE;
    counter++;
}

//消费者
while(true){
    while(counter == 0);
    item = buffer[out] ;
    out=  (iout+ 1) % BUFFER_SIZE;
    counter--;
}
复制代码

在这个最基础的模型中，我们的确做到了去控制生产者消费者运行的时机，但进程的调度是不可预测的，我们不妨再扩充一下如何使用信号counter控制进程的休眠与唤醒。

//生产者
while(true){
    while(counter == BUFFER_SIZE){
        sleep();//缓冲区已满以后，就让创建好的进程进入休眠队列
    }
    buffer[in] = item;
    in =  (in + 1) % BUFFER_SIZE;
    counter++;
    if(counter  == 1){
	wakeup();//唤醒消费者	
    } 
}

//消费者
while(true){
    while(counter == 0){
        sleep();//缓冲区为空的时候，就让消费者进程进出入休眠队列
    }
    item = buffer[out] ;
    out=  (iout+ 1) % BUFFER_SIZE;
    counter--;
    if(counter  == BUFFER_SIZE-1){
	wakeup();//唤醒生产者
    } 
}
复制代码

一个第二版的生产者消费者模型就这样形成的，它无疑更完善了一些，但因为counter信号终究表示的比较宏观，导致在细节上出错了——

假设缓冲区已满，这时生产者进程P1运行，并进入休眠队列，紧接着生产者进程P2运行，也进入休眠队列，此时counter等于BUFFER_SIZE.然后消费者进程运行一次，缓冲区内内容减1，唤醒生产者，但在生产者执行之前，又有一个消费者进程运行，此时counter等于BUFFER_SIZE-2,则生产者进程P2不会被唤醒。

出现这样的问题无疑是因为信号counter仅仅能表示缓冲区中空闲的状态，而无法判断休眠队列中有几个进程，换句话说，事情不是非0即1的，可能这个1表示的还有1.0和1.00的区分——

因而我们要使这个信号可以表达休眠和唤醒两种状态，当然，这个时候已经不能称为信号了，不如就叫信号量？

从信号到信号量

通过信号量我们可以判断休眠或者唤醒的状态。

姑且将信号量记为sem，当sem=0时，表示无资源可用，淡然，需要注意的是，对于进程而言，所谓的资源就是空闲的空间；当sem<0时，表示有进程在等待资源，假设sem=-2，表示有两个进程在等待资源；当sem>0时，表示有多少个空闲资源。

接下来我们给出信号量的官方定义：

1965年，由荷兰学者Dijkstra提出的信号量用于记录，信号用于sleep和wakeup.

我们将信号量再去细化：

struct semphore{
    int value; //记录资源个数
    PCB * queue; //记录等待进程的队列
}
复制代码

此外，由信号量衍生出了P,V原语。P可以记做test，V则为increament

下面给出P,V原语的实现——

//p原语：没资源，队列休眠
P(semaphore s){
    s.value--;
    if(s.value < 0){
        sleep(s.queue);
    }
}

//V原语：有资源，唤醒队列
V(semaphore s){
    s.value++;
    if(s.value >= 0){
        wakeup(s.queue);
    }
}
复制代码

到这里，我们可以回过头来看生产者和消费者问题了，话不多说，上代码：

int fd = open ('buffer.txt');
write(fd,0,sizeof(int)); //写in
write(fd,0,sizeof(int)); //写out

semaphore full = 0;
semaphore empty = BUFFER_SIZE;
//声明互斥信号量为1,即并发修改数
semaphore mutex = 1;

Producer(item){
    //判断缓冲区是否已满
    P(empty);
    //判断mutex是否小于0,也就是判断访问的当前资源是否为互斥信号量
    P(mutex);//mutex--
    //在这里写入in，即将item写到in的位置
    V(mutex);//mutex++
    V(full);//full++
}

Consumer(item){
    P(full);//判断缓冲区为空
    //判断mutex是否小于0,也就是判断访问的当前资源是否为互斥信号量
    P(mutex);//mutex--
    //在这里写入iout，即从文件中的out位置读出到item中
    V(mutex);//mutex++
    V(empty);//empty++
}
复制代码

顺畅如斯，秒啊~

到这里的确已经迈出了一大步，但仍有些小瑕疵，那就是由于进程调度顺序不确定，导致两个进程同时访问一个信号量的状况——

2.对信号量的临界区

为什么要保护临界区呢？什么是临界区，且听我娓娓道来——

因为两个进程对同一份数据存在竞争关系，因而需要将这份资源作为临界区。而这里的竞争条件是指和调度有关的共享语义错误。

临界区： 一次只允许一个进程进入该进程的那一段代码，临界区的基本原则是互斥，

然而仅仅声明一段代码为临界区代码是不够的，一段好的临界区代码还应该是有空让进且有限等待。

首先开始进入临界区的第一种尝试——轮换法。

1.轮换法

首先，这个临界区的设计是满足互斥的，但假如在调用进程P0以后，继续调用进程P0，这时就不再满足有空就进的原则了，所以下一位——

2.标记法

CPU大量时间闲置的问题的确得到了解决，且满足互斥，但假如有这么一种情景——

两个标记都为true，那么两个进程都不再执行，我们可以类比生活中的例子：假设冰箱里没有牛奶，妻子看到丈夫大的标记后，认为丈夫会买，而丈夫看到妻子留下的标记后，认为妻子会买，这样没有真的去买了牛奶。

这是一种对称法**，而在现实中，要打破这种没人买牛奶的窘况，就需要一个人**相对勤快一些。

3.peterson算法

而映射到进程合作，也应该如此，在两个标记都为true的情况下，需要有一个进程去执行，而另一个进程则什么都不做，我们来看具体的实现——

这是peterson算法的思想，它满足了一个好临界区的几个条件，是目前最好的临界区实现方式！！！

两个进程竞争临界区的问题解决了，那一个多个进程呢，所谓万法不离其宗，我们来实际地体会一下

面包店算法

我们在开始的时候强调过，衡量临界区算法的标准是互斥进入，有空让进，有限等待。而正在之前的篇幅中，我们也验证了要同时满足这两个条件，需要结合轮换和标记的思想，那在多个进程中如何体现呢？

轮转：每个进程都有一个序号
标记：进程中序号最小的进入

首先选中第i个进程，即将它标记。并将当前进程序号最小的序号赋给数组num的第i个元素。

接着再取消当前的标记，即做标记只是为了取出当前最小的序号。然后遍历序号，假如有被选中的其他进程，且该进程的序号比当前进程小，则等待它执行完，否则执行当前进程。进程结束后，将数组num的第i个元素置0.开始下一次循环。

多个进程同步的问题的确可以通过面包店算法得到解决，但这么繁琐的算法看着就头疼，而且回顾为什么会产生临界区，本质上是因为不可控的调度导致的，而调度是要进入内核的，且进入内核的方式是中断，那我们只让一个进程触发中断不就可以保护临界区了吗？那么这样可行吗？

这就要谈到软硬件协同开发中的硬件了——

这里使用cli()将中断的寄存器INTR置1，而在执行完临界区代码以后，再将其置0，就可以实现同一时刻只有一个进程访问临界区了。这种方法的核心在于中断寄存器，但假如是多核CPU，那每个CPU中都有这样一个寄存器，改变一个CPU的中断寄存器对别的CPU是没有影响的，可见这个方法是有局限性的。

那要怎么办呢？显然我们需要一个全局的信号量来标记当前临界区的状态。这里我们尝试硬件原子指令法

boolean 
    //这是一段原子代码，即一次执行完毕，不回切出
    TestAndSet(boolean &x){//1.假如x为true，则执行完   2.假如为false,将x置为true并将false返回
    	booean rv = x;
    	x = true ;
    	return rv ;
     }


while(TestAndSet(&lock));
//临界区
lock = false;
//剩余区
复制代码

也就是说，假如信号量是上锁的的，则进入并执行完，执行完后开锁；而假如进去之后发现锁是开着的，则马上上锁，并返回等待下次执行。这种方式对于多CPU同样是可行的。

3.临界区的代码实现

在之前我们完成了信号量的引出，临界区的保护，接下来来看如何使用代码实现临界区。话不多说，我们直入主题——

sem.c //进入内核
typedef struct{//声明信号量的结构体
    char name[20];
    int value;
    task_struct * queue;
}semable[20]
    
 //用户态的程序
 producer.c
 main(){
       //从信号量结构体中读取empty的下标
 	sd = sem_open("empty");
       for（int i = 0; i<=5;i++）{
           //设置阻塞状态，切换进程
           sem_wait(sd);
           //在文件fd中写入4个字节的数据
           write(fd,&i,4);
       }
 }

//在semable中寻找name对应的，没找到则创建，找到则返回下标
sys_sem_open(char *queue);

sys_sem_wait(int sd){
        //中断保护
	cli();
        if(semtable[sd].value-- < 0){
            //这里设置自己为阻塞，将自己加入到队列semtable.[sd].queue中去 
            schedule();
        }
   	   sti();
}
复制代码

复杂的思想最终也不过凝结为这几句宏观的代码，但即便如此，我们也要不忘初心，去探寻那冰山下的百分之九十。

这样思想的应用在linux0.11中更是被广泛的应用，让我们来从那里学点思想吧——

//读磁盘块
bread(int dev,int block){
    struct buffer_head *bh;
    //开始磁盘读后睡眠，切换进程，再由磁盘中断将其唤醒，即同步
    ll_rw_block(READ,bh);
    wait_on_buffer(bh);
}
//锁住临界区
lock_buffer (buffer_head *bh){
    cli();
    //while?为什么不用if
    while(bh -> b_lock){//进入后，不管之前是否上锁，之后都要上锁
        sleep_on(&bh_wait);
        bh -> b_lock = 1;
    }
    sti();
}

void sleep_on(struct task_struct){
       //加入队列，号称世界上最隐蔽的队列？
	struct task_struct *tmp;
        tmp = *p;
        *p = current;
        current -> state = TASK_UNINTERUPTIBLE;
        schdule();
        if(tmp){
		tmp -> state = 0;
        }
        
}
复制代码

我们来挑战一下世界上最隐蔽的队列——

将tmp指向task_struct,再将p指向当前的task_struct，当前的即是队列的队首，也就是说将tmp指向队首的下一个，p指向队首。又这两个指针都是存储在这个进程的内核栈中的，因此下一次可从下一个进程task_struct的内核栈中取出tmp指向上一个进程，再将指针p指向当前进程。

这样就可以回答使用while，是将所有的进程状态都判断了一次，从而找出那个优先级高的，让他来执行。

这里的p是指针的指针，我们可以理解为p指向的是一个内存空间的起始地址，则三级指针，n级指针同样——

上面的内容在切换进程时，会将当前进程加入阻塞队列，那如何唤醒呢？

通过磁盘中断调用对临界区开锁的函数，并在其中调用wake_up函数，在其中改变了当前进程的状态，然后使用iret返回继续往下执行。

4.死锁处理

我们依然以生产者-消费者模型作为例子，我们知道不管在生产者抑或消费者函数，首先都是要判断缓冲区是否已满或者缓冲区为空，那假如将判断与之后的代码调换位置，会导致怎样的结果呢？

这样的话会导致死锁，通俗的说，也就是多个进程互相等待对方持有的资源，而造成谁也无法执行的现象

本质上说，死锁的成因是因为自己占有的资源和申请的资源造成环路等待。

我们再来看死锁的必要条件——

那怎样处理死锁呢？

那针对每种方法，我们可以具体在进程同步中如何做呢？

死锁预防 ：一次性申请所有需要资源，这样就不需要因为资源冲突而造成环路等待，但效率太低，没有使用的价值；另外一种直观的想法就是资源申请按需进行，不会造成死锁没错，但资源浪费比较严重，果断弃坑。
死锁避免：死锁避免的思想被银行家算法“完美”地实现了——

假设系统中的所有进程存在一个可以完成的执行序列，则称系统处于安全状态，而银行家算法就是用来找出这个安全序列的。

对于一个进程来说，它与资源间的关系分为目前占有的资源，还需要的资源，可供分配的资源三种。

来看具体的实现——
```
int Available[1,...,n];//每种资源剩余的数量
int Allocation[1,....,m];//已分配的资源数量
int Need[1,..,m];//进程还需要的各种资源数量
int work[1,..,m];//工作向量
bool Finish [1,..,n];//进程是否结束

work = Available;
Finish[1,..,n] = false;
while(true){
    for(i=1; i<=n; i++){
        if(Finish[i]==false&& Need[i]≤Work)
        {
            Work = Work + Allocation[i];
            Finish[i] = true; 
            break;
        }else 
        {
            goto end;
        }
    }
}
End: 
for(i=1;i<=n;i++) 
    if(Finish[i]==false) 
        return “deadlock”;
T(n)=O(mn2)

复制代码
```
银行家算法的实现相对通俗易懂一些，但同时带来了时间复杂度高的问题，而时间复杂度高的原因在于它会事无巨细的判断每一个，但出现死锁的概率毕竟比较低，所以判断所有就显得浪费时间。

那我们是否可以先假装分配，然后调用银行家算法，再判断是否可行呢？这样我们就需要申请一个死锁进程组，判断每一个序列是否为安全序列。
死锁检测+恢复 ：核心思想在于先发现问题，然后再处理，当发生死锁的时候，就让进程回滚，但是实现机制比较复杂
死锁忽略 ：究极秘诀——重启；