程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集和
进程：是动态的，是程序的一次执行过程，是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
PCB是进程存在的唯一标志。
一个进程实体（进程映象）由PCB、程序段、数据段组成。进程是动态的，进程实体是静态的。
进程的特征：动态性、并发性、独立性、异步性、结构性

进程的状态与转换

创建态：操作系统为进程分配资源、初始化PCB
就绪态：已经具备运行条件，但由于没有空闲CPU，就暂时不能运行
运行态：在CPU上运行
阻塞态：请求等待某个事件的发生，在这个事件发生之前，进程无法继续往下执行
终止态：执行exit系统调用，请求操作系统终止该进程，并回收内存空间等资源，最后回收PCB
==进程不可能由阻塞态直接转换为运行态，也不能有就绪态直接转换为阻塞态==
使用链接队列或者索引方式进行组织。

进程控制

进程控制：对系统中的所有进程是是有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。（原语实现）

“关中断”：不在例行检查中断信号
“开中断”：恢复检查中断信号

进程的创建

申请空白PCB
为新进程分配所需资源
初始化PCB
将PCB插入就绪队列
实例：用户登录、作业调度、提供服务、应用请求

进程终止

从PCB集合中找到终止进程的PCB
若进程正在执行，立即剥夺CPU，将CPU分配给其他进程
终止其所有子进程（进程之间的关系是树形结构）
将该进程拥有的所有资源归还给父进程或操作系统
删除PCB
引起事件：正常结束、异常结束、外界干预

阻塞原语

运行态->阻塞态

找到要阻塞的进程对应的PCB
保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
将PCB插入响应时间的等待队列
引起事件：需要等待系统分配某种资源、需要等待相互合作的其他进程完成工作

唤醒原语

阻塞态->就绪态

在事件等待队列中找到PCB
将PCB从等待队列移除，设置进程为就绪态
将PCB插入就绪队列，等待被调度
引起事件：等待的事件发生

切换原语

运行态->就绪态，就绪态->运行态

将运行环境信息存入PCB
PCB移入相应队列
选择另一个进程执行，并更新其PCB
根据PCB恢复新进程所需的运行环境
引起事件：当前进程时间片到、有更高优先级的进程到达、当前进程主动阻塞、当前进程终止
PSW：程序状态字寄存器
PC：程序计数器，存放下一条指令的地址
IR：指令寄存器，存放当前正在执行的指令
通用寄存器：其他一些必要信息

进程通信

进程间的通信：两个进程之间产生数据交互。

共享存储

通过“增加页表项/段表项”即可将同一片共享内存区映射到各个进程的地址空间中。
为避免出错，各个进程对共享空间的访问应该是互斥的。各个进程可使用操作系统内核提供的同步互斥工具。

基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式
基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式。

消息传递

进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

直接通信：消息发送进程要指明接收进程的ID
间接通信（信箱通信方式）：通过“信箱”间接地通信。

管道通信

“管道”：是一个特殊的共享文件，又名pipe文件。其实就是在内存中开辟了一个大小固定的内存缓冲区。（先进先出，循环队列）
管道只能支持半双工通信，某一时间段内只能是西安单向的传输。如果要实现双向同时通信，则需要设置两个管道。
各进程要互斥地访问管道（由操作系统实现）
当管道写满时，写进程将堵塞，直到读进程将管道中的数据取走，即可唤醒写进程。
当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
管道中的数据一旦被读出，就彻底消失。因此多个进程读一个管道时，可能会错乱：

==一个管道允许多个写进程，一个读进程==
允许有多个写进程，多个读进程，但系统会让多个读进程轮流从管道中读数据

线程

线程是一个基本的CPU执行单元，也是程序执行流的最小单位，是操作系统中最小的调度单位。

线程是处理及调度的单位
多CPU计算机中，各个线程客栈用不同的CPU
每个线程都有一个线程ID、线程控制块
线程也有就绪、阻塞、运行三种基本状态
线程几乎不拥有系统资源
同一进程的不同线程之间共享进程的资源
由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
同一进程中的线程切换，不会引起进程切换
切换同进程内的线程，系统开销小；切换进程，系统开销大

实现方式

用户级线程：线程的管理工作由线程库完成，线程切换不需要CPU变态，操作系统意识不到用户级线程的存在。（”代码逻辑“的载体）
优点：不需要切换到核心态，线程管理的系统开销小，效率高。
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
内核级线程：线程的管理工作由操作系统完成，线程切换需要CPU变态。（运行机会的载体）
优点：并发能力强，多线程可在多核处理及上并行执行。
缺点：需要切换内核态，线程管理成本高，开销大。
多线程：

一对一模型：一个用户及线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
- 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行
- 缺点：需要切换内核态，线程管理成本高，开销大。
多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。
- 不需要切换核心态，系统开销小，效率高
- 并发度不高，多个线程不可在多核处理机上并行运行
多对多模型：n用户及线程线程映射到m个内核级线程（n>=m）。每个用户进程对应m各内核级线程。（克服了一对一模型和多对一模型的缺点）

调度

高级调度(作业调度)：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。(无->创建态->就绪态)
低级调度（进程调度/处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。（进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次，就绪态->运行态）
中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。（挂起态->就绪态）

不能进行进程调度与切换的情况：

在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
进程在操作系统内核程序临界区（一般是用来访问某种内核数据结构）中
在原子操作过程中。原子操作不可中断，要一气呵成。
进程调度的方式：
非剥夺调度方式：实现简单，系统开销小，无法及时处理紧急任务
剥夺调度方式：适合于分时操作系统、实时操作系统
“狭义的进程调度”与“进程切换”的区别：
==狭义的进程调度==是指从就绪队列中选中一个要运行的进程
进程切换是指一个进程让出处理机，有另一个进程占用处理机的过程
- 对原来运行进程各种数据的保存
- 对新的进程各种数据的恢复

什么事件会触发“调度程序”

创建新进程
进程退出
运行进程阻塞
I/O中断发生
非抢占式调度策略只有运行进程阻塞或退出才出发调度程序工作
抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作
闲逛进程（调度程序永远的备胎）：
优先级最低
可以是0地址指令，占一个完整的指令周期
能耗低

调度算法的评价指标

CPU利用率

指cpu“忙碌”的事件占总时间的比例（ $利用率忙碌的时间总时间$ ）

系统吞吐量

单位时间内完成作业的数量（ $系统吞吐量总共完成的作业数总共花的时间$ ）

周转时间

指从作业被提交给系统开始，到作业完成为止的这段时间间隔
包括四个部分：作业在外存后备队列上等待作业调度的时间、进程在就绪队列上等待作业调度的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间
$周转时间作业完成时间作业提交时间平均周转时间各作业周转时间之和作业数带权周转时间作业周转时间作业实际运行的时间作业完成时间作业提交时间作业实际运行的时间平均带权周转时间各作业带权周转时间之和作业数$

等待时间

指作业/进程处于等待处理机状态之和，等待时间越长，用户满意度越低。

对于进程，等待时间就是指进程建立之后等待被服务的时间之和，在等待I/O完成的期间其实进程也是被服务的，所以不计入等待时间
对于作业，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间

响应时间

只从用户提交请求到首次响应所用的时间

调度算法

先来先服务（FCFS）

短作业优先（SJF）

短作业/进程优先算法默认是非抢占式
在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少
相比于其他算法，SJF依然可以获得较少的平均等待时间、平均周转时间

高响应比优先（HRRN）

时间片轮转调度算法（RR）

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间，因此时间片不能太大。
如果时间片太小，会导致进程切换过于频繁，系统会花大量时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片不能太小。

优先级调度算法

多级反馈队列调度算法

系统进程>交互式进程>批处理进程

同步与互斥

一个时间段内只允许一个进程使用的资源称为临界资源。
进入区和退出区是负责实现互斥的代码段。

空闲让进
忙则等待
有限等待
让权等待

进程互斥的软件实现方法

单标志法

两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
缺点：“空闲让进”

双标志先检查法

设置一个布尔型数据flag []，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=true”意味着0号进程P0现在想要进入临界区。
缺点：违反“忙则等待”原则

双标志后检查法

相对于“双标志先检查法”，先进行“上锁”，在进行“检查”
缺点：违背了“空闲让进”和“有限等待”原则，会产生“饥饿”现象

Peterson算法

如果双方都争着想进入临界区，那可以让进程尝试谦让。
缺点：未遵循“让权等待”原则

进程互斥的硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现
优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程

TestAndSet指令

TSL指令使用硬件实现的，执行的过程不允许被中断，只能一气呵成。（简称TS指令或TSL指令）
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

Swap指令

也叫XCHG指令，与TS指令相似
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

锁

互斥锁：一个进程在进入临界区时应获得锁；在退出临界区时释放锁。（忙等待）
需要连续循环忙等的互斥锁，被称为自旋锁
优点：等待期间不用切换进程上下文，多处理机系统中，若上锁的时间短，则等待代价很低，常用于多处理机系统，不适用于单处理机系统。

信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量操作，从而很方便的是西安进程互斥、进程同步。
信号量：标识系统中某种资源的数量
整形信号量不满足“让权等待”原则，会发生“忙等”；但记录型信号量不会出现这个问题。

实现进程互斥

分析并发进程的关键活动，划定临界区
设置互斥信号量mutex，初值为1
在进入区P（mutex）–申请资源
在退出区V（mutex）–释放资源
对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。

实现进程同步

分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作
设置同步信号量S，初始值为0
在“前操作”之后执行V（S）
在“后操作”之前执行P（S）

生产者与消费者问题

系统中有一组生产者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品使用。（生产者、消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问）

semophore mutex=1;                   //临界区互斥信号量
semophore empty=n;                   //空闲缓冲区
semophore full=0;                    //缓冲区初始化为空
producer(){                          //生产者进程
	while(1){
		produce an item in nextp;    //生产数据
		P(empty);                    //获取空缓冲区单元
		P(mutex);                    //进入临界区
		add nextp to buffer;         //将数据放入缓冲区
		V(mutex);                    //离开临界区，释放互斥信号量
		V(full);                     //满缓冲区加1
	}
}
consumer(){                          //消费者进程
	while(1){
		P(full);                     //获取满缓冲区单元
		P(mutex);                    //进入临界区
		remove an item from buffer;  //从缓冲区中取出数据
		V(mutex);                    //离开临界区，释放互斥信号量
		P(empty);                    //空缓冲区数加1
		consume the item;            //消费数据
	}
}

读者写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上地读进程同时访问共享数据时不会产生副作用，但若某个写进程和其它进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：允许多个读者可以同时对文件执行读操作；只允许一个写者往文件中写信息；任一写者在完成写操作之前不允许其他读者或写者工作；写者执行写操作之前，应让已有的读者和写者全部退出。

int count=0;          //用于记录当前的读者数量
semaphore mutex=1;    //用于保护更新count变量是的互斥
semaphore rw=1;       //用于保证读者和写着互斥地访问文件
semaphore w=1;        //用于实现“写优先”
writer(){             //写者进程
	while(1){
		P(w);         //在无写进程请求时进入
		P(rw);        //互斥访问共享文件
		writing;      //写入
		V(rw);        //释放共享文件
		V(w);         //恢复对共享文件的访问
	}
}
reader(){             //读者进程
	while(1){
		P(w);         //在无写进程请求时进入
		P(mutex);     //互斥访问count变量
		if(count==0)  //当一个读进程读共享文件时
			P(rw);    //阻止写进程写
		count++;      //读者计数器加1
		V(mutex);     //释放互斥变量count
		V(w);         //恢复对共享文件的访问
		reading;      //读取
		P(mutex);     //互斥访问count变量
		count--;      //读者计数器减1
		if(count==0)  //当最后一个读进程读完共享文件
			V(rw);    //允许写进程写
		V(mutex);     //释放互斥变量count
	}
}

哲学家进餐问题

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌子摆一根筷子，桌子的中间是一碗米饭。哲学家倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才是试图拿起左、右两根筷子。如果筷子已在他人受伤，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

semaphore chopstick[5]={1,1,1,1,1};  //初始化信号量
semaphore mutex=1;                   //设置取筷子地信号量
Pi(){                                //i号哲学家的进程
	do{
		P(mutex);                    //在取筷子前获得互斥量
		P(chopstick[i]);             //取左边筷子
		P(chopstick[(i+1)%5]);       //取右边筷子
		V(mutex);                    //释放取筷子的信号量
		eat;                         //进餐
		V(chopstick[i]);             //放回左边筷子
		P(chopstick[(i+1)%5]);       //放回右边筷子
		think;                       //思考
	}while(1);
}

管程

管程是一种特殊的软件模块：

局部于管程的共享数据结构说明
对该数据结构进行操作对的一组过程
对局部于管程的共享数据设置初始值的语句；
管程有一个名字；
管程的基本特征：
局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入莞城访问共享数据
每次仅允许一个进程在管程内执行某个内部过程

死锁

死锁：各进程互相等待对方手里的资源，导致各进程阻塞，无法推进的现象。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。
死循环：某进程执行过程中一直跳不出某个循环地现象。
死锁发生的条件：

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己已有的资源保持不变。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

发生死锁的时机：

对系统资源的竞争
进程推进顺序非法
信号量使用不当
死锁地处理策略：
预防死锁
避免死锁：”银行家算法“：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态
死锁的检测和解除
- 资源剥夺法
- 撤销进程法
- 进程回退法

XYX Blog

第二章-进程管理