本来想先学计组的，但是硬件太底层了，不难但是很烦，学不进去，就先学操作系统了qwq

Chap1 概述

概念功能和目标

  1. 目前的主流操作系统

    Windows，Android，ios，macos，linux

  2. 层次结构

    • 用户层

    • 应用程序层

    • 操作系统层

      • 负责管理协调硬件，软件等计算机资源的工作
      • 为上层的应用程序，用户提供简单易用的服务
      • 操作系统是系统软件，而不是硬件

    • 硬件层

  3. 概念

    • 是系统最基本最核心的软件，属于系统软件

    • 控制和管理整个计算机的硬件和软件资源

    • 合理的组织、调度计算机的工作与资源的分配

    • 为用户和其它软件提供方便的接口和环境

  4. 功能和目标

在这里插入图片描述

  1. 作为计算机系统资源的管理者

    • 管理软硬件资源，合理的组织调度计算机的工作与资源分配

      1. 处理器（CPU）管理

        在多道程序环境下，cpu的分配和运行都以进程（或线程）为基本单位，因此对cpu的管理可理解为对进程的管理。进程管理的主要功能包括进程控制、进程同步、进程通信、死锁处理、处理机调度等。

      2. 存储器管理

        为多道程序的运行提供良好的环境，方便用户使用及提高内存的利用率，主要包括内存分配与回收、地址映射、内存保护与共享和内存扩充等功能。

      3. 文件管理

        计算机中所有的信息都是以文件的形式存在的，操作系统中负责文件的管理的部分称为文件系统，文件管理包括文件存储空间的管理、目录管理及文件读写管理和保护等。

      4. 设备管理

        设备管理的主要任务是完成用户的I/O请求，方便用户使用各种设备，并提高设备的利用率，主要包括缓存管理、设备分配、设备处理和虚拟设备等功能。

  2. 作为用户与计算机硬件系统之间的接口

    • 为了让用户方便、快捷、可靠的操作计算机硬件并执行自己的程序，操作系统提供了用户接口
    • 操作系统提供的接口分为两类：命令接口和程序接口
    • 命令接口：用户可以直接使用的，利用这些操作命令来组织和控制作业的执行
    • 程序接口：用户通过程序间接使用的，编程人员可以使用它们来请求操作系统服务

    1. 命令接口

      • 命令接口分为两类：联机命令接口和脱机命令接口，用户可以直接调用

      • 联机命令接口：又称交互式命令接口，适用于分时或实时系统的接口，由一组键盘操作命令组成。用户输入一条指令，操作系统就执行一条指令；

      • 脱机命令接口：又称批处理接口，使用于批处理系统，由一组作业控制命令组成。用户输入一堆指令，操作系统运行一堆指令。在操作系统运行这些命令时用户不可干预。

        批处理(Batch)，也称为批处理脚本。顾名思义，批处理就是对某对象进行批量的处理，通常被认为是一种简化的脚本语言，它应用于DOS和Windows系统中。批处理文件的扩展名为bat 。

    2. 程序接口

      • 程序接口：由一组系统调用（也称广义指令）组成
      • 用户通过在程序中使用这些系统调用来请求操作系统为其提供服务，只能通过用户程序间接调用
      • 如使用各种外部设备、申请分配和回收内存及其它各种要求

      例如C:\Windows\System32\user.dll就是程序接口，只能通过用户程序间接调用

      • 比如常见的图形用户界面程序接口GUI

        系统调用=系统调用命令=广义指令

    3. 作为扩充机器(虚拟机)

      • 没有任何软件支持的计算机称为裸机
      • 覆盖了软件的机器称为扩充机器或虚拟机

特征

在这里插入图片描述

并发

  • 并发:两个或多个时间在同一时间间隔内发生，这些事件在宏观上被认为是同时发生，在微观上被认为是交替发生的

    • 一个单核(CPU)同一时刻只能执行一个程序，因此操作系统会协调多个程序使他们交替进行（这些程序在宏观上是同时发生的，在微观上是交替进行的）

  • 并行:两个或多路时间在同一个时刻发送

    • 多核cpu 每一个核都都能运行一个程序，同一时刻可以同时运行多个程序，这就是并行

  • 操作系统是伴随着“多道程序技术出现的”，因此操作系统和并发是一同诞生的

共享

  • 资源共享即共享，是指系统中的资源可以供内存中多个并发执行的进程共同使用
  • 共享分为两类:互斥共享和同时共享

  1. 互斥共享

    • 计算机中的某个资源在一段时间内只能允许一个进程访问，别的进程没有访问权
    • 临界资源(独占资源):在一段时间内只允许一个进程访问的资源，计算机中大多数物理设备及某些软件中的栈、变量和表格都属于临界资源，它们被要求互斥共享
    • 例如:QQ和微信视频。同一段时间内摄像头只能分配给其中一个进程

  2. 同时共享

    • 计算机中的某个资源在在一段时间内可以同时允许多个进程访问
    • 同时共享通常要求一个请求分为几个时间片段间隔的完成，即交替进行，“分时共享”
      这里的同时指在宏观上是同时的，在微观上是交替进行访问(并发)的，只是cpu处理速度很快，我们感觉不到，在宏观上感觉是在同时进行,有时也是并行的
    • 举个例子：比如QQ在发送文件A，微信在发送文件B，宏观上两个进程A和B都在访问磁盘，在我们看来是同时进行的，但是在微观上两个进程A和B是交替进行访问磁盘的，只是时间太短，cpu处理速度太快，我们感觉不到。
    • 注意：有时候多个进程可能真的是在同时进行资源访问，比如玩游戏时可以放音乐，游戏声音和音乐声音都能听见(并行)

  3. 并发性和共享性互为存在条件

    因为并发性是指计算机系统中同时存在着多个运行着的程序

    共享性是指系统中的资源可供内存中多个并发执行的进程共同使用

    如果失去并发性，则系统中只有一个程序正在运行，共享性就失去了存在的意义

    如果失去共享性，则两个进程不能同时访问硬盘资源，就无法实现并发的操作

虚拟

多道程序设计：是指在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插的运行。 两个或两个以上程序在计算机系统中同处于开始到结束之间的状态。这就称为多道程序设计。多道程序技术运行的特征：多道、宏观上并行、微观上串行。

  • 虚拟是把一个物理上的实体变为若干逻辑上的对应物
  • 物理实体(前者)是实际存在的；而后者是虚的，是用户感觉上的事务
  • 虚拟处理器(CPU):通过多道程序设计技术，采用让多道程序并发执行的方法，分时来使用一个CPU，实际物理上只有一个CPU，但是用户感觉到有多个CPU
  • 虚拟技术:用于实现虚拟的技术
    • 空分复用技术(如虚拟存储器机器,RAM的复用)
    • 时分复用技术(虚拟处理器的并发使用一个CPU的技术)

异步

  • 异步:多道程序环境允许多个程序并发执行，但由于资源有限，例如cpu只有1个，进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进

  • 比如A进程正在占用CPU计算，B进程这时也想占用CPU计算，B进程只有等，等A进程算完了，A进程去访问磁盘资源了，这时B进程再占用CPU进行计算，B进程还没计算完，A进程从磁盘取出资源了，A进程发现B这时在占用CPU，这时A进程就需要等待，等B算完后再继续到CPU中进行计算。由于每个进程占用资源的时间不固定，所以进程的执行以不可预知的速度前进

发展和分类

分类

在这里插入图片描述

发展

在这里插入图片描述

运行机制和体系结构

运行机制和体系结构

image-20240715223253646

层次结构

在这里插入图片描述

操作系统体系结构类比

在这里插入图片描述

用户态和核心态的转换

在这里插入图片描述

中断和异常

在这里插入图片描述

系统调用

系统调用知识框架
在这里插入图片描述
系统调用和库函数的区别
在这里插入图片描述
系统调用执行过程
在这里插入图片描述

Chap2 进程管理

进程定义

  1. 程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。

  2. 进程（Process）的概念：是动态的，是程序的一次执行过程。同一程序多次执行会对应多个进程。

  3. 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。(线程才是调度的最小单位)

  4. 进程是动态的，进程实体是静态的；进程实体反应了进程某一时刻的状态就像视频中的一帧。

  5. 进程，’‘用进程实体（进程映像）更准确’‘：由PCB，程序段（代码：指令序列），数据段（运行过程中产生当各种数据）。其中PCB是给操作系统用的，程序段和数据段是给进程自己用的。

    • 操作系统对进程进行管理工作所需的信息都存在PCB中。
    • PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。
    • 进程控制块（PCB）：包括进程描述信息（PID，UID），进程控制和管理信息（CPU、磁盘、网络流量；进程当前状态：就绪态阻塞态/运行态），资源分配清单（正在使用哪些文件，I/O，内存），处理机相关信息（PSW各种寄存器用于实现进程切换）
    • PID：当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”。
    • ID（UID）：基本的进程描述信息，可以让操作系统区分各个进程。

进程有独立性，能并发执行;程序不能并发执行。

进程异步运行，会相互制约;程序不具备此特征。

进程与程序又有密切的联系： 进程不能脱离具体程序而虚设， 程序规定了相应进程所要完成的动作。

)组成不同。进程包含PCB、程序段、数据段。程序包含数据和指令代码。

程序是一个包含了所有指令和数据的静态实体。本身除占用磁盘的存储空间外，并不占用系统如CPU、内存等运行资源。

进程由程序段、数据段和PCB构成,会占用系统如CPU、内存等运行资源。

进程特征

  • 动态性-进程是程序的一次执行过程，是动态地产生，变化和消亡的
  • 并发性-内存中有多个进程实体，各进程可并发执行
  • 独立性-进程是能独立运行，独立获得资源，独立接受调度的基本单位
  • 异步性-各进程是按各自独立的，不可预知的速度向前推进，操作系统要提供"进程同步机制"来解决异步问题
  • 结构性-每一个进程都会配置一个PCB。结构上看，进程由程序段，数据段，PCB组成

动态性是进程最基本的特征

进程是资源分配，接受调度的基本单位

进程组成

进程由程序段，数据段，PCB三部分组成

在这里插入图片描述
  • 而其中最重要的就是进程控制块PCB（Process Control Block）

PCB简介：
PCB中记录了操作系统所需的，用于描述进程的当前情况以及控制进程运行的全部信息。
PCB的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。
或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。
例如，当OS要调度某进程执行时，要从该进程的PCB中查处其现行状态及优先级；在调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存始址，找到其程序和数据；
进程在执行过程中，当需要和与之合作的进程实现同步，通信或者访问文件时，也都需要访问PCB；
当进程由于某种原因而暂停执行时，又须将器断点的处理机环境保存在PCB中。
可见，在进程的整个生命期中，系统总是通过PCB对进程进行控制的，即系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的。
所以说，PCB是进程存在的唯一标志。

PCB结构图

进程组织

在这里插入图片描述

(1)链接方式

在这里插入图片描述

(2)索引方式

在这里插入图片描述

进程状态

在这里插入图片描述

（1）三种基本状态（就绪、运行、阻塞）

在这里插入图片描述

(2）创建态和结束态

  • 创建态(NEW)------进程正在被创建，操作系统为进程分配资源，初始化PCB
  • 终止态(Terminated)---------进程正在从系统中撤销，操作系统会回收进程拥有的资源，撤销PCB
创建态
在这里插入图片描述
结束态
在这里插入图片描述

进程状态之间的转换

丁字裤模型

原语对进程的控制

在这里插入图片描述

什么是进程控制

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

简而言之就是实现进程状态转换

image-20240716141157757

原语实现对进程的控制

进程控制由原语实现。所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。原语采用 “关中断指令” 和 “开中断指令” 来实现。 注意： 原语运行在核心态。

原语是如何实现进程状态的转换

  1. 更新PCB中的信息**（如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境**)
    1. 所有的进程控制原语一定都会修改进程状态标志
    2. 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
    3. 某进程开始运行前必然要恢复期运行环境
  2. 将PCB插入合适的队列
  3. 分配/回收资源
在这里插入图片描述

一旦执行关指令，每一条代码执行的过程中不会外部中断信号

进程控制的图解

在这里插入图片描述

调度是指决定资源分配给哪个进程的行为，是一种决策行为
切换是指实际分配的行为，是执行行为
一般来说现有资源调度，后有进程切换

进程控制原语的相同点

进程控制原语会导致进程状态的转换，无论哪个原语，都要做下面的三件事情

  • 更新PCB中的信息(如修改进程状态标志，将运行环境保存到PCB，从PCB恢复运行环境)
    1. 所有进程控制原语一定都会修改进程状态标志
    2. 剥夺当前运行进程的CPU使用权必然要保存其运行环境
    3. 某进程开始运行前必然要恢复运行环境
  • 将PCB插入合适的队列
  • 分配/回收资源

进程控制的5种原语

进程的创建原语
在这里插入图片描述

无->创建态->就绪态

  • 申请空白PCB
  • 为新进程分配所需资源
  • 初始化PCB
  • 将PCB插入就绪队列
进程的终止原语
在这里插入图片描述

就绪态/阻塞态/运行态->终止态

  • 从PCB集合中找到终止进程的PCB
  • 若进程正在运行，立刻剥夺CPU,将CPU分配给其他进程
  • 终止其所有子进程
  • 将该进程拥有的所有资源归还给父进程或操作系统
  • 删除PCB
进程的唤醒和阻塞原语
  • 进程的阻塞和唤醒原语是成对存在的，必须成对使用
  • 阻塞原语是由被阻塞进程自我调用实现的
  • 唤醒原语是由一个被唤醒进程合作或被其他相关的进程调用实现的

  1. 阻塞原语

    运行态->阻塞态

    • 找到要阻塞的进程对应的PCB
    • 保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止进程运行
    • 将PCB插入相应时间的等待队列

  2. 唤醒原语

    阻塞态->就绪态

    • 在事件等待队列中找到PCB
    • 将PCB从等待队列移除，设置进程为就绪态
    • 将PCB插入就绪队列，等待被调度
进程的切换原语
在这里插入图片描述

运行态->阻塞态/就绪态

就绪态->运行态

切换原语的步骤

  • 将运行环境信息存入PCB
  • PCB移入响应队列
  • 选择另一个进程执行，并更新其PCB
  • 根据PCB恢复新进程所需的运行环境

引起进程切换的事件

  • 当前进程时间片到
  • 有更高优先级的进程到达
  • 当前进程主动阻塞
  • 当前进程终止

进程通信

在这里插入图片描述

概念

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

`进程是分配系统资源的单位(包括内存地址空间),因此各进程拥有的内存地址空间相互独立

为了保证安全，一个进程不能直接访问另一个进程的地址空间

但是进程之间的信息交换又必须实现

进程通信的三种方式

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

共享存储

共享一块大家都可以访问的空间，一次只能有一个进程进行读或写操作

在这里插入图片描述

管道通信

在这里插入图片描述

消息传递

在这里插入图片描述

线程与多线程

在这里插入图片描述

引入线程的目的

  • 有的进程可能需要同时做很多事情，而传统的进程只能串行地执行一系列程序，因此引入了"线程"来增加并发度
  • 传统的进程是程序执行流的最小单位，而引入了线程，线程成为了程序执行流的最小单位
在这里插入图片描述

什么是线程

在这里插入图片描述

  • 线程是一个基本的CPU执行单元

    也是程序执行流的最小单位

  • 引入线程，不仅进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提高了系统的并发度

  • 一个进程的不同线程有共享内存空间，方便线程之间的通信

线程的属性

  • 线程是CPU调度的单位
  • 多CPU计算机中，各个线程可占用不同的CPU
  • 每个线程都有一个TID(线程ID),TCB(线程控制块)
  • 线程也有就绪,阻塞,运行三种基本状态
  • 线程几乎不拥有系统资源
  • 同一进程的不同线程间共享进程的资源
  • 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
  • 同一进程中的线程切换，会引起进程切换
  • 切换同进程内的线程，系统开销很小
  • 切换进程，系统开销较大

线程的实现方式

线程的实现分为两类用户级线程(User-Level Thread,UTL)和内核级线程(Kernel-Level Thread, KTL)l。内核级线程又称内核支持的线程。

用户级线程

相当于利用逻辑进行模拟线程

在内核看来还是只有一个进程

在这里插入图片描述
内核级线程
在这里插入图片描述
特殊的组合方式
在这里插入图片描述

多线程模型

  • 前面我们提到了线程的实现方式，有用户级和内核级。那么这两种模式的交叉组合就会产生几种不一样的组织结构，即不一样的模型。
多对一模型
在这里插入图片描述
  • 多个用户及线程映射到一个内核级线程，每个用户进程只对应一个内核级线程
  • 优点:用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
  • 缺点:当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
一对一模型
在这里插入图片描述
  • 一个用户及线程映射到一个内核级线程，每个用户进程有与用户级线程同数量的内核级线程
  • 优点:当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行
  • 缺点:一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高开销大
多对多模型

此种模型效率是三种模型中最好的

在这里插入图片描述

  • n用户及线程映射到m个内核(n>=m)线程。每个用户进程对应m个内核级线程

  • 克服了多对一模型并发度不高的缺点，又客服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

线程的状态与转换

image-20240716161024380

线程的组织与控制

TCB的结构

image-20240716161121716

类比PCB

处理机调度

在这里插入图片描述

概念

当有一堆任务要处理，由于资源有限，有些事情无法同时处理，这就需要某种规则来决定处理这些任务的顺序

层次

高级调度
在这里插入图片描述
中级调度(内存调度)
在这里插入图片描述
进程的挂起状态与七状态模型
在这里插入图片描述
低级调度(进程调度)
在这里插入图片描述
三层调度的联系和对比
在这里插入图片描述

进程调度时机

在这里插入图片描述

时机

什么时候进行进程调度
在这里插入图片描述
什么时候不能进行进程调度
在这里插入图片描述
OS内核程序临界区与普通临界区的进程调度情况
在这里插入图片描述

调度算法评价指标

在这里插入图片描述
CPU利用率

CPU利用率指CPU忙碌的时间占总时间的比例

在这里插入图片描述
系统吞吐量
在这里插入图片描述
周转时间
在这里插入图片描述 在这里插入图片描述
等待时间
在这里插入图片描述
响应时间

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

作业/进程调度算法1

FCFS(FirstComeFistServe)先来先服务

在这里插入图片描述 在这里插入图片描述

SJF(ShortestJobFirst)短作业优先

在这里插入图片描述

  • 非抢占式-SJF

    在这里插入图片描述

  • 抢占式-SJF(SRTN)

    在这里插入图片描述

  • 细节

    在这里插入图片描述

HRRN-高响应比优先

在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

总结

在这里插入图片描述

作业/进程调度算法2

在这里插入图片描述

时间片轮转—RR

  • Round-Robin
在这里插入图片描述
  • 可能出现的问题，比如与FCFS对比
在这里插入图片描述

优先级调度算法

在这里插入图片描述

  • 非抢占式

    在这里插入图片描述

  • 抢占式

    在这里插入图片描述

  • 补充

    在这里插入图片描述

多级反馈队列调度算法

在这里插入图片描述

总结

在这里插入图片描述

进程同步/互斥

在这里插入图片描述

1.进程同步

  • 同步也称为直接制约关系。
  • 在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系,如等待、传递信息等，引入了进程同步的概念。进程同步是为了解决进程的异步问题。
  • 一个简单的例子来理解这个概念。
    例如，让系统计算1 + 2x3，假设系统产生两个进程: 一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后,但实际上操作系统具有异步性,若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生。
  • 异步性：进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

2.进程互斥

  • 互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
  • 在这里需复习一下临界资源的概念。
    我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
    对临界资源的访问，必须互斥地进行。
在这里插入图片描述

  • 为了禁止两个进程同时进入临界区，需遵循以下准则

    在这里插入图片描述

进程互斥的软件实现

在这里插入图片描述

单标志法

在这里插入图片描述 在这里插入图片描述

双标志先检查法

在这里插入图片描述

双标志后检查法

在这里插入图片描述

Peterson算法

在这里插入图片描述 在这里插入图片描述

进程互斥的硬件实现

在这里插入图片描述

中断隐藏方法

在这里插入图片描述

TestAndSet指令

  • 执行TSL指令时，它的内部运转逻辑：
  • 假设lock现在为false，代表临界资源A空闲，那么我就可以访问这个资源，同时将lock=true，提醒别的进程，这个临界资源A我正在使用，让他们等等
  • 假设lock为true，代表临界资源正在有人使用，所以我必须等待，并且将lock=true，并不影响什么，所以没关系，只是为了让lock为false时可以上锁，将上锁与检查在一个TSL指令完成。
在这里插入图片描述

swap指令

  • old是每个进程都要进行的一步，都必须将old=true
  • 分析一下这样做的原因：
    因为lock是某一特定临界资源的共享变量，当每一个进程准备访问这个特定的临界资源时，初始化old=true，然后进入while循环进行交换，如果当前lock是false,则交换后old=false,则当前进程可以跳出循环进入临界区代码段，同时因为交换，lock=old=true上锁，不让别的进程来打扰，别的进程会因为lock变为true,一直在while循环等待,当我使用完临界资源，则将lock=false,此时别的进程再交换old和lock就能判断old=false,可以跳出循环，使用临界资源。

信号量机制

在这里插入图片描述

为什么要引入信号量机制

  • 为了更好的解决进程互斥与同步的问题
在这里插入图片描述

什么是信号量机制

在这里插入图片描述

整型信号量

在这里插入图片描述

记录型信号量

在这里插入图片描述 在这里插入图片描述

管程

为什么引入管程

信号量机制存在的问题 : 编写程序困难、易出错。 因此人们想设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松。1973年，Brinch Hansen首次在程序设计语言(Pascal)中引入了“管程”成分――一种高级同步机制。

管程的定义和基本组成

管程相当于对临界区资源进行抽象而编写的一个类。

管程是一种特殊的软件模块，有这些部分组成:

  1. 局部于管程的共享数据结构说明; （一个类）
  2. 对该数据结构进行操作的一组过程; （类中的方法）
  3. 对局部于管程的共享数据设置初始值的语句; （类中的变量）
  4. 管程有一个名字。 （类名）

管程的基本特征

  1. 局部于管程的数据只能被局部于管程的过程所访问; （类中变量有自己的作用范围）
  2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据; ** 这种互斥特性是由编译器来实现的。
  3. 每次仅允许一个进程在管程内执行某个内部过程。

死锁

定义

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁“。

死锁，饥饿，死循环的区别

  • 死锁:各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
  • 饥饿:由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
  • 死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug 导致的，有时是程序员故意设计的。

死锁产生的必要条件

产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。

  • 互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源）。
  • 不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
  • 请求 和 保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
  • 循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
    注意 : 发生死锁时一定有循环等待 , 但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件)

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

什么时候发生死锁

  • 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的
  • 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程p1又紧接着申请资源R2，而进程p2又申请资源R1,两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
  • 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)

处理措施

  1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
  2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法)
  3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

避免死锁

安全序列

  • 所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
  • 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。
  • 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，则可能会发生死锁。（不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)
  • 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

银行家算法

数据结构

长度为m的一维数组 Available表示还有多少可用资源

nm矩阵Max表示各进程对资源的最大需求数

nm矩阵Allocation表示已经给各进程分配了多少资源

Max - Allocation = Need矩阵表示各进程最多还需要多少资源

用长度为m的一位数组Request表示进程此次申请的各种资源数

算法步骤

①检查此次申请是否超过了之前声明的最大需求数

②检查此时系统剩余的可用资源是否还能满足这次请求

③试探着分配，更改各数据结构

④用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤

检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。

不断重复上述过程，看最终是否能让所有进程都加入安全序列。

Chap3 内存管理

基础

内存是用于存放数据的硬件。程序执行之前需要先放进内存才可以被cpu执行

  • 相对地址和绝对地址

    编译时产生指令只关心相对地址，实际放入内存再想办法根据起始地址得到绝对地址

  • 编址方法

    (bit)(byte)(word)的区别

    1. 按位编址:1b
    2. 按字节编址:1Byte=8bit
    3. 按字编址:机器字长1word=32/64bit

  • 计算机字长（word）为32位，存储容量为16MB，按字节编址和字编制的时候，它的寻址范围分别为多少？

    寻址范围：存储容量/编址大小（单位都是B）

    1.按照字节编址： 16MB=2^24B=2^24*8bit=2^27bit

    寻址范围: (2^27b)/8b=2^24b

    2.按字寻址: (2^27bit)/32bit=2^22bit

内存管理

  1. 内存空间的分配和回收
  2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充。
  3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换

装入方式

  • 绝对装入(单道程序阶段)

    编译时产生绝对地址

  • 可重定位装入(用于早起的多道批处理操作系统)

    装入时将逻辑地址转换为物理地址

  • 动态运行时装入(现代操作系统)

    运行时，将逻辑地址转换为物理地址，需设置重定位寄存器

操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

内存保护

方法1

在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。

方法2

采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

覆盖和交换

覆盖技术

覆盖技术的思想 : 将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束)不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。

img

必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点:对用户不透明，增加了用户编程负担。覆盖技术只用于早期的操作系统中，现在已成为历史。

交换技术

交换（对换）技术的设计思想: **内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）。**之前讲的中级调度（内存调度）就是为这个服务的。

img

1.应该在外存（磁盘）的什么位置保存被换出的进程?

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。总之，对换区的I/O速度比文件区的更快。

2.什么时候应该交换?

交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。

3.应该换出哪些进程?

可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…(注意:PCB会常驻内存，不会被换出外存)

(注意:PCB会常驻内存，不会被换出外存)

分配与回收

连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间。

img
1.单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据;用户区用于存放用户进程相关数据。
内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点: 实现简单 ;无外部碎片;可以采用覆盖技术扩充内存;不一定需要采取内存保护（eg:早期的 PC操作系统MS-DOS)。
缺点:只能用于单用户、单任务的操作系统中;有内部碎片;存储器利用率极低。

img
2.固定分区分配
img img
3.动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

使用这种方式的话，我们需要考虑以下三个问题。

  1. 系统要用什么样的数据结构记录内存的使用情况?
img

  1. 当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配?

    使用动态分区算法(下节)

  2. 如何进行分区的分配与回收操作?

    1. 如何分配？

      使用动态分区算法之后，修改数据结构即可。

      img

    2. 如何回收

      将相邻的空闲区域合并为1个

      img
内部碎片和外部碎片
  • 动态分区分配没有内部碎片，但是有外部碎片。
  • 内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。
  • 外部碎片，是指内存中的某些空闲分区由于太小而难以利用。
  • 如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些进程“碎片”不能满足进程的需求。可以通过紧凑（(拼凑，Compaction)技术来解决外部碎片。

动态分区分配算法

动态分区分配算法:在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?

首次适应算法

算法思想: 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表），找到大小能满足要求的第一个空闲分区。

img
最佳适应算法

算法思想:由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

img
最大适应算法

又称最坏适应算法(Largest Fit)

算法思想:为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表），找到大小能满足要求的第一个空闲分区。

临近适应算法

算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现:空闲分区以地址递增的顺序排列(可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

img
比较
img

基本分页存储管理

连续分配:为用户进程分配的必须是一个连续的内存空间。

非连续分配:为用户进程分配的可以是一些分散的内存空间。

基本分页存储管理的思想――把内存分为一个个相等的小分区,再按照分区大小把进程拆分成一个个小部分。

将内存空间分为一个个大小相等的分区（比如:每个分区4KB），每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)页框号从0开始。

将用户进程的地址空间也分为与页框大小相等的一个个区域，称为**“页”或“页面”**。每个页面也有一个编号，即“页号”，页号也是从0开始。

(注:进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片)

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

思考： 将进程地址空间分页之后，操作系统该如何实现逻辑地址到物理地址的转换?

要算出逻辑地址对应的页号
要知道该页号对应页面在内存中的起始地址
要算出逻辑地址在页面内的“偏移量”
物理地址 = 页面始址＋页内偏移量
如何计算:

页号=逻辑地址/页面长度(取除法的整数部分)
页内偏移量 = 逻辑地址%页面长度（取除法的余数部分)
页面在内存中的起始位置:操作系统需要用某种数据结构记录进程各个页面的起始位置。
举例:

页号=80 / 50= 1

页内偏移量=80 % 50 = 30

1号页在内存中存放的起始地址为450

img

思考: 如何知道该页号对应页面在内存中的起始地址?

img

如何理解每个页表项的长度是相同的，页号是“隐含的”？

img

基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会在系统中设置一个页表寄存器(PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块(PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

  1. 执行流程
img

页表项长度，页表长度，页面大小
页表长度是指这个页表中总共有几个页表项，即总共有多少页。页面大小是指一个页面占多大的存储空间。页表项长度是指每个页表项占多大的存储空间。

通过下面这个例子来理解页表项长度。

Eg:假设某系统物理内存大小为4GB，页面大小为4KB，内存总共会被分为2^32/ 212=220个内存块，因此内存块号的范围应该是0~2^20 - 1。因此至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才够(每个字节8个二进制位，3个字节共24个二进制位)。每个块号用三个字节来表示。

img

具有快表的地址变换机构

1.局部性原理
时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

空间局部性:一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

上小节介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢?

2.快表
快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

执行流程

img

两级页表

两级页表的出现主要是为了解决单级页表的问题。那么单级页表有什么问题呢？

问题一:页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。

问题二:没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

1.解决问题一

我们可以回想以下当初是如何解决进程必须连续的问题 ？

我们可以把页表放在不同的页框中，再用一个表来记录各个各个子页表所在位置，我们把这个表叫做页目录表（外层页表，顶级页表）。

img

2.解决问题二

img

  1. 其他细节

  2. 若采用多级页表机制，则各级页表的大小不能超过一个页面

注意页表项是放在页面里面的一个结构，所以我们可以通过页面大小/页面项大小算出可以放多少个页表项

img
  1. 两级页表的访存次数分析（假设没有快表机构）
  • 第一次访存:访问内存中的页目录表
  • 第二次访存:访问内存中的二级页表
  • 第三次访存:访问目标内存单元

N级页表访问一个逻辑地址需要N+1次访问内存。

基本分段存储管理方式