程序运行方式

程序顺序运行

  • 顺序运行的特性包括顺序性，封闭性，可再现性

  • image.png

    并发与并行运行

  • 并发(Concurrent)与并行(Parallel)的概念

  • 并行指多个事件在同一时刻发生
  • 并发指多个事件在同一时期内发生
  • 并行是并发的特例，程序并行运行的条件是系统中有多个CPU

  • image.png

    进程

  • 进程是操作系统中一个最基本也是最重要的概念，但目前没有一个非常确切的定义。

  • 为了强调进程并发性和动态性的特点，将其定义为：
  • 进程是程序的一次执行，该程序可以与其它程序并发执行。

进程的特征与控制

进程具有如下特征

  • 结构性
    • 由程序，数据集合，进程控制块PCB组成
  • 动态性
  • 独立性
  • 并发性

进程通常分为两类

  • 系统进程
  • 用户进程

关于进程控制块PCB(Process Control Block)

  • 为了对进程进行有效的控制和管理，系统为每一进程设置一个进程控制块，PCB是进程存在的唯一标志。 PCB表常驻内存，属于系统空间，只有操作系统程序才能够访问，用户程序不得访问。通常PCB包含以下几类信息
    • 进程描述信息
      • 进程标识名(Process ID)：也称为标识符或标识数，为进程的内部标识，用来唯一标识一个进程，通常是一个整数。
      • 进程名：为进程的外部标识，通常基于可执行文件名（不唯一）
    • 进程控制信息
      • 当前状态：进程当前所处状态，为进程调度之用
      • 优先级：进程需要处理的缓急程度标识
      • 程序和数据的地址：程序和数据所在的内存或外存地址。
      • 队列指针或链接字：处于同状态的进程链接指针
    • 资源占用信息
    • CPU现场保护结构
      • 它由处理机各种寄存器（通用寄存器、指令计数器、程序状态字PSW、用户栈指针等）的内容所组成，该类信息使进程被中断后重新执行时能恢复现场从断点处继续运行。

PCB表的组织形式

  • 索引方式：
    • 根据进程的状态，在内存中建立相应的索引表，系统中的某些固定单元保存各索引表的首地址。各索引表的表目中记录相应状态的PCB表的首地址
    • image.png
  • 链接方式：
    • 用PCB表中的队列指针项将具有相同状态的进程的PCB表链接起来，这样PCB表就形成就绪队列、空闲队列及阻塞队列等。其中，空闲队列是一个，而就绪队列与阻塞队列可以是多个。也可以将不同优先级的进程的PCB表排入不同的就绪队列中
    • image.png

进程状态及转换

进程的三种基本状态

  • 运行态(Running)
    • 当一个进程在处理机上运行时，则称该进程处于运行状态。
  • 就绪态(Ready)
    • 一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。
  • 阻塞态(Blocked)
    • 当一个进程正在等待某一事件发生（例如请求I／O而等待I／O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。注意与就绪状态的不同在于即使处理机处于空闲状态也无法运行。

状态转换

image.png

  • 就绪→运行：调度程序选择一个新的进程运行
  • 运行→就绪：运行进程用完时间片被中断或在抢占调度方式中, 因为一高优先级进程进入就绪状态
  • 运行→阻塞：进程发生I/O请求或等待某事件时

  • 阻塞→就绪：当I/O完成或所等待的事件发生时

    细分的进程调度状态-挂起

  • 由于终端用户及操作系统的需要(排除故障或为系统减负)，为了能够将指定进程暂时静止下来，增加了静止阻塞 (阻塞挂起) 和静止就绪 (就绪挂起)态，原阻塞和就绪改称为活动阻塞和活动就绪状态

  • image.png

进程控制

处理机的执行状态分为两种

  • 核心态(管态)
  • 用户态(目态)
  1. 一般来说，当发生中断或系统调用时,用户进程暂停，CPU模式从用户态切换到核心态，执行服务进程，此时进程依 然在原上下文中运行，仅模式发生变化，系统内核在该上下文中进行中断响应和服务。当中断响应和系统务完成后，通过逆向模式来切换恢复被中断进程的运行。
  2. 进程由创建而产生，由调度而执行，由撤销而消亡

  3. 进程的控制通常由原语(Primitive)完成

    1. 原语又称为“原子操作(Atomic Operation)”过程，作为一个整体而不可分割——要么全都完成，要么全都不做。
    2. 原语是操作系统的核心(不是由进程而是由一组程序模块所组成)的一个组成部分，并且常驻内存，通常在核心态(管态)下运行。

      创建进程

  4. 进程的创建方式

    1. 用户登录
    2. 作业调度
    3. 提供服务
    4. 应用请求
  5. 进程图
    1. 允许进程创建子进程，子进程还可以创建自己的子进程，从而形成树型的进程家族。
    2. image.png
    3. 树形结构的优点：资源分配严格，进程控制灵活，进程层次清晰，关系明确
  6. 进程创建
    1. 系统生成时就建立起一些系统进程。主要用于创建常驻内存的系统进程
    2. 经创建原语产生进程。主要用于创建非常驻的系统进程和用户进程
  7. 进程的创建过程
    1. 一旦发现了要求创建新进程的事件，OS便调用创建原语, 按以下过程创建新进程。
    2. 分配一个维一的进程标识符,索取一个空白PCB
    3. 为新进程的程序和数据分配内存空间
    4. 初始化进程控制块
      1. 初始化标识符信息(填入)、处理机的状态信息(指令指针, 栈指针)和控制信息(状态,优先级…)
    5. 设置相应的链接。如: 把新进程加到就绪队列的链表中
  8. image.png

撤销与终止进程

  • 一旦发生终止进程的事件，OS便调用撤消原语，按以下过程终止该进程
  • 从PCB中读取进程的状态
  • 若进程处于执行态, 应立即终止该进程的执行，并置调度标志为真（以便该进程终止后系统重新进行调度,将处理机分配给新选择的进程）
  • 若有子孙进程则将其全部终止，以防它们失控、
  • 将该进程所占有的全部资源还给父进程或系统

  • 将该进程的PCB从所在队列中移出

    阻塞与唤醒进程

  • 处于运行状态的进程，在其运行过程中期待某一事件发生（如：请求系统服务、等待键盘输入、等待数据传输完成、等待其它进程发送消息） 当被等待的事件未发生时, 由进程调用阻塞原语(block),将自己阻塞

  • 阻塞原语使处于运行态的进程停止运行，将运行现场保存在其PCB的CPU现场保护区，然后将 PCB中的现行状态由运行态变为阻塞态，并将该进程插入到相应事件的阻塞队列中。最后，转进程调度程序重新调度，将处理机分配给一个就绪进程，按新进程PCB中的处理机状态设置CPU环境，使它投入运行。
  • 当被阻塞进程期待的事件到来时, 由中断处理进程或其它产生该事件的进程调用唤醒原语, 将期待该事件的进程唤醒

  • 唤醒原语执行时, 将被阻塞进程从相应等队列中移出, 并将其 PCB中的现行状态由阻塞改为就绪态, 然后将该进程插入就绪队列中

    挂起与激活进程

  • 当进程请求将自己挂起或父进程请求将子进程挂起时, 调用挂起原语(suspend),将指定进程挂起。

  • 执行过程: 检查要挂起进程的状态，若处于活动就绪态就将其改为静止就绪态，对于活动阻塞态的进程则将其改为静止阻塞态。如果被挂起的进程正在执行则还要转到调度程序重新调度。

  • 挂起原语既可以由该进程自己调用，也可由其他进程或系统调用，但激活原语只能由其他进程或系统调用

    进程的互斥与同步

    并发执行的多个进程之间存在两种基本关系：竞争和协作
    会引发两种极端情况

  • 死锁(Deadlock)

  • 饥饿(Starvation)

    临界资源与临界资源区

    软件方法管理

  • 设置标志位falg turn

  • flag 表示是否有意访问

  • turn 表示临界资源是否有其他进程访问

    硬件管理

  • 禁止中断法

    • 影响效率
    • 多CPU下失效

  • 特殊指令法

    • TS(Test and Set)指令

      • 其功能可看为一个函数
        1. bool TS (bool &x){
        2. if(x == true){
        3. x = false;
        4. return true;
        5. }
        6. else return false;
        7. }
        将x与临界区关联 x为真表示进程不在临界区

    • SWAP(Exchange)指令

      1. bool lock = true
      2. cobegin
      3. process Pi() {
      4. bool ki = true;
      5. do {
      6.    SWAP(ki, lock);
      7. }while(ki);        //上锁
      8. 临界区
      9. SWAP(ki, lock);    //开锁
      10. }
      11. coend

lock表示有无进程在临界区，初值为false，表示系统初始化时有无进程进入临界区
此时进程进入运行一次do while 设置lock 为真 ki为假
若还有其他进程要进入将在do while 循环达到互斥

常见的同步机制

  • 锁
  • 信号量
  • 管程

  • 消息传递

    信号量与PV操作

  • 在信号量机制下进程在一个特殊点被迫阻塞，直到接受一个信号量(Semaphore)

  • 信号量的主要作用
    • 封锁临界区
    • 进程同步
    • 维护资源计数
  • 设信号量s为一个记录型数据结构，一个分量为整形量value 另一个信号量队列初始为空
  • P和V操作原语
  • P 将S 减一
    • 若S < 0 进程进入阻塞队列
    • 若S >= 0继续
  • V 将S 加一
    • 若S <= 0 从阻塞队列里释放，唤醒一个处于等待状态的进程，将其转换为就绪状态
    • 若S >= 0 继续

      进程同步经典问题

      生产者-消费者问题

读者-写者问题

哲学家就餐问题

睡眠理发师问题

进程同步和互斥间关系

  • 相似
    • 进程的互斥实际上是进程同步的一种特殊情况； 进程的互斥和同步统称为进程同步
  • 差别
    • 进程互斥是进程间共享资源的使用权 ，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；而进程同步则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。

进程通信

进程通信(InterProcess Communication,IPC)是进程之间数据的相互交换和信息的相互传递，是一种高级通信机制
主要的通信机制有

  • 消息传递通信
  • 共享内存通信
  • 管道通信

分类 进程管理 - 图9

消息传递通信

共享内存通信

  • 基于共享数据结构的通信方式：通信进程公用某些数据结构，如生产者与消费者问题中的公共缓冲区
  • 基于共享存储区的通信方式：多个进程可以通过对共享内存储区中数据的读操作与写操作完成进程之间的通信。
  • image.png

  • 进程利用共享内存储区进行通信时，需要进行如下操作：

    1、向操作系统申请共享存储区
    2、挂接共享存储区到进程的存储空间
    3、进程互斥读写存储区
    4、通信结束后归还存储区

  • 直接通信方式：发送进程将消息直接发给接收进程，挂在接收进程的消息队列上，由接收进程从自己的消息队列上取下消息，完成一次消息的通信过程。

  • 间接通信方式：通信时指明一个中间媒介，即信箱。发送者执行发送命令，将消息发到指明的信箱，接收者执行接收命令时，从指定的信箱中接收消息。

    管道通信

    管道是外存上的一个共享文件，是一个单向的、先进先出的、固定大小的数据流。写进程向管道尾部写入数据，读进程从管道首端读出数据。管道空时，读进程被阻塞，管道满时，写进程被阻塞。管道提供了一种简单的流控制机制。

image.png

  • 在管道通信过程中，首先要建立一个管道文件。管道文件是外存上的一个共享文件。生成一个管道时，要返回两个文件描述符，一个用来读管道，另一个用来写管道。进程可以利用这两个描述符共享管道文件。
  • 写进程向管道尾部写入数据，读进程从管道首端读出数据读进程和写进程之间必须互斥地访问管道。当进程写管道时，管道满，则停写，写进程被阻塞，等到被读进程唤醒后再写；读进程读管道时，管道空，则停读，读进程被阻塞，等到被写进程唤醒后再读，即读进程和写进程访问管道时要保持同步关系。
  • 无名管道
    • 无名管道是操作系统提供的资源，可以被所有的进程使用。但是无名管道在使用上的限制是：它仅能用于连接具有共同祖先的进程
    • 有名管道克服了无名管道使用上的限制，所有进程都可以共享对管道的操作，相互之间通过管道通信

进程调度

死锁

线程的基本概念

管程的基本概念