Geekerstar

计算机操作系统核心知识总结(二)进程管理
目录计算机操作系统核心知识总结(一)概述计算机操作系统核心知识总结(二)进程管理计算机操作系统核心知识总结(三)死...
扫描右侧二维码阅读全文
01
2018/03

计算机操作系统核心知识总结(二)进程管理

目录

计算机操作系统核心知识总结(一)概述

计算机操作系统核心知识总结(二)进程管理

计算机操作系统核心知识总结(三)死锁

计算机操作系统核心知识总结(四)存储器管理

计算机操作系统核心知识总结(五)设备管理


进程与线程

1. 进程

进程是操作系统进行资源分配的基本单位。

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

2. 线程

一个进程中可以有多个线程,线程是独立调度的基本单位。同一个进程中的多个线程之间可以并发执行,它们共享进程资源。

3. 区别

  • 拥有资源:进程是资源分配的基本单位,但是线程不拥有资源,线程可以访问率属进程的资源。
  • 调度:线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换,从一个进程内的线程切换到另一个进程中的线程时,会引起进程切换。
  • 系统开销:由于创建或撤销进程时,系统都要为之分配或回收资源,如内存空间、I/O 设备等,因此操作系统所付出的开销远大于创建或撤销线程时的开销。类似地,在进行进程切换时,涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置。而线程切换时只需保存和设置少量寄存器内容,开销很小。
  • 通信方面:进程间通信 (IPC) 需要进程同步和互斥手段的辅助,以保证数据的一致性,而线程间可以通过直接读/写同一进程中的数据段(如全局变量)来进行通信。

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

进程状态的切换

进程状态的切换.jpg

阻塞状态是缺少需要的资源从而由运行状态转换而来,但是该资源不包括 CPU,缺少 CPU 会让进程从运行态转换为就绪态。

只有就绪态和运行态可以相互转换,其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间,转为运行状态;而运行状态的进程,在分配给它的 CPU 时间片用完之后就会转为就绪状态,等待下一次调度。

调度算法

需要针对不同环境来讨论调度算法。

1. 批处理系统中的调度

1.1 先来先服务

first-come first-serverd(FCFS)。

调度最先进入就绪队列的作业。

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

1.2 短作业优先

shortest job first(SJF)。

调度估计运行时间最短的作业。

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

1.3 最短剩余时间优先

shortest remaining time next(SRTN)。

2. 交互式系统中的调度

2.1 优先权优先

除了可以手动赋予优先权之外,还可以把响应比作为优先权,这种调度方式叫做高响应比优先调度算法。

响应比 = (等待时间 + 要求服务时间) / 要求服务时间 = 响应时间 / 要求服务时间

这种调度算法主要是为了解决 SJF 中长作业可能会饿死的问题,因为随着等待时间的增长,响应比也会越来越高。

2.2 时间片轮转

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

时间片轮转算法的效率和时间片的大小有很大关系。因为每次进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,进程切换太频繁,在进程切换上就会花过多时间。

2.3 多级反馈队列

多级反馈队列.jpg

  1. 设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同,在优先权越高的队列中,为每个进程所规定的执行时间片就越小。
  2. 当一个新进程进入内存后,首先将它放入第一队列的末尾,按 FCFS 原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入下一个队列的队尾。
  3. 仅当前 i -1 个队列均空时,才会调度第 i 个队列中的进程。

优点:实时性好,同时适合运行短作业和长作业。

2.4 短进程优先

3. 实时系统中的调度

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

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

进程同步

1. 临界区

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

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

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

2. 同步与互斥

同步指多个进程按一定顺序执行;互斥指多个进程在同一时刻只有一个进程能进入临界区。

同步是在对临界区互斥访问的基础上,通过其它机制来实现有序访问的。

3. 信号量

信号量(Samaphore) 是一个整型变量,可以对其执行 down 和 up 操作,也就是常见的 P 和 V 操作。

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

down 和 up 操作需要被设计成原语,不可分割,通常的做法是在执行这些操作的时候屏蔽中断。

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

typedef int samaphore;
samaphore mutex = 1;
void P1() {
    down(mutex);
    // 临界区
    up(mutex);
}

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

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

使用一个互斥量 mutex 来对临界资源进行访问;empty 记录空缓冲区的数量,full 记录满缓冲区的数量。

注意,必须先执行 down 操作再用互斥量对临界区加锁,否则会出现死锁。因为如果都先对临界区加锁,然后再执行 down 操作,那么可能会出现这种情况:生产者对临界区加锁后,执行 down(empty) 操作,发现 empty = 0,此时生成者睡眠。消费者此时不能进入临界区,因为生产者对临界区加锁了,也就无法执行 up(empty) 操作,那么生产者和消费者就会一直等待下去。

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

void producer() {
    while(TRUE){
        int item = produce_item;
        down(empty);
        down(mutex);
        insert_item(item);
        up(mutex);
        up(full);
    }
}

void consumer() {
    while(TRUE){
        down(full);
        down(mutex);
        int item = remove_item(item);
        up(mutex);
        up(empty);
        consume_item(item);
    }
}

4. 管程

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

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 ten 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. 管道

管道是单向的、先进先出的、无结构的、固定大小的字节流,它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据,读进程在管道的首端读出数据。数据读出后将从管道中移走,其它读进程都不能再读到这些数据。

管道提供了简单的流控制机制,进程试图读空管道时,在有数据写入管道前,进程将一直阻塞。同样地,管道已经满时,进程再试图写管道,在其它进程从管道中移走数据之前,写进程将一直阻塞。

Linux 中管道是通过空文件来实现。

管道有三种:

  1. 普通管道:有两个限制:一是只支持半双工通信方式,即只能单向传输;二是只能在父子进程之间使用;
  2. 流管道:去除第一个限制,支持双向传输;
  3. 命名管道:去除第二个限制,可以在不相关进程之间进行通信。

2. 信号量

信号量是一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,防止某进程正在访问共享资源时,其它进程也访问该资源。因此,主要作为进程间以及同一进程内不同线程之间的同步手段。

3. 消息队列

消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

4. 信号

信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生。

5. 共享内存

共享内存就是映射一段能被其它进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问。共享内存是最快的 IPC 方式,它是针对其它 IPC 运行效率低而专门设计的。它往往与其它通信机制(如信号量)配合使用,来实现进程间的同步和通信。

6. 套接字

套接字也是一种进程间通信机制,与其它通信机制不同的是,它可用于不同机器间的进程通信。

经典同步问题

生产者和消费者问题前面已经讨论过。

1. 读者-写者问题

允许多个进程同时对数据进行读操作,但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量,一个互斥量 count_mutex 用于对 count 加锁,一个互斥量 data_mutex 用于对读写的数据加锁。

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        down(count_mutex);
        count++;
        if(count == 1) down(data_mutex); // 第一个读者需要对数据进行加锁,防止写进程访问
        up(count_mutex);
        read();
        down(count_mutex);
        count--;
        if(count == 0) up(data_mutex);
        up(count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(data_mutex);
        write();
        up(data_mutex);
    }
}

2. 哲学家进餐问题

哲学家问题.jpg

五个哲学家围着一张圆周,每个哲学家面前放着饭。哲学家的生活有两种交替活动:吃饭以及思考。当一个哲学家吃饭时,需要先一根一根拿起左右两边的筷子。

下面是一种错误的解法,考虑到如果每个哲学家同时拿起左手边的筷子,那么就无法拿起右手边的筷子,造成死锁。

#define N 5
#define LEFT (i + N - 1) % N
#define RIGHT (i + N) % N
typedef int semaphore;
semaphore chopstick[N];

void philosopher(int i) {
    while(TURE){
        think();
        down(chopstick[LEFT[i]]);
        down(chopstick[RIGHT[i]]);
        eat();
        up(chopstick[RIGHT[i]]);
        up(chopstick[LEFT[i]]);
    }
}

为了防止死锁的发生,可以加一点限制,只允许同时拿起左右两边的筷子,方法是引入一个互斥量,对拿起两个筷子的那段代码加锁。

semaphore mutex = 1;

void philosopher(int i) {
    while(TURE){
        think();
        down(mutex);
        down(chopstick[LEFT[i]]);
        down(chopstick[RIGHT[i]]);
        up(mutex);
        eat();
        down(mutex);
        up(chopstick[RIGHT[i]]);
        up(chopstick[LEFT[i]]);
        up(mutex);
    }
}

上一章:计算机操作系统核心知识总结(一)概述
下一章:计算机操作系统核心知识总结(三)死锁


最后修改:2018 年 03 月 03 日 11 : 23 AM
如果觉得我的文章对你有用,请随意赞赏

发表评论