操作系统的接口与实现

相关知识

相关链接：

【构建操作系统】全局描述符表GDT

GDT（全居描述符表）和LDT（局部描述符表）

GDT（Global Descriptor Table）：全局描述符表

LDT：局部描述符表

GDT和LDT：GDT为一级描述符表，LDT为二级描述符表

段选择子：引用GDT和LDT中的段描述符所描述的段，是通过一个16-bit的数据结构来实现的，这个数据结构叫做Segment Selector——段选择子。它的高13位作为被引用的段描述符在GDT/LDT中的下标索引，bit 2用来指定被引用段描述符被放在GDT中还是到LDT中，bit 0和bit 1是RPL——请求特权等级，被用来做保护目的。如图所示：

task_struct：每个进程在内核中都有一个进程控制块(PCB)来维护进程相关的信息，Linux内核的进程控制块是task_struct结构体。Linux内核通过一个被称为进程描述符的task_struct结构体来管理进程，这个结构体包含了一个进程所需的所有信息。它定义在include/linux/sched.h文件中。

浅析Linux下的task_struct结构体

TSS(Task Struct Segement)：任务结构段，TSS是一个段，即一块内存，这里保存要切换的进程的cpu信息，包括各种寄存器的值、局部描述表ldt的段选择子等，切换时cpu会将这段内容存进各自对应的寄存器，然后就完成了切换。（任务切换或者说CPU状态更新实质上就是改变各个寄存器的值）

Linux中进程、线程和fork()

关于Linux中的线程，Linux采用了一种“偷懒”的方法，Linux没有专门的线程对象，当需要建立一个线程时，实际上内核创建的是一个进程对象，也就是task_struct，只不过这个进程对象和父进程共享了大量资源，有时也称为轻权进程（LightWeight Process）。Linux建立进程和线程的接口也一致，比如都是fork()，而通过不同的参数来指定要建立的是进程还是线程。调用fork()函数将返回两次，一次是在父进程中，一次是在子进程中，这一定会让大都数人疑惑。其实fork()就是把当前的进程对象task_struct复制一份，这样在进程队列中就多了一个进程对象，由于两个进程相同，所以调度器调度到父进程时，返回一次，调度到子进程时，返回一次。

那么fork()调用一次返回两次的原理是什么呢？这可通过do_fork()所调用的函数copy_thread()来回答。应用程序通过fork()系统调用进入内核空间，其内核态堆栈上保存着该进程的进程上下文（即该进程的各个寄存器），通过复制父进程的内核态堆栈上的进程上下文，同时将eax置为0（如linux 1.2，*childregs = *regs; childregs->eax = 0;），而父进程通过do_fork()的返回值（return last_pid）来得到fork()的返回值。

前言

当操作系统运行到main程序中有这样一行代码

1

if(!fork()){init();}

这是创建一个子进程，对于windows来说就是启动桌面，对于linux来说就是打开shell。这一篇文章说说操作系统的接口以及实现，即上层应用是如何穿过接口进入操作系统的

一、接口

1.接口的定义

操作系统接口：接口表现为函数调用，又由系统提供，所以称为系统调用

一般情况下我们有三种方式来操作计算机：

1.命令行：即通过命令程序，linux系统中常用此种方式 2.图形按钮：通过鼠标点击等操作实现对计算机的操控。windows系统在这方面做的就非常优秀。这种方式通过消息框架程序和消息处理程序实现 3.应用程序

不管采用何种方式，我们都需要让操作系统和应用程序之间建立联系。如何建立连接 ?

==操作系统接口==

接口其实是一种抽象，比如插排，它将内部的电路全部封装起来，只提供两个插口，用电设备插上就能用；不用管插座内部是如何实现的。

操作系统接口也具有连接两个东西、屏蔽细节、方便用户使用的特点。它连接上层应用软件和底层硬件，屏蔽细节，用户直接通过程序（应用软件）使用计算机，方便用户使用。==操作系统的接口其实就是一个个函数，知道它的功能然后直接调用就行，而不用管它内核里面是怎么实现的，因为这个函数是系统调用的，所以也称为系统调用。==比如：write()、read()等等

2.接口分类

操作系统接口的功能就是提供一个用户使用系统的界面。根据服务对象的不同，==操作系统的接口可以划分为两类：一是供用户使用的用户级接口，二是供程序使用的程序级接口。==

操作系统中有专门响应用户控制要求的接口，负责系统与用户之间的双向信息传送

(1)用户接口

用户接口就是操作系统向用户提供的使用界面。分为脱机接口与交互式接口两种

(2) 程序接口

程序级接口是为程序访问系统资源而提供的，它由一组系统调用组成。系统调用(System Call)可以看作是由操作系统内核提供的一组广义指令。程序员在设计程序时，凡涉及到系统资源访问的操作，如文件读/写、数据输入/输出、网络传输等，都必须通过系统调用来实现。所以说，==系统调用是操作系统提供给应用程序的唯一接口。==

从层次上来看，用户接口属于高层接口，是用户与操作系统之间的接口。而程序接口则是低级接口，是任何核外程序(包括应用程序和系统程序)与操作系统内核之间的接口。用户接口的功能最终是通过程序接口来实现的。

二、系统调用的实现

1.系统调用

==计算机硬件系统并不允许我们在内存中通过jmp等跳转指令直接调用操作系统内核提供的函数，因为这样有可能会导致敏感信息的泄露==

为了确保系统的安全性，计算机硬件为我们设计了内核态和用户态的模式，内核态可以访问用户态的信息，但用户态不能访问内核态。

用户程序的CPL（Current Privilege Level）初始化结果是3，而操作系统内核里函数的DPL（Descriptor Privilege Level）是0，所以用户对内核的访问权限不够。

CPL寄存器表示当前程序执行在什么态，0表示内核态，3表示用户态；

DPL寄存器表示即将访问的数据在什么段，同样0表示内核段，3表示用户段。

每次访问数据的时候检查两个寄存器的大小关系，若DPL≥CPL，则可以访问，反之，则不能访问

把内存分为了操作系统内核段和用户程序用户段，把在内核段执行的代码和数据称为处于内核态，把在用户段执行的代码和数据称为处于用户态，将内核程序和用户程序隔离。所以：

内核态：处于内核态可以访问用户段和内核段的数据

用户态：处于用户态只能访问用户段的数据而不能访问内核段的数据

为了实现系统调用，操作系统为我们提供了用户程序调用内核函数的唯一方法：==中断指令int==。当程序执行到int指令时，int指令会将CS中的CPL修改为0，当访问内核结束之后，又将CPL重置为3继续执行用户程序。

系统调用的核心：

(1)用户程序中包含一段包含int指令的代码

(2)操作系统中有中断函数表，从中可以获取中断服务函数入口地址

(3)操作系统执行中断服务函数

CPL是当前进程的权限级别(Current Privilege Level)，是当前正在执行的代码所在的段的特权级，存在于cs寄存器的低两位。

RPL说明的是进程对段访问的请求权限(Request Privilege Level)，是对于段选择子而言的，每个段选择子有自己的RPL，它说明的是进程对段访问的请求权限，有点像函数参数。而且RPL对每个段来说不是固定的，两次访问同一段时的RPL可以不同。RPL可能会削弱CPL的作用，例如当前CPL=0的进程要访问一个数据段，它把段选择符中的RPL设为3，这样虽然它对该段仍然只有特权为3的访问权限。

DPL存储在段描述符中，规定访问该段的权限级别(Descriptor Privilege Level)，每个段的DPL固定。 当进程访问一个段时，需要进程特权级检查，一般要求DPL >= max {CPL, RPL}

2.具体实现

以printf为例：printf(“%d”,a)

内核中printf()函数：

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

//printf()产生格式化信息输出到标准设备stdout(1),在屏幕上显示
// 参数fmt：指定输出将采用的格式
static int printf(const char *fmt, ...)
{
	va_list args;
	int i;

	va_start(args, fmt);
	write(1,printbuf,i=vsprintf(printbuf, fmt, args));
	va_end(args);
	return i;
}

在printf()内部其实是调用了系统函数write()

1
2
3
4

ssize_t write(int fd, const void *buf, size_t count);
//fd：要进行写操作的文件描述符
//buf：需要输出的缓冲区
//count：最大输出字节计数

printf()函数的形参和write()的形参是不一样的，因此如果printf(“%d”,a)能调用write函数的话，肯定要对printf的形参进行处理，使其符合write函数的格式，或者说换一种方式调用。在printf()函数里面调用write()如下所示：

_syscall3 是一个嵌入汇编宏定义

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

#define _syscall3(type,name,atype,a,btype,b,ctype,c) 
type name(atype a,btype b,ctype c) 
{ 
long __res; 
__asm__ volatile ("int $0x80" 
	: "=a" (__res) 
	: "0" (__NR_##name),"b" ((long)(a)),"c" ((long)(b)),"d" ((long)(c))); 
if (__res>=0) 
	return (type) __res; 
errno=-__res; 
return -1; 
}

==分析：==

_syscall3这个宏调用之后就是展开成上面的一段汇编代码

比如write调用：

1

_syscall3(int, write, int, fd, const char* buf, off_t, count)

就是将宏展开的代码中的

1

type=int,name=write,atype=int,a=fd,btype=const char * ,b=buf,ctype=off_t,c=count;

用这些来替换,所以

1

type name(atype a, btype b, ctype c)

就变成了

1

int write(int fd,const char * buf, off_t count)

这样，展开的汇编代码一样跟着变。int 0x80这个中断，前面已经说过在head.s里面会重新建立idt表，之后中断就是表示根据中断号查那个表，然后获取中断服务函数的入口地址，==0x80这个中断就是进入操作系统内核，这是上层应用进入操作系统的唯一手段==，int 0x80相当于是操作系统的一个门户

接着看_syscall3宏定义下面的代码

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

long __res;     //定义一个寄存器
__asm__ volatile ("int $0x80"   //中断指令
	: "=a" (__res)       //输出，最后将eax-->res中，作为函数输出
	: "0" (__NR_##name),"b" ((long)(a)),"c" ((long)(b)),"d" ((long)(c)));    //输入
	// "0":表示使用与上面同个位置的输出相同的寄存器 eax
	// 将__NR_##name赋值给eax
	//__NR_write称为系统调用号
	// 然后，把形参的a、b、c依次赋值给ebx、ecx、edx三个寄存器
if (__res>=0) 
	return (type) __res; 
errno=-__res; 
return -1; 

这是一段内嵌汇编，分为四部分

1
2
3
4
5

__asm__("汇编语句"
		:输出寄存器
		:输入寄存器
		:会被修改的寄存器
		)

详情见下面这篇文章：

GCC 内联汇编

__NR_write称为系统调用号

1
2

在linux/inlcude/unistd.h中
# define __NR_write 4   

所有的系统调用都是通过int 0x80这个中断来调用的,

根据这个系统调用号来区分__NR_write表示write调用，会接着执行write对应的内核代码，__NR_read表示read调用，同理，其他的系统调用号也是如此

在内嵌汇编中,“a"这种被称作==限制字符==

1
2
3
4
5
6
7
8

"a"               将输入变量放入eax
"b"               将输入变量放入ebx
"c"               将输入变量放入ecx
"d"               将输入变量放入edx
"s"               将输入变量放入esi
"d"               将输入变量放入edi
"q"               将输入变量放入eax，ebx，ecx，edx中的一个
"r"               将输入变量放入通用寄存器，也就是eax，ebx，ecx，edx，esi，edi中的一个

所以，把形参的a、b、c依次赋值给ebx、ecx、edx三个寄存器

输入完成之后就通过int 0x80这个中断号进入操作系统，int 0x80这条指令执行完之后，eax中就会存放int 0x80的返回值，然后将这个返回值赋值给__res，__res就是int write()这个系统调用的返回值。write这个系统调用也就结束了

1
2
3
4
5
6
7
8

小结:_syscall3宏定义
格式：#define _syscall3(type,name,atype,a,btype,b,ctype,c)

type 表示函数返回值，name表示函数名，后面分别是三个形参的类型和行参名。

name不同，系统调用号不同，所以调用_syscall3之后执行的代码不同，在宏里面通过

int 0x80进入系统内核并将指条指令的结果存在eax寄存器中，然后返回到宏的调用处

==INT 0x80 指令==

int 0x80是进入中断服务函数的一条指令，所以int 指令首先要查idt表转去哪里执行

1
2

void sched_init(void)
{ set_system_gate(0x80,&system_call); }

int 0x80对应的中断处理程序就是system_call，从这个init就知道这是一个初始化，0x80这个中断就是用后面这个system_call来处理，那么系统是怎么设置的呢？通过set_system_gate这个宏

1
2
3

在linux/include/asm/system.h中
#define set_system_gate(n, addr) 
_set_gate(&idt[n],15,3,addr); //idt是中断向量表基址

然后在set_system_gate这个宏又调用了_set_gate这个宏，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#define _set_gate(gate_addr,type,dpl,addr) 
__asm__ ("movw %%dx,%%axnt" 
	"movw %0,%%dxnt" 
	"movl %%eax,%1nt" 
	"movl %%edx,%2" 
	: 
	: "i" ((short) (0x8000+(dpl<<13)+(type<<8))), 
	"o" (*((char *) (gate_addr))), 
	"o" (*(4+(char *) (gate_addr))), 
	"d" ((char *) (addr)),"a" (0x00080000))

_set_gate这个宏的作用就是建立一个类似这样的下图表，处理函数入口点偏移=system_call,DPL就是3，段选择符就是0x0008,即CS是8

用户态的程序如果要进入内核，必须使用0x80号中断，那么就必须先要进入idt表。用户态的CPL=3，且idt表的DPL故意设置成3，因此能够跳到idt表，跳到idt表中之后就能找到之后程序跳转的地方，也就是中断服务函数的起始地址，CS就是段选择符（8），ip就是”处理函数入口点偏移“。

1

在setup.s中指令： jmpi 0,8

这条指令表示根据gdt表跳转到内核代码的地址0处。CS=8，ip=system_call就是跳到内核的system_call这个函数；另外如果CS=8，那么CPL=0，因为CPL是CS最低两位。也就是说当前程序的特权级变了，变成内核态的了。完整流程：初始化的时候0x80号中断的DPL设成3，让用户态的代码能跳进来，跳进来之后根据CS=8将CPL设为0，到了内核态，到了内核态就什么都能干了，将来int 0x80返回的之后，CS最后两位肯定变成3，变成用户态

中断处理函数system_call

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

在linux/kernel/system_call.s中

nr_system_calls=72
.globl _system_call
_system_call: cmpl $nr_system_calls-1,%eax
ja bad_sys_call
push %ds push %es push %fs
pushl %edx pushl %ecx pushl %ebx //调用的参数
movl $0x10,%edx mov %dx,%ds mov %dx,%es //内核数据
movl $0x17,%edx mov %dx,%fs //fs可以找到用户数据
call _sys_call_table(,%eax,4) //a(,%eax,4)=a+4*eax
pushl %eax //返回值压栈，留着ret_from_sys_call时用
... //其他代码
ret_from_sys_call: popl %eax, 其他pop, iret

前面都是压栈和赋值，接着调用了_sys_call_table(,%eax,4)。

a(,%eax,4)=a+4_eax,所以_sys_call_table(,%eax,4)=_sys_call_table+4_%eax这是一种寻址方式。eax是系统调用号

_sys_call_table

1
2
3
4
5
6
7

在include/linux/sys.h中
fn_ptr sys_call_table[]=
{sys_setup, sys_exit, sys_fork, sys_read, sys_write,
...};

在include/linux/sched.h中
typedef int (fn_ptr*)();

sys_call_table是一个fn_ptr类型的全局函数表，fn_ptr是一个函数指针，4个字节，这就是_sys_call_table+4*%eax；这里为什么要*4的原因，sys_call_table的每一项都是4个字节，然后就可以根据eax来知道要调用的真正中断服务函数的入口地址了，对于write系统函数来说，就sys_write

系统调用进入内核态之后的过程：

printf ->_syscall3 ->write -> int 0x80 -> system_call -> sys_call_table -> sys_write

printf通用_syscall3这个宏调用write函数，在write函数里面用system_call来处理int 0x80,在system_call中会调用system_call_table这个表，根据eax中存储的系统调用号就可以找到真正的sys_write了。

main中，CPL=3，int 0x80的DPL也设置成3，这个时候就可以传过去，然后CPL就被设置成0，访问哪个地方都可以

总结

操作系统接口就是由C语言代码和由操作系统提供的一些重要函数组成。又因为这些函数调用时系统提供的，所以又叫系统调用(system_call)。我们通过系统调用就能在应用程序和操作系统之间建立连接

进程与线程

进程

我们都知道计算机的核心是CPU，它承担了所有的计算任务，而操作系统是计算机的管理者，它负责任务的调度，资源的分配和管理，统领整个计算机硬件；应用程序是具有某种功能的程序，程序是运行于操作系统之上的。

进程是一个具有一定独立功能的程序在一个数据集上的一次动态执行的过程，是操作系统进行资源分配和调度的一个独立单位，是应用程序运行的载体。进程是一种抽象的概念，从来没有统一的标准定义。进程一般由程序，数据集合和进程控制块三部分组成。程序用于描述进程要完成的功能，是控制进程执行的指令集；数据集合是程序在执行时所需要的数据和工作区；程序控制块包含进程的描述信息和控制信息是进程存在的唯一标志

进程具有的特征：

动态性：进程是程序的一次执行过程，是临时的，有生命期的，是动态产生，动态消亡的；

并发性：任何进程都可以同其他进程一起并发执行；

独立性：进程是系统进行资源分配和调度的一个独立单位；

结构性：进程由程序，数据和进程控制块三部分组成

线程

在早期的操作系统中并没有线程的概念，进程是拥有资源和独立运行的最小单位，也是程序执行的最小单位。任务调度采用的是时间片轮转的抢占式调度方式，而进程是任务调度的最小单位，每个进程有各自独立的一块内存，使得各个进程之间内存地址相互隔离。

后来，随着计算机的发展，对CPU的要求越来越高，进程之间的切换开销较大，已经无法满足越来越复杂的程序的要求了。于是就发明了线程，线程是程序执行中一个单一的顺序控制流程，是程序执行流的最小单元，是处理器调度和分派的基本单位。一个进程可以有一个或多个线程，各个线程之间共享程序的内存空间(也就是所在进程的内存空间)。一个标准的线程由线程ID，当前指令指针PC，寄存器和堆栈组成。而进程由内存空间(代码，数据，进程空间，打开的文件)和一个或多个线程组成。

进程与线程的区别

1. 线程是程序执行的最小单位，而进程是操作系统分配资源的最小单位；

2. 一个进程由一个或多个线程组成，线程是一个进程中代码的不同执行路线

3. 进程之间相互独立，但同一进程下的各个线程之间共享程序的内存空间(包括代码段，数据集，堆等)及一些进程级的资源(如打开文件和信号等)，某进程内的线程在其他进程不可见；

4. 调度和切换：线程上下文切换比进程上下文切换要快得多

任务调度

大部分操作系统的任务调度是采用时间片轮转的抢占式调度方式，也就是说一个任务执行一小段时间后强制暂停去执行下一个任务，每个任务轮流执行。任务执行的一小段时间叫做时间片，任务正在执行时的状态叫运行状态，任务执行一段时间后强制暂停去执行下一个任务，被暂停的任务就处于就绪状态，等待下一个属于它的时间片的到来。这样每个任务都能得到执行，由于CPU的执行效率非常高，时间片非常短，在各个任务之间快速地切换，给人的感觉就是多个任务在“同时进行”，这也就是我们所说的并发

CPU的工作原理

给一个初始PC地址，按顺序取址执行

PCB ：process control block

为了描述控制进程的运行，系统中存放进程的管理和控制信息的数据结构称为进程控制块（PCB Process Control Block），它是进程实体的一部分，是操作系统中最重要的记录性数据结构。它是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。

TCB ：thread control block

线程有自己的TCB，thread control block, 只负责这条流程的信息，包括PC程序计数器，SP堆栈，State状态，和寄存器。有不同的控制流，需要不同的寄存器来表示控制流的执行状态，每个线程有独立的这些信息，但共享一个资源。

ESP（Extended Stack Pointer）

ESP为扩展栈指针寄存器，是指针寄存器的一种，用于存放函数栈顶指针。与之对应的是EBP（Extended Base Pointer），扩展基址指针寄存器，也被称为帧指针寄存器，用于存放函数栈底指针。

ESP为栈指针，用于指向栈的栈顶（下一个压入栈的活动记录的顶部），而EBP为帧指针，指向当前活动记录的底部

初识多进程

一、CPU工作原理

CPU工作原理很简单，就是不断的取指执行。CPU根据PC寄存器中的值到内存中取指令，PC会自动+1，当执行完本条指令后，CPU又根据PC寄存器取指执行。

所以我们让CPU执行一段程序最直接的做法就是让PC的值设置为程序的起始地址，这样CPU会自动的执行这段程序直到程序结束。

==CPU的工作原理：取指执行（自动的取指执行）==

但是如果我们不对CPU进行管理，会导致CPU的利用率较低。

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

int main(int argc, char* argv[])
{
	int i , to, *fp, sum = 0;
	to = atoi(argv[1]);
	for(i=1; i<=to; i++)
	{
		sum = sum + i;
		fprintf(fp,“%d”, sum);
	}
}
//执行时间为 0.30521424865722897

int main(int argc, char* argv[])
{
	int i , to, *fp, sum = 0;
	to = atoi(argv[1]);
	for(i=1; i<=to; i++)
	{
		sum = sum + i;
	}
}
//执行时间为： 0.006346824075317383

从上面可以看到相同的循环次数，但IO任务的执行时间远远大于计算任务，但在执行IO任务时，CPU是空闲的，此时CPU利用率很低。我们可以让CPU在这段时间里忙碌起来，这就要我们对CPU进行管理。

当将PC的值设置为程序的起始地址，如果不对CPU进行管理，让CPU自动的取指执行，如果程序有大量的IO任务时，CPU的利用率极低，所以我们要对CPU进行管理，提高CPU的利用率

CPU管理

当在执行IO任务时，此时CPU处于空闲状态，我们可以将CPU分配给其他程序使用，当IO任务完成时，CPU又切换到该程序继续执行。

管理：核心是任务的切换，内存存放多个程序，多个程序交替执行

CPU的利用率将会提高：

任务切换：当一个程序执行IO任务时，把PC的值设置为另一个程序的执行地址就可以去执行另一个程序，然后IO任务完成，又切回原来的程序执行

但是，如何在让CPU切换回来呢？

运行中的程序会有一个称为PCB的数据结构，这个数据结构是用来记录当前程序运行的状态信息的，在进行任务切换时，将一些必要的信息压栈（如CS,IP)，然后要切换回来时，出栈（恢复成切换任务前的状态)，即可以让当前PC指针指向原来的程序位置，继续运行。

二、多进程

1.引入进程

进程：==进程是进行（执行） 中的程序==(CPU的管理是为了提高CPU的利用率，提高的核心思想就是多道程序交替执行，为了实现多道程序交替执行，通过进程来管理程序的运行）

进程和程序区别：

1
2
3

1.进程是有状态的。有开始、结束等运行状态，而程序没有。
2.进程会记录一些寄存器的值，这些值就是上下文。
3.进程会走走停停，程序没有这个概念。

2.多进程

多进程图像：启动多个程序，交替执行，能充分利用CPU，启动了的的程序就是进程，多个进程的推进，操作系统只要把这些进程记录好，按照合理的次序推进(分配资源，进行调度)

多进程图像一直存在于操作系统启动到关机的整个过程中

操作系统在启动时开的第一个进程是shell或者windows桌面，shell再启动其他进程

启动shell程序：

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

//一个命令启动一个进程， 返回shell再启动其他进程
int main(int argc, char * argv[])
{ 
	while(1) 
	{ 
		scanf(“%s”, cmd);
		if(!fork()) 
		{ 
			exec(cmd);
		} 
		wait(); 
	}
}

shell程序中在等待输入命令（CMD），有命令输入后就启动该命令对应的进程，然后返回shell再等待启动其他进程。如下图所示：

3.多进程的组织

==多进程的组织：PCB + 状态 + 队列==

每个进程都有个PCB（progress control block）来记录该进程的信息，操作系统依赖PCB来感知该进程，通过对PCB的感知将进程排入不同的队列，放在不同的状态中。如图

三种不同的队列分别对应==运行态、就绪态、阻塞态。==操作系统控制进程在不同状态间切换将他们同时推进。形成如下状态图

时间片

时间片即CPU分配给各个程序的时间，每个线程被分配一个时间段，称作它的时间片，即该进程允许运行的时间，使各个程序从表面上看是同时进行的。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。而不会造成CPU资源浪费。在宏观上：我们可以同时打开多个应用程序，每个程序并行不悖，同时运行。但在微观上：由于只有一个CPU，一次只能处理程序要求的一部分，如何处理公平，一种方法就是引入时间片，每个程序轮流执行

进程资源和进程状态

TASK_RUNNING：正在运行或处于就绪状态：就绪状态是指进程申请到了CPU以外的其它全部资源。正所谓：万事俱备，仅仅欠东风.提醒：一般的操作系统教科书将正在CPU上运行的进程定义为RUNNING状态、而将可运行可是尚未被调度运行的进程定义为READY状态。这两种状态在Linux下统一为 TASK_RUNNING状态。

TASK_INTERRUPTIBLE：处于等待队伍中，等待资源有效时唤醒（比方等待键盘输入、socket连接、信号等等），但能够被中断唤醒.普通情况下，进程列表中的绝大多数进程都处于TASK_INTERRUPTIBLE状态.毕竟皇帝仅仅有一个（单个CPU时），后宫佳丽几千；假设不是绝大多数进程都在睡眠，CPU又怎么响应得过来。

TASK_UNINTERRUPTIBLE：处于等待队伍中，等待资源有效时唤醒（比方等待键盘输入、socket连接、信号等等），但不能够被中断唤醒。

TASK_ZOMBIE:僵死状态。进程资源用户空间被释放，但内核中的进程PCB并没有释放。等待父进程回收。

TASK_STOPPED:进程被外部程序暂停（如收到SIGSTOP信号，进程会进入到TASK_STOPPED状态），当再次同意时继续运行（进程收到SIGCONT信号，进入TASK_RUNNING状态）。因此处于这一状态的进程能够被唤醒。

多进程的交替

==多进程交替： 队列操作+调度+切换==

启动磁盘的读写为例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

启动磁盘读写;
pCur.state = ‘W’;
将pCur放到DiskWaitQueue(磁盘等待队列);
schedule();

schedule()
{
	pNew = getNext(ReadyQueue);
	switch_to(pCur,pNew);
}

pCur是PCB的里面的信息，w表示阻塞态。先将当前进程的状态置为阻塞态，将该进程放进磁盘等待队列。然后启动调度函数（schedule)来切换到下一个进程，其中getnext就是从就绪队列中取下一个将要执行的进程，switch完成切换

进程切换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

//上下文切换
switch_to(pCur,pNew) 
{
	//保存正在进行的程序
	pCur.ax = CPU.ax;
	pCur.bx = CPU.bx;
	...
	pCur.cs = CPU.cs;
	pCur.retpc = CPU.pc;

	//将要运行的程序压入CPU中
	CPU.ax = pNew.ax;
	CPU.bx = pNew.bx;
	...
	CPU.cs = pNew.cs;
	CPU.retpc = pNew.pc; 
}

保存当前现场，恢复下个程序的现场然后执行下个程序。

4.多进程的影响

1.内存管理 由于内存中同时存在多个进程的，多个进程在交替，那么如图中进程1在访问地址100，而地址一百正是进程2开始的地方，进程2很可能还没有完成，就切到了进程1，如果在进程1中地址100处的内容被修改了，那么切回进程2时程序就出错了。 解决的办法：限制对地址100的读写

多进程的地址空间分离：内存管理的主要内容

==通过进程的地址映射实现进程间的地址空间分离==

进程1的映射表将访问限制在进程1范围内，进程1根本访问不到其他进程的内容。也就是[100]只是逻辑上的地址，其对应一篇内存上的物理地址，即使不同进程间都有逻辑地址100，但其对应的物理空间不同

2.多进程合作

打印任务1看到就绪队列空了后，就把自己放了进去，这时打印任务2也看了就绪队列空了，也想把自己放进去，此时任务1还没放完，进插入了任务2，那么7上同时由两个任务的内容，打出来不就是乱码 所以，在处理共享资源时，可以给共享的资源进行上锁。等待该资源被开锁，下一个进程才能使用

用户级线程与内核级线程

一、线程的定义

==线程是操作系统能够调度和执行的基本单位，在 Linux 中也被称之为轻量级进程(LWP：light weight process)==,在 Linux 系统中，一个进程至少需要一个线程作为它的指令执行体，进程管理着资源比如 cpu、内存、文件，将线程分配到某个 cpu 上执行

一个进程可以拥有多个线程，它还可以同时使用多个cpu 来执行各个线程，以达到最大程度的并行，提高工作的效率。

==线程的本质是一个进程内部的一个控制序列，它是进程里面的东西，一个进程可以拥有一个进程或者多个进程==

每一个进程都包含一个映射表，如果进程切换了，那么程序选择的映射表肯定也不一样；进程的切换其实是包含两个部分的，**第一个指令的切换，第二个映射表的切换。**指令的切换就是从这段程序跳到另外一段程序执行，映射表切换就是执行不同的进程，所选择的映射表不一样。线程的切换只有指令的切换，同处于一个进程里面，不存在映射表的切换。进程的切换就是在线程切换的基础上加上映射表的切换。

==进程 = 资源 + 指令执行序列==

所以，对应线程来说只是切换pc，内存和表不用切。

在每个大的进程里，有很多小的线程，并行的时候只需要改每个小的线程的PC指针，而不需要切换映射表。

所以，学习好线程是学习好进程的关键。

二、用户级线程

pthread_create函数用来创建一个线程，yield函数保证线程之间可以进行切换。

打开一个浏览器：

1
2
3
4

一个线程用来从服务器接收数据
一个线程用来处理图片(如解压缩)
一个线程用来显示文本
一个线程用来显示图片

这些线程要共享资源： 接收数据放在100处， 显示时要读… 所有的文本、 图片都显示在一个屏幕上

Yield进行线程间的调度：

下面程序就是用户级线程的应用，==通过用户主动进行切换，不用内核帮助。用户级线程是可以独立于操作系统的==

yield实现线程的切换

两个执行序列对应两个栈

一个方法执行完 esp(extended stack pointer)弹栈

jmp 204 后，执行完B()方法，esp指向的内存值还是204，又返回到了204，所以jmp 204要去掉

线程一先执行A,执行到B,跳转到B并将A的下一条指令的压栈，Yield切换到线程二的C，同时将下一条指令压栈。到了线程二在C里面又跳转到D并压栈，D里面又切换线程，压栈，同时将B压入的栈弹出，执行B。B执行完又弹栈，跳到A里面执行…（大概就是这样吧)

注：线程一和线程二压入的栈不是同一个

两个线程的样子： 两个TCB、 两个栈、 切换的PC在栈中

创建一个线程就要为该线程创建相应的栈，并将sp指向栈顶

Yield是用户程序

用户级线程只能在用户态进行切换，进入内核后还是同一个进程，Yiled程序是用户程序，而核心级线程会进入内核进行切换，ThreadCreat是系统调用，内核也知道TCB，Yield程序也不是用户编写，而是内核程序，用户不可见，至于调度点，也是有操作系统决定

三、核心级线程

并发——有处理多个任务的能力，但不一定得同时执行

并行——有能力处理多个任务，并且是同时执行的

MMU：Memory Management Unit 内存管理单元

多进程：因为切换时有地址映射的切换，需要消耗显著的资源

用户级线程，因为不进入到内核，所以操作系统无法为其分配cpu，即多个线程在一个cpu上切换

通过查阅资料，老师说的多进程不能发挥多核价值，或许有误

1.linux下并未对进程线程分别做抽象，都是利用task_struct来描述具体调度的一个单元

2.也就是说创建进程、线程的时候其实都是调用的clone

3.如果clone传参共享资源则为创建线程反之则为进程

4.所以“多进程在多核上的情况”，其关键就在于MMU是否共享

5.直接给出回答：MMU通常不是共享的。

6.具体参考i7存储系统框图，每个core都有一个MMU

7.也就是说如果有两个进程A B，每个进程下有两个线程A:T1T2 B:T3T4

8.两core单CPU情况下，可以是core1:T1 core2:T3

核心级线程与用户级线程区别：

1.==核心级线程需要在用户态和核心态里面跑，在用户态里跑需要一个用户栈，在核心态里面跑需要一个核心栈==。用户栈和核心栈合起来称为一套栈，这就是核心级线程与用户级线程一个很重要的区别，从一个栈变成了一套栈。

2.用户级线程用TCB切换栈的时候是在一个栈与另外一个栈之间切换，核心级线程就是在一套栈与另外一套栈之间的切换（核心级线程切换），核心级线程的TCB应该是在内核态里面。

内核级线程一套栈如图: 用户栈+内核栈

用户栈和内核栈之间的关联：

当线程进入内核的时候就应该建立一个属于这个线程的内核栈，通过INT中断进入内核。当线程下一次进入内核的时候，操作系统可以根据一些硬件寄存器来知道这个哪个线程，它对应的内核栈在哪里。**同时会将用户态的栈的位置（SS、SP）和程序执行到哪个地方了（CS、IP）都压入内核栈。**等线程在内核里面执行完（也就是IRET指令）之后就根据进入时存入的SS、SP的值找到用户态中对应栈的位置，根据存入的CS、IP的值找到程序执行到哪个地方。

内核级线程执行过程： 首先该线程调用B函数，将104压栈（用户栈），进入B函数之后调用read()这个系统调用，同时将204压栈（用户栈），进入read()系统调用通过int0x80这个中断号进入内核态，执行到sys_read()

sys_read()函数:

1
2
3
4
5
6

sys_read()
{	
	启动磁盘读;
	将自己变成阻塞;
	找到next;
	switch_to(cur, next);}

switch_to的作用就是切换线程 switch_to仍然是通过TCB找到内核栈指针；然后通过ret切到某个内核程序；最后再用CS:PC切到用户程序

形参cur表示当前线程的TCB，next表示下一个执行线程的TCB。 这个函数首先将目前esp寄存器的值存入cur.TCB.esp，将next.TCB.esp放入esp寄存器里面；其实就是从当前线程的内核栈切换到next线程的内核栈。

==内核级线程自己的代码还是在用户态的，只是进入内核态完成系统调用==，也就是逛一圈之后还是要回去执行的。因此切换到next线程就是要根据next线程的内核栈找到这个线程阻塞前执行到的位置，并接着执行。所以切换到next线程的内核栈之后应该通过一条包含IRET指令的语句进入到用户态执行这个线程的代码。这样就从cur线程切换到next线程。

内核级线程的切换是在内核里面进行切换的，切换完成后，再根据next内核栈里面的数据，返回到next用户栈

所以，要想从next的内核栈，经过弹栈，返回到next的用户栈，在我们调用ThreadCreate()创建线程的时候，我们就要将线程的内核栈和用户栈创建好并且将相应的数据压栈。

1、申请内存，作为TCB 2、申请内存，作为内核栈 3、内核栈和用户栈相关联 4、TCB关联内核栈

如图

内核线程switch_to的五段论（这里先了解一下）

流程大概是这样的，用户态线程切换，需要中断进入内核态，然后在内核态进行TCB切换

TCB切换之后，可以切换到另一个内核态线程，然后通过中断返回切换成用户态线程，从而实现用户态线程的切换

其实就是T线程用户栈到内核栈(这个切换要记录返回的东西)，再通过内核中的TCB队列，切换到S线程的内核栈， 由于S的内核保留了S的用户栈，所以可以切到S的用户栈继续执行

下一篇笔记将详细介绍这个五段论

对比：

总结

根据在用户空间还是在核心实现多线程机制，线程又被分为用户级线程（User Level Thread）和内核级线程（Kernel Level Thread）

内核级线程实现

前言

提示： 这里主要对内核线程switch_to的五段论程序进行分析。

五段论：

核心级线程的两套栈， 核心是内核栈

==核心级线程的切换过程：==

一、中断入口及出口

从INT 中断进入内核：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

在 main()中：

1.首先在A()函数中系统调用fork()，将B()的地址压入用户栈。

2.fork() 引起中断0x80，进入内核。

3.执行int 0x80时，还未进入内核，首先找到内核栈，压入当前栈地址（即用户栈）;
压入当前CS:IP（用户态）(ret = CS:IP)

4.进入内核，执行system_call。

1.中断入口

int对应的中断处理函数是 system_call，int执行时，是用户态，执行完，进入内核态，如图，0x80 对应sysstem_call

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

1.刚进入内核，首先在内核态中的各种寄存器压到栈中，即保护现场。

2.执行sys_fork(),继续向下执行，但在执行sys_fork的时候可能引起切换

3.接下来看当前PCB中的state是否等于0，如果不是那么就要进行调度，就是靠
schedule，完成五端论中的中间三步

state(%eax)相当于state + _current,与 0（就绪或运行态）作比较，非0即阻塞，
_current即PCB，阻塞则调度(reschedule)

4.再看看它的时间片是否等于0，时间片用光了也要进行调度
再次判断counter + _current 判断是否时间片用尽，若是则切换(reschedule

5.执行中断返回的函数ret_from_sys_call，iret也就是从内核栈到用户栈的切换

system_call.s

1
2
3
4
5
6

_system_call:
    push %ds..%fs
    pushl %edx...
    call _sys_call_table(,%eax,4)
    pushl %eax    //把系统调用号入栈。
//刚进入内核，_system_call将用户态信息压栈，通过 _sys_fork_table 调用 sys_fork

reschedule执行的是_schedule().

1
2
3
4

reschedule:
;将ret_from_sys_call 的地址入栈,，reschedule遇到 } 出栈，弹出ret_from_sys_call
pushl $ret_from_sys_call
jmp _schedule ;调用schedule

2.中断出口

中断入口: 建立 内核栈和用户栈 的关联 ，sys_fork与中间三段有关，然后先看中断出口

中断出口这里完成第二次切换，从内核栈切换到用户栈 还原现场，并恢复到用户态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 中断返回，执行中断返回函数，从内核栈，切换到用户栈
ret_from_sys_call:
...
popl %eax # 弹出信号值,出栈，与中断入口的push对应
popl %ebx
popl %ecx
popl %edx
pop %fs
pop %es
pop %ds
iret    # 将内核栈的内容出栈，切换到 下一个进程的TCB

二、切换

1.schedule

==schedule()是调度函数==

next是下一个进程的PCB，核心是switch_to

1
2
3
4
5
6
7

void schedule (void)
{
	next = i;
    //找到下一个线程的TCB next，切换到下一个线程
    ...
    switch_to (next);       // 切换到任务号为next 的任务，并运行之
}

2.Switch_to(内核栈切换)

linux 0.11 中基于==TSS(Task Struct Segement) 切换==，但也可以用栈切换，因为tss中的信息可以写到内核栈中

TSS是一个段，即一块内存，这里保存要切换的进程的cpu信息，包括各种寄存器的值、局部描述表ldt的段选择子等，切换时cpu会将这段内容存进各自对应的寄存器，然后就完成了切换。（任务切换或者说CPU状态更新实质上就是改变各个寄存器的值）

1
2
3
4
5
6
7
8

//32位TSS段结构
struct TSS32
{
    int backlink, esp0, ss0, esp1, ss1, esp2, ss2, cr3;
    int eip, eflags, eax, ecx, edx, ebx, esp, ebp, esi, edi;
    int es, cs, ss, ds, fs, gs;
    int ldtr, iomap;
}；

每一个进程都有自已的TSS和LDT，而TSS（任务描述符）和LDT（私有描述符）必须放在GDT中

使用的话首先要在GDT表中设置一个TSS段，就是保存TSS段的位置，然后将TSS段对应的是段选择子存入TR寄存器，告诉cpu这个TSS段在哪里。按照intel最初的设计，每个任务或者进程都应该设置一个TSS段，任务切换时直接将对应的TSS段的内存加载到CPU就行了。

但是后来发现这种设计会带来过多的系统开销，每次切换都要将所有的寄存器更新，需要数百个指令周期，因此主流的操作系统均不使用这种方法。linux采取的方法是绕开TSS段进行任务切换，每个CPU仅设置一个TSS段，仅使用esp0和iomap，采用软件方法切换寄存器，节省了开销。

switch_to 通过 TSS(任务结构段） 实现切换，ljmp 是长跳转指令，如图 黄色的是原TSS，绿的是新TSS，下边 GDT（全局描述符表Global Descriptor Table保存的是TSS的描述符

粉色的是 CPU当前的寄存器段信息，TR是一个选择子，可以根据TR找到当前进程的tss

==切换就是 将 CPU的寄存器信息 写入当前线程的TSS中，TR指向新的TSS(n) 的段描述符，再找到新的TSS，将新的TSS段内容 载入 CPU的寄存器ESP中==

swith_to内嵌宏定义

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

#define switch_to(n) {
struct {long a,b;} __tmp; 
__asm__( "cmpl %%ecx,_currentnt"     // 任务n 是当前任务吗?(current ==task[n]?)
  "je 1fnt"          // 是，则什么都不做，退出。
  "movw %%dx,%1nt"       // 将新任务的选择符*&__tmp.b。
  "xchgl %%ecx,_currentnt"   // current = task[n]；ecx = 被切换出的任务。
  "ljmp %0nt"        // 执行长跳转至*&__tmp，造成任务切换。
  // %0 是 "m"(*&__tmp.a),%1 是 "m"(*&__tmp.b)
// 在任务切换回来后才会继续执行下面的语句。
  "cmpl %%ecx,_last_task_used_mathnt"    // 新任务上次使用过协处理器吗？
  "jne 1fnt"         // 没有则跳转，退出。
  "cltsn"             // 新任务上次使用过协处理器，则清cr0 的TS 标志。
  "1:"::"m" (*&__tmp.a), "m" (*&__tmp.b),
  "d" (_TSS (n)), "c" ((long) task[n]));
}

3.sys_fork

创建一个进程（或内核级线程），就是要做成能切换的样子

system_call.s

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

# 根据父进程，创建子进程，copy_press前,将参数压栈,这些参数是父进程在用户态的样子
_sys_fork:
call _find_empty_process # 调用find_empty_process()(kernel/fork.c)。
testl %eax,%eax
js 1f
push %gs
pushl %esi
pushl %edi
pushl %ebp
pushl %eax

call _copy_process # 调用C 函数copy_process()(kernel/fork.c)。
addl $20,%esp # 丢弃这里所有压栈内容。
ret

_copy_process 调用 copy_process() 函数

copy_process 将父进程的栈都作为参数，C语言中参数越靠后越靠近栈顶

作用如图：

同时还要设置TTS，是使能够切换

父进程与子进程 内核栈不同，用户栈相同

copy_process ()函数

 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
44
45
46

/*
* Ok, this is the main fork-routine. It copies the system process
* information (task[nr]) and sets up the necessary registers. It
* also copies the data segment in it's entirety.
*/
/*
* OK，下面是主要的fork 子程序。它复制系统进程信息(task[n])并且设置必要的寄存器。
* 它还整个地复制数据段。
*/
// 复制进程。
int
copy_process (int nr, long ebp, long edi, long esi, long gs, long none,
          long ebx, long ecx, long edx,
          long fs, long es, long ds,
          long eip, long cs, long eflags, long esp, long ss)
{
  struct task_struct *p;
  int i;
  struct file *f;

  p = (struct task_struct *) get_free_page ();  // 获取一页空闲内存作为PCB，一页是4k
  ……
  p->state = TASK_UNINTERRUPTIBLE;  // 将新进程的状态先置为不可中断等待状态。
  p->pid = last_pid;        // 新进程号。由前面调用find_empty_process()得到。
  p->father = current->pid; // 设置父进程号。
  p->counter = p->priority;
  ……
  // 设置TSS
  p->tss.esp0 = PAGE_SIZE + (long) p;   // esp0 正好指向该页顶端，PAGE_SIZE=4k，p是刚申请的内存空间
  p->tss.ss0 = 0x10;        // 堆栈段选择符（内核数据段）[??]。
  p->tss.eip = eip;     // 指令代码指针。
  p->tss.eflags = eflags;   // 标志寄存器。
  p->tss.eax = 0;
  p->tss.ecx = ecx;
  p->tss.cs = cs & 0xffff;
  ……
  p->tss.ldt = _LDT (nr);   // 该新任务nr 的局部描述符表选择符（LDT 的描述符在GDT 中）。
  ……
// 在GDT 中设置新任务的TSS 和LDT 描述符项，数据从task 结构中取。
// 在任务切换时，任务寄存器tr 由CPU 自动加载。
  set_tss_desc (gdt + (nr << 1) + FIRST_TSS_ENTRY, &(p->tss));
  set_ldt_desc (gdt + (nr << 1) + FIRST_LDT_ENTRY, &(p->ldt));
  p->state = TASK_RUNNING;  /* do this last, just in case */
/* 最后再将新任务设置成可运行状态，以防万一 */
  return last_pid;      // 返回新进程号（与任务号是不同的）。
}

==小结：==

1.fork有中断，中断会调用 system_call

2.system_call的作用：

(1) 调用sys_fork，调用 copy_process，父进程与子进程内核栈不同，用户栈相同

(2) 判断cmpl $0,state(%eax)，非0表示阻塞，调用 reschedule 进程调度 reschedule 调用 schedule，schedule调用 switch_to（switch_to中ljmp实现长跳转，子进程将 TSS的内容复制到 CPU上，TSS图中粉色的部分）

(3) iret 内核栈出栈 a.子进程回到用户栈，执行的是 中断下边的一句代码：mov res, %eax ，res = %eax = 0

b.父进程回到用户栈，执行的也是 中断下边的一句代码：mov res, %eax， 父进程 eax != 0

程序在用户态执行，切换时找到自己的内核栈， 找到TCB，通过switch_to 完成TCB的切换，完成内核栈的切换，再完成用户栈的切换

4.fork()典例

基本使用格式：

1
2
3
4
5
6
7
8

if(!fork()) 
{
    //子进程执行
} 
else
{
    //父进程执行
}

shell终端的命令的执行

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

int main(int argc, char * argv[])
{
    while(1)
    {
        scanf("%s", cmd);
        if(!fork())
        {
            exec(smd); // 执行子进程命令
        }
        wait(0); // 执行父进程命令，shell等待用户输入
    }

}

==exec 是一个系统调用，会执行 system_call==

子进程将进入if块内，调用exec，子进程将被更换新的代码，如下图

ThreadCreate(*A)创建一个进程：

子进程A执行： do_execve，将程序入口地址给eip，更改代码段；eip[3]正好等于SP，更改栈。

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

_system_call:
    push %ds ... %fs
    pushl %edx...
    call sys_execve
# sys_execve执行前，执行的是 父进程的代码

_sys_execve:
    lea EIP(%esp),%eax  # EIP = 0x1C是十进制的28，将%esp偏移28，eip的地址复制给eax
    pushl %eax
    call _do_execve
# 子进程通过 _sys_execve 退出内核（通过IRET实现中断返回），回到用户态，执行新的子进程的代码

int do_execve(* eip, ...)
{
    p += change_ldt(...;
    eip[0] = ex.a_entry;// ex.a_entry是可执行程序入口地址，产生可执行文件时 写入
    eip[3] = p;
    // eip[0]=esp + 0x1C; 28的位置存的子进程的入口
    // eip[3]=esp+0x1C+0x0C
    ...
}

总结

1.理解switch_to对应的栈切换， 将自己变成计算机 2.ThreadCreate的目的就是初始化这样一套栈 如图

切换过程：

程序在用户态执行，切换时找到自己的内核栈， 找到TCB，通过switch_to 完成TCB的切换，完成内核栈的切换，再完成用户栈的切换

CPU调度策略

前言

问题引入：

当线程1阻塞，线程2 3都处于就绪态，该执行哪个呢？需要有调度策略

CPU调度的直观想法：

1.FIFO:先进先出 (排队) 2.Priority:优先级高的先执行

面对复杂的场景，这两种几乎行不通的。

CPU调度：即按一定的调度算法从就绪队列中选择一个进程，把CPU的使用权交给被选中的进程，如果没有就绪进程，系统会安排一个系统空闲进程或idle进程

CPU调度时机：发生在内核对中断/异常/系统调用处理后返回到用户态时

1
2
3
4

进程正常终止 或 由于某种错误而终止；
新进程创建 或 一个等待进程变成就绪；
当一个进程从运行态进入阻塞态；
当一个进程从运行态变为就绪态。

CPU调度算法衡量指标：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

吞吐量 （Throughput）： 每单位时间完成的进程数目；

周转时间TT (Turnaround Time)：每个进程从提出请求到运行完成的时间；

响应时间RT(Response Time)：从提出请求到第一次回应的时间；

CPU利用率(CPU Utilization)：CPU做有效工作的时间比例；

等待时间(Waiting time)：每个进程在就绪队列(ready queue)中等待的时间；

……

一、调度算法

设计调度算法的目的：

1
2
3
4
5
6
7
8
9

1.面对用户，目的是让用户满意
2.面对进程：CPU调度的目标是进程满意

进程满意:
尽快结束任务：周转时间（从任务进入到任务结束）短
响应用户操作快：响应时间（从操作发生到响应）短
系统内耗时间少：吞吐量（完成的任务量）

总原则：系统专注于任务执行，又能合理调配任务

1.FCFS（First Come, First Served）

先来先服务算法（FCFS——First Come First Serve）：

==按照进程就绪的先后顺序使用CPU。==

特点：非抢占，公平，实现简单，长进程后面的短进程需要等很长时间，不利于用户体验

三个进程的处理时间分别为12，3，3，分两种进程到达顺序讨论 优点：调度算法简单

缺点： 1.平均等待时间波动较大，短的进程可能排在长的进程后面得到执行

2.I/O资源和CPU资源利用率较低，CPU密集型进程会导致I/O设备闲置，I/O密集型进程会导致CPU闲置

2.SJF（Shortest Job First）

最短作业优先（SJF——Shortest Job First）：

具有==最短完成时间==的进程优先执行，非抢占

如果调度结果是 P1，P2，…，Pn，则平均周转时间为： P1 + P2 + P3 + … + Pn = ∑(n + 1 - i) * Pi P1的周转时间是 P1 P2的周转时间是 P1 + P2 …… Pn的周转时间中含有 n*P1 + (n - 1) * P2 + … P1 计算的次数最多，需要把最短的任务放在前边

所以，这种方式平均周转时间最小。

3.RR（Round Robin）

==时间片轮转调度算法（Round Robin——RR）：==

每个进程被分配一个时间片，允许该进程在该时间段运行，如果在时间片结束时该进程还在运行，则剥夺CPU并分配给另一个进程，如果该进程在时间片结RR束前阻塞或结束，则CPU立即进行切换。

特点：公平；有利于交互式计算，响应时间快；由于进程切换，时间片轮转算法要花费较高的开销；对进程表中不同进程的大小差异较大的有利，而对进程都是相同大小的不利。

时间片设计需要避免的两点：

1.时间片太大，等待的时间过长，极限的情况下退化成为FCFS算法

2.时间片太小，反应过于迅速，产生大量的上下文切换，会影响到系统的吞吐量

4.折中方案

我们可以==设置优先级，设置前台任务和后台任务，前台任务优先级高，后台任务优先级低==，定义前台任务队列和后台任务队列，只有前台任务没有了才调度后台任务

但是，如果一直有前台任务，后台任务一直得不到执行（优先级低的任务一直得不到执行）

所以，==任务的优先级要动态调整== 一般后台任务 耗时比较长，一旦后台任务转到前台执行，可能耗时很长，一直不释放CPU，前台任务的响应时间又没法保证，前后台任务都要设置时间片，后台任务转到前台，执行一段，要释放CPU，让其他任务执行

==折中方案：短任务优先（减少周转时间）、以 轮转调度为核心，要设置优先级==

二、Schedule()

schedule() 的目的是找到下一个任务 next，切换到下一个任务

源码：

 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

// 任务0是一个闲置(idle)任务，只有当其他任务没有运行时才调用它
// 它不能被杀死，也不能睡眠。任务0中的状态信息“state”是从来不用的

void schedule(void)
{
	int i,next,c;
	struct task_struct ** p; // 任务结构体的指针的指针

/* check alarm, wake up any interruptible tasks that have got a signal */
// 检查 alarm(进程的报警定时值)，唤醒任何已得到信号的可中断任务

	把p初始化为指向最后一个进程的地址的指针,逆向扫描所有进程,并跳过空指针
	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p) { //*p 指向当前进程的指针
		//jiffies是系统从开机算起的滴答数(每10ms/滴答)
			//判断定时器是否到期，如果到期需要在信号位图中置SIGALARM位，并且将定时器清0
			if ((*p)->alarm && (*p)->alarm < jiffies) { 
					(*p)->signal |= (1<<(SIGALRM-1));
					(*p)->alarm = 0;
				}
			//如果信号位图中表示有非阻塞信号被递送，该任务的状态是可中断的，那么将该任务状态置为就绪
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
			(*p)->state==TASK_INTERRUPTIBLE)
				(*p)->state=TASK_RUNNING;   // 置为就绪可以执行状态
		}

/* this is the scheduler proper: */

// 进程的调度
	// 检查就绪的任务，判断下一个运行的任务。
	while (1) {
		c = -1;                 //从最后一个任务开始遍历任务数组
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];

		//对就绪任务按照时间片进行排序 
		//比较每个就绪状态任务的counter值(任务运行时间的递减滴答计数)
		//哪一个值大，运行的时间还不长，next就指向哪一个任务号
		while (--i) {
			if (!*--p)
				continue;
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c) //counter这里是时间片
			//判断是就绪态，并且 counter>-1，就给c和next赋值，遍历找到最大的counter
				c = (*p)->counter, next = i;
		}

		
		//如果比较得出有counter值不等于0的结果，或者系统中没有一个可运行的任务存在
		//则跳出循环，执行任务切换操作
		if (c) break;

		//如果所有任务的时间片都为0，那么重新计算各个任务的时间片，计算原则是根据优先级进行计算
      	//更新每个任务的counter值，然后再回到开始处比较
		//计算方法：counter = counter/2 + priority
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
				(*p)->counter = ((*p)->counter >> 1) + //counter这里代表优先级
						(*p)->priority;
	}
	//把当前任务指针current指向任务号为next的任务，并切换到该任务中运行
	//若系统中没有其他可运行的任务，则next=0,所以调度去指向空闲任务
	switch_to(next);    // 任务切换,切换到任务号为next的任务，并允许
}

1.counter（时间片）

counter是典型的时间片， 所以是轮转调度， 保证了响应 do_timer 中 counter 减到0，就schedule

2.counter（优先级）

counter代表的优先级可以动态调整

==阻塞的进程再就绪以后优先级高于非阻塞进程==

首先是找到所有就绪态任务的最大counter，大于零则切过去，否则更新所有任务的counter，即右移一位再加priority，然后进入下一次的找最大counter，大于零则切否则更新counter，所以说那些没在就绪态的counter就一直在更新，数学证明出等的时间越长counter越大等他们变成就绪态了，由于counter大，也就可以优先切过去了

总结

==调度函数的核心处理部分==：这是根据进程的==时间片==和==优先权调度机制==，来选择随后要执行的任务。

它首先循环检查任务数组中的所有任务，根据每个就绪态任务剩余执行时间的值counter，选取该值最大的一个任务，并利用switch_to(next)函数切换到该任务。

若所有就绪态任务的该值都等于零，表示此刻所有任务的时间片都已经运行完，于是就根据任务的优先权值pitority，重置每个任务的运行时间片值counter，再重新执行循环检查所有任务的执行时间片值。

进程同步与信号量

前言

一般情况下，系统中运行着大量的进程，而每个进程之间并不是相互独立的，有些进程之间经常需要互相传递消息，所以就引出了信号，但是信号不能完全满足需求，又引入了信号量

一、信号

信号的大致内容可以参考这篇文章 Linux信号基本知识

为了完成进程间的同步或者通信从而引出了信号，但是单靠信号是不能解决问题的，如生产者与消费者典例

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

注：这里counter 就是一个信号
//生产者
while(true){
    //当 counter == BUFFER_SIZE，生产者 sleep()，不再生产
    if(counter == BUFFER_SIZE)
        sleep();
    ...
    counter++;
    //当生产者发现 counter == 1，又有产品资源了，唤醒消费者
    if(counter == 1)
        wakeup(消费者);
}

//消费者
while(true){
    //当消费者发现 counter == 0，进入sleep，不再消费
    if(counter == 0)
        sleep();
    ...
    counter--;
    //当消费者发现 counter == BUFFER_SIZE - 1，就可以生产了，唤醒生产者
    if(counter == BUFFER_SIZE - 1)
        wakeup(生产者);
}

假设程序执行过程如下：

(1) 缓冲区满以后生产者P1生产一个item放入， 会sleep信号

(2) 又一个生产者P2生产一个item放入， 会sleep

(3) 消费者C执行1次循环， counter==BUFFER_SIZE-1，发信号给P1，P1 wakeup

(4) 消费者C再执行1次循环， counter==BUFFER_SIZE-2， P2不能被唤醒

这就导致进程2不能被执行，所以，单纯依靠counter判断缓冲区的个数是不够的，还要知道有多少进程睡眠了

二、信号量

背景介绍：

原子操作（atomic operation） 原子操作意为不可被中断的一个或一系列操作，也可以理解为就是一件事情要么做了，要么没做。而原子操作的实现，一般是依靠硬件来实现的

同步与互斥 同步：在访问资源的时候，以某种特定顺序的方式去访问资源 互斥：一个资源每次只能被一个进程所访问

临界资源 不同进程能够看到的一份公共的资源（如：打印机，磁带机等），且一次仅允许一个进程使用的资源称为临界资源。

临界区 临界区是一段代码，在这段代码中进程将访问临界资源，当有进程进入临界区时，其他进程必须等待，有一些同步的机制必须在临界区段的进入点和离开点实现，确保这些共用资源被互斥所获得。

1.引入信号量

单独依靠信号，会导致无法唤醒P2进程。生产者消费者之间的多种映射对应，多个生产者，多个消费者。由这个原因引出信号量。

==信号量（Semaphore）可以被看做是一种具有原子操作的计数器==，它控制多个进程对共享资源的访问，通常描述临界资源当中，临界资源的数目，常常被当做锁（lock）来使用，防止一个进程访问另外一个进程正在使用的资源。

==信号量的工作原理==

若此信号量的值为正，则进程可以使用该资源。进程将信号量值减1,表示一个资源被使用。

若此信号量的值为0，则进程进入休眠状态，直至信号量值大于0，进程被唤醒

若次信号量的值为负，则进程无法使用资源，进程被阻塞

为了正确地实现信号量，信号量的操作应是原子操作，所以信号量通常是在内核中实现的。

在以上面的问题为例，引入信号量后

1.缓冲区满，P1执行，P1 sleep，sem = -1，表示一个进程睡眠了

2.P2执行，发现缓冲区满，P2 sleep，sem = -2，表示2个进程睡眠了

3.消费者C执行，wakeup P1，sem = -1

4.消费者C再执行一次，wakeup P2，sem = 0

5.消费者C再执行一次，sem = 1，消费者进程睡眠

6.P3执行，sem = 0，表示没有资源了

这样就完美的解决这个问题

这种机制的主要思想就是——通过将资源数量化，将申请资源和释放资源的动作具体化，从而达到对资源的操作及结果可视化的程度

1
2
3
4
5
6

P(semaphore s){
    s.value--;
    if(s.value < 0){
        sleep(s.queue);
    }
}

1
2
3
4
5
6

v(semaphore s){
    s.value++;
    if(s.value <= 0){
        wakeup(s.queue);
    }
}

2.临界区

通过对信号量的访问和修改，让进程有序推进，但是让程序正确有序的进行的前提是保证信号量的值必须是正确的

信号量操作可能出现的问题

 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

注：这里empty是信号量
//生产者
Producer(item)
{
    P(empty);//生产者先判断 缓存区个数 empty是否满了，empty == 0，阻塞
    ...
}

//生产者P1
register = empty;
register = register - 1;
empty = register;

//生产者P2
register = empty;
register = register - 1;
empty = register;

//初始情况
empty = -1; //空闲缓冲区的个数，-1表示有一个进程在睡眠

//一个可能的执行（调度）
P1.register = empty; // P1.register = -1
P1.register = P1.register - 1; // P1.register = -2

P2.register = empty; // P2.register = -1;
P2.register = P2.register - 1; // P2.register = -2

empty = P1.register; // empty = -2
empty = P2.register; // empty = -2

如果进程真像上面的调度就会导致信号量的值出错。

可能某一次调度会正确执行（进程时间片不知道）如下图

所以，必须对信号量进行保护操作。临界区就是用来保护信号量的

==临界区：==

每个进程中访问临界资源的那段代码称为临界区（criticalsection），每次只允许一个进程进入临界区，进入后，不允许其他进程进入。不论是硬件临界资源还是软件临界资源，多个进程必须互斥的对它进行访问。

多个进程涉及到同一个临界资源的的临界区称为相关临界区。使用临界区时，一般不允许其运行时间过长，只要运行在临界区的线程还没有离开，其他所有进入此临界区的线程都会被挂起而进入等待状态，并在一定程度上影响程序的运行性能。

临界区代码的保护原则

1.互斥进入：如果一个进程在临界区中执行，其他进程不允许进入。进程间是互斥关系

2.有空让进：若干进程要求进入空闲临界区时，要尽快使一个进程进入临界区

3.有限等待：从进程发出进入请求到允许进入，不能无限等待

所以，找出进程中的临界区代码（读写信号量的代码）不就可以对信号量保护了吗？

临界区算法

1)软件方式：

1.轮换法 2.标记法 3.非对称标记法 4.Peterson算法(结合标记和轮转思想) 5.面包店算法

2)硬件方式

1.中断控制 一个进程在操作临界区，==另一个进程请求进入临界区，一定发生了调度，只要阻止这种调度不进行就可以，只要关闭中断，系统就不会响应==

1
2
3
4
5

//进程Pi
cli(); //关中断
临界区
sti();//开中断
剩余区

这种方式只适合单核CPU，像UCOS，FreeRTOS这种小型系统都采用的这种。这种方式不适合多核系统。

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

单核CPU：
中断是在CPU上有一个中断寄存器 INTR，发生中断，寄存器某的某一位置1，CPU每执
行完一个指令，看INTR是否是1，如果是1，就进入中断处理程序，一旦设置了 
cli()，指令执行完，就不判断 INTR 了

多核CPU(不适用)：
多CPU时，执行中断，每个CPU对应的 INTR 都置1

假设临界区在 CPU1 上，P1在执行，设置了 cli()， CPU1 上再有中断，就不调度了，CPU1 上的临界区可以一直执行

设 CPU2 在执行P2，设置了 cli()，也不判断中断，P2 也执行
此时 P1 P2 就都在执行临界区了

2.硬件原子指令法 在执行临界区之前上锁，然后执行临界区，执行完开锁，其实这个锁就是一个变量，上锁或者开锁就是给变量赋值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// TestAndSet是操作锁的，不能被打断
boolean TestAndSet(boolean &x)
{
    //该函数代码 一次执行完毕
    boolean rv = x;
    x = true;
    return rv;
}

//进程Pi
// lock = true 表示上锁，TestAndSet返回true，如果锁上了，Pi就空转
while(TestAndSet(&lock));

临界区; // 没上锁，进入临界区执行

lock = false; // 执行完临界区，解锁
剩余区

3.信号量的代码实现

schedule()是主动的程序调度，不使用中断，而检查程序时间片是否用完了进行的调度涉及时钟中断，所以这里的关中断是防止发生不受控制的时钟中断，从而引起程序调度

4.信号量的操作

有关信号量的操作及相关API可以参考一下链接 systerm-V

5.信号量的类型

信号量有三种类型：

① ==Posⅸ有名信号量==：可用于进程或线程间的同步。

② ==Posix基于内存的信号量(无名信号量)==：存放在内存区中，可用于进程或线程间的同步。常用于多线程间同步。

③ ==System V信号量（IPC机制）==：在内核中维护，可用于进程或线程间的同步。 常用于进程间同步。

1
2
3
4
5

有名信号量通过文件系统中的路径名对应的文件名进行维护（信号量只是通过文件名进行标识，信号量的值并不存放到这个文件中，除非信号量存放在空间映射到这个文件上）。

无名信号量通过用户空间内存进行维护，无名信号量要想在进程间通信，该内存必须为共享内存区。

System V信号量由内核进行维护。

信号量的分类：

① ==二值信号量(binary semaphore)==：其值或为0或为1的信号量。这与互斥锁类似,若资源被锁住则信号量值为0，若资源可用则信号量值为1。

② ==计数信号量(counting semaphore)==：其值在0和某个限制值(对于Posiⅸ信号量，该值必须至少为32767)之间的信号量。信号量的值就是可用资源数。

Posix信号量为单个计数信号量，System V信号量为计数信号量集，偏集合的概念。

由于信号量只能进行两种操作等待和发送信号，即P(sv)和V(sv),他们的行为是这样的：

P(sv)：如果sv的值大于零，就给它减1；如果它的值为零，就挂起该进程的执行

V(sv)：如果有其他进程因等待sv而被挂起，就让它恢复运行，如果没有进程因等待sv而挂起，就给它加1。

除可以像互斥锁那样使用外，信号量还有一个互斥锁没有提供的特性：互斥锁必须总是由锁住它的线程解锁，信号量的挂出却不必由执行过它的等待操作的同一线程执行。

总结

用临界区保护信号量，用信号量保证同步

进程死锁以及处理

一、死锁的定义

1.死锁的引出

==死锁 (deallocks)==： 是指两个或两个以上的进程（线程）在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程（线程）称为死锁进程（线程）

生产者 –消费者问题

 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

//用文件定义 共享缓冲区
int fd = open("buffer.txt");
write(fd, 0, sizeof(int));//写in
write(fd, 0, sizeof(int));//写out

//信号量的定义和初始化
semaphore full = 0;//生产的产品的个数
semaphore empty = BUFFER_SIZE;//空闲缓冲区的个数
semaphore mutex = 1;//互斥信号量

//生产者
Producer(item)
{
    P(empty);//生产者先判断 缓存区个数 empty是否满了，empty == 0，阻塞
    P(mutex);//操作文件前，用mutex防止其他进程操作该文件
    读入in，将item写到in的位置上
    V(mutex);//使用完文件，释放文件资源
    V(full);//生产者生产产品，增加full，消费者就可以消费了
}

//消费者
Consumer()
{
    P(full);//当full == 0,缓冲区空了，阻塞
    P(mutex);
    读入out，从文件中的out位置读出到item，打印item;
    V(mutex);
    V(empty);//消费者消耗产品，增加缓冲区个数，增加empty，生产者就可以继续生产了
}

这时不管是生产者还是消费者都是先调用P(empty)/P(full),然后再调用互斥信号量mutex，进程能正确的执行

但是如果我们将这两个先后顺序调换一下：

在这里假设 mutex初值是1，empty初值是0，缓冲区取满了

在生产者中，P(mutex) 会把 mutex 变成 0，// P(empty) 会把 empty 变成 -1，生产者阻塞，然后消费者启动，P(mutex)，mutex是0，执行P(mutex)将mutex变成 -1，消费者阻塞，此时消费者和生产者都阻塞了

生产者要执行，需要把empty释放了，即消费者要执行 V(empty)，当前消费者卡在 P(mutex)，释放不了

消费者要执行，需要生产者把 mutex释放了，生产者要执行 V(metux)，生产者卡在上边的 P(empty)，也释放不了

生产者在P(empty)往下执行，依赖于消费者，消费者要往下执行，又依赖生产者P(empty)下边的指令，形成环路等待，死锁。

2.死锁产生原因

原因：

(1)系统资源的竞争 系统资源的竞争导致系统资源不足，以及资源分配不当，导致死锁。

(2)进程运行推进顺序不合适 进程在运行过程中，请求和释放资源的顺序不当，会导致死锁。

死锁的四个必要条件

==1.互斥条件：==

一个资源每次只能被一个进程使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。

==2.请求和保持条件：==

一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源。

==3.不可抢占条件：==

别人已经占有了某项资源，不能因为自己也需要该资源，就去把别人的资源抢过来。

==4.循环等待条件：==

若干进程间形成 首尾相接 循环等待资源的关系

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

二、死锁策略

死锁处理方法概述

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

1.死锁预防
破坏死锁出现的条件，不要 占有资源 又申请其他资源

2.死锁避免
检测每个资源请求，如果造成死锁就拒绝

3.死锁检测 + 恢复
检测到死锁出现时，让一些进程回滚，让出资源

4.死锁忽略
好像没有出现死锁一样

1.死锁预防

方法1： 在进程执行前，一次性申请所有需要的资源，不会占有资源再去申请其他资源

优点：简单易实施且安全。 缺点：因为某项资源不满足，进程无法启动，而其他已经满足了的资源也不会得到利用，严重降低了资源的利用率，造成资源浪费。使进程经常发生饥饿现象

**方法2：**对资源类型进行排序，资源申请必须按序进行，不会出现环路等待

缺点：仍会造成资源浪费

2.死锁避免

在使用前进行判断，只允许不会产生死锁的进程申请资源。死锁的避免是利用额外的检验信息，在分配资源时判断是否会出现死锁，只在不会出现死锁的情况下才分配资源。

两种避免办法：

1、如果一个进程的请求会导致死锁，则不启动该进程 2、如果一个进程的增加资源请求会导致死锁 ，则拒绝该申请。

问题： 上图含有5个进程：P0-P4 Allocation:占有的资源,以P1 为例，占用资源A3个，资源B0个，资源C2个 Need：需要的资源 Available：系统中剩余的资源

分析： 当前系统剩余资源：ABC = 230，给 P1，P1可以执行完，P1 执行完 Available ABC = 532，P3 可以执行，P3 执行完，Available ABC = 743 其他进程都可以执行…A 是安全序列

3.银行家算法

银行家算法通过对进程需求、占有和系统拥有资源的实时统计，确保系统在分配给进程资源不会造成死锁才会给与分配

 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

int Available[1..m]; //每种资源剩余数量
int Allocation[1..n, 1..m];  //已分配资源数量
int Need[1..n, 1..m];  //进程还需的各种资源数量
int Max[1..n, 1..m];//进程总共需要的资源数量
int Work[1..m];  //工作向量
bool Finifh[1..n];  //进程是否结束

Work = Available;
Finifh[1..n] = false;
while(true)
{
    for(i = 1; i <= n; i++)
    {
        // Need[i] <= Work 这个任务是可以完成的
        if(Finish[i] == false && Need[i] <= Work)
        {
            Work = Work + Allocation[i];  // Work 累加系统曾分配给 i 的资源
            Finish[i] = true;
            break;
        } else {
            goto end;
        }
    }
}

End: for(i = 1; i <=n; i++)
        if(Finish[i] == false)
            return "deadlock";

相关数据结构：

可利用资源向量Available：用于表示系统里边各种资源剩余的数目。由于系统里边拥有的资源通常都是有很多种（假设有m种），所以，我们用一个有m个元素的数组来表示各种资源。数组元素的初始值为系统里边所配置的该类全部可用资源的数目，其数值随着该类资源的分配与回收动态地改变。

分配矩阵Allocation：顾名思义，就是用于表示已经分配给各个进程的各种资源的数目。也是一个nxm的矩阵。

需求矩阵Need：用于表示进程仍然需要的资源数目，用一个nxm的矩阵表示。系统可能没法一下就满足了某个进程的最大需求（通常进程对资源的最大需求也是只它在整个运行周期中需要的资源数目，并不是每一个时刻都需要这么多），于是，为了进程的执行能够向前推进，通常，系统会先分配个进程一部分资源保证进程能够执行起来。那么，进程的最大需求减去已经分配给进程的数目，就得到了进程仍然需要的资源数目了。

所以,根据该算法可以解决上面的问题

其时间复杂度是 T(n) = O(m* n^2)，m是资源数，n是进程数

死锁避免的优点：

不需要死锁预防中的抢占和重新运行进程，并且比死锁预防的限制要少

死锁避免的缺点：

必须事先声明每个进程请求的最大资源量 考虑的进程必须无关的，也就是说，它们执行的顺序必须没有任何同步要求的限制
分配的资源数目必须是固定的 在占有资源时，进程不能退出

4.死锁检测与恢复

定时检测或者是发现资源利用率低时检测

检测算法：

1
2
3
4
5
6

Finish[1..n] = false;
if(Allocation[i] == 0) Finish[i]=true;
...//和Banker算法完全一样
for(i=1;i<=n;i++)
if(Finish[i]==false)
deadlock = deadlock + {i};

检测处问题，进程解锁:

1.抢占资源：从一个或多个进程中抢占足够数量的资源分配给死锁进程，以解除死锁状态。 2.终止（或撤销）进程：终止或撤销系统中的一个或多个死锁进程，直至打破死锁状态。

5.死锁忽略

死锁出现不是确定的， 可以用重启动来处理死锁， Windows和Linux都采用了死锁忽略的方法：

• 死锁忽略的处理代价最小
• 这种机器上出现死锁的概率比其他机器低
• 死锁可以用重启来解决，PC重启造成的影响小