operating system

请思考以下问题

  1. 为什么要引入进程
  2. 什么是进程?进程由什么组成?
  3. 进程是如何解决问题的?

1. 进程的概念和特征

1.1 进程的概念

进程是程序的一次执行过程,那么程序的顺序执行有如下要求

  1. 顺序性

    程序按顺序逐步执行。这和你编程一样,编程就是按照你的思路做一件事,思路乱了事就做不成了。

  2. 封闭性

    独占全机资源,所有资源状态由程序完成。这也是必须的,如果进程 A 读文件读到一半,过一会继续读发现数据状态发生了改变,不是我要的数据,自然就出错了,所以所有状态都要由进程 A 来改变,这就是封闭性。

  3. 可再现性

    程序的执行结果不变,且与计算机的执行速度、方式(持续或走停)无关。

在多道批处理、分时、实时系统等操作系统中,由于存在多个运行的程序,使得程序的执行具有并发性、共享性和异步性等特征。在程序并发的同时,导致程序出现如下特征

  1. 间断性

    多个程序相互制约(如输入程序与计算程序的先后顺序)

  2. 失去封闭性

    多个程序共享资源(资源状态由多个程序改变)

  3. 不可再现性

    由于状态的随意改变,导致有些程序找不到北。

为了使程序在并发、共享和异步的环境下能正常运行,必须专门设置一个控制数据区,为程序保留运行的现场(处理机状态、断点 IP)及控制管理信息(进程标识、处理机状态、进程调度、进程控制等信息),并进行有效的隔离,这样程序又恢复了顺序性、封闭性和可再现性。

1.2 进程的特征

进程是程序的一次运行。

进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

进程是进程实体(包括程序段、数据和 PCB)的运行过程,是系统进行资源分配和调度的一个独立单位(正如人是社会资源分配和调度的独立单位一样)

  1. 进程的特征

    结构性:由程序段、数据段和进程控制块组成。

    动态性:进行可以被动态地创建、执行和撤销。

    并发性:在一个时间段内有多个进程运行。

    独立性:是独立运行和获得资源的基本单位。

    异步性:异步执行。

  2. 进程和程序的区别

    进程是动态的,程序是静态的(是指令的集合)。

    一个程序可以包含多个进程。

    进程可以描述并发活动,程序则并不明显。

    进程执行需要处理机,程序存储需要介质。

    进程有生命周期,程序是永存的。

  3. 进程的结构

    进程由纯代码段、数据和进程控制块组成。

    代码段:描述进程所完成的功能。

    数据集合:程序运行时所需要完成的数据区。

    进程控制块(PCB):既能标识进程的存在,又能刻画出进程瞬间特征的数据结构。

    linux 系统可以通过 cat /proc/pid/maps 查看进程虚存空间布局。

2. 进程的状态和转换

进程有三种基本状态。

  1. 就绪状态

    进程获得了除处理机 CPU 之外的所有资源(多个就绪进程排成就绪队列)。

  2. 执行状态

    进程的程序正在处理机上执行(单 CPU 中只有一个进程处于该状态)。

  3. 阻塞状态

    因发生某事件(如请求 I/O,申请缓存空间等)而暂停执行的状态(也称为睡眠状态或等待状态)。

处于执行状态的进程,可以主动用阻塞原语(block)将其变为阻塞状态。

处于阻塞状态的进程,可以用唤醒(wakeup)原语将其变为就绪状态。

进程状态切换

除了上面三种基本状态,进程还有一些其他状态 。

2.1 挂起状态

挂起状态是一种静止状态,既不能马上投入运行的状态,包括静止就绪状态(Readys)和静止阻塞状态(Blockeds)。

处于挂起状态的进程可以存放到外存保留,而且可以回收这些挂起状态进程的内存、设备等部分资源。(反正挂着不用)。

设置挂起状态的原因有如下几个

  1. 终端用户的需要:(调试)
  2. 父进程的需求:(子进程同步)
  3. 负荷调节的需要:(减轻负荷)
  4. 操作系统的需要:(检查资源的使用情况)

处于活动状态的进程(Readya,Blockeda)可以用(Suspend)原语将其变为挂起状态(Readys,Blockeds)。

处于挂起状态(静止状态)的进程,可以用激活(Active)原语将其变为活动状态。

进程状态切换

3. 进程控制

进程的控制由原语操作实现。原语是由若干条指令构成,用于完成一定功能的一个过程。

原语操作是一种 “原子操作” ,因此原语操作中的所有动作、要么全做,要么不做。

原语操作是一种不可分割的操作。(类似化学世界中原子不可分割)

原语操作是 OS 内核执行基本操作的主要方法。

3.1 进程的创建

引起进程创建的事件有

  1. 用户登录:用户合法登录后创建 init 进程。
  2. 作业调度:某作业被调度(批处理系统)
  3. 提供服务:用户调用某些系统调用或命令后
  4. 应用请求:由用户程序自己创建进程(贪玩蓝月启动)

进程创建原语的基本步骤是

  1. 申请空白 PCB
  2. 分配资源
  3. 初始化 PCB
  4. 将新进程插入就绪队列。
// 参数依次是 进程名、优先级、所需初始资源,执行程序文件名、参数列表
procedure create (pn, pri, res, fn, args);
begin
    getfreepcb(i);                    // 1. 申请空白 PCB
    if i=NIL then return (NIL);       
    i.id := pn;                       // 2. 初始化 PCB   
	i.priority := pri;                   
	i.resources := res;               // 3. 分配资源  
    memallocate(datasetsize, add);    // 3. 分配内存,add 是首地址
    if add = NIL then                    
    begin
        pcbrelease (i);
        return (NIL);
    end;
    i.dataadd := add;                 // 3. 初始化 PCB
	i.datasize:= datasetsize; 
    datasetinit(i.dataadd, args);     
    filestate(fn, add, size);         // 2. 分配资源 
    if add = NIL then
    begin
       memallocate(size, add);
        if add = NIL then
        begin
            memrelease (i.dataadd, i.datasize);
            pcbrelease(i); return(NIL);
        end
        read(fn, size, add);
    end;
    i.textadd := add;                // 3. 初始化 PCB
	i.textsize : = size;
    i.prog := fn;       
	i.pc := add;
    i. children := 0;  
	i.parent := EXE;                 // EXE 是执行态进程的 PCB 指针
    EXE.children := EXE.children+1;
    i.state := ready; i.queue := RQ;
    insert(RQ, i);                   // 4. 将新进程插入就绪队列
    otherinit;
    return(i);
End;

可以看出,如果 PCB 或资源不足,创建就不会成功。

3.2 进程的终止

  1. 进程正常结束

    通过停止原语实现。

    procedure halt(i);
    begin
        i.state := stop;           // 进程状态变为 stop
        send(i.parent, completed); // 告知父进程,等待回收
    end;
    
  2. 外部干预

    用户或系统干预,父进程请求或终止。

进程的终止原语(和停止原语不同,这是强制终止)的大概逻辑是

  1. 读取进程状态,如果是 stop,跳到 2,如果不是 stop,调用 halt 再到 2 。
  2. 将子孙进程终止
  3. 归还资源
  4. 释放 PCB
procedure destory(i);
begin
    if i.state <> stop then
        halt(i);
    while i.children > 0 do       // 2. 将子孙进程终止
    begin
        i.children := i.children  1;
        findchild(i, child);      // 查找子进程
        destory(child);
    end;
    memrelease(i.dataadd, i.datasize)  // 3. 归还资源
    close(i.prog, t);
    if t = true then
        memrelease(i.textadd, i.textsize);
    resrelease(i);
    remove(i.queue, i);         // 4. 释放 PCB ,remove 将进程移出队列
    pcbrelease(i);      
end;

3.3 进程的阻塞和唤醒

引起进程阻塞的事件有

  1. 请求系统服务(如请求分配 I/O)
  2. 启动某种操作(如启动 I/O)
  3. 新数据尚未到达(如进程通信)
  4. 无新工作可做(系统进程)

进程阻塞原语一般要经过如下几个步骤

  1. 保存现场信息
  2. 进程变为 “Blockeda”
  3. 插入阻塞队列 q
  4. 进程调度
procedure block(q);
begin
    save(EXE);                // 1. 保存现场信息
    EXE.state := Blockeda;  // 2. 进程变为'Blockeda'
    EXE.queue := q;           // 3. 插入阻塞队列 q
    insert(q, EXE);           // insert 将进程插入队列
    EXE := NIL;               // 4. 进程调度
    scheduler;
end;

引起进程唤醒的事件有

  1. 系统请求实现(如获得 I/O 资源)
  2. 某些操作完成(如 I/O 操作完成)
  3. 新数据已经到达(如其他进程已将数据送达)
  4. 又有新工作可做(系统进程)

进程唤醒原语主要有以下步骤

  1. 从队列中移出进程
  2. 读取进程状态,如果为 Blockeda,活动就绪,否则为静止就绪(挂起了)。
procedure wakeup(q);
begin
    outqueue(q, i);             // 1. 从队列移出进程
    if i.state = Blockeda     // 2. 读取进程状态并做相应操作
    then i.state = Readya 
    else  i.state = Readys;
    i.queue := RQ;
    insert(RQ, i);
end;

3.4 进程的切换

3.5 进程的挂起

挂起原语 suspend 的操作步骤如下

  1. 读取进程状态,如果是就绪改为静止就绪,否则改为静止阻塞。
  2. 将数据集合复制到外存。
  3. 释放数据段内存。
  4. 判断代码段是否共享,如果不共享释放代码段内存。
procedure suspend(i);
begin
    if i.state = Readya   // 1. 读取并判断相应状态
    then i.state=Readys else i.state=Blockeds; // 活动阻塞 ? 静止阻塞
    swapout(i.dataadd, i.datasize, add)  // 2. 将数据段复制到外存
    i.swapadd := add;
    memrelease(i.dataadd, i.datasize);   // 3. 释放数据段内存
    close(i.prog, t);                    // 4. 判断是否释放程序段内存
    if t = true then memrelease(i.textadd, i.textsize);
end;

3.6 进程的激活

激活原语 active 的操作步骤如下

  1. 为数据段申请内存,失败就退出。
  2. 将数据集调入内存。
  3. 若程序段不是共享的,为程序段申请内存,失败就退出。
  4. 将程序调入内存。
  5. 将进程设置为活动阻塞或活动就绪。
procedure active(i);
begin
    memallocate(i.datasize, add);        // 1. 为数据集申请内存
    if add = NIL then return(false);
    swapin(i.swapadd, i.datasize, add);  // 2. 将数据集调度内存
    i.dataadd := add;
    filestate(i.prog, add, size);        // 3. 为程序段申请内存
    if add = NIL then
    begin
        memallocate(size, add);
        if add = NIL then
        begin
            memrelease(i.dataadd, i.datasize);
            return(false);
        end;
       read(i.prog, size, add);          // 4. 将程序调入内存
    end;
    i.textadd := add;
    if i.state = Readys                // 5. 状态设置
    then i.state := Readya 
    else  i.state := Blockeda
    return(true);
end;

4. 进程的组织

4.1 进程控制块

由于我们需要让进程在共享世界中还能拥有顺序性、封闭性和可再现性,我们需要用一种数据结构存储进程状态信息,这种结构称为进程控制块(PCB),具体作用如下

  1. 描述进程的变化过程
  2. 记录进程的外部特征
  3. 记录进程与其他进程的联系
  4. 是进程存在的唯一标志

操作系统通过 PCB 控制和管理进程,没有身份证的进程在计算机世界是活不下去的。

PCB 的具体内容有很多,包括

  1. 进程标识符信息

    内部标识符信息:进程唯一序号(进程的身份证号码)

    外部标识符信息:由创建者提供的进程名字(多个进程的名字可以重复)

  2. 处理机状态信息

    如果进程 A 没有运行完,处理机就被进程 B 抢走了,操作系统会在进程切换之前,将进程 A 的处理机状态信息存储到 PCB 中。包括通用寄存器、指令计数器、程序状态字 PSW、用户堆栈指针等信息。

  3. 进程调度信息

    进程的状态(就绪、阻塞、执行)

    进程优先级(优先级高的进程更有机会先用 CPU)

    进程调度所需的其他信息(进程已用 CPU 时间,为调度算法准备的)

    事件(阻塞原因)

  4. 进程控制信息

    程序和数据的地址,以至于下次程序重新拥有 CPU 之后可以找到执行的起点。

    进程同步和通信机制(如消息队列指针等)

    资源清单

    链接指针(与其他 PCB 形成一个队列)

  5. 进程其他信息

    父进程:由系统或用户首先创建的进程。

    子进程:由父进程创建的进程。

    父子(孙)进程之间构成一课树形结构,即进程树。(Linux 系统下用 pstree 查看)

任何子进程只能由父进程创建和撤销,子进程不能对父进程实施控制。父子进程的运行无先后顺序(异步性)。子进程可全部或部分共享父进程拥有的资源。

PCB 的组织方式(数据结构)有三种。

  1. 线性表方式

    将所有 PCB 不分状态,全部组织在一个连续表中。实现简单,但是每次查找都要扫描整个 PCB 表,一般在进程较少的系统中使用。

  2. 链接方式

    把具有相同状态的 PCB,链接成一个队列。有执行队列、就绪队列、阻塞队列和空闲队列。

  3. 索引方式

    所有 PCB 线性存放(不论状态),但是有相应的索引表记录 PCB 的偏移位置。(如就绪索引表、阻塞索引表)

4.2 程序段

4.3 数据段

5. 进程的通信

进程通信时指进程之间的信息交换。

采用信号量机制可以实现进程(低级)通信(如生产者-消费者问题),但其通信效率低,通信对用户不透明(用户必须自己编写访问临界资源的程序或管程,包括数据结构的设置、数据的传送、进程的互斥于同步等),算是进程之间的低级通信。

进程通信有三种常用类型。分别是

  1. 共享存储器系统(无格式)
  2. 消息传递系统(有格式)
  3. 管道通信系统(单向通道)

共享存储器系统:进程间以共享存储器方式进行数据通信。

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

    由用户程序定义数据结构、申请内存,并同步各进程对该数据结构的访问。(生产者-消费者问题)

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

    系统设置一共享存储区,由系统同步各进程对该共享存储区的访问。用户需要共享存储区时,到系统中去申请,系统分配一部分共享存储分区给用户并返回该分区的名字,相关进程按名共享该分区。

消息传递系统:进程程间的数据交换以消息(message)为单位。操作系统直接提供一组命令(原语)实现通信。

管道:管道是一个打开的共享文件(pipe文件)。管道用于连接一批读进程和一批写进程,实现它们之间的通信。所有相关进程之间的同步都由系统控制,管道采用先进先出(FIFO)操作。发送进程可以源源不断地从管道一端写入数据流;每次写入的信息长度可变;但一个时刻只能有一个发送进程写。接收进程可以从管道另一端读出数据,同样每次读出的信息长度可变;但一个时刻只能有一个接收进程读。

5.1 共享存储

5.2 消息传递

  1. 直接通信方式

    发生进程直接将消息发送给接收进程。

    接收进程从发送进程得到消息。

    主要采用两种命令(原语)

    1. 发送消息原语 Send(Receiver, message)
    2. 接收消息原语 Receive(Sender, message)
  2. 间接通信方式

    需要某种共享数据结构的实体作为中介。发送进程将发送给目标进程的消息暂存于该中介中,接收进程从中介中取出发送给自己的消息。

    中介一般称为信箱(mailbox),因此,间接消息传递通信也称信箱通信。

    主要采用四种命令(原语)

    1. 信箱创建命令 Create(mailbox)
    2. 信箱撤销命令 Delete(mailbox)
    3. 消息发送命令 Send(mailbox,message)
    4. 消息接收命令 Receive(mailbox, message)

    信箱也有好几种类型,如下

    1. 私用信箱

      由用户进程创建,其它进程只能向该信箱发送消息。

    2. 公用信箱

      由操作系统创建,并提供给系统中的所有核准进程使用。

    3. 共享信箱

      由某进程创建,并指明共享者名字;所有共享者和创建者进程都可以取走自己的消息。

    通信可以实现一对一,一对多,多对一,多对多。

  3. 进程同步方式

    发送进程阻塞,接收进程阻塞[无缓冲]。

    发送进程不阻塞,接收进程阻塞[如服务器]

    发送进程不阻塞,接收进程不阻塞[相当于生产者消费者问题]

消息缓冲队列通信机制 :发送进程直接将消息发送给接收进程,并将它挂在接收进程的消息缓冲队列上,接收进程从消息缓冲队列中取得消息。

5.3 管道通信

6. 线程

6.1 线程的基本概念

在传统OS中,进程既是CPU调度和分配的基本单位,同时,进程又是拥有资源的独立实体。在处理(创建、撤消、调度)进程时,所费开销较大。

在OS中引入进程,主要是为了提高计算机系统的并发执行能力,将进程的两个属性分开,即让进程仅成为拥有资源的单位,而让线程成为调度和执行的基本单位,是为了进一步提高并发能力,并有利于多处理机系统的调度。

6.2 线程与进程的比较

  1. 进程是线程的载体。
  2. 一个进程可包含多个线程。
  3. 一个线程是进程的一个执行流。
  4. 一个进程中至少包含一个线程,称主线程。

6.3 线程的属性

6.4 线程的实现方式

6.5 多线程模型