认识操作系统

操作系统目标及作用

现代计算机中的计算机硬件:输入设备+输出设备+存储器+运算器+控制器

image-20200908184220320

  • 操作系统(Operating System,OS):是管理计算机硬件与软件资源的系统软件,也是计算机系统的内核与基石。
    • 操作系统处理管理与配置内存
    • 决定系统资源供需的优先次序
    • 控制输入与输出设备
    • 操作网络与管理文件系统等基本事务
    • 提供一个让用户与系统交互的操作界面

操作系统的目标

  1. 方便性
  2. 有效性
  3. 可扩充性
  4. 开放性

操作系统的作用

  1. 作为用户与计算机硬件系统之间的接口:OS处于用户与计算机硬件系统之间,用户通过OS来使用计算机系统。image-20200909195136530
  2. 作为计算机系统资源的管理者:管理计算机资源,这些资源包括CPU、内存、磁盘驱动器、打印机等。
  3. 实现了对计算机资源的抽象:为其他软件软件提供服务,操作系统与软件进行交互,以便为其分配运行所需的任何必要资源。

操作系统发展过程

未配置操作系统计算机系统

  1. 人工操作
  2. 脱机输入/输出(Off-Line I/O)方式
    1. 脱机IO:事先将装有用户程序和数据的纸带装入纸带输入机,在一台外围机的控制下,把纸带上的数据输入到磁带上。当CPU需要这些程序和数据时,再从磁带上高速地调入内存;
    2. 联机IO:在主机的直接控制下进行输入/输出的方式,称为联机输入/输出(On-Line I/O)方式

单道批处理系统

  • 具体的工作过程是首先由监督程序将磁带上的第一个作业装入内存,并把运行控制权交给作业;该作业处理完时,又把控制权交给监督程序,再有监督程序把磁带的第二个作业调入内存等等。可以看成是串行的。

  • 优点:解决人机矛盾和CPU与IO设备速度不匹配问题,提高系统资源的利用率和系统吞吐量。

  • 缺点:不能充分的利用系统资源,现很少使用。

多道批处理系统

  • 用户所提交的作业先放在外存上,并排成一个对列(后备对列),由作业调度程序按照一定的算法,从后备对列中选择若干个作业调入内存,使其共享CPU和系统中的各种资源。同时在内存中装入若干程序,这样可以在A程序运行时,利用其IO操作而暂停的CPU空挡时间,再调度另一道程序B运行,同样可以利用B程序在IO操作时调用CPU空档调用程序C运行,使用多道程序交替运行,始终保持CPU忙碌的状态。
  • 优势:资源利用率高,使CPU始终处于忙碌的状态,提高内存的利用率,提高IO利用率;系统吞吐量大(CPU和其资源始终保持忙碌的状态,仅在作业完成时或者运行不下去的时候才切换,系统开销小)。
  • 缺点:平均周转时间长,无交互能力。

分时系统(Time Sharing System)

分时系统概念

在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统,该系统允许多个用户同时通过自己的终端,以交互方式使用计算机,共享主机中的资源。

分时系统特征

  1. 多路性:多用户同时在各自终端上使用同一CPU。
  2. 独立性:用户可彼此独立操作,互不干扰,互不混淆。
  3. 及时性:用户在短时间内可得到系统的及时回答。
  4. 交互性:用户与系统进行人机对话。

实时系统(Real Time System)

实时系统概念

系统能及时响应外部事件的请求,在规定的时间内完成对该事件的处理,并控制所有实时任务协调一致地运行。

实时系统的类型

  1. 工业(武器)控制系统
  2. 信息查询系统
  3. 多媒体系统
  4. 嵌入式系统

实时任务的类型

  1. 周期性实行任务和非周期性实时任务。
  2. 硬实时任务和软实时任务。

实时任务特征

  1. 多任务:由于真实世界的事件的异步性,能够运行许多并发进程或任务是很重要的。多任务提供了一个较好的对真实世界的匹配,因为它允许对应于许多外部事件的多线程执行。系统内核分配CPU给这些任务来获得并发性。
  2. 抢占调度:真实世界的事件具有继承的优先级,在分配CPU的时候要注意到这些优先级。基于优先级的抢占调度,任务都被指定了优先级,在能够执行的任务(没有被挂起或正在等待资源)中,优先级最高的任务被分配CPU资源。换句话说,当一个高优先级的任务变为可执行态,它会立即抢占当前正在运行的较低优先级的任务。
  3. 任务间的通讯与同步:在一个实时系统中,可能有许多任务作为一个应用的一部分执行。系统必须提供这些任务间的快速且功能强大的通信机制。内核也要提供为了有效地共享不可抢占的资源或临界区所需的同步机制。
  4. 任务与中断之间的通信:尽管真实世界的事件通常作为中断方式到来,但为了提供有效的排队、优先化和减少中断延时,我们通常希望在任务级处理相应的工作。所以需要在任务级和中断级之间存在通信。

操作系统的基本特征

image-20200913173604664

并发(Concurrence)

  • 并行:指两个或多个事件在同一时刻发生

  • 并发:指两个或多个事件在同一时间间隔内发生

  • 具体地说:并发指在一段时间内宏观上有多个程序在同时运行,但在单处理机系统中,每一时刻却仅能有一道程序执行,故在微观上这些程序是分时地交替执行。
    若计算机系统有多个处理机,这些可以并发执行的程序便可以被分配到多个处理机上,实现并行执行。即利用每一个处理机来处理一个可并发执行的程序。

  • 引入概念【进程】:指在系统中能独立运行 并作为资源分配的基本单位,它是由一组机器指令、数据和堆栈等组成的,是一个能独立运行的活动实体。

  • 在一个没有引入进程的系统中,属于同一个应用程序的计算机程序和 I/O程序之间只能是顺序执行,也就是计算机程序执行告一段落后,才允许I/O程序执行;反之,在程序执行I/O操作时,计算程序也不能执行。———–为计算程序和I/O程序分别建立一个进程(Process)后,这两个程序就可以 并发执行。

image-20200913161252525

共享(Sharing)

  • 在OS环境下的资源共享或称为资源复用,指的是系统中的资源可供内存中多个并发执行的进程共同使用。 ——-在宏观上既限定了时间(进程在内存期间),也限定了地点(内存)。
  • 实现资源共享的两种方式
    • 互斥共享方式:系统中的某些资源:如打印机、磁带机等,虽然可以提供给多个进程(线程)使用,但是应规定在一段时间内,只允许一个进程访问该资源。
      -------“临界资源”:一段时间内只允许一个进程访问的资源
    • 同时访问方式:系统中还有另外一些资源,允许在一段时间内由多个进程“同时”对它们进行访问。 ——这里的“同时”也就是前面讲的在微观下交替进行的。
      典型的例子:磁盘设备!

并发和共享是OS的两个最基本的特征!

虚拟(Virtual)

虚拟和异步是依赖于并发特性的。

所谓虚拟(Virtual)是指通过某种技术把一个物理实体变成为若干个逻辑上的对应物。
物理实体是实际存在的东西,逻辑实体是虚的,它并不存在,但是用户却感觉它存在。
用于实现虚拟的技术称为虚拟技术,在操作系统中利用了两种方式实现虚拟技术:时分复用技术和空分复用技术。

时分复用技术

时分复用技术概念:将资源在不同的时间片内分配给各进程以使该资源被重复利用,从而提高资源的利用率。如采用时分复用的虚拟处理机,能够在不同的时间片内处理多个用户的请求,从而使得用户感觉自己独占主机,而处理机在这期间也被充分的利用。

  1. 虚拟处理机技术:一台处理机,通过时分复用的方法,能实现同时(宏观上)为多个用户服务,亦即,利用多道程序设计技术,可将一台物理上的处理机虚拟为多台逻辑上的处理机 —- 虚拟处理机。
  2. 虚拟设备技术:通过时分复用的方法,将一台物理I/O设备虚拟为多台逻辑上的I/O设备,并允许每个用户占用一台逻辑上的I/O设备。
  • 这样可使原来仅允许在一段时间内由一个用户访问的设备(即临界资源),变为允许多个用户“同时”访问的共享设备

  • 当一种资源在时间上复用时,不同的程序或用户轮流使用它。时分复用技术通过利用处理及的空闲时间运行其他程序,提高了处理机的利用率

空用复用技术

  • 实质上就是每次只把用户程序的一部分调入内存运行,运行完成后将该部分换出,再换入另一部分到内存中执行,通过这样的置换功能,实现了用户程序的各个部分分时地进入内存运行。

  • 让同一个频段在不同的空间内得到重复利用。空分复用技术利用存储器的空闲空间分区域分存放和运行其他多道程序,以此来提高内存的利用率。

注意:采用分时复用技术,每台虚拟设备的平均速度必然等于或低于物理设备速度的1/N,同理,采用空分复用技术,一台虚拟设备平均占用的空间必然等于或低于物理设备所拥有空间的1/N

异步

  • 由于资源等因素的限制,使进程的执行通常都不可能“一气呵成”,而是以“走走停停”的方式运行。

    对于内存中的每个进程,在何时能获得处理机执行,何时又因提出某种资源请求而暂停,以及进程以怎样的速度向前推进,每道程序总共需要多少时间才能完成等等,都是不可预知的

    进程是以人们不可预知的速度向前推进的,此即进程的异步性

操作系统的主要功能

处理机管理功能

操作系统关于进程方面管理任务有如下几种:进程控制进程同步进程通信调度

进程控制

  • 为作业创建进程、撤销(终止)已结束的进程,控制进程在运行过程中的状态转换。

进程同步

  • 为了使多进程同时运行时协调,有两种方式
    • 进程互斥方式:进程在对临界资源进行访问时,应采用互斥方式。(临界资源加锁实现,关锁时禁止访问;锁开时允许访问。
    • 进程同步方式:相互合作去完成共同任务的进程间,由同步机构对他们的执行次序加以协调。(信号量机制

进程通信

  • 实现相互合作进程之间的信息交换。

调度

  1. 作业调度:从后备队列中按照一定算法选择出若干个作业,为他们分配运行所需资源,讲作业调入内存后,分别建立与之对应的进程,使它们成为可能获得处理机的就绪进程,并将他们插入就绪队列中。
  2. 进程调度:从进程就绪队列中按照一定算法选出一个进程,将处理机分配给他,并为他设置运行现场,使其投入执行。

存储器管理功能

内存管理主要功能:内存分配内存保护地址映射内存扩充

内存分配

  1. 作用:为每道程序分配内存空间;提高存储器利用率,尽量减少内存空间碎片。
  2. 两种内存分配方式
    1. 动态内存分配:每个作业所要求的基本内存空间也是在装入时确定的,但允许作业在运行过程中继续申请新的附加内存空间,以适应程序和数据的动态增长,也允许作业在内存中“移动”。
    2. 静态内存分配:每个作业的内存空间是在作业装入时确定的;在作业装入后的整个运行期间,不允许该作业再申请新的内存空间,也不允许作业在内存中“移动”。
  3. 内存分配机制应具有的结构和功能:内存分配数据结构、内存分配功能、内存回收功能。

内存保护

  1. 主要作用:确保每道用户程序都只在自己的内存空间内运行,彼此互不干扰;绝不允许用户程序访问操作系统的程序和数据;也不允许用户程序转移到非共享的其它用户程序中去执行。
  2. 内存保护机制:设置两个界限寄存器,分别用于存放正在执行程序的上界和下界。系统对每条指令所要访问的地址进行检查,如果发生越界,产生越界中断请求,停止该程序的执行。

地址映射

  • 程序的逻辑地址通常从0开始,而物理地址不从0开始,因此需要一个映射转换过程。主要功能即为:将地址空间的逻辑地址转换为内存空间与之对应的物理地址。

内存扩充

  1. 借助于虚拟存储技术,从逻辑上去扩充内存容量。
  2. 为了能在逻辑上扩充内存,系统必须具有内存扩充机制,用于实现下述各功能:
    1. 请求调入功能:允许在装入一部分用户程序和数据的情况下,便能启动该程序运行。在程序运行过程中,若发现要继续运行时所需的程序和数据尚未装入内存,可向 OS 发出请求,由 OS 从磁盘中将所需部分调入内存,以便继续运行。
    2. 置换功能:若发现在内存中已无足够的空间来装入需要调入的程序和数据时,系统应能将内存中的一部分暂时不用的程序和数据调至盘上,以腾出内存空间,然后再将所需调入的部分装入内存。

设备管理功能

  • 主要任务
    • 完成用户进程提出的I/O请求;为用户进程分配其所需的I/O设备;
    • 提高CPU和I/O设备的利用率;提高I/O速度;方便用户使用I/O设备。
  • 为此,设备管理应具有缓冲管理设备分配设备处理等功能。

缓冲管理

  • CPU运行的高速性和I/O低速性间的矛盾自计算机诞生时起便已存在。
    如果在I/O设备和CPU之间引入缓冲,则可有效地缓和CPU和I/O设备速度不匹配的矛盾,提高CPU的利用率,进而提高系统吞吐量。
    因此,在现代计算机系统中, 都毫无例外地在内存中设置了缓冲区,而且还可通过增加缓冲区容量的方法,来改善系统的性能

设备分配

  • 设备分配的基本任务,是根据用户进程的I/O请求、系统的现有资源情况以及按照某种设备分配策略,为之分配其所需的设备。如果在I/O设备和CPU之间,还存在着设备控制器和I/O通道时,还须为分配出去的设备分配相应的控制器和通道。

设备处理

  • 设备处理程序又称为设备驱动程序。基本任务是用于实现CPU和设备控制器之间的通信,即由CPU向设备控制器发出I/O命令,要求它完成指定的I/O操作;反之,由CPU接收从控制器发来的中断请求,并给予迅速的响应和相应的处理。
  • 处理过程是:设备处理程序首先检查I/O请求的合法性,了解设备状态是否是空闲的,了解有关的传递参数及设置设备的工作方式。然后向设备控制器发出I/O命令,启动I/O设备去完成指定的I/O操作。

文件管理功能

  • 文件管理的主要任务是对用户文件和系统文件进行管理以方便用户使用并保证文件的安全性。
    为此,文件管理应具有对文件存储空间的管理目录管理文件的读/写管理以及文件的共享与保护等功能。

文件存储空间的管理

  • 由文件系统对诸多文件及文件的存储空间,实施统一的管理。其主要任务是为每个文件分配必要的外存空间,提高外存的利用率,进而提高文件系统的存、取速度。
  • 为此,系统中应设置用于记录文件存储空间使用情况的数据结构,以供分配存储空间时参考,还应具备对存储空间进行分配和回收的功能

目录管理

  • 目录管理的主要任务,是为每个文件建立一个目录项,并对众多的目录项加以有效的组织,以实现方便的按名存取。
  • 通常由系统为每个文件建立一个目录项。目录项包括文件名、文件属性、文件在磁盘上的物理位置等。由若干个目录项又可构成一个目录文件。即用户只须提供文件名, 即可对该文件进行存取。

文件的读/写管理

  • 该功能是根据用户的请求,从外存中读取数据;或将数据写入外存。由于读和写操作不会同时进行,故可合用一个读/写指针。

文件的共享与保护

  • 防止未经核准的用户存取文件;防止冒名顶替存取文件;防止以不正确的方式使用文件。

操作系统与用户之间的接口

  • 引题:image-20200913171719035

  • 包含关系:image-20200913172420937

用户接口

  • 为了方便用户直接/间接控制自己的作业,操作系统提供了命令接口,该接口又分为联机用户接口脱机用户接口图形用户接口3种
联机用户接口
  • 用户说一句,系统做一句。用户可通过先后键入不同命令的方式,来实现对作业的控制,直至作业完成。
  • image-20200913170246761
脱机用户接口
  • 用户说一堆,系统做一堆。该接口是为批处理image-20200913170618948
图形用户接口
  • 采用图形化操作界面。

程序接口

  • 由一组系统调用命令(简称系统调用,也称广义指令)组成。
  • 系统调用的目的:请求系统服务
  • 系统调用/程序接口/程序接口 是操作系统提供给编程人员的接口 选Cimage-20200913175632848
  • 系统调用≠库函数 选Aimage-20200913175227658

注意事项:

image-20200913171920463

操作系统的结构

传统OS结构

无结构OS

  • OS的各部分是以最基本的过程存在,每个过程都可随意地调用其他过程

模块化结构OS

基本概念
  • 对OS的各部分经过了划分,行程若干个具有一定独立性和大小的模块

image-20200914164420048

模块独立性
  • 模块划分过小→降低本身复杂性,但会引起模块之间联系过多,造成系统混乱
  • 模块划分过大→增加模块内部复杂性,使内部联系增加
  • 内聚性:指模块内部各部分间联系的亲密程度。内聚性高→模块独立性强
  • 耦合度:指模块间相互联系和相互影响的程度。耦合度低→模块独立性强。
模块接口法的优缺点
  • 优点
    • 提高OS设计的正确性、可理解性和可维护性
    • 增强OS的可适应性
    • 加速OS的开发过程
  • 不足/存在的问题
    • 接口规定困难
    • 存在无序性

分层式结构OS

分层式结构概念
  • 目标系统An和裸机系统A0之间有许多层次软件:A1,A2,A3….An-1,使An通过这几层最终能在A0上运行。

image-20200914170157431

分层结构的优缺点
  • 优点
    • 易保证系统的正确性:自下而上的设计方式使所有设计的决定都是有序的或者说是建立在较为可靠的基础上的,这样比较容易保证整个系统的正确性。
    • 具有易扩充和易维护性:在系统中增加、修改或替换一个层次中模块或整个层次时,只要不改变相应层次间接口,就不会影响其他层次,这就使得维护和扩充变得easy。
  • 缺点
    • 系统效率降低:由于层次结构是分层单项依赖的,必须在每层间都建立层次间的通信机制,OS执行一个功能就得由上到下穿越多层次,就会增加系统通信开销,从而导致系统效率降低。

客户端/服务端

客户/服务器模式由来、组成和类型

  • 客户机:每台客户机都是一个自主计算机,具有一定处理能力,客户进程在其上运行,平时处理一些本地业务,也可以发送一个消息给服务器用以请求某项服务
  • 服务器:通常是一台规模较大的机器,含有网络文件系统或数据库系统,应能为网上所有用户提供一种或多种服务。
  • 网络系统:用于连接所有客户机和服务器,实现他们之间通信和网络资源共享的系统

客户/服务器之间交互

一次完整的交互过程可以分成以下四步:

  1. 客户发送请求消息
  2. 服务器接收消息
  3. 服务器回送信息
  4. 客户机接收消息

客户/服务器模式优点

  1. 数据的分布处理和存储
  2. 便于集中管理
  3. 灵活性和可扩充性
  4. 便于改编应用软件

ps:经常会问到 在微内核OS中,为什么要采用客户/服务器模式?我们答客户/服务器模式的优点即可

微内核

微内核OS的基本概念

微内核技术——把操作系统中更多的成分和功能放到更高的层次(用户模式)中去运行,而留下一个尽量小的内核,用它来完成操作系统最基本的核心功能。

  1. 足够小的内核:微内核≠一个完整的OS,含有:
    1. 与硬件处理紧密相关的部分
    2. 一些较基本的功能
    3. 客户和服务器之间的通信
  2. 基于【客户/服务器模式】image-20200914173409746
  3. 应用”机制和策略分离”原理
    1. 机制:是指在实现某一功能时的具体规定或说原则
    2. 策略:在机制的基础上,借助某些参数和算法,用以实现该功能的优化,或达到不同的目标
  4. 采用面向对象技术

微内核的基本功能

基于【机制与策略分离】的原理,将机制部分以及与硬件紧密相关的部分放入微内核中。由此微内核通常具有如下几个方面功能:

  1. 进程(线程)管理
  2. 低级存储器管理
  3. 中断和陷入处理

微内核操作系统的优点

  1. 提高了系统的可扩展性
  2. 增强了系统的可靠性
  3. 可移植性强
  4. 提供了对分布式系统的支持
  5. 新技术——融入了面向对象技术

微内核操作系统存在的问题

  1. 缺点:微内核操作系统的运行效率相较早期操作系统有所降低
  2. 改进方法:可以把一些常用的操作系统基本功能由服务器移入微内核中

进程和线程

前趋图和程序执行

前趋图

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

程序执行

程序顺序执行

  • 特征:
    • 顺序性:所谓顺序性是指,处理机严格的按照程序所规定的顺序执行,一个操作的开始必须在其前一个操作结束之后。
    • 封闭性:所谓封闭性是指,程序在执行的时候独占全机的资源
    • 可再现性:所谓可再现性是指,只要初始条件运行环境系统相同,其运行结果一定是一样的。

程序并发执行

  • 事实上,只有不存在前趋关系的程序之间才有可能并发执行,否则无法并发执行

  • 特征:

    • 间断性:所谓间断性指的是,由于多个程序对资源的要求产生的制约性,而导致的某一个程序在运行时等待资源的情况。 比如有两个程序都需要使用打印机这个资源,如果其中的一个程序已经占用,而另一个必须等待。这样后者表现出来的就是程序运行时的间断性。
    • 失去封闭性:所谓失去封闭性指的是,由于多个程序并发执行会共享资源,从而导致各个程序运行环境会失去封闭性。
    • 不可再现性:所谓不可再现性是指相同的输入,由于资源的共享,导致最后的输出结果不同。

进程的描述

进程的定义和特征

定义

  • 程序:是静态的,是一个存放在磁盘里的可执行文件,是一系列的指令集合

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

    其中,进程实体包含三部分:程序段相关的数据段PCB

  • 程序进程关系:一个程序多次执行会对应多个进程,比如说QQ可以登录三个账号。那么既然都是QQ,那OS是怎么区分不同进程的呢?当进程被创建的时候,OS会为该进程分配一个唯一的,不重复身份证——PID(Process ID,进程ID)image-20200916193516137

  • 进程控制块(PCB):OS需要记录进程PID,分配了哪些资源,运行情况,那么这些信息需要记录到哪里呢?答案就是进程控制块——PCB。image-20200916192007658

    • 作用:PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位,一个能与其他进程并发执行的进程。下面是具体作用:
      • 作为独立运行基本单位的标志:在进程的整个生命周期中,系统总是通过PCB对进程进行控制的,亦即系统是根据 进程的PCB感知该进程的存在的,所以,PCB是进程存在的唯一标志。
      • 能实现间断性运行方式
      • 提供进程管理所需要的信息
      • 提供进程调度所需要的信息
      • 实现与其他进程的同步与通信

特征

  • 主要由:动态性,并发性,独立性,异步性,结构性组成。

image-20200916193752881

进程的基本状态及转换

image-20200916194141953

进程的状态

进程状态有五种:创建状态,就绪状态,执行状态,阻塞状态,终止状态;其中就绪、执行、阻塞是三种基本状态。

创建态、就绪态

  • 创建状态:对于处于创建态的进程,当其获得了所需的资源以及对其PCB的初始化工作完成后,便可由创建态转入就绪态
  • 就绪状态:进程已经处于准备好运行的状态了,只需要CPU临门一脚便可以立即执行。

运行态

  • 运行态:指进程已经获CPU,其程序正在执行的状态。在单处理机系统中,只有一个进程处于执行状态,而在多处理机系统中,有多个进程处于执行状态。

image-20200916195133485

阻塞态

  • 阻塞态:指正在执行的进程由于发生某事件(I/O请求,申请缓冲区失败等)暂时无法继续执行时的状态,亦即进程的执行收到阻塞。image-20200916203322409

终止态

  • 终止态:即一个进程达到了自然结束点,或是出现了无法克服的错误,或是被操作系统所终结,或是被其他有终止权的进程所终结,它将进入终止状态。

    image-20200916204018353

进程的转换

三态模型

  • 基本的三态模型:这里写图片描述

五态模型

  • 未引入挂起的五态模型:

image-20200916204307618

引起进程状态转换的具体原因如下:

  • NULL→新建态:执行一个程序,创建一个子进程。
  • 新建态→就绪态:当操作系统完成了进程创建的必要操作,并且当前系统的性能和虚拟内存的容量均允许。

  • 就绪态→运行态:进程被调度

  • 运行态→终止态:当一个进程到达了自然结束点,或是出现了无法克服的错误,或是被操作系统所终结,或是被其他有终止权的进程所终结。

  • 运行态→就绪态:运行时间片到;出现有更高优先权进程。

  • 运行态→阻塞态:等待使用资源;如等待外设传输;等待人工干预。

  • 阻塞态→就绪态:申请资源被分配,或等待的事件已经发生了

  • 就绪态→终止态:未在状态转换图中显示,但某些操作系统允许父进程终结子进程。

  • 阻塞态→终止态:未在状态转换图中显示,但某些操作系统允许父进程终结子进程。
  • 终止态→NULL:完成善后操作。

七态模型

接下来,我们引入了两个操作:挂起和激活

当挂起操作作用于某个进程时,该进程将被将被挂起,意味着此时该进程处于静止状态;

假如进程正在执行,他将暂停执行。

假如进程原本就处于就绪状态,则该进程此时暂不接受调度。

与挂起操作对应的就是激活啦。

  • 引入挂起后的进程状态转换五态模型:

这里写图片描述

  • 引入创建和终止——七态模型:

    image-20201005151351838

这里写图片描述

引起进程状态转换的具体原因如下:

  • 等待态—→挂起等待态:如果当前不存在就绪进程,那么至少有一个等待态进程将被对换出去成为挂起等待态;操作系统根据当前资源状况和性能要求,可以决定把等待态进程对换出去成为挂起等待态。
  • 挂起等待态—→挂起就绪态:引起进程等待的事件发生之后,相应的挂起等待态进程将转换为挂起就绪态。
  • 挂起就绪态—→就绪态:当内存中没有就绪态进程,或者挂起就绪态进程具有比就绪态进程更高的优先级,系统将把挂起就绪态进程转换成就绪态。
  • 就绪态—→挂起就绪态:操作系统根据当前资源状况和性能要求,也可以决定把就绪态进程对换出去成为挂起就绪态。
  • 挂起等待态—→等待态:当一个进程等待一个事件时,原则上不需要把它调入内存。但是在下面一种情况下,这一状态变化是可能的。当一个进程退出后,主存已经有了一大块自由空间,而某个挂起等待态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束,此时便发生了这一状态变化。
  • 运行态—→挂起就绪态:当一个具有较高优先级的挂起等待态进程的等待事件结束后,它需要抢占 CPU,,而此时主存空间不够,从而可能导致正在运行的进程转化为挂起就绪态。另外处于运行态的进程也可以自己挂起自己。
  • 新建态—→挂起就绪态:考虑到系统当前资源状况和性能要求,可以决定新建的进程将被对换出去成为挂起就绪态。

进程的组织

线性方式

  • 不论进程的状态如何,将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。

链接方式

  • 系统按照进程的状态将进程的PCB组成队列,从而形成就绪队列、阻塞队列、运行队列等。image-20200919213505282

索引方式

  • 该方式是线性表方式的改进,系统按照进程的状态分别建立就绪索引表、阻塞索引表等。image-20200919213530758

进程控制

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

简单来说,进程控制→实现进程状态转换。

image-20200919213859096

  • 简单的流程图:

    image-20201005155458987

OS内核

image-20200919214807617

与硬件紧密相关的模块、各种常用的设备的驱动程序以及运行频率较高的模块,安排在紧靠硬件的软件层次中,将它们常驻内存,通常被称为OS内核也就是OS内核其实本质上是各个模块

原语

  • 我们知道原语的执行具有原子性,它执行过程只能一气呵成,不允许被打断,那么为什么要一气呵成呢?下图即为解释,假如不一气呵成,就会导致操作系统某些关键的数据结构信息不统一,就会影响操作系统进行别的管理工作image-20200919215018317
  • 如何实现原语的原子性呢?其实是利用了“关中断指令“和”开中断指令“;
  • CPU执行了关中断指令后,不会再check中断信号,直到遇到了开中断指令才会再去check;
  • 因此关——开中断之间的指令是连续的,不可中断的,这就实现了原子性;image-20200919215955758

进程的创建

创建原语:

  1. 申请空白PCB
  2. 为新进程分配所需的资源
  3. 初始化PCB
  4. 将PCB插入就绪队列

哪里会用到进程创建呢?

  1. 用户登录
  2. 作业调度
  3. 提供服务
  4. 应用请求

image-20200919220556546

进程的终止

终止/撤销原语:

  1. 从PCB集合中找到终止进程的PCB
  2. 若该进程正在运行,立刻剥夺CPU,将CPU分配给其他进程
  3. 终止其所有子进程
  4. 将该进程所拥有的所有资源还给父进程或操作系统
  5. 删除PCB

哪里会用到进程终止呢?

  1. 正常结束:进程自己请求终止
  2. 异常结束:非法使用特权指令
  3. 外界干预:用户自己选择杀某进程

image-20200919222346641

进程的阻塞和唤醒

被什么事件所阻塞就会被该事件所唤醒

image-20200919222900878

进程的切换

切换原语:

  1. 运行环境信息存入PCB
  2. PCB移入相应队列
  3. 选择另一个进程执行,并更新其PCB
  4. 根据PCB恢复进程所需的运行环境

这里有一个地方:进程所需的运行环境是什么东西呢?

image-20200920180827278

首先回顾一下我们程序是如何运行的:是通过把我们的代码保存到硬盘然后转入内存,然后CPU去从内存中读取一条条指令,然后我们的程序就跑起来了。那么CPU中有个东西 叫做寄存器。它们有不同的功能,比如可以存放下一条指令地址,也可以存放正在执行的指令,也可以保存暂时运算得到的结果;然而我们知道寄存器并不是很专一的,他有可能会随时被其他的进程使用,那我们之前运算的结果啊,什么保存的指令啊,岂不是都不见了吗?这个时候就会用到我们的PCB了,它能够保持关键的一些信息,也就是运行环境,这样等我们的寄存器又空闲下来了的时候,我们就可以继续我们未完成的指令啦。image-20200920181231409

进程同步

进程同步与互斥

首先,我们回顾一下我们之前学的进程异步问题,由于并发执行的进程以各自独立,不可预知速度向前推进,我们所得到的结果往往也会不一样,而我们往往有时候需要控制一个事件的发生在一个事件前,那么就需要进程同步

同步也称为直接制约关系,是指为了完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系

image-20200924203323774

有进程同步就有进程互斥,那么进程互斥又是什么呢?

要明白互斥,就引入了一个概念:临界资源

临界资源,即一个时间段内只允许一个进程使用的资源。对于该资源我们必须互斥的访问,也就是我访问,你不能访问,反之亦然;因此,进程互斥,即指当一个进程访问某临界资源时,另一个想访问此临界资源的进程必须要等待,只有当我正在访问该资源的进程访问结束了,释放掉了,下一个进程才能去访问该资源。

image-20200924203831680

那么我们一般是如何进行对临界资源的访问的呢?image-20200924204737502

  • 进入区:负责检查是否可以进入临界区(上锁)
  • 临界区:访问临界资源的那段代码
  • 退出区:用于将临界区正被访问的标志恢复为未被访问的标志
  • 剩余区:做其他处理

ps:临界区是进程中访问临界资源的代码段;进入区和退出区是负责实现互斥的代码段;临界区也被称为”临界段

同步机制遵循的规则

  • 空闲让进:多中选一
  • 忙则等待:互斥访问
  • 有限等待:避免死等
  • 让权等待:避免忙等

image-20200924205632915

硬件同步机制

让硬件同步即为进程互斥的硬件实现方法:中断屏蔽方法,TestAndSet,Swap指令

image-20200924211219675

中断屏蔽方法

  • 在进入锁测试之前关闭中断,直到完成锁测试并上锁之后才能打开中断。

image-20200924211536165

TestAndSet

简称TS指令,也有称TestAndSetLock指令,或TSL指令

用TS指令管理临界区的时候,为每个临界资源设置一个布尔变量lock;

用lock的布尔值就可以判断资源是否空闲,进程能否访问。

  • 优点:实现简单;适用于多处理机的环境
  • 缺点:不满足让权等待

image-20201005153906850

Swap指令

有的地方称为Exchange指令,或XCHG指令;Swap指令用硬件实现,不允许被中断

Swap指令与TS指令在逻辑上其实差不多,但Swap需要两个参数,不需要返回值,TS需要一个共享的变量实现互斥,因此在不同的地方就要用不同的方式去进行进程互斥。

image-20201005153942707

信号量

信号量机制

image-20200927175523422

由于之前的措施方案无法实现进程的“让权等待”问题,因此我们引出了信号量这个概念进行解决;

image-20200927220306063

整型信号量

  • Dijkstra把整型信号量定义为一个用于表示资源数目的整形量S,它仅能通过P\V操作进行访问。(P\V 即 wait & signal)这两个操作是原子操作,是不可以在执行过程中被中断的。
  • 整形信号量存在的问题:不满足让权等待原则

image-20200927221635070

记录型信号量

  • 对于每次的wait操作,意味着进程请求一个单位的该类资源,使系统中可供分配的该类资源数减少一个,因此描述为S→value–;S→value < 0时,表 示该类资源已分配完毕,因此进程应调用block原语进行自我阻塞,放弃处理机,并插入到信号量链表S→list中

  • 对于每次的signal操作,意味着执行进程释放一个单位资源,使系统中可供分配的该类资源数增加一个,故S→value++操作表示资源数目+1。若+1后还是S→value <= 0,表示在该信号量链表中仍有等待该资源的进程被阻塞了,故应该调用wakeup原语,将S→list链表中的第一个等待进程唤醒。(被唤醒进程从阻塞态→就绪态)

    image-20201005154049852

ps:记录型信号量可实现进程互斥、进程同步;如果出现了P(S),V(S)的操作,除非默认说明,默认S为记录型信号量

信号量应用

实现进程互斥

image-20200928152442455

  • 为使得多个进程互斥访问某临界资源【目的】,为该资源设置 互斥信号量【mutex】,初始值为1
  • 将该资源置于P、V操作之间;
  • 注意:利用信号量机制去实现进程互斥时必须保证我们的P\V操作是成对出现的
    • 缺少P会导致系统混乱,不能保证对临界资源互斥访问
    • 缺少V将会使临界资源永远不被释放,导致临界资源永远不被释放,从而使因等待该资源的阻塞的进程不能被唤醒
实现进程同步
  • 进程同步:要让各并发进程按要求有序地推进

image-20200928160518569

现在P1,P2并发执行,由于存在异步性,二者交替推进次序无法控制,是不确定的;

假如我P2的代码4需要用到P1的代码1、2、3运行结果才能执行的话,我就得保证代码4是在代码3后执行;

此即进程同步问题:让本异步并发的进程互相配合,有序推进。

重点:在前操作之后执行V(S),在后操作之前执行P(S); image-20200928200922651

实现前趋关系

每一对的前趋关系都是一个进程同步的问题(为了保证一前一后的操作)

为了实现这个目标,我们需要做的事情

  1. 为每一对前趋关系各设置一个同步信号量
  2. 在【前操作】的之后相对应的同步信号量执行V
  3. 在【后操作】的之前相对应的同步信号量执行P

image-20200928201842866

管程

引子

  • 为什么要引入管程?因为信号量机制存在一定的问题:编写程序困难,容易出错(废话,这么多PV操作,想不错都难)因此我们在1973年引入管程机制进行处理;

管程的定义

代表资源的数据结构以及由对该共享数据结构实施操作的一组过程所造成的资源管理程序共同构成了一个操作系统的资源管理模块——管程

管程是一种特殊的软件模块,由以下部分组成:

  1. 局部于管程的共享数据结构说明;
  2. 对该数据结构进行操作的一组过程(就是函数)
  3. 对局部于管程的共享数据设置初始值的语句【对数据结构初始化的语句】
  4. 管程有一个名字

发现了吗,管程和我们面向对象的有点相似——可以定义一些数据,可以定义一些对这些数据操作的函数,对属性初始化的语句。

管程的基本特征

  1. 局部于管程的数据只能被局部于管程的过程所访问
  2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  3. 每次仅允许一个进程在管程内执行某个内部过程

什么意思呢?通过1+2我们可以知道,假如我们要修改管程内的数据结构,我们只能够通过调用管程内封装好的方法(函数)去修改数据结构;而3则实现了进程互斥

管程中的条件变量

我们使用管程实现进程同步需要用到同步工具,如wait,signal;

但仅仅有这两个是不够的,我们知道,每次仅能有一个进程进入管程,假如某进程在管程中被挂起或阻塞就得等很久了,那么解决这问题就引入了——条件变量 condition

怎么用呢?管程中对每个条件变量以说明:condition x,y;条件变量的操作是wait,signal;

每个条件变量保存一个链表,用以记录因为这条件变量所阻塞的所有进程,提供2个操作:

x.wait 和 x.signal

  • x.wait:正在调用管程的进程因为x条件需要被阻塞或者挂起,调用x.wait将自己插入到x条件的等待队列上,并释放管程,直到x条件变化。此时其他进程可以使用该管程——让出了入口。
  • x.signal:若正在调用管程的进程发现x条件发生了变化,则调用x.signal重新启动一个因x条件而阻塞或挂起的进程,如果存在多个这样的进程,则选择一个,如果没有,则继续执行原进程,而不产生任何结果。
    • 注意了 这与信号量机制的signal操作不能混为一谈,信号量中的signal需要s++操作,信号量改变了。

管程解决生产者消费者问题

image-20201001155941689

  1. 假如两个生产者进程并发执行,依次调用insert过程的话:
    1. 第一个生产者进程可以顺利执行完insert函数
    2. 假如在第一个生产者进程还未结束的时候,第二个生产者进程插入进来了,就会把第二个进程阻塞在insert函数后面,排队
  2. 假如两个消费者进程先执行,生产者进程后执行的话:
    1. 第一个进程进来,发现count = 0,那么就执行wait操作,就等待在empty变量相关的队列中
    2. 同样的,第二个就排在了empty变量相关的队列中
    3. 此时假如有个生产者进程进来了,进行生产,把生产品放在了缓冲区当中,假如发现自己的产品是第一个产品,那么此时有可能有别的消费者进程在等待产品,就执行一个唤醒操作,唤醒一个消费者进程。
    4. 然后count–,检查拿走前缓冲区是否是满的,假如是满的,说明有生产者进程需要被唤醒,就来一个signal(full)操作。

Java中类似管程的机制

Java中,如果用关键字【synchronized】描述一个函数,那么这个函数同一个时间段只能被一个线程调用。

image-20201001164432414

经典的进程同步问题

生产者-消费者问题

问题描述

image-20201005154151145

问题分析
  • 缓冲区未空(有产品)V→P消费者消费
  • 缓冲区未满P→V生产者生产

image-20200928204830509

问题的解法步骤
  1. 关系分析,找出题目中描述的各个进程,分析他们之间的同步、互斥关系
  2. 根据各进程的操作流程去确定P、V的大致顺序
  3. 设置信号量,根据题目条件设信号量初值
    1. 互斥信号量初值一般为1
    2. 同步信号量的初值看对应的资源初值值(0/n…)
具体实现
  1. 设置好信号量
    1. 互斥信号量 = 1:实现对缓冲区的互斥访问
    2. 同步信号量empty = n:实现空闲缓冲区的数量
    3. 同步信号量full = 0:代表产品的数量,也即非空缓冲区的数量
  2. 分别在生产者,消费者中放置P、V操作(注意顺序,以及操作的哪个信号量)

image-20200928205550396

思考
  • 想一想 能不能改变相邻P、V操作的顺序呢?

image-20201005154232845

得出结论了:实现互斥的P操作必须放在实现同步的P操作之后;由于V操作并不会导致进程阻塞,因此两个V操作顺序可以交换

多生产者-多消费者问题

问题描述

image-20200929094120224

注意 这里的多生产者的多 代表的不是数量 而是多个类型

问题分析
  • 找出题目描述的各进程,分析它们之间同步、互斥关系;
    • 互斥关系:对缓冲区(盘子)的访问要互斥的进行
    • 同步关系:父亲放苹果,女儿才能取苹果;母亲放橘子,儿子才能取橘子;盘子为空时,父/母才能放水果,因此需要儿/女进行从盘子取水果;
  • 根据进程的操作流程确定P、V操作大致顺序
    • 实现互斥:在临界区前后分别P、V
    • 实现同步:前操作后V,后操作前P
  • 设置信号量
具体实现
  • 实现互斥访问盘子:mutex = 1
  • 多少个苹果 apple = 0
  • 多少个橘子 orange = 0
  • 盘子中还能放多少水果 plate = 1

image-20200929095442030

以父亲和女儿举例:

父亲首先应该P盘子,查看是否为空,如果为空,则V苹果(苹果++);女儿首先P苹果,查看是否准备好了,有的话就取出,V盘子(盘子++);为了保证互斥,必须在P、V操作之中加入对互斥信号量mutex 的 P、V操作。

思考

可不可以不要互斥信号量mutex?

image-20201005153712342

由于缓冲区大小为1,因此orange,apple,plate三者中最多只有一个是1;这样的话最多只有一个进程的P操作不会被阻塞,可以顺利进入临界区,因此可以顺利执行;

那么假如缓冲区(plate)数量为2呢?

那么父亲和母亲都能访问盘子,有可能出现不同进程写入缓冲区的数据相互覆盖的问题;

得出结论:如果缓冲区的大小大于1,那么就必须专门设置一个互斥信号量mutex来保证互斥的访问缓冲区

吸烟者问题

问题描述

image-20200929104120937

问题分析
  • 找出题目描述的各进程,分析它们之间同步、互斥关系;
    • 同步关系:桌上有组合1→第一个抽烟者取走;组合2→第二个抽烟者取走;组合3→第三个抽烟者取走
    • 互斥关系:桌子只有一个,可以理解为容量为1的缓冲区需要互斥访问
  • 根据进程的操作流程确定P、V操作大致顺序
  • 设置信号量

image-20200929104936547

具体实现
  • 桌上组合1、2、3分别为 offer1 offer2 offer3,他们的初值都是0
  • 设置一个信号量i,用于实现三个抽烟者轮流吸烟

image-20200929105814971

以smoker1为例,首先P(offer1)检查是否有需要的组合1,有的话就拿走去抽,并且告诉供给者抽完了,然后供给者i++,p一下finish,并将下一个组合放在桌上然后v下一个组合;

读者-写者问题

进程通信

image-20201001165028814

进程通信概念

  • 进程通信是指进程之间的信息交换。
  • 进程所拥有的内存地址空间相互独立,换而言之,进程不能直接访问另一个进程的地址空间,然而有时候有需要信息交换,那该怎么办呢?OS提供了一些方法给我们。

image-20201001165400139

共享存储

前提:两个进程对于共享空间的访问必须是互斥的。

  • 基于数据结构共享:各进程公用某些数据结构,实现各进程的信息交换:如生产者-消费者问题中的有界缓冲区。是低级通信方式。
  • 基于存储区共享:在内存中画一片共享存储区,数据形式和存放位置由进程控制而非OS。是高级通信方式。

image-20201001165948214

管道通信

  • 【管道 pipe文件】是指用于连接读写进程的一个共享文件,本质是内存空间中开辟的一个固定大小的缓冲区
  • 管道采取半双工通信,一个时间段内只能实现单向传输;
  • 进程互斥访问管道
  • 管道写满时,写进程的系统调用被阻塞;管道为空时,读进程的系统调用被阻塞
  • 没写满不准读,没读空不准写。
  • 管道数据被读出后被抛弃,意味着读进程最多只能有一个,不然可能会读错数据。

image-20201005154325305

消息传递

进程通过【格式化的消息】为单位,将通信的数据封装在消息中,通过OS提供的发送接收原语,在进程间进行消息传递,完成进程的数据交换。是一种高级通信方式。

  • 直接通信方式:发送进程利用OS提供的发送原语直接把消息发给接收进程/消息直接挂到接收方的消息队列中。

  • 间接通信方式/信箱通信方式:发送进程先发送到中间实体(信箱)中,接受进程再去接收,完成进程间的通信。

    image-20201005154353653

线程

线程的概念和特点

  • 什么是线程?为什么要引入线程?

下列是三个进程,他们所占用不同的空间内存和系统资源;假如我们要切换进程的时候,需要用保存/恢复运行环境,还需要切换内存地址空间(更新快表、更新缓存)开销非常大,因此,人们引入了线程机制

image-20201001175345544

  • 引入了线程之后,线程是CPU调度基本单位。一个线程里面可以包含多个线程。线程之间可以并发进行。
  • 但是进程依旧是资源分配基本单位,从属一进程的各线程共享使用进程的资源。
  • 同一个进程内各个进程间并发,不需要切换进程运行环境和内存地址空间,省时省力。

image-20201001180053003

引入线程后的变化

image-20201005154628052

线程的属性

image-20201005154719829

线程的特性与优点

  • 进程间并发,开销很大;线程间并发,开销很小

  • 引入线程机制之后,并发带来的系统开销降低,系统并发性提升

ps:从属于不同进程的线程间切换,也会导致进程间切换,开销也会很大。

  • 从属于同一进程的各个线程共享进程所拥有的资源。
  • 进程间通信必须请求操作系统服务(CPU需要切换到核心态),开销大;同进程下线程通信,无需OS干预,开销更小;

image-20201001193612876

线程实现方式

用户级线程

image-20201003164146178

  1. 线程的管理工作是由谁完成的?
    1. 答 线程的管理工作由应用程序通过线程库来完成的,不是通过OS完成的
  2. 线程切换是否需要CPU从用户态转换为内核态?
    1. 答 在用户态下,由应用程序通过线程库就可以进行线程切换了
  3. OS是否能意识到用户及线程的存在?
    1. 答 意识不到,只有用户能意识到有多个线程
  4. 用户级线程有什么优点和缺点?
    1. 答 优点:用户级线程的切换在用户态可以完成,不需要切换到核心态,系统开销小,效率高
    2. 缺点:假如其中某一个线程被阻塞了,其他线程都会被阻塞,并发度不高;

内核级线程

image-20201003165327004

  1. 线程的管理工作由谁来完成?
    1. 答 由OS内核完成
  2. 线程切换是否需要CPU从用户态转换到内核态?
    1. 答 由于线程调度、切换工作由内核负责,因此在内核级线程的线程切换时需要从用户态转换到内核态的。
  3. OS能否意识到内核级线程的存在?
    1. 答 OS会为每个内核级线程建立对应TCB,然后通过TCB对线程进行管理,因此,OS能够意识到内核级线程的存在
  4. 内核级线程的实现方式的优缺点?
    1. 答 优点:内核级线程是处理机调度的基本单位,而进程只作为资源分配的基本单位;因此在多核CPU中,这几个线程可以被分配在多个不同cpu中并发执行,其中一个线程被阻塞了,其他的也能正常执行;
    2. 缺点:一个用户进程会占用多个内核级线程,线程切换由OS内核完成,由于用户态到核心态的转换需要开销,因此线程管理成本高,开销大。

多线程模型

  • 一对一模型

image-20201003170653283

  • 多对一模型

image-20201003170837716

  • 多对多模型

image-20201003171220652

处理机调度与死锁

处理机调度

调度基本概念

  • 当有一堆任务需要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是调度所研究的问题,简单来说就算:按照某种算法选择一个进程将处理机分配给他

image-20201005143651479

处理机调度的层次

高级调度

image-20201005154801232

  • 高级调度/长程调度/作业调度,调度对象为作业;

  • 高级调度主要用于多道批处理系统中,什么是多道批系统呢?虽然前面讲过了 再复习一遍吧:

    image-20201005144635558

  • 高级调度根据某种算法/一定的原则从处于后备队列的作业中挑选一个/多个作业,分配内存等资源,建立PCB,使他们获得竞争处理机的权利

  • 高级调度是外存与内存之间的调度,每个作业只调入一次,调出一次。调入时创建相应PCB,作业调出时又撤销PCB。由于调出的时机一定是作业运行结束的时候,因此高级调度主要是解决调入的问题

中级调度

image-20201005154819601

  • 中级调度/内存调度,引入这个调度的目的是为了提高内存的利用率和系统的吞吐量

  • 引入虚拟存储技术后,将那些暂时不能运行的进程调至外存等待,此时进程的状态称为:就绪驻外存状态(挂起状态),等它们已具备运行条件且内存又稍有空闲时,由中级调度决定,重新调入内存并修改状态为就绪状态,挂在就绪队列上等待

    ps:PCB并不会一起被调到外存,而是常驻内存。OS通过内存中的PCB保持对各进程的监控和管理

低级调度

image-20201005151550183

  • 低级调度/进程调度/短程调度:调度对象是进程(或内核级线程);
  • 主要功能是根据某种算法/方法/策略,决定就绪队列中哪个进程应该获得处理机,将处理机分配给它。
  • 这种调度方式是OS中最基本的一种调度,在多道批、实时和分时三种类型OS中必须配置这级调度;
  • 低级调度的频率很高,一般几十毫秒一次;

三种调度方式的联系、对比

image-20201005152354921)image-20201005152256817

进程调度

进程调度的时机

image-20201005160523382

  • 这个地方有人会说:那么进程处于临界区时,不能进行处理机调度咯? 这个说法是错的 为什么呢?

    • 临界资源:一个时间段内只允许一个进程使用的资源,各进程需要互斥地访问临界资源。
    • 临界区:访问临界资源的那段代码
    • 内核程序临界区:一般是用来访问某种内核数据结构的(比如进程的就绪队列,由各就绪队列PCB租成)

    image-20201005160815845

进程调度的方式

非剥夺调度方式

image-20201005161431904

在采用这种方式时,可能引起进程调度的因素归结为:

  1. 正在执行的进程运行完毕,或因发生某事件而使其无法再继续执行;
  2. 正在执行中的进程因提出I/O请求而暂停执行;
  3. 在进程通信/同步过程中,执行某原语操作;
剥夺调度方式

image-20201005161437212

抢占并非是任意的,必须遵循一定原则。包括:

  1. 优先权原则:指允许优先级高的新进程抢占当前进程的处理机;
  2. 短进程优先原则:指允许新的短进程可以抢占当前长进程的处理机;
  3. 时间片原则:即各进程按时间片轮转运行时,当正在执行的进程一个时间片用完时,便停止该进程的执行而重新进行调度;

进程调度的切换与过程

image-20201005162732619

调度算法

调度算法的评价指标
CPU利用率

image-20201005163718195

系统吞吐量

image-20201005163838042

周转时间

image-20201005164349602

  • 对于每个用户而言,都希望自己作业的周转时间短一点,然而对于OS,则向作业周转时间平均值小;那么引入了概念:带权周转时间,平均带权周转时间;

    image-20201005164734068

等待时间

image-20201005165031694

响应时间

image-20201005165627506

FCFS-先来先服务算法

image-20201007173524434

  • FCFS例题:

    image-20201007173555912

SJF-短作业优先算法

image-20201007174950265

  • SJF例题:

    • 非抢占式:

      在0时刻,只有P1进来了,在他运行的时间7内,P2,P3,P4都进来了,在P1结束后选择运行时间最短的P3执行,后续同理;

      image-20201007174045837

    • 抢占式:

      image-20201007174549414)

HRRN-高相应比优先算法

image-20201007175748653

  • HRRN例题:

image-20201007180105263

时间片轮转调度算法RR

image-20201008150220842

  • RR例题

    • 时间片大小为2情况:

      image-20201008145601465)image-20201008145627089

    image-20201008145644629

    最后的运行流程图:

    image-20201008145757946

    • 时间片大小为5情况:

      image-20201008145938524

补充:

  • 时间片太大的影响:如果时间片太大,使得每个进程都可以在一个时间片内完成,则时间片轮转调度算法会退化为先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大。
  • 时间片太小的影响:如果时间片太小,我们知道,进程调度、切换是有时间代价的(保存、恢复运行环境),因此这样的话会导致进程切换过于频繁,系统会花大量时间来处理进程切换,从而导致实际用于进程执行的时间比例减少。
优先级调度算法

image-20201008152411598

  • 例题

    • 非抢占式的优先级调度算法:

      image-20201008150852742

    • 抢占式的优先级调度算法:

      image-20201008151221693

extra

  • 就绪队列未必是只有一个的,可以按照不同优先级来组织;另外也可以把优先级高的进程排在更靠近对头的位置
  • 根据优先级是否可以动态改变,可将优先级分为静态优先级动态优先级两种;
    • 静态优先级:创建进程时确定,之后一直不变
    • 动态优先级:创建进程时有一个初始值,之后根据情况动态地调整优先级
  • 如何合理设置各进程优先级呢?通常来说
    • 系统进程优先级高于用户进程
    • 前台进程优先级高于后台进程
    • I/0进程优先级高于计算型进程
  • 若采用动态优先级,什么时候该调整?
    • 如果某进程在就绪队列中等待了很久,适当提升优先级
    • 如果某进程占用处理机运行了很久,适当降低优先级
    • 如果发现一个进程频繁进行I/0操作,适当提升优先级
多级反馈队列调度算法

image-20201008153258694

  • 例题:

    image-20201008153117802

死锁

死锁的概念

内存

文件系统