内容纲要

程序的执行

顺序执行

程序的顺序执行:把一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。程序的顺序性与计算机硬件的顺序性是一致的。

  • 顺序性:程序顺序执行时,其执行过程可看作一系列严格按程序规定的状态转移过程,也就是每执行一条指令,系统将从上一个执行状态转移到下一个执行状态,且上一条指令的执行结束是下一条指令执行开始的充分必要条件。
  • 封闭性:程序执行得到的最终结果由给定的初始条件决定,不受外界因素的影响。
  • 可再现性:顺序执行的最终结果可再现是指它与执行速度无关。只要输入的初始条件相同,则无论何时重复执行该程序都会得到相同的结果。

并发执行

程序的并发执行:是为了增强计算机系统的处理能力和提高资源利用率所采取的一种同时操作技术。

  • 间断性:竞争资源失败或时间片结束
  • 开放/交互性:失去封闭性,当程序执行时,必然受到其他程序的影响。
  • 不可再现性:结果多种可能

进程

进程定义

  • 一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。简言之,进程是程序的一次执行活动。它是操作系统动态执行的基本单元,在传统的操作系统中,进程既是基本的分配单元,也是基本的执行单元。(没有提出线程概念之前)
  • 进程描述了程序的动态执行过程;
  • 它对应虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收;
  • 反映系统中程序执行的并发性、随机性和资源共享;
  • 引入多进程,提高了对硬件资源的利用率,但又带来额外的空间和时间开销,增加了操作系统的复杂性。

进程特性

  • 动态性:(进程对应程序的执行、进程是动态产生:创建–运行–消亡、进程在其生命周期内,在内存三种基本状态之间转换,必要时还可能被挂起到外存)
  • 独立性:各进程的地址空间相互独立,除非采用进程间通信手段
  • 并发性:任何进程都可以同其他进程一起向前推进
  • 异步性:每个进程都以其相对独立的不可预知的速度向前推进
  • 结构化:进程=代码段+数据段+PCB(进程控制块)

进程与程序的区别:

  • 进程是动态的,程序是静态的;
  • 进程是暂时的,程序是永久的:进程是一个状态变化的过程,程序可长久保存;
  • 进程与程序的组成不同:进程的组成包括程序、数据和进程控制块(即进程状态信息);
  • 进程与程序的对应关系:通过多次执行,一个程序可对应多个进程;通过调用关系,一个进程可包括多个程序;
  • 进程具有并发特征,程序没有。进程具有独立性和异步性;
  • 进程是竞争计算机资源的基本单位。
  • 在计算机中处于运行状态的任何一个程序都是一个进程,一个进程拥有内存、CPU 时间等一系列资源。

进程组成

进程的组成:进程=程序+数据+进程控制块PCB(Process Control Block)

进程控制块:是由OS 维护的用来记录进程相关信息和管理进程而设置的一个专门的数据结构。

  • PCB 是进程动态特性的集中反映
  • PCB 结构的全部或部分常驻内存
  • PCB 随进程的创建而填写,随进程的撤消而释放
  • 系统利用PCB 来控制和管理进程,所以PCB 是系统感知进程存在的唯一标志
  • 进程与PCB 是一一对应的

进程控制块的内容包括:

  1. 进程描述信息进程标识符 (process ID),唯一,通常是一个整数
    进程名,通常基于可执行文件名
    用户标识符 (user ID)
    进程组关系 (process group)
  2. 进程控制信息当前状态
    优先级 (priority)
    代码执行入口地址
    程序的外存地址
    运行统计信息(执行时间、页面调度)
    进程间同步和通信,阻塞原因
  3. 资源占用信息虚拟地址空间的现状、打开文件列表
  4. CPU 现场保护结构寄存器值(通用、程序计数器PC、状态PSW,地址包括栈指针)

进程上下文:是对进程执行活动全过程的静态描述。进程上下文由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成(正文段、数据集、堆栈)。

  • 用户级上下文:进程的用户地址空间(包括用户栈各层次),包括用户正文段、用户数据段和用户栈;
  • 寄存器级上下文:程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值;
  • 系统级上下文:静态部分(PCB 和资源表格);动态部分:核心栈(核心过程的栈结构,不同进程在调用相同核心过程时有不同核心栈)。

进程控制块可以采用链表、索引表等组织方式。

进程状态及转换

三态模式:

三态模式

五态模式:

五态模式

七态模式:

七态模式

为什么要有“挂起”状态?

由于进程的不断创建,系统资源已不能满足进程运行的要求,就必须把某些进程挂起(suspend),对换到磁盘镜像区中,暂时不参与进程调度,起到平滑系统操作负荷的目的。

进程控制

进程控制:系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换,从而达到多进程高效率并发执行和协调、实现资源共享的目的。

CPU的运行模式

  • 核心态(内核态),也称为管态 (操作系统内核代码、设备驱动等)
  • 用户态,也称为目态 (CPU保护模式、执行部分普通指令)

原语:一般地,把系统态下执行的某些具有特定功能的程序段称为原语。

  • 机器指令级的原语,其特点是执行期间不允许中断,正如在物理学中的原子一样,在操作系统中,它是一个不可分割的基本单位。
  • 功能级的原语,其特点是作为原语的程序段不允许并发执行。

进程控制原语:

  1. 创建进程:操作系统创建进程主要步骤,导致创建进程的事件
  2. 撤消与终止进程:撤销原语撤销的是PCB,而非进程的程序段
  3. 阻塞与唤醒进程:进程阻塞是进程的自主行为,唤醒则是被动的
  4. 挂起与激活进程:既可以由该进程自己调用,也可由其它进程或系统调用,但激活原语只能由其它进程或系统调用

同步与互斥

进程的互斥与同步:竞争和协作

并发执行的两种制约关系:直接制约关系、间接制约关系

直接制约关系:进程需等待来自其他进程的信息而产生的协作关系。进程间的相互联系是有意识的安排的,直接作用只发生在相关进程间。

进程的同步(直接作用):指系统中一些进程需要相互合作,共同完成一项任务。具体说,一个进程运行到某一点时要求另一伙伴进程为它提供消息,在未获得消息之前,该进程处于等待状态,获得消息后被唤醒进入就绪态。

间接制约关系:是指进程独占分配到的部分或全部共享资源(共享变量)而产生的竞争关系。进程间要通过某种中介发生联系,是无意识安排的,可发生在相关进程之间,也可发生在无关进程之间。

进程同步机制遵循的准则:

  1. 空闲让进
  2. 忙则等待
  3. 有限等待
  4. 让权等待

进程的互斥(间接作用):由于各进程要求共享资源,而有些资源需要互斥使用,即多个进程不能同时使用同一个资源,因此各进程间竞争使用这些资源,进程的这种关系为进程的互斥。

临界资源:系统中某些资源一次只允许一个进程使用,这样的资源为临界资源或互斥资源或共享变量。

临界区:把每个进程中访问临界资源的那段代码称为临界区。

软件方法管理临界区:

算法1:单标志
基本思想是设立一个公用整型变量 turn,描述允许进入临界区的进程标识:

  • 在进入区循环检查是否允许本进程进入:turn 为 i 时,进程Pi 可进入;
  • 在退出区修改允许进入进程标识:进程Pi 退出时,改turn为进程Pj 的标识j。

算法一

缺点:是强制两个进程轮流进入临界区,在Pi 出让临界区之后,Pj 使用临界区之前,Pi 不可能再次使用临界区。没有考虑进程的实际需要。容易造成资源利用不充分。

算法2:双标志、先检查
基本思想是设立一个标志数组flag[]:描述进程是否在临界区,初值均为FALSE,表示进程不在临界区。

  • 先检查,后修改:在进入区检查另一个进程是否在临界区,不在时修改本进程在临界区的标志;
  • 在退出区修改本进程在临界区的标志。

算法二

优点:不用交替进入,可连续使用;
缺点: Pi 和 Pj 可能同时进入临界区。在Pi 和 Pj 都不在临界区时,假设按 “Pi; Pj ;
Pi; Pj”的顺序并发执行时,会同时进入临界区。即在检查对方flag 之后发生进程切换,结果都通过检查。这里的问题出在检查和修改操作不能连续进行。

算法3:双标志、后检查

算法三

算法3 类似于算法2,与算法2 的区别在于先修改后检查。可防止两个进程同时进入临界区。其缺点为:Pi 和Pj 可能都进入不了临界区。在Pi 和Pj 都不在临界区时,假设按 Pi Pj Pi Pj顺序并发执行时,会都进不了临界区,即在设置进入临界区的标志后发生进程切换,结果检查都不能通过。

算法4 (Peterson’s Algorithm):先修改、后检查、后修改者等待
基本思想是在进入区先修改后检查,并检查并发修改的先后:

  • 检查对方flag,如果不在临界区则自己进入——空闲则入;
  • 否则再检查turn:保存的是较晚的一次赋值,则较晚的进程等待,较早的进程进入,即先到先入,后到等待。

算法四

算法4 结合算法1 和算法3,是正确的算法。当同时修改标志时,采用标志turn 描述可进入的进程。

硬件方法管理临界区:

  • 禁止中断法
  • 特殊指令法

1、Test-and-Set 指令(TS 指令):该指令读出标志后将其设置为TRUE:

TS指令

2、Swap 指令(或Exchange 指令):可保证在一个指令周期内交换一个寄存器和一个存储单元内容

Swap指令

进程同步机制:常见的同步机制有锁、信号量、管程和消息传递等。

信号量

信号量:信号量(semaphore)是一个数据结构,是一种卓有成效的进程同步机制。信号量就是OS 提供的管理公有资源的有效手段。信号量的值代表可用资源实体的数量。定义如下:

typedef struct {
    int count;
    Pointer_PCB Queue;
} Semaphore;

信号量在始化时被指定一个非负整数值,表示空闲资源总数(又称为“资源信号量”),在进程执行过程中,信号量的值(即其计数值)可能发生变化:

  • 若为非负值,表示当前的空闲资源数;
  • 若为负值,其绝对值表示当前等待临界区的进程数。

对于“二进制信号量(binary semaphore)”,只允许信号量取0 或1 值。

利用信号量实现互斥的过程是:

利用信号量实现互斥的过程

P 原语–P(s) 或wait(s),在互斥问题中,申请使用临界资源时调用P 原语,其实现原理为:

P(Semaphore s)
{
  --s.count; //表示申请一个资源;
  if (s.count <0) //表示没有空闲资源;
  {
    //调用进程进入等待队列s.queue;
    //阻塞调用进程;
  }
}

V 原语—V(s) 或 signal(s),V 原语通常唤醒进程等待队列中的头一个进程,其实现原理为:

V(Semaphore s )
{
  ++s.count; //表示释放一个资源;
  if (s.count <= 0) //表示有进程处于阻塞状态;
  {
    //从等待队列s.queue 中取出一个进程P;
    //进程P 进入就绪队列;
  }
}

利用信号量实现互斥,需要注意的是:

  • 必须成对使用P 和V 原语:遗漏P 原语则不能保证互斥访问;遗漏V 原语则不能在使用临界资源之后将其释放(给其他等待的进程);
  • P、V 原语不能出现次序错误、重复或遗漏。

P 操作实现:

P(s)
  BEGIN
    封锁中断;
    lock(lockbit);
    --s.count; //表示申请一个资源;
    if (s.count <0) //表示没有空闲资源;
    { 
      //调用进程进入等待队列s.queue;
      //阻塞调用进程;
    }
    unlock(lockbit);
    开放中断;
  END;

V 操作实现:

V(s)
  BEGIN
    封锁中断;
    lock(lockbit);
    ++s.count;
    if (s.count <= 0)
    { 
      //从等待队列s.queue 中取出一个进程P;
      //进程P进入就绪队列;
    }
    unlock(lockbit);
    开放中断;
  END;

信号量集:信号量集主要用于同时需要多个资源时的信号量操作,包括:AND 型信号量集和一般信号量集。

AND 型信号量集:AND 型信号量集用于同时需要多种资源且每种占用一个时的信号量操作。基本思想是将一段代码同时需要的多个临界资源,要么全部分配给它,要么一个都不分配。其实现原理为:

Swait (S1,S2,…,Sn){
    while (true){
        if (S1>=1 && S2>=1 && … && Sn>=1){
            for (i=1; i<=n; ++i) --Si;
                break;
            }
        else{
            //调用进程进入第一个小于1 信号量的等待队列Sj.queue;
            //阻塞调用进程;
        }
    }
}
Ssignal (S1,S2,…,Sn){
    for (i=1; i<=n; ++i){
        ++Si;
    for (each process P waiting in Si.queue){
        //从等待队列Si.queue 中取出进程P;
        if (进程P 通过Swait 中的测试)
            //进程P 进入就绪队列
        else
            //进程P 进入某等待队列;
        }
    }
}

一般信号量集:一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理。其调用形式为:

Swait(S1,t1,d1;…;Sn,tn,dn) (或SP)
Ssignal(S1,d1;…;Sn,dn) (或SV)

经典互斥与同步问题:生产者-消费者问题

问题描述:若干进程通过有限的共享缓冲区交换数据。其中,生产者进程不断写入,而消费者进程不断读出;共享缓冲区共有N 个;任何时刻只能有一个进程可对共享缓冲区进行操作。

  • 任何时刻只能有一个进程可对共享缓冲区进行操作,可知使用共享缓冲区的生产者与生产者之间、生产者与消费者之间以及消费者与消费者之间存在互斥关系。
  • 缓冲区不满,生产者才能写入;缓冲区不空,消费者才能读出,可知生产者与消费者之间存在同步关系。

设置如下信号量:
full 是“满”缓冲区数目,初值为0;
empty 是“空”缓冲区数目,初值为N;
mutex 用于访问缓冲区时的互斥,初值是1 。
实际上,full 和 empty 是同一个含义:full + empty == N。

用信号量和P、V 原语解决生产者-消费者问题如下:

生产者,消费者

操作的顺序很重要,不当会产生死锁。如假定Producer 和Consumer 如下:

生产者,消费者死锁

当full=0, mutex = 1 时,如果执行顺序为:
Consumer.P(mutex) ; Consumer.P(full); // C 阻塞,等待Producer 发出的full 信号
Producer.P(empty) ; Producer.P(mutex) ; // P 阻塞,等待Consumer 发出的mutex 信号
此时将出现死锁 。

经典进程同步问题:读者-写者问题(the readers-writers problem)

问题描述:对共享资源的读写操作,任一时刻“写者”最多只允许一个,而“读者”则允许多个,要求:“读-写” 互斥,“写-写” 互斥,“读-读” 允许

  • 只要一个reader 进程在读,便不允许writer 进程去写;
  • 仅当Rcount=0,reader 进程才需要执行P(Wmutex)操作;
  • 仅当reader 进程执行了Rcount 减1 操作后,其值为0 时,才须执行V(Wmutex)操作。

设置如下信号量:
Wmutex 表示“允许写”,初值是1;
Rmutex 表示对Rcount 的互斥操作,初值是1。
公共变量Rcount 表示“正在读”的进程数,初值是0。

用信号量和P、V 原语解决读者-写者问题如下:

读者-写者问题

经典进程互斥同步问题:哲学家进餐问题(the dining philosophers problem)

问题描述:(由Dijkstra 首先提出并解决)5 个哲学家围绕一张圆桌而坐,桌子上放着5 支筷子,每两个哲学家之间放一支,哲学家的动作包括思考和进餐,进餐时需要同时拿起他左边和右边的两支筷子,思考时则同时将两支筷子放回原处。

  • 不出现相邻者同时要求进餐;
  • 不出现有人永远拿不到筷子。

哲学家的生活规律是:

Repeat
  思考;
  取fork[i];取fork[(i+1) mod 5];
  进食;
  放fork[i];放fork[(i+1) mod 5];
Until false;

实现方法:一个信号量表示一根筷子,五个信号量构成信号量数组chop[5],所有信号量初始值为1。第i 个哲学家的进餐过程为:

思考问题
P(chop[i]);
P(chop(i+1) mod 5]);
进餐
V(chop[i]);
V(chop[(i+1) mod 5]);
//该算法可保证两个相邻的哲学家不能同时进餐,但不能防止五位哲学家同时拿起各自左
边的筷子、又试图拿起右边的筷子,这会引起死锁。

防止死锁发生的解决方案:

Semaphore fork[5] = {1};
Semaphore room = 4;
Void philospher (int i) {
  while (true) {
    thinking();
    P( room );
    P(fork[i]);
    P(fork[(i+1) mod 5])
    eating();
    V(fork[i]);
    V(fork[(i+1) mod 5])
    V(room); 
  }
}

管程

管程:是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。

基本思想:是把信号量及其操作原语封装在一个对象内部。即:将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。

管程的组成:

  • 管程的名称
  • 局部于管程内部的共享数据结构说明
  • 对该数据结构进行操作的一组过程
  • 对局部于管程内部的共享数据设置初始值的语句

管程的特点:

  • 模块化-管程是一个基本程序单位,其中不仅有数据,还有对数据的操作;
  • 隐蔽性-进程若想进入管程,必须调用管程内的某个过程;其内部的局部数据变量只能被管程内定义的过程所访问,不能为管程外声明的过程直接访问;
  • 互斥性-一次只能有一个进程在管程内执行,其余调用该管程的过程均被挂起,等待该管程成为可用的;管程能有效地实现互斥。

管程和进程的异同点:

  • 设置进程和管程的目的不同
  • 管理的数据结构不同,进程:PCB,管程:等待队列
  • 管程被进程调用
  • 管程是操作系统的固有成分,无创建和撤消
  • 进程之间能并发执行,而管程不能与其调用并发

进程通信

进程通信:是进程之间数据的相互交换和信息的相互传递,是一种高级通信机制。主要包括消息传递(message passing)通信、共享内存(shared memory)通信和管道(pipe)通信。

进程间通信可分为4种形式:

  • 主从式;
  • 会话式;
  • 消息或邮箱机制;
  • 共享存储区方式。

消息或邮箱机制:消息缓冲区构成了进程通信的一个基本单位,消息通信中存在直接通信与间接通信两种类型。

特点:

  • 只要存在空缓冲区或邮箱,发送进程就可以发送消息。
  • 与会话系统不同,发送进程和接收进程之间无直接连接关系,接收进程可能在收到某个发送进程发来的消息之后,又转去接收另一个发送进程发来的消息。
  • 发送进程和接收进程之间存在缓冲区或邮箱用来存放被传送消息。

邮箱通信:邮箱通信就是由发送进程申请建立一个与接收进程链接的邮箱。发送进程把消息送往邮箱,接收进程从邮箱中取出消息,从而完成进程间的信息交换。设置邮箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制。一个邮箱可考虑成发送进程与接收进程之间的大小固定的私有数据结构,它不像缓冲区那样被系统内所有进程共享。

共享存储区方式:

相互通信的进程共享某些数据结构或共享存储区。一组进程向该公共区中写,另一组进程从公共区中读,又可进一步分为:基于共享数据结构的通信方式和基于共享存储区的通信方式。

管道:是一条在进程间以字节流方式传送的通信通道,它由OS 核心的缓冲区(通常几十KB)来实现,是单向的。在使用管道前要建立相应的管道,然后才可使用。

UNIX 系统中,通过pipe 系统调用创建无名管道,得到两个文件描述符,分别用于写和读。具体调用形式为:
int pipe(int fildes[2]);
其中,文件描述符fildes[0]为读端,fildes[1]为写端。
通信时,通过系统调用write 和read 进行管道的写和读。
如果进程间需要双向通信,通常需要两个管道。

最后修改日期:2020年7月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。