操作系统程序员

操作系统基础之进程管理

2017-06-19  本文已影响71人  颜洛滨

进程管理

进程相关的基本概念

进程控制块

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

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

进程控制块的组织形式

进程的控制

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

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

进程的创建

引起进程创建的事件

进程创建过程

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

进程的终止

进程终止事件

进程终止过程

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

进程的阻塞与唤醒

引起阻塞的事件

阻塞过程

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

引起唤醒的事件

唤醒过程

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

进程的挂起与激活

挂起过程

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

激活过程

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

进程同步

进程间的关系

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

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

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

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

信号量机制

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

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

信号量的应用：

管程机制

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

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

管程的组成：

条件变量：管程内部可以根据需要设置多个多个同步变量，如果管程中的进程因为等待条件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中的进程

线程间的同步和通讯

线程的分类

上一篇 下一篇

猜你喜欢

热点阅读