操作系统之进程

[TOC]

Introduction

本节总结了操作系统的相关概念，操作系统的知识点基本上是围绕着进程展开。

进程

进程的概念与特征

• 进程是程序的一次执行
• 进程是一个程序及数据在处理机上顺序执行时所发生的活动
• 进程是系统进行资源分配和调度的一个独立单位。进程的独立运行由进程控制块（PCB）控制和管理。程序段、相关数据、PCB三部分构成了进程映像。进程映像是静态的进程。

进程具有动态性（有着创建、活动、暂停、终止等过程，具有生命周期）、并发性（多个进程在一段时间内同时运行）、独立性（进程是一个独立运行、获得资源和接收调度的基本单位）、异步性（进程按照独自的、不可预知的速度前进）、结构性（每个进程都有一个PCB对其描述）

进程的状态

• 运行状态：进程在处理机上运行

• 就绪状态：进程已处于准备运行的状态，即进程获得了除处理机以外的一切所需资源，只需得到处理机即可执行

• 阻塞状态（等待/封锁状态）：进程正在等待某一事件而暂停运行。特点是即使处理机空闲也不能运行

• 创建状态：进程正在创建尚未转到就绪状态。创建进程通常需要经过几个步骤：申请空白PCB、向PCB写入控制和管理进程的信息，然后为该进程分配运行时所必须的资源，最后将其转入就绪状态

• 结束状态：进程从系统中消失，这可能是因为正常结束或其他原因中断退出。当进程结束运行时，系统首先置该进程为结束状态，进一步处理资源释放和回收等工作。

  

进程控制

进程控制是指对系统中的进程实施有效管理。一般把控制进程的程序段称为原语，原语的特点是执行期间不允许中断，它是不可分割的单位。

进程的创建

引起进程创建的事件

1. 用户登录：分时系统中，每一个用户登录都可以被看做是一个新的进程。系统为该终端建立一个进程并插入就绪队列
2. 作业调度：批处理系统中，当系统按照一定算法调度到某作业时，便将该作业调入内存并为其分配资源，创建进程，插入就绪队列
3. 提供服务：运行中的用户提出某种请求后，系统为其创建一个进程来提供用户需要服务
4. 应用请求；前三种是系统创建进程，而用户基于自己的需求可以创建新进程，以便用户并发的完成特定任务。

进程的创建过程

进程创建原语create

1. 为进程申请一个唯一的进程识别号与一个空白的PCB
2. 为进程分配资源，为新进程的程序和数据、用户栈分配内存空间
3. 初始化PCB，主要包括初始化标志信息，状态信息及处理机控制信息
4. 如果就绪队列能够接纳新进程，插入就绪队列等待被调度运行

进程的终止

引起进程终止的事件

1. 正常结束
2. 异常结束：出现某种错误或故障导致程序无法进行，如：越界错误、非法指令、运行超时、等待超时、IO故障
3. 外界干预：进程应外界请求而终止

进程的终止过程

进程终止原语destroy

1. 根据被终止进程的标识符，从PCB集合中检索出进程的PCB，并读取进程状态
2. 若进程处于执行状态，立即终止该进程，并置调度标志为真
3. 若进程还有子孙进程，将其所有子孙进程终止，以防其不可控
4. 将终止进程的所有资源释放给系统或父进程
5. 将被终止进程移出所在队列

进程的阻塞与唤醒

进程的阻塞

阻塞原语block

正在执行的进程，由于期待某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达，系统自动执行阻塞原语(block)，是自己由运动态转为阻塞态，可见阻塞是一种主动现象

阻塞过程

1. 找到要阻塞的标识号对应的PCB
2. 若进程为运行态，则保护现场，将其运行状态转为阻塞，停止运行
3. 将PCB插入相应的时间等待队列中去

进程的唤醒

唤醒原语wakeup

当被阻塞的进程所期待的出现时，如它启动的I/O操作所期待的数据已到达，则有关进程调用唤醒原语（wakeup）将该进程唤醒

唤醒过程

1. 在事件的等待队列中找到进程的PCB
2. 将其从等待序列中移除，并置为就绪状态
3. PCB插入就绪队列，等待进程调度

进程的挂起与激活

进程的挂起

挂起原语：suspend()

当出现了进程挂起事件时，比如用户请求挂起自己的进程，或父进程挂起子进程。

进程的激活

激活原语：active()

当激活的事件发生时，例如父进程或用户进程请求激活子进程，若进程驻留在外存而内存有足够的空间时，将外存的进程换入内存

进程通信

进程间通信主要包括三种：共享储存、消息传递、管道通信

共享储存

在通信的进程之间存在一块可以直接访问的共享空间（内存），这块内存由一个进程创建但是多个进程都可以访问。共享内存是最快的IPC方式，它是专门针对其他通信方式的低效而设计的。与其他通信机制配合（如信号量）来实现进程的同步和通信

消息传递

消息以格式化的形式为单位，通过一个缓冲队列发送至另一个进程。该缓冲队列可能由操作系统提供。

管道通信

管道是进程通信的一种特殊方式，指连接一个读进程和一个写进程实现他们通信的共享文件。为了协调双方通信，管道机制必须提供以下协调能力：互斥、同步、确定对方存在。

linux中管道是一种频繁使用的机制，本质上管道是一种文件，克服通信上的两个问题：

1. 当写进程较快，限制管道大小，linux中该管道大小为4KB，这样缓存大小不会无限制增长。当管道满时，管道对write的调用被阻塞
2. 当读进程较快，管道空后，read操作被阻塞

管道是半双工的，同一时刻只能单向传输。管道可以作为一共享储存的一个优化，利用缓冲区实现了读写的同步。

线程

线程的概念与特征

引入线程的目的是为了更好的使多道程序并发执行，以提高资源利用率与吞吐量，减小程序并发执行付出的时空开销，提高操作系统的并发性能。

线程是“轻量级进程”，是一个基本的CPU执行单元。由线程ID、程序计数器、寄存器和堆栈组成。线程是进程中的一个实体，是被系统调度和分派的独立单位。线程不拥有系统资源，线程只有就绪、阻塞、运行三种状态

引入线程后，进程只作为除CPU外系统资源的分配单元，线程则作为CPU的分配单元。这样同一进程内线程的切换开销很小。

线程的属性

多线程的操作系统中，线程作为独立运行的基本单位，进程的执行实际上是进程的某个线程在执行

• 线程是一个轻型实体，不拥有系统资源，每个线程有唯一的标识符和线程控制块。
• 不同的线程可以执行相同的程序，同一个服务程序被不同用户调用时，操作系统建成不同的线程
• 同一进程各个线程共享进程拥有的资源
• 线程是处理机调度的独立单位，多个线程可以并发执行。在单CPU计算机中线程交替的占用CPU，多CPU中线程可以同时的占有不同的CPU

线程的实现

线程分为两类：用户级线程 和 内核级线程

用户级线程中，线程的管理工作由应用程序完成，内核意识不到线程的存在。

内核级线程中，线程的管理工作由内核完成，引用程序没有进行线程管理的代码，只有一个内核级线程的编程接口，线程的调度也是在内核线程的基础上完成的。

还有组合式的方式

进程与线程的比较

调度

引入线程的操作系统中，线程是调度和分派的基本单位。在同一个进程的中，线程的切换不会引起进程的切换。

拥有资源

进程是拥有除CPU外其他资源的基本单位，程序运行所需要的必要资源（程序、PCB、堆栈）都由进程所有。一般而言线程不占有系统资源（除了一些必不可少的资源），其访问隶属于进程的资源

并发性

进程之间可以并行运行，同一进程的线程间也可以并发运行

创建和开销

进程的创建和撤销，系统都要为之创建、回收PCB，分配和回收资源。操作系统付出的代价比较大。而线程的创建和撤销比较简单。

进程调度

调度层次

作业调度

高级调度，主要任务是按一定原则从外存中将处于后备状态的作业挑选1个或几个，分配内存、输入输出等资源，建立相应进程。使得他们拥有竞争处理机的权力（内存与辅存之间的调度）

中级调度

进程的挂起与就绪

进程调度

低级调度，某种方法和策略从就绪队列中选取一个进程，为其分配处理机。进程调度是最基本的调度，频率很高，一般几十毫秒一次

调度算法

先来先服务（FCFS）算法

FCFS是一种最简单的调度算法，从后备作业队列中选择最先进入该队列作业调度

FCFS是不可剥夺算法，长作业会使后到的短作业长期等待。

特点：算法简单，效率低，对长作业有利，有利于CPU繁忙性作业

短作业优先（SJF）算法

从后背队列中选择一个或若干个估计运行时间最短的作业调入内存运行

特点：对长作业不利，如果短作业源源不断，会使得长作业一直处于饥饿状态。

优先级调度算法

优先级调度算法每次从后背队列中选取优先级最高的一个或几个作业

特点：优先级调度可以剥夺式占有，也可以非剥夺式占有

高响应比优先

高响应比有限主要用于作业调度，该算法是对FCFS和SJF算法的一种平衡，计算每个作业的响应比。

响应比的计算为（等待时间+要求服务时间）/ 要求服务时间

时间片轮转调度算法

时间片轮转算法适用于分时系统，系统将所有就绪的进程按照到达时间排成一个序列，进程调度总是选择就绪队列中的第一个进程执行。但是仅能运行一个，如100ms。

特点：受系统响应时间影响、队列进程数目、进程长短影响较大

多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展

1） 设置多个就绪队列，为各个队列赋予优先级，1、2、3等等

2） 赋予各个队列中时间片大小不同，优先级高时间片越小

3） 一个进程进入内存后首先放入1级队列末尾，FCFS原则等待，如果其能够完成，则撤离系统，否则放入2级队列的末尾，依次向下执行

4） 仅当1级队列为空时，调度程序调度2级队列中的进程，依次类推。

进程同步

临界区

虽然多个进程可以共享系统中的资源，但许多资源一次只能被一个进程使用，把一次仅允许一个进程使用的资源称为临界资源。

// entry

// critical section

// exit section

同步与互斥

同步：进程之间具有直接制约关系，进程之间需要按照一定的次序进行

互斥：进程之间的间接制约关系，不能同时访问临界区

信号量

信号量是一个整形变量，可以被定义为两个标准的原语wait(S) signal(S) 即P、V操作

• P操作 如果信号量大于0，执行 -1操作，如果等于0，执行等待信号量大于0
• V操作 对信号量完成加1操作，唤醒睡眠的进程

typedef int semaphore
semaphore mutex = 1 
void P1(){
    P(&mutex);
    //临界区
    V(&mutex);
}
void P2(){
    P(&mutex);
    //临界区
    V(&mutex);
}

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

问题描述：使用一个缓冲区来保存物品，只有缓冲区没满，生产者才可以放入物品；只有缓冲区不空，消费者可以拿走物品

由于缓冲区输入临界资源，需要一个互斥量mutex来完成缓冲区的互斥访问

为了同步生产者和消费者的行为，需要记录缓冲区物品数量，数量可以用信号量表示，empty记录空缓冲区，full记录满缓冲区

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

void producer(){
    while(True){
        int item = produceItem();
        P(&empty);
        P(&mutex);
        Item.push(item);
        V(&mutex);
        V(&full);
    }
}

void consumer(){
    while(True){
        P(&full);
        P(&mutex);
        int item = Item.top();
        Item.pop();
        consume(item);
        V(mutex);
        V(&empty())
    }
}

管程

使用信号量机制生产消费问题客户端代码需要很多控制，管程作用是把控制的代码独立出来。

管程有一个重要作用：一个时刻只能有一个进程使用。进程不能一直占用管程，不然其他程序都无法使用

管程的生产者消费者实现

monitor ProducerConsumer
	condition full, empty;
	integer cout :=0;
	
	function insert(item:integer);
	begin
		if count = N then wait(full)
		insert_item(item);
		count := count + 1;
		if count = 1 then signal(empty);
	end;
	
	function remote(item:integer);
	begin
		if count = 0 then wait(empty);
		item = remove_item(item);
		count := conut-1;
		if count = N-1 then signal(full);
		return item;
	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);
	end
end;

读者-写者问题

问题描述： 控制多个进程对数据进行读、写操作，但是不允许读-写和写-写操作同时进行

用一个count表示读进程数量，分别用read_mutex 和write_mutex 作为读锁和写锁

typedef int semaphore
semaphore count = 0;
semaphore read_mutex = 1;
semaphore write_mutex = 1;

void read(){
    P(&read_mutex);
    count++;
    if(count==1) P(&write_mutex);
    V(&read_mutex);
    read();
    p(&read_mutex);
    count--;
    if(count==0) V(&write_mutex);
    V(&read_mutex);
}

void write(){
    P(&write);
    write();
    V(&write);
}

哲学家进餐问题

问题描述：五个哲学家围着一张圆桌，每个哲学家面前放着食物，哲学家有两种活动：吃饭与思考，吃饭时，他拿起左边及右边的筷子，并且一次只能拿一根

如果所有哲学家都拿左边的筷子，就会出现死锁，这样只需加一步，当哲学家拿起筷子时检查是否能同时拿起两根筷子，不然就等待

typedef int semaphore
semaphore chop[5] = {1,1,1,1,1};
semaphore mutex = 1;

void process(){
    while(true){
        P(&mutex);
        /*
        if(chop[i]&&chop[(i+1)%5])
        {
      		P(chop[i]);
        	P(chop[(i+1)%5]);
        }
        else{
            V(&mutex);
         	break;   
        }
        */
        P(chop[i]);
        P(chop[(i+1)%5]);
        V(&mutex);
        eat();
        V(chop[i]);
        V(chop[(i+1)%5]);
    }
}

死锁

死锁的定义：多个进程因为竞争资源而造成的一种僵局（互相等待），若无外力作用，所有的进程都无法向前推进。

死锁四个必要条件：

• 互斥条件：进程要求对所分配的资源进行排他性控制，在一段时间内资源仅为一个进程所有。
• 不剥夺条件：进程所获得资源未使用完毕之前，不能被其他进程强行夺走，只能等获得资源的进程自己主动释放
• 请求和保持条件：进程已经至少保持了一个资源，但是又提出了新的资源请求，而该资源已被其他进程占有。此时进程被阻塞，但是对自己资源不释放。
• 循环等待条件：存在某一进程的循环等待链，链中每个进程已获得资源下个进程的请求。

死锁的处理策略

死锁的处理便是破坏四个必要条件，使得死锁无法发生

鸵鸟策略

把头埋在沙子里，假装问题没有发生

由于解决死锁问题的代价往往很高，鸵鸟策略在很多情况下可以取得更高的性能。

大多数操作系统，Unix、Linux、windows处理死锁都是采用鸵鸟策略

死锁预防

1. 破坏互斥条件

   对于可共享的资源竞争，不会发生死锁

2. 破坏不剥夺状态

   当一个进程无法获取其需要的资源时，将之前已获得的资源释放，待需要是再重新申请

3. 破坏请求 和 保持条件

   预先分配的静态方法，在进程运行前一次申请完它需要的所有资源。在资源不满足前不运行，一旦运行这些资源都归期所有。

4. 破坏循环等待

   资源顺序分配法，例如为资源编号，每个进程申请分配某个资源以后，再之后只能申请该编号以后的资源

死锁避免

系统的安全状态：所谓安全状态，是系统能按照某种进程推进顺序（P1，P2，，）为每个进程分配资源，直至满足每个进程对资源的最大需求，使每个系统进程都能顺序完成，则（P1、P2,,)称为安全序列。如果无法找到安全序列，则系统处于不安全状态。

允许进程池动态的申请资源，但是每次分配资源前系统都会计算资源分配的安全性，如果分配资源不会导致系统进入不安全状态，将资源分配给进程；否则，进程等待

银行家算法

银行家算法是最著名的死锁避免算法。它的思想是，把操作系统看成银行家，操作系统管理的资源当成银行家管理的资金，向操作系统请求资源相当于向银行请求贷款。

进程申请资源时，系统评估该进程的最大需求资源，检查资源分配后系统是否还处于安全状态，由此来决定是否分配该资源

死锁检测和接触

死锁检测

死锁解除

• 资源剥夺法

  挂起死锁进程，抢占其资源分配给其他进程

• 撤销进程法

  强制撤销一些死锁进程

• 进程回退法

  借助历史信息使一个或多个进程回退到系统不再死锁的地步