1. 进程

进程的概念

进程是具有独立功能的程序关于某个数据集合上的一次运行活动，也是操作系统资源分配和调度的基本单位，又称为任务。

进程的分类

• 按照是否进行系统调用可以分为：

  系统进程，用户进程

• 按照前后台可分为：

  前台进程，后台进程

• 根据状态可以分为：

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

进程的组成

进程控制块PCB、数据段、正文段

关于进程和程序的区别

关于进程和程序的区别，我们可以这么理解：程序是存储在磁盘的文件里面的一系列指令流，这些文件通常就是我们所说的可执行文件（例如C语言编译后生成的exe文件或者out文件），而当我们运行这些可执行文件时，操作系统就会将这些可执行文件加载到内存上并运行，这个时候就成为进程了。总的来说，程序是存储在磁盘上的、静态的、没有任何运行意义的指令流，而进程是运行于内存和CPU上的、动态的、用于执行这些指令流的实体。

进程和程序的其它区别如下：

• 进程更能真实地描述并发，而程序不能；
• 进程是由程序和数据两部分组成的；
• 进程是具有生命周期的，而程序没有；
• 一个程序对应多个进程，反之亦然。

进程的状态

进程具有以下的几个状态：

• 新的：进程正在创建

• 运行：进程正在执行

• 等待：进程正在等待某个事件（如I/O完成或收到信号）

• 就绪：进程正在等待分配处理器

• 终止：进程已经执行完成

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

进程控制块PCB是记录了进程的相关信息的数据结构，包括：进程状态、程序计数器、CPU寄存器、CPU调度信息、内存管理信息、记账信息、I/O状态信息等。

2. 进程调度

调度队列

直接用图表示吧：

调度程序

操作系统是通过调度器或者调度器来对进程进行调度的。对于批处理系统，提交的进程多于可以立即执行的进程时，这些进程就会被保存到大容量存储设备（磁盘）中的缓冲池中

• 长期调度程序：从缓冲池中选择进程，并加载到内存，以便执行；
• 短期调度程序（或CPU调度程序）：从准备执行的进程中选择进程，并分配CPU资源。

上下文切换

当一个进程由于中断的发生而需要去执行其它任务时，需要对该进程的状态进行保存，以便该进程在恢复时可以继续执行，这时就涉及到了一个词叫做上下文切换。当进行上下文切换时，内核会将旧进程状态保存在其PCB中，然后加载经调度要执行的新进程的上下文。当要恢复到原来的进程时，就能保证原本旧进程的状态不受影响。

3. 进程的运行

PID

在操作系统中，通常需要使用唯一标识符来标识每一个进程，而这个标识符就称之为pid，并且通常为整数，它可以用作索引，以便访问内核中的各种属性。

#include<sys/types.h>
#include<stdio.h>
#include<unistd.h>int main(){pid_t pid;pid = fork();if(pid < 0){fprintf(stderr,"Fork Failed");return 1;}else if(pid == 0){execlp("/bin/ls","ls",NULL);}else{wait(NULL);printf("Child Complete\n");}return 0;
}

fork() ：创建子进程，子进程复制父进程的地址空间，即继续执行fork()以下的语句。父进程的返回值为子进程的pid，子进程的返回值是0

exec()：加载二进制文件到内容，覆盖进程原本的地址空间，开始执行；

wait()：使进程等待子进程执行完才继续执行。

4. 进程的终止

当进程执行完最后语句并且通过系统调用exit()请求操作系统删除自身时，进程终止，这时进程可以返回状态值到父进程，所有进程的资源会由操作系统释放。

父进程终止子进程的原因：

• 子进程使用了超过父进程所分配的资源；
• 分配给子进程的任务不再需要；
• 父进程正在退出，而且操作系统不允许无父进程的子进程继续执行。

当一个进程终止时，操作系统会释放其资源。不过它位于进程表中的条目还在，这时候它就成了僵尸进程，直到父进程调用wait()为止。所有的进程终止时都会过渡到这种状态。如果它的父进程没有调用wait()就已经结束了，那么这个进程就成了孤儿进程。

调用wait（）时，如下流程所示：

没有调用wait（）时，如下流程所示：

5. 进程间通信

操作系统内的并发执行进程可以是独立的也可以是协作的。如果一个进程不能影响其它进程或受其它进程影响，则该进程是是独立的，反之则是协作的。如果进程为协作进程，那么就必须提供通信机制，使其能够与其它协作进程进行通信。

进程间的通信机制，主要有两种：

• 共享内存：在内存中规定一块内存，作为公共内存，多个协作进程可以对该块内存进行读写。
• 信息传递：通过进程间的交换消息通信来实现。

6. 线程

线程的概念

线程是进程内的一个执行单位，是CPU调度的最小单位，它包括线程ID、程序计数器、寄存器和堆栈。每个线程与同一进程的其他线程共享代码段、数据段和其他操作系统资源。

进程和线程的区别和联系

• 进程是CPU资源分配的最小单位
• 线程是CPU调度的最小单位
• 进程之间切换的开销远大于线程之间的切换
• CPU把资源分配给进程，但线程不拥有任何系统资源
• 一个进程中包含一个或多个线程

多线程技术的优点

• 响应性高
• 资源共享
• 轻量级
• 可伸缩性

多线程模型

• 多对一模型

  多对一模型的实现是将每一个用户线程都只映射到同一个内核线程。优点是线程管理是由用户空间的线程库来完成的，效率比较高，用户可以创建多个进程；缺点是只有一个内核线程，因此在同一时刻只有一个用户线程能够访问内核线程，因此多个线程不能并行运行，并且如果其中一个线程阻塞了，那么就会使得整个进程都发生阻塞。

• 一对一模型

  一对一模型的实现是将每一个用户线程都能映射到对应的一个内核线程。优点是线程执行阻塞时，其他线程还能够继续执行，所以能够并行运行多个线程；但是缺点也很明显，创建一个用户线程就需要创建一个相对应的内核线程，而创建内核线程会增加开销进而降低应用程序的性能，所以这种模型就需要对线程的数量进行限制。

• 多对多模型

  多对多模型实际上就是将一对多模型和一对一模型进行混合实现，这种情况下线程既能够拥有并行执行的能力，又能够创建任意多的用户线程。当任何一个线程阻塞时，内核可以调度另一个线程来执行。

线程的撤销

线程撤销指的是在线程完成之前就把线程给终止掉。

7. 进程同步

临界区问题

每个进程都有一段访问共享内存的代码，这段代码称为临界区。当有一个进程在临界区内执行时，其它进程不允许在临界区内执行。

临界区代码中可以分为：进入区、临界区、退出区、剩余区。

临界区问题的解决方案需要满足三个需求：

• 互斥：如果进程pi在其临界区内执行，那么其它进程就都不能在其临界区内执行；
• 进步：如果没有进程在其临界区内执行，并且有进程需要进入临界区，那么只有那些不在剩余区内执行的进程可以参加选择，以便确定谁能下次进入临界区，而且这种选择不能无限推迟。
• 有限等待：当一个进程做出进入临界区的请求直到这个请求允许为止，其他进程允许进入其临界区的次数具有上限。

解决临界区问题的方案

• Peterson解决方案

  //以pi和pj两个进程并发访问临界区作为例子int turn;bool flag[2];//i进程的代码do{flag[i] = true;turn = j;while(flag[j] && turn == j);//临界区flag[i] = false;//剩余区}while(true);//j进程的代码do{flag[j] = true;turn = i;while(flag[i] && turn == i);//临界区flag[j] = false;//剩余区}while(true);

• 硬件同步

  加锁，指令test_and_set()、指令compare_and_swap()

• 互斥锁

  通过一个公共的互斥锁变量，来解决临界区问题。当进程pi要进入临界区时需要先调用acquire()获取互斥锁available，如果available可用，那么进程pi获得该锁，这时对于其它进程来说该锁不可用，然后进程pi执行临界区的代码。当临界区pi执行完临界区的代码以后，通过调用release()来释放锁，这时候对于其它进程来说该锁是可用的，这时其它进程就可以使用该锁了。

  //互斥锁变量
  bool available = true;//获取锁
  void acquire(){while(!available); //忙等待available = false; 
  }//释放锁
  void release(){available = true;
  }//两个同步进程的代码均如下：
  do{acquire();//临界区release();
  }while(true);

• 信号量

  通过一个公共的信号量S，来解决临界区问题。当一个进程执行wait操作时，会使信号量的值减1，当信号量的值小于等于0时，所有执行wait操作的进程都会被阻塞，并被放到等待队列中，并将该进程切换成等待状态，直到信号量的值大于0为止。当一个进程执行完signal操作后，信号量的值会加1，如果这时候信号量的值还是小于等于0的话，就会从等待队列中唤醒一个进程。

  假设信号量的值为n，那么：

  当n>0时，代表有n个信号量可用；

  当n=0时，代表所有信号量已经被使用；

  当n<0时，代表所有信号量已经被使用，并且等待队列中有|n|个进程在等待信号量的使用。

  typedef struct{int value;struct process *list;
  }semaphore;void wait(semaphore *s){s->value--;if(s->value < 0){addProcessToList(s);//add this process to s->list;block();}
  }void signal(semaphore *s){s->value++;if(s->value <= 0){removeProcessFromList(s);//remove a process P from s->listwakeup(P);}
  }

  如果使用多个信号量的情况下，有可能出现死锁或者饥饿的情况，情景如下：

  	P0		 	   P1wait(s);	     wait(Q);wait(Q);        wait(S);...			   ...signal(s);  	signal(Q);signal(Q); 		signal(S);
  

  
  

8. 死锁

死锁的概念

在一组进程中，每一个进程都在无限等待另一进程所占有的资源，因此所有进程都永远得不到资源，这种情况我们把它称之为死锁

情景图：

死锁的必要条件

• 互斥：至少有一个资源处于非共享模式，即一次只有一个进程可以使用。
• 占有并等待：一个进程应占有至少一个资源，并等待另一个资源，而等待的资源为其他进程所占有。
• 非抢占式：资源不能被其他进程抢占，即资源只能被进程在完成任务后自愿释放。
• 循环等待：存在一组等待进程{p0,p1,p2,…,pn-1,pn}，p0等待p1的资源，p1等待p2的资源，pn-1等待pn的资源，pn等待p0的资源。

死锁的解决方案

• 死锁预防

  通过破坏死锁的四个必要条件的其中一个，确保系统永远不会进入死锁的状态。

• 死锁避免

  使用前进行判断，如果启动一个进程会导致死锁的话，就不启动这个进程。

• 死锁检测

  系统提供一个算法来检查系统状态以确定死锁是否发生，并且提供另一个算法在死锁确实已经发生的情况下从死锁中恢复。

9. CPU调度

CPU调度程序

每当CPU空闲时，操作系统就应从就绪队列种选择一个进程来执行。进程选择采用短期调度程序或CPU调度程序。调度程序从内存中选择一个能够执行的进程，并为其分配CPU。

该程序的功能包括：

• 切换上下文。
• 切换到用户模式。
• 跳转到用户程序的合适为止，以便重新启动程序。

调度方案

需要进行CPU调度的四种情况：

• 当一个进程从运行状态切换为等待状态时
• 当一个进程从运行状态切换为就绪状态时
• 当一个进程从等待状态切换到就绪状态时
• 当一个进程终止时

如果调度只能发生在以上第1和第4种情况，则调度方案称为非抢占的；否则，调度方案为抢占的。

CPU调度算法

• 先来先服务调度（FCFS）
• 最短作业优先调度（SJF）
• 优先级调度
• 轮转调度（RR）