Lec2 Process
进程¶
Why process¶
提高计算机系统中各种资源的利用率
现代 OS 广泛采用多道程序技术（multi-programming），多个程序在 OS 中同时存在并运行。
在多道程序系统中，程序并发执行，CPU需要在各个运行的程序之间来回切换。
x86 CPU Registers¶
通用寄存器
共有 8 类，又可以分成两组：4个数据寄存器，4个指针寄存器及变址寄存器。
AH & AL = AX (accumulator)：累加寄存器。 BH & BL = BX (base)：基址寄存器 CH & CL = CX (count)：计数寄存器 DH & DL = DX (data)：数据寄存器
- SP (Stack Pointer)
- BP (Base Pointer)
- SI (Source Index)
- DI (Destination Index)
主要用来形成操作数的地址，用于堆栈操作和变址运算中计算操作数的有效地址。
段寄存器（Segment Register）
- CS (Code Segment)
- DS (Data Segment)
- SS (Stack Segment)
- ES (Extra Segment)
决定程序代码，数据，堆栈各要用到内存的那些位置。
FS、GS：两个辅助段寄存器
指令指针 IP (Instruction pointer)
标志寄存器 FR (Flag Register)
进程的概念¶
A process is a program in execution
进程包含一个正在运行的程序的所有状态信息
A Process is a program + running context
也就是说进程是一个动态的概念
进程的特性¶
- 动态性
- 独立性
- 并发性
进程的创建¶
- 系统初始化：服务进程，自启进程
- 正在运行的进程执行了创建进程的系统调用
- 用户请求创建一个新进程
从技术上说，只能通过系统调用创建一个新的进程
进程的状态¶
- 运行状态
- 就绪状态
- 阻塞状态
进程的转换
进程控制块¶
进程控制块（Process Control Block）是用来描述进程的数据结构。系统为每个进程维护一个 PCB，保存与该进程有关的各种状态信息。
- 进程的创建：生成一个 PCB
- 进程的终止：回收 PCB
- 进程的组织管理：组织管理 PCB
操作系统会维护一组队列，表示系统中所有进程的当前状态。不同状态的进程用不同的队列来管理（运行队列，就绪队列，各种阻塞队列）。
线程¶
Why Thread¶
需要一种新的实体，有以下特性：
- 实体之间可以并发执行
- 实体之间共享相同的地址空间
这个东西就是我们需要的 “Thread” 的概念。
进程拥有一个完整的资源平台，线程只独享必要的资源，如 reg，stack，PC。
线程控制块¶
Thread Control Block，描述线程的数据结构。
进程间通信¶
进程间通信与同步¶
进程间通信（Inter Process Communication, IPC）
- 进程互斥问题：两个或多个进程在访问共享资源时，如何确保它们不会相互妨碍
- 进程同步问题：当进程之间存在某种依存关系时，如何调整它们运行的先后次序
进程间有不同的通信方式
- 低级通信：只能传递状态或整数值
- 信号量，信号
- 高级通信：能传送任意数量的数据
- 共享内存，消息传递，管道
进程间互斥¶
- 竞争 CPU
- 竞争资源
竞争状态：两个或多个进程对同一共享数据同时进行读写的操作
解决方案：同一时刻，只允许一个进程访问该共享数据（互斥概念）
- 临界区：可能会导致竞争状态出现的程序段
- 临界资源：需要互斥访问的共享资源
实现互斥访问的条件
- 任何两个进程不能同时进入临界区
- 不能事先假定 CPU 的个数，核数和运行速度
- 一个进程运行在临界区外时，不能妨碍其他进程进入临界区
- 进程进入临界区的要求应得到满足
基于关闭中断的互斥实现¶
当一个进程进入临界区后，关闭所有的中断；当它退出临界区时，再打开中断。
问题：
- 临界区中可能有大量计算
- 能否用于用户进程？
- 能否用于多 CPU 系统？
基于繁忙等待的互斥实现¶
加锁¶
缺点：可能出现对于锁的竞争
强制轮流法¶
缺点：违反了互斥访问四条件中的第三个条件
一个进程运行在临界区外时，不能妨碍其他进程进入临界区
Peterson 方法¶
当一个进程想进入临界区时，先调用 enter_region，判断能否安全进入，不能的话等待。从临界区退出时，调用 leave_region。
小结¶
基于 busy waiting 的策略有一些共同的缺点，
- 浪费CPU时间
- 可能导致预料之外的结果（如高优先级的进程在低优先级的进程在临界区中时试图进入临界区）
- 这是一个导致死锁的例子
- 解决的方式是把等待进入临界区的进程阻塞掉
Question
如果允许 \(N\) 个进程同时进入临界区如何解决？
信号量¶
- Dijkstra
基本思路：用一种新的变量类型（semaphore）来记录当前可用资源的数量，这个值可正可负。
信号量由 OS 维护，用户只能用初始化和两个标准原语访问，初始化可指定空闲资源总数
- P原语：申请一个空闲资源（信号量减1），成功则退出，失败则阻塞该进程
- V原语：释放一个被占用资源（信号量加1），若发现有被阻塞的进程，选择一个唤醒
typedef struct {
int count;
struct PCB* queue;
} semaphore;
可以利用信号量来实现进程互斥。
进程间同步¶
进程间的同步是指多个进程中发生的事件存在某种时序关系。
一个尝试
// A
A; V(S);
// B
P(S); B;
Note
- 将初始信号量设置为 0
- 先执行的代码后面整个 V 原语
- 后执行的代码前面整个 P 原语
Example
- Compute & Print
- 生产者-消费者
- 哲学家就餐问题
进程调度¶
要解决的问题¶
- When：合适分配 CPU
- 调度时机
- What：按什么原则分配 CPU
- 调度算法
- How： 进程的上下文切换
- 上下文切换
进程的行为¶
- CPU 执行 (CPU burst)
- 等待 I/O (I/O burst)
调度算法的目标¶
- 周转时间
- 平均周转时间
- 平均带权周转时间
- 等待时间
- 响应时间
- 吞吐量
- CPU利用率
- 设备的均衡利用
时间片轮转法¶
将所有的就绪进程按照FCFS原则，排成一个队列，时间片结束时，在时钟中断中，进程调度程序暂停当前进程的执行，将其送到就绪队列的末尾，然后执行队首进程。
优先级算法¶
给每个进程设置一个优先级，然后再所有就绪进程中选一个优先级最高的进程去运行。
Example
Shortest Job First 就是一个优先级算法，优先级是它的 CPU 运行时间