进程管理

进程管理

概念

并发：程序的并发执行是指两个或两个以上的程序或程序段在同一时间段内发生

进程：是程序的一次执行-> 资源分配由 PCB 控制，==（就算被阻塞也）常驻内存==

​​

⚠️ 进程不一定就并发，线程不一定并行，这两对概念没有对应关系

多道程序设计系统：在多道程序设计中，操作系统将 CPU 时间分割成很短的时间片（时间段），并在每个时间片中将 CPU 分配给不同的程序。这样，多个程序可以并发地执行，从而提高了系统的吞吐量和利用率。
不过不一定采取时间片轮转算法？

临界资源是一次仅允许一个进程使用的共享资源
每个进程中访问临界资源的那段代码称为临界区

原语：不可分割的操作

进程的基本概念

进程=pcb+ 程序段 + 数据段

三种基本状态：运行，就绪，阻塞

两个额外状态：创建，终止

状态转换：

• (1) 就绪 → 执行
  处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。

• (2) 执行 → 就绪
  处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。（一旦再次分配到时间片就可以立即执行）

• (3) 执行 → 阻塞
  正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。

• (4) 阻塞 → 就绪
  处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。

  • 注意，是“等待的事件”而不是什么其他的词汇
  • 是发生而不是完成

挂起状态：在操作系统中可以定义为暂时被淘汰出内存的进程的状态

进程控制

系统态，用户态

父进程，子进程，资源关系

【这部分看下 ppt】进程控制原语：
创建，撤销，阻塞，唤醒，挂起，激活

进程同步

​​

广义同步：对多个相关进程在执行次序上进行协调，它的目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性；包含狭义同步和互斥

临界资源：一次只允许一个进程使用的资源

临界区：每个进程中访问临界资源的代码

经常做题的时候反应不过来这几个词含义是什么

规则：空闲让进，忙则等待，有限等待，让权等待

虽然很八股，但是有的选择题会让你判断 xx 代码符合上述的哪几个规则，读者应该明确这几个词的含义...

信号量机制

• 整形信号量
• 记录型信号量 value 和 next 指针
• and 型信号量
• 信号量集

整形信号量

一个 int，可以 wait 和 signal

记录型信号量【重点】

是一个数据结构

​​

Typedef struct{
	int value;
	struct process_control_block *list;
} semaphore;
	相应地，wait(S)和signal(S)操作可描述为：
wait(semaphore *S){
	S->value --;
	if S->value＜0 block(S->list)
}
signal(semaphore *S){
	S->value ++;
	if S->value＜=0 wakeup(S->list)
}

and 型信号量

给一个进程一次性分配全部的资源

swait(S1, S2, …, Sn){
	while (TRUE){
	if ( S1≥1 && … && Sn≥1 ){
	for (i=1; i<=n; i++) Si--;
	break; // 成功为进程分配资源跳出 while
}
else
	place the process in the waiting queue associated with the
	first Si found with Si＜1, and set the program counter of
	this process to the beginning of Swait operation
}
}
Ssignal(S1, S2, …, Sn){
	while (TRUE){
		for (i=1; i<=n; i++){
			Si ++;
			Remove all the process waiting in the queue associated
		with Si into the ready queue.
}}}

信号量集

？细节位置

实现互斥访问，实现前趋关系

​​

若是前面的一对代码交换：...

进程同步的经典问题

经典问题：生产者消费者问题；读者写者问题；哲学家进餐；

大题大概率从这里出，仔细看一下并且刷几道

linux 的信号量接口:

进程通信

​​

• 低级通信和高级通信；直接通信和间接通信（通过中间实体）
• 消息缓冲队列-> 直接通信的例子
• Linux 中的进程间通信（消息队列、共享内存、管道）

这部分看一下它 ppt 中的提法吧

线程

线程是 cpu 调度单位，是“轻量化”进程；进程是资源分配单位，若是在具有线程的 os 里，进程不可执行

还是要仔细琢磨下区别

状态：执行就绪阻塞-> 控制块 tcb

实现方式：内核，用户，组合；注意解释和优缺点，前者并行效率高，但是开销大

​​

死锁

定义：当两个以上的运算单元，双方都在等待对方停止执行，以获取系统资源，但是没有一方提前退出时，就称为死锁。

产生原因

系统资源的竞争，进程推进的非法

产生的必要条件

互斥，不剥夺，请求并保持，循环等待

循环等待若是同类资源大于一，可通过外部的请求打破，不等于死锁的字面意

​​

区分不剥夺和请求保持

处理策略

预防

避免

安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态

不安全状态不一定死锁

银行家算法一定会手算和做题

检测和解除

资源分配图
圆圈代表进程，方框代表资源
进程-> 资源 请求边
资源-> 进程 分配边

​​

简化：模拟进程执行并释放所有资源

死锁定理：当且仅当某状态的资源分配图不可完全简化

解除方法：资源剥夺法；撤销进程法；进程回退法

处理机调度

调度的层次

• 高级调度：从后备队列建立进程
• 中级调度：挂起至外存和激活
• 低级调度：分配和解除分配处理机

​​

衡量调度好坏的指标

• CPU 利用率,CPU工作时间 \div (CPU工作时间+空闲时间)

• 系统吞吐量: 单位时间内 CPU 完成作业的量

• 周转时间：作业提交到作业完成的事件

  • 平均周转时间
  • 带权周转时间 作业周转时间 \div 作业实际运行时间

• 等待时间: 进程处于就绪状态等待 CPU 所花费的总时间

• 响应时间：作业提交到系统产生第一个输出

调度的实现

​​

调度的时机

除了：处理中断的过程，内核临界区和原子操作，都可以切换

调度方式：剥夺，非剥夺

闲逛进程：系统中没有就绪进程时执行

层级：用户级调度，内核级调度

典型算法

​​

‍