Operation System_操作系统 - Hanni Rio’s Blog

Reference：黑书、https://www.cnblogs.com/Roshin/p/WangDao_OS_notes.html
不是修考重点，但是迅速回顾一下❗️

第一部份：导论

计算机系统可以粗分为四个部件：硬件（hardware）、内存（memory）、输入/输出设备（I/O device）、应用程序（application program）。操作系统设计的主要目的是用户使用方便（ease of use），次要的是性能，不在乎的是资源利用（resource utilization）(如何共享硬件和软件资源)。

关于OS一个公认的定义是，操作系统是一直运行在计算机上的程序（通常称为内核kernel）

事件发生通常通过硬件或软件的中断（interrupt）来通知。当CPU被中断时，它停止正在做的事，并立即转到固定位置再继续执行。这个固定位置通包含中断服务程序的开始地址。中断服务程序开始执行，在执行完毕后，CPU重新执行被中断的计算。

CPU只能从内存中加载指令，因此执行程序必须位于内存。在理想情况下，程序和数据都应永久驻留在内存中，但由于两个原因是不可能的：
1️⃣内存通常太少，不能永久保护所有需要的程序的数据。
2️⃣内存是易失性的(volatile)存储设备，掉电时就会失去所有内容。
因此❗️大多数的计算机系统都提供外存（secondary storage）来扩充内存；最常用的外存设备是磁盘或硬盘（magnetic disk）。大多数程序（系统与应用）都保存在磁盘上，当要执行时才加载到内存

单处理系统：只有一个主CPU，以便执行一个通用指令集
多处理器系统（multiprocessing system）(也称为并行系统（parallel system）)或多核系统（multicore system），主要有三个优点：
1️⃣增加吞吐量: 采用N个处理器的加速比不是N，而是小于N（考虑资源共享竞争）
2️⃣规模经济：多处理器系统的价格低于相同功能的多个单处理器系统的价格
3️⃣增加可靠性：如果将功能分布在多个处理器上，那么单个处理器的失灵不会使整个系统停止，而只会让它变慢（鸡蛋不要装在一个篮子里🥚🧺）

在操作系统中，**中断（Interrupt）和异常（Exception）**是两种重要的事件，它们都会导致CPU暂停当前的任务，转而去处理这些事件。

中断（Interrupt）：中断是由硬件设备（如键盘，鼠标，网络接口卡等）发出的信号，通知操作系统有一些重要的事件发生，需要立即处理。例如，当你按下键盘上的一个键时，键盘会向CPU发送一个中断信号，CPU会暂停当前的任务，转而去处理这个按键事件。处理完这个事件后，CPU会返回到被中断的任务，继续执行。
异常（Exception）：异常是由CPU在执行指令过程中发现的问题，如除以零，访问无效的内存地址等。当发生异常时，CPU会暂停当前的任务，转而去执行一个特殊的异常处理程序。处理完这个异常后，CPU可能会返回到被中断的任务，也可能会终止这个任务，这取决于异常的类型和严重性。

总的来说，中断和异常都是操作系统用来响应和处理重要事件的机制。它们都会导致CPU暂停当前的任务，但是它们的来源和处理方式是不同的。
发生中断，意味着OS需要介入，展开管理工作；用户台和和心态的切换是通过中断（interrupt）实现的，并且是唯一途径，改变程序状态字（PSW）即可。

API（应用程序编程接口）和系统调用（System Call）都是一种接口，它们允许程序员访问某些预定义的功能或服务。系统调用是操作系统提供的一组函数，程序员可以通过这些函数请求操作系统提供的低级服务，如文件操作，网络访问，进程管理等。系统调用通常在内核模式下执行，因为它们需要访问受保护的系统资源。API则更为广泛，它可以是一组函数、类、协议或工具，用于构建或交互软件应用。API可以是操作系统的一部分，也可以是库、框架、服务等的一部分。API的主要目的是提供一种抽象，使程序员可以使用高级语言和简单的接口来完成复杂的任务。系统调用可以被看作是操作系统API的一部分。当你在编程时使用API，你可能会间接地使用系统调用。例如，当你使用C++的文件流对象（如std::fstream）来读写文件时，这些对象内部可能会使用到操作系统的系统调用来进行实际的文件操作。总的来说，API和系统调用都是使程序员能够更容易地编写代码和交互系统的工具。API提供了更高级别的抽象，而系统调用则提供了对操作系统服务的直接访问。

系统调用流程

传递系统调用参数
执行陷入指令(用户态)
- 陷入指令在用户态执行, 执行陷入指令后立即引发内中断, 从而 CPU 进入核心态
- 发出请求在用户态, 相应处理在核心态
- 是唯一一个只能在用户态执行的指令, 核心态不可执行
执行系统调用相应服务程序(核心态)
返回用户程序

操作系统的四个重要特征包括：

并发（Concurrency）：并发是指两个或多个事件在同一时间间隔内发生。在操作系统中，这可以是通过多线程或进程实现的，它们可以在一个处理器上交替执行，或者在多个处理器上同时执行。（并行是指两个或多个事件在同一时刻同时发生）
共享（Sharing）：共享是指系统中的资源可以被多个并发进程共同使用。有两种共享方式：同时访问（同时共享）或者在一段时间内交替访问（互斥共享）。
虚拟化（Virtualization）：虚拟化是指把一个物理资源（如处理器，内存或磁盘）抽象为多个逻辑资源，或者把多个物理资源抽象为一个逻辑资源。这使得用户感觉有更多的资源可用，或者使得资源使用更加高效。eg。空分复用（虚拟存储器，4G内存电脑拥有,同时运行超过4G运行空间的程序），时分复用（虚拟处理器，CPU时间片轮转）
异步性（Asynchronism）：异步性是指由于进程间的并发性，使得进程交替执行，进程的执行不是一贯的，也不是在固定的时间间隔内发生。（也就是走走停停）

第二部份：进程管理

进程（Process）是计算机中的程序关于其运行过程的抽象，也是操作系统资源分配和调度的基本单位。每个进程都有自己的独立地址空间，包含了程序运行所需要的所有资源。
进程的组成主要包括以下部分：

程序计数器（Program Counter）：存储了下一条需要执行的指令的地址。
进程状态（Process State）：描述了进程当前的状态，如运行态，就绪态，等待态等。
寄存器（Registers）：包含了进程运行所需要的当前值，如累加器，数据寄存器，地址寄存器等。
内存管理信息（Memory Management Information）：包含了进程地址空间的信息，如页表，段表等。

进程的组织方式通常是通过进程控制块（Process Control Block, PCB）来实现的。PCB是操作系统中用于表示进程的数据结构，每个进程都有一个对应的PCB，其中包含了进程的状态，程序计数器，CPU寄存器和内存管理信息等。PCB是进程存在的唯一标志！！
进程的特征主要包括：

动态性（Dynamic）：进程是程序的一次执行过程，它有创建，结束的生命周期。
并发性（Concurrent）：多个进程可以并发执行。
独立性（Independent）：每个进程都有自己独立的地址空间，一般情况下，除非显式共享，否则进程之间不能直接访问其他进程的资源。
异步性（Asynchronism）：由于进程间的并发性，使得进程交替执行，进程的执行不是一贯的，也不是在固定的时间间隔内发生。

进程在其生命周期中会经历几种不同的状态，主要包括：

新建（New）：进程正在被创建。
运行（Running）：指令正在被执行。
等待（Waiting）：进程正在等待某些事件发生，例如等待用户输入或等待I/O操作完成。
就绪（Ready）：进程已经准备好运行，正在等待系统分配处理器。
终止（Terminated）：进程已经完成执行，或者被系统终止。

这些状态之间的转换通常由操作系统的调度程序（Scheduler）控制。例如，当一个进程从等待状态变为就绪状态时，可能是因为它所等待的事件已经发生；当一个进程从运行状态变为等待状态时，可能是因为它发起了一个I/O请求，需要等待这个请求完成。

**进程控制块（Process Control Block，PCB）**是操作系统中的一个数据结构，用于存储特定进程相关的信息。PCB的主要组成信息包括：

进程标识符（Process Identifier）：每个进程都有一个唯一的标识符，用于区分不同的进程。
进程状态（Process State）：记录进程当前的状态，如新建（New），运行（Running），等待（Waiting），就绪（Ready），或者终止（Terminated）。
程序计数器（Program Counter）：存储了下一条需要执行的指令的地址。
CPU寄存器（CPU Registers）：保存了进程当前的运行状态，包括累加器，数据寄存器，地址寄存器等。
CPU调度信息（CPU Scheduling Information）：包括进程优先级，调度队列的链接等。
内存管理信息（Memory Management Information）：包含了进程地址空间的信息，如页表，段表等。
账号和审计信息（Accounting and Auditing Information）：包括CPU使用的总时间，时间限制，账号号码，进程号等。
I/O状态信息（I/O Status Information）：包括I/O请求，分配的I/O设备，文件列表等。

PCB是操作系统管理和控制进程的关键数据结构，它包含了操作系统需要知道的关于进程的所有信息。

**进程控制（Process Control）**是操作系统中的一个重要概念，它涉及到创建、调度、暂停和终止进程等操作。以下是一些与进程控制相关的关键概念：

进程创建（Process Creation）：新的进程可以由已有的进程创建。在UNIX和Linux系统中，这通常通过fork系统调用实现。
进程调度（Process Scheduling）：操作系统的调度程序决定哪个进程应该获得CPU的使用权。这涉及到一些策略，如优先级调度，轮转调度，多级反馈队列调度等。
进程暂停（Process Suspension）：一个正在运行的进程可能会被暂停，此时它的状态会被保存下来，以便以后可以恢复执行。这通常发生在多任务系统中，当系统资源需要被其他更高优先级的进程使用时。
进程终止（Process Termination）：当进程完成其执行或者由于某种原因需要被终止时，操作系统会回收它占用的资源，并将其从系统中移除。

这些操作都是操作系统进行进程管理的基本手段，它们使得操作系统可以有效地管理和控制系统中的并发执行的进程。

**进程通信（Inter-Process Communication，IPC）**是操作系统提供的一种机制，允许进程之间共享信息和协调行为。进程通信对于构建复杂的并发应用程序至关重要，因为它允许进程之间进行数据交换，同步执行，以及共享系统资源。
进程通信的主要方法包括：

管道（Pipes）：管道是最简单的IPC形式，通常用于父子进程之间的通信。数据在管道中只能单向流动。（因为是半双工通信，如果要实行双向同时通信，则需要设置两个管道）注：“管道”是指用于连接读写进程的一个共享文件，又名pipe文件。其实就是在内存中开辟个大小固定的缓冲区
消息队列（Message Queues）：消息队列允许进程将消息发送到一个队列中，其他进程可以从队列中读取这些消息。消息队列支持不同进程之间的通信，而不仅仅是父子进程。
共享内存（Shared Memory）：在共享内存模型中，两个或更多的进程可以访问同一块内存区域。一个进程写入的数据可以被其他进程读取。这里的访问必须要是互斥的！
信号（Signals）：信号是一种用于通知进程某个事件已经发生的机制。例如，当用户按下Ctrl+C时，会向前台进程发送一个中断信号。
套接字（Sockets）：套接字是一种在网络中进行进程间通信的机制，支持不同机器上的进程间的通信。

线程与多线程

线程（Thread）：是程序执行流的最小单元，也是基本的CPU执行单元。一个进程可以包含多个线程，所有线程共享进程的资源，如内存空间，文件句柄等。引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）即, 进程是资源分配的基本单位, 线程是调度的基本单位。线程的主要特性包括：

轻量级（Lightweight）：线程是比进程更小的执行单位，创建、销毁和切换线程的开销比进程要小。
共享资源（Resource Sharing）：同一进程内的线程共享进程的资源，如内存，全局变量等。这使得线程间的通信更加方便。
并发性（Concurrency）：在多核或多处理器的系统中，进程内的多个线程可以并行执行，提高了系统的并发性。
独立调度（Independent Scheduling）：操作系统独立调度每个线程，当一个线程阻塞时，其他线程可以继续执行。

⚠️重点: 只有内核级线程才是处理机分配的单位

操作系统中的**多线程模型（Multithreading Models）**主要有以下几种：

一对一模型（One-to-One Model）：这种模型中，每个用户线程都映射到一个内核线程。这种模型的优点是可以充分利用多处理器的并行性，因为每个线程都可以在不同的处理器上运行。然而，由于每个线程都需要一个内核线程，所以线程的创建和管理开销可能会比较大。
多对一模型（Many-to-One Model）：这种模型中，多个用户线程映射到一个内核线程。这种模型的优点是线程的创建和管理开销较小，但是由于所有线程都运行在同一个内核线程上，所以不能利用多处理器的并行性。
多对多模型（Many-to-Many Model）：这种模型中，多个用户线程可以映射到多个内核线程。这种模型结合了前两种模型的优点，既可以利用多处理器的并行性，又可以控制线程的创建和管理开销。
二级模型（Two-Level Model）：这种模型是多对多模型的一种变体，允许多个用户线程映射到同一个内核线程，也允许一个用户线程映射到多个内核线程。

在操作系统中，**进程调度（Process Scheduling）**是一个核心功能，它决定了哪个进程应该获得CPU的使用权。以下是一些关于进程调度的关键概念：

调度时机（Scheduling Points）：操作系统可能在以下几个时刻进行进程调度：
- 当一个进程从运行状态转换到等待状态时（例如，当进程进行I/O操作时）。
- 当一个进程从运行状态转换到就绪状态时（例如，当操作系统分配给进程的CPU时间片用完时）。
- 当一个进程从等待状态转换到就绪状态时（例如，当进程等待的I/O操作完成时）。
- 当一个进程结束时。
上下文切换（Context Switch）：当CPU从一个进程切换到另一个进程时，操作系统会保存当前进程的状态，并加载新进程的状态。这个过程被称为上下文切换。
调度策略（Scheduling Policies）：操作系统使用一种或多种策略来决定下一个要运行的进程。这些策略可能包括先来先服务（First-Come, First-Served），短作业优先（Shortest Job Next），优先级调度（Priority Scheduling），轮转调度（Round Robin），多级反馈队列（Multilevel Feedback Queue）等。

在操作系统中，评价调度算法的性能通常会考虑以下几个指标：

周转时间（Turnaround Time）：这是指从进程提交（开始）到进程完成（结束）的总时间。周转时间包括了进程在CPU上运行的时间，以及在就绪队列和等待队列中等待的时间。周转时间越短，说明系统的响应性越好。周转时间的计算公式为：周转时间 = 进程完成时间 - 进程到达时间。
等待时间（Waiting Time）：这是指进程在就绪队列中等待CPU的总时间。等待时间越短，说明系统的效率越高。等待时间的计算公式为：等待时间 = 周转时间 - 进程实际运行时间。
响应时间（Response Time）：在交互式系统中，响应时间是一个重要的指标。这是指从进程提交到进程开始运行的时间。响应时间越短，用户感觉到的系统速度越快。
吞吐量（Throughput）：这是指单位时间内系统完成进程的数量。吞吐量越高，说明系统的效率越高。系统吞吐量 = 总共完成多少作业 / 总共花了多少时间

调度算法

1️⃣先到先服务（First-Come First-Served, FCFS）直观理解

**先到先服务（First-Come, First-Served，FCFS）**是一种简单的进程调度算法，它的工作原理是：当进程到达系统时，它们被放入就绪队列。调度器选择队列中的第一个进程进行执行，直到该进程完成或发生阻塞事件，然后调度器选择下一个进程。
优点：
公平性（Fairness）：FCFS算法对所有进程都是公平的，因为它按照进程到达的顺序进行调度。
简单性（Simplicity）：FCFS算法非常简单和易于实现。
缺点：
无法充分利用CPU（Poor CPU Utilization）：如果当前正在运行的进程需要大量的I/O操作，那么CPU可能会在等待I/O操作完成时处于空闲状态。
平均等待时间可能较长（Long Average Waiting Time）：在FCFS算法中，短的进程可能会被长的进程阻塞，这种现象被称为“饥饿”（Starvation）或“拖尾效应”（Convoy Effect）。
无法支持优先级（Lack of Priority Support）：FCFS算法不支持优先级，因此无法保证重要的进程能够优先执行。
总的来说，虽然FCFS算法简单且公平，但由于其无法有效地利用CPU和支持优先级，所以在需要高效率或优先级调度的系统中，通常不会使用FCFS算法。

2️⃣短作业优先（Shortest-Job-First, SJF）直观理解

在这种算法中，调度器选择就绪队列中预计运行时间最短的进程进行执行。预计运行时间可以是进程的CPU突发时间（CPU burst time）或者是进程的剩余执行时间。（这里就要看是非抢占式的还是抢占式的了，可以直观理解）
短作业优先调度算法的主要优点是它最小化了平均等待时间。因为短的进程总是优先于长的进程，所以它们的等待时间会更短，从而使得平均等待时间最小。
然而，这种算法也有一些缺点。首先，它需要知道进程的预计运行时间，但在实际的系统中，这通常是无法预知的。其次，这种算法可能会导致“饥饿”（Starvation）现象，即长的进程可能会被无限期地推迟，因为总是有短的进程到来。
总的来说，短作业优先调度算法在理论上是非常有效的，但在实际的系统中，由于需要预知进程的运行时间以及可能导致的饥饿问题，它的应用受到了一些限制。

3️⃣优先级调度算法（priority-scheduling）

优先级调度算法是一种操作系统中的进程调度算法。在这种算法中，每个进程都有一个优先级，操作系统总是选择优先级最高的进程来运行。这种算法的主要特点如下：
优先级：每个进程都有一个优先级，优先级高的进程优先执行。（抢占式，preemptive）
动态调整：系统可以根据需要动态调整进程的优先级。例如，为了防止低优先级的进程永远得不到执行，系统可能会随着时间的推移提高等待进程的优先级。
饿死问题：如果总是有新的高优先级进程出现，那么低优先级的进程可能永远得不到执行，这就是所谓的饿死问题。为了解决这个问题，系统可能会采取一些策略，比如老化（随着时间的推移提高等待进程的优先级）。
这种算法在实时系统中特别有用，因为在这些系统中，有些任务（比如控制飞机的自动驾驶仪）比其他任务更重要，因此需要优先执行。但是，这种算法也有一些缺点，比如可能会导致低优先级的进程饿死。因此，设计一个好的优先级调度算法需要权衡各种因素。

4️⃣轮转调度（Round-Robin，RR）算法

轮转调度（Round-Robin，RR）算法是一种非常常见的操作系统进程调度算法。以下是对其的简要解释：
时间片（Time Quantum）：在轮转调度算法中，每个进程被分配一个固定长度的时间片来执行。当一个进程的时间片用完时，它将被移出CPU，下一个进程将开始执行。
公平性（Fairness）：由于每个进程都有相同长度的时间片来执行，因此这种算法被认为是公平的。没有进程会因为优先级低而被饿死。
上下文切换（Context Switch）：当一个进程的时间片用完，操作系统需要进行上下文切换，将CPU从当前进程切换到下一个进程。这会产生一定的开销。
响应时间（Response Time）：轮转调度算法通常能提供良好的响应时间，因为每个进程都会定期得到CPU时间。
这种算法适用于时间共享系统，但如果时间片设置得不合适，可能会导致过多的上下文切换，从而降低系统性能。因此，选择合适的时间片长度是实现轮转调度算法的关键。如果时间片过长，那么系统的响应时间可能会变差；如果时间片过短，那么上下文切换的开销可能会变大。

同一时刻两个进程 A 和 B, A 刚下处理机, B 刚进入队列, 默认 B 先轮转时间片
如果时间片太大, 退化为FCFS, 会增大进程响应时间
如果时间片太小, 进程切换频繁, 切换进程会花费大量时间
一般来说, 设计时间片要让切换进程的开销占比不超过 1%

5️⃣多级反馈队列调度算法（multilevel feedback queue）

多级反馈队列调度算法（Multilevel Feedback Queue Scheduling）是一种操作系统中的进程调度算法。以下是对其的简要解释：
多级队列（Multilevel Queues）：在这种算法中，存在多个队列，每个队列都有自己的优先级。优先级最高的队列中的进程首先得到执行。（也就是前一队列为空的时候，才能执行当前队列！！）
反馈（Feedback）：如果一个进程在其分配的时间片内没有完成，那么它将被移动到优先级较低的队列。这就是所谓的“反馈”机制。
公平性和灵活性（Fairness and Flexibility）：这种算法旨在结合优先级调度和轮转调度的优点，以实现公平性和灵活性。它可以确保高优先级的进程快速执行，同时也不会饿死低优先级的进程。
动态优先级（Dynamic Priorities）：进程的优先级不是固定的，而是可以根据其行为动态改变。例如，如果一个进程经常阻塞等待I/O操作，那么它的优先级可能会提高，以便在I/O操作完成后能够快速得到执行。
这种算法在许多操作系统中都得到了应用，因为它既可以处理交互式进程（这些进程需要快速响应），也可以处理批处理进程（这些进程需要长时间运行）。然而，它的实现相对复杂，需要维护多个队列，并动态调整进程的优先级。此外，选择合适的队列数量和时间片长度也是一个挑战。如果设置不当，可能会导致某些进程得不到公平的CPU时间，或者系统的上下文切换开销过大。因此，实现这种算法需要权衡各种因素。这个算法无明显缺点，但是会导致饥饿！

临界区（Critical Section）：临界区是一个进程中访问共享数据的代码段。如果两个进程同时进入临界区并修改共享数据，可能会导致数据不一致和其他错误。
互斥（Mutual Exclusion）：为了解决临界区问题，需要确保任何时候只有一个进程能进入临界区。这就是所谓的互斥。实现互斥的一种常见方法是使用锁（Locks）或信号量（Semaphores）。
死锁（Deadlock）：如果两个或更多的进程都在等待对方释放资源，那么就会发生死锁。死锁是临界区问题的一个重要方面，需要通过适当的调度和同步机制来避免。
饥饿（Starvation）：如果一个进程长时间无法进入临界区，那么就会发生饥饿。为了避免饥饿，需要使用公平的调度算法，确保每个进程都有机会进入临界区。

进程互斥的软件实现方法

1️⃣单标志法（Single Flag Method）：在这种方法中，有一个共享的布尔标志，用于表示是否有进程正在执行临界区的代码。如果标志为真，那么其他进程就必须等待，直到标志变为假。这种方法简单，但可能会导致竞态条件，因为检查标志和设置标志的操作不是原子的。

// P0:
{
    while (turn != 0);
    critical section;
    turn = 1;
    remainder section;
}
// P1:
{
    while (turn != 1);
    critical section;
    turn = 1;
    remainder section;
}
//访问顺序一定是 01010101... , 当临界区空闲, 0 没有访问临界区时, turn == 0 , 1 需要访问但无法进入.
//不满足空闲让进的互斥原则

2️⃣双标志先检查法（Two Flags, Check First Method）：在这种方法中，每个进程都有一个标志，用于表示它是否希望进入临界区。一个进程在进入临界区之前，会先检查其他进程的标志。如果其他进程的标志表示它们不希望进入临界区，那么这个进程就可以进入临界区。这种方法可以避免单标志法中的竞态条件，但仍然可能会导致死锁。

bool flag[2];       // flag[i] = true 表示 i 进程想要进入临界区
flag[0] = false;
flag[1] = false;        

// P0:
{
    while (flag[1]);
    flag[0] = true;
    critical section;
    flag[0] = false;
    remainder section;
}
// P1:
{
    while (flag[0]);
    flag[1] = true;
    critical section;
    flag[1] = false;
    remainder section;
}
// 若 0, 1 两个进程并发执行, P0 结束while循环还未复制 flag[0] 时, 发生进程切换, P1 也可以进入临界区, 不满足忙则等待 原则.

3️⃣双标志后检查法（Two Flags, Check Afterwards Method）：这种方法与双标志先检查法类似，但在设置自己的标志后，进程会检查其他进程的标志。如果其他进程的标志表示它们不希望进入临界区，那么这个进程就可以进入临界区。这种方法可以避免死锁，但可能会导致饥饿。

4️⃣Peterson 算法（Peterson’s Algorithm）：这是一种解决两个进程的互斥问题的经典算法。在这种算法中，两个进程共享两个变量：一个用于表示希望进入临界区的进程，另一个用于表示轮到哪个进程进入临界区。通过适当地设置和检查这两个变量，可以确保任何时候只有一个进程在临界区内，从而实现互斥。
简要来说：就是主动让对方进入临界区

bool flag[2];
int turn = 0;
// P0
void funcp0(){
    flag[0] = true;
    turn = 1;
    while (flag[1] && turn == 1) ;
    critical section;
    flag[0] = false;
    remainder section;
}

// P1
void funcp1(){
    flag[1] = true;
    turn = 0;
    while (flag[0] && turn == 0) ;
    critical section;
    flag[1] = false;
    remainder section;
}

操作系统中进程互斥的硬件实现方法主要有以下几种：

禁止中断（Disable Interrupts）：在这种方法中，进程在进入临界区之前会禁止所有中断。这可以防止进程在执行临界区代码时被中断，从而避免竞态条件。但是，这种方法只适用于单处理器系统，而且可能会影响系统的响应性。
特殊机器指令（Special Machine Instructions）：一些计算机硬件提供了特殊的机器指令，如测试并设置（Test and Set）或交换（Swap）。这些指令可以在一个不可中断的操作中读取和修改内存位置。这些指令可以用来实现锁，从而实现进程互斥。
原子操作（Atomic Operations）：原子操作是一种特殊类型的操作，它在执行过程中不能被中断。原子操作可以用来实现信号量或其他同步机制，从而实现进程互斥。

信号量机制

信号量（Semaphore）：信号量是一个整数值，通常用于保护临界区和同步进程。它有两个基本操作：P（等待）和V（信号）。（记忆：看声调（1声和4声区别），P减V增）
P操作（P Operation）：如果信号量的值大于零，那么P操作会将其减一。如果信号量的值为零，那么P操作会阻塞进程，直到信号量的值大于零。
V操作（V Operation）：V操作会将信号量的值加一。如果有进程因为P操作而阻塞，那么V操作会唤醒这些进程。

⏰注意:
对不同的临界资源需要设置不同的互斥信号量
P, V 操作必须成对出现
进程同步：
设置同步信号量S, 初始为0
在"前操作"之后执行V(S)
在"后操作"之前执行P(S)

Semaphore S = 0;

void P1(){
    code 1;
    code 2;
    V(S);
    code 3;
}

void P2(){
    P(S);
    code 4;
    code 5;
    code 6;
}
// 这样P1先执行，P2后执行

一张图理解前驱关系

经典同步互斥问题

1️⃣生产者-消费者问题（Producer-Consumer Problem）
改变互斥信号量mutex 在同步信号量操作之间

semaphore mutex = 1;    // 互斥
semaphore empty = n;    // 同步
semaphore full = 0;     // 同步

void put() {
    while (1) {
        P(empty);
        P(mutex);
        把产品放入缓冲区;
        V(mutex);
        v(full);
    }
}

void get() {
    while (1) {
        P(full);
        P(mutex);
        取出产品
        V(mutex);
        V(empty);
        // 使用产品
    }

}

2️⃣读者写者问题

有读者和写者两组并发进程，
共享一个文件，当两个或两个以上的读进程同时访问共享数据时不产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致
数据不一致的错误。因此要求：

允许多个读者可以同时对文件执行读操作；
只允许一个写者往文件中写信息；
任一写者在完成写操作之前不允许其他读者或写者工作；
写者执行写操作前，应让己有的读者和写者全部退出。

semaphore rw = 1;   // 读写锁 
int count = 0;      // 记录正在访问的读者数量
semaphore mutex = 1; // 保证对 count 的互斥访问
semaphore w = 1;    // 实现读写公平

void write(){
    while (1) {
        P(w);
        P(rw);

        写文件...

        V(rw);
        V(w);
    }
}

void read() {
    while (1) {
        P(w);
        P (mutex);
        if (count == 0)
            P(rw);
        count ++;
        V(mutex);
        V(w);

        读文件...

        P(mutex);
        count --;
        if (count == 0)
            V(rw);
        V(mutex);
    }
}

3️⃣哲学家进餐问题

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;

void P() {
    while (1) {
        P(mutex);
        P(chopstick[i]);        // 拿左
        P(chopstick[(i + 1) % 5]);      // 拿右
        V(mutex);
        
        吃饭....

        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
    }
}

管程（Monitor）：管程是一种包含共享数据和操作这些数据的方法的程序模块。这些方法通过互斥地访问共享数据，来保证数据的一致性。每次仅允许一个进程在管程内执行某个内部过程。

死锁定义

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

死锁产生的必要条件

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

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

注意！发生死锁时一定有循环等待

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

问：什么时候回发生死锁？

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

死锁的处理策略

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

2.4.2 死锁处理策略---预防死锁

破坏互斥

SPOOLing技术

把独占设备在逻辑上改造成共享设备, 将输出传输到输出进程，进程端视作完成了输出（打印机）

缺点：适用范围小

破坏不剥夺条件

方案一：进程请求新的资源得不到满足时，它必须释放所保持的所有资源，待以后需要时重新申请。

方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）

该策略的缺点：

实现起来比较复杂
释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态
的资源，如CPU。
反复地申请和释放资源会增加系统开销，降低系统吞吐量
若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重
新申请。如果一直发生这样的情况，就会导致进程饥饿。

破坏请求和保持条件

静态分配：进程在运行前一次性申请自己所需要的所有资源, 没申请到就不运行。

实现简单，但也有缺点：

有些资源可能需要用很短的时间，因此如果进程运行期间一直保持，造成了严重的资源浪费，资源利用率低。
另外，该策略也有可能导致某些进程饥饿。

破坏循环等待条件

顺序资源分配：首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。

原理分析：

一个进程只有己占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持
有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

该策略的缺点：

不方便增加新的设备，因为可能需要重新分配所有的编号。
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费。
必须按规定次序申请资源，用户编程麻烦。

死锁的避免策略

安全序列：就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个
安全序列，系统就是安全状态。当然，安全序列可能有多个。

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

简单来说：就是找到一个起始的进程开始不断迭代🔁，执行完要释放资源，再找下一个满足的进程，然后再释放资源，直到运行完所有的进程。一般就是列一个矩阵然后对比下去🆚

死锁的检测：

如果图中的边都可以被消除，则称这个图是可完全简化的

检测算法：

找到一个既不是孤点也不阻塞的点，消除其所有边
消除后释放的资源可以让某些阻塞进程被唤醒，然后继续消除这些进程的边。

死锁定理

如果某时刻系统的资源分配图是不可完全简化的，那么此时系统发生死锁

死锁解除

注意：并不是所有进程都是死锁状态，用检测算法化简资源分配图后，还连着边的进程就是死锁进程。

主要方法：

资源剥夺法。挂起（放外存）某些进程，抢占资源重新分配给其他进程。后续注意饥饿
撤销进程法（终止进程）。付出代价可能很大，前功尽弃，但实现简单
进程回退法, 让死锁进程回退到足以避免死锁的地步，需要系统记录进程历史信息。

第三部份：内存管理

存储方式

内存地址从 00 开始，每个地址对应一个存储单元
按字节编址，每个存储单元大小为 1 字节， 1B， 8 个 bit
按字编址，在字长为16位计算机中，每个存储单元大小为1个字，每个字大小为 16 个 bit

连续分配管理方式

内部碎片（Internal Fragmentation）：当我们将内存分配给进程时，由于分配的内存块大小通常是固定的（例如，页或段的大小），所以可能会有一部分内存没有被利用。这些未使用的内存部分就构成了内部碎片。换句话说，内部碎片是指分配给某个进程的内存区域中，某些部分没有被利用。
外部碎片（External Fragmentation）：在动态内存分配中，随着时间的推移，内存中可能会出现许多小的空闲分区。这些空闲分区由于太小，无法满足新的内存请求，因此难以被利用。这些小的、无法利用的空闲分区就构成了外部碎片。
紧凑（Compaction）：紧凑是一种用于解决外部碎片问题的技术。它的基本思想是将内存中的所有进程移动到内存的一端，使得所有的空闲分区都集中在内存的另一端，从而形成一个大的、连续的空闲分区。这样，就可以满足大的内存请求，从而解决外部碎片问题。然而，紧凑需要移动进程，因此会产生一定的开销。

动态分区分配算法

首次适应算法（First Fit）：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
最佳适应算法（Best Fit）：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。缺点是每次选最小的分区分配，会留下越来越多，很小的，难以利用的内存块。因此会产生很多的外部碎片（External Fragmentation）。
最坏适应算法（Worst Fit，也叫 Largest Fit）：为了解决最佳适应算法的问题，即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。缺点是每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。
邻近适应算法（Next Fit）：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。空闲分区以地址递增的顺序排列（可排成一个循环链表），每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

分页存储管理概念

分页地址转换

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

将用户进程的地址空间也分为与页框大小相等的一个个区域称为 “页”或“页面”。每个页面也有一个编号，即“页号”
页号也是从0开始。(注：进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片）
操作系统以页框为单位为各个进程分配内存空间。进程的每个
页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

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

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

结论：如果每个页面大小为 2𝑘𝐵，用二进制数表示逻辑地址，则末尾 𝐾 位即为页内偏移量，其余部
分就是页号
因此，如果让每个页面的大小为 2的整数幂，计算机就可以很方便地得出一个逻辑地址对应的页号
和页内偏移量。

页表

一个进程对应一张页表
进程的每一页对应一个页表项
每个页表项由“页号”和“块号” 组成
页表记录进程页面和实际存放的内存块之间的对应关系
每个页表项的长度是相同的，页号是“隐含”的

3.1.7. 基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表基地址寄存器（PTBR），存放页表在内存中的起始地址F 和页表长度M.
进程末执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中

请求分页管理方式

请求分页存储管理与基本分页存储管理的主要区别：

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然
后继续执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

请求页表新增增加 4 个字段：

状态位：是否已经调入内存
访问字段：记录最近访问过几次或者上次访问的时间，供置换算法使用
修改位：调入内存后是否被修改
外存地址：页面在外存中的存放位置

缺页中断机构

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然
后由操作系统的缺页中断处理程序处理中断。
此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
如果内存中没有空闲块，，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

缺页中断与当前指令有关，属于内中断

地址变换机构

新增步骤：

查到页表项判断是否调入内存
页面置换（需要调入页面，但没有空闲内存块）
需要修改请求页表中新增的表项

页面置换算法

最佳页面置换算法（Optimal Page Replacement Algorithm）：这种算法选择将来最不可能被访问的页面进行替换。由于它需要预知未来的页面访问请求，所以在实际的操作系统中无法实现，但它常被用作理论上的最优解。
最近最少使用页面置换算法（Least Recently Used, LRU）：这种算法选择最长时间没有被访问的页面进行替换。它的基本思想是，如果一个页面在最近一段时间内没有被访问，那么在将来它被访问的可能性也很小。
先进先出页面置换算法（First-In-First-Out, FIFO）：这种算法总是替换最早进入内存的页面。它的实现简单，但可能会导致较高的页面错误率。Belady 异常---当为进程分配的物理块数增大时，缺页次数不减反增。只有FIFO算法发生Belady异常, 实现简单，但不适应，算法性能差
时钟页面置换算法（Clock Page Replacement Algorithm）：这种算法是最近最少使用页面置换算法的一种近似实现。它维护一个循环队列，每次替换队列中的下一个页面，如果该页面最近被访问过，则跳过并清除其访问位，否则将其替换。
最不常用页面置换算法（Least Frequently Used, LFU）：这种算法选择访问频率最低的页面进行替换。它的基本思想是，如果一个页面的访问频率很低，那么在将来它被访问的可能性也很小

抖动（Thrashing） 或 颠簸（Bouncing） 是操作系统中的一种现象，它发生在内存资源过度分配的情况下。

当操作系统试图运行多于其内存容量允许的进程时，它需要频繁地在内存和硬盘之间交换页面，这就是所谓的页面调度（Page Swapping）。如果这种页面调度变得过于频繁，以至于操作系统花费了大部分时间来交换页面，而不是执行实际的进程，那么就会发生抖动。抖动的一个典型表现是，刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存。这种频繁的页面调度行为会导致系统的性能急剧下降，因为硬盘访问速度远低于内存访问速度。抖动是一个需要避免的现象，因为它会导致系统的响应时间变长，甚至可能导致系统崩溃。操作系统通常通过一些策略来避免抖动，例如改进页面置换算法，或者使用更智能的内存管理策略。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够)

第四部份：文件管理 & I/O设备管理

📃文件的属性

文件名（File Name）：在同一目录下不能有重名文件。
标识符（Identifier）：对用户无可读性，操作系统用于区分文件的内部名称。
类型（Type）：指明文件的类型。
位置（Location）：文件存放的路径（用户使用）、在外存中的地址（操作系统使用，用户不可见）。
大小（Size）：文件大小。
创建信息、上次修改时间、文件所有者信息（Creation Info, Last Modified Time, File Owner Info）：文件的元数据，包括创建日期、最后修改日期和文件所有者等信息。
保护信息（Protection Info）：对文件进行保护的访问控制信息。

文件如何存在外存

外存被分为 块/磁盘快/物理块, 以块为单位读取，即便一个文件远小于一个块大小，依然独自占一个块

操作系统向上提供的功能

创建文件 (create 系统调用)
删除文件 (delete 系统调用)
读文件 (read 系统调用)
写文件 (write 系统调用)
打开文件 (open 系统调用)
关闭文件 (close 系统调用)

文件控制块

文件控制块（File Control Block，FCB）是操作系统为管理文件而设置的一组具有固定格式的数据结构¹。它存放了为管理文件所需的所有有属性信息（文件属性或元数据）¹。

文件名（File Name）：文件的名称，用于用户识别和访问文件。
物理地址（Physical Address）：文件在存储设备上的位置，这通常对用户不可见，但对操作系统来说非常重要，因为它需要知道从哪里获取文件的内容。
逻辑结构（Logical Structure）：文件的组织方式，例如，它可能是一个文本文件、二进制文件、目录文件等。
物理结构（Physical Structure）：文件在磁盘上的实际布局，例如，它可能是连续的、链式的、索引的等。
存取控制信息（Access Control Information）：这些信息定义了哪些用户或进程可以访问文件，以及他们可以进行的操作（例如，读、写、执行等）。
使用信息（Usage Information）：这些信息包括文件的创建时间、最后修改时间、最后访问时间等。

当你创建一个新的文件或目录时，操作系统会在文件系统中创建一个新的FCB来存储这些信息 ² 。FCB的有序集合称为文件目录（File Directory），也就是我们常说的文件夹 ² 。一个FCB就是一个文件目录项（Directory Entry）²。

值得注意的是，一个文件目录也被视为一个文件，称为目录文件（Directory File）² 。这意味着目录文件本身也有一个FCB，其中包含了目录文件的所有属性信息 ²。

文件的物理结构

在很多操作系统中，**磁盘块（Disk Block）**的大小与内存块、页面的大小相同。
在**外存管理（External Storage Management）**中，文件的逻辑地址也被分为了一个一个
的文件块。逻辑地址形式为（逻辑块号，块内地址）。

连续分配（Contiguous Allocation）：每个文件在磁盘上占有一组连续的块。
转换时，只关心 逻辑块号<->物理块号（Logical Block Number <-> Physical Block Number）。验证逻辑块号是否小于物理块长度。物理块号 = 起始块号 + 逻辑块号。
优点： 支持顺序访问（Sequential Access）和直接访问（Direct Access）。读取某个磁盘块，需要移动磁块，连续分配文件在顺序读写的速度最快。
缺点： 物理上不方便对文件拓展（Physically Inconvenient for File Expansion）。空间利用率低，产生难以利用的磁盘碎片，可以通过紧凑解决。

DMA方式

DMA（Direct Memory Access，直接存储器访问）是一种硬件技术，它允许某些类型的硬件子系统（如磁盘驱动器、图形卡等）直接访问系统内存，而无需通过CPU进行中间处理。DMA的主要优点是它可以大大提高CPU的效率，因为CPU在DMA传输数据时可以执行其他任务¹ ² 。然而，DMA也有一些缺点，例如它可能会增加系统的复杂性，并且在某些情况下可能会引入数据一致性问题

数据传送单位是“块”
数据直接在设备与内存间传送，不需要CPU介入
仅在一个或多个数据块开始和结束时，才需要CPU介入

SPOOling技术

需要多道程序技术的支持

共享打印机原理：

独占式设备：只允许各进程串行使用
共享设备：允许多个进程“同时”使用的设备