1 进程管理

学习笔记
作者: MingXiao

1.1 多进程

正在运行的程序才是进程

为了每一个进程能看上去在独立使用CPU，每个进程都需要一个PCB

PCB中记录

  • 当前程序指针，栈指针
  • 寄存器状态
  • 所有的地址都是私有地址，本质是逻辑地址
  • 基地址，用于物理地址换算

进程状态图

子进程

调用fork()函数，为父进程创建一个子进程，函数返回子进程的pid

子进程没有创建孙进程，其pid_t类变量为0

进程切换

内核在进程上下文切换时采取的行动

  1. 保存PC和堆栈指针
  2. 保存寄存器和其他机器状态（FLAGS）
  3. 确定下一个要执行的进程
  4. 检索下一个进程的PCB，利用PCB恢复这个进程的状态

硬件利用率：使用时间 /（使用时间+空闲时间）

1.2 线程

进程是资源分配的基本单位（PCB），线程是调度的基本单位

Amdahl定律

一个进程能被并行加速的上限
\[ Q = \frac{1}{S+\frac{1-S}{N}} \]
其中\(S\)为必须串行的部分，\(1-S\)为可并行部分，\(N\)是并行资源数量

线程

CPU使用的基本单元，包括tid，PC，寄存器和堆栈

同一进程的不同线程共享代码段、数据段和其他资源（基地址一致，用同一块PCB）

进程由线程组成；线程的创建和切换开销小得多，因为不需要资源分配和上下文切换

并行与并发

并行：同时运行多个线程，必须要求多核

并发：支持多个任务，单核可以实现，但是交换线程时需要切换

可以有并发无并行：单核CPU交替执行多个线程

多线程模型

  • 多对一：多个用户级线程到一个内核线程。用户的线程库完成调用，效率高；但一个线程执行阻塞时，整个进程都会阻塞；不能并行
  • 一对一：更好的并发度，可以并行；开销大，限制了线程数量
  • 多对多：任意多的用户线程，且增加了并发度

多对一适用于计算密集型，多对多适用I/O密集型

用户级线程的切换不需要内核支持，用户态调度就行

线程切换

TCB、栈和PC都要切换

MMU：memory manage unit

多处理器独享MMU，对应对进程；多核共享一个MMU，对应多线程

只有一套MMU时，只有多进程而没有多线程的情况下，不能提高并行度；需要多核心线程才能最大化利用CPU

1.3 CPU调度

进程调度场景

  1. 运行——等待：等待I/O等
  2. 运行——就绪：遇到中断
  3. 等待——就绪：I/O完成
  4. 终止

14是非抢占式的主动调度，23是抢占式的调度

调度准则

  • CPU利用率：CPU尽可能忙碌
  • 吞吐量：一个时间单元内完成的进程数
  • 周转时间：进程提交到完成
  • 等待时间：在就绪队列中的等待时间
  • 响应时间：从提交到第一次响应

调度算法

  • 先到先服务，FCFS
  • 最短作业优先，SJF，最短的周转时间
    • 需要用指数加权平均预测下次CPU执行时间，\(\tau_{n+1} = \alpha t _n+(1-\alpha)\tau_n\)，其中\(t_n\)为第n时刻CPU的执行时间
    • 若是抢占式的，那就是最短剩余时间优先
  • 优先级调度，Priority
    • 优先级反转：高优先级等待低优先级，原因是高优先级所需的资源被更低优先级上锁，必须等到低优先级完成后更低优先级才能释放
      • 解决方案：优先级继承：正在访问共享资源的京城获取需要这个资源的的更高优先级进程的优先级，完成后恢复
  • 轮转，RR
  • 多级队列调度
  • 多级反馈队列调度

指标间的矛盾

  • CPU利用率和响应时间：快速切换可以降低响应时间，但是频繁的上下文切换会降低CPU利用率
  • 周转时间和等待时间：SJF的周转时间最短，但是这样会增大长任务的等待
  • I/O利用率和CPU利用率：频繁切换上下文，CPU利用率低了，但是I/O高了
  • 前台任务和后台任务的关注点：响应和周转，I/O和CPU
  • 响应时间和吞吐量：频繁切换，前者小，但是后者差

1.4 进程同步

临界区：进程执行这个区可以修改公共变量，同时不允许其他进程在各自的临界区执行

进入区：临界区之前

其他是剩余区

临界区问题

需要满足下面的条件

  • 互斥：同时仅一个进程在临界区内
  • 进步：仅不在剩余区的进程可以进入临界区
  • 有限等待：一个进程从请求到进入临界区前，其余进程进入临界区此时有上限

Peterson算法

适用于两个进程交错执行临界区与剩余区

对于单个进程来说，程序如下

do{
	flag[i] = true;
	turn = j;
	while(flag[j] && turn == j)
		; // do nothing, pending
	
	/* critical section */
	
	flag[i] = false;
	
	/* remainder section */
	
}while(true)

仅在仅顺序执行命令的CPU上可用

硬件同步

三种方法：内存屏障，TsetAndSet()，CompareAndSwap()；后面两个都是原子化指令

内存屏障

确保多核处理器的内存访问顺序能排序和同步

顺序保证：强：对共享内存修改会立刻广播至其他处理器；弱：无法保证，但存在Cache和MEM更新机制

硬件指令

TestAndSet()如下

boolean TestAndSet(boolean *target)
{
	boolean rv = *target;
	*target = TRUE;
	return rv;
}

这三条指令是原子化的，也就是必须连续执行，不能中断；这可以用来设置锁

do{
	while(TestAndSet(&lock))
		;	// pending
		
	/* critical section */
	
	lock = FALSE;
	
	/* remainder section */
}while(true)

可以用于大于两个进程的场景；lock初始化为FALSE

CompareAndSwap()如下

int CompareAndSwap(int *value, int expected, int new_value)
{
	int temp = *value;
	if (*value == expected)
		*value = new_value;
	return temp;
}

也是原子化的指令，也用在锁中

while(true){
	while(CompareAndSwap(&lock, 0, 1) != 0)
		; // pending
	
	/* critical section */
	
	lock = 0;
	
	/* remainder section */
}

互斥锁

acquire()获取锁，release()释放锁

bool avaliable = true;

void acquire()
{
	while(!available)
		; /* busy wait */
	avaliable = false;
}

void release()
{
	avaliable = true;
}

但是存在问题：当锁不可获取时，CPU一直在acquire()中，浪费周期

信号量

两个标准原子操作

typedef struct{
    int value;
    struct process *list;
}semaphore;

void wait(semaphore *S)			// P(S)
{
	S->value--;
    if (S->value <= 0)
    {
        // add this process to S->list
    	sleep();		// pending this process
    }
}

void signal(semaphore *S)		// V(S)
{
	S->value++;
    if (S->value <= 0 && S->list != NULL)
        // remove a process P from S->list
        wakeup(P);		// wake up the process
}

信号量可以是负数，其绝对值表示正在等待它的进程数

一个使用例子

两个进程依次访问一个数组

int arr[8] = {2, 5, 7, 4, 1, 3, 8, 10};
int S1 = 1, S2 = 0;
int arr1[8] = {0}, arr2[8] = {0};

void P1()
{
    int index1 = 0;
    for (index1; index1 < 8; index1++)
    {
        P(S1);
        if (arr[index1] % 2 == 0)
            arr1.append(arr[index1]);
        V(S2);
    }
}

void P2()
{
    int index2 = 0;
    for (index2; index2 < 8; index2++)
    {
        P(S2);
        if (arr[index2] % 2 == 1)
            arr2.append(arr[index2]);
        V(S1);
    }
}

1.5 死锁

死锁：一系列被阻塞的进程持有部分资源，同时需要另一部分资源，这些资源被该系列中的进程所持有

死锁特征

  • 互斥：至少一个资源是非共享的，一次只能有一个进程可使用
  • 占有并等待：占有一个资源，并等待另一个被占有的资源
  • 非抢占：资源不能抢占
  • 循环等待：在资源分配图中成环

资源分配图

成环并不要求在同一个资源点

没有成环一定无死锁；成环不一定死锁，但资源仅一个实例那一定死锁

死锁处理

  • 预防，确保至少一个条件不成立
  • 避免，得到申请后推算是否会发生死锁
  • 检测和恢复

死锁预防：

  • 互斥：不可能不互斥
  • 占有并等待：每个进程在执行前申请并获取所有的资源；资源利用率低，会发生饥饿
  • 非抢占：将被阻塞的进程的资源隐式释放，可被抢占；但这些资源必须可恢复（PCB）
  • 循环等待：对资源排序，按需分配；用于资源不多的情况，因为不可能一直排序，开销太大

死锁避免

  • 进程声明每种资源的最大数量
  • 动态检查资源分配状态，确保不会死锁

安全状态算法

按一定顺序分配资源，不发生死锁，那么存在安全序列

安全一定不死锁；非安全不一定死锁；死锁一定非安全

安全状态算法保证在安全状态内

银行家算法

  • 每个资源类型有多个实例
  • 每个进程声明需要的最大数量
  • 每个进程必须在有限时间内释放资源

在进程提出申请时，假设给出，调用安全状态算法，存在安全序列就真给，不存在就不给



Comments