进程与线程

进程和线程

进程为操作系统提供了伪(并行)的能力，线程提高了操作系统伪(并行)的能力，没有进程和线程，现代计算是不复存在的
以下内容均为UNIX操作系统中描述

进程

在进程模型中，所有在计算机上可运行的软件，包括操作系统，被组织成若干顺序进程，简称进程

进程模型

一个进程包含程序计数器、寄存器和变量当前的值，从概念上来讲，每个进程拥有自己的cpu，实际上是cpu在进程间不断的切换导致的错觉，这种快速切换称为多道程序设计
对于用户进程，其既有用户地址空间中的栈，也有它自己的内核栈。而内核进程就只有内核栈。

每个进程的内容
地址空间
全局变量
打开文件
子进程
定时器
信号和信号处理程序
账户信息

多道程序设计模型

采用多道程序设计可提高cpu的利用率

cpu利用率计算公式:1-p^n

p表示进程等待时间和运行时间的之比,n表示多道程序设计的道数
例如：一个8g内存的操作系统，操作系统占了2G,每个应用程序占了2G,假如每个应用程序80%的时间都处于IO等待，那么cpu利用率等于1-0.8^3约为49%
这时候，增加8g内存，运行程序数量，可从3道程序设计提高到7道，cpu利用率为1-0.8^7,cpu利用率提升到79%

如果在增加8g内存，cpu利用率只能由79%提升到91%，显然不如之前的第一种投资好

进程创建

进程创建主要通过系统调用fork函数来实现的，调用后会创建后会创建一个与调用进程相同的副本，称之为子进程，这两个进程拥有相同的内存镜像，他们拥有各自不同的地址空间，其中不可写的内存区域是可共享的。可写的内存区是不共享的，通过写时复制共享

进程终止

进程终止由以下几个条件引起

• 正常退出（自愿）
• 出错退出（自愿）
• 严重错误退出（非自愿）
• 被其他进程杀死退出（非自愿）

进程状态

• 运行态
• 就绪态
• 阻塞态

前两种状态是类似的，区别是第二种状态没有分配cpu资源，第三种状态与前两种不同，处于该状态进程不能运行，即使cpu是空闲的

进程实现

操作系统维护一个表格（结构数组或链表）即进程表，该表包含了进程状态的重要信息，包括程序各种状态转换时必须保存的信息，从而保证进程再次启动时，像从未中断过一样

进程管理	存储管理	文件管理
寄存器	正文段指针	根目录
程序计数器	数据段指针	工作目录
程序状态字	堆栈段指针	文件描述符
堆栈指针		用户id
进程状态		组id
优先级
调度参数
进程id
父进程
进程组
信号
进程开始时间
使用cpu的时间
子进程cpu时间
下次定时器时间

进程分类

• 系统进程：可以执行内存资源分配和进程切换等管理工作；而且，该进程的运行不受用户的干预，即使是root用户也不能干预系统进程的运行。
• 用户进程：通过执行用户程序、应用程序或内核之外的系统程序而产生的进程，此类进程可以在用户的控制下运行或关闭。
• 针对用户进程:又可以分为交互进程、批处理进程和守护进程三类。
• 交互进程：由一个shell终端启动的进程，在执行过程中，需要与用户进行交互操作，可以运行于前台，也可以运行在后台。
• 批处理进程：该进程是一个进程集合，负责按顺序启动其他的进程。
• 守护进程:守护进程是一直运行的一种进程，经常在linux系统启动时启动，在系统关闭时终止。它们独立于控制终端并且周期性的执行某种任务或等待处理某些发生的事件。例如httpd进程，一直处于运行状态，等待用户的访问。还有经常用的crond进程，这个进程类似与windows的计划任务，可以周期性的执行用户设定的某些任务

线程

线程是cpu执行的最小单元，比进程更轻量级，更容易创建或撤销

线程模型

线程也包含程序计数器、寄存器和自己的堆栈

进程中的不同线程不像不同进程那样存在很大的独立性，所有的线程都有完全一样的地址空间，这意味着它们可以共享全局变量

每个线程的内容
程序计数器
寄存器
堆栈
状态

每个线程拥有自己的堆栈，原因是：
线程调用时需要使用栈帧存放局部变量和调用后返回的地址，而每个线程调用的过程是不同，要单独维护一套自己的执行历史

线程的使用

需要多线程的原因有两个，

• 并行实体拥有同一个地址空间和所有可用数据的能力
• 线程比进程更轻量级，创建一个线程比进程快10-100倍，当有大量线程需要动态和快速修改时，这一特性很有必要

线程状态

同进程一样，线程也可以处于运行、阻塞、就绪或终止状态

线程实现方式

在用户空间实现

整个线程包处于用户空间，从内核角度考虑，就是按正常单进程单线程方式管理，这种方式好处是有些操作系统内核不支持多线程，也可以一样使用多线程模型

用户空间线程除了这点好处，还有以下几点优势：

• 线程的状态和调度保存是本地过程，不需要内核来参与，也避免了上下问切换，cpu内存高速缓存刷新，调度敏捷
• 允许每个进程有自己的调度算法，例如，在某些应用程序中有垃圾回收线程，应用程序不需要担心线程会在不合适的时刻停止
• 拥有很好的扩展性，内核线程在内核空间需要固定的表格空间和堆栈空间，如果内核线程数量非常大，会出现问题

当然，它也有一些不可避免的缺点：

• 用户空间线程去做系统级调用是不可接受的，会停止所有的线程，而实现线程的目标是要允许每个线程使用阻塞调用，不会影响其他线程，相违背
• 该线程运行时，进程内其他线程不能运行，除非该线程放弃cpu

在内核实现

内核线程在操作系统内核中保存了每个线程的寄存器、状态、和其他信息，跟用户空间线程是一样的，区别是保存在了内核中

内核线程的管理工作由操作系统内核完成，这种实现的好处是当一个线程阻塞时，内核根据选择，可以切换到进程内另一个线程
如果当某个线程引发了页面故障，内核可以很方便的检测是否有其他可用的线程，让其执行

虽然内核解决了线程很多问题，但也不会解决所有问题，比如当一个新进程创建，是将进程里的所有线程都复制，还是只有一个线程？
还有一个问题是当过来一个信号，可以交给需要的线程执行，当时多个线程都注册了该信号，会发生什么？

混合实现

混合实现主要分为用户线程和内核线程多对1、1对1、和多对多模式，其中多对1模式就是前面介绍的在用户空间实现的线程模型，线程中使用阻塞时会阻塞其他线程

混合模式解决了多对多和1对1模型解决了线程没办法使用阻塞问题，但是1对1模型会占用多个内核线程，对操作系统内核切换影响比较大，第三种多对多模型是并发效果最好的

进程间通信

进程通常需要与其他进程通信，以达到信息传递并能保证进程按照正确顺序执行

竞争条件

多个进程读写某个共享数据，而最后的结果取决于进程运行的精准时序，称为竞争条件

临界区

怎样避免竞争条件？主要目标是组织多个进程同时读取共享数据，即互斥
抽象描述就是，我们把共享内存进行访问的程序片段叫做临界资源或者临界区,我们只要保证两个进程不同时在临界区，就能避免竞争

尽管避免竞争条件，我们还是不能保证数据共享的并发进程能高效的执行：对于一个好的解决方案，需要满足以下条件

• 任何两个进程不能同时处于临界区
• 不应对cpu的数量和速度做任何假设
• 临界区外的运行进程不得阻塞其他进程
• 不得使进程无限期等待进入临界区

对于理想的方案应该是如上图这样的，某一时刻对与临界区的访问只能有一个进程

互斥方案

屏蔽中断

最简单的实现方案，当进程进入临界区时，立即屏蔽所有中断，在离开之前打开中断，屏蔽中断后，cpu时钟中断也会屏蔽，cpu只有在发生时钟中断或其他中断时才会切换进程，这样，屏蔽中断后cpu不会切换进程，不必担心其他进程的介入

这个方案并不好，对于单核cpu，执行屏蔽中断如果不在打开，系统会因此而终止，对于多核cpu，仅对执行disable的那个cpu优先，其他cpu仍继续执行

锁变量

实现方案为设计一个锁变量，其值为0，如果有其他程序进入到临界区，会将值赋值为1，这样，其他进程读到1就不会在访问临界区了

这种方案也会出现疏忽，即两个进程同时进入临界区时，读到的临界变量都是0，执行了两次赋值1的操作，但还是发生了资源竞争

严格轮换法

进程a:

while(true) {
    while(turn != 0) {}
    processstart()
    turn = 1
    processend()
}

进程b:

while(true) {
    while(turn != 1) {}
    processstart()
    turn = 0
    processend()
}

一开始，进程a和b拿到的trun都是0，这时，只有进程a能进入并修改turn为1，这时进程b由于turn一直为0，会不断等待，直到turn变成1，这种忙等待行为被称为自旋锁

这种方式如果两个进程的执行速度会相差很多，轮流进入时会有一方等待很长时间，显然是不合适的

Person解法

#define FALSE 0
#define TRUE  1
/* 进程数量 */
#define N     2													

/* 现在轮到谁 */
int turn;					

/* 所有值初始化为 0 (FALSE) */
int interested[N];											

/* 进程是 0 或 1 */
void enter_region(int process){					
  
  /* 另一个进程号 */
  int other;														
  
  /* 另一个进程 */
  other = 1 - process;				
  
  /* 表示愿意进入临界区 */
  interested[process] = TRUE;						
  turn = process;
  
  /* 空循环 */
  while(turn == process 
        && interested[other] == true){} 
  
}

void leave_region(int process){
  
  /* 表示离开临界区 */
  interested[process] == FALSE;				 
}

在使用共享变量时（即进入其临界区）之前，各个进程使用各自的进程号 0 或 1 作为参数来调用 enter_region，这个函数调用在需要时将使进程等待，直到能够安全的临界区。在完成对共享变量的操作之后，进程将调用 leave_region 表示操作完成，并且允许其他进程进入。

现在来看看这个办法是如何工作的。一开始，没有任何进程处于临界区中，现在进程 0 调用 enter_region。它通过设置数组元素和将 turn 置为 0 来表示它希望进入临界区。由于进程 1 并不想进入临界区，所以 enter_region 很快便返回。如果进程现在调用 enter_region，进程 1 将在此处挂起直到 interested[0] 变为 FALSE，这种情况只有在进程 0 调用 leave_region 退出临界区时才会发生。

那么上面讨论的是顺序进入的情况，现在来考虑一种两个进程同时调用 enter_region 的情况。它们都将自己的进程存入 turn，但只有最后保存进去的进程号才有效，前一个进程的进程号因为重写而丢失。假如进程 1 是最后存入的，则 turn 为 1 。当两个进程都运行到 while 的时候，进程 0 将不会循环并进入临界区，而进程 1 将会无限循环且不会进入临界区，直到进程 0 退出位置。

TSL指令

TSL指令是一个需要硬件支持的方案。TSL称为测试并加锁（test and set lock）。他将一个内存字LOCK读到寄存器RX中。然后在该内存地址上存一个非零值。读字和写字操作是不可分割的，即该指令结束前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存中线，以禁止其他CPU在本指令结束前访问内存。TSL指令解决了忙等待的屏蔽中断方案中无法屏蔽多处理器访问共享内存的问题。 因为锁住内存总线不同于屏蔽中断，锁住内存总线后，所有处理器都无法通过内存总线访问内存字。 那些多处理器的计算机都有TSL指令。如下

TSL RX, LOCK

enter_region:
    TSL REGISTER, LOCK
    CMP REGISTER, #0
    JNE enter_region       ; 如果不空闲(=0)，那么反复执行，处于忙等待状态
    RET

leave_region:
    MOVE LOCK, #0
    RET

具体工作过程：第一条指令将lock原来的值复制到寄存器中并将lock设置为1，随后这个原来的值与0相比较。如果原来的值非零，则说明以前已被加锁，则程序将回到开始并再次测试。经过一段时间后，lock值变为0，于是过程返回，此时已加锁。要清除这个锁比较简单，程序只需将0存入lock即可，不需要特殊的同步指令。

一个可替代TSL的指令是XCHG，它原子性地交换两个位置的内容，例如，一个寄存器与一个存储字。它本质上与TSL的解决办法一样。所有的Intel x86 CPU在底层同步中使用XCHG指令。

睡眠与唤醒

上述基于忙等待的互斥，不仅会浪费CPU时间，而且还可能引起预想不到的结果。例如，有两个进程L和H，L的优先级较低、H的优先级较高。调度规则规定，只要H处于就绪态它就会运行。在某一时刻，L处于临界区中，此时H变到就绪态，准备运行。现在H开始忙等待，待由于H就绪时，L就不会被调度，也就无法离开临界区，所以H将永远忙等待下去。这种情况有时被称作优先级反转问题。

最简单的进程间通信原语，它们在无法进入临界区时将阻塞，而不是忙等待。两条最简单的通信原语是：sleep和wakeup。sleep是一个将引起调用进程阻塞的系统调用，即被挂起，直到另外一个进程将其唤醒。wakeup调用有一个参数，即要被唤醒的进程。

信号量

基于支持P、V操作的非负整数实现。

信号量的用处一：生产者-消费者问题

在使用信号量的系统中，隐藏中断的最自然的方法就是为每一个I/O设备设置一个信号量，其初始值为0。在启动一个I/O设备之后，管理进程就立即对相关联的信号量执行一个Down操作，于是进程立即被阻塞。当终端到来时，终端处理程序随即对相关信号量执行一个Up操作，从而将相关的进程设置为就绪状态。

为了解决生产者-消费者问题，可以使用三个信号量：full， 用于记录充满的缓冲槽数据；empty，用于记录空的缓冲槽总数；mutex，用来确保生产者和消费者不会同时访问缓冲区。

信号量的用处二：用于实现同步(Synchronization)

信号量full和empty用来保证某种时间的顺序发生或不发生。例如，当缓冲区满的时候生产者停止运行，而空的时候消费者停止运行。

互斥量

互斥量是一个可以处于两态之一的变量：加锁、解锁。相比于信号量，它没有计数功能。

由于互斥量非常简单，所以如果有TSL或XCHG指令，就可以很容易地在用户空间中实现它们。由于用户级线程包的mutex_lock和mutex_unlock代码下(0表示解锁)：

mutex_lock:
    TSL REGISTER, MUTEX
    CMP REGISTER, #0
    JZE ok                   ; 如果互斥锁空闲，那么就直接返回继续运行
    CALL thread_yield        ; 如果互斥锁忙，那么就调用其它进程，这是与忙等待的区别
    JMP mutex_lock           ; 稍后再试，也就是本代码段的开头
ok: RET


mutex_unlock:
    MOVE MUTEX, #0
    RET

mutex_lock的代码与enter_region的代码很相似，但有一个关键的区别。当enter_region进入临界区失败后，它始终重复测试锁(忙等待)。实际上，由于时钟超时的作用，会调度其它进程运行，这样迟早拥有锁的进程会进入运行并释放锁。

在用户线程中，情形有所不同，因为没有时钟停止运行时间长度的线程。结果就是通过忙等待的方式来试图获取锁的线程将永远循环下去，绝不会得到锁，因为这个运行的线程不会让其它线程运行从而释放锁。

这就是enter_region与mutex_lock的区别

Pthread中的互斥锁

pthread中提供了基于互斥锁的同步机制。提供的函数如下：

pthread_mutex_init();      // 创建互斥锁
pthread_mutex_destroy();   // 销毁互斥锁
pthread_mutex_lock();      // 上锁
pthread_mutex_trylock();   // 尝试上锁，若上锁不成功，会返回错误代码而不是阻塞调用者
pthread_mutex_unlock();    // 对互斥锁解锁

pthread中处理提供了互斥锁，还提供了条件变量用于实现同步。互斥量在允许或阻塞对临界区的访问上是很有用的，条件变量则允许线程由于一些未达到的条件而阻塞。绝大多数情况下，这两种方法是一起使用的。下面就是线程、互斥量、条件变量之间的关联。

管程

为什么引入管程

信号量机制存在的问题：编写程序困难、易出错

能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢?

1973年，Brinch Hansen首次在程序设计语言(Pascal) 中引入了“管程”成分――一种高级同步机制

定义

管程是一种特殊的软件模块，有这些部分组成:

• 局部于管程的共享数据结构说明;

• 对该数据结构进行操作的一组过程;

• 对局部于管程的共享数据设置初始值的语句;

• 管程有一个名字。

特征

管程的基本特征:

• 局部于管程的数据只能被局部于管程的过程所访问;

• 一个进程只有通过调用管程内的过程（函数）才能进入管程访问共享数据;

• 每次仅允许一个进程在管程内执行某个内部过程。

参考文献:现代操作系统