进程管理

进程相关的基本概念

• 进程是多处理程序中作为资源分配和独立运行的基本单位，进程实体由程序段、数据段、PCB三个部分组成，引入进程的目的是为了使进程实体能和其他进程实体并发执行
• 进程的三种基本状态：就绪状态、执行状态、阻塞状态
• 引入线程的目的：使得多个程序能并发执行，以提高资源利用率以及系统吞吐量
• 程序顺序执行的要求
  • 顺序性：程序按照次序逐步执行
  • 封闭性：独占全机资源
  • 可再现性：直接结果不变
• 并发执行的特征
  • 间断性：多个程序相互制约
  • 失去封闭性：多个程序共享资源
  • 不可再现性：执行结果受其他因素干扰
• 进程的特征
  • 结构性：进程由数据段、程序段、PCB构成
  • 动态性：进程可以被动态地创建、执行、撤销
  • 并发性：同一时间内有多个进程在运行
  • 独立性：是独立运行以及获得资源的基本单位
  • 异步性：异步执行

进程控制块

进程控制块是用于描述和控制进程的运行而定义的一个数据结构，系统总是根据PCB来对并发执行的进程进行控制以及管理，也就是系统是根据PCB来感知进程的存在的，PCB是进程存在的唯一标识

进程控制块主要包含以下信息

• 进程标识符：用于唯一标识一个进程
• 处理机状态：主要为处理机的各种寄存器(通用寄存器、指令寄存器、程序状态寄存器、用户栈指针)中的内容
• 进程调度信息：进程状态、进程优先级、进程调度所需要的其他信息、阻塞事件
• 进程控制信息：程序以及数据的地址、进程同步和通信机制、资源清单、链接指针

进程控制块的组织形式

• 线性表方式：所有进程都放在同一个线性表中
  • 优点：简单
  • 缺点：必须扫描整个进程表
  • 应用场景：进程少的系统
• 链接方式：根据线程的状态将其放在不同的链接队列中(执行队列、就绪队列...)
• 索引方式：根据线程的状态，将相同状态的线程在链表中的首地址整理成索引表

进程的控制

进程控制主要的操作为：创建一个新进程、终止一个已经完成的进程、终止一个因其他原因而无法继续执行的进程、进程的状态转换

进程的控制主要由内核的原语来实现，所谓原语就是一连串的操作指令，但是这些指令整体构成一个操作，要么都做，要么都不做，也就是所谓的原子操作

进程的创建

• 使用进程树来描述进程之间的关系
• 子进程可以继承父进程所拥有的资源，撤销子进程时，把从父进程中得到的东西归还给父进程
• 撤销父进程时，也必须同时撤销其所有的子进程

引起进程创建的事件

• 用户登录
• 作业调度
• 提供服务
• 应用请求

进程创建过程

1. 申请空白PCB
2. 为新进程分配资源
3. 初始化进程控制块
4. 将新进程插入就绪队列

进程的终止

进程终止事件

• 正常结束
• 异常结束
  • 越界错误
  • 保护错
  • 非法指令
  • 特权指令错误
  • 运行超时
  • 等待超时
  • 运算错误
  • IO故障
• 外界干扰
  • 操作员或操作系统干预
  • 父进程请求(父进程具有终止任何子进程的权力)
  • 父进程终止

进程终止过程

1. 根据终止进程的标识符，从PCB中检索出该进程的PCB，从中读出进程的状态
2. 若被终止的进程处于执行状态，则立即终止其执行
3. 终止进程的所有子孙进程
4. 回收被终止的进程的全部资源
5. 将被终止的进程从所在队列中移出

进程的阻塞与唤醒

引起阻塞的事件

• 请求系统服务
• 启动某种操作
• 新数据尚未到达
• 无新工作可以做

阻塞过程

1. 保留现场信息
2. 更改线程状态
3. 加入阻塞队列
4. 进程调度

引起唤醒的事件

• 请求的资源准备完成
• 某种操作者完成
• 新数据已经到达
• 有新的工作

唤醒过程

1. 将进程从阻塞队列移出
2. 更改进程状态(静止阻塞 --> 活动阻塞 静止就绪 --> 活动就绪)

进程的挂起与激活

挂起过程

1. 更改进程状态
2. 将数据复制到外存
3. 归还内存

激活过程

1. 重新申请资源
2. 将数据调入内存
3. 恢复线程状态

进程同步

进程间的关系

• 相互合作关系(直接相互约束)
• 资源共享关系(间接相互约束)

进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性

临界资源：同一时刻只能被一个进程使用的资源(硬件资源、软件资源)，临界资源只能使用互斥访问方式，也就是只能一个进程使用完之后才给另一个进程使用

临界区：每个进程中访问临界资源的那段代码称为临界区

临界资源使用的同步原则：

• 空闲让进(提高效率)
• 忙则等待(互斥访问)
• 有限等待(避免死锁)
• 让权等待(放弃占用CPU，避免忙等，浪费资源)

信号量机制

信号量是一种特殊的变量，只有两种基本的原子操作，等待wait(S)，也称为P操作，发信号signal(S)，也称为V操作

信号量是一种有效的进程同步工具，从整型信号量发展到记录型信号量到信号量集

• 整型信号量：用于表示资源数目，除了初始化之外，仅有两个标准的原子操作：wait(S)和signal(S) 也分别称为P、V操作，采用"忙等"
• 记录型信号量：采用让权等待，有一个表示资源数量的value以及一个进程链表L，用于存放所有等待的进程 wait(s) lock(s.L) signal(s) wakeup(s.L)
• AND型信号量：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放，只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给他Swait(s1, s2, s3, ...) Ssignal(s1, s2, s3, ...)
• 信号量集：一次性可以申请一个资源n份 Swait(s1, t1, d1, s2, t2, d2 ...) d为需求值，t为下限值 Ssignal(s1, d1, ...)

信号量的应用：

• 实现进程互斥
• 实现前驱关系(先signal 然后再wait， 这样就能实现wait后面的操作后执行)

管程机制

信号量虽然有效，但是要求每个访问临界资源的进程都自备同步操作，会使得大量的同步操作分散在各个进程中，不便于管理，也容易造成死锁，于是引进了新的进程同步工具管程

管程：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成一个操作系统的资源管理模块

管程的组成：

• 管程的名称
• 局部于管程内部的共享数据结构说明
• 对该数据结构进行操作的一组过程
• 对局部于管程内部的共享数据结构设置初始值的语句

条件变量：管程内部可以根据需要设置多个多个同步变量，如果管程中的进程因为等待条件x，则执行 x.wait，并且加入x队列，将管程控制权交给其他进程，若条件x到达，执行x.signal

经典的进程同步问题

生产者-消费者问题

问题描述

生产者消费者模型描述的是，有一个以上的生产者在生产物品，并将产生的物品放在一个缓冲区中，还有另外一个以上的消费者，消费者从缓冲区中取出物品。这里总共涉及到三个需要同步的地方：缓冲区同时只能被一个进程访问(生产者或者消费者)；当缓冲区满时，生产者不能在往其中放数据，只能等；当缓冲区为空时，消费者不能从中取数据，只能等

伪代码的描述

  var mutex, full, empty:semaphore:= 1, 0, n
  buffer: array[0, ..., n-1]:=item
  in, out:int = 0, 0

  procedure producer:
  begin
    repeat
      生产一个产品 item
      wait(empty);
      wait(mutex);
      buffer(in) = item;
      in: = (in + 1) mod n;
      signal(mutex);
      signal(full);
    until false;
  end

  procedure customer:
  begin 
    repeat 
      wait(full);
      wait(mutex);
      item = buffer(out);
      out:= (out + 1) mod n;
      signal(mutext);
      signal(empty);
    until false;
  end

这里需要注意的是，必须先获得空余/有物品之后再看时候能进入缓冲区，反之会造成死锁，原因如下：以生产者为例，先获得缓冲区访问权，然后查看缓冲区是否满，此时如果缓冲区已满，则生产者会阻塞，但此时生产者已经获得了缓冲区的访问权，所以其他的进程均无法获得缓冲区的访问权，进而无法进行消费(消费者)，所以造成了死锁

生产者消费者具体实现

基于信号量的实现

package cn.xuhuanfeng.cs;

import java.util.concurrent.Semaphore;

/**
 * Created by Huanfeng.Xu on 2017-06-19.
 *
 * 使用记录型信号量来实现生产者消费者模型
 */
public class Exp1 {
    public static void main(String[] args) {
        Buf buf = new Buf();
        Thread producer = new Thread(new Producer(buf));
        Thread customer = new Thread(new Customer(buf));

        producer.start();
        customer.start();
    }
}


/**
 * 生产者
 */
class Producer implements Runnable{

    private Buf buf;

    public Producer(Buf buf) {
        this.buf = buf;
    }

    @Override
    public void run() {
         int num = 0;
        while (true){
            try {
                buf.add(num);
                System.out.printf("Produce item %d\n", num++);
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

/**
 * 消费者
 */
class Customer implements Runnable{

    private Buf buf;

    public Customer(Buf buf) {
        this.buf = buf;
    }

    @Override
    public void run() {
        while (true){
            try {
                int item = buf.get();
                System.out.printf("Get item %d\n", item);
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

/**
 * 缓冲区，生成者将产生的数据放在这里，消费者从这里获取数据
 */
class Buf{

    private final int SIZE = 10;
    /*
    使用concurrent包所提供的信号量机制
    */
    private final Semaphore MUTEX = new Semaphore(1);
    private final Semaphore FULL = new Semaphore(0);
    private final Semaphore EMPTY = new Semaphore(SIZE);
    private int[] data = new int[SIZE];
    private int in, out;

    public Buf() {
        in = 0;
        out = 0;
    }

    public void add(int item) throws InterruptedException {

        /*
        请求资源
         */
        EMPTY.acquire();
        MUTEX.acquire();

        data[in++] = item;
        in %= SIZE;

        /*
        释放资源
         */
        MUTEX.release();
        FULL.release();
    }

    public int get() throws InterruptedException {

        FULL.acquire();
        MUTEX.acquire();

        int item = data[out++];

        out %= SIZE;

        MUTEX.release();
        EMPTY.release();

        return item;
    }

}

基于信号的管程实现

这里需要注意的是，上面的实现方式并不是管程，而只是普通的使用信号量而已，只不过我们把具体操作都封装起来了，但是本质上不是管程，原因是管程同时只能有一个进程进程访问，但是上面的内容中，其实是可以有多个进程同时进行get()、add()操作的，下面的代码展示了使用信号来实现，这种方式理论上属于管程。

/**
 * 基于管程实现的缓冲区
 * 使用synchronized来进行同步操作，保证同时只有
 * 一个进程在访问
 */
class Buf{

    private final int SIZE = 10;
    private int[] data = new int[SIZE];
    private int in;
    private int out;
    private int count;

    public Buf() {
        in = 0;
        out = 0;
        count = 0;
    }

    public synchronized void add(int item) throws InterruptedException {

        /*
        当发现缓冲区已经满的时候，挂起生产者进程
         */
        while (count == SIZE){
            wait();
        }

        data[in++] = item;
        count++;
        in %= SIZE;
        /*
        放入物品之后，通知消费者缓冲区已经有物品
         */
        notifyAll();
    }

    public synchronized int get() throws InterruptedException {

        /*
        当发现缓冲区没有物品时，挂起消费者进程
         */
        while (count == 0){
            wait();
        }

        int item = data[out++];
        count--;
        out %= SIZE;

        // 取出数据之后，通知生产者缓冲区有空
        notifyAll();
        return item;
    }
}

读者-写者问题

问题描述

读者-写者问题是另外一个经典的同步问题，问题如下：有多个读者以及至少一个写者，多个读者可以同时读取文件，但是写者与写者、写者与读者之间必须进行同步(很显然的嘛，一旦出现了写者，就必须进行同步处理了)

伪代码描述

var rmutex,wmutex:semaphore:=1,1
readcount int:=0

procedure write:
  begin
    repeat
      wait(wmutex);
      write
      signal(wmutex);
    until false;
  end

procedure read:
  begin
    repeat
      wait(rmutex);
        if(readcount == 0) then
          wait(wmutex);
        fi  
        readcount:= readcount + 1
      signal(rmutex);
      read

      wait(rmutex)
        readcount:=readcount - 1;
        if(readcount == 0) then
          signal(wmutex);
        fi
      signal(rmutex);
    until false;
  end
        

处理的方式非常灵活，使用readcount用于对读者数量进行计数，如果是第一个读者，则对wmutex进行加锁，防止此时写者进行操作，如果是最后一个读者，则将wmutex进行解锁，表示此时已经没有任何读者在进行读操作，写者可以进行写操作，同时，由于对readcount进行操作本身必须进行同步(多个读者会对其进行修改)，所以必须对readcount进行加锁处理

具体实现

package cn.xuhuanfeng.cs;

import java.util.concurrent.Semaphore;

/**
 * Created by Huanfeng.Xu on 2017-06-19.
 * 读者-写者问题的实现
 */
public class Reader_Writer {

    private int data;
    private final Semaphore W_MUTEX = new Semaphore(1);
    private final Semaphore R_MUTEX = new Semaphore(1);
    private int readerCount = 0;

    class Reader implements Runnable{

        @Override
        public void run() {

            while (true){

                try {
                    // 获得更改readerCount的权限
                   R_MUTEX.acquire();
                   if (readerCount == 0){
                       // 对数据区进行加锁
                       W_MUTEX.acquire();
                   }
                   readerCount ++;
                   // 释放对readerCount操作的权限
                   R_MUTEX.release();

                   System.out.printf("Data is : %d\n", data);

                   // 同上
                   R_MUTEX.acquire();
                   readerCount--;
                   if (readerCount == 0){
                       // 释放数据区的锁
                       W_MUTEX.release();
                   }
                   R_MUTEX.release();

                   Thread.sleep(300);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    class Writer implements Runnable{

        @Override
        public void run() {
            int cnt = 0;
            while (true){
                try {
                    W_MUTEX.acquire();
                    data = ++cnt;
                    W_MUTEX.release();
                    System.out.println("--------------Update-----------------");
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

哲学家进餐问题

关于哲学家进餐问题的背景这里就不进行介绍了

哲学家进餐问题基本的解决方案同上面，不过需要注意的是，需要保证哲学家们不会都拿同一个方向的筷子，所以可以让编号是奇数的哲学家先拿左边的筷子，再拿右边的筷子，编号是偶数的哲学家，先拿右边的筷子，再拿左边的筷子，这样可以有效地避免死锁问题，导致哲学家饿死。

进程通信

进程通信指的是进程之间的信息交换

信号量作为通信机制的缺点

• 效率低下
• 通信对用户不透明
• 属于一种低级通信

进程通信的类型

• 共享存储器系统(无格式)
  • 基于共享数据结构的通信(低效)
  • 基于共享存储区的通信(高效)
• 消息传递系统(有格式)
  • 直接通信：直接发送给用户
  • 间接通信：将消息发送到"邮箱"，然后用户从邮箱中取出自己所要的消息
• 管道通信(单向通信)

线程

引入线程的目的：减少程序并发执行时所付出的时空开销，使OS具有更好的并发性，原因在于，进程在创建、调度、撤销时的开销大

线程与进程的比较

• 调度：线程作为调度和分派的基本单位，进程作为拥有资源的基本单位
• 并发性：进程中的多个线程之间同样可以并发执行，并且同个进程之间的线程进行切换时，不会引起进程的切换
• 拥有资源：进程是系统中拥有资源的基本单位，线程一般不拥有系统资源，但是可以访问其隶属的进程的资源
• 系统开销：开销更小，切换线程时，不需要进行过多的环境保存，撤销时，不需要进行过多的资源回收

线程的属性

在多线程os中，一个进程通常包含多个线程，线程作为利用CPU的基本单位，是花费最小的实体

• 轻型实体：只含有必须的少量资源
• 作为调度和分派的基本单位：切换速度快并且开销小
• 可并发执行
• 共享进程资源：所有线程都具有相同的地址空间(进程的地址空间)

线程的状态

os中的每一个线程都可以用线程标识符以及一组状态参数进行描述

• 状态参数：
  • 寄存器状态
  • 堆栈
  • 线程运行状态
    • 执行状态
    • 就绪状态
    • 阻塞状态
  • 优先级
  • 线程专有存储器
  • 信号屏蔽

线程的创建以及终止

程序启动时，一般只有一个主线程，然后再由主线程根据需要启动其他线程

多线程os中的进程

• 作为系统资源分配的单位
• 包含多个线程
• 进程不再是可执行的实体

线程间的同步和通讯

• 互斥锁：用于实现线程间对资源互斥访问的机制
• 条件变量：每个条件变量一般与一个互斥锁一起使用
• 信号量机制
  • 私用信号量
  • 公用信号量

线程的分类

• 内核支持线程：线程的处理均由内核实现，内核为线程保留TCB，并且通过TCB感知线程
• 用户级线程：线程的信息处理不通过内核，状态保留在用户空间中，内核不能感知用户级线程