进程

进程简介

程序段、数据段、PCB三部分组成了进程实体,一般情况下,我们把进程实体简称为进程;例如,创建进程实质上是创建进程实体的PCB。

引入进程实体的概念后,可把进程定义为:

进程是进程实体的运行过程,是系统进行资源分配调度的一个独立单位

严格来说,进程实体和进程不一样,进程实体是静态的,而进程是动态的。除非专门考察二者区别,我们都可以认为进程实体就是进程。因此我们可以说“进程由程序段,数据段,PCB三部分组成“

PCB

特征

组织方式

总结

进程状态

状态

转换模型

  • 五状态模型

  • 七状态模型(含挂起)

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理,具有创建新进程、撤销已有进程、实现进程状态转换等功能

  • 通过原语实现进程控制,原语执行具有原子性

    如果不能“一气呵成”,就有可能导致操作系统中的某些关键数据结构信息不统一的情况,这会影响操作系统进行别的管理工作

  • 通过”关中断指令“”开中断指令“这两个特权指令实现原语的原子性

    CPU执行了关中断指令之后,就不再例行检查中断信号,直到执行开中断指令之后 才会恢复检查。这样,关中断、开中断之间的这些指令序列就是不可被中断的,这就实现了“原子性”

创建

终止

阻塞和唤醒

切换

进程通信

进程通信就是进程之间的信息交换

为了保证安全,一个进程不能直接访问另一个进程的地址空间,故操作系统提供了一些方法

进程通信

共享存储

进程对共享空间的访问必须是互斥的,操作系统只负责提供共享空间和同步互斥工具(PV操作)

  • 基于数据结构的共享

    比如共享空间里只能放一个长度为10的数组。这种方式速度慢、限制多,是一种低级通信方式

  • 基于存储区的共享

    在内存中画出一块共享存储区,数据的形式、存放位置由进程控制,而不是操作系统。这个方式更快,是一种高级通信方式

消息传递

进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的发送消息/接收消息两个原语进行数据交换

  • 直接通信方式

    消息直接挂到接收进程的消息缓冲队列上

  • 间接通信方式

    消息先发送到中间实体(信箱)中,新词也成为信箱通信方式。例如电子邮件系统

管道通信

管道pipe指用于连接读写进程的一个共享文件,其实就是在内存中开辟一个大小固定的缓冲区

管道

  1. 管道只能采用半双工通信,某一时间段内只能实现单向的传输。如果要实现双向同时通信则需要设置两个管道。
  2. 各进程要互斥地访问管道
  3. 数据以字符流的形式写入管道,当管道写满时,写进程的write()系统调用将被阻塞,等待进程将数据取走。当读进程将数据全部取走后,管道变空,此时读进程的read()系统调用将被阻塞
  4. 如果没写满,就不允许读。如果没读空,就不允许写
  5. 数据一旦被读出,就从管道中被抛弃,这就意味着读进程最多只能有一个,否则可能会有读错数据的情况

线程

特点

线程是一个基本的CPU执行单元,也是程序执行流的最小单位

实现方式

  • 用户级线程
    • 用户级线程由应用程序通过线程库实现
    • 线程切换可以在用户态下进行,无需操作系统干预
    • 操作系统内核是看不到用户线程的存在的
  • 内核级线程
    • 内核级线程的管理工作由操作系统内核完成
    • 线程调度、切换等工作都由内核负责。故内核级线程的切换必须在核心态下完成
    • 操作系统只看得见内核级线程,故只有内核级线程才是处理机分配的单位

多线程模型

多对一

一对一

多对多

处理机调度

概念与层次

在多道程序系统中,进程的数量往往是多于处理机的个数的,这样不可能同时并行地处理各个进程。处理机调度,就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程的并发执行

  • 高级调度(作业调度)

    按一定的原则从外存上处于后备队列的作业中挑选一个或多个作业,给他们分配内存等必要资源,并建立相应进程

  • 中级调度(内存调度)

    决定将哪个处于挂起状态(PCB常驻内存中)的进程重新调入内存。中级调度比高级调度频率更高

  • 低级调度(进程调度)

    主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给他。频率最高

对比:

调度时机

注意:进程在普通临界区是可以进行调度、切换的

方式

  • 非剥夺调度方式

    又称非抢占方式。只允许进程主动放弃处理机。

    • 实现简单,系统开销小但无法及时处理紧急任务,适用于早期的批处理系统
  • 剥夺调度方式

    又称抢占方式。当一个进程正在处理机上执行时,如果有一个更重要或更紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给更重要紧迫的进程

    • 可以优先处理更紧急的进程,也可以实现让各进程按时间片轮流执行的功能(通过时钟中断)。适用于分时操作系统、实时操作系统

切换与过程

“狭义的进程调度”与“进程切换”的区别:

  • 狭义的进程调度指从就绪队列中选中一个要运行的进程(可以是刚刚被暂停执行的进程,也可能是另一个进程)
  • 进程切换是指一个进程让出处理机,由另一个进程占用处理机的过程

广义的进程调度包含了选择一个进程和进程切换两个步骤

  1. 对原来运行进程各种数据的保存
  2. 对新的进程各种数据的恢复

注意:进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少

调度算法评价指标

  • CPU利用率

    利用率 = 忙碌时间 / 总时间

    例:

  • 系统吞吐量

    系统吞吐量 = 单位时间内完成作业的数量 = 总作业数 / 总时间

    例:

  • 周转时间

    • 周转时间 = 作业完成时间 - 作业提交时间

    • 平均周转时间 = 各作业周转时间之和 / 作业数

    • 带权周转时间 = 作业周转时间 / 作业实际运行时间

    • 平均带权时间 = 各作业带权周转时间之和 / 作业数

  • 等待时间

    进程/作业处于等待处理机状态时间之和

    等待时间 = 周转时间 - 运行时间

    • 对于进程,等待时间是指进程建立后等待被服务的时间之和,在等待I/O期间进程也算被服务的,不计入等待时间
    • 对于作业,还要加上作业在外存后备队列中等待的时间
  • 响应时间

    用户提交请求到首次产生响应所用的时间

调度算法

先来先服务(FCFS)

  • 算法规则:按照作业/进程到达的先后顺序进行服务

  • 非抢占

  • 缺点:对长作业有利,对短作业不利

短作业优先(SJF)

  • 算法规则:最短的作业/进程优先得到服务
  • SPF是非抢占,SRTN是抢占,默认是非抢占式的
  • 对短作业有利,对长作业不利,可能产生饥饿现象

短进程优先调度(SPF):

最短剩余时间优先(SRTN):

高响应比优先(HRRN)

  • 算法规则:每次调度时计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务
  • 非抢占式
  • 综合考虑等待时间和运行时间,不会导致饥饿

时间片轮转(RR)

  • 算法规则:按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完则放到就绪队列队尾排队
  • 抢占式
  • 响应快,适用于分时操作系统
  • 高频率进程切换,开销较大,且不区分任务的紧急程度
  • 不会导致饥饿
  • 如果时间片太大,使得每个进程都可以在一个时间片内完成,则时间片轮转调度算法就退化成了先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大。

优先级调度算法

  • 算法规则:调度时选择优先级最高的作业/进程
  • 用优先级区分紧急程度,适用于实时操作系统
  • 可能导致饥饿
  • 非抢占、抢占都有

非抢占

抢占式

多级反馈队列调度算法

同步与互斥

同步

  • 同步也称为直接制约关系
  • 在多道程序环境下,进程是并发执行的,不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系,如等待、传递信息等,引入了进程同步的概念。进程同步是为了解决进程的异步问题。

互斥

  • 互斥,亦称间接制约关系进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。

  • 临界资源

    • 进入区
    • 临界区
    • 退出区
    • 剩余区

    注意:临界区是进程中访问临界资源的代码段;进入区和退出区是负责实现互斥的代码段。

  • 进入临界区的准则

进程互斥的软件实现方法

单标志法

双标志先检查

双标志后检查

Peterson算法

image-20211218212912896

信号量机制

信号量其实就是一个变量,可以用一个信号量来表示系统中某种资源的数量

一对原语:wait(S) signal(S) ,信号量S就是传入的参数

wait, signal原语常简称为P、V操作

整型信号量

记录型信号量

实现进程互斥

  • P(S)——申请一个资源S,如果资源不够就阻塞等待
  • V(S)——释放一个资源S,如果有进程在等待该资源,则唤醒一个进程

实现进程同步

实现前驱关系

生产者-消费者问题

问题描述

多生产者-多消费者

吸烟者问题

读者-写者问题