操作系统 第二章进程描述与控制

2.1 前驱图和程序执行

2.1.1 前趋图

前趋图(Precedence Graph)是指一个有向无循环图,记为 DAG(Directed Acyclic Graph),它用于描述进程之间执行的先后顺序。

注意:前趋图中是不允许有循环的,所以上图右边是错误的。 #### 2.1.2 程序顺序执行

  1. 程序的顺序执行

    通常一个应用程序由若干个程序段组成,每个程序段完成特定的功能,按照某种先后次序顺序执行。

  2. 程序顺序执行时的特征

    • 顺序性,严格按照顺序执行;
    • 封闭性,封闭环境下运行,独占全集资源,结果不受外界干扰;
    • 可再现性,程序重复执行,得到相同结果。

2.1.3 程序并发执行

  1. 程序并发执行

    不存在前驱关系的程序之间才有可能并发执行。

  2. 程序并发执行时的特征

    • 间断性,相互合作、相互制约,“执行——暂停——执行”;
    • 失去封闭性,系统资源共享,状态也随之改变;
    • 不可再现性,失去封闭性->失去可再现性。

2.2 进程的描述

2.2.1 进程的定义和特征

  1. 进程的定义

    为了能够使程序并发执行,并且可以对并发执行的程序加以描述和控制,引入“进程”的概念。

    为了使参与并发执行的每个程序(含数据)都能独立地运行,在操作系统中必须为之配置一个专门的数据结构——进程控制模块(Process Control Block, PCB)。系统利用 PCB 来描述进程的基本情况和活动过程。

    进程——进程实体(进程映像):程序段、相关数据段、PCB。

    创建进程——创建进程实体中的 PCB;撤销进程——撤销进程的 PCB。

    定义传统 OS 中的进程:进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。

  2. 进程的特征

    进程和程序截然不同,进程有 PCB 结构,还具有:

    • 动态性,最基本特征,进程的实质是进程实体的执行过程,“由创建产生,由调度执行,由撤销消亡”,进程实体有一定的生命周期,而程序是静态的,只是一组有序指令的合集;
    • 并发行,多个进程实体同存于内存中,能在一段时间内同时运行。程序(没有建立 PCB) 是不能残余并发执行的,走走停停
    • 独立性,进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位;
    • 异步性,异步方式,即各自独立的、不可预知的速度向前推进。

2.2.2 进程的基本状态及转换

  1. 进程的三种基本状态

    每个进程至少应该处于以下三个基本状态之一:

    • 就绪(Ready) 状态,进程已分配到除 CPU 外的所有必要资源,只要获得 CPU 就执行。若系统中有多个就绪状态的进程,砸按一定的策略排成一个队列——就绪队列;
    • 执行(Running)状态,进程已获得 CPU,正在执行;
    • 阻塞(Block)状态,执行的进程由于某事件暂时无法继续执行。此时引起进程调度。也有阻塞队列的说法,也称等待状态或封锁状态。
  2. 三种基本状态的转换

  3. 创建状态和终止状态

    • 创建状态

      进程由创建产生,步骤:

      1. 首先由进程申请一个空白 PCB;
      2. 再向PCB中填写用于控制和管理进程的信息;
      3. 然后为该进程分配运行时所必须的资源;
      4. 最后,把该进程转入就绪状态并插入就绪队列之中。

      但如果进程所需的资源尚不能得到满足,比如系统尚无足够的内存使进程无法装入其中,此时创建工作尚未完成,进程不能被调度运行,于是把此时进程所处的状态称为创建状态。

    • 终止状态

      步骤:

      1. 首先,是等待操作系统进行善后处理;
      2. 最后将其PCB清零,并将PCB空间返还系统。

2.2.3 挂起操作和进程状态的转换

  1. 挂起操作的引入

    • 终端用户的需要
    • 父进程的需要
    • 符合调节的需要
    • 操作系统的需要
  2. 引入挂起原语操作后三个进程状态的转换

    引入挂起原语 Suspend 和激活原语 Active 后,进程可能发生以下几种状态的转换:

    • 活动就绪 -> 静止就绪。Readya——未被挂起的就绪状态——活动就绪状态,此时可接受调度;挂起后,Readys——静止就绪状态——不再被调度执行。
    • 活动阻塞 -> 静止阻塞。Blockeda——未被挂起的阻塞状态——活动阻塞状态,在期待的事件出现后;挂起后,Blockeds——静止阻塞状态;期待的事情出现后,变为静止就绪状态。
    • 静止就绪 -> 活动就绪。Readys + Active -> Readya.
    • 静止阻塞 -> 活动阻塞。Blockeds + Active -> Blockeda.
  3. 引入挂起操作后五个进程状态的转换

    • NULL -> 创建:新进程的产生。
    • 创建 -> 活动就绪:系统的内存和性能允许的情况下,完成对进程创建的必要操作后。
    • 创建 -> 静止就绪:考虑系统的内存和性能,不分配给新建进程资源(主要是内存),被安置在外存,不参与调度,进程创建未完成。
    • 执行 -> 终止:进程已经完成任务,或出现无法克服的困难,或被 OS 或其他进程所终结。

2.2.4 进程管理中的数据结构
  1. 操作系统中用于管理控制的数据结构

    OS 对每个资源和每个进程都设置一个数据结构,称为资源信息表进程信息表。通常将其分为以下四类:内存表、设备表、文件表和用于进程管理的进程表(PCB)。

  2. 进程控制块 PCB 的作用

    • 作为独立运行基本单位的标志。

    • 能实现间断性运行方式。
    • 提供进程管理所需要的信息。
    • 提供进程调度所需要的信息。
    • 实现与其它进程的同步与通信。

  3. 进程控制块中的信息

    • 进程标识符

      唯一地标识一个进程,一个进程通常两种标识符:

      • 外部标识符,方便用户(进程)对进程的访问。
      • 内部标识符,方便系统对进程的使用。
    • 处理机状态

      处理机的上下文,由各种寄存器中的内容组成。

    • 进程调度信息

      进程状态、进程优先级、进程调度所需的其他信息、事件

    • 进程控制信息

      程序和数据的地址、进程同步和通信机制、资源清单、链接指针

  4. 进程控制块中的组织方式

    • 线性方式

      线性表存储。

    • 链接方式

      把具有相同状态进程的 PCB 分别通过 PCB 中的链接字链接成一个队列。

    • 索引方式

      系统根据所有进程状态的不同,建立几张索引表。

2.3 进程控制

2.3.1 操作系统内核

  1. 支撑功能
    • 中断处理,最基本,OS 活动的基础。
    • 时钟管理,时间控制。
    • 原语操作,原语(Primitive),是由若干条指令组成的,用于完成一定功能的一个过程,它是”原子操作“区别于一般过程。”原子操作“指,一个操作中的所有动作要么全做,要么全不做。即不可分割的基本单位。因此,原语的执行过程不允许被中断。
    1. 资源管理功能
      • 进程管理,将它们放在内核中,提高 OS 的性能。
      • 存储器管理,也放在内核中,以保证存储器管理具有较高的运行速度。
      • 设备管理,也放在内核中。

2.3.2 进程的创建

  1. 进程的层次结构

    OS 允许一个进程创建另一个进程,父进程和子进程。

  2. 进程图

  3. 引起创建进程的事件

    用户登录、作业调度、提供服务、应用请求。

  4. 进程的创建

    OS 调用进程创建原语 Creat 按下属步骤创建一个新进程:

    1. 申请空白 PCB。
    2. 为新进程分配其运行所需要的资源。
    3. 初始化 PCB。
    4. 如果进程就绪队列能够接纳新进程,便将新进程插入就绪队列。

2.3.3 进程的终止

  1. 引起进程终止的事件

    正常结束、异常结束、外界干预。

  2. 进程的终止过程

    如果系统中发生了要求终止进程的某事件,OS便调用进程终止原语,按下述过程去终止指定的进程:

    1. 根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态;
    2. 若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真,用于指示该进程被终止后应重新进行调度;
    3. 若该进程还有子孙进程,还应将其所有子孙进程也都予以终止,以防它们成为不可控的进程;
    4. 将被终止进程所拥有的全部资源或者归还给其父进程,或者归还给系统;
    5. 将被终止进程(PCB)从所在队列(或链表)中移出,等待其它程序来搜集信息。

2.3.4 进程的阻塞与唤醒

  1. 引起进程阻塞和唤醒的事件

    向系统请求共享资源失败、等待某种操作的完成、新数据尚未到达、等待新任务的到达。

  2. 进程阻塞过程

    若发生上述事件,则调用阻塞原语 block 将自己阻塞。阻塞是进程自身的一种主动行为。

  3. 进程唤醒过程

    当被阻塞进程所期待的事件发生时,则由有关进程调用唤醒原语 wakeup,将等待该事件的进程唤醒。

2.3.5 进程的挂起与激活

  1. 进程的挂起过程

    当出现了引起进程挂起的事件时,系统将利用挂起原语 suspend 将指定进程挂起。挂起原语的执行过程是:

    • 检查被挂起进程的状态:若正处于活动就绪状态,便将其改为静止就绪;
    • 对于活动阻塞状态的进程,则将其改为静止阻塞;
    • 为了方便用户或父进程考查该进程的运行情况,而把该进程的 PCB复制到某指定的内存区域;
    • 最后,如被挂起的进程正在执行,则转调度程序重新调度。
  2. 进程的激活过程

    当发生激活过程的事件时,若进程驻留在外存而内存中已有足够的空间,则可将在外存上处于静止就绪状态的进程换入内存。这时,系统将利用激活原语 active 将指定进程激活。

    • 先将进程从外存调入内存,检查该进程的现行状态:若是静止就绪,便将其改为活动就绪;若为静止阻塞,便将其改为活动阻塞。
    • 假如采用的是抢占调度策略,则每当有新进程进入就绪队列时,应检查是否要进行重新调度,即由调度程序将被激活进程与当前进程进行优先级的比较,如果被激活进程的优先级更低,就不必重新调度;否则,立即剥夺当前进程的运行,把处理机分配给刚被激活的进程。

2.4 进程同步

2.4.1 进程同步的基本概念

主要任务是对多个相关进程在执行次序熵进行协调,使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源,并能很好合作,从而使程序的执行具有可再现性。

  1. 两种形式的制约关系

    • 间接相互制约关系

      多个进程并发执行,由于共享系统资源,形成的制约关系。

    • 直接相互制约关系

      进程的相互合作导致直接制约关系。

  2. 临界资源(Critical Resouce)

    许多硬件资源如打印机、 磁带机等,都属于临界资源,诸进程间应采取互斥方式,实现对这种资源的共享。

  3. 临界区(Critical section)

    不论是硬件临界资源还是软件临界资源,多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区。

  4. 同步机制应遵循的规则

    空闲让进、忙则等待、有限等待、让权等待。

2.4.2 硬件同步机制

  1. 关中断

    关中断是实现互斥的最简单的方法之一。在进入锁测试之前关闭中断,直到完成锁测试并上锁之后才能打开中断。这样,进程在临界区执行期间,计算机系统不响应中断,从而不会引发调度,也就不会发生进程或线程切换。由此,保证了对锁的测试和关锁操作的连续性和完整性,有效地保证了互斥。

    缺点:① 滥用关中断权力可能导致严重后果;② 关中断时间过长,会影响系统效率,限制了处理器交叉执行程序的能力;③ 关中断方法也不适用于多CPU 系统,因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

  2. 利用 Test-and-Set 指令实现互斥

    借助一条硬件指令——“测试并建立”指令 TS(Test-and-Set) 以实现互斥的方法。在许多计算机中都提供了这种指令。

  3. 利用 Swap 指令实现进程互斥

    该指令称为对换指令,在 Intel 80x86 中又称为 XCHG 指令,用于交换两个字的内容。

2.4.3 信号量机制

1965年,荷兰学者 Dijkstra 提出的信号量机制是一种卓有成效的进程同步工具。

  1. 整型信号量

    最初信号量 S 是一个整型变量,除初始化外,对信号量仅能执行两个原子操作,即 wait(S) 和signal(S),这两个原子操作以前多称为 P、V 操作。并未遵循“让权等待”的准则。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    wait(S)
    {
    while (S<=0); // do no-loop
    S--;
    }

    singal(S)
    {
    S++;
    }
  2. 记录型信号量

    采取了“让权等待”的策略后,出现多个进程等待访问同一临界资源的情况。为此,在信号量机制中,除了需要一个用于代表资源数目的整型变量 value 外,还应增加一个进程链表指针list,用于链接上述的所有等待进程。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    typedef strcut {
    int value;
    struct process_control_block *list;
    }semaphore;
    wait(semaphore *S)
    {
    S->value--;
    if(S->value<=0) block(S->list);
    }
    singal(semaphore *S)
    {
    S->value++;
    if(S->value<=0) wakeup(S->list);
    }

    S->value 的初值表示系统中某类资源的数目,又称资源信号量,每次 wait 操作,意味着进程请求一个单位的该类资源,使系统中可供分类的该类资源数减少一个,所以是 S->value--;当 S->value<0 时,表示该类资源已分配完毕,则调用 block 进行自我阻塞,插入 list;这就是“让权等待”准则。此时,S->value 的绝对值表示在该信号量链表中已阻塞进程的数目。

  3. AND 型信号量

    在有些应用场合,是一个进程往往需要获得两个或更多的共享资源后方能执行其任务。假定现有两个进程 A 和 B,它们都要求访问共享数据 D 和 E。则设置两个互斥信号量 Dmutex 和Emutex,初值为 1。

    最后进程 A 和 B 处在僵持状态,在无外力作用下,无法解脱,即死锁状态。

    AND同步机制基本思想:将进程中整个运行过程中需要的所有资源,一次性全部地分配给进程,待进程使用完后再一起释放。

    在一个原语中,对多个临界资源的分配采用原子操作方式,要么全部分配给它,要么一个都不分配。称为 Swait(Simultaneous Wait)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    Swait(S1,S2,....Sn)
    {
    while(TRUE)
    {
    if(S1>=1 && S2>=1 && ....&& Sn>=1){
    for (i=1;i<=n;i++) Si--;
    break;
    }
    else{
    place the process in the waiting queue associaed with the first Si found with Si<1, and set the program count of this process to the beginning of Swait operation
    }
    }
    }
    Ssignal(S1,S2,....Sn)
    {
    while(TRUE)
    {
    for (i=1;i<=n;i++) {
    Si++;
    remove all the process waiting in the queue associated with Si into the ready queue
    }
    }
    }
  4. 信号量集

    对 AND 信号量机制加以扩充,对进程所申请的所有资源以及每类资源不同的资源需求量,在一次 P、V 原语操作中完成申请或释放。进程对信号量 Si 的测试值由 1 变为该资源的分配下限值 ti,即要求 Si≥ti,否则不予分配。一旦允许分配,进程对该资源的需求值为 di,表示资源占用量,进行 Si:=Si-di 的命令。对应的的 Swait 和 Ssingal 格式为:

    Swait(S1,t1,d1,…,Sn,tn,dn);

    Ssingle(S1,d1,…,Sn,dn);

    一般“信号量集”有下面几种特殊情况:

    • Swait(S, d, d)。表示每次申请 d 个资源,当少于 d 个时,便不分配;
    • Swait(S, 1, 1)
      • S>1。蜕化为记录型信号量;
      • S=1。蜕化为互斥信号量;
    • Swait(S, 1, 0) 作为一个可控开关
      • 当 S≥1 时,允许任何进程进入临界区;
      • 当 S=0 时,禁止任何进程进入临界区。

2.4.4 信号量的应用

  1. 利用信号量实现互斥

    设 mutex 为互斥信号量,初值为 1。

    • mutex = 1,两个进程皆未进入需要互斥的临界区;
    • mutex = 0,一个进程进入临界区运行,另外一个必须等待,挂入阻塞队列;
    • mutex = -1,一个进程正在临界区运行,另一个进程因等待而阻塞再信号量队列中,需要被当前以在临界区运行的进程退出时唤醒。

  2. 利用信号量实现前趋关系

2.4.5 管理机制

  1. 管程的定义

    代表共享资源的数据结构以及对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成一个操作系统的资源管理模块(软件模块),称之为管程。

    管程的四部分:①管程的名称;②局部于管程的共享收据结构说明;③对该数据结构进行操作的一组过程;④对局部于管程的共享数据结构设置初始值的语句。

    主要特性:①模块化;②抽象数据类型;③信息封装。

  2. 条件变量

    在利用管程实现进程同步时,必须设置同步工具,如两个同步操作原语 wait 和 signal。

    引入条件变量 condition x,y; 对条件变量的操作仅仅是 wait 和 signal,条件变量也是一种抽象数据类型,每个条件变量保存了一个链表,用于记录因该条件变量而阻塞的所有进程,同时提供两个操作 x.wait 和 x.signal:

    • x.wait:正在调用管程的进程因 x 条件阻塞或挂起,则将自己插入 x 条件的等待队列上,直到条件变化。

    • x.singal:正在调用管程的进程发现 x 条件发生了变化,则调用 x.singal,重新启动一个因 x 条件而阻塞或挂起的进程。若有多个,选一个,若没有,继续原进程

    管程中的唤醒切换方法:

    • P等待Q继续,直到Q等待或退出;
    • Q等待P继续,直到P等待或退出。

2.5 经典进程的同步问题

2.5.1 生产者—消费者问题

  1. 利用记录型信号量解决生产者—消费者问题

    假定生产者和消费者之间有 n 个缓冲区,这时可利用互斥信号量 mutex 实现诸进程对缓冲池的互斥使用;信号量 empty 和 full 分别表示缓冲池中空缓冲区和满缓冲区的数量。mutex 初值是 1,full 初值为 0,empty 初值为 N,full + empty = N。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    int in=0,out=0;
    item buffer[n]; // mutex=1 只有 1 个信号量供共同占用
    semaphore mutex=1,empty=n,full=0; // 信号量和初值一定要有
    void producer() { // n = 1 时,mutex 就不再需要
    do {
    produce an item in nextp;

    wait(empty);
    wait(mutex);
    buffer[in] = nextp;
    in = (in + l)% n;
    signal(mutex);
    signal(full);
    }while(TRUE) ;
    }
    void consumer() {
    do{
    wait(full);
    wait(mutex);
    nextc = buffer(out);
    out = (out + l) % n;
    signal(mutex);
    signal(empty);
    consume an item in nextc;
    ....
    }while(TRUE);
    }
    void main() { // main 函数实际上是一个进程,这里用两个函数明显不妥
    cobegin
    procedure();
    consumer();
    coend;
    }

    在进程同步管理时一个共享资源可能要设二个信号量,而在进程互斥管理时只要设一个信号量;资源信号量的 wait 与 signal 操作,也成对出现,但分别出现在不同的程序中;每个程序中的 wait 操作不能颠倒,必须先执行对资源信号量的 wait 操作,然后执行互斥信号量的 wait 操作,否则可能引起进程死锁。

  2. 利用 AND 信号量解决生产者—消费者问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int in=0,out=0;
    item buffer[n];
    semaphore mutex=1,empty=n,full=0;
    void producer() {
    do {
    produce an item in nextp;

    Swait(empty, mutex);
    buffer[in] = nextp;
    in = (in + l)% n;
    Signal(mutex, full);
    }while(TRUE);
    }
    void consumer() {
    do{
    Swait(full, mutex);
    nextc = buffer(out);
    out = (out + l) % n;
    Signal(mutex, empty);
    consume an item in nextc;
    ....
    }while(TRUE);
    }
  3. 利用管程解决生产者—消费者问题

    To be continued…

2.5.2 哲学家进餐问题

  1. 利用记录型信号量解决哲学家进餐问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    semaphore chopstick[5]={1,1,1,1,1};
    do{
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    //eat;
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    //think;
    ...
    }while(TRUE);
  2. 利用 AND 信号量解决哲学家进餐问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    semaphore chopstick[5]={1,1,1,1,1};
    do{

    //think

    Swait(chopstick[(i+1)%5],chopstick[i]);

    //eat

    Ssignal(chopstick[(i+1)%5],chopstick[i]);
    }while(TRUE);

2.5.3 读者—写者问题

允许多个进程同时读一个共享对象,但不允许一个 Writer 进程和其他 Reader 进程或 Writer 进程同时访问共享对象。

  1. 利用记录型信号量解决读者—写者问题

    互斥信号量 Wmutex,整形变量 Readcount 表示正在读的进程数目。当 Readcount=0 时 Reader 进程才需要执行 Wait(Wmutex) 操作。若 Wait(Wmutex) 操作成功,Reader 进程便可以去读,便做 Readcount+1 的操作。同理,仅当 Readcount-1 为 0 时,才须执行 signal(Wmutex) 操作,以便让 Writer 进程写操作。因为 Readcount 是一个可以被多个 Reader 进程访问的临界资源,因此也设置一个互斥信号量 rmutex。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    semaphore rmutex=1,wmutex=1;
    int readcount=0;
    void reader(){
    do{
    wait(rmutex);
    if(readcount==0) wait(wmutex);
    readcount++;
    signal(rmutex);

    perform read operation;

    wait(rmutex);
    readcount--;
    if(readcount==0) signal(wmutex);
    signal(rmutex);
    }while(TRUE);
    }
    void writer(){
    do{
    wait(wmutex);
    perform write operation;
    signal(wmutex);
    }while(TRUE);
    }
    void main(){
    cobegin
    reader();writer();
    coend
    }
  2. 利用信号量集机制解决读者—写者问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    int RN;
    semaphore L=RN,mx=1; // 最多 RN 个读者访问,1个d读者
    void reader(){
    do{
    Swait(L,1,1); // Swait(S,t,d) if S>=t,S-=d,是否有空位
    Swait(mx,1,0); // 读者不可以对 mx 操作,判断有没有写者在写
    // 合在一起的话,不是能不能读而是能不能进入图书馆?
    perform read operation;

    Ssignal(L,1);
    }while(TRUE);
    }
    void writer(){
    do{
    //Swait(L,RN,0); 当读者进程在下一句时,此句无意义,
    Swait(mx,1,1;L,RN,0); // 无读者读,无写者写
    //Swait(mx,1,1);
    perform write operation;
    Ssingal(mx,1);
    }while(TRUE);
    }
    void main(){
    cobegin
    reader();writer();
    coend
    }

2.6 进程通信

低级进程通信:进程的互斥与同步。①效率低②通信对用户不透明。

利用 OS 提供的高级通信工具:①使用方便②高效地传送大量数据,利用高级通信命令(原语)。

2.6.1 进程通信的类型

四大类:共享存储器系统、管道通信系统、消息传递系统、客户机—服务器系统。

  1. 共享存储器系统(Shaerd-Memory System)

    在共享存储器系统中,相互通信的进程共享某些数据结构或共享存储区,进程之间能够通过这些空间进行通信。据此,又可把它们分成以下两种类型:

    1. 基于共享数据结构的通信方式。

    2. 基于共享存储区的通信方式。

  2. 管道(pipe)通信系统

    所谓“管道”,是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件,又名 pipe 文件。

    • 向管道(共享文件)提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管道;
    • 而接受管道输出的接收进程(即读进程)则从管道中接收(读)数据。

    由于发送进程和接收进程是利用管道进行通信的,故又称为管道通信。

    管道机制必须提供以下三方面的协调能力:① 互斥② 同步③ 确定对方是否存在。

  3. 消息传递系统(Message passing system)

    在该机制中,进程不必借助任何共享存储区或数据结构,而是以格式化的消息 (message)为单位,将通信的数据封装在消息中,并利用操作系统提供的一组通信命令(原语),在进程间进行消息传递,完成进d程间的数据交换。

    基于消息传递系统的通信方式属于高级通信方式,因其实现方式的不同,可进一步分成两类:(1) 直接通信方式(2) 间接通信方式。

  4. 客户机-服务器系统(Client-Server system)

    • 套接字(Socket)

      最流行的网络通信程序接口之一,被设计用在同一台主机上多个应用程序之间的通信(即进程间的通信),主要是为了解决多对进程同时通信时端口和物理线路的多路复用问题。

      一个套接字就是一个通信标识类型的数据结构,包含了通信目的的地址、通信使用的端口号、通信网络的传输层协进程坐在的网络地址、针对客户或服务器程序提供的不同系统调用(API函数)。包括两类:

      1. 基于文件型:同一台机器的网络环境,基于本地文件系统支持,一个套接字关联到一个特殊文件,通信双方通过对其读写实现通信(类似管道)。
      2. 基于网络型:非对称方式通信。通信双方的进程在不同主机的网络环境下,被分配一对套接字,一个服务器端(接受进程),一个客户端(服务器端)。
    • 远程过程调用和远程方法调用

      远程过程(函数)调用 RPC(Remote Procedure Call),是一个通信协议,允许一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程。

      主要步骤:

      1. 本地过程调用者以一般方式调用远程过程在本地关联的客户存根,传递相应的参数,然后将控制权转移给客户存根;
      2. 客户存根执行,完成包括过程名和调用参数等信息的消息建立,将控制权转移给本地客户进程;
      3. 本地客户进程完成与服务器的消息传递,将消息发送到远程服务器进程;
      4. 远程服务器进程接收消息后转入执行,并根据其中的远程过程名找到对应的服务器存根,将消息转给该存根;
      5. 该服务器存根接到消息后,由阻塞状态转入执行状态,拆开消息从中取出过程调用的参数,然后以一般方式调用服务器上关联的过程;
      6. 在服务器端的远程过程运行完毕后,将结果返回给与之关联的服务器存根;
      7. 该服务器存根获得控制权运行,将结果打包为消息,并将控制权转移给远程服务器进程;
      8. 远程服务器进程将消息发送回客户端;
      9. 本地客户进程接收到消息后,根据其中的过程名将消息存入关联的客户存根,再将控制权转移给客户存根;
      10. 客户存根从消息中取出结果,返回给本地调用者进程,并完成控制权的转移。

2.6.2 消息传递通信的实现方式

  1. 直接消息传递系统

    直接通信方式,即发送进程利用 OS 提供的发送命令(原语),直接发送消息。

    • 直接通信原语

      • 对称寻址方式。发送和接受进程都显示地提供发送命令(原语):

        1
        2
        send(receiver,message);   // 发送一个消息给接受进程
        receive(sender,message); // 接收 Sender 发送的消息
      • 非对称寻址方式。接收进程可能需要与多个发送进程通信,无法指定发送进程。

        1
        2
        send(P,message);      // 发送一个消息给进程 P
        receive(id,message); // 接受来自任何进程的消息,id 变量可设置为进行通信的发送进程 id 或名字。
      • 消息的格式。在单机系统环境中,可采用比较短的定长消息格式;采用变长的消息格式方便了用户。

      • 进程的同步方式。不论是发送进程还是接收进程,在完成消息的发送或接收后,都存在两种可能性,即进程或者继续发送(或接收)或者阻塞。

      • 通信链路。有两种方式建立通信链路。

        第一种方式是:由发送进程在通信之前用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路,在链路使用完后拆除链路(计算机网络)。

        第二种方式是:发送进程无须明确提出建立的链路的请求,只利用系统提供的发送命令(原语),系统自动建立一条链路(单机系统)。

        链路又分为两种:单向通信链路(只发或只收)、双向通信链路(both)。

  2. 信箱通信

    间接通信方式。

    • 信箱的结构:信箱头、信箱体。

    • 信箱通信原语:邮箱的创建和撤销;消息的发送和接收。

      1
      2
      Send(mailbox, message);
      Receive(mailbox, message);
    • 信箱的类型

      私用邮箱、公用邮箱、共享邮箱。

2.6.3 直接消息传递系统实例

  1. 消息缓冲队列通信机制中的数据结构

    • 消息缓冲区

      1
      2
      3
      4
      5
      6
      typedef  struct message_buffer {
      int sender; // 发送者进程标识符
      int size; // 消息长度
      char *text; // 消息正文
      struct message_buffer *next; // 指向下一个消息缓区的指针
      }
    • PCB 中有关通信的数据项

      1
      2
      3
      4
      5
      6
      7
      typedef  struct  processcontrol_block{

      struct message_buffer *mq; // 消息队列队前指针
      semaphore mutex; // 消息队列互斥信号量
      semaphore sm; // 消息队列资源信号量

      }
  2. 发送原语

  3. 接受原语

2.7 线程(Threads)的基本概念

提高程序并发执行的程度,而引入。

2.7.1 线程的引入

进程:使多个程序能并发执行,提高资源利用率和系统吞吐量;

线程:减少程序在并发执行时所付出的时空开销。

  1. 进程的两个基本属性

    • 进程是一个可拥有资源的独立单位;
    • 进程同时又是一个可独立调度和分派的基本单位。
  2. 程序并发执行所需付出的时空开销

    创建进程、撤销进程、进程切换都需要花费。

  3. 线程——作为调度和分配的基本单位

2.7.2 线程和进程的比较

  1. 调度的基本单位

    传统 OS 中,进程作为独立调度和分派的基本单位,因而进程是能独立运行的基本单位;

    引入线程的 OS 中,线程是调度和分派的基本单位,因而线程是能独立运行的基本单位。

  2. 并发性

    引入线程的 OS 中,进程之间可以并发执行,一个进程中的多个乃至全部线程也能并发执行,不同进程的线程也能并发执行。

  3. 拥有资源

    进程可以拥有资源,作为系统中拥有资源的一个基本单位。

    线程本身不具有系统资源,仅有一点能保证独立运行的资源。线程还允许多个线程共享该进程的资源。

  4. 独立性

    同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。因为为防止进程之间彼此干扰,每个进程都有一个独立的地址空间和其他资源,除了贡献全局变量外,不允许其他进程访问。

    但是同一进程中的不同线程往往是为了提高并发性以及进行相互之间的合作而创建的,共享进程的内存地址和资源。

  5. 系统开销

    在创建或撤销进程时,系统都要为之分配和回收进程回收控制块、分配或回收其他资源。OS 为此所付出的开销明显大于线程创建或撤销所付出的开销。进程切换亦是如此。

  6. 支持多处理机系统

    在多处理机系统中,对于传统的进程(单线程进程),该进程只能运行在一个处理机上。

    但对于多线程进程,就可以将一个进程中的多个线程分配到多个处理机上。

2.7.3 线程的状态和线程控制块

  1. 线程运行的三个状态

    执行状态、就绪状态、阻塞状态

  2. 线程控制块 TCB

    线程标识符、一组寄存器、线程运行状态、优先级、线程专有存储区、信号屏蔽、堆栈指针。

  3. 多线程 OS 中的进程属性

    进程是一个可拥有资源的基本单位。多个线程可并发执行。进程已不是可执行的实体。

2.8 线程的实现

2.8.1 线程的实现方式

  1. 内核支持线程 KST(Kernel Supported Threads)

    在 OS 中的所有进程,无论是系统进程还是用户进程,都是在操作系统内核的支持下运行的。在内核空间为每一个内核线程设置了一个线程控制块,内核根据该控制块而感知某线程的存在,并对其加以控制。四个主要优点:

    • 在多处理器系统中,内核能够同时调度同一进程中的多个线程并行执行;
    • 如果进程中的一个线程被阻塞了,内核可以调度该进程中的其它线程占有处理器运行,也可以运行其它进程中的线程;
    • 内核支持线程具有很小的数据结构和堆栈,线程的切换比较快,切换开销小;
    • 内核本身也可以采用多线程技术,可以提高系统的执行速度和效率。
  2. 用户级线程 ULT(User Level Threads)

    用户级线程是在用户空间中实现的,无需内核的支持,即用户级线程是与内核无关的。优点:

    • 线程切换不需要转换到内核空间。
    • 调度算法可以是进程专用的。
    • 用户级线程的实现与OS平台无关。

    缺点:

    • 系统调用的阻塞问题。在基于进程机制的 OS 中,大多数系统调用将使进程阻塞。
    • 多线程应用不能利用多处理机进行多重处理的优点,内核每次分配给一个进程的仅有一个CPU,因此,进程中仅有一个线程能执行。
  3. 组合方式

    有些 OS 把用户级线程和内核支持线程两种方式进行组合,提供了组合方式 ULT/KST 线程。

2.8.2 线程的实现

  1. 内核支持线程的实现

    在仅设置了内核支持线程的 OS 中,一种可能的线程控制方法是,系统在创建一个新进程时,便为它分配一个任务数据区 PTDA(Per Task Data Area),其中包括若干个线程控制块 TCB 空间。TCB 可保存线程标识符、优先级、线程运行的 CPU 状态等信息。

    每当进程创建一个要线程,便为新线程分配一个 TCB,填入信息分配资源。当 PTDA 中的 TCB 已用完,又要创建新线程时,只要线程数目未超过系统允许的线程数目(数十—数百),系统就可以再分配 TCB 空间;撤销进程时,也应回收所有资源和 TCB,有的系统为了减少创建开销,并不立即回收。

  2. 用户级线程的实现

    • 运行时系统(Runtime System)

      实质上是用于管理和控制线程的函数(过程)的集合,其中包括用于创建和撤消线程的函数、线程同步和通信的函数,以及实现线程调度的函数等。运行时系统中的所有函数都驻留在用户空间,并作为用户级线程与内核之间的接口。

    • 内核控制线程

      又称为轻型进程 LWP(Light Weight Process)。每一个进程都可拥有多个 LWP,每个 LWP 都有自己的数据结构(如 TCB)。LWP 可通过系统调用来获得内核提供的服务,这样,当一个用户级线程运行时,只须将它连接到一 LWP 上,此时它便具有了内核支持线程的所有属性。这种线程实现方式就是组合方式。

2.8.3 线程的创建和终止

  1. 线程的创建

    应用程序在启动时,通常仅有一个线程在执行——初始化线程。主要功能是用于创建新线程。

  2. 线程的终止

    终止线程通过调用相应的函数(或系统调用)对已完成线程异常线程执行终止操作。

    有些线程(主要是系统线程),它们一旦被建立起来之后,便一直运行下去而不被终止。

    在大多数的 OS 中,线程被中止后并不立即释放它所占有的资源,只有当进程中的其它线程执行了分离函数后,被终止的线程才与资源分离,此时的资源才能被其它线程利用。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×