进程和进程管理

程序的顺序执行

一个计算的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。

顺序程序的特点

• 顺序性——处理机的操作严格按照程序所规定的顺序执行。
• 封闭性——程序一旦开始执行，其计算结果不受外界因素的影响。
• 可再现性——程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关。

并发程序

若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的。

并发程序的特点

1、失去程序的封闭性和可再现性

因为一个程序的执行可能会改变另一个程序的变量

2、程序并发执行的相互制约

• 间接的相互制约关系——资源共享
• 直接的相互制约关系——公共变量

进程

进程与程序的区别

简单来说是进程是有生命周期的，但是程序只要输入相同，输出一定相同。

①程序是静态的概念，进程是动态的概念；

②进程是一个独立运行的活动单位；

③进程是竞争系统资源的基本单位；

④一个程序可以对应多个进程，一个进程至少包含一个程序。

进程的状态

进程的基本状态：

①运行状态(running)
该进程已获得运行所必需的资源，它的程序正在处理机上执行。

②等待状态(wait)
进程正等待着某一事件的发生而暂时停止执行。这时，即使给它CPU控制权，它也无法执行。

③就绪状态(ready)
进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行。

进程状态的变迁

新建态： 对应于进程刚刚被创建时没有被提交的状态，并等待系统完成创建进程的所有必要信息。 进程正在创建过程中，还不能运行。操作系统在创建状态要进行的工作包括分配和建立进程控制块表项、建立资源表格（如打开文件表）并分配资源、加载程序并建立地址空间表等。创建进程时分为两个阶段，第一个阶段为一个新进程创建必要的管理信息，第二个阶段让该进程进入就绪状态。由于有了新建态，操作系统往往可以根据系统的性能和主存容量的限制推迟新建态进程的提交。

终止态：进程已结束运行，回收除进程控制块之外的其他资源，并让其他进程从进程控制块中收集有关信息（如记帐和将退出代码传递给父进程）。类似的，进程的终止也可分为两个阶段，第一个阶段等待操作系统进行善后处理，第二个阶段释放主存。

注意因果变迁：

系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁，这种变迁称为因果变迁

进程描述

进程控制块

描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构，称为进程控制块PCB (process control block)。

①进程标识符——进程符号名（唯一的标识符）或内部id号（方便系统管理）

②进程当前状态——本进程目前处于何种状态（只有处在就绪态，才有可能获得处理机）

③当前队列指针next——该项登记了处于同一状态的下一个进程的PCB地址。

​ 进程一般是采用队列的形式，把具有相同状态的进程链在一起，形成队列。

④进程优先级——反映了进程要求CPU的紧迫程度。

⑤CPU现场保护区——当进程由于某种原因释放处理机时，CPU现场信息被保存在PCB的该区域中。

⑥通信信息——进程间进行通信时所记录的有关信息。

⑦家族联系——指明本进程与家族的联系

​ （一般而言，子进程继承父进程的全部资源。如果父进程被杀死，子进程会向上托孤，过继给祖进程）

⑧占有资源清单——不同的OS的PCB结构不同，占有资源清单可以显示PCB的内容

进程的组成

进程=程序 + 数据 + PCB

进程和程序最本质的区别是进程的动态特征。

进程控制

常用的进程控制原语

创建原语、撤消原语、阻塞原语、唤醒原语

进程创建

使用进程创建原语：create (name，priority) // name为被创建进程的标识符，priority为进程优先级

以父进程为模板创建子进程，复制父进程的pcb大部分数据(共用代码段，数据独有,有自己的虚拟地址空间)。

Linux中使用fork函数

#include <unistd.h>
pid_t fork(void);

返回值：

• 子进程返回0
• 父进程返回子进程的pid

进程撤销

使用撤销原语

撤消当前运行的进程。将该进程的PCB结构归还到PCB资源池，所占用的资源归还给父进程，从总链队列中摘除它，然后转进程调度程序。

return调用exit( )，exit 调用终止处理程序和标准I/O清理程序，然后调用 _exit( )或 Exit( )

exit( ) 直接调用 _exit( )或 _Exit( )

_exit( ) 或 _EXIT( )直接调用内核

进程等待

使用进程等待原语

（注意保护进程的CPU现场到PCB结构中）

中止调用进程的执行，并加入到等待chan（等待的资源）的等待队列中；最后使控制转向进程调度。

进程唤醒

使用进程唤醒原语

当进程等待的事件发生时，唤醒等待该事件的进程。

进程之间的约束关系的概念

进程互斥、同步的概念是并发进程下存在的概念，有了并发进程，就产生了资源的竞争与协作，从而就要通过进程的互斥、同步、通信来解决资源的竞争与协作问题。

在多道程序设计系统中，同一时刻可能有许多进程，这些进程之间存在两种基本关系：竞争关系和协作关系。

==进程的互斥、同步、通信都是基于这两种基本关系而存在的。==

==为了解决进程间竞争关系（间接制约关系）而引入进程互斥；==

==为了解决进程间松散的协作关系(直接制约关系)而引入进程同步；==

==为了解决进程间紧密的协作关系而引入进程通信。==

竞争关系

资源竞争出现了两个控制问题：

一个是死锁 （deadlock ）问题，一组进程如果都获得了部分资源，还想要得到其他进程所占有的资源，最终所有的进程将陷入死锁。

另一个是饥饿（starvation ）问题，这是指这样一种情况：一个进程由于其他进程总是优先于它而被无限期拖延。

操作系统需要保证诸进程能互斥地访问临界资源，既要解决饥饿问题，又要解决死锁问题。
进程的互斥（mutual exclusion ）是解决进程间竞争关系( 间接制约关系) 的手段。 进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。

协作关系

某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后方被唤醒并继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。

进程间的协作可以是双方不知道对方名字的间接协作，例如，通过共享访问一个缓冲区进行松散式协作；也可以是双方知道对方名字，直接通过通信机制进行紧密协作。允许进程协同工作有利于共享信息、有利于加快计算速度、有利于实现模块化程序设计。

进程的同步（Synchronization）是解决进程间协作关系( 直接制约关系) 的手段。

进程互斥

临界资源

一次仅允许一个进程使用的资源称为临界资源。

临界区

临界区是进程中对公共变量(或存储区)进行审查与修改的程序段，称为相对于该公共变量的临界区。

注意：

• 临界区是针对某一个临界资源而言的
• 临界区的数量是共享该临界资源的进程数量
• 每次只能至多有一个进程处于其临界区中
• 进程处于临界区的时间是有限的。防止其他进程被饿死
• 为了避免多个进程试图同时进入临界区而导致的阻塞，每个进程进入临界区的时间是有限的，不是任意时候都可以进入临界区

临界区是一种轻量级的同步机制，与互斥和事件这些内核同步对象相比，临界区是用户态下的对象，即只能在同一进程中实现线程互斥。因无需在用户态和核心态之间切换，所以工作效率比较互斥来说要高很多。虽然临界区同步速度很快，但却只能用来同步本 进程内的线程，而不可用来同步多个进程中的线程。

互斥

在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。

进程同步

并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。

不难看出，==进程互斥关系是一种特殊的进程同步关系==，即逐次使用互斥共享资源，也是对进程使用资源次序上的一种协调。

进程通信

并发进程之间的交互必须满足两个基本要求：同步和通信。

进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好进程同步问题，进程同步是一种进程通信，通过修改信号量，进程之间可建立起联系，相互协调运行和协同工作。但是信号量与PV操作只能传递信号，没有传递数据的能力。有些情况下进程之间交换的信息量虽很少，例如，仅仅交换某个状态信息，但很多情况下进程之间需要交换大批数据，例如，传送一批信息或整个文件，这可以通过一种新的通信机制来完成，进程之间互相交换信息的工作称之为进程通信IPC （InterProcess Communication）（主要是指大量数据的交换）。

进程间通信的方式很多，包括：

1 mmap（文件映射）

2 信号

3 管道

4 共享内存

5 消息队列（重要）

6 信号量集（与signal无关）

7 网络（套接字）

进程同步机制

Linux 下常见的进程同步方法有：

1、信号量

2、管程

3、 互斥量（基于共享内存的快速用户态 ）

4、文件锁（通过 fcntl 设定，针对文件）

针对线程（pthread）的还有 pthread_mutex 和 pthread_cond（条件变量）。

线程的同步方法：

1、信号量

2、互斥量

3、临界区

4、事件

锁、上锁、开锁操作

• 检测w的值(是0还是1)；
• 如果w的值为1，继续检测；
• 如果w的值为0，将锁位置1 (表示占用资源)，进入临界区执行。(此为上锁操作)
• 临界资源使用完毕，将锁位置0。(此为开锁操作)

信号灯和P、V操作

信号灯是一个确定的二元组(s，q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理。信号灯是整型变量。

变量值≥ 0 时，表示绿灯，进程执行；
变量值<0 时，表示红灯，进程停止执行。

注意：创建信号灯时，应准确说明信号灯s 的意义和初值(这个初值绝不能为负值)。

P操作

是原语。

即取信号灯值做的是 - 1操作：

• 如果结果>=0，继续执行
• 如果结果<0，该进程阻塞，进入等待队列

V操作

是原语。

即取信号灯值做的是+ 1操作：

• 如果结果>0，继续执行
• 如果结果<=0，帮助唤醒在信号灯等待队列上的一个进程

P、V操作和上锁、解锁的联系

设置信号灯mutex：

• 1：表示没有进程进入到临界区
• 0：表示有一个进程进入到临界区
• -1：表示有一个进程进入到了临界区，并且有一个进程在等待

当mutex=1时，P操作相当于上锁；V操作相当于解锁。

两类同步问题的解法

合作进程的执行次序

使用流图来表示进程的执行顺序。

共享缓冲区的合作进程的同步

生产者和消费者问题

也称为有限缓冲问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。通常采用进程间通信的方法解决该问题。如果解决方法不够完善，则容易出现死锁的情况。出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。

生产者与消费者的同步关系

• 生产者：

  • 当有界缓冲区中无空位置时，要等待；
  • 向有界缓冲区放入物品后，要发消息。

• 消费者：

  • 当有界缓冲区中无物品时，要等待；
  • 从有界缓冲区取出物品后，要发消息。

信号灯设置:

i 两个同步信号灯——

• sb：表示空缓冲区的数目，初值=n
• nsa：表示满缓冲区(即信息)的数目，初值= 0

ii 一个互斥信号灯——

• mutex：表示有界缓冲区是否被占用，初值= 1

main{
	int sa=0;//表示的是满缓冲区的数量
	int sb=n;//表示的是空缓冲区的数量
	int mutex=1;//表示的是有界缓冲区的互斥信号灯
	cobegin
	p1();p2();······pn();
	c1();c2();······cn();
	coend
}
pi()
{
	while(生产未完成)
	{
		P(sb);
		P(mutex);
		生产();
		V(sa);
		V(mutex);
	}
}
ci()
{
	while(继续消费)
	{
		P(sa);
		P(mutex);
		消费();
		V(sb);
		V(mutex);
	}
}

理发师睡觉问题

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等。如果没有空椅子，他就离开。

一个理发师，一把理发椅，n把等候理发的顾客椅子。

（1）如果没有顾客，则理发师在理发椅上睡觉；
（2）当有一个顾客到达时，首先看理发师在干什么，
如果理发师在睡觉，则唤醒理发师理发；
如果理发师正在理发，则查看是否有空的顾客椅子可坐；
如果有顾客椅子可坐，则坐下等待，
如果没有，则离开。

（3）理发师为一位顾客理完发后，查看是否有人在等待，如果有则唤醒下一位顾客理发，没有则理发师去睡觉。

理发师和顾客之间的同步关系：

​ 理发师睡觉的时候，顾客进来需要唤醒理发师
​ 当有顾客的时候，理发师理发；没有就睡觉

理发师与顾客、顾客与顾客之间的互斥关系

​ 由于每次理发师只能为1个人理发，且可供等侯的椅子只有n把，即理发师和椅子是临界资源，顾客之间是互斥的关系。

信号灯设置:

​ 1、控制变量waiting用来记录等候理发的顾客数，初值均为0; 进入理发店的顾客必须先看等候的顾客数，如果少于椅子数，他留下来等，否则他就离开。

​ 2、信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0;

​ 3、信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0;

​ 4、信号量mutex用于互斥，初值为1.

main{
	int customers=0;
	int barbers=1;
	int waiting=0;
	int mutex=1;
	cobegin
	barber();
	customers();
	coend
}
barber()
{
	while(true)
	{
		P(customers);//如果顾客人数为0，睡觉
		P(mutex);
		waiting-=1;
		V(barbers);//该理发师不再睡觉，已经激活
		V(mutex);
		理发;
	}
}
customers()
{
	P(mutex);//该顾客被锁定
	if(waiting==n)
	{
		店满了，走人;
		V(mutex);//顾客走了，取消锁定
	}
	else
	{
		waiting+=1;//增加一名顾客
		V(customers);//告诉理发师，有顾客，睡觉的让他起来
		V(mutex);
		P(barbers);//该理发师为这位顾客理发，其他的顾客得等到理发师理完发即V(barbers)
		剪发;
	}
}

进程通信

进程通信(InterprocessCommunication, IPC)是指进程之间直接以较高的效率传递较多数据的信息交互方式。

IPC机制：指消息（message）从一个进程的地址空间拷贝到另一个进程的地址空间的过程，而不使用共享存储器。该机制由操作系统提供。发送或是接收消息需要操作系统的干预

进程通信方式：消息缓冲通信/信箱通信

消息缓冲通信

在消息通信中，接收方和发送方之间有明确的协议和消息格式。

​ （大多数使用消息头：发送/接收进程的ID、被传消息的字节数……）

消息缓冲通信方式包括消息缓冲、发送原语和接收原语。

​ 发送进程先形成一个消息缓冲区（含消息头和消息内容），然后用发送原语发出。

​ 接收进程在接收前，在本进程的主存空间设置一个接收区，然后用接收原语接收。

信箱通信

在信箱通信中，需要定义信箱结构，还包括消息发送和接收功能模块，提供发送原语和接收原语。

信箱通信中，所使用的信箱可以位于用户空间中，是接收进程地址空间的一部分；也可以放置在操作系统的空间中。

缺点：要求OS为所有的进程分配主存信箱，受系统限制，可能对通信进程数限制。

线程概念及特点

线程就是进程的一个执行路径，一个进程可以有多条执行路径。这样，一个进程内部就有多个可以独立活动的单位，可以加快进程处理的速度，进一步提升并行处理能力。

• 进程中的一条执行路径；
• 它有自己私用的堆栈和处理机执行环境；
• 它与父进程共享分配给父进程的主存；
• 它是单个进程所创建的许多个同时存在的线程中的一个。

进程和线程的主要区别

根本区别：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位

在开销方面：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。

所处环境：在操作系统中能同时运行多个进程（程序）；而在同一个进程（程序）中有多个线程同时执行（通过CPU调度，在每个时间片中只有一个线程执行）

内存分配方面：系统在运行的时候会为每个进程分配不同的内存空间；而对线程而言，除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源。

包含关系：进程是线程的容器，不存在没有线程的进程。

线程的状态变迁

用户线程和内核线程

• 用户线程：

  • 在内核的支持下，在用户层通过线程库实现
  • 创建和调度在用户空间进行，无需内核干预
  • 优点：能快速创建和管理
  • 缺点：如果内核是单线程的，一旦一个用户线程执行了等待的系统调用，则整个进程阻塞

• 内核线程

  • 由OS管理，创建和调度在OS主存空间内完成
  • 当一个线程执行时阻塞，内核能调度另一个线程运行

操作系统的并发机制实例

创建进程

在UNIX/LINUX系统中，使用fork（）函数。

函数的具体用法可见另一篇：《linux的琐碎知识点》

UNIX/Linux系统的核心为系统调用fork完成下列操作：

①为新进程分配一个新的pcb结构；

②为子进程赋一个唯一的进程标识号(PID)；

③做一个父进程上下文的逻辑副本。由于进程的正文区(代码段) 可被几个进程所共享，所以核心只要增加某个正文区的引用数即可，而不是真的将该区拷贝到一个新的内存物理区。这就意味着父子进程将执行相同的代码。数据段和堆栈段属于进程的私有数据，需要拷贝到新的内存区中。

④增加与该进程相关联的文件表和索引节点表的引用数。这就意味着父进程打开的文件子进程可以继续使用。

⑤对父进程返回子进程的进程号，对子进程返回零。

启动一个新的程序的执行

父进程为了启动一个新的程序的执行，在UNIX/LINUX系统中需要用到exec()类函数

Exec()类函数很多

• 作用是根据参数指定的文件名找到可执行文件，并用它来取代调用进程的内容，即在调用进程内部执行一个可执行文件。

exec-执行文件，启动新程序运行

①更换进程执行代码，更换正文段，数据段

②调用格式：exec (文件名，参数表，环境变量表）

示例：

main(){
    if(fork()==0){  
        printf(“a”);
        execlp(“file1”,0);
        printf(“b”);
    }
    printf(“c”);
}
file1:
main()
{
    printf(“d”);
}
运行结果：
    acd、cad、adc（无论如何字母b不会被打印）

创建线程

LINUX下的多线程程序，需要使用pthread.h，连接时需要使用库libpthread.a。

Clone( )是LINUX特有的系统调用，用来实现pthread。与fork( )类似。

功能：创建一个新的线程
原型
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*star
t_routine)(void*), void *arg);
参数
thread:返回线程ID
attr:设置线程的属性，attr为NULL表⽰示使⽤用默认属性
start_routine:是个函数地址，线程启动后要执⾏的函数
arg:传给线程启动函数的参数
返回值：成功返回0；失败返回错误码

终止线程

return返回
pthread_exit(void *val)

功能：线程终止 原型
void pthread_exit(void *value_ptr);
参数
value_ptr:value_ptr 
返回值：无返回值，跟进程一样，线程结束的时候无法返回到它的调用者（自身）

pthread_canel()取消线程，返回-1

功能：杀死一个执行中的线程
原型
int pthread_cancel(pthread_t thread);
参数
thread:线程ID
返回值：成功返回0；失败返回错误码

等待进程、线程的终止

等待进程终止

为什么要线程等待呢？

1、就像子进程死亡，需要父进程等待并回收一样，新线程死亡，其空间没有被释放，需要主线程等待回收

2、如果再创建新的线程不会复用刚才退出线程的地址空间

(1) 等待进程终止

wait();waitpid();

进程一旦调用了wait，就立即阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个已经变成僵尸的子进程，wait
就会收集这个子进程的信息， 并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个出现为止。

如果该进程没有子进程，则立即出错返回，返回值为-1（注意，是wait()函数立即返回，而不是说该父进程也跟着结束了，父进程里该语句后的内容还是要照样接着执行的）

定义函数 pid_t wait (int * status);

• wait()函数用于使父进程（也就是调用wait()的进程）阻塞，直到一个子进程结束或者该进程接收到了一个指定的信号为止。如果该父进程没有子进程或者它的子进程已经结束，则wait()函数就会立即返回。参数status所指向的变量存放子进程的退出码，即从子进程的main函数返回的值或子进程中exit()函数的参数。如果status不是一个空指针，状态信息将被写入它指向的变量。

定义函数 pid_t waitpid(pid_t pid,int * status,int options);

• waitpid()的作用和wait()一样，但它并不一定要等待第一个终止的子进程（它可以指定需要等待终止的子进程），它还有若干选项，如可提供一个非阻塞版本的 wait()功能，也能支持作业控制。实际上，wait()函数只是 waitpid()函数的一个特例，在Linux 内部实现 wait()函数时直接调用的就是waitpid()函数。

进程调度

调度：在众多处于就绪状态的进程中，按一定的原则选择一个进程。

分派：当处理机空闲时，移出就绪队列中第一个进程，并赋予它使用处理机的权利。

调度程序负责将一个进程插入到就绪队列并按一定的原则保持队列结构

分配程序是将进程从就绪从就绪队列中移出并建立该进程执行的机器状态

进程调度的功能

1、记录进程的有关情况

2、决定调度策略：

①优先调度
就绪队列按进程优先级高低排序

②先来先服务
就绪队列按进程来到的先后次序排序

3、 实施处理机的分配和回收

进程调度的方式

• 非剥夺方式

  当“重要而紧迫”的进程来到时，让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程。

• 剥夺方式

当“重要而紧迫”的进程来到时，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。

进程调度算法

进程优先数调度算法

预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权(优先数和一定的优先级相对应)的就绪进程。

优先数的分类及确定

i 静态优先数

• 在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。

ii 静态优先数的确定

• 优先数根据进程所需使用的资源来计算
• 优先数基于程序运行时间的估计

iii 动态优先数

• 进程优先数在进程运行期间可以改变。

iv 动态优先数的确定

• 进程使用CPU超过一定数值时，降低优先数
• 进程I/O操作后，增加优先数
• 进程等待时间超过一定数值时，提高优先数

循环轮转调度算法

当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。相当公平。

队列排序的原则是先来先服务。

循环轮转调度算法的特征：就绪队列中的所有进程以等速度向前进展。
$$
q = t/n
$$
t 为用户所能接受的响应时间，n为进入系统的进程数目。

注意：

​ q值如果取值很大的话，会导致所有进程都可以在分给它的时间片内完成，轮转调度就退化成了FIFO算法。

​ q值如果取值很小的话，进程切换的时间就变得不可忽略，系统的开销又很大。

• 可变时间片轮转调度

每轮开始时，系统根据就绪队列中的进程数量计算一次q值，然后进行轮转。

• 多重时间片循环调度

调度用的进程状态变迁图

①进程状态

• 运行状态

• 低优先就绪状态

• 高优先就绪状态

• 因I/O而等待状态

②队列结构

• 低优先就绪队列
• 高优先就绪队列
• 因I/O而等待队列

优先调度与时间片调度相结合的调度算法

i 当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms。

ii 当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms。

调度效果

优先照顾I∕O量大的进程；适当照顾计算量大的进程。

四种进程或线程同步互斥的控制方法

原文链接

1、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
2、互斥量:为协调共同对一个共享资源的单独访问而设计的。
3、信号量:为控制一个具有有限数量用户资源而设计。
4、事 件:用来通知线程有一些事件已发生，从而启动后继任务的开始。

临界区（Critical Section）

保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么 在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操 作共享资源的目的。
临界区包含两个操作原语：

EnterCriticalSection（） 进入临界区 
LeaveCriticalSection（） 离开临界区 
EnterCriticalSection（） 语句执行后代码将进入临界区以后无论发生什么，必须确保与之匹配的 LeaveCriticalSection（）都能够被执行到。否则临界区保护的共享资源将永远不会被释放。虽然临界区同步速度很快，但却只能用来同步本 进程内的线程，而不可用来同步多个进程中的线程。 

MFC提供了很多功能完备的类，我用MFC实现了临界区。MFC为临界区提供有一个 CCriticalSection类，使用该类进行线程同步处理是 非常简单的。只需在线程函数中用CCriticalSection类成员函数Lock（）和UnLock（）标定出被保护代码片段即可。Lock（）后代 码用到的资源自动被视为临界区内的资源被保护。UnLock后别的线程才能访问这些资源。

MFC提供了很多功能完备的类，我用MFC实现了临界区。MFC为临界区提供有一个 CCriticalSection类，使用该类进行线程同步处理是 非常简单的。只需在线程函数中用CCriticalSection类成员函数Lock（）和UnLock（）标定出被保护代码片段即可。Lock（）后代 码用到的资源自动被视为临界区内的资源被保护。UnLock后别的线程才能访问这些资源。

互斥量（Mutex）

互斥量跟临界区很相似，只有拥有互斥对象的线程才具有访问资源的权限，由于互斥对象只有一个，因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出，以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

互斥量包含的几个操作原语：

CreateMutex（） 创建一个互斥量 
OpenMutex（） 打开一个互斥量 
ReleaseMutex（） 释放互斥量 
WaitForMultipleObjects（） 等待互斥量对象 

信号量（Semaphores）

信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源 ，这与操作系统中的PV操作相同。它指出了同时访问共享 资源的线程 最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore（）创建信号量 时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数 就会减1，只要当前可用资源计数是大于0的，就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目， 不能在允许其他线程的进入，此时的信号量信号将无法发出。线程在处理完共享资源后，应在离开的同时通过ReleaseSemaphore（）函数将当前可 用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。
PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用共享资源的进程数。
P操作 申请资源：
　　（1）S减1；
　　（2）若S减1后仍大于等于零，则进程继续执行；
　　（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转入进程调度。
V操作 释放资源：
　　（1）S加1；
　　（2）若相加结果大于零，则进程继续执行；
　　（3）若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转入进程调度。

CreateSemaphore（） 创建一个信号量 
  　　OpenSemaphore（） 打开一个信号量 
  　　ReleaseSemaphore（） 释放信号量 
  　　WaitForSingleObject（） 等待信号量

　　信号量包含的几个操作原语：

事件（Event）

事件对象也可以通过通知操作的方式来保持线程的同步。并且可以实现不同进程中的线程同步操作。
信号量包含的几个操作原语：

CreateEvent（） 创建一个事件 
  　　OpenEvent（） 打开一个事件 
  　　SetEvent（） 回置事件 
  　　WaitForSingleObject（） 等待一个事件 
  　　WaitForMultipleObjects（）　　　　　　　　 等待多个事件 
  　　　　WaitForMultipleObjects 函数原型： 
  　　　　　WaitForMultipleObjects（ 
  　　　　　IN DWORD nCount, // 等待句柄数 
  　　　　　IN CONST HANDLE *lpHandles, //指向句柄数组 
  　　　　　IN BOOL bWaitAll, //是否完全等待标志 
  　　　　　IN DWORD dwMilliseconds //等待时间 
  　　　　　） 

参 数nCount指定了要等待的内核对象的数目，存放这些内核对象的数组由lpHandles来指向。fWaitAll对指定的这nCount个内核对象的两种等待方式进行了指定，为TRUE时当所有对象都被通知时函数才会返回，为FALSE则只要其中任何一个得到通知就可以返回。 dwMilliseconds在这里的作用与在WaitForSingleObject（）中的作用是完全一致的。如果等待超时，函数将返回 WAIT_TIMEOUT。

总结

1． 互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量 。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。
2． 互斥量（Mutex），信号灯（Semaphore），事件（Event）都可以被跨越进程使用来进行同步数据操作，而其他的对象与数据同步操作无关，但对于进程和线程来讲，如果进程和线程在运行状态则为无信号状态，在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和 线程退出。
3． 通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号灯对象可以说是一种资源计数器。

问题

1.操作系统中为什么要引入进程的概念？为了实现并发进程中的合作和协调，以及保证系统的安全，操作系统在进程管理方面要做哪些工作？

答： 为了从变化角度动态地分析研究可以并发执行的程序，真实的反应系统的独立性、并发性、动态性和相互制约，操作系统中不得不引入进程的概念。

为了防止操作系统及其关键的数据结构如：PCB等，受到用户程序破坏，将处理机分为核心态和用户态。对进程进行创建、撤销以及在某些进程状态之间的转换控制。

\2. 试描述当前正在运行的进程状态改变时，操作系统进行进程切换的步骤。

答：分为两种情况：

（1）：运行状态 就绪 状态：根据进程的自身的情况插入到就绪队列的适当位置，系统收回处理及转入进程调度程序重新进行调度。

（2）：运行状态→阻塞状态：系统会调用进程调度程序重新选择一个进程投入运行。

3.现代操作系统一般都提供多任务的环境，是回答以下问题。

为支持多进程的并发执行，系统必须建立哪些关于进程的数据结构？

答：系统必须建立PCB。

为支持进程的状态变迁，系统至少应该供哪些进程控制原语？

答：阻塞、唤醒、挂起和激活原语。

当进程的状态变迁时，相应的数据结构发生变化吗？

答：会根据状态的变迁发生相应的变化。例如：将进程PCB中进程的状态从阻塞状态改为就绪状态，并将进程从阻塞队列摘下，投入到就绪队列中。

4.什么是进程控制块？从进程管理、中断处理、进程通信、文件管理、设备管理及存储管理的角度设计进程控制块应该包含的内容。

答：PCB：描述进程本身的特征、状态、调度信息以及对资源占有情况等的数据结构，是进程存在的唯一标识。

进程控制块所包含的内容：

①进程信息描述；②CPU信息状态；③进程调度信息；④进程控制和资源占用信息。

5.假设系统就绪队列中有10个进程，这10个进程轮换执行，每隔300ms轮换一次，CPU在进程切换时所花费的时间是10ms，试问系统化在进程切换上的开销占系统整个时间的比例是多少？

解：P=(10*10)/[(300+10)*10]=3.2%

6.试述线程的特点及其与进程之间的关系。

答：线程的特点：是被独立分派和调度的基本单位。线程与进程的关系：线程是进程的一部分，是进程内的一个实体；一个进程可以有多个线程，但至少必须有一个线程。

7.根据图2-18，回答以下问题。

进程发生状态变迁1、3、4、6、7的原因。

答：变迁1原因：创建进程后，将其按高优先级插入就绪队列；

变迁3原因：进程请求I/O或等待某事件而阻塞；

变迁4原因：时间片用完；

变迁6原因：进程I/O完成或时间完成；

变迁7原因：进程完成而退出。

系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁，这种变迁称为因果变迁。下述变迁是否为因果变迁：3→2,4→5,7→2,3→6，是说明原因。

答：

3→2是因果变迁，当一个进程从运行态变为阻塞态时，此时CPU空闲，系统首先到高优先级队列中选择一个进程。

4→5是因果变迁，当一个进程运行完毕时，此时CPU空闲，系统首先到高优先级队列中选择进程，但如果高优先级队列为空，则从低优先队列中选择一个进程。

7→2 是因果变迁，当一个进程运行完毕时，CPU空闲，系统首先到高优先级队列中选择一个进程。

3→6不是因果变迁。一个进程阻塞时由于自身的原因而发生的，和另一个进程等待的时间到达没有因果关系。

根据此进程状态转换图，说明该系统CPU调度的策略和效果。

当进程调度时，首先从高优先级就绪队列选择一个进程，赋予它的时间片为100ms。如果高优先级就绪队列为空，则从低优先级就绪队列选择进程，并且赋予该进程的时间片为500ms。

这种策略一方面照顾了短进程，一个进程如果在100ms运行完毕它将退出系统，更主要的是照顾了I/O量大的进程，进程因I/O进入阻塞队列，当I/O完成后它就进入了高优先级就绪队列，在高优先级就绪队列等待的进程总是优于低优先级就绪队列的进程。而对于计算量较大的进程，它的计算如果在100ms的时间内不能完成，它将进入低优先级就绪队列，在这个队列的进程被选中的机会要少，只有当高优先级就绪队列为空，才从低优先级就绪队列选择进程，但对于计算量大的进程，系统给予的适当照顾时间片增大为500ms。

8.回答以下问题。

若系统中没有运行进程，是否一定没有就绪进程？为什么？

答：是，因为一旦系统中没有运行程序，就会马上从就绪队列中调度就绪进程，只有就绪进程队列为空时，系统中才没有进程。

若系统中既没有运行进程，也没有就绪进程，系统中是否就没有阻塞进程？解释。

答：不是，不一定，当运行的程序都因为请求I/O或等待事件时而进入阻塞，系统中就没有就绪进程。

如果系统采用优先级调度策略，运行的进程是否一定是系统中优先级最高的进程？为什么？

答：不一定，若优先级高的进程进入阻塞状态时，而且优先级高的就绪队列里没有等待的进程，这时就会调度优先级低的就绪队列的进程。

第四章 习题及解答

4-3 什么是进程？进程与程序的主要区别是什么？

答：进程是一个具有一定独立功能的程序关于某个数据集合的一次活动。进程与程序的主要区别是：

(1) 程序是指令的有序集合，是一个静态概念。进程是程序在处理机的一次执行过程，是一个动态概念。进程是有生命期的，因创建而产生，因调度而执行，因得到资源而暂停，因撤消而消亡；

(2) 进程是一个独立的运行单元，是系统进行资源分配和调度的独立单元，而程序则不是。

(3) 进程与程序之间无一一对应关系。一个程序可以对应多个进程，一个进程至少包含一个程序。

4-9 某系统进程调度状态变迁图如图4.31所示，请说明：

(1) 什么原因会导致发生变迁2、变迁3、变迁4 ？

答：发生变迁2的原因：时间片到

发生变迁3的原因：请求I/O或其他系统调用

发生变迁4的原因：I/O完成或其他系统调用完成

(2) 在什么情况下，一个进程的变迁3 能立即引起另一个进程发生变迁1 ？

答：一个进程的变迁3 能立即引起另一个进程发生变迁的条件是，就绪队列非空。

(3) 下列因果变迁是否可能发生？若可能，需要什么条件？

a. 2→1； b. 3→2； c. 4→1

答：a. 2→1 不需要条件，一定会发生。

b. 3→2 不可能发生。

c. 4→1 可能发生，条件：就绪队列为空，或在可剥夺调度方式下，转变为就绪状态的进程优先级最高。

4-10某系统进程状态除了3个最基本状态外，又增加了创建状态、完成状态、因等消息而转变为等待状态3种新的状态，试画出增加新状态后的进程状态变迁图，并说明发生每一个变迁的原因。

答：进程状态变迁图：

进程状态变迁原因：

运行—>等待：请求I/O； 等待—>就绪：请求完成；运行—>就绪：时间片到； 就绪—>运行：CPU空闲，进程调度程序工作；

创建—>就绪：进程创建； 运行—>等消息：等待消息；等消息—>就绪：收到消息；运行—>完成：任务完成

4-12 n个并发进程共用一个公共变量Q，写出用信号灯实现n个进程互斥时的程序描述，给出信号灯值的取值范围, 并说明每个取值的物理意义。

main ( ){
int mutex=1;  //公共变量Q的互斥信号灯
cobegin
	P1; 	P2;	… 	Pn; 
coend                 
}
Pi(){
	…
	P(mutex);
	使用Q；
	V(mutex);
	…
}

(2) 信号灯值的取值范围：[- (n–1)，1]

(3) mutex每个取值的物理意义：

mutex = 1 说明没有进程进入临界段执行；

mutex = 0 说明有一个进程进入临界段执行；

mutex = -1 说明有一个进程进入临界段执行，另有一个进程正在等待进入；

mutex = - (n–1) 说明有一个进程进入临界段执行，另有(n–1)个进程正在等待进入。

4-13 图4.32(a)、(b) 分别给出了两个进程流图。试用信号灯的p、v操作分别实现图4.32(a)、(b)所示的两组进程之间的同步，并写出程序描述。

4-15 如图4.34所示，get、copy和put三个进程共用两个缓冲区s和t (其大小每次存放一个记录) ，get 进程负责不断地把输入记录输入缓冲区s 中，copy 进程负责从缓冲区s 中取出记录复制到缓冲区t 中，而put 进程负责从缓冲区t 中取出记录打印。试用PV 操作实现这三个进程之间的同步，并写出程序描述。

main(){
	int s1=1,s2=0; // s1 表示缓冲区S 是否为空，s2 表示是否已满//
	int s3=1, s4=0; // s3 表示缓冲区T 是否为空，s4 表示是否已满//
	cobegin
	get;
	copy;
	put;
	coend
}

get(){
while(1){
	P(s1);
	input data to buffer S;
	V(s2);
	}
}

copy (){
	while(1){
	P(s2);
	copy data from buffer S;
	V(s1);
	P(s3);
	input copy-data to buffer T;
	V(s4);
	}
}

put(){
	while(1){
		P(s4);
	output data to buffer S;
	V(s3);
	}
}

4-16 什么是进程的互斥与同步？同步和互斥这两个概念有什么联系和区别？

答：在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程读出或者修改该存储区的内容，否则，就会发生后果无法估计的错误。进程之间的这种相互制约关系称为互斥。

所谓同步，就是并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程同步。

同步和互斥这两个概念都属于同步范畴，描述并发进程相互之间的制约关系。同步是指并发进程按照他们之间的约束关系，在执行的先后次序上必须满足这种约束关系。而互斥是同步的一种特例，是指并发进程按照他们之间的约束关系，在某一点上一个时刻只允许一个进程执行，一个进程做完了，另一个进程才能执行，而不管谁先做这个操作。

4-22 什么是线程？线程和进程有什么区别?

答：线程也称为轻量级进程，它是比进程更小的活动单位，它是进程中的一个执行路径，一个进程可能有多个执行路径，即线程。

线程和进程的主要区别如下。

(1) 线程是进程的一个组成部分，一个进程可以有多个线程，而且至少有一个可执行的线程。

(2) 进程是资源分配的基本单位，它拥有自己的地址空间和各种资源；线程是处理机调度的基本单位，它只能和其他线程共享进程的资源，而本身并没有任何资源。

(3) 进程的多个线程都在进程的地址空间内活动。这样，在以线程为单位进行处理机调度和切换时，切换时间较短；而以进程为单位进行处理机调度和切换时，由于涉及到资源转移及现场保护等问题，将导致切换时间变长和资源利用率下降。

(4) 线程和进程一样，都有自己的状态和相应的同步机制，但是，由于线程没有自己单独的程序和数据空间，因而不能像进程那样将程序和数据交换到外存去。

(5) 进程的调度和控制大多由操作系统的内核完成，而线程的控制既可以由操作系统内核完成，也可以由用户控制完成。

4-27 试画出Linux系统的进程状态变迁，并说明这些变迁可能的原因。

答：画出Linux系统的进程状态变迁如图所示：

(1) 进程创建

当系统或用户需要创建一个新进程时，调用fork()系统调用，被创建的新进程被置为就绪状态TASK_RUNNING。

(2) 进程调度

当调度时机来到时，进程调度程序从进程运行队列中选择优先级最高的进程，将其投入运行，设置状态为运行状态。

(3) 被抢占

正在CPU上运行的进程，当其优先级低于处于就绪状态的某一个进程的优先级时，它被抢占而被迫让出CPU的控制权，此时，该进程的状态转为就绪状态。

(4) 进程等待

若正在运行的进程因等待某一事件而暂时不能运行下去时，进入相应的等待队列，设置为等待状态。

(5) 进程唤醒

当某个进程等待的原因撤销时，该进程被唤醒，将其从等待队列中移出，进入就绪队列。

(6) 进程终止

当正在运行的进程完成其任务时，通过exit()系统调用终止自己而进入终止状态。

4-29某公园有一个长凳，其上最多可以坐5个人。公园里的游客遵循以下规则使用长凳：

(1) 如果长凳还有空间可以坐，就坐到长凳上休息，直到休息结束，离开长凳。

(2) 如果长凳上没有空间，就转身离开。

试用信号灯的P、V操作描述这一场景。

答：

main(){
int count=5; // 长凳上可坐的人数
int mutex=0; // 访问count的互斥信号灯
cobegin
guesti;	// i =1,2,3,4……
coend
}
guesti {
	P(mutex);
	if (count == 0) {
		V(mutex);
		return;
	}
	count--;
	V(mutex);
	休息；
	P(mutex);
	Count++;
	V(mutex);
}

4-31 6个进程合作完成一项计算任务的并发描述如图4-38所示，程序中，s1、s2、s3、s4、s5、s6分别是同步信号灯，x、y、z是共享数据变量。试给出变量z的最终结果，并画出6个进程合作的进程流图。

答：

Z=12

4-32现有3个并发进程P1、P2和P3，如图4.39所示。3个并发进程共享两个单缓冲区B1和B2。进程P1负责不断从输入设备读数据，若读入的数据为正数，则直接送入B2，否则应先将数据送入B1，经P2取出加工后再送入B2，P3从B2中取信息输出。请使用信号灯和P、V操作描述进程P1、P2、P3实现同步的算法。

4-34某商场有一个地下停车场，有N个停车位，车辆只能通过一个指定的通道进出停车场，通道处只能容一辆车通过，请设计信号灯和P、V操作给出进、出车辆两种进程的程序描述。

答：

main()
{  
   int count1=count2=0;/*计数器*/
	   int mutex1=mutex2=1;/*两个计数器的互斥访问信号灯*/
    int mutex=1; /*通道互斥访问信号灯*/
  	cobegin
           in();
           out();
       coend
	}
in()
{
   P(empty);
	P(mutex1);
   Count1++;
   if  count1==0  P(mutex);
   V(mutex1);
   开车进地下停车场；
   P(mutex1);
   count1--;
 	if count1==0 V(mutex);
   V(mutex1);
}
out()
{
   P(mutex2);
   Count2++;
   if  count2==0  P(mutex);
   V(mutex2);
   开车出地下停车场；
   P(mutex2);
   Count2--;
 	if count2==0 V(mutex);
   V(mutex2);
   V(empty);
}