Operation System

[tomoya06]

什么是操作系统

0. 本质是一个运行在计算机上的软件程序
1. 是计算机的基石，是管理计算机硬件与资源的程序，屏蔽了硬件层的复杂性
2. 核心部分是内核(Kernel)，基本功能：负责系统的内存管理、设备管理、文件管理、进程管理

• 并发：宏观上在一段时间内能同时运行多个程序；通过引入进程和线程，使得程序能够并发运行
• 并行：并行则指同一时刻能运行多个指令；需要硬件支持，如多流水线、多核处理器或者分布式计算系统。

操作系统基本特征：

1. 并发、
2. 共享：共享是指系统中的资源可以被多个并发进程共同使用。分为互斥共享和同时共享
3. 虚拟：把一个物理实体转换为多个逻辑实体。
   • 有两种虚拟技术：时（时间）分复用技术，如CPU并发执行多个进程；和空（空间）分复用技术，如虚拟内存。
4. 异步：指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

什么是系统调用

前言

进程运行级别分为：

1. 用户态(user mode) : 用户态运行的进程或可以直接读取用户程序的数据。
2. 系统态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

系统调用

指的是指运行在用户空间（用户态）的程序、向操作系统内核、请求需要更高权限运行的服务。

系统调用分类：

设备管理；文件管理；进程控制；进程通信；内存管理；安全管理

[tomoya06]

进程和线程

进程是资源分配的最小单位，线程是CPU调度的最小单位

进程

• 定义：进程（英语：process），是指计算机中已运行的程序。进程曾经是分时系统的基本运作单位。如今，进程本身不是基本运行单位，而是线程的容器。

1. 进程是资源分配的基本单位。
2. 执行开销大，系统要分配或回收资源
3. 进程通信要IPC(进程间通信)

进程控制块 (Process Control Block, PCB)

系统为每个进程定义的一个数据结构，来描述进程的基本信息和运行状态。进程的整个生命周期变化实质上就是系统对PCB的操作。

进程控制块存储的信息：

• 进程标识符
• 处理机状态，处理机被中断时存储的信息，以便进程重新执行时可以从断点继续执行
• 进程调度信息，包括进程状态、优先级、调度所需的其他信息（如等待CPU的时间、进程已执行时间等）、阻塞原因
• 进程控制信息，包括程序和数据的地址、进程同步和通信机制、已分配到的资源清单、下一个进程的PCB的首地址

线程

• 定义：线程（英语：thread）是操作系统能够进行运算调度的最小单位。大部分情况下，它被包含在进程之中，是进程中的实际运作单位。

1. 一个进程中可以有多个线程，它们共享进程资源。
2. 执行开销小，但不利于资源的管理和保护
3. 可以直接读写同一进程中的数据进行通信

关系

进程是计算机管理运行程序的一种方式，一个进程下可包含一个或者多个线程。线程可以理解为子进程。

进程状态

创建 -> 就绪 <-> 运行 ~ 阻塞 - 结束

• 只有就绪态和运行态可以相互转换，其它的都是单向转换。
• 就绪态和运行态的转换原因是CPU时间的调度：就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。

进程通信(Inter-Process Communication, IPC)：进程间通信咯

进程通信方式：

1. 管道aka匿名管道： 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。只存在于内存中的文件。pipe()
2. 有名管道：可以实现本机任意两个进程通信。遵循FIFO。存在于磁盘文件。mkfifo()
3. 消息队列：提供了有格式的数据，能传递更多的信息；异步读写，可以实现消息的随机查询。
4. 信号量：是一个计数器，用于为多个进程提供对共享数据对象的访问。
5. 共享存储：使得多个进程可以访问同一块内存空间，需要依靠某种同步操作，如互斥锁和信号量等。是最快的IPC。
6. 套接字：可用于不同机器间的进程通信。

进程同步： 控制多个进程按一定顺序执行

• 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
• 互斥：多个进程在同一时刻只有一个进程能进入临界区。
• 临界资源：互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。
• 临界区：对临界资源进行访问的那段代码称为临界区。

进程同步方式：

1. 互斥量：只有拥有互斥对象的进程才能访问资源
2. 信号量：允许多个进程同时访问同一资源，但会限制最大进程数量

进程调度

1. 先到先服务 first-come first-service / FCFS
2. 短作业优先 shortest job first / SJF
3. 最短剩余时间优先 shortest remaining time next / SRTN不：比SJF多了时间片控制
4. 时间片轮转
5. 优先级调度
6. 多级反馈队列调度算法：目前最好。
   • 多条队列，从Q1-QN优先级从高到低，时间片从短到长；新作业先进入Q1，一个时间片后未完成则推入Q2；Q1没有作业在等待时再调度Q2；每个队列按FCFS调度，QN按时间片轮转调度；如果低优先级正在执行时、新作业到来，低优先级作业推到所在队列尾部，执行Q1

[tomoya06]

死锁

出现死锁的必要条件

1. 互斥：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由 一个进程占用。
2. 请求和保持：已经得到了某个资源的进程可以再请求新的资源。
3. 不剥夺：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
4. 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

死锁的处理方式

0. 鸵鸟策略：直接不理它。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。（草）
1. 死锁预防：破坏四个条件之一来预防发生死锁
2. 死锁避免：在资源分配过程中防止系统进入不安全状态
3. 死锁检测：允许系统发生死锁，通过设置检测机构来及时检测出死锁的发生，然后将发生死锁的进程和资源处理掉
4. 死锁解除：与死锁检测配套。常用的方法是撤销或者挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态。但，死锁检测+死锁接触实现难度大。

死锁预防

1. 条件1是设备的固有特性，必须保证，不能预防。
2. 摒弃“请求和保持”条件：系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源（摒弃了请求条件）；只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待（摒弃了保持条件）。
3. 摒弃“不剥夺”条件：当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。可以理解为资源被剥夺。
4. 摒弃“环路等待”条件：对所有资源按顺序编号，所有进程对资源的请求 必须严格按照资源序号递增的次序提出，因此不可能出现环路。

死锁避免

系统安全状态vs不安全状态：

所谓安全状态，是指系统能按某种进程顺序P1-P2-...-PN aka安全序列，来为每个进程 Pi 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

eg. from 计算机操作系统第三版

死锁检测+死锁解除

1. 资源分配图

可以用来描述系统死锁。

2. 死锁解除

• 剥夺资源
• 撤销进程

乐观锁 vs 悲观锁

定义

乐观锁：在操作数据时非常乐观，认为别人不会同时修改数据。因此乐观锁不会上锁，只是在执行更新的时候判断一下在此期间别人是否修改了数据，如果别人修改了数据则放弃操作，否则执行操作。

悲观锁：在操作数据时比较悲观，认为别人会同时修改数据。因此操作数据时直接把数据锁住，直到操作完成后才会释放锁；上锁期间其他人不能修改数据。

实现方式

乐观锁和悲观锁是两种思想，它们的使用是非常广泛的，不局限于某种编程语言或数据库。

乐观锁：Compare And Swap aka. CAS；版本号机制

[tomoya06]

内存管理

负责内存的分配和回收

存储器的层次结构

其中主存储器简称内存或主存；寄存器访问速度最快，但容量很小；告诉缓存比寄存器大，访问速度比主存储器/内存快

内存管理机制

分类： 连续分配管理方式+非连续分配管理方式

1. 分页管理：主存分为大小相等且固定的一页一页的形式；页式管理通过页表对应逻辑地址和物理地址。
2. 分段管理：每段长度可以动态增长，一个段构成一个独立的地址空间，段有自己一组完整意义的信息，比如程序段、数据段等
3. 段页式：先分段，每段再分页

分页vs分段：

1. 页是信息的物理单位，是系统所需；段是信息的逻辑单位，是用户所需
   • ps：出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
2. 页的大小由系统决定；段的大小由用户编写的程序决定，由编译程序根据信息的性质来划分：通常，程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中，并且每个程序可以有多个相同类型的段。

寻址

逻辑地址vs物理地址

逻辑地址：程序可以读取的地址，表现为存储在内存中的一个数值 物理地址：内存单元在物理内存中的真实地址

页表

1. 页表：页面映像表，记录页号-内存物理块号的映射；所以CPU存取数据时都要访问两次内存：先读页表再读实际物理地址；页表是需要一直驻留在物理内存中的（多级页表除外）。
2. 分页地址结构=页号P+位移量W(aka页内地址)；实际逻辑地址A=P x 页面大小L + W
3. 快表：用一个高速缓冲存储器，来缓存访问过的部分页表；CPU存取数据时，先访问高速缓存，若有缓存，只需再读主存；没有缓存则多访问一次页表再读主存，并在缓存中记录这条页表项
4. 多级页表：引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中
5. 段表：类似页表，记录段号-段长+基址的映射；每一个程序设置一个段表，放在内存，属于进程的现场信息

页面置换算法

缺页中断：要访问的页不在主存，需要操作系统将其调入主存后再进行访问。 在这个时候，被内存映射的文件实际上成了一个分页交换文件。

页面置换：当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。用来选择淘汰哪一页的规则叫做页面置换算法。

带图的置换流程说明参考这里

1. 最佳(OPT, Optimal replacement algorithm)：所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

2. 最近最久未使用(LRU, Least Recently Used)

3. 最近未使用(NRU, Not Recently Used)：与LRU类似

4. 先进先出(FIFO, First In First Out)

5. 时钟算法(Clock)

[tomoya06]

虚拟内存

什么是虚拟内存

虚拟内存 使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

为什么要虚拟内存

1. 虚拟内存的重要意义是它定义了一个连续的虚拟地址空间，降低编程难度
2. 虚拟内存把内存扩展到硬盘空间，
3. 保护每个进程的地址空间不会被其他进程破坏

CPU寻址

最简单的寻址方式物理寻址，也就是直接使用物理地址；

现代CPU使用的方式是虚拟寻址，CPU需要将虚拟地址翻译成物理地址，

如何虚拟寻址：CPU中有一个内存管理单元(Memory Management Unit, MMU)的硬件，负责管理虚拟地址和物理地址的转换，页表就保存在MMU上。

局部性原理

虚拟内存、CPU高速缓存、以及其他缓存技术，都依赖于局部性原理。

程序的局部性原理是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。

局部性原理又表现为：时间局部性和空间局部性。

1. 时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。
2. 空间局部性是指一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。

从程序编写的角度，想要编写出性能高效的程序，首先要保证程序的时间局部性与空间局部性。

[tomoya06]

TODO：内存管理：栈+堆

[tomoya06]

设备管理

参考CS-Notes设备管理-磁盘调度

[tomoya06]

IO模型

本段手动fork自CS-Notes Socket一节

一、I/O 模型

一个输入操作通常包括两个阶段：

• 等待数据准备好
• 从内核向进程复制数据

对于一个套接字上的输入操作，第一步通常涉及等待数据从网络中到达。当所等待数据到达时，它被复制到内核中的某个缓冲区。第二步就是把数据从内核缓冲区复制到应用进程缓冲区。

Unix 有五种 I/O 模型：

• 阻塞式 I/O
• 非阻塞式 I/O
• I/O 复用（select 和 poll）
• 信号驱动式 I/O（SIGIO）
• 异步 I/O（AIO）

阻塞式 I/O

应用进程被阻塞，直到数据从内核缓冲区复制到应用进程缓冲区中才返回。

应该注意到，在阻塞的过程中，其它应用进程还可以执行，因此阻塞不意味着整个操作系统都被阻塞。因为其它应用进程还可以执行，所以不消耗 CPU 时间，这种模型的 CPU 利用率会比较高。

非阻塞式 I/O

应用进程执行系统调用之后，内核返回一个错误码。应用进程可以继续执行，但是需要不断的执行系统调用来获知 I/O 是否完成，这种方式称为轮询（polling）。

由于 CPU 要处理更多的系统调用，因此这种模型的 CPU 利用率比较低。

I/O 复用

使用 select 或者 poll 等待数据，并且可以等待多个套接字中的任何一个变为可读。这一过程会被阻塞，当某一个套接字可读时返回，之后再把数据从内核复制到进程中。

它可以让单个进程具有处理多个 I/O 事件的能力。又被称为 Event Driven I/O，即事件驱动 I/O。

如果一个 Web 服务器没有 I/O 复用，那么每一个 Socket 连接都需要创建一个线程去处理。如果同时有几万个连接，那么就需要创建相同数量的线程。相比于多进程和多线程技术，I/O 复用不需要进程线程创建和切换的开销，系统开销更小。

信号驱动 I/O

应用进程使用 sigaction 系统调用，内核立即返回，应用进程可以继续执行，也就是说等待数据阶段应用进程是非阻塞的。内核在数据到达时向应用进程发送 SIGIO 信号，应用进程收到之后在信号处理程序中调用 recvfrom 将数据从内核复制到应用进程中。

相比于非阻塞式 I/O 的轮询方式，信号驱动 I/O 的 CPU 利用率更高。

异步 I/O

应用进程执行 aio_read 系统调用会立即返回，应用进程可以继续执行，不会被阻塞，内核会在所有操作完成之后向应用进程发送信号。

异步 I/O 与信号驱动 I/O 的区别在于，异步 I/O 的信号是通知应用进程 I/O 完成，而信号驱动 I/O 的信号是通知应用进程可以开始 I/O。

五大 I/O 模型比较

• 同步 I/O：将数据从内核缓冲区复制到应用进程缓冲区的阶段（第二阶段），应用进程会阻塞。
• 异步 I/O：第二阶段应用进程不会阻塞。

同步 I/O 包括阻塞式 I/O、非阻塞式 I/O、I/O 复用和信号驱动 I/O ，它们的主要区别在第一个阶段。

非阻塞式 I/O 、信号驱动 I/O 和异步 I/O 在第一阶段不会阻塞。

二、I/O 复用

本节完整解析参考这篇博客

select/poll/epoll都是IO复用的方法，实现的方式不同

• select缺点：
  1. 连接数受限1024
  2. 需要轮询所有监听的fd，有数据的就处理，没有的跳过
  3. 每次处理时，fd集合都要从用户态拷贝到内核态
• poll：解决了select缺点1
• epoll特点：
  1. 连接数不受限
  2. 只处理就绪的fd，本质是事件驱动

epoll工作状态：参考这里

1. LT(Level Trigger)：只要fd有数据可读，就会通知
2. ET(Edge Trigger)：只在fd状态发生变化时通知

懒人比较：select/poll处理时间复杂度均为O(N)，且select的连接数受限1024；poll/epoll连接数不受限，epoll处理时间复杂度O(1)