操作系统

中山OS

复杂系统 多种内核架构 宏内核 微内核 外核 多内核 重要设计原则 策略与机制的分离

读写锁:

读-读共享: 只要没有人再写,多少个读者可以同时读取数据(不互斥) 读-写共享: 有人在写的时候,别人不能读; 有人在读的时候别人不能写 写-写互斥: 一个人在写的时候,别人也不能写

由于“读-读”是可以共享的，这就引发了一个问题：当读者和写者都在排队时，我们该让谁先上？这就是“读者优先”和“写者优先”的区别。

偏向读者:

只要还有读者在读，新来的读者就可以直接“插队”进去读，写者必须无限期等待。

致命缺点: 写者饿死 如果系统的读取操作非常频繁,读者络绎不绝,写者可能会永远等不到执行的机会,这种情况在操作系统中被称为饿死

偏向写者

一旦有写者在排队，就不允许新的读者再进入读取区了。

特点：保证数据实时性 写者不会被无限期拖延，只要写者发出了请求，现有的读者读完后，写者就能立刻执行。这保证了后续的读者能读到最新修改的数据。不过，这可能会导致读者的平均等待时间变长。

偏向写者:

一旦有写者在排队，就不允许新的读者再进入读取区了。

操作系统导论(部分笔记 一部分是纸质笔记)

第31章信号量

二值信号量

用信号量作为锁

读者写者锁

允许多个读者访问共享变量

如果某个变量要更新数据结构

rwlock_acquire_writelock() 获得写锁 rwlock_release_writelock() 释放锁 生产者-消费者问题(有界缓冲区问题)

生产者-消费者问题中的死锁

在生产者-消费者问题中，死锁通常发生在生产者和消费者之间相互等待对方释放资源，导致双方都无法继续执行。 消费者线程： 先获得了互斥锁（mutex）。 然后调用 sem_wait(&full)，发现 full 信号量为 0（没有数据可消费），于是阻塞。 但此时消费者仍然持有互斥锁（mutex）。 生产者线程： 尝试获取互斥锁（mutex），但由于消费者已经持有该锁，生产者被阻塞。 生产者无法继续执行，也就无法生产数据并唤醒消费者。

死锁的原因

消费者：持有互斥锁，等待 full 信号量。 生产者：等待互斥锁，无法生产数据。 循环等待：消费者等待生产者生产数据，生产者等待消费者释放互斥锁。 比喻：冰箱没有食物，消费者站在冰箱面前等待冰箱有食物，但是由于生产者 也就是厨师由于消费者也就是顾客把冰箱占着所以无法把食物放进冰箱中。二者互相等待形成死锁 解决方法打开冰箱前先检查一下厨房的计数器，如果计数器有食物，消费者再去打开冰箱，否则在外面 等待。相反同样的道理 为什么有效 避免交叉等待：消费者和生产者都不再因为持有冰箱门（互斥锁）而等待食物或空格子。他们先检查计数器（信号量），确认条件满足后再打开冰箱门。 减少锁的持有时间：冰箱门（互斥锁）只在取放食物时打开，时间很短，减少了锁的争用。 提高效率：生产者和消费者可以更高效地工作，因为他们不再因为锁而互相等待。

解决方案

1. 调整信号量的使用顺序 确保生产者和消费者在获取资源时的顺序一致，避免交叉等待。 2.使用条件变量 条件变量比信号量更灵活，可以避免死锁。通过条件变量，生产者和消费者可以更优雅地协调彼此的操作。
2. 使用高级并发库 如果你使用的是现代编程语言（如 Java 或 C++），可以利用内置的并发库来避免死锁。 4.减少锁的作用域 把获取和释放互斥量的操作调整为紧挨着临界区，把full，empty的唤醒和等待操作调整到锁的外面,结果得到了简单而有效的有界缓冲区

哲学家就餐问题

死锁每个哲学家都拿到了左手边的餐叉，他们每个都会阻塞住，并且一直等待另一个餐叉 解决方案:破除依赖 修改某个或者某些哲学家的取餐叉顺序

第32章常见的并发问题

关键问题:如何处理常见的并发缺陷

并发缺陷会有很多常见的模式。了解这些模式是写出健壮、正确程序的第一步。

非死锁缺陷

主要有两种:

违反原子性缺陷

正式的定义:违反了多次内厝访问中预期的可串行代码 解决方案:加锁

错误顺序

正式的定义:两个内存访问的预期顺序被打破 解决方案:通过强制顺序来修复这种缺陷——条件变量

死锁缺陷

关键问题：如何对付死锁

我们在实现系统时，如何避免 或者检测，恢复死锁呢？ 这是目前系统中的真实问题吗？

为什么发生死锁

原因一： 大型的代码库里，组件之间会有复杂的依赖 以操作系统为例：虚拟内存系统在需要访问文件系统才能从磁盘读到内存页；文件系统随后 又要和虚拟内存交互，去申请一页内存，以便存放读到的块。因此在设计大型的文件系统的锁机制时，必须要仔细地去避免循环依赖导致的死锁 原因二： 封装 软件开发者一直倾向于隐藏实现细节，以模块化的方式让软件开发更容易。然而模块化和锁不是 很 契合，某些看起来没有关系的接口可能会导致死锁

产生死锁的条件

互斥：线程对需要的资源 需要进行互斥访问 持有并等待：线程持有了资源，同时又在等待其他资源 非抢占：线程获得 的 资源，不能被抢占 循环等待：线程之间存在一个环路，环路上每个线程 都额外持有一个资源，而这个资源又是下一个线程 要申请的 上面4个条件的任何一个没有满足，死锁就不会产生

预防：

循环等待：

解决方案：全序或者偏序 提示：通过锁的地址来强制锁的顺序

持有并等待

解决方案：可以通过原子的抢锁来避免 不适合封装：因为这方案需要我们 准确地知道抢哪些锁

非抢占

活锁：两个线程有可能一直重复者一序列，又同时都抢锁失败。在这种情况下系统一直在运行这段代码，但是又不会有进展 解决方案： 可以在循环结束 的时候，先随机等待一个时间，然后再重复整个动作，这样可以降低线程之间的重复互相 干扰。 关于这个方案的最后一

互斥：

预防方法：完全避免互斥 设计各种无等待数据的结构思想？？？ 无等待同步？？？

通过调度避免死锁

银行家算法：略

检查和恢复

允许死锁偶尔发生,检查到死锁时再采取行动

不是所有值得做的事情都 值得做好

第33章基于事件的并发

关键问题：不用线程，如何构建并发服务器

事件循环： 处理事件的代码叫做事件处理程序，他是系统中发生的唯一活动，因此调度就是决定接下来处理哪个事件

重要API：select()或poll()

1. select() select() 是一种古老的多路复用机制，广泛用于各种操作系统（包括Unix、Linux和Windows）。 工作原理 select() 可以同时监视多个文件描述符集合，分别用于读、写和异常条件。它会阻塞当前线程，直到至少有一个文件描述符准备好，或者超时。 文件描述符集合：select() 使用三个文件描述符集合（fd_set）来分别表示可读、可写和异常条件的文件描述符。 超时机制：可以通过timeout参数设置一个超时时间，如果在超时时间内没有任何文件描述符准备好，则返回。 使用场景 select() 适用于文件描述符数量较少的场景。由于它需要遍历所有文件描述符集合来检查状态，因此在文件描述符数量较多时效率较低。
2. poll() poll() 是另一种多路复用机制，比select()更灵活，效率也更高，尤其是在文件描述符数量较多时。 工作原理 poll() 使用一个pollfd数组来监视文件描述符的状态。每个pollfd结构体包含一个文件描述符和两个标志：events（监视的事件类型）和revents（实际发生的事件）。 无固定限制：poll() 不受select()中文件描述符数量的限制（select()的最大文件描述符数量通常受FD_SETSIZE限制）。 动态数组：pollfd数组的大小可以根据需要动态调整。 使用场景 poll() 适用于文件描述符数量较多的场景，因为它不会像select()那样受到固定大小的限制。

为何更简单？无须锁

使用单个CPU和基于事件的应用程序，并发程序中发现的问题不再存在

请勿阻塞基于事件的 服务器

基于事件的服务器可以对任务调度进行细粒度的控制。但是，为了保持这种控制，不可以有阻止调 用者执行的调用。如果不遵守这个设计提示，将导致基于事件的服务器阻塞，客户心塞，并严重质疑你 是否读过本书的这部分内容。

一个问题：阻塞系统调用

但是，使用基于事件的方法时，没有其他线程可以运行：只是主事件循环。这意味着 如果一个事件处理程序发出一个阻塞的调用，整个服务器就会这样做：阻塞直到调用完成。 当事件循环阻塞时，系统处于闲置状态，因此是潜在的巨大资源浪费。因此，我们在基于 事件的系统中必须遵守一条规则：不允许阻塞调用

解决方案：异步I/O

允许程序在等待I/O操作完成时继续执行其他任务。与传统的同步I/O（Synchronous I/O）不同，异步I/O不会阻塞当前线程，从而提高了程序的效率和响应性。异步I/O广泛应用于高性能网络编程、嵌入式系统和现代编程框架中。

另一个问题：状态管理

第36章I/O设备

关键问题：如何将I/O集成进计算机系统中

I/O应该如何集成进系统中？ 其中的一般机制是什么？ 如何让它们变得更高效

系统架构

image.png

为什么用这样的分层架构？ 因为物理布局及造价成本。越快的总线越短，高性能的总线的造价非常高。略

标准设备

帮助理解设备交互机制 image.png

标准协议

一个设备接口包含3个寄存器： 状态寄存器：可以读取并查看设备的当前状态 命令寄存器：用于通知设备执行某个具体任务 数据寄存器：将数据 传给设备或从设备接受数据

关键问题：如何减少轮询开销

操作系统检查设备状态时如何避免频繁轮询，从而降低管理设备的CPU开销

利用中断减少CPU开销：

有了中断后，CPU 不再需要不断轮询设备，而是向设备发出一个请求，然后就可以让对应进 程睡眠，切换执行其他任务。当设备完成了自身操作，会抛出一个硬件中断，引发CPU跳 转执行操作系统预先定义好的中断服务例程（Interrupt Service Routine，ISR），或更为简单 的中断处理程序（interrupt handler）。 注意，使用中断并非总是最佳方案。假如有一个非常高性能的设备，它处理请求很快： 通常在CPU第一次轮询时就可以返回结果。此时如果使用中断，反而会使系统变慢：切换到其他进程，处理中断，再切换回之前的进程代价不小。

提示：中断并非总是比PIO好

1.如果设备非常快：采用轮询 2.如果设备比较慢：采用允许发生重叠的中断更好 3.如果设备的速度未知，或者时快时慢：考虑采用混合策略，先尝试轮询一小段时间，如果设备没 有完成操作，此时再使用中断 4.网络场景最好不要使用中断：网络端收到大量数据包，如果每一个包都发 生一次中断，那么有可能导致操作系统发生活锁（livelock），即不断处理中断而无法处理用 户层的请求。

另一个基于中断的优化就是合并。设备在抛出中断之前往往会等待一小段 时间，在此期间，其他请求可能很快完成，因此多次中断可以合并为一次中断抛出，从而 降低处理中断的代价。当然，等待太长会增加请求的延迟，这是系统中常见的折中

利用DMA进行更高效的数据传送

关键问题：如何减少PIO的开销 使用PIO 的方式，CPU 的时间会浪费在向设备传输数据或从设备传出数据的过程中。如何才能分 离这项工作，从而提高CPU的利用率？

解决方案：使用DMA

设备交互的方法：

硬件如何如与设备通信？是否需要一些明确的指令？或者其他的方式？ 1.明确的I/O指令（这些指令规定了操作系统将数据发 送到特定设备寄存器的方法，从而允许构造上文提到的协议） 2.内存映射

纳入操作系统：设备驱动程序

每个设备都有非常具体的接口，如何将它们纳入操作系统

关键问题：如何实现一个设备无关的操作系统

如何保持操作系统的大部分与设备无关，从而对操作系统的主要子系统隐藏设备交互的细节？ 方法：抽象 在最底层，操作系统的一部分软件清楚地知道设备如何工作，我们将这部分软件称为设备驱动程序，所有设备交互的细节都封装在其中 image.png

第37章磁盘驱动器

关键问题：如何存储和访问磁盘上的数据

现代磁盘如何存储数据？接口是什么？数据是如何安排和访问的？磁盘调度如何提高性能？

简单的磁盘驱动器：

单磁道延迟：旋转延迟

多磁道：寻道时间

1.寻道：首先是磁盘臂移动的加速阶段，然后是全速移动而惯性滑动，然后是随着磁盘臂减速而减速。最后，在磁盘小心地放置在正确地磁道时停下来。 2.传输：数据从表面读取或写入表面

首先寻道，然后等待转动延迟，最后传输

后写缓存： 数据放入其内存之后回报写入完成 直写缓存： 实际写入磁盘之后，回报写入完成

I/O数学

image.png

image.png

计算平均寻道时间

image.png

提示：顺序地使用磁盘

磁盘调度

1.SSTF:最短寻道时间优先

SSTF按磁道对I/O请求队列排序，选择 在最近地磁道上地请求先完成 产生问题：主机操作系统无法利用驱动器地几何结构，而是只会看到一系列地块 第二个 问题会产生饥饿

2.电梯（SCAN或C-SCAN）

SCAN，简单地以跨越磁道的顺序来服务磁盘请求。我们将一次跨越磁盘称为 扫一遍。因此，如果请求的块所属的磁道在这次扫一遍中已经服务过了，它就不会立即处 理，而是排队等待下次扫一遍。

F-SCAN， 它在扫一遍时冻结队列以进行维护

C-SCAN 是另一种常见的变体，即循环SCAN（Circular SCAN）的缩写。不是在一个 方向扫过磁盘，该算法从外圈扫到内圈，然后从内圈扫到外圈，如此下去 长得很像电梯 并没有严格遵守 SJF的原则。具体来说他们忽视了旋转

关键问题：如何计算磁盘旋转开销

如何同时考虑寻道和旋转，实现更接近SJF的算法

第38章：廉价冗余磁盘阵列(RAID)

第44章数据完整性和保护

关键问题：如何确保数据完整性

磁盘故障模式

两种类型的单块故障：

潜在扇区错误（LSE）

当磁盘扇区（或扇区组）以某种方式讹误时，会出现 LSE 例如：磁头碰撞或宇宙射线—-磁盘内纠错码确定块中的磁盘位是否完好在某些情况下，修复它们。如果它们不好，并且驱动器没有足够的信息来修复错误，则在 发出请求读取它们时，磁盘会返回错误。

块讹误

磁盘块出现讹误（corrupt），但磁盘本身无法检测到 有缺陷的磁盘固件可能会将块写入错误的位置 一个块通过有故障的总线 从主机传输到磁盘时，它可能会讹误。 无声的故障（silent fault）。返回故障数据时， 磁盘没有报告问题。
image.png

处理潜在的扇区错误

存储系统应该就用 它具有的任何冗余机制，来返回正确的数据 当全盘故障和LSE接连发生时：增加了额外的冗余度

检测讹误：校验和

校验和：校验和就是一 410 第44章 数据完整性和保护 个函数的结果，该函数以一块数据（例如4KB块）作为输入，并计算这段数据的函数，产 生数据内容的小概要（比如4字节或8字节）。此摘要称为校验和 校验和函数： 异或（XOR）函数 如果每个校验和单元内相同位置的两 个位发生变化，则校验和将不会检测到讹误

加法函数 但如果数据被 移位，则不好

为Fletcher校验和 s1 = s1 + di mod 255 s2 = s2 + s1 mod 255

循环冗余校验（CRC） 所做的只是将D视为一个大的二进制数（毕竟它只 是一串位）并将其除以约定的值（k）。该除法的其余部分是CRC的值

两个具有不相同的数据块可能具有相同的校验和，这被称为碰撞 image.png

使用校验和： 略 发现讹误：如果存储系统有冗余副本就尝试使用它，如果没有，则可能的答案是返回错误

问题：错误的写入：

正确地将数据写入磁盘，但位置错误 解决方案： 添加物理标识符：包括磁盘号和扇区偏移量

问题：丢失的写入：

当设备通知上层写入已完成，但事实上它从未持有。因此磁盘上留下的是该块的旧内容 解决方案： 方法一：执行写入验证或写入后读取。 方法二：在系统的其他位置添加校验和，以检测丢失的写入.

擦净：

通过 定期读取系统的每个块，并检查校验和是否仍然有效，磁盘系统可以减少某个数据项的所 有副本都被破坏的可能性。典型的系统每晚或每周安排扫描。

校验和的开销