第三章操作系统知识

Posted on 2024-10-24 In 嵌入式 Views:

操作系统的作用

通过资源管理（软硬件资源管理），提高计算机系统的效率改善人机界面，向用户提供友好的工作环境。

进程管理

进程的概念

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成。
进程与程序的区别
- 进程是程序的一次执行过程，没有程序就没有进程
- 程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，它就永远存在
- 程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是

进程状态：三态模型

运行态：占有处理器正在运行
就绪态：指具备运行条件，等待系统分配处理器以便运行
等待态：又称为阻塞态或睡眠态，指不具备运行条件，正在等待某个事件的完成
运行态–等待态：等待使用资源，如等待外设传输，等待人工干预
等待态–就绪态：资源得到满足，如外设传输结束，人工干预完成
运行态–就绪态：运行时间片到，出现有更高优先权进程
就绪态–运行态：CPU空闲时选择一个就绪进程

进程状态：五态模型

挂起：将进程调出内存，保存到外存队列中，并释放资源
激活：恢复挂起进程，重新调入内存
目的：释放进程占用的资源以缓解资源不足
原因：终端用户的请求，父进程的请求、OS的需要（如负荷调节、对换等）

前驱图

出度：多少箭头出
入度：多少箭头入

进程的同步和互斥

互斥：间接制约
同步：直接制约

PV操作

临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等
临界区：每个进程中访问临界资源的那段代码称为临界区
信号量：是一种特殊的变量
P操作：申请资源，阻塞进程
V操作：释放资源，唤醒进程

死锁

进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一个不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。
死锁的预防：打破四大条件
- 互斥
- 保持和等待
- 不剥夺
- 环路等待
死锁的避免
- 有序资源分配法
- 银行家算法
银行家算法：分配资源的原则
- 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
- 进程可以分期请求资源，但请求的总数不能超过最大需求量
- 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源

任务的调度的概述

任务的调度要解决的问题：
- WHEN：何时分配CPU
  - 任务调度的时机，5种情形
- HOW：如何分配CPU
  - 任务调度方式，不可抢占，可抢占
- WHAT：按什么原则分配CPU
  - 任务调度算法，先来先服务、短作业优先、时间片轮转调度、优先级算法
  - 调度算法的性能指标

调度器

定义：调度用来确定多任务环境下任务执行的顺序和在获得CPU资源后能够执行的时间长度。
操作系统通过一个调度程序来实现调度功能
- 调度程序以函数的形式存在，用来实现操作系统的调度算法
- 调度程序本身并不是一个任务，是一个函数调用，可在内核的各个部分进行调用
调度程序：可以看作CPU的资源管理者
- 从就绪队列中选择一个任务去执行
- 调度算法：调度程序在决策过程中所采用的算法，是在一个特定时刻用来确定将要运行的任务的一组规则

任务调度的时机

一般来说有5种情形可能会发生任务的调度。
- 当一个新的任务被创建时，需要做出一个调度决策，是立即执行这个新任务还是继续执行父任务
- 当一个任务运行结束时，它不再占用CPU，这时调度器必须做出一个决策，从就绪队列中选择某个任务去运行
- 当一个任务由于I/O操作、信号量或其他原因被阻塞时，也必须另选一个任务运行
- 当一个I/O操作已经完成，而等待该I/O操作的任务将从阻塞状态变为就绪状态
- 当一个时钟中断发生时，会唤醒一些延时任务或者可能会发现当前任务的时间片已用完，从而把它变为就绪状态

任务调度的方式

不可抢占调度方式（Non-Preemptive）：
- 如果一个任务被调度程序选中，就会一直运行下去
- 直到它因为某种原因（如I/O操作或任务间的同步）被阻塞了，或者它主动地交出了CPU的使用权。
- 调度时机中的前3种情况（任务创建、任务运行结束、任务被阻塞），都可能会发生调度。第4、5种情况（即发生中断），不会发生调度
可抢占调度方式（Preemptive）：
- 当一个任务正在运行的时候，调度程序可以去打断它，并安排其他的任务去运行
- 调度时机中所有的5种情况，都可能会发生调度
实时操作系统大都采用可抢占调度方式
- 使关键任务能够打断非关键任务的执行，确保关键任务的截止时间能够得到满足

任务调度算法的性能指标

CPU的使用率（CPU utilization）
响应时间（responsive time）：调度器为一个就绪任务进行上下文切换时所需的时间，以及任务在就绪队列中的等待时间
周转时间：一个任务从提交到完成所经历的时间
调度开销：调度器在做出调度决策时所需要的时间和空间开销
公平性：大致相当的两个任务所得到的CPU时间应该大致相同。要防止饥饿，即一个任务始终得不到处理器去运行
均衡性：尽可能使整个系统的各个部分（CPU、I/O）都忙起来，提高系统资源的使用效率
吞吐量：单位时间内完成的任务数量
这些性能指标之间具有一定的冲突性
- 比如可通过让更多的任务处于就绪状态来提高CPU的使用率，但这显然会降低系统的响应时间
- 调度程序的设计需要优先考虑最重要的需求，然后在各种因素之间进行折中处理

FCFS

先来先服务算法（First Come First Served，FCFS）：也叫先进先出算法（First In First Out，FIFO）按照任务到达的先后次序进行调度，是不可抢占的调度方式
- 若当前任务占用CPU在运行，一直等到它执行完或被阻塞，才释放CPU
- 被阻塞的任务，唤醒后，放在就绪队列的末尾，重新开始排队
先来先服务算法特点：
- 简单，易于理解，易于实现
- 一批任务的平均周转时间取决于各个任务到达的顺序，如果短任务位于长任务之后，将增大平均周转时间

SJF

短作业优先算法（Shortest Job First，SJF）：各个任务开始执行之前，事先预计好它的执行时间，从中选择用时较短的任务优先执行
短作业优先算法有2种实现方案：
- 不可抢占方式：任务正在运行时，即使来了一个更短的任务，也不会被打断，只有当它运行完毕或被阻塞时，才会让出CPU，进行新的调度
- 可抢占方式：如果一个新的短任务到了，且它的运行时间要小于当前正在运行的任务的剩余时间，则新任务会抢占CPU去运行。也称为最短剩余时间优先算法（Shortest Remaining Time First，SRTF）

RR

时间片轮转调度（round-robin scheduing RR）算法：
- 所有的就绪任务按照先来先服务的原则排成一个队列
- 在每次调度的时候，把处理器分派给队列当中的第一个任务，让它去执行一小段时间（时间片）。在这个时间段里任务被阻塞或结束，或者任务的时间片用完了，它会被送到就绪队列的末尾，然后调度器再执行当前队列的第一个任务
特点：
- 时间片轮转调度（round-robin scheduing RR）算法的优点：
  - 公平性：每个就绪任务平均地分配使用CPU的时间
  - 活动性：每个就绪任务都能一直保持着活动性
- 采用时间片轮转调度算法，任务的时间片大小要适当选择
- 时间片大小的选择会影响系统的性能和效率
  - 时间片太大，时间片轮转调度就没有意义
  - 时间片太小，任务切换过于频繁，处理器开销大，真正用于运行应用程序的时间会减小
时间片轮转法有一个默认前提，即位于就绪队列中的各个任务时同等重要的
- 任务按照先来后到的顺序排成一个队列
- 大家轮流执行相同长度的时间片

优先级算法：

给每个任务都设置一个优先级
在任务调度的时候，让所有处于就绪状态的任务中选择优先级最高的那个任务去运行
优先级算法分为：可抢占式和不可抢占式
- 可抢占式：当一个任务正在运行，一个优先级更高的新任务进入就绪状态，会立即抢占CPU运行新任务
- 不可抢占式：当一个任务正在运行，一个优先级更高的新任务进入就绪状态，等当前任务执行完再决定
优先级算法确定方式：
- 静态方式
  - 在创建任务的时候就确定任务的优先级，且一直保持不变直到任务结束
  - 缺点：高优先级的任务会一直占用着CPU运行，低优先级的任务可能会长时间地得不到CPU，一直处于“饥饿”状态
- 动态方式
  - 在创建任务的时候确定任务的优先级，但该优先级可以在任务的运行过程中动态改变，以获得更好的调度性能
在优先级算法中，把任务按照不同的优先级进行分组，不同组的任务之间使用优先级算法，同一组的各任务之间使用时间片轮转法
采用优先级调度算法还有一个问题是可能会发生优先级反转（priority inversion），出现任务“饥饿”现象
理想情况下，高优先级任务就绪后，能够立即抢占低优先级任务而得到执行
实际系统中，但在有多个任务需要使用共享资源的情况下，可能会出现高优先级任务被低优先级任务阻塞，并等待低优先级任务执行的现象
优先级反转（priority inversion）
- 高优先级任务需要等待低优先级任务释放资源，而低优先级任务又正在等待中等优先级任务的现象

任务间通信

任务间通信（intertask communication）：任务之间为了协调工作，需要相互交换数据和控制信息
任务之间的通信可以分为两种类型：
- 低级通信：只能传递状态和整数值等控制信息，例如信号量机制、异步信号机制
- 高级通信：能够传输任意数量的数据，主要有三类：共享内存、消息传递和管道
共享内存（shared memory）：各个任务共享其地址空间中的某些部分，在此区域，可以任意读写和使用任意的数据结构，把它看成一个通用的缓冲区
- 使用共享内存来传递数据时，通常需和任务间的互斥机制结合起来，以免产生竞争条件，确保数据顺利传送
消息：内存空间中一段长度可变的缓冲区，其长度和内容均可以由用户定义，其内容可以是实际的数据、数据块的指针或空
对消息内容的解释由应用完成
- 从操作系统观点看，消息没有定义的格式，所有的消息都是字节流，没有特定的含义
- 从应用观点看，根据应用定义的消息格式，消息被解释成特定的含义
- 应用可以只把消息当成一个标志，这时消息机制用于实现同步
消息传递：任务与任务之间通过发送和接受消息来交换信息
消息机制由操作系统来维护，包括定义寻址方式、认证协议、消息的数量等，一般提供两个基本操作
- send操作：发送一条消息
- receive操作：接受一条消息
任务间的通信方式：
- 直接通信。在通信过程中双方必须明确地知道（命名）彼此：
  - Send（p，message）发送一个消息到任务p
  - Receive（Q，message）从任务Q接受一个消息
- 间接通信。通信双方不需要指出消息的来源或去向，而通过中间机制来通信。如：
  - snend（A，message）发送一个消息给邮箱A
  - receive（A，message）从邮箱A接受一个消息
一些操作系统内核把消息进一步分为：邮箱和消息队列
- 邮箱仅能存放单条消息，它提供了一种低开销的机制来传递信息。每个邮箱可以保存一条大小为若干个字节的消息
- 消息队列可存放若干消息，提供了一种任务间缓冲通信的方法，间接通信方式
管道（pipe）是提供非结构化数据交换和实现任务间同步的内核对象。在传统的实现中，管道是单向数据交换设施
- 数据在管道中像一个非结构字节流，按FIFO的次序从管道中读出
- 当管道空时，阻塞读者，当管道满时，阻塞写者
管道和消息队列的区别
- 管道不存储多个消息，它存储的数据是非结构化的字节流
- 管道中的数据严格地遵循先进先出的顺序
- 管道支持选择（select）操作，而消息队列不支持