bomo的开发随笔

记录工作学习点滴

0%

《操作系统》进程管理（二）

发表于 分类于

概念

程序：是静态的，存放在磁盘的一系列可执行的指令集合
进程：是动态的，程序加载到内存运行的一次执行过程

组成

  • 进程控制块(PCB): 操作系统用于管理进程所需要的相关信息，通常包含

    • 进程描述信息
      • 进程标识符PID
      • 用户标识符UID
    • 资源相关信息
      • I/O设备使用
      • 文件使用情况
      • 内存分配情况
    • 运行相关信息
      • CPU，磁盘使用，网络流量等）
      • 进程状态信息（就绪态/阻塞态/运行态）
    • 处理机相关信息
      • PSW，PC等寄存器等信息（用于进程切换保留现场）

  • 程序段：用于CPU执行的指令集合，只读

  • 数据段：用户存放程序运行过程中的产生的数据，可读写

特性

  • 动态性
  • 并发性
  • 独立性
  • 异步性
  • 结构性

状态

  • 就绪态：具备运行的条件，等待CPU运行

  • 运行态：正在被CPU执行

  • 阻塞态：请求等待某个事件发生

  • 创建态：操作系统为新进程分配资源，创建PCB

  • 终止态：操作系统回收进程资源，撤销PCB

状态转换

  • 就绪态->运行态：进程被调度

  • 运行态->就绪态：CPU运行时间片到，或CPU被其他更高优先级的进程抢占了

  • 运行态->阻塞态：等待某个事件发生（主动行为）

  • 阻塞态->就绪态：等待的事件被触发（被动行为）

  • 创建态->就绪态：系统完成创建进程的相关工作

  • 运行态->终止态：进程运行结束，或运行遇到不可修复的错误

原语

原语的执行具有原子性，原子性通过开中断指令和关中断指令两个特权指令实现原子性

如果中断信号在关中断指令和开中断指令之间发生，则会推迟到之后

开关中断指令只能在内核进程使用，不能在用户进程使用

进程通信

进程的地址空间是相互独立的，一个进程无法直接访问另一个进程的地址空间，操作系统提供了下面三种通信方式

  • 共享存储: 独立于进程之外的空间，两个进程都能互斥访问
  • 管道通信: 其实是在内存中开辟的一个固定大小的缓冲区
    • 管道只能采用半双工通信（一个时间段只能实现单向传输），如果要实现双向通信，需要2个管道
    • 进程访问管道是互斥的
    • 管道必须写满才能被读，必须读完才能被写
  • 消息传递
    • 直接通信方式：每个进程会有一个消息缓冲队列，用于接受其他进程发送过来的消息
    • 间接通信方式：消息通过信箱集中管理进程的通信

线程

进程也有并发的需求，多进程并发，会有性能差，通信麻烦的问题，所以在进程内部引入线程

  1. 解决进程并发问题
  2. 解决进程切换开销大的问题
  3. 解决进程通信的问题

线程：处理器的调度单位，为进程的执行过程，一个进程可以由多个线程，进程内的线程共享进程的地址空间，资源等

线程实现方式

  • 用户级线程: 用单线程模拟多线程，例如消息循环
    • 不支持多核并行
    • 一个线程阻塞会导致所有线程被阻塞
    • 不需要CPU切换内核态核用户态，效率高
  • 内核级线程: 由操作系统内核支持
    • 并发能力强
    • 需要CPU切换内核态核用户态，开销大

进程的调度

  • 高级调度（作业调度）: 外存 -> 内存
  • 中级调度（内存调度）: 内存 ⇌ 外存
  • 低级调度（进程调度）: 内存 ⇌ CPU

时机

  • 主动放弃
    • 进程正常终止
    • 运行过程发生异常而终止
    • 主动阻塞（如I/O等待）
  • 被动放弃
    • CPU时间片用完
    • 有更紧急的事情要处理（如I/O中断）
    • 有更高优先级的进程进入就绪队列
  • 不能进行线程调度
    • 处理中断过程中
    • 进程在操作系统内核程序临界区中
    • 院子操作过程中

调度

  • 非抢占方式: 由进程主动放弃处理器, 可能CPU会被一个进程一直占用
  • 抢占方式: 可以优先处理更紧急的进程

切换

  1. 保存当前进程现场（保存寄存器）
  2. 恢复即将切换进程现场（恢复寄存器）

临界区

临界资源：一个时间段只允许一个进程使用的资源，进程互斥访问临界资源
临界区：访问临界资源的代码
内核程序临界区：访问某种内核数据结构的代码，如进程的就绪队列，过程中进程不能被调度

优先级调度算法

  • 系统进程优先级高于用户进程
  • 前台进程优先级高于后台进程
  • 操作系统更偏好I/O型进程（可以让I/O进程尽早投入工作，提高资源利用率，系统吞吐量）

优先级分为静态优先级和动态优先级

  • 如果某进程在就绪队列等待了很长时间，则可以适当的提高优先级
  • 如果某进程占用处理机运行了很长事件，则可以适当的降低优先级

进程同步

由于操作系统的并发性，导致不同进程中业务的执行顺序不可预测，为了满足特地执行流程（例如，先进程A读数据要在进程B写数据之后才能继续），就需要使用进程同步的技术，解决异步的问题

临界资源：一个时间段内只允许一个进程使用的资源，进程对于临界资源的访问是互斥的

四个部分

  • 进入区：检查是否可以进入临界区，负责上锁
  • 临界区：访问临界区的代码
  • 退出区：负责解锁
  • 剩余区：其余代码部分

遵循原则

  • 空闲进入
  • 忙则等待
  • 优先等待
  • 让权等待，等待的时候让出CPU

进程互斥软件实现方法

  • 单标志法
  • 双标志先检查法
  • 双标志后检查法
  • Peterson算法

进程互斥的硬件实现

  • 中断屏蔽方法：通过开/关中断指令实现，简单高效，只是用于单处理器，只是用于内核进程
  • TestAndSet指令：检查临界区和上锁的操作为原子操作
  • Swap指令：与TestAndSet指令类似

信号量机制

整型信号量

信号量：一个变量，可以表示系统某种资源的数量

使用wait和signal原语对信号量进行操作，也称为PV操作

1
2
3
4
5
6
7
8
9
10
11
12
13
// 初始化整形信号量S，可用资源为1
int S = 1;

// wait原语，相当于进入区
void wait(int S) {
    while(S <= 0) ;     // 资源不够时，进入忙等待
    S = S - 1;          // 占用资源
}

// signal原语，相当于退出区
void signal(int S) {  
    S = S + 1;          // 释放资源
}

使用资源

1
2
3
4
5
6
7
// P操作
wait(S);

// 使用资源

// V操作
signal(S)

存在问题：不满足让权等待的原则，会出现CPU空转的情况

记录型信号量

解决整形信号量让权等待的问题，通过block和wakeup原语，避免忙等待的情况，提高CPU的利用率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct {
    int value;
    struct process *L;      // 等待队列
} semaphore;

// 原子操作
void wait(semaphore S) {
    S.value--;
    if (S.value < 0) {
        // 没有空闲的资源， 阻塞当前进程进程，并把进程放到等待队列中
        block(S.L);
    }
}

// 原子操作
void signal(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        // 说明有进程在等待，唤醒队列中的进程
        wakeup(S.L);
    }
}

使用信号量解决互斥问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
semaphore mutex = 1;

// 进程P1
P1() {
    ...
    // P操作
    P(mutex);
    临界区代码
    // V操作
    V(mutex)
    ...
}

// 进程P2
P2() {
...
    P(mutex);
    临界区代码
    V(mutex)
    ...
}

使用信号量解决同步问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
semaphore S=0;

P1() {
    代码1;
    代码2;
    // 释放资源
    V(S);
    代码3;
}

P2() {
    // 在代码2执行完成后执行
    P(S);
    代码4;
    代码5;
    代码6;
}

生产者消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
semaphore mutex = 1;        // 互斥信号量
semaphore empty = n;        // 缓冲区大小
semaphore full = 0;         // 产品数量

producer() {
    while(1) {
        // 生产一个产品

        P(empty);       // 消耗一个空闲缓冲区

        P(mutex);
        将产品放入缓冲区
        V(mutex);

        V(full);        // 增加一个产品
    }
}

consumer() {
    while(1) {
        P(full);        // 消耗一个产品

        P(mutex);
        从缓冲区取出一个产品
        V(mutex);

        V(empty)        // 增加一个空闲缓存区

        // 使用产品
    }
}

读者写者问题

读并发，写互斥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
semaphore rw = 1;       // 文件互斥访问
int count = 0;          // 读文件进程个数
semaphore mutex = 1;    // 用户对count互斥
semaphore w = 1;        // 实现当写进程进入的时候，新的读进程进不来，防止写饥饿


writer() {
    while(1) {
        P(w);

        P(rw);
        写文件
        V(rw);

        V(w)
    }
}

reader() {
    while(1) {
        P(w);
        P(mutex);
        if (count == 0) {
            P(rw);
        }
        count++;
        V(mutex);
        V(w);
        读文件

        P(mutex);
        count--;
        if (count == 0) {
            V(rw);              // 没有读操作，释放
        }
        V(mutex);
    }
}

哲学家进餐问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Pi() {
    while(1) {
        P(mutex);
        P(chopstick[i]);        // 拿起左边筷子
        P(chopstick[(i+1)%5]);  // 拿起右边筷子
        V(mutex)

        吃饭

        V(chopstick[i]);        // 放下左边筷子
        V(chopstick[(i+1)%5]);  // 放下右边筷子
    }
}

其他问题

  • 多生产者消费者问题
  • 吸烟者问题

管程

信号量机制存在问题：编写程序困难，易出错，容易发生死锁，管程的引入是为了解决该问题
管程：通过封装同步数据的方法，由编译器实现方法的互斥，从而简单化信号量的使用，对于管程的方法，同一时间只有一个进程能进入方法，如下面JAVA的管程

1
2
3
4
5
6
7
8
static class monitor {
    private Item buffer[] = new Item[N];
    private int count = 0;

    public synchronized void insert(Item item) {
        // 每次只能有一个线程进入，由编译器实现互斥
    }
}

管程其实是利用了封装的思想，把进程同步互斥的逻辑封装到方法里面，通过编译器实现方法的互斥，达到线程同步的目的