操作系统

进程与线程

对于有线程系统：

进程是资源分配的独立单位
线程是资源调度的独立单位

对于无线程系统：

进程是资源调度、分配的独立单位

进程之间的通信方式以及优缺点

管道（PIPE）
- 有名管道：一种半双工的通信方式，它允许无亲缘关系进程间的通信
  - 优点：可以实现任意关系的进程间的通信
  - 缺点：
    1. 长期存于系统中，使用不当容易出错
    2. 缓冲区有限
- 无名管道：一种半双工的通信方式，只能在具有亲缘关系的进程间使用（父子进程）
  - 优点：简单方便
  - 缺点：
    1. 局限于单向通信
    2. 只能创建在它的进程以及其有亲缘关系的进程之间
    3. 缓冲区有限
信号量（Semaphore）：一个计数器，可以用来控制多个线程对共享资源的访问
- 优点：可以同步进程
- 缺点：信号量有限
信号（Signal）：一种比较复杂的通信方式，用于通知接收进程某个事件已经发生
消息队列（Message Queue）：是消息的链表，存放在内核中并由消息队列标识符标识
- 优点：可以实现任意进程间的通信，并通过系统调用函数来实现消息发送和接收之间的同步，无需考虑同步问题，方便
- 缺点：信息的复制需要额外消耗 CPU 的时间，不适宜于信息量大或操作频繁的场合
共享内存（Shared Memory）：映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问
- 优点：无须复制，快捷，信息量大
- 缺点：
  1. 通信是通过将共享空间缓冲区直接附加到进程的虚拟地址空间中来实现的，因此进程间的读写操作的同步问题
  2. 利用内存缓冲区直接交换信息，内存的实体存在于计算机中，只能同一个计算机系统中的诸多进程共享，不方便网络通信
套接字（Socket）：可用于不同及其间的进程通信
- 优点：
  1. 传输数据为字节级，传输数据可自定义，数据量小效率高
  2. 传输数据时间短，性能高
  3. 适合于客户端和服务器端之间信息实时交互
  4. 可以加密,数据安全性强
- 缺点：需对传输的数据进行解析，转化成应用级的数据。

线程之间的通信方式

锁机制：包括互斥锁/量（mutex）、读写锁（reader-writer lock）、自旋锁（spin lock）、条件变量（condition）
- 互斥锁/量（mutex）：提供了以排他方式防止数据结构被并发修改的方法。
- 读写锁（reader-writer lock）：允许多个线程同时读共享数据，而对写操作是互斥的。
- 自旋锁（spin lock）与互斥锁类似，都是为了保护共享资源。互斥锁是当资源被占用，申请者进入睡眠状态；而自旋锁则循环检测保持着是否已经释放锁。
- 条件变量（condition）：可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
信号量机制(Semaphore)
- 无名线程信号量
- 命名线程信号量
信号机制(Signal)：类似进程间的信号处理
屏障（barrier）：屏障允许每个线程等待，直到所有的合作线程都达到某一点，然后从该点继续执行。

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制

进程之间的通信方式以及优缺点来源于：进程线程面试题总结

进程之间私有和共享的资源

私有：地址空间、堆、全局变量、栈、寄存器
共享：代码段，公共数据，进程目录，进程 ID

线程之间私有和共享的资源

私有：线程栈，寄存器，程序寄存器
共享：堆，地址空间，全局变量，静态变量

多进程与多线程间的对比、优劣与选择

对比

对比维度	多进程	多线程	总结
数据共享、同步	数据共享复杂，需要用 IPC；数据是分开的，同步简单	因为共享进程数据，数据共享简单，但也是因为这个原因导致同步复杂	各有优势
内存、CPU	占用内存多，切换复杂，CPU 利用率低	占用内存少，切换简单，CPU 利用率高	线程占优
创建销毁、切换	创建销毁、切换复杂，速度慢	创建销毁、切换简单，速度很快	线程占优
编程、调试	编程简单，调试简单	编程复杂，调试复杂	进程占优
可靠性	进程间不会互相影响	一个线程挂掉将导致整个进程挂掉	进程占优
分布式	适应于多核、多机分布式；如果一台机器不够，扩展到多台机器比较简单	适应于多核分布式	进程占优

优劣

优劣	多进程	多线程
优点	编程、调试简单，可靠性较高	创建、销毁、切换速度快，内存、资源占用小
缺点	创建、销毁、切换速度慢，内存、资源占用大	编程、调试复杂，可靠性较差

选择

需要频繁创建销毁的优先用线程
需要进行大量计算的优先使用线程
强相关的处理用线程，弱相关的处理用进程
可能要扩展到多机分布的用进程，多核分布的用线程
都满足需求的情况下，用你最熟悉、最拿手的方式

多进程与多线程间的对比、优劣与选择来自：多线程还是多进程的选择及区别

Linux 内核的同步方式

原因

在现代操作系统里，同一时间可能有多个内核执行流在执行，因此内核其实象多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上，更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。

同步方式

原子操作
信号量（semaphore）
读写信号量（rw_semaphore）
自旋锁（spinlock）
大内核锁（BKL，Big Kernel Lock）
读写锁（rwlock）
大读者锁（brlock-Big Reader Lock）
读-拷贝修改(RCU，Read-Copy Update)
顺序锁（seqlock）

来自：Linux 内核的同步机制，第 1 部分、Linux 内核的同步机制，第 2 部分

死锁

原因

系统资源不足
资源分配不当
进程运行推进顺序不合适

产生条件

互斥
请求和保持
不剥夺
环路

预防

打破互斥条件：改造独占性资源为虚拟资源，大部分资源已无法改造。
打破不可抢占条件：当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。
打破占有且申请条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。
打破循环等待条件：实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源。
有序资源分配法
银行家算法

文件系统

Windows：FCB 表 + FAT + 位图
Unix：inode + 混合索引 + 成组链接

主机字节序与网络字节序

主机字节序（CPU 字节序）

概念

主机字节序又叫 CPU 字节序，其不是由操作系统决定的，而是由 CPU 指令集架构决定的。主机字节序分为两种：

大端字节序（Big Endian）：高序字节存储在低位地址，低序字节存储在高位地址
小端字节序（Little Endian）：高序字节存储在高位地址，低序字节存储在低位地址

存储方式

32 位整数 0x12345678 是从起始位置为 0x00 的地址开始存放，则：

内存地址	0x00	0x01	0x02	0x03
大端	12	34	56	78
小端	78	56	34	12

大端小端图片

判断大端小端

可以这样判断自己 CPU 字节序是大端还是小端：

cpp
#include <iostream>
using namespace std;
int main()
{
int i = 0x12345678;
if (*((char*)&i) == 0x12)
cout << "大端" << endl;
else
cout << "小端" << endl;
return 0;
}

各架构处理器的字节序

x86（Intel、AMD）、MOS Technology 6502、Z80、VAX、PDP-11 等处理器为小端序；
Motorola 6800、Motorola 68000、PowerPC 970、System/370、SPARC（除 V9 外）等处理器为大端序；
ARM（默认小端序）、PowerPC（除 PowerPC 970 外）、DEC Alpha、SPARC V9、MIPS、PA-RISC 及 IA64 的字节序是可配置的。

网络字节序

网络字节顺序是 TCP/IP 中规定好的一种数据表示格式，它与具体的 CPU 类型、操作系统等无关，从而可以保重数据在不同主机之间传输时能够被正确解释。

网络字节顺序采用：大端（Big Endian）排列方式。

页面置换算法

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

算法

全局：

工作集算法
缺页率置换算法

局部：

最佳置换算法（OPT）
先进先出置换算法（FIFO）
最近最久未使用（LRU）算法
时钟（Clock）置换算法

操作系统

操作系统

进程与线程

进程之间的通信方式以及优缺点

线程之间的通信方式

进程之间私有和共享的资源

线程之间私有和共享的资源

多进程与多线程间的对比、优劣与选择

对比

优劣

选择

Linux 内核的同步方式

原因

同步方式

死锁

原因

产生条件

预防

文件系统

主机字节序与网络字节序

主机字节序（CPU 字节序）

概念

存储方式

判断大端小端

各架构处理器的字节序

网络字节序

页面置换算法

分类

算法