文章目录

• 进程与线程
• • 进程
  • • 进程的特点
    • 进程的模型
    • 进程的创建
    • 进程的终止
    • 进程的状态
    • 进程的切换
    • 进程的实现
    • 进程的合作
  • 线程
  • • 为什么有线程？
    • 线程的使用
    • 经典的线程模型
    • POSIX线程
    • 用户级线程
    • 内核级线程
    • 混合实现
    • 调度程序激活机制
    • 进程与线程的比较
  • 进程间通信
  • • 竞争条件
    • 临界区
    • 忙等待的互斥
    • 信号量
    • 互斥量
  • 管程
  • 调度
  • • 调度时机
    • 调度算法分类
    • 调度目标和算法
  • 小结
  • 参考资料

进程与线程

想要了解操作系统是如何设计的？ 那得先了解进程。操作系统的所有内容都是围绕着进程的概念展开的，包括由此衍生出来的线程。

进程

首先了解两个概念：

并发：在同一时间段内，多个事件执行，强调同一时间段。

并行：多个事件同时执行，强调同一时刻。

现代计算机大致可分为两种：单处理器系统和多处理器系统。

对于单处理器系统，通过采用多道程序设计(指程序的快速切换)支持多进程，即在同一时间段内，分时运行多个程序，实现并行的错觉，而这种模型被称之为顺序进程。

之所以是伪并行，是因为：一个CPU一次只能运行一个程序！

进程的特点

• 动态性：可动态的创建、结束进程；
• 独立性：不同进程的工作互不影响；
• 并发性：进程可以被独立调度并占用CPU;
• 制约性：因访问共享数据/资源或进程间同步而产生制约。

进程的模型

在进程模型中，计算机上所有可运行的软件，包括操作系统，被组织成若干顺序进程，简称进程。换言之，我们可以简单的认为（不一定正确）：计算机 = 硬件 + 进程

进程是操作系统中最核心的概念，一个进程就是一个正在执行程序的实例，这个实例包含程序计数器，寄存器和变量的当前值等。

note: 面试考点！

注意理解进程和程序之间的区别，程序只是进程的一部分。一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。

联系

程序是产生进程的基础；

程序的每次运行构成不同的进程；

进程是程序功能的体现；

通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

区别

进程是动态的，程序是静态的；

程序是有序代码的集合；进程是程序的执行；

进程有核心态和用户态；

进程与程序的组成不同，进程的组成包括程序、数据和进程控制块等。

进程的创建

操作系统需要有一种方式来创建进程。通常，4种主要事件会导致进程的创建：

• 系统初始化，如加载操作系统；
• 正在运行的程序执行了创建进程的系统调用；
• 用户请求创建一个新进程；
• 一个批处理作业的初始化。

操作系统初始化时会启动若干进程，包括前台进程和后台进程。后台进程又被称为守护进程。一个正在运行的进程经常发出系统调用，以便创建一个或多个新进程协助其工作。在UNIX和Windows系统中，用户可以同时打开多个窗口，每个窗口都运行一个进程。

综上，新进程都是由于一个已经存在的进程（操作系统初始化除外）执行了一个用于创建进程的系统调用而创建的。这个系统调用通知操作系统创建一个新进程，并且直接或间接地指定在该进程中运行的程序。

在UNIX系统中，只有一个系统调用可以用来创建新进程：fork。这个调用会创建一个与调用进程相同的副本，即这个两个进程（父子进程）拥有相同的内存映像、同样的环境字符串和同样的打开文件。通常，子进程接着执行execve或者一个类似的系统调用，以修改其内存映像并运行一个新的程序。之所以要安排两步建立进程，是为了在fork之后但在execve之前允许孩子进程处理其文件描述符，这样可以完成对标准输入文件、标准输出文件和标准错误文件的重定向。

在Windows系统中，一个Win32函数调用CreateProcess既处理进程的创建，也负责把正确的程序装入新进程。在UNIX和Windows中，进程创建之后，父进程和子进程有各自不同的地址空间。

在Linux系统中, main中创建第一个系统进程，并init()启动shell，shell（shell是根进程，即1号进程）再启动其他进程。

int main(int argc,char* argv[]){
    ...
    ...
    // 上面为各种init()
     while(1){
         // 用户命令
         scanf("%s",cmd);
         // 启动一个新进程执行命令
         if(fork()){  // 判断为子进程（了解fork的返回值）
             exec(cmd);
         }
         // 父进程的等待命令
         wait();
     }
}

进程的终止

通常以下情况会导致进程的终止：

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

在UNIX中，该调用是exit，而在Windows中，是ExitProcess。在UNIX中，某个进程调用kill通知操作系统杀死某个进程，而Windows是TeriminateProcess。在这两种情形中，“杀手”都必须获得确定的授权以便进行动作。

进程之间有时还存在层次结构。在UNIX中，进程和它所有子进程以及后裔共同组成一个进程组。该进程中的每一个成员都会对某一信号做出响应，比如捕获该信号，忽略该信号或采取默认动作，即被该信号杀死。在Windows中没有进程层次的概念，所有进程都是地位相同的，唯一的联系是父进程在创建一个新进程时会得到一个句柄，用来控制子进程，但是这个句柄是可以移交的，而UNIX中，则不能改变父子关系。

进程的状态

通常进程有三种状态，四种转换关系：

• 运行态（该时刻进程实际占用CPU）
• 就绪态（可运行，但因为其他进程正在运行而暂时停止）
• 阻塞态（除非某种外部事件发生，否则进程不能运行）

当一个进程在逻辑上不能继续运行时，它就会被阻塞，典型的例子是它在等待可以使用的输入。

调度程序的主要工作就是决定应当运行哪个进程、何时运行及运行多长时间。调度程序采用调度算法，力图在整体效率和进程的竞争公平性之间取得平衡。

进程只能自己阻塞自己，被别的进程或操作系统唤醒。

进程的切换

停止当前运行的进程（从运行状态改变成其他状态）并且调度其他进程（转变成运行态）

• 必须在切换之前存储进程的上下文；
• 必须能够在之后恢复它们，所以进程不能显示它曾经被暂停过；
• 必须快速（上下文转换是非常频繁的）

需要存储什么上下文？

• 寄存器（PC,SP,…）, CPU状态…
• 一些时候可能会很费时，所以我们应该尽量避免频繁切换进程
  

// 进程切换
void schedule(){
   pNew = getNext(ReadyQueue);  // 调度
   switch_to(pCur,pNew);        // 参数 PCB（结构体）
}

操作系统为活跃进程准备了进程控制块PCB。操作系统将进程控制块PCB放置在一个合适的队列里。队列可分为：

• 就绪队列
• 等待I/O队列（每个设备的队列）
• 僵尸队列

调度算法

• FIFO：先来先服务算法
• Priority：优先级调度算法

FIFO比较公平，但是没考虑到进程的区别，即有些进程可能更重要。
Priority可能导致某些进程饥饿，即始终得不到CPU的服务。

进程的实现

为了实现进程模型，操作系统维护着一张表格（一个结构数组），即进程表（Process Control Blocks,PCB）。每个进程占用一个进程表项，该表项包含了进程状态的重要信息，包括程序计数器，堆栈指针，内存分配情况，所打开文件的状态，账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断过一样。

PCB的组织方式：链表，索引表。

进程的合作

生产者—消费者模型(竞争，同步问题)

// 共享数据
int counter = 0;

// 生产者进程
counter++;
// 汇编代码
{
    register = counter;
    register = register + 1;  // 在这个过程中，可能会被切换，从而发生错误
    counter = register;
}

// 消费者进程
counter--;
// 汇编代码
{
    register = counter;
    register = register - 1;  // 在这个过程中，可能会被切换，从而发生错误
    counter = register;
}

解决

进程同步（合理的推进顺序），给counter上锁，写counter时阻断其他进程访问counter，写完解锁。

线程

线程是轻量级的进程。在传统操作系统中，每个进程有一个地址空间和一个控制线程。

为什么有线程？

我们知道，每个进程拥有独立的地址空间。那如果我们要让多个类似进程的东西共享地址空间怎么办？这就需要引入线程了。人们需要多线程的主要原因在于许多应用中同时发生着多种活动，其中某些活动随着时间的推移会被阻塞。通过将这些应用程序分解成可以准并行运行的多个顺序线程，程序设计模型会变得更简单。

线程的使用

线程就是拥有共享同一个地址空间和所有可用数据的能力的并行实体

经典的线程模型

进程模型基于两种独立的概念：资源分组处理与执行。理解进程的一个角度是，用某种方法将相关的资源集中在一起。进程是中存放程序正文和数据以及其他资源的地址空间。另一个角度是，进程拥有一个执行的线程，通常简写为线程。在线程中有一个程序计数器，用来记录接着要执行的哪一条指令；线程拥有寄存器，用来保存线程当前的工作变量；线程还拥有一个堆栈，用来记录执行历史，其中每一帧保存了一个已调用的但是还没有从中返回的过程。

进程用于把资源集中到一起，而线程则是在CPU上被调度执行的实体。

线程给进程模型增加了一项内容，即在同一个进程环境中，允许彼此之间有较大独立性的多个线程执行。多线程和多进程类似，CPU在线程之间快速的切换，制造了线程并行运行的假象。进程中的不同线程不像不同进程之间那样存在很大的独立性。所有的线程都有完全一样的地址空间，这意味着它们也共享同样的全局变量。

资源管理的单位是进程而非线程。线程概念试图实现的是，共享一组资源的多个线程的执行能力，以便这些线程可以为完成某一任务而共同工作。

和进程类似，线程可以处于若干种状态的任何一个：运行、阻塞、就绪或终止。每个线程都有自己的堆栈。每个线程的堆栈有一帧，供各个被调用但是还没有从中返回的过程使用。在该栈帧中存放了相应过程的局部变量以及过程调用完成之后使用的返回地址。

创建线程通常都会返回一个线程标识符，该标识符就是新线程的名字。

thread_create   // 线程创建
thread_exit     // 线程退出
thread_join     // 调用线程等待某个线程结束后才结束
thread_yield    // 自动放弃CPU，让另一个线程运行

不同于进程，线程是无法利用时钟中断强制线程让出CPU的。线程是有益的，但是线程也在程序设计模式中引入了某种程度的复杂性,比如生产者—消费者模型。总之，要使多线程的程序正常工作，就需要仔细思考和设计。

ThreadCreate 的核心就是将TCB，栈关联在一起。

void  ThreadCreate(A){  // 线程创建
    TCB *tcb = malloc();
    Stack *stack = malloc();
    *stack = A;  
    tcb.esp = stack;
}

POSIX线程

为了实现可移植的线程程序，IEEE在IEEE标准1003.1c中定义了线程的标准，其线程包名为pthread。每一个pthread线程都有某些特性。每一个都含有一个标识符，一组寄存器（包括程序计数器）和一组存储在结构中的属性。这些属性包括堆栈大小、调度参数以及其他线程需要的项目。

用户级线程

把整个线程包放在用户空间中，内核对线程包一无所知。其优点是用户级线程包可以在不支持多线程的操作系统上实现。

在用户空间管理线程时，每个进程需要有其专用的线程表，用来跟踪该进程中的线程。这些表和内核中的进程表类似，不过它仅仅记录每个线程的属性，如每个线程的程序计数器、堆栈指针、寄存器和状态等。使用用户级线程的最大优点就是线程切换很快，开销小（相对陷入内核），且允许每个进程有自己定制的调度算法。

使用线程的一个主要目标是，首先要允许每个线程使用阻塞调用，但是还要避免被阻塞的线程影响其他的线程。

用户级线程有其明显的问题：

• 如何实现阻塞系统调用
• 缺页中断问题
• 线程可永久运行

程序员通常在经常发生线程阻塞的应用中才希望使用多个线程，对于CPU密集型而且极少有阻塞的应用程序而言，就没必要使用多线程。

线程切换

每个线程需要自己的栈，（Thread Control Block,TCB）配合栈实现线程间的切换。

void Yield(){
   TCB2.esp = esp;  // 保存栈
   esp = TCB1.esp;  // 设置当前栈
}

内核级线程

在内核中有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它进行一个系统调用，这个系统调用通过对线程表的更新完成线程创建或撤销工作。

内核的线程表保存了每个线程的寄存器、状态和其他信息。所有能够阻塞线程的调用都以系统调用的形式实现，这就解决了用户级线程的实现阻塞系统调用的问题。当一个线程阻塞时，内核根据其选择，可以运行同一个进程中的另一个线程（若有一个就绪线程）或者运行另一个进程中的线程。内核线程不需要任何新的、非阻塞系统调用。

在经典模型中，信号是发给进程而不是线程的。

混合实现

使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来。采用这种方法，编程人员可以决定有多少个内核级线程和多少个用户级线程彼此多路复用。内核只识别内核级线程，并对其进行调度。

调度程序激活机制

尽管内核级线程在一些关键点上优于用户级线程，但无可争议的是内核级线程的速度慢。因此，很有必要寻找一种保持其优良特性的前提下改进其速度的方法。

调度程序激活机制就是一种好方法。

调度程序激活工作的目标就是模拟内核线程的功能，但是为线程包提供通常在用户空间中才能实现的更好的性能和更大的灵活性。由于避免了在用户空间和内核空间之间的不必要转换，从而提高了效率。

进程与线程的比较

• 进程是资源分配单位，线程是CPU调度单位；

• 进程拥有独立的地址空间，线程共享同一地址空间；

• 进程拥有完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈等；

• 线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系；

• 线程能减少并发执行的时间和空间开销：

  1）线程创建时间比进程短；

  2）线程的终止时间比进程短；

  3）同一进程内的线程切换时间比进程短；

  4）由于同一进程中各线程共享内存和文件资源，可直接进行不通过内核的通信。

面试考点！

进程间通信

进程之间经常需要通信（InterProcess Communication,IPC）。如何实现IPC? 挑战有三：

• 即一个进程如何把信息传递给另一个？
• 确保两个或更多的进程在关键活动中不会出现交叉
• 顺序相关（生产者–消费者模型）

竞争条件

在一些操作系统中，协作的进程可能共享一些彼此都能读写的公用存储区。即两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race condition）。

这里建议看书！

临界区

怎么避免上述的竞争条件？ 要避免这种错误，关键是要找出某种途径来阻止多个进程同时读写共享的数据。换言之，我们需要的是互斥（mutual exclusion），即以某种手段确保当一个进程在使用一个共享变量或共享文件时，其他进程不能做同样的操作。

我们把对共享内存进行访问的程序片段称为临界区（Critical region）。如果我们能够适当地安排，使得两个进程不可能同时处于临界区中，就能避免竞争条件。

一个好的解决方案必须满足以下4个条件：

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

忙等待的互斥

当一个进程在临界区中更新共享内存时，其他进程将不会进入临界区，也不会带来任何麻烦。

几种实现临界区的方案：

• 屏蔽中断：基本不用
• 锁变量：软件解决方案，这个经常用到！！！
• 严格轮换法
• Peterson解法
• TSL指令 ：测试并加锁，需要硬件支持

详细看书！

用于忙等待的锁，称为自旋锁（spin lock）。

Peterson解法

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

int turn;    // 轮到谁
int interested[N];  // 感兴趣？  

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;
}

Peterson解法和TSL解法都是正确的，但是它们都有忙等待的缺点。这就有可能会造成优先级反转问题，即优先级低的进程处于临界区时，优先级高的进程会进入忙等待（就绪态）。根据调度算法原则，优先级高的进程就绪时，优先级低的进程不会被调度，因而该进程无法离开临界区，优先级高的进程也将永远忙等待下去。

信号量

我们可以使用一个整型变量来累计唤醒次数，供以后使用，而这种变量我们称之为信号量（semaphore）。信号量的取值可以为0（表示没有保存下来的唤醒操作）或者正值（表示有一个或多个唤醒操作）。

信号量的两种操作：down 和 up（为一般化后的sleep和wakeup）。对一信号量执行down操作，则会检查其值是否大于0，若大于0，则将其值减1（即用掉一个保存的唤醒信号），若等于0，则进程将睡眠。

注意检查数值、修改变量值以及可能发生的睡眠操作都是原子操作。这保证了一旦一个信号量操作开始，则在该操作完成或者阻塞之前，其他进程均不允许访问该信号量。所谓原子操作，是指一组相关联的操作，要么都不间断的执行，要么都不执行。

up操作对信号量的值增1。对一个有进程在其上睡眠的信号量执行一次up操作之后，该信号量的值仍旧是0，但在其上睡眠的进程却少一个。信号量的值增1和唤醒一个进程同样是不可分割的。

用信号量解决生产者-消费者问题

#define N 100
typedef int semaphore
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void produce(void){
  int item;
  while(TRUE){
      item = produce_item();
      down(&empty);
      down(&mutex);
      insert_item(item);
      up(&mutex);
      up(&full);
  }
}

void consumer(void){
   int item;
   while(TRUE){
       down(&full);
       down(&mutex);
       item = remove_item();
       up(&mutex);
       up(&empty);
       consumer_item(item);
   }
}

信号量的也可用于实现同步。

互斥量

去掉计数功能的信号量。互斥量仅仅适用于管理共享资源或一小段代码，因此其实现既简单又有效，对实现用户级线程非常有用。

互斥量有两种状态：解锁和加锁。用整型量表示，0表示解锁，其他值表示加锁。

当一个线程访问临界区时调用mutex_lock，如果该互斥量是解锁的，则该线程进入临界区，否则阻塞，直到临界区中的线程完成并调用mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。

mutex_lock:
   TSL REGISTER,MUTEX    |将互斥信号量复制到寄存器，置位互斥量
   CMP REGISTER,#0       |互斥量是0？
   JZE oK                |为0，则解锁，返回
   CALL thread_yield     |不为0，互斥信号量忙，阻塞，调度其他线程
   JMP mutex_lock        |稍后再试
ok:RET                   |返回调用者，进入临界区

mutex_unlock:
   MOVE MUTEX,#0         |mutex 复位
   RET                   |返回调用者

管程

为了更易于编写正确的程序，人们提出来管程的概念。一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。管程有一个很重要的特性，即任一时刻管程中只能有一个活跃进程，这一特性使管程能有效地完成互斥。程序员只需要知道将所有的临界区转换成管程过程即可，而不用关系编译器是如何实现互斥的。

调度

进程如何切换？ 通过调度程序（scheduler）进行调度切换。

调度时机

• 创建一个新进程后
• 一个进程退出后
• 一个进程阻塞时
• 发生一个I/O中断时

调度算法分类

按照如何处理时钟中断：

• 非抢占式：挑选一个进程，让其运行直至阻塞，或者该进程自动释放CPU，不处理时钟中断。
• 抢占式：挑选一个进程，给其一个时间片，时间片用完发生时钟中断，然后调度。

按照系统环境：

• 批处理调度算法
• 交互式调度算法
• 实时调度算法

调度目标和算法

所有系统

• 公平：给每个进程公平的CPU份额
• 策略强制执行：保证规定的策略被执行
• 平衡：保持系统的所有部分都忙碌

批处理系统

• 吞吐量：每小时最大作业数
• 周转时间：从提交到终止间的最小时间
• CPU利用率: 保持CPU时钟忙碌

算法：

• 先来先服务
• 最短作业优先
• 最短剩余时间优先

交互式系统

• 相应时间： 快速响应请求
• 均衡性： 满足用户的期望

算法：

• 轮转调度（round robin）: 每个进程被分配一个时间段，称为时间片（quantum），即允许该进程在该时间段中运行。
• 优先级调度： 每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。

这两种算法最为常用！！！

实时系统

• 满足截止时间： 避免丢失数据

分为硬实时和软实时。

小结

本文粗略的介绍了操作系统中最为重要的两个概念：进程和线程。当然了，笔者略去了很多内容，或是觉得晦涩，或是觉得没必要一一列出。毕竟，这是一篇笔记。个中细节，还是建议阅读原书~

参考资料

《现代操作系统》（第四版）