操作系统

记录不完全操作系统相关内容

计算机组成

硬件由运算器、控制器、存储器、输入设备和输出设备组成，运算器和控制器集成在一起统称为中央处理器（CPU）。计算机各部件通过总线连接形成有机整体，总线有三种：地址总线、控制总线和数据总线。

运算器的主要功能是：完成算术运算和逻辑运算；
控制器的功能是：协调指挥计算机各部件工作；
存储器的主要作用是：存储程序和数据，实现记忆的功能；
输入设备的功能是：输入数据并转换为机内信息存储；
输出设备的作用是：将机内信息转换为便于识别、处理和使用的字符、图形，并输出显示。

进程和线程

进程

所有运行在Linux操作系统的进程都被task_struct这个结构体管理，task_struct也被称为进程描述符。进程描述符包含一个进程运行所需的所有信息，比如进程的识别、进程的属性以及构建进程的资源。

linux系统中，系统复制一个现有的进程来创建一个全新的进程。调用fork的进程成为父进程，新产生的进程成为子进程。调用fork结束后，父进程恢复执行，子进程开始执行，fork系统调用从内核返回两次，一次回到父进程，另一次回到子进程。创建新的进程都是为了立即执行新的、不同的程序，接着调用exec*族函数，创建新的地址空间，并把新的程序载入。程序通过exit系统调用退出执行。终结进程并将其占用的资源释放。wait4()查看子进程是否终结。进程退出执行后被设置为僵死状态，直到父进程调用wait()或waitpid()为止。

进程状态

TASK_RUNNING

在这个状态中，进程正在CPU中执行，或者在运行队列（run queue）中等待运行。

TASK_STOPPED

进程由于特定的信号（如SIGINT、SIGSTOP）而挂起就会处于这个状态，等待恢复信号，比如SINCONT。

TASK_INTERRUPTIBLE

在此状态中，进程挂起并且等待一个特定的条件。假如进程处于TASK_INTERRUPTIBLE状态并且收到一个停止信号，进程状态会发生改变，操作会中断。TASK_INTERRUPTIBLE的典型例子是等待键盘中断。

TASK_UNINTERRUPTIBLE

类似于TASK_INTERRUPTIBLE。当进程处于TASK_INTERRUPTIBLE 状态可以被中断，发送一个信号给TASK_UNINTERRUPTIBLE却不会有任何反应。TASK_UNINTERRUPTIBLE最典型的例子是进程等待磁盘I/O操作。

TASK_ZOMBIE

进程在使用exit()系统调用退出以后，父进程应该知道进程终结。在TASK_ZOMBIE状态中，进程在等待父进程收到通知并释放所有的数据结构

进程的调度策略

SCHED_OTHER 分时调度策略
SCHED_FIFO实时调度策略，先到先服务，按照进程的先后顺序调度
SCHED_RR实时调度策略，时间片轮转

进程的通信方式

无名管道：是一种半双工的通信方式，数据只能单向流动，亲缘进程之间
有名管道：是半双工的通信方式，可用非亲缘进程
信号量：是一个计数器，可控制多个进程对共享资源的访问。常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。
信号：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生
消息队列：是由消息的链表，存放在内核中并由消息队列标识符标识。
共享内存：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式。
套接字( socket )：可用于不同机器间通信

进程优先级和nice级别

进程优先级由动态优先级和静态优先级决定，它是决定进程在CPU中执行顺序的数字。优先级越高的进程被处理器执行的机会越大。根据进程的行为，内核使用启发式算法决定开启或关闭动态优先级。可以通过nice级别直接修改进程的静态优先级，拥有越高静态优先级的进程会获得更长的时间片（时间片是进程在处理器中的执行时间）。

Linux支持的nice级别从19（最低优先级）到-20（最高优先级），默认只是0。只有root身份的用户才能把进程的nice级别调整为负数（让其具备较高优先级）。

线程

线程是进程中活动的对象，每个线程都有一个独立的程序计数器，进程栈和一组进程寄存器。线程是单个进程中生成的执行单元。多个线程在同一个进程中并发运行。它们共享内存、地址空间、打开文件等等资源。还能访问同样的应用数据集。线程也被称为轻量级进程（Light Weight Process）。由于线程间共享资源，线程不能同时改变它们共享的资源。互斥、锁、序列化等等都是由用户应用程序来实现。

内核调度的对象是线程，不是进程。线程是进程中执行运算的最小单位，一个标准的线程由线程ID，当前指令指针(PC），寄存器集合和堆栈组成。线程相关的执行状态和存储变量放在线程控制表内，一个进程可以有多个线程，有多个线程控制表及堆栈寄存器，共享一个用户地址空间。

线程的通信方式

锁机制：包括互斥锁、条件变量、读写锁。互斥锁提供了以排他方式防止数据结构被并发修改的方法。读写锁允许多个线程同时读共享数据，而对写操作是互斥的。条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。
信号量机制：包括无名线程信号量和命名线程信号量。
信号机制：类似进程间的信号处理。

线程的状态：运行状态、就绪状态、阻塞状态、终止状态

CPU

CPU多核协同工作原理

多核CPU，单片芯片内集成多个处理器核心，每个核心独立的处理器单元，内部可以有多个处理器线程。

体系架构

多线程处理器，减少cache不命中和执行时间长的指令对处理器效率的影响，在单个处理器内部实现多个硬件线程。当某个线程处理 cache不命中时，其他线程可以以继续执行有效工作，从而隐藏访存延迟，提高综合性能。多线程处理器的优点在于由于能够快速切换线程上下文，因此多线程处理器能在每个时钟周期发射一个独立线程的指令。
同时多线程处理器SMT，在一个时钟周期内发送多个线程的指令到功能部件上执行，结合了超标量和多线程处理器的特点。
单片多处理器结构CMP，将大规模并行处理器中的SMP（对称多处理器）集成到同一芯片内，各个处理器并行执行不同的进程。片上多处理器系统允许线程在多个处理器核上并行执行，它利用线程级并行性来提高系统性能。
多核多线程处理器，是一个片上有多个处理器，同时每个处理器内部支持多个线程，所以说是单片多处理器和多线程的结合体。

访问内存模型

UMA（均匀存储访问）模型

节点访问任意存储单元的时间相同；
发生访存竞争时，仲裁策略平等对待每个节点；
外围I/O设备也可以共享；每个节点平等访问。

NUMA（非均匀存储访问）模型

节点访问内存模块的速度不同；
发生访存竞争时，仲裁策略对节点可能是不等价的；
外围I/O设备也可以共享，但对各节点是不等价的。

多核工作原理

核心独立运行指令，共享内存；
Cache/TLB一致性，通过核间通信保持各核访问缓存数据正确，核间通信一种是基于总线共享的Cache结构，每个CPU内核拥有共享的二级或三级Cache，通过连接核心的总线进行通信。一种是基于片上的互连结构，通过交叉开关或片上网络等方式连接，通过消息通信。
中断控制，通过APIC控制中断信号的处理位置；每个核带有独立的APIC单元，可通过中断互相通信；中断绑定，把某些中断绑定到指定核,，降低其他核的中断和上下文切换数, 提高效率。
虚拟化技术，每个进程都拥有自己的虚拟CPU，分时共享。

CPU调度算法

先到先服务调度FCFS（first-come,first-served），非抢占式，当一个进程进入到就需队列，其pcb就被链接到队列的尾部，当CPU空闲时，CPU被分配给位于队列头的进程。接着，该运行进程从队列中被删除。
最短作业优先调度SJF（shortest-job-first），抢占式或非抢占式，当CPU为可用时，它会赋给具有最短后续CPU区间的进程。如果两个进程具有同样长度的CPU区间，那么可以使用FCFS调度来处理。新进程与当前运行进程所产生的CPU区间相比，可能有一个更短的下一个CPU区间。可抢占SJF算法可能会抢占当前运行进程，而非抢占SJF算法会允许当前运行进程完成其CPU区间。可抢占SJF调度有时称为最短剩余时间优先调度。
优先权调度，每个进程都有一个优先权与其关联，具有最高优先权的进程会被分配到CPU。具有相同优先权的进程按FCFS顺序调度。
轮转法（round-robin,RR）调度算法，专门为分时系统设计的。定义一个小时间单元，称为时间量或时间片。就绪队列作为循环队列处理。CPU调度程序循环就需队列，为每个进程分配不超过一个时间片间隔的CPU。
多级队列调度（multilevel queue-scheduling algorithm），混合式，把就绪队列划分成几个单独的队列，一般根据进程的某些特性如内存大小和进程类型，永久性地把各个进程分别链入其中某一个队列中，每个队列都有自己的调度算法，进程并不在队列之间移动。
多级反馈队列调度，混合式，能使高优先级的作业得到响应又能使短作业（进程）迅速完成，允许进程在各队列间移动一个进程要使用很长的CPU 时间，则应把它移至较低级的队列中，这种方式把I/O 繁忙型和交互式进程放在较高优先级的队列中，同样在低优先级队列中长时间等待的进程可以移到较高优先级队列中。

多级反馈队列调度

进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。在多级反馈队列中，后进的作业不一定慢完成。

多核调度

系统为每个处理器都维护一个单独的就绪队列；
任务的调度是基于优先级调度的，每个处理器上的任务分优先级，每个就绪任务的优先级通过散列函数直接映射到处理器的位图数据结构上，通过位图的find-first-bit可以找到优先级最高的执行；
负载均衡，一个core的任务结束，转而处理其他最忙core上的任务；若所有core都有任务，则每200ms检查是否均衡。

缓存策略

多级CPU缓存，cpu在寄存器中计算数据，而数据存储在内存中，由于cpu和内存之间的性能逐渐增大，系统设计者在cpu和内存之间插入了3层的高速缓存。存储器层次结构的主要思想是一层上的存储器作为低一层存储器的高速缓存。

L1d是一级数据缓存，L1i是一级指令缓存

高速缓存的读，先从高层读数据，如果缓存命中了就返回数据。如果不命中就去低层读，如果从低层命中，返回数据的同时将低层的数据写入高层。
高速缓存的写，先直接向高层写入数据，向低层写入有两种方式，一种是直写（write-through），就是立即向低层写入。另一种是写回（write-back），等到算法淘汰的时候再向底层写入。

多处理器的计算机，每个CPU都有自己的寄存器和缓存。那么一个多线程的程序就会出现这个问题，线程A更改了缓存A中的数据，但是缓存B中的数据还是原来的数据，那么线程B去缓存B中读取的数据就是错误的数据。这个就是缓存一致性的问题。

缓存一致性策略，当有多个处理器(或核心、超线程)访问同一块内存时，必须确保它们在任何时候看到的都是相同的内容。

MESI协议，支持写回策略的缓存一致性协议，CPU中每个缓存行使用4种状态进行标记。

M: 被修改（Modified)，只被缓存在该CPU的缓存中，并且是被修改过的，该缓存行中的内存需要在未来写回（write back）主存，写回后变为E状态；
E: 独享的（Exclusive)，只被缓存在该CPU的缓存中，它是未被修改过的，与主存中数据一致，当有其它CPU读取该内存时变成共享状态，当CPU修改缓存行中内容时，该状态可以变成Modified状态；
S:共享的（Shared)，该缓存行可能被多个CPU缓存，并且各个缓存中的数据与主存数据一致；当有一个CPU修改该缓存行中，其它CPU中该缓存行可以被作废，变成无效状态（Invalid）；
I: 无效的（Invalid），该缓存是无效的。

缓存淘汰策略，常见的淘汰策略主要有FIFO、LRU、LFU和Random。

内存

内存管理功能

内存空间的分配与回收
地址转换，把逻辑地址转换成相应的物理地址
内存空间的扩充，利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存
存储保护，保证各道作业在各自的存储空间内运行，互不干扰

内存连续分配管理方式

是指为一个用户程序分配一个连续的内存空间

单一连续分配，每次只允许一个程序，独占内存；
固定分区分配，可分配的内存空间分割为若干个连续区域（分区），大小可以相同可以不同，分区只能装载一个进程；
动态分区分配，根据进程需求，把可分配的内存空间分割出一个分区分配给进程，分区的大小和数目是可变的。

内存非连续分配管理方式

一个程序分散地装入到不相邻的内存分区中

1、分页式，进程会被固定单位的空间划分成块，一个块称之为页，内存也被这个单位划分成块，一个块称之为页框，外存也以同样单位划分成块，称之为块。进程在执行时需要申请主存空间，也就是为每个页面分配主存中可用的页框，每个进程建立一张页表，记录页面在内存中对应的物理块号。

页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存：一次是访问页表，确定所存取的数据或指令的物理地址，第二次才根据该地址存取数据或指令。使用TLB，用来存放当前访问的若干页表项（块表），以加速地址变换的过程。主存中则相对称为慢表。

快表的有效性是基于著名的局部性原理

CPU给出逻辑地址后，由硬件进行地址转换并将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
如果找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样，存取数据仅一次访存便可实现。
如果没有找到，则需要访问主存中的页表，在读出页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换

TLB（Translation Lookaside Buffer）传输后备缓冲器是一个内存管理单元用于改进虚拟地址到物理地址转换速度的缓存。TLB是一个小的，虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。如果没有TLB，则每次取数据都需要两次访问内存，即查页表获得物理地址和取数据。用于虚拟地址与实地址之间的交互，提供一个寻找实地址的缓存区，能够有效减少寻找物理地址所消耗时间。页表缓冲；里面存放的是一些页表文件（虚拟地址到物理地址的转换表）。

在X86体系的CPU里边，一般都设有如下4组TLB:

第一组：缓存一般页表（4K字节页面）的指令页表缓存（Instruction-TLB）；
第二组：缓存一般页表（4K字节页面）的数据页表缓存（Data-TLB）；
第三组：缓存大尺寸页表（2M/4M字节页面）的指令页表缓存（Instruction-TLB）；
第四组：缓存大尺寸页表（2M/4M字节页面）的数据页表缓存（Data-TLB）。

2、分段式，段式管理方式按照用户进程中的自然段划分逻辑空间，如一用户进程由主程序，两个子程序，桟和一段数据组成，可以分为5段，每段从0开始编址，并分配一段连续连续地址空间（段内要求连续，段间不要求连续）。每个进程都有一张逻辑空间与内存映射的段表。

3、段页式，地址空间首先被分成若干个逻辑段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页

虚拟内存管理

时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。

按需分页（demand paging），通过内存地址虚拟化，可以使得软件在没有访问某虚拟内存地址时不分配具体的物理内存，而只有在实际访问某虚拟内存地址时，操作系统再动态地分配物理内存，建立虚拟内存到物理内存的页映射关系，这种技术属于lazy load技术。
页换入换出（page swap in/out），把不经常访问的数据所占的内存空间临时写到硬盘上，这样可以腾出更多的空闲内存空间给经常访问的数据；当CPU访问到不经常访问的数据时，再把这些数据从硬盘读入到内存中。页面置换算法，先进先出，LRU置换。在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞，调页完成时唤醒，如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项，若此时内存中没有空闲块，则要淘汰某页。
写时复制（Copy On Write，简称COW），两个虚拟页的数据内容相同时，可只分配一个物理页框，这样如果对两个虚拟页的访问方式是只读方式，这这两个虚拟页可共享页框，节省内存空间；如果CPU对其中之一的虚拟页进行写操作，则这两个虚拟页的数据内容会不同，需要分配一个新的物理页框，并将物理页框标记为可写，这样两个虚拟页面将映射到不同的物理页帧，确保整个内存空间的正确访问。

硬盘

磁盘IO性能

单个IO的大小(IO Chunk Size)
IOPS (Input/Output Per Second)即每秒的输入输出量，指单位时间内系统能处理的I/O请求数量
磁盘的吞吐量，也就是每秒磁盘 I/O 的流量，即磁盘写入加上读出的数据的大小。每秒 I/O 吞吐量＝ IOPS* 平均 I/O SIZE。

IO操作步骤

当控制器对磁盘发出一个IO操作命令的时候，磁盘的驱动臂(Actuator Arm)带读写磁头(Head)离开着陆区(Landing Zone，位于内圈没有数据的区域)，移动到要操作的初始数据块所在的磁道(Track)的正上方，这个过程被称为寻址(Seeking)，对应消耗的时间被称为寻址时间(Seek Time)；
但是找到对应磁道还不能马上读取数据，这时候磁头要等到磁盘盘片(Platter)旋转到初始数据块所在的扇区(Sector)落在读写磁头正上方的之后才能开始读取数据，在这个等待盘片旋转到可操作扇区的过程中消耗的时间称为旋转延时(Rotational Delay)；
接下来就随着盘片的旋转，磁头不断的读/写相应的数据块，直到完成这次IO所需要操作的全部数据，这个过程称为数据传送(Data Transfer)，对应的时间称为传送时间(Transfer Time)。

IOPS计算公式

寻址时间，驱动臂带读写磁头移动到要操作的初始数据块所在的磁道的时间

旋转延时，旋转到初始数据块所在的扇区的时间（转/分）

传送时间，随着盘片的旋转，磁头不断的读/写相应的数据块的时间

计算单次随机IO时间

IO Time = Seek Time + （60 sec/Rotational Speed）* 1/2 + IO Chunk Size/Transfer Rate
IOPS = 1/IO Time

当单次IO越小的时候，单次IO所耗费的时间也越少，相应的IOPS也就越大

5ms + (60sec/15000RPM/2) + 32K/40MB = 5 + 2 + 0.8 = 7.8ms
(1000ms/7.8 ms = 128 IOPS)

提高磁盘IO性能必须减少磁盘寻道次数， Linux实现了四种IO调度算法，通过合并和排序IO请求队列中的请求大大降低所需的磁盘寻道时间。

磁盘调度算法

cat /sys/block/sda/queue/scheduler
noop anticipatory deadline [cfq]

修改调度器，此更改可以在不重新启动计算机的情况下生效。一旦更改，I/O 调度器将会切换

sudo echo noop > /sys/block/hda/queue/scheduler

CFQ(完全公平排队I/O调度程序) scheduler cfq registered (default) ，为每个进程/线程，触发IO的请求的所以进程中保持磁盘IO带宽的公平分配；
NOOP(电梯式调度程序) scheduler noop registeredio ，实现了一个简单的FIFO队列,它像电梯的工作主法一样对I/O请求进行组织，合并用户请求，并不排序请求：新的请求通常被插在调度队列的开头或末尾。
AS(预料I/O调度程序) scheduler anticipatory registeredio，本质上与Deadline一样,但在最后一次读操作后,要等待6ms,才能继续进行对其它I/O请求进行调度,在每个6ms中插入新的I/O操作比如刚调度一个P进程请求，下一个请求是否来自P进程，是，立即执行，否则，查看P进程的统计信息，如果P进程会很快发起一个请求，延迟1小段时间，算法预测P发出的读请求和刚调度的请求是近邻。
Deadline(截止时间调度程序) scheduler deadline registeredio，确保了在一个截止时间内服务请求,这个截止时间是可调整的,而默认读期限短于写期限（避免NOOP请求饿死问题）

寻道算法

先来先服务算法（FCFS），据进程请求访问磁盘的先后次序进行调度
最短寻道时间优先算法（SSTF），每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短
扫描算法（SCAN），磁头前进方向上的最短查找时间优先算法
循环扫描算法（CSCAN）,不考虑访问者等待的先后次序，总是从0号柱面开始向里道扫描，按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后，立即快速返回到0号柱面，返回时不为任何的访问者等待服务。在返回到0号柱面后，再次进行扫描

页高速缓存，解决磁盘IO和CPU速度严重不匹配的问题，所有文件的IO操作都是“读写缓存”。对于读操作，只有当数据不在缓存时才需要IO操作。对于写操作，一定需要IO操作，但内核把数据写到高速缓存后write系统调用立马返回，内核采用特定的写进程统一回写dirty的缓存页。即内核对读写是分别对待的：“同步读，异步写” 。

IO

网络IO模型

一个read操作发生时，它会经历两个阶段

等待数据准备 (Waiting for the data to be ready)
将数据从内核拷贝到进程中(Copying the data from the kernel to the process)

阻塞I/O（blocking I/O），socket默认都是阻塞的，进程在发出IO系统调用后一直堵塞，直到内核有数据且把数据拷贝给进程后，该进程才继续运行。
非阻塞I/O （nonblocking I/O）设置socket为非堵塞的，进程反复调用IO系统调用，如果内核没数据就立即返回继续调用；否则堵塞直到内核把数据拷贝给该进程后，该进程继续运行。
I/O复用(select 和poll) （I/O multiplexing）进程调用IO系统调用，同时监测多个socket。如果所有socket都没有数据则堵塞；否则进程继续运行并通过另一个系统调用以堵塞IO方式去读取数据。
信号驱动I/O （signal driven I/O (SIGIO)）进程调用IO系统调用后不受影响地继续运行，直到内核有数据并发信号给该进程。该进程处理信号时通过另一个系统调用以堵塞IO方式去读取数据。
异步I/O （asynchronous I/O (the POSIX aio_functions)）进程发出IO系统调用后不受影响地继续运行，直到内核有数据并把数据拷贝给进程才发信号给该进程。该进程处理信号即可，无需读取。

前四种都是同步，只有最后一种才是异步IO。异步IO是真正非阻塞的，它不会对请求进程产生任何的阻塞。