程序的顺序与并发执行

顺序程序及特点

• 计算：程序的一次执行过程称为一个计算，它由许多简单操作所组成。

• 程序的顺序执行：一个计算的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。顺序的含义不但指一个程序的内部，也指两个模块之间。

• 顺序程序的特点

  • 单道系统的工作情况

    对用户作业的处理——首先输入用户的程序和数据；然后进行计算；最后打印计算结果，即有三个顺序执行的操作。

  • 顺序程序的特点

    顺序性——处理机的操作严格按照程序所规定的顺序执行。

    封闭性——程序一旦开始执行，其计算结果不受外界因素的影响。

    可再现性——程序执行的结果与它的执行速度无关（即与时间无关），而只与初始条件有关。

并发程序

并发的引入

——多道作业的工作分析

对\(n\)个用户的作业处理：

什么是程序的并发执行

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

三个并发执行的程序段：

并行语句记号：

cobegin
S1;S2;...;Sn;
coend//各个程序段以不可预知的次序运行

从宏观上看，一个时间段中几个程序都在同一处理器上，处于运行还未结束的状态。

从微观上看，任一时刻仅有一个程序在处理器上运行。

并发的实质是一个处理器在几个程序之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。

并发程序的特点

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

  顺序程序具有封闭性特征，即程序一旦开始执行，其计算结果不受外界因素的影响，与它的执行速度无关（即与时间无关）。这是因为程序的变量是其他程序执行时不可接触的，所以这个程序执行后的输出结果是其输入的一个与时间无关的函数。若一个程序的执行可以改变另一个程序的变量，那么后者的输出就可能有赖于各程序执行的相对速度，即失去了程序的封闭性特点。不同的速度会导致输出结果不一致就会导致程序不可再现。

• 程序与计算不再一一对应

  当多个计算任务共享某个程序时，它们都可以调用这个程序，且调用一次就是执行一次计算，因而这个程序可执行多次，即这个共享的程序对应多个计算。

• 程序并发执行的相互制约

  间接的相互制约关系——资源共享

  直接的相互制约关系——公共变量

与时间有关的错误

定义：程序并发执行时，若共享了公共变量，其执行结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误。

进程概念

定义：所谓进程，就是一个程序在给定活动空间和初始环境下，在一个处理机上的执行过程。进程是操作系统中最基本、最重要的概念。是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念，所有多道程序设计操作系统都建立在进程的基础上。

从理论角度看，进程是对正在运行的程序过程的抽象；从实现角度看，进程是一种数据结构，目的在于清晰地刻画动态系统的内在规律，有效管理和调度进入计算机系统主存储器运行的程序。

进程与程序的区别

• 程序是静态的概念，进程是动态的概念。程序可以作为一种软件资料长期保存，而进程则是有一定生命期的，它能够动态地产生和消亡。即进程可由创建而产生，由调度而执行，因得不到资源而暂停，以致最后由撤销而消亡。
• 进程是一个独立运行的活动单位
• 进程是竞争系统资源的基本单位
• 一个程序可以对应多个进程，一个进程至少包含一个程序

进程的状态

进程的三个基本状态

• 运行状态（running）：该进程已获得运行所必需的资源，它的程序正在处理机上执行。
• 等待状态（wait）：进程正等待着某一事件的发生而暂时停止执行。这时即使给它CPU控制权，它也无法执行。
• 就绪状态（ready）：进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行。

进程状态的变迁

• 进程状态可能的变迁

  

• 具有进程基本状态的变迁图

  

• 进程五个状态及其转换

  

• 具有挂起状态的进程状态变迁图

  

进程描述

什么是进程控制块

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

进程的组成

• 程序与数据：描述进程本身所应完成的功能
• PCB：进程的动态特征，该进程与其他进程和系统资源的关系

进程控制块的主要内容

• 进程标识符——进程符号名或内部id号
• 进程当前状态——本进程目前处于何种状态
• 当前队列指针next——该项登记了处于同一状态的下一个进程的PCB地址
• 进程优先级——反映了进程要求CPU的紧迫程度
• CPU现场保护区——当进程由于某种原因释放处理机时，CPU现场信息被保存在PCB的该区域中
• 通信信息——进程间进行通信时所记录的有关信息
• 家族联系——指明本进程与家族的联系
• 占有资源清单

进程控制

进程控制的概念

进程控制的职责

进程控制的职责：对系统中的进程实施有效的管理，负责进程状态的改变。

• 进程状态变化

  无→创建→有→撤销→消亡

  运行→等待→等待

  就绪←唤醒←等待

• 常用的进程控制原语

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

进程创建

• 进程创建原语的形式——create（name ， priority）

  • name——为被创建进程的标识符
  • priority——为进程优先级

• 进程创建原语的功能：创建一个具有指定标识符的进程，建立进程的PCB结构。

• 进程创建原语的实现

  

进程撤销

• 进程撤销原语的形式：当进程完成任务后希望终止自己时使用进程撤销原语Kill（或exit）
• 进程撤销原语的功能： 撤消当前运行的进程。将该进程的PCB结构归还到PCB资源池，所占用的资源归还给父进程，从总链队列中摘除它，然后转进程调度程序。
• 进程撤销原语的实现
  

进程等待

• 进程等待原语的形式：当进行需要等待某一事件完成时，它可以调用等待原语挂起自己。

  susp（chan）

  入口参数chan：进程等待的原因

• 进程等待原语的功能：中止调用进程的执行，并加入到等待chan的等待队列中；最后使控制转向进程调度。

• 进程等待原语的实现

  

进程唤醒

• 进程唤醒原语的形式

  当处于等待状态的进程所期待的事件来到时，由发现者进程使用唤醒原语唤醒它。

  wakeup（chan）

  入口参数chan：进程等待的原因

• 进程唤醒原语的功能：当进程等待的事件发生时，唤醒等待该事件的进程

• 进程唤醒原语的实现

  

进程之间的相互制约关系

进程互斥的概念

当两个进程公用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。

临界资源

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

硬件：如输入机、打印机、磁带机等

软件：如公用变量、数据、表格、队列等

临界区

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

互斥

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

进程同步的概念

什么是进程同步

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

同步的例子

共享缓冲区的计算进程与打印进程的同步

进程同步机构

锁和上锁、开锁操作

什么是锁

用变量w代表某种资源的状态，w称为锁。

上锁操作和开锁操作

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

进程使用临界资源的操作

上锁原语和开锁原语

• 上锁原语

  算法 lock

  输入：锁变量w

  输出：无

  {

  test ： if(w为1)//测试锁位的值

  goto test：

  else w = 1;//上锁

  }

• 开锁原语

  算法：unlock

  输入：锁变量w

  输出：无

  {

  w = 0；//开锁

  }

信号灯和P、V操作

什么是信号灯

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

信号灯是整型变量。变量值大于等于0时，表示绿灯，进程执行。变量值小于0时，表示红灯，进程停止执行。注意：创建信号灯时，应准确说明信号灯s的意义和初值（这个初值绝不能为负值）。

P操作

定义：对信号灯s的 p操作记为 p(s)。p(s)是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用p(s)的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。

V操作

定义：对信号灯s的 v操作记为 v(s)。v(s)是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队列上的一个进程。

进程互斥与同步的实现

上锁原语和开锁原语实现进程互斥

用信号灯的P、V操作实现互斥

两类同步问题的解法

合作进程的执行次序

有一个表达式Z = (x+1)*(y+1)的计算任务(x,y初始值为1)，假设每个运算符操作分别对应一个进程，设计完成该表达式计算任务的多进程并发执行的实现方案，并给出类C程序描述。

main() {
	int x=1;
	int y=1;
	cobegin
	p1();p2();p3();
	coend
}
p1() {
	x = x+1;
}
p2() {
	y = y+1;
}
p3() {
	z=x+y;
}

进程流图：描述一组合作进程执行的先后次序的有向图

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

计算进程 cp和打印进程 iop公用一个单缓冲，为了完成正确的计算与打印，试用信号灯的p、v操作实现这两个进程的同步。

• 两个进程的任务

  计算进程cp经过计算，将计算结果送入buf；打印进程iop把buf中的数据取出打印。

• 分析任务的同步关系

  当cp进程把计算结果送入buf时，iop进程才能从buf中取出结果去打印，否则必须等待。当iop进程把buf中的数据取出打印后，cp进程才能把下一个计算结果数据送入buf中，否则必须等待。

• 信号灯设置

  \(s_a\)：表示缓冲区中是否有可供打印的计算结果，其初值为0。

  \(s_b\)：表示缓冲区有无空位置存放新的信息，其初值为1。

• 同步描述

  

• 程序描述
  

生产者——消费者问题

生产者——消费者问题的例子

• 计算进程和打印进程：计算进程cp不断产生数据，是生产者；打印进程iop不断打印数据，是消费者。
• 通信问题：发送消息进程send不断产生消息，是生产者；收消息进程receive不断接收消息，是消费者。

生产者——消费者问题的一般解答

• 生产者——消费者问题图示
  

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

  • 生产者：当有界缓冲区中无空位置时，要等待；向有界缓冲区放入物品后，要发消息。
  • 消费者：当有界缓冲区中无空位置时，需要等待；从有界缓冲区取出物品后，要发消息。

• 信号灯设置

  • 两个同步信号灯：

    \(s_b\)：表示空缓冲区的数目，初值为\(n\)；\(s_a\)：表示满缓冲区的数目，初值为\(0\)。

  • 一个互斥信号灯

    mutex：表示有界缓冲区是否被占用，初始值为\(1\)。

• 同步描述

  

• 程序描述

  
  

进程通信

进程通信的概念

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

进程通信方式

消息缓存通信

在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区。在消息通信中，接收方和发送方之间有明确的协议和消息格式。消息缓冲通信方式包括消息缓冲、发送原语和接收原语。

消息缓冲区结构

• 消息头：含控制信息如：收/发进程名，消息长度、类型、编号。
• 消息长度：定长消息：系统开销小，用户不便变长消息：开销大，用户方便。
• 消息正文

消息队列

消息缓冲区构成队列，PCB中增加指针消息队列指针。

基于有界缓冲区的消息通信

在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行。

在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行。

信箱通信——实现非实时通信

在信箱通信中，需要定义信箱结构，还包括消息发送和接收功能模块，提供发送原语和接收原语。 信箱通信中，所使用的信箱可以位于用户空间中，是接收进程地址空间的一部分；也可以放置在操作系统的空间中。

线程概念及特点

什么是线程

定义：线程是比进程更小的活动单位，它是进程的一个执行路径。

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

线程的内存布局：

线程的特点

线程是比进程更小的活动单位，它是进程中的一个执行路径。创建一个线程比创建一个进程开销要小得多。实现线程间通信十分方便，因为一个进程创建的多个线程可以共享地址区域和数据。线程是一个动态的概念。在进程内创建多线程，可以提高系统的并行处理能力，加快进程的处理速度。

线程的状态变迁

操作系统的并发机制实例

创建进程及应用实例

调用形式

int pid = fork（）；

功能：创建一个子进程，被创建的子进程是父进程的进程映像的一个副本（除proc结构外），在UNIX系统中，除了0#进程外，其它进程都是通过调用进程创建系统调用创建的。

返回值：-1 创建失败；0 从子进程返回； > 0 从父进程返回，且返回值为子进程号。

系统调用fork完成的操作

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

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

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

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

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

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

等待进程、线程的终止及其应用

等待进程、线程终止

wait(); waitpid(); pthread_join();

• wait（）语法格式

  pid=wait(stat_addr);wait()函数使父进程暂停执行，直到它的一个子进程结束为止，该函数的返回值是终止运行的子进程的PID。参数status所指向的变量存放子进程的退出码，即从子进程的main函数返回的值或子进程中exit()函数的参数。如果status不是一

  个空指针，状态信息将被写入它指向的变量。

• waitpid（）语法格式

  waitpid(pid_t pid,int * status,int options)用来等待子进程的结束，但它用于等待某个特定进程结束。参数pid指明要等待的子进程的PID，参数status的含义与wait()函数中的status相同。

• 线程等待：等待一个线程的结束

  int pthread_join __P ((pthread_t __th, void **__thread_return));

  _th被等待的线程标识符， __thread_return为一个用户定义的指针，它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回。