进程

进程与线程

进程

进程是资源分配的基本单位。

进程控制块(Process Control Block,PCB)描述进程的基本信息和运行状态,所谓的创建进程和撤销进程,都是指对PCB的操作。

下图显示了4个程序创建了4个进程,这4个进程可以并发的执行。

线程

线程是独立调度的基本单位。

一个进程中可以有多个线程,他们共享进程资源。

QQ 和浏览器是两个进程,浏览器进程里面有很多线程,例如 HTTP 请求线程、事件响应线程、渲染线程等等,线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时,浏览器还可以响应用户的其它事件。

区别

  1. 拥有资源

进程是资源分配的基本单位,但是线程不拥有资源,线程可以访问隶属进程的资源。

  1. 调度

线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换,从一个进程中的线程切换到另一个进程中的线程时,会引起进程切换。

  1. 系统开销

由于创建和撤销进程时,系统都要为之分配或回收资源,如内存空间、I/O设备等,所付出的开销远大于创建和撤销线程时的开销。类似的,在进行进程切换时,涉及到当前执行进程的CPU环境的保存以及新调度进程CPU环境的设置,而线程切换时,只需保存和设置少量的寄存器内容,开销很小。

  1. 通信方面

线程间可通过直接读写同一进程中的数据进行通信,但是进程通信需要借助IPC。

进程间状态的切换

scheduler dispatch:调度器调度

terminated:终止

  • 就绪状态(ready):等待被调度
  • 运行状态(running)
  • 阻塞状态(waiting):等待资源

应注意以下内容:

  • 只有就绪态和运行态可以互相转换,其他的都是单向转换。就绪状态的进程通过调度算法从而获得CPU时间,转为运行状态;而运行状态的进程,在CPU给他分配的时间片用完之后就会转为就绪状态,等待下一次的调度。
  • 阻塞状态是缺少需要的资源而从运行状态转换而来,但是该资源不包括CPU时间,缺少CPU时间会从运行态转为就绪态。

进程调度算法

批处理系统

批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量和周转时间(从提交到终止的时间)

  1. 先来先服务 first-com first-serverd(FCFS)

非抢占式的调度算法,按请求顺序进行调度。

有利于长作业,但不利于短作业,因为短作业必须一直等待前面长作业执行完毕才能执行,而长作业又需要执行很长时间,造成短作业等待时间过长。

  1. 短作业优先 shortest job first(SJF)

非抢占式的调度算法,按估计运行时间最短的顺序进行调度。

长作业有可能被饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。

  1. 最短剩余时间优先 shortes remaining time next(SRTN)

最短作业优先的抢占式版本,按剩余时间的顺序进行调度。

当一个新作业到达时,其整个运行时间与当前进程的剩余时间作比较,如果新进程需要的时间更少,则挂起当前进程,运行新进程,否则新进程等待。

交互式系统

交互式系统有大量的用户交互操作,在该系统中调度算法的目标是快速进行响应。

  1. 时间片轮转

将所有就绪进程按FCFS的原则排成一个队列,每次调度时,把CPU时间分配给队首进程,该进程可以执行一个时间片,当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时把CPU时间分配给队首进程。

时间片轮转算法的效率和时间片的大小有很大关系:

  • 因为进程的切换需要保存进程的信息并且载入新进程信息,如果时间片太小,会导致进程切换的太频繁,在进程切换上就会花过多时间。
  • 而时间片太长,那么实时性就得不到保障。

  1. 优先级调度

为每个进程分配优先级,按优先级进行调度。

为了防止低优先级的进程得不到调度,可以随时间的推移增加等待进程的优先级。

  1. 多级反馈队列

一个进程需要执行100个时间片,如果采用时间片轮转调度算法,需要交换100次。

多级队列是为了这种需要执行多个时间片的进程考虑,它设置了多个队列,每个队列的大小都不同,例如1,2,4,8,…。进程在第一个队列没执行完(用完当前队列设置的时间片后),就会被移到下一个队列。这种方式下,之间的进程只需要切换7次。

每个队列的优先级也不同,最上面的优先级最高。因此只有上一个队列中没有等待(就绪)进程在排队,才能调度

当前队列上的进程。

可将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时,前者必须满足绝对的截止时间,后者可以容忍一定的超时。

进程同步

临界资源

各进程采取互斥的方式,实现共享的资源称作临界资源。属于临界资源的硬件有打印机、磁带机等,软件有消息缓冲队列、变量、[数组、缓冲区等。 诸进程间应采取互斥方式,实现对这种资源的共享。

临界区

对临界资源进行访问的那段代码叫做临界区。

为了互斥访问临界资源,每个进程进入临界区前,需先进行检查。

// entry section
// critical section;
// exit section

同步与互斥

  • 同步:多个进程因为合作产生的直接制约关系,使得进程有一定的先后执行关系。
  • 互斥:多个进程在同一时刻只有一个进程能进入临界区。

信号量

在系统中,给予每一个进程一个信号量,代表每个进程目前的状态,未得到控制权的进程会在特定地方被强迫停下来,等待可以继续进行的信号到来。如果信号量是一个任意的整数,通常被称为计数信号量(Counting semaphore),或一般信号量(general semaphore);如果信号量只有二进制的0或1,称为二进制信号量(binary semaphore)。在linux系统中,二进制信号量(binary semaphore)又称互斥锁(Mutex)。

  • down:如果信号量大于0,执行-1操作,如果信号量等于0,进程睡眠,等待信号量大于0;
  • up:对信号量执行+1操作,唤醒睡眠的进程让其完成 down 操作。

如果信号量的取值只能为0或1,那么就成为了互斥量(Mutex)也是二进制信号量,0表示临界区已加锁,1表示临界区已解锁。

P(Semaphore s){
    while(S==0)     //wait until s=0
        S = S - 1;
}
V(Semaphore s){
    S = S + 1;
}
typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

使用信号量实现生产者-消费者问题

问题描述:使用给一个缓存区来存放物品,只有当缓存区没有满时,生产者才可以放入物品;只有当缓存区不为空时,消费者才可以拿走物品。

因为缓存区属于临界资源,因此需要使用一个互斥量 mutex 来控制对缓存区的互斥访问。

为了同步生产者和消费者的行为,需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计,这里需要使用两个信号量:empty 记录空缓冲区的数量,full 记录满缓冲区的数量。其中,empty 信号量是在生产者进程中使用,当 empty 不为 0 时,生产者才可以放入物品;full 信号量是在消费者进程中使用,当 full 信号量不为 0 时,消费者才可以取走物品。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer(){
    int item = produce_item();
    down(empty);
    down(mutex);
    insert_item(item);
    up(full);
    up(mutex);
}
void consumer(){
    down(full);
    down(mutex);
    int item = remove_item();
    consumer_item(item);
    up(empty);
    up(mutex);
}

管程

管程可以看做一个软件模块,它是将共享的变量和对于这些共享变量的操作封装起来,形成一个具有一定接口的功能模块,进程可以调用管程来实现进程级别的并发控制

在管程入口处的等待队列称为入口等待队列,由于进程会执行唤醒操作,因此可能有多个等待使用管程的队列,这样的队列称为紧急队列,它的优先级高于等待队列。

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制,而管程把控制的代码独立出来,不仅不容易出错,也使得客户端代码调用更容易。

c 语言不支持管程,下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法,客户端代码通过调用这两个方法来解决生产者-消费者问题。

monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

管程有一个重要特性:在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程,否则其它进程永远不能使用管程。

管程引入了 条件变量 以及相关的操作:wait()signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞,把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

经典同步问题

哲学家进餐问题

哲学家进餐问题描述有五个哲学家,他们的生活方式是交替地进行思考和进餐,哲学家们共用一张圆桌,分别坐在周围的五张椅子上,在圆桌上有五个碗和五支筷子,平时哲学家进行思考,饥饿时便试图取其左、右最靠近他的筷子,只有在他拿到两支筷子时才能进餐,该哲学家进餐完毕后,放下左右两只筷子又继续思考。

约束条件

(1)只有拿到两只筷子时,哲学家才能吃饭。

(2)如果筷子已被别人拿走,则必须等别人吃完之后才能拿到筷子。

(3)任一哲学家在自己未拿到两只筷子吃完饭前,不会放下手中已经拿到的筷子。

分析

因为是五位哲学家,并且每位哲学家的各自做自己的事情(思考和吃饭),因此可以创建五个线程表示五位哲学家,五个线程相互独立(异步)。并对五位哲学家分别编号为0~4

有五根筷子,每根筷子只对其相邻的两位哲学家是共享的,因此这五根筷子可以看做是五种不同的临界资源

因为筷子是临界资源,因此当一个线程在使用某根筷子的时候,应该给这根筷子加锁,使其不能被其他进程使用。

为了防止死锁,提供以下解决方案

解决方案

设置一个全局互斥量mutex,用来锁住全部的临界资源,当一个哲学家企图拿筷子的时候,就将所有的资源锁住,然后让他去拿他需要的筷子,等他取到他需要的筷子之后,就解锁,然后让其他哲学家取筷子。

semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int i)
{
    while(true)
    {
        /* 这个过程中可能只能由一个人在吃饭 */
        think();
        wait(mutex); // 保护信号量
        wait(chopstick[(i+1)%5]); // 请求右手边的筷子
        wait(chopstick[i]); // 请求左手边的筷子
        signal(mutex); // 释放保护信号量
        eat();
        signal(chopstick[(i+1)%5]); // 释放右手边的筷子
        signal(chopstick[i]); // 释放左手边的筷子
    }
} 

 代码实现

public class ThreadTest{
    public static void main(String[] args) {
        Fork fork = new Fork();
        new Philosopher("0", fork).start();
        new Philosopher("1", fork).start();
        new Philosopher("2", fork).start();
        new Philosopher("3", fork).start();
        new Philosopher("4", fork).start();
    }

}
class Philosopher extends Thread{
    private String name;
    private Fork fork;

    public Philosopher(String name, Fork fork) {
        super(name);
        this.name = name;
        this.fork = fork;
    }

    @Override
    public void run() {
        while (true){
            thinking();
            fork.takeFork();
            eating();
            fork.putFork();
        }

    }

    public void eating(){
        System.out.println("I am Eating:"+name);
        try {
            sleep(1000);//模拟吃饭,占用一段时间资源
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    public void thinking(){
        System.out.println("I am Thinking:"+name);
        try {
            sleep(1000);//模拟思考
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    public Fork getFork() {
        return fork;
    }

    public void setFork(Fork fork) {
        this.fork = fork;
    }
}
class Fork{
    /*5只筷子,初始为都未被用*/
    private boolean[] used={false,false,false,false,false,false};
    public synchronized void takeFork(){
        String name = Thread.currentThread().getName();
        int i = Integer.parseInt(name);
        while(used[i]||used[(i+1)%5]){
            try {
                wait();//如果左右手有一只正被使用,等待
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        used[i ]= true;
        used[(i+1)%5]=true;
    }

    public synchronized void putFork(){
        String name = Thread.currentThread().getName();
        int i = Integer.parseInt(name);
        used[i]= false;
        used[(i+1)%5]=false;
        notifyAll();//唤醒其他线程
    }
}

读写者问题

有读者和写者两组并发进程,共享一个文件,当两个或以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:

  • 允许多个读者可以同时对文件执行读操作;
  • 只允许一个写者往文件中写信息;
  • 任一写者在完成写操作之前不允许其他读者或写者工作;
  • 写者执行写操作前,应让已有的读者和写者全部退出。

读者优先

读者和写者是互斥的,写者和写者也是互斥的,而读者和读者不存在互斥问题。

两个进程,即读者和写者。写者是比较简单的,它和任何进程互斥,用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂,它必须实现与写者互斥的同时还要实现与其他读者的同步,因此,仅仅简单的一对P操作、V操作是无法解决的。那么,在这里用到了一个计数器,用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的,此时读者会一直占用文件,当没有读者的时候写者才可以写文件。同时这里不同读者对计数器的访问也应该是互斥的。

信号量设置。首先设置信号量count为计数器,用来记录当前读者数量,初值为0; 设置mutex为互斥信号量,用于保护更新count变量时的互斥;设置互斥信号量rw用于保证读者和写者的互斥访问。

int count=0;  //用于记录当前的读者数量
semaphore mutex=1;  //用于保护更新count变量时的互斥
semaphore rw=1;  //用于保证读者和写者互斥地访问文件
writer () {  //写者进程
    while (1){
        P(rw); // 互斥访问共享文件
        Writing;  //写入
        V(rw) ;  //释放共享文件
    }
}

reader () {  // 读者进程
    while(1){
        P (mutex) ;  //互斥访问count变量
        if (count==0)  //当第一个读进程读共享文件时
            P(rw);  //阻止写进程写
        count++;  //读者计数器加1
        V (mutex) ;  //释放互斥变量count
        reading;  //读取
        P (mutex) ;  //互斥访问count变量
        count--; //读者计数器减1
        if (count==0)  //当最后一个读进程读完共享文件
            V(rw) ;  //允许写进程写
        V (mutex) ;  //释放互斥变量 count
    }
}

进程通信

进程同步与进程通信很容易混淆,它们的区别在于:

  • 进程同步:控制多个进程按一定顺序执行;
  • 进程通信:进程间传输信息。

进程通信是一种手段,而进程同步是一种目的。也可以说,为了能够达到进程同步的目的,需要让进程进行通信,传输一些进程同步所需要的信息。

管道

管道是一种最基本的进程间通信机制。管道由pipe函数来创建:

#include <unistd.h>
int pipe(int fd[2]);

调用pipe函数,会在内核中开辟出一块缓冲区用来进行进程间通信,这块缓冲区称为管道,它有一个读端和一个写端。

pipe函数接受一个参数,是包含两个整数的数组,如果调用成功,会通过pipefd[2]传出给用户程序两个文件描述符,需要注意pipefd [0]指向管道的读端, pipefd [1]指向管道的写端,那么此时这个管道对于用户程序就是一个文件,可以通过read(pipefd [0]);或者write(pipefd [1])进行操作。pipe函数调用成功返回0,否则返回-1..

那么再来看看通过管道进行通信的步骤:

  • 父进程创建管道,得到两个文件描述符指向管道的两端

  • 利用fork函数创建出子进程,则子进程也得到两个文件描述符指向同一管道

  • 父进程关闭读端(pipe[0]),子进程关闭写端pipe[1],则此时父进程可以往管道中进行写操作,子进程可以从管道中读,从而实现了通过管道的进程间通信。

它具有以下特点:

  • 只支持半双工通信(单向交替传输);

  • 只能在父子进程或者兄弟进程中使用。(只能血缘关系的进程进行通信)

  • 依赖于文件系统

  • 生命周期随进程

  • 面向字节流的服务

  • 管道内部提供了同步机制

说明:因为管道通信是单向的,在上面的例子中我们是通过子进程写父进程来读,如果想要同时父进程写而子进程来读,就需要再打开另外的管道;

管道的读写端通过打开的文件描述符来传递,因此要通信的两个进程必须从它们的公共祖先那里继承管道的件描述符。 上面的例子是父进程把文件描述符传给子进程之后父子进程之 间通信,也可以父进程fork两次,把文件描述符传给两个子进程,然后两个子进程之间通信, 总之 需要通过fork传递文件描述符使两个进程都能访问同一管道,它们才能通信。

FIFO

也称为命名管道,去除了管道只能在父子进程中使用的限制。

#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

FIFO 常用于客户-服务器应用程序中,FIFO 用作汇聚点,在客户进程和服务器进程之间传递数据。

消息队列

消息队列(System V IPC)实际上是操作系统在内核为我们创建的一个队列,通过这个队列的标识符key,每一个进程都可以打开这个队列,每个进程都可以通过这个队列向这个队列中插入一个结点或者获取一个结点来完成不同进程间的通信。
如何传输数据:
用户组织一个带有类型的数据块,添加到队列中,其他的进程从队列中获取数据块,即消息队列发送的是一个带有类型的数据块;消息队列是一个全双工通信,可读可写(可以发送数据,也可以接受数据)
消息队列生命周期随内核,如果没有释放消息队列或者没有关闭操作系统,消息队列会一直存在。

相比于 FIFO,消息队列具有以下优点:

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

信号量

它是一个计数器,用于为多个进程提供对共享数据对象的访问。

共享存储

一般数据操作过程把数据从用户态拷贝到内核态,用的时候,再将内核态拷贝到用户态,但共享内存不需要这两步,对虚拟地址空间的操作也就是操作了物理内存,那么另一个虚拟地址空间也可以有这个数据,即不需要拷贝。
因为共享内存直接申请一块物理内存通过页表映射到虚拟地址空间中,操作虚拟地址空间,其实是操作同一块物理内存区域,因此进行数据传输时相较于其他通信方 式,少了两步用户态与内核态数据拷贝的过程,因此共享内存是最快的进程间通信方式。

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制,所以这是最快的一种 IPC。

需要使用信号量用来同步对共享存储的访问。

多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件,而是使用内存的匿名段。

共享内存使用步骤:

  1. 创建共享内存
  2. 将共享内存映射到虚拟地址空间
  3. 内存的数据操作(数据拷贝)
  4. 解除映射,删除共享内存(如果有进程依然与共享内存保持映射连接关系,那么共享内存将不会被立即删 除,而是等最后一个映射断开后删除,在这期间,将拒绝其他进程映射)

发表评论

电子邮件地址不会被公开。 必填项已用*标注