操作系统

系统

ubuntu开机的时候系统做了什么

• 加载BIOS
  BIOS程序首先检查，计算机硬件能否满足运行的基本条件，这叫做”硬件自检”。硬件自检完成后，BIOS把控制权转交给下一阶段的启动程序。
• 读取MBR
  计算机读取该设备的第一个扇区，也就是读取最前面的512个字节。如果这512个字节的最后两个字节是0x55和0xAA，表明这个设备可以用于启动；如果不是，表明设备不能用于启动，控制权于是被转交给”启动顺序”中的下一个设备。
• Bootloader
  在这种情况下，计算机读取”主引导记录”前面446字节的机器码之后，不再把控制权转交给某一个分区，而是运行事先安装的”启动管理器”（boot loader），由用户选择启动哪一个操作系统。
  Boot Loader 就是在操作系统内核运行之前运行的一段小程序。通过这段小程序，我们可以初始化硬件设备、建立内存空间的映射图，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用操作系统内核做好一切准备。
  Boot Loader有若干种，其中Grub、Lilo和spfdisk是常见的Loader。Linux环境中，目前最流行的启动管理器是Grub。
• 加载内核
  内核的加载，内核加载后，接开始操作系统初始化，根据进程的优先级启动进程。

ref. ubuntu启动过程

内核态（管态）和用户态（目态）

用户态（User Mode）：处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理器是可被抢占的。

内核态（Kernel Mode）：处于内核态执行时，则能访问所有的内存空间和对象，且所占有的处理器是不允许被抢占的。

三种会导致用户态到内核态切换的情况：

1. 系统调用：应用程序主动向操作系统发出的服务请求
2. 异常：非法指令或者其他原因导致当前指令执行失败。(如：内存出错)后的处理请求
3. 外围设备的中断：来自硬件设备的处理请求

用户态和内核态的区别

什么的系统调用

用户态调用操作系统提供的内核态级别的子功能。

系统调用按功能大致可分为如下几类：

• 设备管理。完成设备的请求或释放，以及设备启动等功能。
• 文件管理。完成文件的读、写、创建及删除等功能。
• 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
• 进程通信。完成进程之间的消息传递或信号传递等功能。
• 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

存储管理

连续内存分配

动态分区分配

• 最先匹配(First-fit)
• 最佳匹配(Best-fit)
• 最差匹配(Worst-fit)

伙伴算法(Buddy system)

Buddy（伙伴的定义）：
这里给出伙伴的概念，满足以下三个条件的称为伙伴：

1. 两个块大小相同；
2. 两个块地址连续；
3. 两个块必须是同一个大块中分离出来的；

• 伙伴算法分配内存:
  若申请的内存大小为n则将n向上取整为2的幂设次数为s,则需要分配s大小的内存块,定位大相应数组：
  1. 如果该数组有剩余内存块,则分配出去；
  2. 若没有剩余内存块就沿数组向上查找,然后再将该内存块分割出来s并将剩余的内存块放入相应大小的数组中。

例如分配5大小的内存块：定位到大小为8的链表中。若该链表中之中没有空余元素,则定位到16的链表中,16中有剩余元素,则取出该元素,并分割出大小为8的内存块供用户使用,然后将剩余的8连接到大小为8的数组中。

• 伙伴算法的内存合并:
  当用户用完内存后会归还,然后根据该内存块实际大小(向上取整为2的幂)归入链表中,在归入之前,
  1. 我们还要检测他的伙伴内存块是否空闲,
  2. 如果空闲就合并在一起,合并后转到1,继续执行.
  3. 若果不是空闲的就直接归入链表中.

一般来说,伙伴算法实现中会用位图记录内存块是否被使用,用于伙伴内存的合并。

伙伴算法的特点:

• 伙伴算法会浪费大量的内存，(如果需要大小为9的内存块必须分配大小为16的内存块)
• 优点也是明显的，分配和合并算法都很简单易行。

ps. 对于小块内存的分配和回收,伙伴算法效果不好，一般采用slab算法,或者叫做slab机制

什么是内存碎片，怎么解决

空闲的内存不但是能被利用

• 外部碎片：分配单元之间的未被使用内存
• 内部碎片：
  • 分配单元内部的未被使用内存
  • 取决于分配单元大小是否要取整

解决：使用非连续内存分配：段、页、段页式

非连续内存分配

段式存储管理系统

进程的段地址空间由多个段组成

• 主代码段
• 子模块代码段
• 公用库代码段
• 堆栈段(stack)
• 堆数据(heap)
• 初始化数据段
• 符号表等

页式存储管理系统

分页就是说，将磁盘或者硬盘分为大小固定的数据块，叫做页，然后内存也分为同样大小的块，叫做页框。当进程执行的时候，会将磁盘的页载入内存的某些页框中，并且正在执行的进程如果发生缺页中断也会发生这个过程。页和页框都是由两个部分组成的，一个是页号或者页框号，一个是偏移量。分页一般是有硬件来完成的，每个页都对应一个页框，它们的对应关系存放在一个叫做页表的数据结构中，页号作为这个页表的索引，页框号作为页表的值。操作系统负责维护这个页表。

帧（物理页面）

把物理地址空间划分为大小相同的基本分配单位，大小为2的n次方，如512, 4096, 8192。

内存物理地址的表示：二元组 (f, o)

• f：帧号 (F 位, 共有2^F个帧)
• o：帧内偏移 (S 位, 每帧有2^S字节)
• 物理地址 = f * 2^S + o

页（逻辑页面）

把逻辑地址空间也划分为相同大小的基本分配单位，帧和页的大小必须是相同的。

• 页内偏移 = 帧内偏移
• 通常：页号大小 ≠ 帧号大小

进程逻辑地址的表示：二元组 (p, o)

• p：页号 (P 位, 2P 个页)
• o：页内偏移 (S 位, 每页有2S 字节)
• 虚拟地址 = p * 2S + o

页表

页表项的组成：

• 帧号 f
• 页表项标志
  • 存在位
  • 引用位
  • 修改位

快表（TLB）

缓存近期访问的页表项。TLB 使用关联存储(associative memory)实现，具备快速访问性能。

• 如果TLB命中，物理页号可以很快被获取
• 如果TLB未命中，对应的表项被更新到TLB中

多级页表

分页和分段有什区别？

• 分页对程序员是透明的，但是分段需要程序员显式划分每个段。
• 分页的地址空间是一维地址空间，分段是二维的。
• 页的大小不可变，段的大小可以动态改变。
• 分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

段页式存储管理系统

在段式存储管理基础上，给每个段加一级页表

段页式存储管理中的内存共享：

虚拟存储

虚拟存储就是说，让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。虚拟内存使用部分加载的技术，让一个进程或者资源的某些页面加载进内存，从而能够加载更多的进程，甚至能加载比内存大的进程，这样看起来好像内存变大了，这部分内存其实包含了磁盘或者硬盘，并且就叫做虚拟内存。

虚拟页式存储管理

在页式存储管理的基础上，增加请求调页和页面置换。

• 当用户程序要装载到内存运行时，只装入部分页面，就启动程序运行
• 进程在运行中发现有需要的代码或数据不在内存时，则向系统发出缺页异常请求
• 操作系统在处理缺页异常时，将外存中相应的页面调入内存，使得进程能继续运行

虚拟段式存储管理

在段式存储管理的基础上，以分段为单位进行换入换出。

缺页异常

页面置换算法

当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面

局部置换

置换页面的选择范围仅限于当前进程占用的物理页面内

• 最优置换算法
  选择的被换出的页面是未来最长时间内不再被访问的页面，通常可以保证获得最低的缺页率。这是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。
• 先进先出
  选择换出的页面是最先进入的页面。该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。
• 最近最久未使用(Least Recently Used, LRU)
  虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
  为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
• 时钟算法(Clock)
  页面装入内存时，访问位初始化为0。访问页面（读/写)时，置访问位置为1。缺页时，从指针当前位置顺序检查环形链表：
  • 访问位为0，则置换该页
  • 访问位为1，则访问位置0，并指针移动到下一个页面，直到找到可置换的页面
• 最不常用算法(Least Frequently Used, LFU)
  缺页时，置换访问次数最少的页面。每个页面设置一个访问计数，访问页面时，访问计数加1，缺页时，置换计数最小的页面。

全局置换

置换页面的选择范围是所有可换出的物理页面。

• 工作集置换算法：换出不在工作集中的页面。当前时刻前τ个内存访问的页引用是工作集，τ被称为窗口大小。
• 缺页率算法：通过调节常驻集大小，使每个进程的缺页率保持在一个合理的范围内。

Belady现象

采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象

• FIFO算法的置换特征与进程访问内存的动态特征矛盾
• 被它置换出去的页面并不一定是进程近期不会访问的

LRU算法没有Belady现象

抖动(thrashing)

进程物理页面太少，不能包含工作集，造成大量缺页，频繁置换，进程运行速度变慢。

原因：随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。

进程和线程

进程

Linux 下创建新进程的系统调用是fork

#include <sys/types.h>
#include <unistd.h>
pid_t fork(void);

//处理僵尸进程
pid_t waitpid(pid_t pid, int* stat_loc, int options);

进程有哪几种状态?他们的转换方式

• 创建状态(new)：进程正在被创建，尚未到就绪状态。
• 就绪状态(ready)：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。
• 运行状态(running)：进程正在处理器上上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。
• 阻塞状态(waiting)：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
• 结束状态(terminated)：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

进程间的通信方式

1. 管道/匿名管道(Pipes)：速度慢，容量有限，只用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
2. 命名管道(Names Pipes/FIFO)：任何进程间都能通讯，但速度慢，严格遵循先进先出(first in first out)。
3. 消息队列(Message Queuing)：消息队列是消息的链表，具有特定的格式，存放在内存中并由消息队列标识符标识。容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题。
4. 信号量(Semaphores)：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。不能传递复杂消息，只能用来同步。
5. 共享内存(Shared memory)：能够很容易控制容量，速度快，但需要依靠某种同步操作，如互斥锁和信号量等。比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存。
6. 套接字(Sockets)：此方法主要用于在客户端和服务器之间通过网络进行通信，也可以用于同一主机上的socket通信。
7. 信号(Signal) ：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

进程间的五种通信方式介绍

进程控制块（process control block，PCB）

PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

进程描述信息：

• 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
• 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

• 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
• 进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

• 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

CPU 相关信息：

• CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

每个 PCB 是如何组织的呢？

通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

• 将所有处于就绪状态的进程链在一起，称为就绪队列；
• 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
• 另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

进程的调度算法

• 先到先服务(FCFS)调度算法：从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 短作业优先(SJF)的调度算法：从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 时间片轮转调度算法：时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
• 多级反馈队列调度算法：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
• 优先级调度：为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

孤儿进程，僵尸进程，守护进程

孤儿进程：父进程退出后子进程还在运行。这些子进程就叫做孤儿进程。孤儿进程被init进程收养。

僵尸进程：子进程结束后，内核不会立即释放该进程的进程表表项，以满足父进程后续对该子进程的信息查询。子进程退出之后，父进程读取其退出状态（调用waitpid获取子进程状态信息）之前，就是僵尸进程。

守护进程：在后台运行不受终端控制的进程。如输入，输出，网络服务等。

创建守护进程

1. 创建子进程，父进程退出
2. 在子进程中创建新的会话（脱离控制终端）：使用系统函数setsid()来创建。
3. 改变当前目录为根目录
4. 重设文件权限掩码，关闭文件描述符

处理孤儿进程，僵尸进程

孤儿进程没有什么危害，所以并不需要怎么处理。

如果父进程一直不调用wait/waitpid处理以及退出的子进程，子进程就会一直在系统里占用资源。

僵尸进程的处理方式为：当一个进程结束时，它会给父进程发送一个SIGCHLD信号，我们在父进程中捕获SIGCHLD信号，并在信号处理函数中调用waitpid函数来处理退出的子进程。

线程

Linux 系统中，线程的基础API都定义在 pthread.h 中。

#include <pthead.h>
int pthread_create(pthread_t* thread, const pthread_attr_r* attr,
                   void* (*start_routine)(void*), void* arg);

void pthread_exit(void* retval);

线程间的同步的方式

1. 锁机制
   • 互斥锁：互斥锁提供了以排他方式防止数据结构被并发修改的方法
   • 读写锁：读写锁允许多个线程同时读共享数据，而对写操作是互斥的
   • 条件变量：条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用
   • 自旋锁
2. 信号量(Semphares)：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
3. 信号机制(Signal)：类似进程间的信号处理

互斥锁与信号量的区别：

• 互斥锁用户线程互斥，信号量用于线程同步。
• 互斥锁仅用于线程，信号量还可以用于进程。

线程安全怎么实现

线程安全定义：当多个线程访问一个对象时，如果不用考虑这些线程在运行时环境下的调度和交替执行，也不需要进行额外的同步，或者在调用方进行任何其他的协调操作，调用这个对象的行为都可以获得正确的结果，那么这个对象就是线程安全的。

线程安全的实现方式：

1. 互斥同步：指多个线程并发访问共享数据时，保证共享数据在同一时刻只被一个线程使用。常见的互斥实现方式有：临界区(critical selection)，互斥量(mutex)和信号量(semaphore)。互斥同步最主要的问题就是进行线程阻塞和唤醒所带来的性能问题，因此这种实现方式也叫阻塞同步。从处理问题的方式上来说，互斥同步属于一种悲观的并发策略。
2. 非阻塞同步：随着硬件指令集的发展，我们有了另外的一个选择：基于冲突检测的乐观并发策略。也就是先进行操作，如果没有其它线程使用共享数据，那就操作成功；如果有，那就再采取补偿措施。这种方式不需要把线程挂起，因此称为：非阻塞同步(Non-Blocking Synchronization)。
3. 无同步方案：
   • 可重入代码
   • 线程本地存储：如果一段代码中所需要的数据都完全包含在同一个线程中，如果能保证这一点，那就不会因为跟其它线程争抢修改资源而导致数据不一致，也就没有线程风险，是线程安全的。

ref.

• 线程安全的实现方式

进程和线程的差别

线程是指进程内的一个执行单元，也是进程内的可调度实体。线程与进程的区别：

• 调度：线程作为CPU调度的基本单位，进程作为拥有资源的基本单位；
• 拥有资源：进程是拥有资源的一个独立单元，进程拥有一个完整的资源平台；线程只独享必不可少的资源，如寄存器和栈，不拥有系统资源但可以访问隶属于进程的资源
• 并发性：不仅进程之间可以并发执行，同一个进程的多个线程也可以并发执行；
• 线程的状态：线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
• 系统开销：在创建或撤销进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤销线程时的开销；

进程上下文切换，线程上下文切换，中断上下文切换

进程上下文切换

进程上下文包括计算机系统中与执行该进程有关的各种寄存器（例如通用寄存器，程序计数器PC，程序状态字寄存器PS等）的值，程序段在经过编译过后形成的机器指令代码集，数据集及各种堆栈值PCB结构。

当切换进程时，需要保存当前进程的所有状态，即当前进程的进程上下文，以便再次执行该进程时，能够恢复切换时的状态，继续执行。

发生进程上下文切换有哪些场景？

在进程状态发生改变时，且进程基本都属于进程上下文切换的场景：

• 为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；
• 进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；
• 当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；
• 当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；
• 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

线程上下文切换

线程上下文：当进程只有一个线程时，可以认为进程就等于线程；当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

线程的上下文切换：

• 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
• 当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；

中断上下文切换

中断上下文：中断时需要保存的参数和进程环境。

线程有自己的堆，栈吗

与线程“绑定”的是栈，用于存储自动变量。每一个线程建立的时候，都会新建一个默认栈与之配合。堆则是通常与进程相关，用于存储全局性的变量，进程建立的时候，会建立默认堆。于是，每一个线程都有自己的栈，然后访问共同的堆。当然，你可以通过OsApi建立其他堆栈。

• 堆：是大家共有的空间，分全局堆和局部堆。全局堆就是所有没有分配的空间，局部堆就是用户分配的空间。堆在操作系统对进程初始化的时候分配，运行过程中也可以向系统要额外的堆，但是记得用完了要还给操作系统，要不然就是内存泄漏。
• 栈：是个线程独有的，保存其运行状态和局部自动变量的。栈在线程开始的时候初始化，每个线程的栈互相独立，因此，栈是　thread safe的。操作系统在切换线程的时候会自动的切换栈，就是切换　ＳＳ／ＥＳＰ寄存器。栈空间不需要在高级语言里面显式的分配和释放。

并发，同步，异步，互斥，阻塞，非阻塞

并发：多个程序同时运行即并发。并发可分为同步和互斥。

同步，互斥

互斥：同一时间只能有一个访问者访问资源，无序的

同步：必须按照某种顺序运行。在互斥的基础上通过其他机制实现资源的有序访问。

同步时一种更复杂的互斥，互斥是一种特殊的同步。

同步，异步

同步：顺序执行，需要等待、协调运作。

异步：彼此独立，在等待某事件的过程中继续做自己的事，不需要等待。

• 线程是实现异步的一个方式
• 异步 不等于 多线程。异步是最终目的，多线程只是实现异步的一种手段

阻塞，非阻塞

经常访问数据时，根据IO操作的就绪状态不同采取的不同处理方式。比如读取文件内容，阻塞方式下主程序会等到函数读取完再继续，非阻塞方式下主程序不等待文件读取完就继续往下执行。

一般可以分为：同步阻塞，同步非阻塞，异步阻塞，异步非阻塞

同步阻塞，同步非阻塞，异步阻塞，异步非阻塞

以发送方发出请求要接收方读取文件内容为例。

• 同步阻塞：发送方发出请求后一直等待（同步）。接受方开始读取，如果不能马上读到就一直等待，直到读取后响应发送方，等待期间不能做其他操作（阻塞）。
• 同步非阻塞：发送方发出请求后一直等待（同步）。接受方开始读取，如果不能马上读到就立即返回继续做其他事情（非阻塞），并未响应发送方。直到IO完成才响应。
• 异步阻塞：发送方发出请求后不等待响应，继续其他工作（异步）。接受方开始读取，如果不能马上读到就一直等待，直到读取后响应发送方，等待期间不能做其他操作（阻塞）。
• 异步非阻塞：发送方发出请求后不等待响应，继续其他工作（异步）。接受方开始读取，如果不能马上读到就立即返回继续做其他事情（非阻塞），并未响应发送方。直到IO完成才响应。（效率最高）

ps. 发送方等待就是同步，不等待就是异步；接收方等待就是阻塞，不等待就是非阻塞。

总结：

• 同步异步是两个线程之间的关系，两个线程之间要么是同步的，要么是异步的。
• 阻塞与非阻塞是对同一个线程来说。某个时刻，线程处于阻塞或非阻塞

多进程、多线程的优缺点

• 多进程更鲁棒，一个进程死了不影响其他进程，子进程死了不影响主进程。多线程比较脆弱，一个线程崩溃可能会影响整个程序。
• 进程性能大于线程，但是创建进程花销大于线程。
• 进程通讯需要跨越进程边界，不适合大量数据传送，更适合小数据活着密集数据。线程可以共享内存和变量，适合大量数据的传送。
• 多进程逻辑空控制比多线程复杂
• 多线程虽然逻辑控制比较简单，但是需要复杂的同步和加锁控制等机制
• 可以通过增加CPU数量来增加进程的数量，但是不能通过增加CPU来增加线程的数量，线程的数量由进程的空间资源和线程本身栈大小确定。

为什么要使用线程？与进程相比有哪些好处

1. 资源
   和进程相比，它是一种非常”节俭”的多任务操作方式。在linux系统下，启动一个新的进程必须分配给它独立的地址空间，建立众多的数据表来维护它的代码段、堆栈段和数据段，这是一种”昂贵”的多任务工作方式。
2. 切换效率
   运行于一个进程中的多个线程，它们之间使用相同的地址空间，而且线程间彼此切换所需时间也远远小于进程间切换所需要的时间。据统计，一个进程的开销大约是一个线程开销的30倍左右。（但是进程性能大于线程）
3. 通信
   线程间方便的通信机制。对不同进程来说，它们具有独立的数据空间，要进行数据的传递只能通过进程间通信的方式进行，这种方式不仅费时，而且很不方便。线程则不然，由于同一进城下的线程之间贡献数据空间，所以一个线程的数据可以直接为其他线程所用，这不仅快捷，而且方便。
4. 使多CPU系统更加有效。
   操作系统会保证当线程数不大于CPU数目时，不同的线程运行于不同的CPU上。(CPU设计保证）
5. 改善程序结构。
   一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序才会利于理解和修改。（代码易维护）

什么时候用进程，什么时候用线程

进程用来“做大事”，线程用来“各自做小事”：

• 创建和销毁较频繁，用线程
• 需要大量数据传送，用线程
• 并行操作，用线程
• 总结：安全稳定用进程，快速频繁用线程

Linux查看/杀死/重启进程

• 查看：ps -aux 或 ps -ef
• 杀死：kill -PID 或强制杀死kill -KILL PID
• 重启：kill -HUP PID

ref

进程、线程基础知识全家桶

有哪些锁？

• 互斥锁：同一时间只能有一个线程获得互斥锁，其他线程阻塞进入休眠态
• 读写锁：同一时间可以有多个线程获得读锁，适用于读操作频繁的场景
• 自旋锁：同一时间只能有一个线程获得自旋锁，其他线程会一直等待锁并且不会进入休眠态，如果不加限制，某个线程申请已经锁定的自旋锁，就会导致其他线程卡死，所以自旋锁适用于锁拥有者保持锁时间很短的场景

C++有哪些锁

什么是可重入和不可重入函数？

• 可重入函数可以由多个任务并发使用，而不必担心数据错误。
  可重入函数可以在任意时刻被中断，稍后继续运行，不会丢失数据，可重入函数要么使用本地变量，要么使用全局变量时保护自己的数据。
• 不可重入函数不能由多个任务共享，除非能确保函数的互斥。

特点：

• 可重入函数
  • 不可连续的调用持有静态数据；
  • 不返回指向静态数据的指针，所有数据都是由函数的调用者提供；
  • 使用本地数据，或者通过制作全局数据的本地拷贝来保护全局数据；
  • 如果必须访问全局变量，记住利用互斥信号量来保护全局变量；
  • 绝不调用任何不可重入函数。
• 不可重入函数
  • 函数中使用了静态变量，无论是全局静态变量还是局部静态变量；
  • 函数返回静态变量；
  • 函数中调用了不可重入函数；
  • 函数体内使用了静态的数据结构；
  • 函数体内调用了malloc()或者free()函数；
  • 函数体内调用了其他标准I/O函数；

总之，如果一个函数在重入条件下使用了未受保护的共享资源，那么就是不可重入的。

死锁

死锁是指两个或多个进程在执行的过程中，因为竞争资源而造成互相等待的现象，若无外力作用，它们都无法推进下去。

死锁的处理方法

• 预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。
• 避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。
• 检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。
• 解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。

产生死锁的原因

1. 因为系统资源不足。
2. 进程运行推进的顺序不合适。
3. 资源分配不当等。

死锁的4个必要条件

1. 互斥：一个资源每次只能被一个进程使用。
2. 请求与保持：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
3. 不剥夺：进程已获得的资源，在末使用完之前，不能强行剥夺。
4. 循环等待：若干进程之间形成一种头尾相接的循环等待资源关系。

死锁的预防

我们可以通过破坏产生死锁的四个必要条件来预防死锁，但是资源互斥是固有特性无法改变的。

1. 破坏“请求与保持”条件
   • 静态分配，每个进程在开始执行时就申请他所需要的全部资源。
   • 动态分配，每个进程在申请所需要的资源时他本身不占用系统资源。
2. 破坏“不可剥夺”条件
   一个进程不可获得其所需要的全部资源便处于等待状态，等待期间他占用的资源将被隐式的释放重新加入到系统的资源列表中，可以被其他进程使用，而等待的进程只有重新获得自己原有的资源以及新申请的资源才可以重新启动，执行。
3. 破坏“循环等待”条件
   采用资源有序分配的基本思想。将系统中的资源顺序进行编号，将紧缺的、稀少的资源采用较大的编号，申请资源时必须按照编号的顺序执行，一个进程只有较小编号的进程才能申请较大编号的进程。

死锁的避免

• 有序资源分配法：源按某种规则系统中的所有资源统一编号，申请时必须以上升的次序。
• 银行家算法

ref.

• 死锁

进程占用率过高怎么排查

• jstack：适用于java进程，可以取到所以线程的堆栈dump；
• pstack：适用于所有linux进程，是对gdb的功能封装。
  此命令可显示每个进程的栈跟踪。pstack 命令必须由相应进程的属主或 root 运行。可以使用 pstack 来确定进程挂起的位置。此命令允许使用的唯一选项是要检查的进程的 PID。

文件系统

文件描述符

文件描述符是打开文件的标识，操作系统在打开文件表中维护的打开文件状态和信息。

• 文件指针
• 文件打开计数
• 文件的磁盘位置
• 访问权限

Linux文件系统

Linux文件系统里面有文件和目录，组成一个树状的结构，树的每一个叶子节点表示文件或者空目录。每个文件基本上都由两部分组成：

• inode：一个文件占用一个 inode，记录文件的属性，同时记录此文件的内容所在的 block 编号；
• block：记录文件的内容，文件太大时，会占用多个 block。

除此之外还包括：

• superblock：记录文件系统的整体信息，包括 inode 和 block 的总量、使用量、剩余量，以及文件系统的格式与相关信息等；
• block bitmap：记录 block 是否被使用的位图。

当要读取一个文件的内容时，先在 inode 中查找文件内容所在的所有 block，然后把所有 block 的内容读出来。

从内核文件系统看文件读写过程

什么是 inode

理解inode，要从文件储存说起。

文件储存在硬盘上，硬盘的最小存储单位叫做”扇区”（Sector）。每个扇区储存512字节（相当于0.5KB）。

操作系统读取硬盘的时候，不会一个个扇区地读取，这样效率太低，而是一次性连续读取多个扇区，即一次性读取一个”块”（block）。这种由多个扇区组成的”块”，是文件存取的最小单位。”块”的大小，最常见的是4KB，即连续八个 sector组成一个 block。

文件数据都储存在”块”中，那么很显然，我们还必须找到一个地方储存文件的元信息，比如文件的创建者、文件的创建日期、文件的大小等等。这种储存文件元信息的区域就叫做inode，中文译名为”索引节点”。

每一个文件都有对应的inode，里面包含了与该文件有关的一些信息。

Linux 文件系统通过 i 节点把文件的逻辑结构和物理结构转换的工作过程

Linux 通过 inode 节点表将文件的逻辑结构和物理结构进行转换。

inode 节点是一个 64 字节长的表，表中包含了文件的相关信息，其中有文件的大小、文件所有者、文件的存取许可方式以及文件的类型等重要信息。在 inode 节点表中最重要的内容是磁盘地址表。在磁盘地址表中有 13 个块号，文件将以块号在磁盘地址表中出现的顺序依次读取相应的块。
Linux 文件系统通过把 inode 节点和文件名进行连接，当需要读取该文件时，文件系统在当前目录表中查找该文件名对应的项，由此得到该文件相对应的 inode 节点号，通过该 inode 节点的磁盘地址表把分散存放的文件物理块连接成文件的逻辑结构。

硬链接和软链接有什么区别

• 硬链接：由于 Linux 下的文件是通过索引节点(inode)来识别文件，硬链接可以认为是一个指针，指向文件索引节点的指针，系统并不为它重新分配 inode 。每添加一个一个硬链接，文件的链接数就加 1。
  不足：

  • 不可以在不同文件系统的文件间建立链接；
  • 只有超级用户才可以为目录创建硬链接。

• 软链接：软链接克服了硬链接的不足，没有任何文件系统的限制，任何用户可以创建指向目录的符号链接。因而现在更为广泛使用，它具有更大的灵活性，甚至可以跨越不同机器、不同网络对文件进行链接。
  不足：

  • 因为链接文件包含有原文件的路径信息，所以当原文件从一个目录下移到其他目录中，再访问链接文件，系统就找不到了，而硬链接就没有这个缺陷，你想怎么移就怎么移；还有它要系统分配额外的空间用于建立新的索引节点和保存原文件的路径。

• 实际场景下，基本是使用软链接。总结区别如下：

  • 硬链接不可以跨分区，软件链可以跨分区。
  • 硬链接指向一个 inode 节点，而软链接则是创建一个新的 inode 节点。
  • 删除硬链接文件，不会删除原文件，删除软链接文件，会把原文件删除。

文件的分配

• 连续分配
• 链式分配
• 索引分配

操作系统读写文件的过程

从Linux文件系统看文件读写过程
从内核文件系统看文件读写过程

I/O

三种I/O操作

• 阻塞I/O：读写数据时，进程将进入等待状态
• 非阻塞I/O：立即从read或write系统调用返回，返回值为成功传输字节数
• 异步I/O：使用指针标记好用户缓冲区，立即返回；稍后内核再处理并通知用户

I/O请求生存周期

CPU与设备控制器的数据传输

程序控制I/O(PIO, Programmed I/O)

通过CPU的in/out或者load/store传输所有数据。

直接内存访问(DMA)

设备控制器可直接访问系统总线，控制器直接与内存互相传输数据。

I/O设备如何通知操作系统

• CPU主动轮询：I/O 设备在特定的状态寄存器中放置状态和错误信息，操作系统定期检测状态寄存器。
• 设备中断：CPU在I/O之前设置任务参数；CPU发出I/O请求后，继续执行其他任务；I/O设备处理I/O请求；I/O设备处理完成时，触发CPU中断请求；CPU接收中断，分发到相应中断处理例程。
  

磁盘调度算法

• 先来先服务(FIFO)
  • 按照磁盘请求的顺序进行调度。
  • 优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。
• 最短寻道时间优先(SSTF)
  • 优先调度与当前磁头所在磁道距离最近的磁道。
  • 虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。一般来说，两端的磁道请求更容易出现饥饿现象。
• 电梯算法(SCAN扫描算法)
  • 电梯算法就是说读写磁头总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。
  • 因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了最短寻道时间优先的饥饿问题。
• 循环扫描算法(C-SCAN)
  • 限制了仅在一个方向上扫描
  • 当最后一个磁道也被访问过了后，磁臂返回到磁盘的另外一端再次进行
• C-LOOK算法
  • 磁臂先到达该方向上最后一个请求处，然后立即反转，而不是先到最后点路径上的所有请求
• N步扫描(N-step-SCAN)算法
  • 磁头粘着(Arm Stickiness)现象：SSTF、SCAN及CSCAN等算法中，可能出现磁头停留在某处不动的情况
  • N步扫描算法将磁盘请求队列分成长度为N的子队列，按FIFO算法依次处理所有子队列，扫描算法处理每个队列
• 双队列扫描(FSCAN)算法
  • FSCAN算法是N步扫描算法的简化，FSCAN只将磁盘请求队列分成两个子队列
  • 把磁盘I/O请求分成两个队列，交替使用扫描算法处理一个队列，新生成的磁盘I/O请求放入另一队列中，所有的新请求都将被推迟到下一次扫描时处理。

磁盘缓存

• 单缓存
  
• 双缓存
  

ref

• 清华大学操作系统课程