一、操作系统概述

1、指令权限与工作模式

处理器能处理的指令分为：

• 特权指令：需要特殊权限才可以使用的指令，通常涉及系统安全。
• 非特权指令：任何情况下都可以使用的指令。

处理器的控制寄存器中用专门的位标识当前的工作模式：

• 核心态(管态)：已获得特殊权限的状态，能够执行所有指令。
• 用户态(目态)：只能指令非特权指令。

事实上，现代处理器通常具有更多层权限和工作模式。从高到低划分为特权级0(管态)，特权级1，特权级2，特权级3(目态)。

2、内存空间与操作系统的内核

处理器处于核心态时可以将内存的不同区段分别设置为两种类型：

• 内核(系统)空间：其中存储的程序将运行在核心态上，从而可以使用所有指令，且可以访问所有内存空间数据。
• 用户空间：其中存储的程序将运行在用户态上，于是只能使用非特权指令，且只能访问用户空间数据。

操作系统通常在启动时指定内核空间，并将其核心程序放置在内核空间内。操作系统的这一部分叫内核，操作系统的其他部分叫核外部分。

3、操作系统的内核

操作系统的内核通常包含以下程序和数据：

• 与硬件密切相关的操作
• 关键数据结构
• 基本中断处理程序
• 使用频繁的功能模块

操作系统的内核具有两个基本特点：

• 常驻内存
• 运行在核心态

4、固件

操作系统的启动依赖于一组称作固件（Firmware）的特殊软件。

固件存储在只读存储器ROM中，也可以将部分程序或者数据存储在硬盘中。

与PC启动相关的固件有BIOS和UEFI，他们在计算机启动时首先被运行，并运行基本硬件的检查，装入操作系统引导程序，提供基本硬件驱动程序和中断处理程序等。

5、基本输入输出系统(BIOS)

BIOS包含3个部分：

• POST自检程序：计算机启动后识别硬件配置、自检、初始化。
• 基本启动程序：在存储介质中查找有效的主引导程序，如果找到，将它读入内存[0000:7C00]处并开始执行，从而引导操作系统启动。
• 基本硬件驱动程序以及中断处理程序：用来在未加载操作系统时识别和控制基本IO设置(键盘、鼠标、显卡、硬盘等)

硬盘的主引导记录MBR

5.1、基于BIOS的操作系统启动过程

• 硬件自检
• 加载驱动
• 基本启动程序
• 主引导程序(440字节)
• 引导程序(512字节)
• 操作系统装载程序
• 操作系统

操作系统装载程序Loader的作用：

• 进一步检查和配置系统硬件。
• 建立内核空间，装入操作系统内核，并初始化数据。
• 加载用户登录程序和人机交互环境。

6、统一的可扩展固件接口UEFI

Intel公司在1997年新推出的高性能处理器，计划设计一种可扩展的、标准化的固件接口规划EFI(Extensible Firmware Interface)，用来计算机系统的启动以及提供与操作系统的接口。在2006年EFI发展成UEFI(Unified EFI)。

UEFI的特点：

• 驱动程序环境DXE
• 磁盘管理采用GUID分区方法
• UEFI应用程序

6.1、基于UEFI的操作系统启动过程

UEFI体系包含2部分内容：

• 平台初始化框架：包含了支持系统启动的底层程序，包含：安全检查、硬件自检和初始化、DXE、启动管理器。
• UEFI映像(UEFI Image):一组在框架的支持下可执行的程序，包括启动管理器、操作系统装载程序、临时操作系统装载程序、EFI应用程序、设备驱动程序。

UEFI固件的启动过程：

• 安全检查
• Pre-EFI
• 加载DXE
• 启动管理器
• 临时操作系统装载程序
• EFI应用程序
• 操作系统装载程序
• 操作系统

7、GUID硬盘分区方式

UEFI采用GUID硬盘分区方式，优点是：

• 扇区块号为64位，消除2TB限制。
• 磁盘分区数不受4个限制，最多划分128个分区
• 分区扇区数为64位，消除2TB限制
• 自带备份，增加可靠性
• 采用CRC32校验，增加完整性
• 每个分区都有唯一标识GUID

8、操作系统的用户接口–命令接口

命令接口是人机交互的主要途径

8.1、按命令接口在操作系统内的实现方式，分为

• 内部命令：内核完成的命令
• 外部命令：由其他应用程序完成的命令

8.2、按命令接口的使用方式，分为：

• 脱机命令：预先编写好，送交执行后无法立即反馈的命令接口形式。

  比如批处理系统中的JCL

• 联机命令：交互式执行，能够立即得到反馈的命令接口形式。

  比如分时操作系统的交互式命令接口。又可细分为字符命令、菜单命令和图标命令。

9、操作系统的用户接口–程序接口(系统调用)

9.1、系统调用的简介

程序接口是程序员在编写应用程序时使用操作系统功能的接口。目前，程序接口通常通过系统调用System Call方式实现。

系统调用在不同的上下文中，可能表示2种含义：

• 一组由操作系统设计者编写的内核中的子程序，用来封装程序员可能使用到的操作系统功能。
• 程序员在编程中对这些子程序进行调用的行为

系统调用所涉及的子程序属于操作系统内核的一部分，保存在内存空间中，应用程序不能直接访问，于是需要通过特殊方式才能实现系统调用。

9.2、系统调用的实现：

• 放置调用号标识

• 访管指令：发出表示系统调用请求的中断或者陷阱

• 处理器保护程序现场，转向中断处理（内核态）

• 中断处理程序识别中断为系统调用请求，于是转向内核的访管指令处理程序

• 访管指令处理程序在地址入口表中查找所请求的调用号对应的内核子程序的入口地址。

• 从查找到的地址开始执行内核子程序(系统调用)并得到结果。

• 恢复应用程序现场，返回用户态。

9.3、系统调用与用户子程序对比

二、进程管理

1、程序与系统的工作流程

程序应具体2个基本特点：

• 顺序性
• 可再现性

系统的工作流程分为顺序执行和并发执行

• 顺序执行的工作方式具有2个特点：

  • 封闭性：独占全部资源，不受其他程序影响
  • 可再现性：重复运行的结果相同

• 并发执行的工作方式中，多道程序

  • 微观上看，轮流执行
  • 宏观上看，同时执行

• 并发执行的工作方式有3个特点：

  • 随机性：运行时情景随机
  • 不可再现性：重复运行结果可能不同
  • 相互制约：资源争夺和协作关系

2、进程

Dijkstra：一道程序在一个数据集上的一次执行过程，叫一个进程Process

IBM：程序的运行过程成为任务Task

进程和任务都是运行着程序的描述，二者可以互换使用，不加区别。

进程的主要特征：

• 动态性：具有生命周期，状态不断变化
• 并发性：可以并发执行
• 独立性：互相独立，只能访问自身的内存空间
• 结构性：不同的进程可抽象出相同的属性，从而抽象结构相同
• 异步性：运行时情况不可预知

3、进程的动态性

进程的3种状态

• 就绪：能够运行但却未在被处理器处理的状态
• 运行：正在被处理器处理的状态
• 阻塞：由于各种原因(IO操作、资源缺乏等)暂时无法运行的状态。

4、进程信息的描述–PCB

进程控制块PCB：是操作系统用来描述进程信息的数据结构，由3部分组成：

• 基本信息部分：

  • 进程名：通常是程序名
  • 进程标识符PID：操作系统用来识别进程的唯一标识
  • 用户标识：创建进程的用户标识
  • 进程状态：运行、就绪或者阻塞

• 管理信息部分：

  • 程序和数据地址：程序和数据在内存中的位置信息
  • IO操作相关参数：进程进行IO操作时的参数
  • 进程通信信息：用来进程间通信的消息队列指针等。

• 控制信息部分：

  • 现场信息：进程离开运行状态时，保存进程现场以备恢复。
  • 调度参数：与进程调度相关的参考信息，如优先级、运行时间等
  • 同步、互斥信号量：用来保证进程间同步、互斥关系的信息。

5、PCB队列和进程管理

操作系统用PCB来描述进程信息，并利用2种PCB队列来组织这些PCB:

• 就绪队列：就绪进程的PCB组成的队列，按照进程性质或者优先级，系统中可以有多个就绪队列，用来提高进程调度算法选择进程的效率。在多处理器系统中，就绪队列也叫请求队列，每个处理器都有独立的请求队列。
• 等待队列：阻塞进程的PCB组成队列，按照阻塞原因，系统中可以有多个等待对了。方便在阻塞原因解除的时候统一调整进程状态。

6、原语

改变进程状态操作不应该被打断，也就是具有原子性。

原语是特殊的程序段，这样的程序段中的所有指令要么全部执行要么一个都不执行。原语就是具有原子性的程序段。

• 原语可以被看做广义的指令，指令都具有原子性
• 原语中的指令若执行不成功，系统需要回退到原语执行前的状态。
• 定义原语是为了保证系统运行的一致性。

7、进程控制–创建

进程控制通过一组原语来实现，包括进程的创建、撤销、阻塞、唤醒和切换。

1、进程的创建原语Create用来创建一个进程

Create可能在以下情况下被使用：

• 按照作业调度程序的作业步规定
• 按照用户提交的命令
• 用户程序使用了创建进程的系统调用比如Unix的fork

Create被使用时完成以下操作：

• 建立PCB
• 生成进程标识符PID
• 初始化进程和PCB
• 将PCB加入适当的就绪队列

8、进程控制–撤销

1、进程的撤销原语Destroy用来结束一个进程

Destroy可能在以下情况下被使用：

• 进程执行完毕
• 进程出错而结束
• 父进程结束
• 人为终止

Destroy被使用时完成以下操作：

• 进程资源回收
• 删除进程PCB

9、进程控制–阻塞

1、进程的阻塞原语Block用来让一个进程进入阻塞状态

Block在阻塞原因发生时被使用。

Block被使用时完成以下操作：

• 修改进程状态为阻塞状态
• 将进程的现场保存，以备恢复
• 将进程PCB加入合适的等待队列

10、进程控制–唤醒

1、进程的唤醒原语Wakeup用来让一个进程从阻塞状态进入就绪状态

Wakeup在阻塞原因解除时被使用。

Wakeup被使用时完成以下操作：

• 将进程PCB从等待队列中移除
• 修改进程状态为就绪状态
• 将进程PCB加入合适的就绪队列

阻塞原因解除后，进程未必可以直接运行，因此合理的唤醒原语并不会将阻塞状态直接修改为运行状态。

11、进程控制–切换

进程切换使处理器的控制权在进程之间专员，无法通过操作系统内核独立完成，必须借助硬件来实现。

进程：系统调用（系统调用中断），外部因素（IO中断，异常），调度维护（计时器中断），然后进程进入中断、异常处理机制。然后在通过内核功能，控制原语，进程调度等。

12、相关进程间的制约关系–间接制约

间接制约关系：仅由于使用相同的资源而造成的制约。

比如：2个进程p1和p2分别使用同一台打印机，逐行打印各自文本。

1、间接制约与临界资源

• 在操作系统的控制下，进程对系统资源的访问逻辑上需要经历3个步骤：申请、使用、归还。

• 某些系统资源，在进程从申请到归还的周期中只能允许此进程独占，否则将造成运行错误。则称这样的资源为临界资源。

  常见的临界资源有：打印机，存储单元，文件等。

• 间接制约实质上是一组并发进程共享某种临界资源的制约关系。

2、间接制约与护持关系

• 临界区Critical Section/Critical Region：是指进程对应的程序中访问临界资源的一段程序代码，即进程从申请资源开始到归还资源为止的一段程序代码。

• 对于一组(在某资源上)存在间接制约关系的并发进程，可以通过建立一种机制来避免制约关系导致的运行错误：当一个进程在这种临界资源对应的临界区内执行时，其他要求进入相关临界区的进程必须等待。

• 上面的机制得以建立，则称这些并发进程为互斥进程，它们之间建立了护持关系。

3、临界区管理

实现互斥关系的关键是对临界区的执行进行有效控制。

临界区管理的准则有：

• 空闲让进：如果进程请求进入临界区，而没有其他进程在相关临界区内执行，则允许进入。
• 忙则等待：如果有进程在临界区内执行，则其他要求进入相关临界区的进程都需要等待。
• 有限等待：对于要求进入临界区的进程，等待的时间应该是有限的
• 让权等待：当一个进程离开临界区时，应该让请求进入相关临界区的下一个进程进入临界区执行。

4、互斥关系的实现–加锁机制

加锁机制由3个要素组成：锁变量key，加锁操作lock(key)和解锁操作unlock(key)

1
2
3
4
5
6
7
8

lock(key){
    while(key==1);
    key=1;
}

unlock(key){
    key=0;
}

• 这个机制中，锁变量key=1时表示上锁状态，key=0为未上锁。

• 当进程申请资源时需要对资源加锁，若资源已经上锁，则上锁操作 将进行反复测试也就是反复等待，直到资源被解锁了；当进程归还资源的时候需要对资源解锁。

• 高级语言，软件实现的加锁机制并不能实现真正的加锁，因为加锁操作内部仍可能被打断。

加锁机制的缺陷：

• 存在忙等待现象，浪费了处理器时间
• 存在饥饿现象，进程等待时间可能无限长
• 多个锁变量的加锁操作可能导致进程死锁

5、互斥关系的实现–信号量机制

信号量机制由3个要素组成：信号量s，原语p和原语v

也就是所谓的pv操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

struct semaphore{
    int value;//信号量的值
    PCB *bq;/由于该信号量而阻塞的进程队列PCB队列，(阻塞队列/等待队列)
}

p(s){
    s.value=s.value-1;
    if(s.value<0)
        blocked(s);
}

v(s){
    s.value=s.value+1;
    if(s.value<=0)
        wakeup(s);
}

• 信号量机制中，s.value>0表示资源就绪，否则就表示有其他进程在使用或者请求使用资源。

• 进程请求资源时需要使用原语p，如果资源不空闲，则进入由于s而导致的等待队列。直到正在使用资源的进程归还资源时，使用原语v将它唤醒。

信号量机制相比于加锁机制的优势：

• 信号量机制把等待资源的进程设置为阻塞状态，而不是忙等待，提高了处理器的利用率。
• 信号量机制中由操作系统原语wakeup唤醒进程，可以采取一定策略，比如短作业优先，而不是像加锁机制一样，抢先者得到处理器，这样可以避免饥饿现象的发生。

13、相关进程间的制约关系–直接制约

直接制约关系：由于进程协作关系造成的制约。

某任务需要通过循环使用read、move、write，3个操作将源磁盘上的数据文件，复制到目标磁盘。一次操作处理一个文件。

• 如果这3个操作在同一个进程中顺序执行，则当进行IO操作read,write的时候，进程就处在阻塞状态了。
• 如果这3个操作，分别建立进程，并发执行，则会节约运行时间。
• 然后，由于并发执行的时候这3个操作执行顺序的随机性，可能会造成重复拷贝文件或者遗漏文件的错误。

1、直接制约与同步关系

• 对于一组存在直接制约关系的并发进程，为了避免制约关系导致的运行错误，应该让各个进程中代码的运行顺序服从其内在要求，需要建立进程间单向或者相互的依赖关系。

• 如果一组进程中的每一个进程都要与其他至少一个进程建立了单向或者相互的依赖关系，则把这组进程叫同步进程，这组进程之间建立了同步关系。

2、同步关系的实现–信号量机制

• 比如有代码段L1对L2有依赖，可以将L2的一次执行看做一种资源的归还，而L1的执行，需要申请使用这种资源。

• 于是，可以类似用信号量机制来实现同步关系：在L1执行之前先执行原语p，而在L2执行后执行原语v。

• 与互斥关系不同的是，L1使用资源后并不归还。

3、文件拷贝问题–同步关系的实现

• read中的代码段L1
• L1将文件src的内容存到缓冲区buf1
• 然后Move中的代码段L2
• L2读出buf1中的内容
• 然后Move中的代码段L3，再把读出的内容写到buf2
• 最后write中的代码段L4，再从buf2中读的内容写到别的文件

初始化的时候：先S1=1,S2=0,S3=0,S4=0，P他们刚开始只能S1进行使用处理器资源，其他的都加入到阻塞队列了。

首先Read进程是p(S1),因为S1初始化必须为1，P操作，先是做减1操作，然后再做判断S1是否小于0，如果小于0，先加入到阻塞队列。

为了顺序执行，我们先把S1初始化为1，刚开始S1是1，减1操作后，S1变为0了。此时就是Read进程的L1代码段在使用处理器资源。

当L1的代码段执行完后，需要进行Move了，此时也就是L1已经让出处理器资源，则需要先把S2给唤醒，需要V以下S2。唤醒S2之后S2做加1操作，然后再P(S2)就得到了处理器资源，然后等到P(S2)减1操作，执行完后，等同理。

14、进程同步总结

• 控制并发进程的互斥，同步关系，保证他们能够正确执行，称作进程同步，实现集成同步的方法叫做进程同步机制。
• 操作系统需要为程序提供进程同步机制，而当需要处理互斥/同步关系时才决定如何使用这些机制。
• 用于实现互斥关系，针对间接制约的进程同步关系：加锁机制、信号量机制
• 用于实现同步关系，针对直接制约的进程同步关系：信号量机制。
• 除了加锁机制、信号量机制之外，常用的进程同步机制还有：标志位机制，管程机制等。

15、生产者、消费者问题

用两个进程Pro和Con分别表示生产者和消费者，用数组B[]表示最大库存为k的仓库，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

slot=k;//正信号量表示还有多少个空位
item=0;//需要消费的
Pro(){
    生产货物;
    p(slot);
    查找B中任意空位in;
    将货物放入B[in];
    v(item);
}

Con(){
    p(item);
    查找B中任意存有货物的位置out;
    取出获取B[out];
    v(slot);
    消费货物；
}

16、从信号量到进程通信

• 进程的独立性：不同进程无法互相访问代码和数据。
• 进程需要相互写作必须能够通信（也就是共享受）。
• 信号量就是一种常见的共享受–低级通信
• 信号量数据结构的存放位置并不是yoghurt进程的私有空间，而是内核空间，信号量使用前需要向内核申请，用来获得信号量标识。

1、共享存储区通信

• 共享存储区通信：进程根据需要向内核申请位于内核空间的共享存储区，并将此区域映射到发送进程与接收进程的地址空间，使得发送，接收进程可以通过共享存储区进行通信。

• 共享存储区中的数据存取没有固定模式，需要注意根据实际情况处理同步/互斥关系。

2、信箱通信

• 信箱通信：在内核空间中建立专门区域作为信箱，信箱划分有限个信格，每个信格可存放一条信息（信件）。每个信箱可由多个发送进程与接收进程共享 ，发送进程用send操作将信息放入信格中，接收进程用receive操作从信格中取出信息。

• 与共享存储区通信相比，信箱通信的数据存取模式固定，其实现是一个多生产者消费者的PC问题。

3、消息缓冲通信

• 消息缓冲通信：内核空间中为每个进程配备一个消息队列MQ，并记录在进程的PCB中。发送进程通过send操作将信息封到一个消息缓冲区中，并追加到接收进程的消息队列中。接收进程通过receive操作收取自身消息队中的信息。

• 消息缓冲区包含：

  • 发送进程的标识pid
  • 正文大小size
  • 正文data
  • 向下指针next

• 与信箱通信比较，消息缓冲通信中的消息队列属于进程。消息缓冲通信是一种直接通信，当接收进程没有开启的时候，通信不成功。

4、管道通信

• 管道通信：通信双方共享一个文件，发送进程向文件中写入数据，接收进程从中读出数据，从而实现通信。共享的文件叫做管道。
• 管道通信中的共享数据并不是存放在内核空间中，而是存放在管道(文件)中，需要注意维护数据的安全问题。
• 管道通信中的管道文件，和共享存储区类似，并没有固定数据存取模式，所以需要注意根据实际情况处理互斥同步关系。
• 管道通信可以使用远程文件作为管道，所以，这样通信方式不局限于单机系统。

17、线程

把进程细化成若干个可以独立运行的实体，每一个实体叫做一个线程Thread。

线程和进程的比较

引入线程减小了系统的基本工作单位粒度，目的是：

• 实现进程内部的并发执行，提供并行程度
• 减少处理器切换带来的开销
• 简化进程通信方式

1、线程的控制与类型

对线程实施管理，控制的模块称作线程包

根据线程包的实现方式，将线程划分为：

• 用户级线程：由用户态的线程包来管控，而内核中不识别这种线程

  • 优点：切换时不需要进入到内核
  • 缺点：某一个线程在内核上阻塞的时候，会导致全部进程阻塞。

• 系统级线程：使用内核提供的线程包来管控

  • 优点：某线程在内核上阻塞时，同进程的其他线程仍然可以运行。
  • 缺点：切换时不需要进入内核。

2、进程的常用细化方法

将进程细化为线程需要根据实际应用的需要，主要的细化方法有：

• 分派/处理模型（Dispatcher/Worker Model）

  由一个分派线程Dispatcher负责接收工作需求，然后将工作任务分派给工作线程Worker来完成动作。

• 队列模型Team Model

  将进程细化为具有独立关系的线程，各自完成独立的任务

• 管道模型Pipeline Model

  将完整进程中有序的各执行步骤作为线程，依次顺序运行（流水线）

三、调度

调度Scheduling是管理的一种方法，一种决策。目的是通过一种合理的，有效的安排方式，提供资源(比如工作，人力 ，车辆等)的利用率。

操作系统中关注的调度问题有4种：

• 作业调度(宏观)：考虑何时执行哪些作业(比如Hive的数据抽取脚本)
• 进程调度(微观)：考虑将哪个就绪进程转换为运行状态
• 交换调度(中级)：考虑将进程如何在内/外存储器之间交换
• 设备调度：考虑让哪个进程唤醒使用设备。

1、调度的性能指标

评价调度的效果，常使用一组性能指标：

1、周转时间和平均周转时间

从处理过程的完成时间来进行评价(批处理系统)，处理过程Ji的周转时间；Ti=Ji的完成时刻-Ji的提交时刻

一批(n个)处理过程的平均周转时间：T=∑Ti/n

2、带权周转时间

周转时间并不直接体现某处理过程耗时的合理性。

处理过程Ji的带权周转时间：Twi=Ti/Tri

一批(n个)处理过程的平均带权周转时间：Tw=∑Twi/n

3、响应时间

从处理过程的响应速度来进行评价，常用在分时系统，实时系统

处理过程Ji的响应时间：

Ri=Ji第一次对用户做出响应的时刻-Ji的提交时刻

4、其他性能指标

• 公平合理：安排公平，用户满意
• 资源利用率(并行度)：资源闲置的情况
• 吞吐量：单位时间完成处理过程的数量

2、作业调度算法

1、先到先服务FCFS(First Come First Served)

思想：排队

特点：

• 公平合理
• 算法简单，容易实现
• 服务质量欠佳(不利于短作业)

2、短作业优先SJF(Shortest Job First)

思想：减少共同等待时间

特点：

• 实现最小的平均周转时间
• 吞吐量大
• 存在饥饿现象
• 算法简单，但实现困难

3、高响应比优先HRN(Highest Response-ratio Next)

思想：通过考虑作业以等待的时间解决SJF的饥饿问题

响应比R=作业等待时间/作业大小

作业等待时间=系统当前时间-作业提交时刻

3、进程调度方式

进程调度：在采用并发执行方式的系统中，决定正在运行的进程何时将处理器使用权交给就绪队列中的哪个进程。

进程调度方式指操作系统何时实行调度，也就是处理器使用权何时可能切换，可分为：

• 非抢占式：除非进程由于自身原因或者外部(非操作系统的)原因交出处理器使用权，否则一直运行直到结束，非剥夺的
• 抢占式：操作系统定期检查系统状态(定期调度)，按照某种原则主动将进程暂停并将处理器使用权交给下个进程。剥夺式

4、进程调度算法

进程调度算法考虑调度进行时的行为，也就是如何判断是否真正发生处理器使用权切换，以及切换时选择哪个进程。

1、先来先服务FCFS

• 调度时不修改就绪队列，并且总是选择队首。
• FCFS基于非抢占调度方式
  • FCFS进程调度的优缺点类似FCFS的作业调度。（公平，容易实现，服务质量欠佳）

2、时间片轮转RR（Round-Robin）

• RR基于抢占调度方式，它的实现依赖与计时器中断。

• 进程每次被选中时分配一个时间片，调度时判断其时间片是否用尽，如果用尽，则将其移到就绪队列末尾，否则不修改就绪队列。并且总是选择队首。

• 时间片长度为T，如果就绪队列中已经存在了n个进程，则提交新进程的最长响应时间：R=Txn

• 应用RR算法的关键是根据实际需要确定T的值：

  • T太长则响应时间太长
  • T太短则进程切换太频繁，系统开销加大。

3、优先级算法Priority

• 为每个进程赋予一个优先数，调度时总是选择优先数最高的进程。

• 可基于抢占式调度，也可以基于非抢占式调度：

  • 抢占式调度：可以保证总是执行高优先级进程
  • 非抢占式调度：仅能保证当前一个进程阻塞或者结束时总能选择优先级最高的进程。

• 优先级调度的关键是进程优先数的配置。按照优先数配置的特点，优先级算法分为：

  • 静态优先级算法：进程优先数在进程创建时确定，并不可改变。
  • 动态优先级算法：进程优先数在创建进程时被赋初始值，运行中可以根据系统状态改变。

• 通过不同的优先数配置策略，优先级算法可以灵活的体现各种算法思想FCFS，SJF

• 经验：IO繁忙型的进程应该被赋予高优先级用来提供系统的并行度。

5、实时系统的进程调度

实时系统需要对周期性或者非周期性发生的时间作出处理，其对处理正确性和时效性要求十分苛刻。

不同类型的时间对于时效性的要求各异，可表达为以下时间参数：

• 就绪时限：事件发生时到相应处理进程被创建的时间长度要求。
• 开始时限：事件发生时到相应处理进程第一次运行的时间长度要求
• 完成时限：事件发生时到相应处理进程完成的时间长度要求。
• 处理时间：某些特殊事件要求定期触发处理过程。

5、可调度以及条件

• 对于一组事件，如果存在某种处理方式，让其中每个事件的时限要求都可以得到满足，就说明这组事件是可调度的Schedulable。否则，如果无论用何种方式，都至少有一个事件无法满足时限要求，则说明这组事件是不可调度的。

• 可调度的一个必要条件：u>r，u表示系统单位时间内可以处理的事件数（处理能力），r表示单位事件内到达的事件数。

四、死锁

一组进程都处于阻塞状态，其中的任一进程阻塞状态的解除都依赖与另一进程的后续操作 。这种系统状态叫做死锁DeadLock。

1、死锁的分类：

• 资源死锁：由于相互等待临界资源而导致的死锁
• 通信死锁：由于相互等待通信导致的死锁
• 控制死锁：由于系统或者用户的特殊控制导致的死锁

2、死锁的特点

• 偶发性：由于特殊的并发执行顺序导致，是小概率事件
• 非消耗：死锁的相关进程处于阻塞状态，不占用处理器
• 程序无关：并非个别程序设计的错误，而是系统运行的错误。

3、死锁的原因

资源死锁的根本原因是可用资源的数量小于所需资源的数量。

但不可能靠无限制的增加资源数量来根本性的解决死锁问题。

死锁的发生的必要条件：

• 互斥条件：死锁的相关进程都是互斥的
• 不剥夺条件：当进程申请资源时不能剥夺其他进程正在使用的资源
• 请求与保持(部分分配)条件：进程在申请资源不成功的时候仍然保持已经申请的资源。
• 环路等待条件：进程相互等待关系形成环路。

4、死锁的预防

通过在资源分配的时候采取一系列的限制措施，来破坏4个必要条件之一，就可以避免死锁的发生。

• 互斥条件的破坏

  • 方法：不允许申请临界资源
  • 缺点：临界资源需要转化为非临界资源才能被申请和使用，大部分情况下无法实现。

• 不剥夺条件的破坏

  • 方法：允许进程申请资源时剥夺其他进程正在使用的资源
  • 缺点：被剥夺资源的进程不可预期的打断，系统需要处理回退。缺乏公平性，反复剥夺与被剥夺

• 请求与保持条件的破坏

  • 方法1：资源暂时归还

    • 进程申请资源不成功时，暂时归还已经分配的资源。

    • 缺点：系统需要处理回退，反复申请与归还。

  • 方法2：静态分配

    • 进程需要一次性申请完所有可能使用的资源
    • 缺点：难以预知需要使用的资源，降低资源利用率。

• 环路等待条件的破坏

  • 方法1：单请求方式

    • 资源申请不允许嵌套，但可以一次申请多个，归还旧的资源后方可以申请新资源。
    • 缺点：同时需要多个资源时只能实行小范围内的静态分配。

  • 方法2：按序分配

    • 对资源编号，进程只允许申请比当前已拥有资源编号更大的资源。
    • 缺点：如果使用大编号资源的段内需要使用小编号资源，则只能实行小范围内的静态分配。而且，编号管理也困难。

5、死锁的经典问题

哲学家用餐问题

6、死锁的避免

进程可以自由的动态的，申请资源，但是分配资源的时候对可能发生的死锁，进行预测，来决定是否立即分配。

死锁的避免具有以下特点：

• 原理上是通过预测潜在的死锁
• 不影响程序设计
• 临界资源分配并非空闲让进

7、银行家算法

• 初始化，计算资源可用量Avaiable和当前需求矩阵Need，

  • Available=Total-∑Used
  • Need=Max-Used

• 合法检查，检查资源申请与需求矩阵的相容性，未通过则报错，Request<=Need

• 资源检查，检查请求的资源是否可用，未通过则阻塞进程P。Request<=Avaiable

• 预分配，嘉定Request得到满足

  • Available=Available-Request
  • Used=Used+Request
  • Need=Need-Request

• 安全状态检查，检查预分配后的状态是否为安全状态。

某系统有4类资源A,B,C,D，数量分别是8,10,9,12。当前有5个进程P1，P2，P3，P4，P5。最大需求矩阵Max和当前分配矩阵Used如下：
$$
Max = \left[ \matrix{ 4 & 6 & 3 & 8\ 3 & 3 & 5 & 2\ 6 & 6 & 0 & 9\ 3 & 4 & 8 & 5\ 4 & 3 & 2 & 2 } \right]
$$

$$
Used = \left[ \matrix{ 1 & 1 & 0 & 2\ 2 & 2 & 4 & 0\ 0 & 5 & 0 & 1\ 1 & 1 & 1 & 5\ 2 & 0 & 2 & 2 } \right]
$$

• 在当前状态下，如果进程P1申请request=(1,0,1,0)，系统能否分配？

  • 资源总量(8,10,9,12)

    进程			Max			Used					Need			Avaiable			Finished
    	A	B	C	D	A	B	C	D	A	B	C	D	1	1	1	2
    p1	4	6	3	8	1	1	0	2
    p2	3	3	5	2	2	2	4	0
    p3	6	6	0	9	0	5	0	1
    p4	3	4	8	5	1	1	1	5
    p5	4	3	2	2	2	0	2	2

• 在当前状态下，如果进程P3申请request=(1,0,0,1),系统能否分配？

五、存储管理

1、存储器的类型

• 外存储器、磁带，离线存储，容量大，速度慢
• 外存储器，磁盘，光盘等，主板外
• cache主存储器，主板类（存储器管理）
• 寄存器cache，cpu内，速度块，容量小

2、程序的编码与装入

• 程序（高级语言）

  1 2 3 4 5 6

  int a=10; main(){ int b=a; cout<<b<<a; cout<"hello"; }

• 编译链接

• 程序（机器码）

  1 2 3 4 5

  0~1 10 2~8 hello. 9 ???? (将[0~1]压栈) 10~13 ???? (cout<<[esp]<<[0~1];) 14~17 ???? 装入(count<<[2~8];)

• 运行时内存

  • 数据段：全局变量和敞亮
  • 代码段：指令存放处
  • 堆栈：局部变量存放处（由指令动态操作）

3、逻辑地址与物理地址

​ 程序在运行的时候被装入到内存中，其中的指令与数据的位置用地址值表示，地址值的变现形式可分为：

• 逻辑（虚拟）地址：指令或者数据在程序中的编号（位置）
• 物理地址：指令或者数据内存中的位置

4、重定位（地址转换）

​ 若程序中的变量与指令用逻辑地址加以引用，则为了在运行的时候正确访问这些变量或者指令，需要进行重定位（或者叫地址转换），来确定实际的物理地址。

​ 根据地址转换操作的时机，重定位分为：

• 静态重定位：操作系统在装入程序时候修改其中所引用的逻辑地址值为物理地址值–由操作系统实现。

• 动态重定位：在运行过程中需要做访问操作的时候才进行地址转换–由cpu的存储管理单元MMU自动实现，操作系统只登记MMU进行重定位时需要的相关信息。

个人理解，Java的反射机制，可以在运行的时候，获取Class信息，想必底层实现原理就是利用的动态重定位吧。

5、静态重定位与动态重定位的特点对比：

6、存储器管理的关键问题

​ 存储器管理主要是对用户空间进行管理，目的是为了提供主存储器的利用率，方便用户对主存储器的使用。

​ 存储器管理的关键问题：

1、存储空间的分配与回收

• 设计合理的数据结构以记录存储空间的分配情况
• 设计合理的算法来提高存储器的利用率（装入尽可能多的程序）

2、重定位方式的确定

• 决定采用静态重定位或者动态重定位，并进行相应的工作

3、实现保护与共享

• 存储空间保护使得各进程不能访问彼此的存储空间，主要方法有：

  • 利用出其里的特权级，防止跨级访问

  • 利用MMU的界限寄存器规则，防止同级访问

  • 操作系统设置和检查存储区域的保护键与当前进程的键以及操作是否匹配

• 存储空间共享：

  • 提供进程间共享数据的途径

4、实现虚拟存储技术

7、存储器管理的方法

1、从程序的角度分为：

• 非分段管理：将进程的数据、代码、堆栈作为一个完整的逻辑空间
• 分段管理：将进程的数据、代码、堆栈、各自作为独立的逻辑空间

2、从内存分配的角度分为：

• 分区管理：一个逻辑空间对应物理空间中一个分区，连续分配
• 分页管理：一个逻辑空间对应物理空间中多个分页，可不连续分配。
• 段页式管理：比较先进复杂的综合方法。

8、单一连续区存储管理

​ 操作系统占用内核空间之外，将整个用户空间看做一个内存区域，一次只能装入一道用户程序，只有用户区中的程序运行完毕方可以装入下一道程序。

也就是说，一个内存，有系统区，还有用户区。系统区，存储一个操作系统信息。

• 常用静态重定位

• 管理简单

• 不需要复杂硬件支持

• 只允许单任务

  为了实现单一连续区存储管理，或者其他任何存储管理的方法，操作系统采用的请求表来记录请求装入内存的程序信息。

  程序标识	需要的空间长度（虚拟地址空间大小）
  A	50K
  B	90K
  C	130K
  D	10K
  E	165K

9、固定分区存储管理

​ 操作系统占用内核空间之外，将整个用户空间划分为若干个固定大小的区域（大小可不相等）。多道程序分别装入不同的分区内，一道程序只能装入一个分区，而一个分区也只能分配给一道程序。

​ 为了实现固定分区存储管理，操作系统必须记录各分区的位置和使用情况，采用关键数据结构–分区说明表（DPT）

​ 固定分区存储管理一般采用静态重定位，配合界限寄存器法防止各进程彼此访问存储区域（存储保护）。

​ 利用MMU的界限寄存器规则，防止同级间房屋内，操作系统设置和检查存储区域的保护建与当前进程的键是否匹配。

​ 固定分区存储管理的特点：

• 支持多道程序设计
• 并发执行进程数受到分区数限制
• 程序可用空间受分区大小限制
• 存储区存在“碎片”
• 长作业优先、输入队列法

10、可变分区存储管理

​ 在程序装入时选择一个空闲区域并在其中动态创建一个分区来装入程序。

​ 为了实现可变分区存储管理，操作系统需要记录空闲内存区域的位置，可采用以下两种数据结构：

1、可用表

类似分区说明表DPT，但是其中的记录是变化的，并且状态1表示空闲，而状态0表示记录无效（预留着存储位置）

• 缺点：可用表的长度受到了限制，从而导致表示的空闲区个数受到限制，影响并发的进程个数

2、空闲区链表

用链表的形式来记录空闲区

ps：怪不得面试的时候，让手写LRU算法，而LRU算法也是用链表实现的。

1
2
3
4
5

struct FreeNode{
    long start;//分区的起始地址
    long length;//分区的长度
    struct FreeNode *next;//向下指针
}

3、可变分区存储管理空间分配算法

当程序请求装入的时候，进行空间分配的算法：

• 最先适应法FF：依次查找空闲区，选择收个足够大的空闲区装入程序。
• 最佳适应法BF：在所有足够装入程序的空闲区中选择最小者
• 最坏适应法WF就：在所有足够装入程序的空闲区中选择最大者

4、空间分配算法优缺点：

三种算法的优势和缺点：

• 最先适应法FF：分配速度最快，但是堆内存使用没有规划。
• 最佳适应法BF：找到的空闲区与请求最匹配，对大程序的装入有充分的准备，但是容易产生外碎片。
• 最坏适应法WF：不容易产生外碎片，但是容易造成大程序装入的失败。

赏

谢谢你请我吃糖果

支付宝

微信