操作系统

进程与线程

对于有线程系统：

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

对于无线程系统：

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

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

• 管道（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）：可以以原子的方式阻塞进程，知道某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用

• 信号量机制（Semaphore）

  • 无名线程信号量
  • 命名线程信号量

• 信号机制（SIgnal）：类似进程间的信号处理

• 屏障（Barrier）：屏障允许每个线程等待，知道所有的合作线程都达到某一点，然后从该点继续执行

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

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

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

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

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

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

对比

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

优劣

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

选择

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

死锁

原因

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

产生条件

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

预防

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

文件系统

• 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

大端小端图片

大小端实例

我们知道在计算机中所有数据都是用二进制表示的，举个例子，如果用16位二进制表示数字 258 ，它的二进制是 0000000100000010 ，转换成16进制是 0x0102 。

假如使用大端模式存入内存，内存数据如图：

还原这个数字的步骤是：

• 拿到第1个字节的数据 00000001，乘以进制位256（2的8次方），得到256，即第1个字节（低地址）代表了十进制数字256；
• 拿到第2个字节的数据 00000010 ，它代表十进制数字2，乘以进制位1，得到2；
• 将前两步得到的数字相加，即256+2，得到258，还原出数字。

假如使用小端模式存入内存，内存数据如图：

还原这个数字的步骤是：

• 拿到第1个字节的数据 00000010 ，它代表十进制数字2，乘以进制位1，得到2；
• 拿到第2个字节的数据 00000001，乘以进制位256（2的8次方），得到256，即第1个字节（低地址）代表了十进制数字256；
• 将前两步得到的数字相加，即256+2，得到258，还原出数字。

常用的X86结构是小端模式，很多的ARM、DSP都为小端模式，但KEIL C51则为大端模式，有些ARM处理器还可以由硬件来选择是大端模式还是小端模式。也就是说市面上的手机有些采用大端，有些采用小端模式。

判断大端小端

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

#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类型、操作系统等无关，从而可以保证数据在不同主机之间传输时能够被正确解释。

页面置换算法

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

分类

• 全局置换：在整个内存空间置换
• 局部置换：在本进程中进行置换

算法

全局：

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

局部：

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

内存管理

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

虚拟内存是指把磁盘的一部分作为假想的内存来使用。

通过借助虚拟内存，在内存不足时也可以运行程序。例如，造只剩下5MB内存空间的情况下也能运行10MB大小的程序。不过，CPU只能执行加载到内存中的程序。虚拟内存虽说是把磁盘作为内存的一部分来使用，但实际上正在运行的程序部分，在这个时间点上是必须在内存中的。也就是说，为了实现虚拟内存，就必须把实际内存（也可称物理内存）的内容和磁盘的虚拟内存的内容进行部分置换，并同时运行程序。

虚拟内存的方法分为两种：

• 分页式：在不考虑程序构造的情况下，把运行的程序按照一定大小的页（Page）进行分割，并以页为单位在内存和磁盘建进行置换。
• 分段式：把要运行的程序分割成以处理集合及数据集合等为单位的段落，然后再以分割后的段落为单位在内存和磁盘之间进行数据置换。

Windows使用的是分页式

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着16个页，这16页需要用4个比特为来进行索引定位。例如对于虚拟地址（0010 000000000100），前4位是存储页面号2，读取表向内容为（1101），页表顶最后一位表示是否存在于内存中，1表示存在。后12位存储偏移量。这个页对应的页框的地址为（110 000000000100）。

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

1.最佳 OPT, Optimal replacement algorithm

所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。

是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

开始运行时，先将7，0，,三个页面装入内存。当进程要访问页面2时，产生缺页中断，会将页面7换出，因为页面7再次被访问的时间最长。

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

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

4，7，0，7，1，0，1，2，1，2，6

3.最近未使用 NRU, Not Recently Used

每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：

• R=0，M=0
• R=0，M=1
• R=1，M=0
• R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）

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

选择换出的页面是最先进入的页面。

该算法会将那些经常被访问的页面换出，导致缺页率升高。

5.第二次机会算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

6.时钟 Clock

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页与分段的比较

• 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。

• 地址空间的维度：分页是一维地址空间，分段是二维的。

• 大小是否可以改变：页的大小不可变，段的大小可以动态改变。

• 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。