0%

操作系统-进程管理

Posted on Edited on

SurfboardRow_ZH-CN5154549470_1920x1080.jpg

进程 & 线程

进程

进程是指具有一定独立功能的程序在一个数据集上的一次动态执行过程，进程是资源分配的基本单位

进程的特点

  • 动态性：可以动态创建、结束进程
  • 并发性：进程之间可以通过时间片轮询并发执行
  • 独立性：不同进程工作互不影响，需要通过进程通信
  • 制约性：多个进程访问临界资源时需要实现同步机制

进程 & 程序

  • 进程是处于执行状态的程序的抽象，包括程序和执行状态；程序是静态可执行文件
  • 同一个程序的多次执行对应着不同的进程
  • 进程是资源分配的基本单位，进程运行需要系统资源，比如 CPU 和内存
  • 进程是动态的，程序是静态的
  • 进程是暂时的，程序是永久的

进程控制块

进程控制块是操作系统管理控制进程运行的信息集合，描述了进程的基本信息和运行状态。创建进程时生成该进程的进程控制块，进程终止时回收进程控制块，操作系统通过进程控制块来管理控制进程

进程控制块内容

  • 进程标识信息：FID，UID 等
  • 进程控制信息：进程所用资源、进程间通信信息、调度和状态信息等
  • 现场保存：寄存器

进程地址空间中保存了初始化数据、代码、堆栈、段表、共享库等，抽取一部分信息放在进程控制块中

进程状态

pic

  • 创建（created）
  • 就绪（ready）：进程获取了除 CPU 之前的资源，等待被调度
  • 运行（running）：正在执行的进程
  • 阻塞（waiting）：等待资源或等待某个事件的出现
  • 终止（terminated）

创建 - > 就绪：进程被创建，完成初始化，一切就绪工作执行完就会进入就绪状态

就绪 -> 运行：当前进程时间片执行完，CPU 使用进程调度算法从就绪队列中选择一个进程执行

运行 -> 就绪：运行状态的进程时间片用完或高优先级进程抢占低优先级进程时间片

线程

一个进程可以有多个线程，线程能够提高进程内部的并发性，是独立调度的基本单位。线程共享同一进程的资源

线程的地址空间类似于 Java 运行时数据区域

  • 用户线程：线程功能在用户态实现，开发者能够制定自己的线程调度算法，不需要进入内核态，开销小；但进程是独立调度的基本单位
  • 内核线程（正在使用的）：线程功能由操作系统完成，线程是独立调度的基本单位；线程调度需要进入内核态，开销比较大

进程和线程的比较

  • 进程是资源分配的基本单位，线程是独立调度的基本单位
  • 进程的系统开销比线程大
  • 线程共享进程的资源，通信方便；进程通信需要借助进程通信机制

进程控制

进程切换

  • 暂停当前进程，保存进程状态到 PCB 中，从运行状态变成其他状态
  • 调度另一个进程，从PCB中恢复现场，从就绪状态变为运行状态

进程创建

  • fork：创建子进程，子进程完全复制父进程的地址空间，但子进程有自己的进程ID
  • exec：加载可执行文件并覆盖进程的地址空间
1
2
3
4
5
6
7
8
9
10
11
// 共有两个进程
int main(){
    int childId;
    childId = fork(); // 创建子进程，对父进程地址空间的一次复制。父进程返回子进程ID，子进程返回0
    if(childId == 0) {
        // 执行子进程
        exec(); // 加载子进程代码，会替换掉父进程的代码
    }else {
        //　执行父进程
    }
}
1
2
3
4
5
6
7
8
9
// 共有四个进程
int main() {
    for(int i = 0; i < 2; i++) {
        int pid = fork();
        if(pid == 0){
           // 子进程代码
        }
    }
}

进程调度

调度准则

  • CPU 利用率：CPU处于忙状态的时间百分比
  • 吞吐量：单位时间内完成的进程数量
  • 周转时间：进程从初始化到结束的总时间

调度策略的目标

  • 减少响应时间
  • 减少响应时间的波动
  • 公平性

调度算法

  • 先来先服务：依据进程进入优先队列的先后顺序排列。当前进程进入阻塞或终止状态时，就绪队列中的下一个进程占用 CPU

    3个进程ABC依次到达，计算时间分别为12 3 3，则 FCFS 的周转时间为
    $$
    (12+15+18)/3=15
    $$
    优点：简单

    缺点：平均等待时间波动较大；IO 资源和 CPU 资源利用率低

  • 短进程优先：平均周转时间短

    • 短作业优先：选择执行时间最短的进程占用 CPU

      优点：有最优周转时间

      缺点：不公平，导致长进程饥饿，需要预知未来执行时间

    • 最短剩余时间优先：选择剩余时间最短的进程占用 CPU

  • 最高响应比优先：依据就绪队列中进程等待时间的长短

    能够解决饥饿现象

  • 时间片轮转：时间片结束后，按照先来先服务算法切换到下一个进程

    优点：公平

    缺点：平均等待时间较差

  • 优先级调度：为每个进程分配一个优先级，按优先级进行调度

  • 多级反馈队列：将就绪队列排成多个子队列，不同子队列时间片长短不同，优先级不同

    每个队列可以拥有自己的调度策略

不同的系统对进程调度的要求不一样：

  • 批处理系统：要求高吞吐量和较短的周转时间
  • 交互式系统：要求响应时间短
  • 实时系统：要求一个请求在一个确定时间内得到响应

同步互斥

临界区

对临界资源进行访问的需要互斥执行的那段代码称为临界区

临界区的实现

  • 禁用中断：禁用时钟中断，没有上下文切换，即保证了同一时刻只有一个进程访问临界资源

    缺点：禁用中断后，进程无法被停止，可能导致其他进程处于饥饿状态

  • 软件实现：通过进程之间共享变量的方式实现

  • 更高级的抽象方法

    • 原子操作指令锁（单CPU和多CPU均可）
    • 信号量
    • 管程

信号量

操作系统提供的互斥资源访问的方法

信号是一种抽象数据结构，由一个整型变量（$sem$）和两个原子操作组成，并且包含等待队列

  • P意味着信号量值减1，减完之后如果信号量值小于0，则说明资源不够用的，把进程加入等待队列
  • V意味着信号量值加1，加完之后如果信号量值小于等于0，则说明等待队列里有进程，那么唤醒一个等待进程
1
2
3
4
5
6
void Semaphore::P() {
    sem--;
    if(sem < 0) {
        wait();
    }
}
1
2
3
4
5
6
void Semaphore::V() {
    sem++;
    if(sem <= 0) { // 说明前边还有等待的进程
        notify();
    }
}

P 和 V 操作由操作系统保证原子性，比如说屏蔽中断。如果信号量只能取 0 和 1，他就是互斥量

管程

  • 管程是一种用于多线程访问互斥访问共享资源的程序结构

  • 管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作

  • 管程包括一个锁、一个或多个条件变量

  • 管程可以放弃临界资源访问权

管程 & 信号量

  • 信号量先检查资源信号量，才能进入临界区；管程可以先进入临界区再去检查条件变量
  • 在管程中的线程可以临时放弃管程的互斥访问，让其他线程进入到管程中来；临界区中的线程只能在线程退出临界区时，才可以放弃对临界区的访问

经典同步问题

哲学家就餐问题

同时拿左边或同时拿右边会死锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define N 5
semaphone fork[5];
void philosopher(int i) {
    while(true) {
        think();
        if(i%2 == 1) {
            p(fork[i]);
            p(fork[(i+1)%N]);
        }else {
            p(fork[(i+1)%N]);
            p(fork[i]);
        }
        eat();
        v(fork[i]);
        v(fork[(i+1)%N]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define N 5
semaphone fork[5];
semaphone mutex;
void philosopher(int i) {
    while(true) {
        think();
        p(mutex);
        p(fork[i]);
        p(fork[(i+1)%N]);
        eat();
        v(fork[i]);
        v(fork[(i+1)%N]);
        v(mutex);
    }
}

死锁

死锁

条件

  • 互斥
  • 持有并等待
    • 进程持有至少一个资源，并等待其他进程持有的资源
  • 非抢占
  • 循环等待

处理方法

  • 死锁预防：采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件

    • 持有并等待
      • 进程请求资源时，要求他不持有任何其他资源
      • 仅允许进程在开始执行时，一次请求所有需要的资源

  • 死锁避免

    • 银行家算法

  • 死锁检测和恢复

    • 允许操作系统出现死锁
    • 维护系统的资源分配图
    • 定期用死锁检测算法来搜索图中是否存在死锁
    • 出现死锁时，用死锁恢复机制进行恢复

    死锁检测算法和银行家算法相似

银行家算法

银行家算法是一种死锁避免的算法

银行家 -> 操作系统

资金 -> 系统资源

客户 -> 进程

n = 线程总数
m = 资源类型数量
Available（剩余空闲量）：长度为m的向量
Max（总需求量）：n×m矩阵
Allocation（已分配量）：n×m矩阵
Need（未来需要量）：n×m矩阵
$$
Need[i,j] = Max[i,j]-Allocation[i,j]
$$

安全：

pic

不安全：

pic

进程通信

进程通信是进行信息交流和同步的机制。通信具有两种基本操作：发送操作和接收操作

直接通信和间接通信

  • 直接通信：两个进程通过共享信道实现通信
  • 间接通信：在内核建立消息队列

阻塞通信和非阻塞通信

  • 阻塞通信
    • 阻塞发送：发送者发送消息后进入等待，直到接收者成功接收到
    • 阻塞接收：接收者请求消息后进入等待，直到成功接收消息
  • 非阻塞通信
    • 非阻塞发送：发送者发送消息之后执行其他操作
    • 非阻塞接收：没有消息时，接收者请求接收消息，不会得到任何消息

信号

进程间的软件中断通知和处理机制

信号的接收处理：

  • 捕获
  • 忽略
  • 屏蔽

缺点：传送信息少，只有一个信号类型

管道

进程间基于内存文件的通信机制

缺点：

  • 只支持半双工通信（双向交替传输）
  • 只能在父子进程中使用

消息队列

消息队列是由操作系统维护的以字节序列为基本单位的间接通信机制

  • 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难
  • 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法
  • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收

共享内存

共享内存是把同一个物理内存区域映射到多个进程的内存地址空间的通信机制

优点：快

缺点：不提供同步，需要程序员实现同步机制