OS--学习笔记：进程管理
二、进程管理
1.前驱图以及程序顺序执行和并发执行的特点
-
前驱图：一种用来描述程序（或进程）之间先后执行顺序的有向无环图（简称DAG）
-
顺序执行特点
- 顺序性
- 封闭性
- 程序运行时独占全资源
- 执行结果不受外界因素影响
- 可再现性
- 执行环境和初始条件相同，程序重复执行，最终结果相同
-
并发执行的特点
-
间断性
-
失去封闭性
-
不可再现性
结论：程序在并发执行时，其计算结果和并发执行程序执行的速度有关，从而使程序的执行失去可再现性
-
-
进程的概念和思想
- 进程是一个可并发执行的具有独立功能的程序关于某个数据集合的依次执行过程，也是操作系统进行资源分配和保护的基本单位。
- 引入进程的目的：使多个进程能够并发执行，以提高资源利用率和系统吞吐量
-
进程的状态与转换
-
进程控制块及其作用
- 概念：是进程实体的一部分，记录了OS所需的，用于描述进程当前情况，以及控制进程运行的全部能容
- 具体作用：使一个在不到程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程比方执行的进程，PCB是进程存在的唯一标志
- 进程控制块中的信息：
- 进程标识符：用于标识一个进程
- 处理机状态：由CPU中各种寄存器中的内容组成，用于中断时信息的存储
- 进程调度信息：进程状态，优先权等
- 进程控制信息
-
进程组织方式：
-
线性方式：把所有PCB组织在一张线性表中，将该表的首地址存放在内存的一个专用区域中， 适用于系统中进程数目不多的情况。优点：实现简单、开销小；缺点：每次查找是需要扫描全表
-
连接方式：把具有同一状态的 PCB，用其中 的链接字链接成一个队列，PCB存储在一个连续的存区。
-
索引方式：各个索引表在内存单元中的首地址也记录在内存中的专用单元中， 用添加索引表的方式记录具有相应状态下的某个PCB在PCB表中的地址。
-
-
进程组织：
- 进程控制块（PCB）
- 程序段
- 数据段
-
进程同步的概念与原则
- 概念：进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系
- 原则：
- 空闲让进：临界区空闲，可以允许一个请求进程立即进入临界区
- 忙则等待：已有进程进入临界区，其他试图进入理解去的进程等等
- 有限等待：对请求访问的进程，应保证其在有限时间内进入临界区
- 让权等待：单进程不能进入临界区使，应理解释放处理机防止等待
-
互斥概念：一个进程进入临界区使用资源时，另一个进程必须等待，当占用临界资源的进程推出临界区时，另一个进程才允许去访问此临界资源
-
临界资源：一次允许一个进程访问的资源
-
临界区：进程中访问临界资源的那段代码
-
信号量：信号量S的值表示它代表的物理资源的使用状态，S>0表示还有共享资源可以使用，S=0 表示共享在在被使用且没有多余的资源，S<0表示资源已被分配完且|S|为当前等待进程数量
-
经典进程同步问题：
-
常见信号量描述：
整型：
// P操作（或者称 wait(S) 原语） wait(S) { while(S <= 0) // 未遵循“让权等待”。当 S <= 0 时，使得进程一直“忙等” ; // 空操作 S--; } // V 操作（或者称 signal(S) 原语） signal(S) { S++; }记录型
// 类型定义 typedef struct{ int value; struct process_control_block *list; }semaphore; // P操作（或者称 wait(S) 原语） wait(semaphore *S) // 相当于申请资源 { S->value--; if(S->value < 0) block(S->list); } // V 操作（或者称 signal(S) 原语） signal(semaphore *S) // 相当于释放资源 { S->value++; if(S->value <= 0) wakeup(S->list); } -
应用：
实现同步
// P2 的 y 要调用 P1 的 x 的结果，所以需要先执行 P1 的 x 后再执行 P2 的 y semaphore S = 0; P1() { ...; x; // x 语句 V(S); // 通知 P2，x 语句已完成 ...; } P2() { ...; P(S); // 检查语句 x 是否完成 y; // 检查无误，运行 y ...; }实现互斥
semaphore S = 1; P1() { ...; P(S); // 准备访问前，对临界资源加锁 进入 P1 临界区; V(S); // 访问结束，释放临界资源的锁 ...; } P2() { ...; P(S); 进入 P2 临界区; V(S); ...; } -
实现前驱图关系
- 进程前半段包含对前驱结点资源的 P 操作（想要前驱完成，才能继续本进程的继续向下运行）
- 进程后半段包含对自身结点资源的 V 操作（释放自身，通知其后继结点，我已完成）
-
经典进程同步问题
-
生产者 - 消费者问题
// 生产者-消费者模型 // in 输入缓冲区中数据的位置 // out 输出缓冲区中数据的位置 int in = 0, out = 0; // buffer 缓冲区 item buffer[n]; // mutex 临界区互斥信号量。 // 若为 1，则临界区空闲； // 若为 0，说明有一个进程在使用，另一个进程并未请求使用； // 若为 -1，则临界区正被一个进程使用，并且有另一个进程在请求使用这个临界区 // empty 表示还剩下多少空闲缓冲区，初始化为 n。若为 0，则缓冲区已满 // full 表示缓冲区已经使用的个数，初始化为 0。若为缓冲区的最大容量，则缓冲区已满。 semaphore mutex = 1, empty = n, full = 0; void producer() { do{ produce an item nextp; ...; wait(empty); // 使用 wait(P操作) 检查是否还有空闲缓冲区资源 // 总结：要什么临界资源之前，先 P 一下 wait(mutex); // 互斥访问请求 buffer[in] = nextp;// 临界区操作 in = (in + 1) % n; signal(mutex); // 互斥访问释放 signal(full); // 缓冲区已使用个数加 1(注意这里是 full ) // 总结：操作完成后，提供什么资源，要 V 一下 }while(TRUE); } void consumer() { do{ wait(full); // 使用 wait(P操作) 检查缓冲区是否有资源（注意是检查 full ） wait(mutex); nextp = buffer[out]; out = (out + 1) % n; signal(mutex); signal(empty); // 缓冲区空闲个数加 1(注意这里是 empty ) consume the item in nextp; ...; }while(TRUE); } void main() { cobegin producer(); consumer(); coend } -
哲学家进餐问题
// 此法可能导致死锁：每个人都拿起左手边的筷子，每个人都又申请右手边的筷子，此时产生死锁。 semaphore chopstick[5] = {1, 1, 1, 1, 1}; Pi() { do{ wait(chopstick[i]); wait(chopstick[(i + 1) % 5]); ...; // eat ...; signal(chopstick[i]); signal(chopstick[(i + 1) % 5]); ...; // think ...; }while(TRUE); }// 改进方案：仅当一名哲学家左右两边的筷子都可用时，才允许拿筷子 semaphore chopstick[5] = {1, 1, 1, 1, 1}; semaphore mutex = 1; // 互斥取筷子 Pi() { do{ wait(mutex); wait(chopstick[i]); wait(chopstick[(i + 1) % 5]); signal(mutex); // 注意在此时释放互斥取筷子信号量 ...; // eat ...; signal(chopstick[i]); signal(chopstick[(i + 1) % 5]); ...; // think ...; }while(TRUE); } -
读者 - 写者问题
// rmutex 信号量用于多个 reader 进程互斥访问 readcount 这个临界资源 // wmutex 信号量用于 reader 和 writer 互斥访问 semaphore rmutex = 1, wmutex = 1; int readcount = 0; void reader() { do{ // 正式读之前，readcount 要增 1 wait(rmutex); if(readcount == 0) wait(wmutex); readcount ++; signal(rmutex); ...; perform read operation; ...; // 读完后，readcount 要减 1 wait(rmutex); readcount--; if(readcount == 0) signal(wmutex); signal(rmutex); }while(TRUE); } void writer() { do{ wait(wmutex); perform write operation; signal(wmutex); }while(TRUE); }
-
-
-
进程通信的基本概念和方法
- 概念：指进程之间的信息交换
- 进程通信方法：
- 低级：PV 操作
- 高级：
- 共享存储：基于共享数据结构、基于共享存储区
- 管道通信：半双工通信（某一时刻只能单向传输）
- 消息传递：
- 直接通信：通过原语，发送端直接到接受端
- 间接通信：通过共享中间实体（称作邮箱）进行消息收发
- 客户机 - 服务器系统：套接字、远程过程调用和远程方法调用
-
线程的概念：是轻量级进程，是进程中的一条执行路径
-
引入线程的优点：程序执行效率高、响应时间长、程序的交互性好
-
多线程模型：
-
多对一模型：多个用户级线程映射到一个内核级线程
- 优点：线程管理在用户空间进行，效率较高
- 缺点：
- 一个线程在使用内核服务时被阻塞，整个进程都会被阻塞
- 多个线程不能并行地运行在多处理机上
-
一对一模型：一个用户级线程映射到一个内核级线程
- 优点：一个线程被阻塞，允许另一个线程继续执行，并发能力强
- 缺点：这样创建线程，开销较大，影响程序性能
-
多对多模型：
n 个用户级线程映射到 m 个内核级线程（m ≤ n）
对比前两者，可谓集两者之所长，补两者之所短
-