操作系统理论

站在冯诺依曼角度，理解操作系统定位

管理和控制计算机硬件与软件资源的计算机程序
冯诺伊曼（存储程序原理）

1. 冯诺伊曼体系的存储器指的是内存

2. 不考虑缓存的情况，CPU只能对内存进行操作，不能访问外设（输入或输出设备）

3. 外设（输入输出设备）如果想输入输出数据也只能写入内存或从内存中读取

4. 所有设备只能直接和内存打交道

站在管理角度，理解操作系统[先描述再组织]

1. 描述：管理软件的软件

2. 组织：如何管理软件？
   操作系统是最基本的系统软件，它控制着计算机所有的资源并提供应用程序开发的接口

站在应用者的角度，理解操作系统

1. 从程序员角度看，操作系统是将程序员从复杂的硬件控制中解脱出来，并为软件开发者提供了一个虚拟机，从而能更方便的进行程序设计

2. 从一般用户角度看，操作系统为他们提供了一个良好的交互界面，使得他们不必了解有关硬件和系统软件的细节，就能方便地使用计算机

站在操作系统角度，理解系统调用接口

操作系统作为系统软件，它的任务是为用户的应用程序提供良好的运行环境。因此，由操作系统内核提供一系列内核函数，通过一组称为系统调用的接口提供给用户使用。系统调用的作用是把应用程序的请求传递给系统内核，然后调用相应的内核函数完成所需的处理，最终将处理结果返回给应用程序。因此，系统调用是应用程序和系统内核之间的接口

站在操作系统角度，理解操作系统外壳程序定位与作用（Linux shell）

1. 在操作系统之上提供的一套命令解释程序叫做外壳程序（shell）

2. 外壳程序是操作员与操作系统交互的界面，操作系统再负责完成与机器硬件的交互。

3. 所以操作系统可成为机器硬件的外壳，shell命令解析程序可称为操作系统的外壳。

4. 自定义网站/动画/图片/flash等、可添加统计代码、自定义限制运行时间，限制操作等、自定义公告内容、到时自动运行、设置开机启动、隐藏执行‘、hosts修改、设置主页

对比系统调用，理解库函数

• 一般而言，跟内核功能与操作系统特性紧密相关的服务，由系统调用提供；

• 具有共通特性的功能一般需要较好的平台移植性，故而由库函数提供。

• 库函数与系统调用在功能上相互补充：

  1. 如进程间通信资源的管理，进程控制等功能与平台特性和内核息息相关，必须由系统调用来实现。

  2. 文件 I/O操作等各平台都具有的共通功能一般采用库函数，也便于跨平台移植。

• 某些情况下，库函数与系统调用也有交集：
  如库函数中的I/O操作的内部实现依然需要调用系统的I/O方能实现。

• 库函数与系统调用主要区别：

  1. 所有 C 函数库是相同的，而各个操作系统的系统调用是不同的。

  2. 函数库调用是调用函数库中的一个程序，而系统调用是调用系统内核的服务。

  3. 函数库调用是与用户程序相联系，而系统调用是操作系统的一个进入点

  4. 函数库调用是在用户地址空间执行，而系统调用是在内核地址空间执行

  5. 函数库调用的运行时间属于用户时间，而系统调用的运行时间属于系统时间

  6. 函数库调用属于过程调用，开销较小，而系统调用需要切换到内核上下文环境然后切换回来，开销较大

  7. 在C函数库libc中大约 300 个程序，在 UNIX 中大约有 90 个系统调用

  8. 函数库典型的 C 函数：system, fprintf, malloc，而典型的系统调用：chdir, fork, write, brk

进程基本概念（重点）

进程概念（PCB［task_struct］）

基本概念：程序执行的一个实例，正在运行的程序
基于内核：但当分配系统资源（CPU时间、内存）的实体
基于PCB（Linux下称为task_struct）：task_struct是一种数据结构，他被装载到RAM里并包含进程信息（信息如下）
1. 标示符：区别和其他进程的唯一标识符号
2. 状态：任务状态、退出代码、退出信号
3. 优先级：相对其他进程的优先级
4. 程序计数器：程序中即将被执行的下一条指令
5. 内存指针：包括程序代码和进程相关的数据指针，还有和其他进程共享内存的指针
6. 上下文数据：进程执行时处理器的寄存器中的数据
7. I/O状态信息：包括I/O显示的请求、分配给I/O的设备、被进程使用的文件列表
8. 记账信息：可能包括处理器时间总和，使用的时钟数总和，时间限制，记账号

进程和程序有什么区别

• 进程是程序的一次执行过程，是动态概念，程序是一组有序的指令集和，是静态概念

• 进程是暂时的，是程序在数据集上的一次执行，可创建可撤销，程序是永存的

• 进程具有并发行，程序没有

• 进程是竞争计算机资源的最小单位，程序不是

• 进程与程序不是一一对应，多个进程可执行一个程序，一个程序可执行多个程序

进程标识，进程间关系

• 进程标识：进程ID，简称PID，是大多数操作系统内核用于唯一标识进程的数值

  1. PID的数值是非负整数

  2. 每个进程都有唯一的一个PID

  3. PID可以简单地表示为主进程表中的一个索引

  4. 当某一进程终止后，其PID可以作为另一个进程的PID

  5. 调度进程的PID固定为0，他按一定原则把处理机分配给进程使用

  6. 初始化进程的PID固定为1，他是Linux系统中其他进程的祖先，是进程的最终控制者

  7. 每个进程都有六个重要的ID：进程ID，父进程ID，有效用户ID，有效组ID，实际用户ID，实际组ID

  获取各类ID的函数
  #include<sys/types.h>
  #include<unistd.h>
  void getpid(void)//返回值：进程ID
  void getppid(void)//返回值：父进程ID
  void getpid(void)//返回值：进程ID
  void getuid(void)//返回值：实际用户进程ID
  void geteuid(void)//返回值：有效用户进程ID
  void getgid(void)//返回值：实际组进程ID
  void getegid(void)//返回值：有效组进程ID
  
  

进程状态

进程在运行中的几种运行状态

• 创建状态：进程在创建是需要需要申请一个新的PCB，并将控制和管理进程的信息放在PCB里面，从而完成资源分配。如果创建工作无法完成（比如资源无法满足）就无法被调度运行。

• 就绪状态：进程已经准备好了，已经分配到所需资源，只要分配到PCB上就能立即运行。（此状态允许父进程终止子进程）

• 执行状态：处于就绪状态的进程被调度后就进入到执行状态

• 阻塞状态：正在执行的程序由于受到某些事件（IO请求/申请缓存区失败）的影响而暂时无法运行，进程受到阻塞。在满足条件时进程进入就绪状态等待被调度。（此状态允许父进程终止子进程）

• 终止状态：进程结束，或出现错误，或被系统终止，进入终止状态，无法再执行



Linux下的进程状态（R、S、D、T、Z、X）

• R（可执行）状态：并比意味着进程一定在运行中，它表明要么在运行中，要么在运行队列里面

• S（睡眠）状态：意味着进程在等待事件完成（这里的睡眠有时候也叫做可中断睡眠）

• D（不可中断睡眠）状态：在这个状态的进程通常会等待IO结束

• T（暂停）状态：可以发送信号SIGSTOP给进程从而来停止进程，这个进程可以通过SIGCONT信号让进程继续运行

• Z（僵尸）状态：该进程在其父进程没有读取到子进程退出返回的代码时就退出了，该进程就进入了僵尸状态。僵尸状态会以终止的状态保持在进程表中，并一直等待父进程读取退出状态码

• X（死亡/退出）状态：这个状态只是一个返回状态，在任务列表中看不到这个状态

进程优先级

• CPU资源分配的先后顺序，就是进程的优先权

• 优先权高的进程先执行，配置优先权对多任务的Linux环境很有用，可以提高系统的性能

• 还可以把某个进程指定到某个CPU上，可以提高系统整体的性能

进程创建

fork函数

#include<unistd.h>
pid_t fork(void)

返回值：自进程返回0，父进程返回子进程ID，出错返回-1。

• 进程调用fork函数时，当控制转移到内核中fork代码后，内核做的事情有：

  1. 分配新的数据块和数据结构给子进程

  2. 将父进程的数据结构的部分内容拷贝到子进程中

  3. 将子进程添加到系统进程列表

  4. fork返回。开始调度器调度

• fork之前，父进程独立执行，fork之后，父子进程两个执行流分别执行，谁先谁后不确定，完全由调度器决定的。

• 通常情况下，父子代码共享，父子在不写入的情况下都是共享的。当有一方试图写入时，便以写实拷贝各自一份副本进行写入。

• 错误码EAGAIN表示达到进程数上线，ENOMEM表示没有足够空间给一个新进程分配

• 所有由父进程打开的文件描述符都被复制到子进程中，父子进程中相同编号的文件描述符在内核中指向同一个file结构体，也就是说file结构体的引用计数要增加

• fork常用的场景：

  1. 父进程希望复制自己，父子进程同时执行不同代码段（比如：父进程等待客户端请求，生成子进程来处理请求）

  2. 一个进程要执行不同的程序（比如：子进程从fork返回后调用exec函数）

vfork函数

#include<unistd.h>
pid_t vfork(void)

返回值：自进程返回0，父进程返回子进程ID，出错返回-1。

• 产生一个子进程，但父子进程共享数据段（共享地址空间）

• vfork保证子进程先运行，等到子进程调用exec或者exit之后父进程才开始执行

• 如果在调用exec或exit之前，子进程依赖于父进程进一步动作，则会造成死锁

• 改变子进程变量的值，也是的父进程中的值发生改变，如果想改变共享数据段中的变量值，应该先拷贝父进程

fork和vfork的区别

• fork产生子进程不共享地址空间，vfork产生子进程共享地址空间

• fork不阻塞，父子进程可以同时执行，vfork阻塞，父进程要等待子进程执行完才能执行

• fork后子进程和父进程的执行顺序不一定，vfork后子进程先执行，待到子进程退出后父进程才开始执行

进程等待

• 为什么要等待？

  1.子进程退出，如果父进程不管不顾，可能造成僵尸问题，造成内存泄漏

  2.一旦变成僵尸状态，kill -9都无能为力，因为没有谁可以杀死一个死去了的进程

  3.父进程需要知道子进程完成任务的情况（对错与否，有没有异常退出等）

  4.父进程需要通过进程等待的方式回收子进程的资源，获取退出信息

• 怎么等待？（两个接口函数）

  wait系统调用

  #include<sys/types.h>
  #include<sys/wait.h>
  pid_t wait(int* status)
  

  参数：status输出型参数，整型指针，指向的空间存放的是子进程退出的状态，获取子进程状态，不关心可以设置为NULL

  返回值：pid_t类型，如果返回值大于0，说明等待成功，返回的是子进程的ID，可以通过status查看子进程的退出状态；如果返回值等于-1，则说明等待失败（可能wait的进程本身没有子进程）

  该方式为阻塞式等待，父进程什么都不做在等待子进程退出，如果没有子进程退出，父进程会一直等；如果父进程收到SIGCHLD信号，该函数就会立马返回立马清理。

  —

  waitpid系统调用

  #include<sys/types.h>
  #include<sys/wait.h>
  pid_t waitpid(pid_t pid, int* status, int options)
  

  参数：pid表示要等待的是哪个进程，status仍然是个输出型参数，存放子进程的退出码，options是一个选项，如果options设置为0，那么这个函数就是阻塞式等待，如果设置为WNOHANG，则函数为非阻塞式等待（发现已经没有退出的子进程可以收集）

  返回值：返回值大于0，等待成功，返回子进程的id，返回值等于0，表示发现等待的子进程没有退出，返回值等于-1，调用失败

  如果参数pid设置为-1,则表示等待任意子进程，和wait等效

  —

  wait和waitpid的区别？

  1. wait是阻塞式等待，waitpid可自行选择（options为0阻塞，options为WNOHANG为非阻塞）

  2. wait等待的是任意子进程（等到谁就是谁），waitpid等待的是参数pid传进来的确定子进程

进程程序替换

• 替换原理
  fork创建子进程执行的是和父进程相同的程序（也有可能是某个分支），通常fork出的子进程是为了完成父进程所分配的任务，所以子进程通常会调用一种exec函数（六种中的任何一种）来执行另一个任务。当进程调用exec函数时，当前用户空间的代码和数据会被新程序所替换，该进程就会从新程序的启动历程开始执行。在这个过程中没有创建新进程，所以调用exec并没有改变进程的id。

• 替换过程(图解)
  

• 替换函数（exec簇）—六种

#include<unistd.h>
int execl(const char* path, const char* arg, ···)
int execlp(const char* file, const char* arg, ···)
int execle(const char* path, const char* arg, ···, char* const envp[])
int execv(const char* path, char* const argv[])
int execvp(const char* file, char* const argv[])
int execve(const char* path, char* const argv[], char* const envp[])

函数特点

1. 这些函数如果调用成功，则加载的新程序从启动代码开始执行，不再返回
2. 如果调用出错返回-1
3. exec系列函数成功调用没有返回值，调用失败才有返回值

命名规律

1. l(list)：表示参数采用列表
2. v(vector)：表示参数采用数组
3. p(path)：自动搜索环境变量PATH
4. e(env)：自己维护环境变量（自己组装环境变量）

• 六个函数之间的关系
  事实上，只有execve是系统调用，其他五个最终都调用execve。
  

• 拓展：写简易shell的需要循环的步骤

  1. 获取命令行
  2. 解析命令行
  3. 创建子进程（fork）
  4. 进行程序替换—替换子进程（execve）
  5. 父进程等待子进程退出（wait）

进程终止

• 终止方式

  1.正常终止，结果正确

  2.正常终止，结果错误

  3.异常终止

• 终止方法

  1.正常终止（可以通过echo $?查看进程退出码）

  • 调用_exit函数

  #include <unistd.h>
  void _exit(int status)
  
  参数：status定义了进程终止状态，父进程通过wait来获取
  注意：虽然status是int，但只有低八位可以被父进程使用
       证明：_exit(-1)时，执行echo $?返回值255 
  

  • 调用exit函数

  #include <unistd.h>
  void exit(int status)
  
  exit函数做了以下事情，最终调用了_exit函数：
  1. 执行用户通过ataxia或on_exit定义的清理函数
  2. 冲刷缓存，将所有缓存数据写入，并且关闭所有打开的流
  3. 调用_exit函数
  

  

  • main函数返回（return退出）

  return是一种更常见的退出进程的方法
  main函数运行时，exit函数会将main返回值当作参数
  return n则相当于exit(n)。
  

  2.异常退出

    ctrl + c 信号终止
  

进程地址空间

• 对于一个进程空间分布图如下：
  

• 引子：猜猜下面输出结果，为什么呢？

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int g_val = 0;
int main() {
     pid_t id = fork();
     if(id < 0){
         perror("fork");
return 0; }
     else if(id == 0){ //child
         printf("child[%d]: %d : %p\n", getpid(), g_val, &g_val);
     }else{ //parent
         printf("parent[%d]: %d : %p\n", getpid(), g_val, &g_val);
     }
     sleep(1);
     return 0;
}

输出结果：
parent[2995]: 0 : 0x80497d8
child[2996]: 0 : 0x80497d8

由上可以发现，父子进程变量值和地址一模一样，因为子进程是以父进程为模版，并且父子进程都没有对变量进行修改
修改一下代码（如下），看看结果

```
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int g_val = 0;
int main() {
    pid_t id = fork();
    if(id < 0){
        perror("fork");
    return 0; }
    else if(id == 0){ //child
        printf("child[%d]: %d : %p\n", getpid(), g_val, &g_val);
    }else{ //parent
        printf("parent[%d]: %d : %p\n", getpid(), g_val, &g_val);
    }
    sleep(1);
    return 0;
}

输出结果：
child[3046]: 100 : 0x80497e8 
parent[3045]: 0 : 0x80497e8
我们发现，父子进程，输出地址是一致的，但是变量内容不一样!

```

• 结合上面两个例子我们可以总结出以下结论：
  1. 变量内容不一样,所以⽗子进程输出的变量绝对不是同⼀个变量
  2. 但地址值是⼀样的，则该地址绝对不是物理地址
  3. 在Linux地址下，这种地址叫做虚拟地址
  4. 我们在⽤C/C++语⾔言所看到的地址，全部都是虚拟地址，物理地址，⽤户一概看不到，由OS统⼀管理

• 早期内存管理原理：

  1. 要运⾏一个程序，会把这些程序全都装⼊内存
  2. 当计算机同时运⾏多个程序时，必须保证这些程序用到的内存总量要⼩于计算机实际物理内存的⼤⼩问题:
  3. 进程地址空间不隔离。由于程序都是直接访问物理内存，所以恶意程序可以随意修改别的进程的内存数据，以达到破坏的目的
  4. 内存使⽤效率低。在 A 和 B 都运⾏的情况下，如果⽤户⼜运⾏了程序 C ，⽽程序 C 需要 15M ⼤ ⼩的内存才能运⾏，而此时系统只剩下 4M 的空间可供使⽤，所以此时系统必须在已运⾏的程序中 选择一个将该程序的数据暂时拷⻉到硬盘上，释放出部分空间来供程序 C 使⽤，然后再将程序 C 的数据全部装入内存中运⾏
  5. 程序运⾏的地址不确定。当内存中的剩余空间可以满足程序 C 的要求后，操作系统会在剩余空间中随机分配一段连续的 20M ⼤⼩的空间给程序 C 使⽤，因为是随机分配的，所以程序运⾏的地址是不确定的，这种情况下，程序的起始地址都是物理地址，⽽而物理地址都是在加载之后才能确定。

  由于以上机制存在问题，于是后来使用分段来解决这些问题

• 分段

  1. 在编写代码的时候，只要指明了所属段，代码段和数据段中出现的所有的地址，都是从0零开始，映射关系完全由操作系统维护
  2. CPU将内存分割成了不同的段，于是指令和数据的有效地址并不是真正的物理地址⽽是相对于段⾸地址的偏移地址

  解决问题:

  1. 因为段寄存器的存在，使得进程的地址空间得以隔离，越界问题很容易被判定出来
  2. 实际代码和数据中的地址，都是偏移量，所以第一条指令可以从0地址开始，系统会⾃动进⾏转化映射，也就解决了程序运⾏的地址不确定的问题。
  3. 可是，分段并没有解决性能问题，在内存空间不⾜的情况下，依旧要换⼊唤出整个程序或者整个段，⽆疑要造成内存和硬盘之间拷⻉⼤量数据的情况，进⽽导致性能问题。

  分段仍然存在一些问题，于是引进了分页和虚拟地址概念

• 分页&虚拟地址空间

  页表：实现从页号到物理块号的地址映射

  虚拟内存基本思想：每个进程有用独立的逻辑地址空间，内存被分为大小相等的多个块,称为页(Page).每个页都是一段连续的地址。对于进程来看,逻辑上貌似有很多内存空间，其中一部分对应物理内存上的一块(称为页框，通常页和页框大小相等)，还有一些没加载在内存中的对应在硬盘上

  创建进程，虚拟地址和物理地址之间的映射关系
  
  上面的图说明：同一个变量，地址相同，其实是虚拟地址相同，内容不同其实是被映射到了不同的物理地址!

  过程：当访问虚拟内存时，会访问MMU（内存管理单元）去匹配对应的物理地址，而如果虚拟内存的页并不存在于物理内存中，会产生缺页中断，从磁盘中取得缺的页放入内存，如果内存已满，还会根据某种算法将磁盘中的页换出。（MMU中存储页表，用来匹配虚拟内存和物理内存）

  二级页表：因为页表中每个条目是4字节，现在的32位操作系统虚拟地址空间是2^32次方，假设每页分为4k，也需(2^32/(4*2^10))*4=4M的空间，为每个进程建立一个4M的页表并不明智。因此在页表的概念上进行推广，产生二级页表，虽然页表条目没有减少，但内存中可以仅仅存放需要使用的二级页表和一级页表，大大减少了内存的使用。

  缺页中断：虚拟内存的页并不存在于物理内存中，会产生缺页中断。处理中断地址转换➕更新（地址转换：有空闲块儿，调入页面，没有利用置换算法替换出去一个；更新页表，重启该命令，检索页表，命中物理块儿，运算得出物理地址）

• 拓展
  CPU把虚拟地址转换成物理地址：一个虚拟地址，大小4个字节(32bit)，分为3个部分：第22位到第31位这10位（最高10位）是页目录中的索引，第12位到第21位这10位是页表中的索引，第0位到第11位这12位（低12位）是页内偏移。一个一级页表有1024项，虚拟地址最高的10bit刚好可以索引1024项（2的10次方等于1024）。一个二级页表也有1024项，虚拟地址中间部分的10bit，刚好索引1024项。虚拟地址最低的12bit（2的12次方等于4096），作为页内偏移，刚好可以索引4KB，也就是一个物理页中的每个字节。

  页面替换算法：物理内存是极其有限的，当虚拟内存所求的页不在物理内存中时，将需要将物理内存中的页替换出去，选择哪些页替换出去就显得尤为重要。

  最佳置换算法(Optimal Page Replacement Algorithm)：将未来最久不使用的页替换出去，这听起来很简单，但是无法实现。但是这种算法可以作为衡量其它算法的基准。

  最近不常使用算法(Not Recently Used Replacement Algorithm)：这种算法给每个页一个标志位，R表示最近被访问过，M表示被修改过。定期对R进行清零。这个算法的思路是首先淘汰那些未被访问过R=0的页，其次是被访问过R=1,未被修改过M=0的页，最后是R=1,M=1的页。

  先进先出页面置换算法(First-In,First-Out Page Replacement Algorithm)：淘汰在内存中最久的页，这种算法的性能接近于随机淘汰。并不好。

  改进型FIFO算法(Second Chance Page Replacement Algorithm)：这种算法是在FIFO的基础上，为了避免置换出经常使用的页，增加一个标志位R，如果最近使用过将R置1，当页将会淘汰时，如果R为1，则不淘汰页，将R置0.而那些R=0的页将被淘汰时，直接淘汰。

  时钟替换算法(Clock Page Replacement Algorithm)：虽然改进型FIFO算法避免置换出常用的页，但由于需要经常移动页，效率并不高。因此在改进型FIFO算法的基础上，将队列首位相连形成一个环路，当缺页中断产生时，从当前位置开始找R=0的页，而所经过的R=1的页被置0，并不需要移动页。

  最久未使用算法(LRU Page Replacement Algorithm)：LRU算法的思路是淘汰最近最长未使用的页。这种算法性能比较好，但实现起来比较困难。

进程间通信

一组编程接口，让程序员能够协调不同的进程，使之能在一个操作系统里同时运行，并能够相互传递交换信息

为什么要通信（重点）

• 数据传输：一个进程需要将它的数据发送到另一个进程

• 资源共享：多个进程之间需要共享资源

• 事件通知：一个进程要向另一个或者一组进程发送消息，通知它（们）发生的事件（比如进程终止要通知父进程）

• 进程控制：有些进程需要完全控制另一个进程（如Debug进程），此时，控制进程希望能够拦截它想控制的进程的所有的陷入和异常，并能够及时知道其状态的改变

怎么通信（主要三种方式），通信本质（重点）

管道（Unix中最古老的进程间通信的方式）

我们把一个进程连接到另一个进程的一个数据流称为管道

• 匿名管道（通常就叫管道）

  创建方法
  #include <unistd.h>
  int pipe(int fd[2])
  
  参数：文件描述符数组，fd[0]表示读端，fd[1]表示写端
  返回值：成功返回0，失败返回错误代码
  

  特点：
  1. 单向传输（单工），只能在父子进程间或兄弟进程间使用
  2. 管道是临时对象
  3. 管道和文件的使用方法类似，都能使用read、write、open等普通IO函数
  4. 管道面向字节流，即提供流式服务
  5. 一般来讲，管道生命周期随进程，进程退出，管道释放
  6. 一般来讲，内核会对管道操作进行同步与互斥
  7. 本质上Linux上的管道是通过空文件夹实现的
  8. 事实上，管道使用的文件描述符、文件描述符、文件指针最终都会转化成系统内核中SOCKET描述符，都收到了SOCKET描述符的限制
  9. 补充：Linux中，用两个file数据结构来实现管道

• 命名管道

  创建方法
  $ mkfifo filename //命令行创建
  
  int mkfifo(count char* filename, mode_t mode)//函数
  

  特点：

  1. 命名管道也是单向传输，但它可以在不相关的进程间使用
  2. 命名管道不是临时对象，它们是文件系统真正的实体
  3. Linux下，在写进程打开命名管道之前，必须处理读进程对命名管道的打开，在写进程写数据之前，也必须处理处理读进程对管道的读
  4. 除了以上的特点与管道不同，其他的都是都与管道一样，包括数据结构和操作

  匿名管道和命名管道的区别？

  答：匿名管道只能在父子进程间或兄弟进程间使用，命名管道可以在不相关的进程间使用；匿名管道是临时对象，命名管道是文件系统真正的实体；匿名管道和命名管道打开和关闭方式不同。

• 管道的缺陷

  1. 管道读数据的同时也将数据移除，所以管道不能对多个接收者广播数据
  2. 管道中的数据被当作字节流，所以无法识别信息的边界
  3. 如果一个进程中有多个读进程，写进程无法发送到指定的读进程，如果有多个写进程，无法知道数据是哪一个发送的

系统IPC（System V IPC资源生命周期随内核）

• 消息队列

  提供了一个由一个进程向另外一个进程发送一块数据的方法

  特点：
  1. 消息队列是随内核，只有重启和手动删除才会被真正的删除
  2. 每个数据块都被认为是有个类型，接受者进程接受的数据块可以是不同类型值
  3. 每个消息是有最大长度的上限的，每个消息队列的字节数也是有上限的，系统上消息队列数也有上限
  4. 可用于机器上的任何进程间通信

  消息队列与管道的区别：
  1. 提供有格式的字节流，减少开发人员的工作量
  2. 消息具有类型，实际应用中，可以当做优先级使用
  3. 消息队列随内核，生命周期比管道长，应用空间更大

• 共享内存

  由一个进程创建，其余进程对这块内存进行读写

  特点：

  1. 最快的IPC形式
  2. 进程间数据传递不再涉及到内存（不执行进入系统的内核调用来传递彼此的数据）
  3. Linux无法对共享内存进行同步，需要程序自己对共享内存做同步运算，这种运算很多时候就是通过信号量来实现的

• 信号量

  主要用于同步与互斥

  1. 进程互斥

     1. 由于有些进程需要共享资源，而且需要互斥使用，所以个进程竞争使用这些资源，这种关系被称为进程互斥
     2. 系统中某些进程一次只能被一个进程使用，称这样的资源为临界资源或者互斥资源
     3. 在进程中涉及互斥资源的的程序段叫做临界区

  2. 进程同步
     多个进程需要配合完成同一个任务

  3. 信号量和P、V原语

     1. 由Dijkstra提出
     2. 信号量
        1. 互斥：P、V在同一个进程
        2. 同步：P、V在不同的进程
     3. 信号量值的含义
        1. S>0：表示可用资源个数
        2. S=0：表示没有可以用的资源，无等待进程
        3. S<0：表示等待队列中有|S|个进程

套接字（socket）

• TCP用主机的ip地址加上主机上的端口号作为TCP连接的端点，这种端点就叫做套接字或插口

• 用（IP地址：端口号）表示

• 特点：

  1. 是网络通信过程中端点的抽象表示，是支持TCP/IP的网络通信的基本操作单元
  2. 包含进行网络通信必须的五种信息：连接使用的协议、本地主机的IP地址、本地进程的协议端口、远地主机的IP地址、远地进程的协议端口
  3. 在所有提供了TCP/IP协议栈的操作系统都适用，且编程方法几乎一样
  4. 要通过Internet进行通信，至少需要一对套接字

进程与文件（重点）

进程打开文件的本质

当我们打开文件时，操作系统在内存中要创建相应的数据结构来描述目标文件。于是就有了file结构体。表⽰⼀个已经打开的文件对象。而进程执行open系统调⽤，所以必须让进程和文件关联起来。每个进程都有⼀个指针*files, 指向⼀张表files_struct,该表最重要的部分就是包涵一个指针数组，每个元素都是一个指向打开文件的指针!所以，本质上，文件描述符就是该数组的下标。所以，只要拿着文件描述符，就可以找到对应的文件。

文件描述符的本质

本质是数组元素的下标，每个进程都对应一张文件描述符表，该表可视为指针数组，给数组的元素指向文件表的一个元素，数组元素的下标就是大名鼎鼎的文件描述符



图详解：

1.右侧的表称为i节点表，在整个系统中只有1张。该表可以视为结构体数组，该数组的一个元素对应于一个物理文件。
2.中间的表称为文件表，在整个系统中只有1张。该表可以视为结构体数组，一个结构体中有很多字段，其中有3个字段比较重要：

file status flags
用于记录文件被打开来读的，还是写的。其实记录的就是open调用中用户指定的第2个参数
current file offset
用于记录文件的当前读写位置（指针）。正是由于此字段的存在，使得一个文件被打开并读取后，
下一次读取将从上一次读取的字符后开始读取
v-node ptr
该字段是指针，指向右侧表的一个元素，从而关联了物理文件。

3.左侧的表称为文件描述符表，每个进程有且仅有1张。该表可以视为指针数组，数组的元素指向文件表的一个元素。最重要的是：数组元素的下标就是大名鼎鼎的文件描述符。
4.open系统调用执行的操作：新建一个i节点表元素，让其对应打开的物理文件（如果对应于该物理文件的i节点元素已经建立，就不做任何操作）；新建一个文件表的元素，根据open的第2个参数设置file status flags字段，将current file offset字段置0，将v-node ptr指向刚建立的i节点表元素；在文件描述符表中，寻找1个尚未使用的元素，在该元素中填入一个指针值，让其指向刚建立的文件表元素。最重要的是：将该元素的下标作为open的返回值返回。
5.这样一来，当调用read（write）时，根据传入的文件描述符，OS就可以找到对应的文件描述符表元素，进而找到文件表的元素，进而找到i节点表元素，从而完成对物理文件的读写。

文件描述符与C FILE*的关系，理解系统调用与库函数

每个进程都有⼀个指针*files, 指向⼀张表files_struct,该表最重要的部分就是包涵一个指针数组，每个元素都是一个指向打开文件的指针，文件描述符就是该数组的下标。

系统调用与库函数
可以认为，f#系列的函数(库函数)，都是对系统调⽤的封装，方便⼆次开发。

站在系统角度，常见的文件操作接口的使用

open系统调用执行的操作：新建一个i节点表元素，让其对应打开的物理文件（如果对应于该物理文件的i节点元素已经建立，就不做任何操作）；新建一个文件表的元素，根据open的第2个参数设置file status flags字段，将current file offset字段置0，将v-node ptr指向刚建立的i节点表元素；在文件描述符表中，寻找1个尚未使用的元素，在该元素中填入一个指针值，让其指向刚建立的文件表元素。最重要的是：将该元素的下标作为open的返回值返回。

read（write）时，根据传入的文件描述符，OS就可以找到对应的文件描述符表元素，进而找到文件表的元素，进而找到i节点表元素，从而完成对物理文件的读写

open close read write lseek都属于系统提供的接⼝，称之为系统调⽤接⼝

文件描述符重定向的本质与操作

1.linux用文件描述符来标识每个文件对象，文件描述符是一个非负整数，可以唯一地标识会话中打开的文件，每个过程一次最多可以有9个文件描述符；

2.0=>STDIN=>标准输入；1=>STDOUT=>标准输出；2=>STDERR=>标准错误；

3.STDIN：STDIN文件描述符代表shell的标准输入，对终端界面来说，标准输入是键盘，在使用输入重定向时（<），linux会用重定向指定的文件来替换标准输入文件描述符，它会读取文件并提取数据，如同它是在键盘上输入的；

4.STDOUT：STDOUT文件描述符代表标准的shell输出，在终端界面上，标准输出就是终端显示器，shell的所有输出会被重定向到标准输出中，也就是显示器，在使用输出重定向（>）时，linux会用重定向指定的文件来替换标准输出文件描述符，>>表示追加到文件；

5.STDERR：STDERR文件描述符代表shell的标准错误输出，默认情况下，STDERR文件描述符会和STDOUT文件描述符指向同样的地方，即：错误消息也会输出到显示器输出中，使用2>file，可以只将错误消息输出至文件file中，使用&>file可将标准输出和错误消息都重定向至文件file；

理解文件系统中inode的概念

• 概念：inode就是索引节点，它用来存放档案及目录的基本信息，包含时间、档名、使用者及群组等

• inode 是 UNIX 操作系统中的一种数据结构，其本质是结构体

• 在 Linux 中，索引节点结构存在于系统内存及磁盘，其可区分成 VFS inode 与实际文件系统的 inode。

• VFS inode 作为实际文件系统中 inode 的抽象，定义了结构体 inode 与其相关的操作 inode_operations

  Linux 中 VFS inode
  include/linux/fs.h
  
  struct inode { 
  ... 
  const struct inode_operations   *i_op; // 索引节点操作
  unsigned long           i_ino;      // 索引节点号
  atomic_t                i_count;    // 引用计数器
  unsigned int            i_nlink;    // 硬链接数目
  ... 
  } 
  
  struct inode_operations { 
  ... 
  int (*create) (struct inode *,struct dentry         *,int, struct nameidata *); 
  int (*link) (struct dentry *,struct inode *,struct dentry *); 
  int (*unlink) (struct inode *,struct dentry *); 
  int (*symlink) (struct inode *,struct dentry *,const char *); 
  int (*mkdir) (struct inode *,struct dentry *,int); 
  int (*rmdir) (struct inode *,struct dentry *); 
  ... 
  }
  

1. Linux 中 VFS inode

   • 每个文件存在两个计数器：i_count 与 i_nlink，即引用计数与硬链接计数
   • i_count 用于跟踪文件被访问的数量，而 i_nlink 则是上述使用 ls -l 等命令查看到的文件硬链接数
   • 当文件被删除时，则 i_nlink 先被设置成 0
   • 文件的这两个计数器使得 Linux 系统升级或程序更新变的容易
   • 系统或程序可在不关闭的情况下（即文件 i_count 不为 0），将新文件以同样的文件名进行替换，新文件有自己的 inode 及 data block，旧文件会在相关进程关闭后被完整的删除

2. 文件系统 ext4 中的 inode

   ext4 中的 inode
   
   struct ext4_inode { 
   ... 
   __le32  i_atime;        // 文件内容最后一次访问时间
   __le32  i_ctime;        // inode 修改时间
   __le32  i_mtime;        // 文件内容最后一次修改时间
   __le16  i_links_count;  // 硬链接计数
   __le32  i_blocks_lo;    // Block 计数
   __le32  i_block[EXT4_N_BLOCKS];  // 指向具体的 block 
   ... 
   };
   

   • 三个时间的定义可对应与命令 stat 中查看到三个时间

   • i_links_count 不仅用于文件的硬链接计数，也用于目录的子目录数跟踪（目录并不显示硬链接数，命令 ls -ld 查看到的是子目录数）

   • 文件系统 ext3 对 i_links_count 有限制，其最大数为：32000（该限制在 ext4 中被取消）

理解软硬链接及其区别

硬链接

• 概念：硬链接(hard link, 也称链接)就是一个文件的一个或多个文件名，其中一个修改后，所有与其有硬链接的文件都一起修改了

• 特点

  （1）文件有相同的 inode 及 data block
  （2）只能对已存在的文件进行创建
  （3）硬链接文件不占用存储空间
  （4）硬链接文件不能跨文件系统
  （5）不能对目录文件进行创建硬链接操作
  （6）硬链接只能引用同一文件系统中的文件。它引用的是文件在文件系统中的物理索引(也称为 inode)
  （7）移动或删除原始文件时，硬链接不会被破坏，因为它所引用的是文件的物理数据而不是文件在文件结构中的位置
  （8）硬链接的文件不需要用户有访问原始文件的权限，也不会显示原始文件的位置，这样有助于文件的安全
  （9）删除的文件有相应的硬链接，那么这个文件依然会保留，直到所有对它的引用都被删除

软链接

• 概念：软链接又叫符号链接，这个文件包含了另一个文件的路径名。可以是任意文件或目录，可以链接不同文件系统的文件

• 特点

  （1）软链接有自己的文件属性及权限等
  （2）可对不存在的文件或目录创建软链接（链接文件可以链接不存在的文件，这就产生一般称之为”断链”的现象）
  （3）软链接可交叉文件系统
  （4）软链接可对文件或目录创建
  （5）创建软链接时，链接计数 i_nlink 不会增加
  （6）链接文件可以循环链接自己，类似于编程语言中的递归。
  （7）删除软链接并不影响被指向的文件
  （8）软链接文件只是被指向的源文件的一个标记，当删除了源文件后，链接文件不能独立存在，虽然仍保留文件名，但却不能查看软链接文件的内容了，成为了死链接
  （9）被指向路径文件被重新创建，死链接可恢复为正常的软链接

硬链接和软链接的区别

• 硬链接文件有相同的 inode 及 data block；软连接文件有自己的 inode 及 data block 等文件属性
• 硬链接文件只能对已存在的文件进行创建；软链接文件可对不存在的文件或目录创建软链接
• 硬链接不可交叉文件系统；软链接可交叉文件系统
• 硬链接不可对文件或目录创建；软链接可对文件或目录创建
• 移动或删除原始文件时，硬链接不会被破坏；删除了源文件后，链接文件不能独立存在
• 软链接文件相比硬链接文件占用存储空间更大

理解动态与静态库

静态库

• 概念

  • 静态库是指在我们的应用中，有一些公共代码是需要反复使用，就把这些代码编译为“库”文件；在链接步骤中，连接器将从库文件取得所需的代码，复制到生成的可执行文件中的这种库

• 特点

  • 可执行文件中包含了库代码的一份完整拷贝

  • 静态库的代码是在编译过程中被载入程序中

• 缺点

  • 就是被多次使用就会有多份冗余拷贝

动态库（动态链接库）

• 概念

  • 动态链接提供了一种方法，使进程可以调用不属于其可执行代码的函数

• 特点

  • 函数的可执行代码位于一个 DLL 中，该 DLL 包含一个或多个已被编译、链接并与使用它们的进程分开存储的函数

  • DLL 还有助于共享数据和资源

  • 多个应用程序可同时访问内存中单个DLL 副本的内容

  • DLL 是一个包含可由多个程序同时使用的代码和数据的库，Windows下动态库为.dll后缀，在linux下为.so后缀

Linux下静态库和动态库区别

1. 命名上：静态库文件名的命名方式是“libxxx.a”,库名前加”lib”，后缀用”.a”，“xxx”为静态库名；动态库的命名方式与静态库类似，前缀相同，为“lib”，后缀变为“.so”。所以为“libmytime.so”

2. 链接上：静态库的代码是在编译过程中被载入程序中；动态库在编译的时候并没有被编译进目标代码，而是当你的程序执行到相关函数时才调用该函数库里的相应函数

3. 更新上：如果所使用的静态库发生更新改变，你的程序必须重新编译；动态库的改变并不影响你的程序，动态函数库升级比较方便

4. 当同一个程序分别使用静态库，动态库两种方式生成两个可执行文件时，静态链接所生成的文件所占用的内存要远远大于动态链接所生成的文件

5. 内存上：静态库每一次编译都需要载入静态库代码，内存开销大；系统只需载入一次动态库，不同的程序可以得到内存中相同的动态库的副本，内存开销小

6. 静态库和程序链接有关和程序运行无关；动态库和程序链接无关和程序运行有关

进程与线程（重点）

站在操作系统管理角度，理解什么是线程

线程是不拥有独立资源空间的程序执行流的最小单位

站在进程地址空间角度，理解什么是线程

线程是进程中的实体，是进程内部的控制序列，和该进程内的其他线程共享地址空间和资源

站在执行流角度，理解什么是线程

线程是程序中一个单一的顺序控制流程，是程序执行流的最小单位

如何理解线程是进程内部的一个执行分支

• 原因

  1. 60年代，在OS中能拥有资源和独立运行的基本单位是进程，然而随着计算机技术的发展，进程出现了很多弊端，由于进程是资源拥有者，创建、撤消与切换存在较大的时空开销，因此需要引入轻型进程；

  2. 对称多处理机（SMP）出现，可以满足多个运行单位，而多个进程并行开销过大，因此在80年代，出现了能独立运行的基本单位——线程（Threads）

• 进程就是一棵树，我们的线程就是其中的一个个分支，没有了线程，进程并不能执行任何操作。我们进程的具体操作最后还是分配给每一个线程来执行。相对于线程，我们甚至可以把进程理解为线程的一个容器，它代表线程来接受分配到的资源，为线程提供执行代码，所以进程是资源分配的基本单位。

进程与线程有什么区别

体区别点击这里进来

Linux下线程有什么特点

• 线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证独立运行的资源。

• 独立调度和分派的基本单位

• 多个线程可并发执行（同个或不同进程中均可以）

• 多个线程共享同个进程的资源和地址空间。

• 线程是动态概念，它的动态特性由线程控制块TCB（线程状态、当线程不运行时被保存的现场资源、一组执行堆栈、存放每个线程的局部变量主存区、访问同一个进程中的主存和其它资源）描述。

Linux下，pthread库如何控制线程

简单来说是通过pthread簇函数来控制，常见的必不可少的就是创建和终止，具体如下：

创建线程(pthread_create)

#include <pthread.h>
 
int pthread_create(pthread_t *restrict thread,/
                   const pthread_attr_t * restrict attr, /
                   void *(*start_routine)(void *),/
                   void * restrict arg);
                   
返回值:成功返回0，失败返回错误号。
其他的系统函数都是成功返回0，失败返回-1，而错误号保存在全局变量errno中。
pthread库的函数都是通过返回值返回错误号
虽然每个线程也都有一个errno，但这是为了兼容其他函数接口而提供的
pthread库本身并不使用它，通过返回值返回错误码更加清晰。

注意：gcc编译时要加上选项 -lpthread

• 执行过程：在一个线程中调用pthread_create()创建线程后，当前线程从pthread_create()返回继续往下执行，而新的线程所执行的代码由我们传给pthread_create的函数指针start_routine决定。start_routine函数接收一个参数，是通过ptherad_create的arg参数传递给它的，该参数的类型为void *，这个指针按什么类型解释由调用者自己定义。start_routine的返回值类型也是void *，这个指针的含义同样由调用者自己定义。start_routine返回时，这个线程就退出了，其他线程可以调用pthread_join得到start_routine的返回值，类似于父进程调用wait()得到子进程的退出状态。

• 成功返回： pthread_create成功返回后，新创建的线程的id被填写到thread参数所指向的内存单元。进程id的类型是pid_t，每个进程的id在整个系统中是唯一的，调用getpid()可以获得当前进程的id，是一个正整数值。线程id的类型是thread_t，它只在当前进程中保证是唯一的，在不同的系统中thread_t这个类型有不同的实现，他可能是一个整数值，也可能是一个结构体，也可能是一个地址，所以不能简单的当成整数用printf打印，调用pthread_self()可以获得当前线程的id。

• 总结

  1. 在linux上，thread_t类型是一个地址值，属于同一进程的多个线程调用getpid()可以得到相同的进程号,而调用pthread_self()得到的线程号各不相同

  2. 由于pthread_create的错误码不保存在errno中，因此不能直接用perror()打印错误信息，可以先用strerror()把错误码转成错误信息再打印

  3. 如果任意一个线程调用了exit或_exit，则整个进程的所有线程都终止，由于从main函数return也相当于调用exit，为了防止新创建的线程还没有得到执行就终止，我们在main函数return之前延时1秒，但是即使主线程等待1秒钟，内核也不一定会调度新创建的线程执行。

终止线程

• 只终止线程而不终止进程的方法有三种

  • return(从线程函数return)。主线程return相当于调用了exit。

  • 调用pthread_exit函数。

  • 调用pthread_cancel函数（一个线程可以调用pthread_cancel函数终止同一进程中的另一线程）

• 终止函数

  #include <pthread.h>
  void pthread_exit(void *value_ptr);
  
   value_ptr是void *类型，和线程函数返回值的用法一样，其他线程可以调用pthread_join获得这个指针
   
   pthread_exit或者return返回的指针所指向的内存单元必须是全局的或者是用malloc分配的
   
   不能在线程函数的栈上分配，因为当其他线程得到这个返回指针时线程函数已经退出了
  

  在这里需要用到pthread_join函数所以引入线程等待的概念线程等待

  通常情况下，线程终止后，其终止状态一直保留到其它线程调用pthread_join获取它的状态为止。

  线程也可以被置为detach状态，这样的线程一旦终止就立刻回收它所占用的所有资源，而不保留终止状态。

  不能对一个已经处于detach状态的线程调用pthread_join,这样的调用将返回EINVAL。

  对一个尚未detach的线程调用pthread_join或pthread_detach都可以把该线程置为detach状态

  不能对同一线程重复调用pthread_join

  对一个线程调用pthread_detach就不能再调用pthread_join了。

  #include <pthread.h>
  int pthread_detach(pthread_t tid);
  返回值：成功返回0，失败返回错误号。
  

为什么线程等待，如何等待

• 为什么需要线程等待（WHY）?

  1. 已经退出的线程，其空间没有被释放，仍然在进程的地址空间内。

  2. 创建新的线程不会复⽤刚才退出线程的地址空间

• 如何等待（HOW）？

  功能:等待线程结束 原型
  #include <pthread.h>
  int pthread_join(pthread_t thread, void **value_ptr);
  
  参数 thread:线程ID
  value_ptr:它指向⼀一个指针，后者指向线程的返回值 
  返回值:成功返回0;失败返回错误码
  
  

  调用该函数的线程将挂起等待，直到id为thread的线程终止
  
  thread线程以不同的方法终止，通过pthread_join得到的终止状态是不同的：
  1. 如果thread线程通过return返回，value_ptr所指向的单元里存放的是thread线程函数
  

的返回值

2. 如果thread线程被别的线程调用pthread_cancel异常终止掉，value_ptr所指向的单元

里存放的是常数PTHREAD_CANCELED（pthread库中常数PTHREAD_CANCELED的值是-1）

define PTHREAD_CANCELED ((void *)-1)

3. 如果thread线程是自己调用pthread_exit终止的，value_ptr所指向的单元存放的是传

给pthread_exit的参数

注意：如果对thread线程的终止状态不关心，可以传NULL给value_ptr参数

```

如何分离线程，为何要分离

• 什么是线程分离（WHAT）

  简单来讲，线程分离就是当线程被设置为分离状态后，线程结束时，它的资源会被系统自动的回收，而不再需要在其它线程中对其进行 pthread_join() 操作。

• 为什么线程分离（WHY）

  在我们使用默认属性创建一个线程的时候，线程是 joinable 的。 joinable 状态的线程，必须在另一个线程中使用 pthread_join() 等待其结束，如果一个 joinable 的线程在结束后，没有使用 pthread_join() 进行操作，这个线程就会变成”僵尸线程”。每个僵尸线程都会消耗一些系统资源，当有太多的僵尸线程的时候，可能会导致创建线程失败。

• 怎么分离（HOW）

  在前面讲到线程控制时提到了终止线程，其中就提到了detach状态，下面就是设置为detach状态的函数

  #include <pthread.h>
  int pthread_detach(pthread_t tid);
  返回值：成功返回0，失败返回错误号。
  
  注意：线程分离可以在创建的时候属性里面设置
  

  核心思想：

  1. 把一个线程的属性设置为 detachd 的状态，让系统来回收它的资源；
  2. 把一个线程的属性设置为 joinable 状态，这样就可以使用 pthread_join() 来阻塞的等待一个线程的结束，并回收其资源，并且pthread_join() 还会得到线程退出后的返回值，来判断线程的退出状态 。

什么叫做临界区，临界资源，原子性

• 临界资源：临界资源是一次仅允许一个进程使用的共享资源。各进程采取互斥的方式，实现共享的资源称作临界资源。属于临界资源的硬件有，打印机，磁带机等；软件有消息队列，变量，数组，缓冲区等。诸进程间采取互斥方式，实现对这种资源的共享。

• 临界区：每个进程中访问临界资源的那段代码称为临界区（criticalsection），每次只允许一个进程进入临界区，进入后，不允许其他进程进入。不论是硬件临界资源还是软件临界资源，多个进程必须互斥的对它进行访问。多个进程涉及到同一个临界资源的的临界区称为相关临界区。使用临界区时，一般不允许其运行时间过长，只要运行在临界区的线程还没有离开，其他所有进入此临界区的线程都会被挂起而进入等待状态，并在一定程度上影响程序的运行性能。

• 原子性：原子性是指一个操作是不可中断的，要么全部执行成功要么全部执行失败，有着“同生共死”的感觉。及时在多个线程一起执行的时候，一个操作一旦开始，就不会被其他线程所干扰。

什么叫做互斥与同步，为什么要引入互斥与同步机制

• 互斥：是指散步在不同任务之间的若干程序片断，当某个任务运行其中一个程序片段时，其它任务就不能运行它们之中的任一程序片段，只能等到该任务运行完这个程序片段后才可以运行。最基本的场景就是：一个公共资源同一时刻只能被一个进程或线程使用，多个进程或线程不能同时使用公共资源。

• 同步：是指散步在不同任务之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。最基本的场景就是：两个或两个以上的进程或线程在运行过程中协同步调，按预定的先后次序运行。比如 A 任务的运行依赖于 B 任务产生的数据。

• 引入互斥与同步机制原因：
  现代操作系统基本都是多任务操作系统，即同时有大量可调度实体在运行。在多任务操作系统中，同时运行的多个任务可能：

  1. 都需要访问/使用同一种资源
  2. 多个任务之间有依赖关系，某个任务的运行依赖于另一个任务

  这两种情形是多任务编程中遇到的最基本的问题，也是多任务编程中的核心问题，同步和互斥就是用于解决这两个问题的。

死锁以及死锁产生的4个必要条件

• 所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

• 产生死锁的原因：

  可归结为如下两点：

  a. 竞争资源

  • 系统中的资源可以分为两类：

    1. 可剥夺资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，CPU和主存均属于可剥夺性资源；
    2. 另一类资源是不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。

  • 产生死锁中的竞争资源之一指的是竞争不可剥夺资源（例如：系统中只有一台打印机，可供进程P1使用，假定P1已占用了打印机，若P2继续要求打印机打印将阻塞）

  • 产生死锁中的竞争资源另外一种资源指的是竞争临时资源（临时资源包括硬件中断、信号、消息、缓冲区内的消息等），通常消息通信顺序进行不当，则会产生死锁

  b. 进程间推进顺序非法

  • 若P1保持了资源R1,P2保持了资源R2，系统处于不安全状态，因为这两个进程再向前推进，便可能发生死锁

  • 例如，当P1运行到P1：Request（R2）时，将因R2已被P2占用而阻塞；当P2运行到P2：Request（R1）时，也将因R1已被P1占用而阻塞，于是发生进程死锁

• 产生死锁的必要条件：

  • 互斥条件
  • 请求和保持条件
  • 不剥夺条件
  • 环路等待条件。

如何避免死锁

• 三种用于避免死锁的技术：

  1. 加锁顺序（线程按照一定的顺序加锁）

     • 再多线程中，如果一个线程需要锁，那么他就必须要按照一定顺序获得锁

     thread a
     lock 1
     lock 2
     
     thread b
         等待 1//等待线程a中1加锁后才能对3上锁        
         lock 3(1已经被上锁)
     
     thread c
         //如果想获取锁1,2,3，则
         等待 1
         等待 2
         等待 3
         //然后才轮到该线程获取
     

     • 缺点：按照顺序加锁是一种有效的死锁预防机制，这种方式需要你事先知道所有可能会用到的锁和锁的顺序，但这个很难，并不一定所有的都能知道。

  2. 加锁时限（线程尝试获取锁的时候加上一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁）

     • 在尝试获取锁的时候加一个超时时间，这也就意味着在尝试获取锁的过程中若超过了这个时限该线程则放弃对该锁请求。

     • 若一个线程没有在给定的时限内成功获得所有需要的锁，则会进行回退并释放所有已经获得的锁，然后等待一段随机的时间再重试

     • 这段随机的等待时间让其它线程有机会尝试获取相同的这些锁，并且让该应用在没有获得锁的时候可以继续运行（可以做些其他的事）

     • 缺点：有时为了执行某个任务。某个线程花了很长的时间去执行任务，如果在其他线程看来，可能这个时间已经超过了等待的时限，可能出现了死锁。

  3. 死锁检测

     • 死锁检测是一个更好的预防死锁机制，针对的是那些不可能按序加锁且锁超时不可行的场景

     • 每当线程获取了锁，会在线程和锁相关的数据结构（map、graph等）中，同样，线程请求锁也需要记录在这个数据结构中

     • 当一个线程请求失败时，这个线程可以遍历锁的关系图看看是否有死锁发生，死锁一般要比两个线程互相持有对方的锁这种情况要复杂的多

     • 当检测出死锁时，一个可行的做法是释放所有锁，回退，并且等待一段随机的时间后重试，更好的方案是给这些线程设置优先级，让一个（或几个）线程回退，剩下的线程就像没发生死锁一样继续保持着它们需要的锁。

最具有代表性的避免死锁算法是银行家算法

• 银行家算法中的数据结构：
  ① 可利用资源向量 Available
  ② 最大需求矩阵Max
  ③ 分配矩阵 Allocation
  ④ 需求矩阵 Need
  三个矩阵间存在下述关系：

  Needp[i,j] = Max[i,j] –Allocation[i,j]

• 算法思想：
  （1）如果Request i[j] <= Need[i,j]，便转向步骤 （2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
  （2）如果Request i[j] <= Available[j]，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。
  （3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的值：

    Available[j]:=Available[j] – Request i[j];
    Allocation[i,j]:=Allocation[i,j] + Request i[j];
    Need[i,j]:=Need[i,j] – Request i[j];
  

（4）系统执行安全性算法，减产此次算法分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

• 安全性算法：
  （1）设置两个向量：

  ① 工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。
  ② Finish，表示系统是否有足够的资源分配给进程，使之运行完成。开始时限做Finish[i]:=false；当有足够资源分配给进程时，再令Finish[i]:=true。
  （2）从进程集合中找到一个能满足下述条件的进程：

  ① Finish[i] = false；
  ② Need[i,j] <= Work[j]；
  若找到，执行步骤（3），否则，执行步骤（4）

  （3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

    Work[j]:=Work[j] + Allocation[i,j];
    Finish[i]:=true;
    go to step 2;
  

  （4）如果所有进程的Finish[i] = true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

• 常用解除死锁的两种方法是：① 剥夺资源； ② 撤销进程。

• 例题：在银行家算法中，若出现下述资源分配情况：

试问：
⑴ 该状态是否安全？
⑵ 若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？

答： ⑴该状态是安全的，因为存在一个安全序列< P0P3P4P1P2>。下表为该时刻的安全序列表。

⑵若进程P2提出上述请求，系统不能将资源分配给它，因为分配之后系统将进入不安全状态。

P2请求资源：P2发出请求向量Request2（1，2，2，2），系统按银行家算法进行检查：
①Request2（1，2，2，2）≤Need2（2，3，5，6）；
②Request2（1，2，2，2）≤Available（1，6，2，2）；
③系统暂时先假定可为P2分配资源，并修改P2的有关数据，如下表：

生产者消费者模型的理解

生产者消费者模型也叫缓存绑定问题，是一个经典的、多进程同步问题。

单生产者和单消费者

• 有两个进程：一组生产者进程和一组消费者进程共享一个初始为空、固定大小为的缓冲区。

• 生产者：生产者的工作是制造一段数据，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待，如此反复;

• 消费者：只有缓冲区不空时，消费者才能从缓冲区中取出消息，一次消费一段数据（即将其从缓存中移出），否则必须等待。

• 由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。

• 需要解决的主要问题

  1. 生产者在缓存还是满的时候不能向缓存区写数据;
  2. 消费者不能从空的缓存中取出数据。

  生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。

  解决思路：
  对于生产者，如果缓存是满的就去睡觉。消费者从缓存中取走数据后就叫醒生产者，让它再次将缓存填满。若消费者发现缓存是空的，就去睡觉了。下一轮中生产者将数据写入后就叫醒消费者。

  不完善的解决方案会造成“死锁”，即两个进程都在“睡觉”等着对方来“唤醒”。

  只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。使用“进程间通信”，“信号标”semaphore就可以解决唤醒的问题：

  我们使用了两个信号标：full 和 empty 。信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初值为1；信号量 full 用于记录当前缓冲池中“满”缓冲区数，初值为0。信号量 empty 用于记录当前缓冲池中“空”缓冲区数，初值为n。新的数据添加到缓存中后，full 在增加，而 empty 则减少。如果生产者试图在 empty 为0时减少其值，生产者就会被“催眠”。下一轮中有数据被消费掉时，empty就会增加，生产者就会被“唤醒”。

  该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时便可对empty变量执行P 操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前。

  1、若生产者进程已经将缓冲区放满，消费者进程并没有取产品，即 empty = 0，当下次仍然是生产者进程运行时，它先执行 P(mutex)封锁信号量，再执行 P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行 P(mutex)，然而由于生产者进程已经封锁 mutex 信号量，消费者进程也会被阻塞，这样一来生产者进程与消费者进程都
  将阻塞，都指望对方唤醒自己，陷入了无休止的等待。
  2、若消费者进程已经将缓冲区取空，即 full = 0,下次如果还是消费者先运行，也会出现类似的死锁。
  不过生产者释放信号量时，mutex、full 先释放哪一个无所谓，消费者先释放 mutex 还是 empty 都可以。

多生产者多消费者

• 在多个制造商和多个消费者出现的情况下就会造成拥护不堪的情况，会导致两个或多个进程同时向一个磁道写入或读出数据。要理解这种情况是如何出现的，我们可以借助于putItemIntoBuffer()函数。它包含两个动作：一个来判断是否有可用磁道，另一个则用来向其写入数据。如果进程可以由多个制造商并发执行，下面的情况则会出现：
  1. 两个制造商为emptyCount减值；
  2. 一个制造商判断缓存中有可用磁道；
  3. 第二个制造商与第一个制造商一样判断缓存中有可用磁道；
  4. 两个制造商同时向同一个磁道写入数据。

• 多个生产者向一个缓冲区中存入数据，多个生产者从缓冲区中取数据。这是有界缓冲区问题，队列改写，生产者们之间、消费者们之间、生产者消费者之间互相互斥。共享缓冲区作为一个环绕缓冲区，存数据到尾时再从头开始。

  • 我们使用一个互斥量保护生产者向缓冲区中存入数据。由于有多个生产者，因此需要记住现在向缓冲区中存入的位置。

  • 使用一个互斥量保护缓冲区中消息的数目，这个生产的数据数目作为生产者和消费者沟通的桥梁。

  • 使用一个条件变量用于唤醒消费者。由于有多个消费者，同样消费者也需要记住每次取的位置。

• 在选项中选择生产条目的数目，生产者的线程数目，消费者的线程数目。生产者将条目数目循环放入缓冲区中，消费者从缓冲区中循环取出并在屏幕上打印出来。

• 为了克服这个问题，我们需要一个方法，以确保一次只有一个制造商在执行调用函数。换个说法来讲，我们需要一个有“互斥信号标”（mutal exclusion）的“关键扇区”（critical section）。为了实现这一点，我们使用一个叫mutex二位信号标。因为一个二位信号标的值只能是1或0，只有一个进程能执行down(mutex)或up(mutex)。

读者写者模型的理解

什么是读者写者模型

读者和写者模型是操作系统中的一种同步与互斥机制，它与消费者和生产者模型类似，但也有不同的地方，最明显的一个特点是在读者写者模型中，多个多者之间可以共享“仓库”，读者与读者之间采用了并行机制；而在消费者和生产者模型中，消费者只能有一个独占仓库，消费者与消费者是竞争关系。

读者写者模型的要具有的条件

写者是排它性的，即在有多个写者的情况下，只能有一个写者占有“仓库”；
读者的并行机制：可以运行多个读者去访问仓库；
如果读者占有了仓库，那么写者则不能占有；

读者写者模型的关系

读者优先：读者先来读取数据，此时写者处于阻塞状态，当读者都读取完数据后且没有读者了时写者才能访问仓库；
写者优先：类似与读者优先的情况；
公平情况：写者与读者访问“仓库”优先级相等，谁先进入优先级队列谁先访问；

两个模型之间的区别

从两个模型的原理中可以看出，两个模型最大的区别在于在生产者消费者模型中，生产者与生产者是互斥关系，消费者和消费者是互斥关系，生产者和消费者之间是互斥与同步关系；而在读者写者模型中，读者和读者没有关系，写者和写者是互斥关系，读者和写者是互斥与同步关系。

互斥量，条件变量，信号量，读写锁，自旋锁

• 互斥锁–保护了一个临界区，在这个临界区中，一次最多只能进入一个线程。如果有多个进程在同一个临界区内活动，就有可能产生竞态条件(race condition)导致错误，其中包含递归锁和非递归锁，（递归锁：同一个线程可以多次获得该锁，别的线程必须等该线程释放所有次数的锁才可以获得）。

• 读写锁–从广义的逻辑上讲，也可以认为是一种共享版的互斥锁。可以多个线程同时进行读,但是写操作必须单独进行,不可多写和边读边写。如果对一个临界区大部分是读操作而只有少量的写操作，读写锁在一定程度上能够降低线程互斥产生的代价。

• 条件变量–允许线程以一种无竞争的方式等待某个条件的发生。当该条件没有发生时，线程会一直处于休眠状态。当被其它线程通知条件已经发生时，线程才会被唤醒从而继续向下执行。条件变量是比较底层的同步原语，直接使用的情况不多，往往用于实现高层之间的线程同步。使用条件变量的一个经典的例子就是线程池(Thread Pool)了。

• 信号量–通过精心设计信号量的PV操作，可以实现很复杂的进程同步情况（例如经典的哲学家就餐问题和理发店问题）。而现实的程序设计中，却极少有人使用信号量。能用信号量解决的问题似乎总能用其它更清晰更简洁的设计手段去代替信号量。

• 自旋锁–当要获取一把自旋锁的时候又被别的线程持有时,不断循环的去检索是否可以获得自旋锁,一直占CPU资源。

• 对于这些同步对象，有一些共同点：

  1. 每种类型的同步对象都有一个init的API，它完成该对象的初始化，在初始化过程中会分配该同步对象所需要的资源（注意是为支持这种锁而需要的资源，不包括表示同步对象的变量本身所需要的内存）
  2. 每种类型的同步对象都一个destory的API，它完成与init相反的工作
  3. 对于使用动态分配内存的同步对象，在使用它之前必须先调用init
  4. 在释放使用动态分配内存的同步对象所使用的内存时，必须先调用destory释放系统为其申请的资源
  5. 每种同步对象的默认作用范围都是进程内部的线程，但是可以通过修改其属性为PTHREAD_PROCESS_SHARED并在进程共享内存中创建它的方式使其作用范围跨越进程范围
  6. 无论是作用于进程内的线程，还是作用于不同进程间的线程，真正参与竞争的都是线程（对于不存在多个线程的进程来说就是其主线程），因而讨论都基于线程来
  7. 这些同步对象都是协作性质的，相当于一种君子协定，需要相关线程主动去使用，无法强制一个线程必须使用某个同步对象

• 总体上来说，可以将它们分为两类：

  1. 第一类是互斥锁、读写锁、自旋锁，它们主要是用来保护临界区的，也就是主要用于解决互斥问题的，当尝试上锁时大体上有两种情况下会返回：上锁成功或出错，它们不会因为出现信号而返回。另外解锁只能由锁的拥有着进行
  2. 第二类是条件变量和信号量，它们提供了异步通知的能力，因而可以用于同步和互斥。但是二者又有区别：
     1. 信号量可以由发起P操作的线程发起V操作，也可以由其它线程发起V操作；但是条件变量一般要由其它线程发起signal（即唤醒）操作
     2. 由于条件变量并没有包含任何需要检测的条件的信息，因而对这个条件需要用其它方式来保护，所以条件变量需要和互斥锁一起使用，而信号量本身就包含了相关的条件信息（一般是资源可用量），因而不需要和其它方式一起来使用
     3. 类似于三种锁，信号量的P操作要么成功返回，要么失败返回，不会因而出现信号而返回；但是条件变量可能因为出现信号而返回，这也是因为它没包含相关的条件信息而导致的。

进程关系

守护进程（重点）

• 概念理解

  1. 守护进程是一个在后台运行并且不受任何终端控制的进程。Unix操作系统有很多典型的守护进程(其数目根据需要或20—50不等)，它们在后台运行，执行不同的管理任务。

  2. 守护进程也称精灵进程(Daemon)，是运⾏在后台的⼀种特殊进程。它独立于控制终端并且周期性地执行 某种任务或等待处理某些发生的事件。守护进程是⼀种很有用的进程。

  3. Linux的⼤多数服务器就是⽤用守护进程实现的。比如，ftp服务器，ssh服务器，Web服务器httpd等。同时，守护进程完成许多系统任务。⽐如，作业规划进程crond等。

  4. Linux系统启动时会启动很多系统服务进程,这些系统服务进程没有控制终端,不能直接和⽤户交互。其它进程 都是在用户登录或运行程序时创建,在运行结束或⽤户注销时终止,但系统服务进程(守护进程)不受用户登录 注销的影响,它们一直在运⾏行着。这种进程有⼀个名称叫守护进程(Daemon)。

  5. 守护进程没有控制终端，因此当某些情况发生时，不管是一般的报告性信息，还是需由管理员处理的紧急信息，都需要以某种方式输出。Syslog 函数就是输出这些信息的标准方法，它把信息发送给 syslogd 守护进程

• 查看守护进程

  1. ps axj命令查看系统中的进程。参数a表示不仅列出当前⽤户的进程,也列出所有其他⽤户的进程,参数x表示不仅列有控制终端的进程,也列出所有⽆控制终端的进程,参数j表示列出与作业控制相关的信息。

      ps axj | more
     

  2. 找出守护进程
     凡是TPGID⼀栏写着-1的都是没有控制终端的进程,也就是守护进程。 在COMMAND⼀列⽤[]括起来的名字表⽰内核线程,这些线程在内核⾥创建,没有⽤户空间代码,因此 没有程序文件名和命令行, 通常采⽤以k开头的名字,表⽰Kernel。init进程我们已经很熟悉了,udevd负责维护/dev目录下的设备⽂件,acpid负责电源管理,syslogd负责 维护/var/log下的⽇志文件可以看出,守护进程通常采⽤以d结尾的名字,表⽰Daemon。

特点：

1. 守护进程最重要的特性是后台运行。

2. 守护进程必须与其运行前的环境隔离开来（这些环境包括未关闭的文件描述符、控制终端、会话和进程组、工作目录以及文件创建掩码等），这些环境通常是守护进程从执行它的父进程(特别是shell)继承下来的。

3. 守护进程的启动方式有其特殊之处。它可以在Linux系统启动时从启动脚本/etc/rc．d中启动，也可以由作业控制进程crond启动，还可以由用户终端(通常是shell)执行。