系统架构设计师②：操作系统

操作系统作用
①管理系统的硬件、软件、数据资源
②控制程序运行
③人机之间的接口
④应用软件与硬件之间的接口

进程管理

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成。

PCB:PCB是进程存在的唯一标志。内容包含进程标识符、状态、位置信控制信息、队列指针(链接同一状态的进程)、优先级、现场保护区等。

注意：进程与程序的区别-进程是程序的一次执行过程，没有程序就没有进程。

程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是。

进程的2个基本属性：
①可拥有资源的独立单位
②可独立调度和分配资源的基本单位

进程和线程共享资源情况如下图所示：

进程的状态

进程状态转移图：

信号量与PV操作

临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、
磁带机、缓冲区等
临界区:每个进程中访问临界资源的那段代码称为临界区
信号量:是一种特殊的变量

注:P是荷兰语的Passeren，V是荷兰语的Verhoog。

前驱图

操作系统中的前驱图（Precedence Graph），又称为有向无环图（Directed Acyclic Graph，简称DAG），是一种用来描述程序（或进程）之间先后执行顺序的数据结构。

以下是对前驱图的详细解析：

一、前驱图的定义与性质

定义：前驱图是一种有向无环图，用于表示进程或任务之间的优先级或执行顺序。它通过节点和边的组合，清晰地展示了进程间的依赖关系。
性质：
有向性：图中的边具有方向，表示进程间的执行顺序。
无环性：图中不存在环路，即不存在一个进程直接或间接地依赖于自己，这避免了死锁的产生。
连通性：虽然前驱图是无环的，但它可能是一个连通图，即任意两个节点之间都存在一条路径相连。

二、前驱图的组成元素

节点：代表一个进程或任务。这些进程可能是并发执行的，也可能是串行执行的，具体取决于它们之间的依赖关系。
边：表示两个进程之间的依赖关系。如果存在从进程A到进程B的边，那么进程A是进程B的前驱，意味着进程B必须等待进程A完成后才能开始执行。

三、前驱图的作用

进程调度：通过前驱图，操作系统可以清晰地看到各个进程之间的依赖关系，从而进行合理的进程调度。例如，对于那些没有任何前驱的进程，操作系统可以选择它们作为首先执行的候选者；而对于那些还有未完成前驱的进程，则需要等待其所有前驱都完成后才能被考虑执行。

死锁检测：前驱图也是检测死锁的一种工具。在操作系统中，如果存在一组进程，它们之间的依赖关系形成了一个环路，则可能会发生死锁。

优先级分配：在某些情况下，操作系统需要根据进程的依赖关系来分配优先级。利用前驱图，我们可以确定每个进程的优先级。例如，如果一个进程有很多后继，那么这个进程就应该被赋予高优先级，因为它的完成会影响到很多其他进程；反之，如果一个进程没有任何后继，那么这个进程就可以被赋予低优先级。

死锁及银行家算法

死锁是在并发环境下，两个或多个进程（线程）互相等待对方持有的资源而无法继续执行的状态。
死锁的形成条件主要包括以下四个：

互斥条件（Mutual Exclusion）：
定义：指一个资源每次只能被一个进程（线程）所使用，即资源具有排他性。
说明：这是由资源本身的属性决定的，即资源不能被多个进程同时共享。

请求与保持条件（Hold and Wait）：
定义：也称为占有且等待条件，指进程在请求新的资源的同时不会释放已经占有的资源。
说明：这意味着进程在持有至少一个资源的同时，还在等待其他资源。

不可抢占条件（No Preemption）：
定义：指资源只能由持有者主动释放，其他进程无法强制剥夺持有者资源。
说明：资源一旦被进程占用，在其使用完之前，不能被其他进程强行抢占。

循环等待条件（Circular Wait）：
定义：指一组进程互相等待对方所持有的资源，形成一个循环等待的链式结构。
说明：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有若干种资源中的某一种，同时每一个进程还要求链上下一个进程所占有的资源。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立。反之，只要上述条件之一不满足，就不会发生死锁。

存储管理

页式存储

页式存储:将程序与内存均划分为同样大小的块，以页为单位将程序调入内存。

优点:利用率高，碎片小，分配及管理简单
缺点:①增加了系统开销;②可能产生抖动现象

段氏存储

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。

优点:多道程序共享内存，各段程序修改互不影响
缺点:内存利用率低，内存碎片浪费大

段页式存储

段页式存储:段式与页式的综合体。先分段，再分页。1个程序有若干个段，每段中可以有若干页，每个页的大小相同，但每个段的大小不同。

优点:空间浪费小、存储共享容易、存储保护容易、能动态连接
缺点:由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内存也有所增加，使得执行速度大大下降

页面置换算法

页面置换算法（Page Replacement Algorithm），也称为页面替换策略或页面调度算法，主要用于管理计算机内存中页面的置换，以确保有效的内存使用和较低的页面错误率。当操作系统需要为新的页面分配内存空间，但所有内存空间都已满时，就会根据页面置换算法选择一个页面将其移出内存，以便为新的页面腾出空间。

以下是一些常见的页面置换算法：

最优页面置换算法（Optimal Page Replacement Algorithm）：
在页面置换时，选择将来最长时间不会被访问的页面进行置换。这是一个理论上的算法，实际上无法实现，因为它需要知道未来的页面访问顺序。

先进先出页面置换算法（First-In, First-Out Page Replacement Algorithm, FIFO）：
最简单的页面置换算法，总是移除最早进入内存的页面。可能会导致“Belady异常”，即分配的物理块数增加，页面错误率反而提高。

最近最少使用页面置换算法（Least Recently Used Page Replacement Algorithm, LRU）：
移除最长时间未被访问的页面。通常需要维护一个记录所有页面使用情况的列表。

时钟页面置换算法（Clock Page Replacement Algorithm）：
是LRU的近似实现，使用更少的资源。维护一个循环列表，类似于时钟的指针移动，选择置换页面。

第二次机会算法（Second Chance Algorithm）：
是时钟算法的变种，给予要被置换的页面第二次留在内存中的机会。如果页面的引用位为0，则置换该页面；如果为1，则清除引用位，并给予该页面第二次机会。

工作集页面置换算法（Working Set Page Replacement Algorithm）：
基于“工作集”理论，即进程在一段时间内会频繁访问特定的页面集合。置换不在当前工作集中的页面。

最不常用页面置换算法（Least Frequently Used Page Replacement Algorithm, LFU）：
移除访问次数最少的页面。需要记录每个页面的访问频率。

选择哪种页面置换算法取决于特定的系统需求和目标，例如，对页面错误率的容忍度、算法实现的复杂度和开销等。

文件管理

索引文件

文件索引是一种用于快速定位和访问文件中特定记录的数据结构或机制。它类似于书籍的目录，可以帮助用户快速找到所需的信息。

一、定义与作用

文件索引是一种特殊的文件或数据结构，用于存储关于主文件中记录的关键信息（如关键字、记录的物理地址等），以便快速检索和访问这些记录。索引的主要作用是加快数据检索速度，提高数据处理效率。

二、类型与结构

文件索引根据其结构和用途可以分为多种类型，
主要包括：
顺序索引：索引项按关键字顺序排列，适用于主文件也是按关键字顺序排列的情况。这种索引结构简单，但只适用于顺序存取。

非顺序索引（稠密索引）：为每个记录建立一个索引项，索引项按关键字顺序排列，适用于主文件记录无序的情况。这种索引结构占用空间较大，但支持随机存取。

稀疏索引：只为记录集中的某些记录建立索引项，适用于记录集较大且分布均匀的情况。这种索引结构占用空间较小，但检索效率可能略低于稠密索引。

此外，根据索引的层次结构，还可以分为单级索引和多级索引。多级索引通过为索引表建立索引表的方式，进一步提高了检索效率。
文件在逻辑上是连续的，但是在物理存储上可以是分散的。

位示图

位示图（Bitmap），又称位图，是一种非常重要的数据结构，特别是在文件系统和数据管理中有着广泛的应用。

定义：位示图是利用二进制的一位来表示磁盘（或其他存储介质）中的一个盘块（或存储块）的使用情况。

基本原理：每个bit（二进制位）对应一个盘块，通过该bit的取值（0或1）来表示对应盘块的空闲或已分配状态。有的系统中，0表示空闲，1表示已分配；而有的系统则相反，但本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况。

树形目录结构

文件属性：
①R只读文件属性
②A存档属性
③S系统文件
④H隐藏文件

文件名组成：
①驱动器号
②路径
③主文件名
④扩展名

①绝对路径：从盘符开始的路径
②相对路径：从当前目录开始的路径
若当前目录为:D1，要求F2路径，则:绝对路径:/D1/W2/F2，相对路径:W2/F2

微内核操作系统

现代操作系统大多拥有两种工作状态，分别是核心态和用户态。一般应用程序工作在用户态，而内核模块和最基本的操作系统核心工作在核心态。
将传统的操作系统代码放置到更高层，从操作系统中去掉尽可能多的东西，而只留下最小的核心，称之为微内核。(C/S结构)

操作系统的内核服务:异常和中断、计时器、I/O管理等

单体内核和微内核的对比

嵌入式操作系统

嵌入式系统主要由嵌入式硬件平台、相关支撑硬件、嵌入式操作系统、支撑软件和应用软件组成。
其中，嵌入性、专用性和计算机系统是嵌入式系统的三个核心要素。

典型的嵌入式系统具有以下特点:
① 系统专用性强
② 系统实时性强
③ 软硬件依赖性强
④ 处理器专用
⑤多种技术紧密结合
⑥系统透明性
⑦ 系统资源受限

嵌入式操作系统特点:

①微型化、② 代码质量高、③ 专业化、④ 实时性强、⑤ 可裁减、可配置。

针对不同的硬件平台，操作系统通常建立在一个硬件抽象层(HAL)上，该层位于底层硬件和内核之间，为内核提供各种方便移植的宏定义
接口，在不同的平台间移植时，只需要修改宏定义即可。

与硬件相关，与操作系统相关。

嵌入式系统开发设计之交叉编译

交叉编译（Cross-compilation）是一种编译技术，它允许你在一个平台上编译出适用于另一个平台的可执行代码。这种技术非常有用，特别是在嵌入式系统、移动设备和游戏开发等领域，因为开发者可能无法直接在目标硬件上运行编译工具和编译过程。

交叉编译的基本步骤
①准备交叉编译工具链：
交叉编译工具链是一组工具（如编译器、链接器、调试器等），它们被配置为在宿主机上运行，但生成针对目标平台的代码。这通常包括GCC（GNU Compiler Collection）的变体，以及可能的其他工具，如binutils（一组二进制工具）。

②安装交叉编译工具链：
可以从源代码编译工具链，或者从许多Linux发行版的包管理器中安装预编译的工具链。例如，在Ubuntu上，你可以使用apt-get安装针对ARM架构的交叉编译工具链。

③配置编译环境：
确保环境变量（如PATH）包含了交叉编译工具链的路径。调用gcc或g++时，系统会使用交叉编译版本的工具。

④编写或准备源代码：
确保源代码是可移植的，并且没有依赖于宿主机特有的特性。

⑤修改Makefile或CMakeLists.txt（如果适用）：
如果项目使用Makefile或CMake，需要修改它以使用交叉编译工具链。这通常涉及到设置CC（C编译器）、CXX（C++编译器）等变量。
例如，在Makefile中：

makefile CC=arm-linux-gnueabihf-gcc   CXX=arm-linux-gnueabihf-g++ 

在CMake中，你可以使用toolchain文件来指定交叉编译工具链。

⑥编译源代码：
使用交叉编译工具链编译你的源代码。涉及到在命令行中运行make或cmake命令。

注意：
依赖库：如果你的程序依赖于第三方库，这些库也需要被交叉编译或已经存在适用于目标平台的版本。
系统调用和API：确保你的代码不依赖于宿主机特有的系统调用或API。
调试：交叉编译的程序可能难以在宿主机上调试。使用目标平台上的调试工具（如GDB）可能更为有效。

基于硬件的低功耗设计
板级电路低功耗设计;选择低功耗处理器;总线的低功耗设计:接口驱动电路的设计;分区分时供电技术。

基于软件的低功耗设计
编译优化技术(指令开销);软件与硬件的协同设计(硬件功能交由软件完成);算法优化(低时间复杂度)。

实时操作系统

实时操作系统是指当外界事件或数据产生时，能够接受并以足够快的速度予以处理，其处理的结果又能在规定的时间之内来控制生产过程或对处理系统做出快速响应，调度一切可利用的资源完成实时任务，并控制所有实时任务协调一致运行的操作系统。

其主要特点包括：

①及时响应：RTOS通过实时任务调度器，能够保证高优先级任务在有限的时间内得到响应和处理，这对于需要快速反应的系统至关重要。
②高可靠性：RTOS的设计注重于系统的稳定性和可靠性，通常包含错误检测和恢复机制，以确保系统即使在出现问题时也能保持运行。
③优化资源管理：RTOS能够有效地管理和分配系统资源，如CPU时间、内存和I/O设备，确保关键任务能够获得必要的资源以按时完成。
④支持多任务处理：RTOS允许多个任务并发执行，每个任务可以独立运行，互不干扰，这样可以提高系统的效率和性能。
⑤减少延迟：RTOS通过减少粗粒度的锁和长期关中断的使用，降低了系统的延迟，提高了响应速度。

实时系统的性能指标：

①任务切换时间
②中断处理相关的时间指标
-中断延迟时间
-中断响应时间
③系统响应时间（对用户的输入或请求做出反应的时间）
④信号量混洗时间（指从一个任务释放信号量到另一个等待该信号量的任务被激活的时间延迟）

实时系统存在多种调度算法

①优先级调度算法:分配一个相对固定的优先顺序，然后调度程序根据优先级的高低排序按时间顺序进行高优先级任务优先调度。(非抢占式)

②抢占式优先级调度算法:是在优先级调度算法基础上，允许高优先级任务抢占低优先级任务而运行。

③时间轮转调度算法:调度程序会依次调度每个任务运行一个小的时间片，然后再调度另一个任务。每个任务运行完一个时间片，无论是否结束都会释放CPU让下一个任务运行。(纯粹的时间轮转调度无法满足实时系统的要求，取而代之的是基于优先级的抢占式时间轮转调度)

④最晚截止期调度算法:指调度程序按每个任务的最接近其截止期末端的时间进行调度

⑤最早截止期调度算法:指调度程序按每个任务的截止期时间，选择最早到截止期头端时间的任务进行调度。

在RTOS中，大多数的RTOS调度算法都是抢占式的

常见的实时操作系统

常见的嵌入式RTOS(实时操作系统,Real-TimeOperatingSystem)VxWorks、RT-Linux、QNX、pSOS.