一、并发

 在一定时间内，多个进程在一个CPU中采用进程切换的方式进行推进，我们称之为并发！

二、进程切换原理

 为了方便CPU对进程的调度，操作系统会为每一个CPU维护一个运行队列。下面是来自LInux内核2.6版本的运行队列示意图。

 我们发现运行队列中维护了两个进程：活跃进程、过期进程。其中活跃进程中维护了一个活跃队列queue[140]、过期队列中维护了一个过期队列。进程切换则是通过这两个队列协调工作来实现的！！

三、活跃进程、过期进程

 在活跃进程和过期进程中都维护了3个变量：nr_active、bitmap[5]、queue[140]。下面我们我们依次结束每个部分意义！

3.1分时操作系统、实时操作系统

 在LInux中，操作系统分类种类繁多，很难统一。而分时操作系统、实时操作系统就是其中之一。（运行队列queue[140]中维护的PCB优先级就是采用这两货）。那分时操作系统、实时操作系统究竟是什么呢？
 
【分时操作系统定义】：

 【来自百度百科】：分时操作系统是使一台计算机采用时间片轮转的方式同时为几个、几十个甚至几百个用户服务的一种操作系统。
 把计算机与许多终端用户连接起来，分时操作系统将系统处理机时间与内存空间按一定的时间间隔，轮流地切换给各终端用户的程序使用。由于时间间隔很短，每个用户的感觉就像他独占计算机一样。分时操作系统的特点是可有效增加资源的使用率。

 在分时操作系统中，每个进程不是一直都在CPU上运行的。每隔一段时间（时间片），会自动从CPU上剥离下来。分时操作系统是基于时间片的轮转式抢占式内核，支持进程将对CPU资源的抢占。

&emsp；分时操作系统保证了CPU对进程调度的相对公平，让优先级较低的进程也能被CPU调度！！

【实时操作系统定义】：

 【来自百度百科】：实时操作系统（Real Time Operating System，简称RTOS）是指当外界事件或数据产生时，能够接受并以足够快的速度予以处理，其处理的结果又能在规定的时间之内来控制生产过程或对处理系统做出快速响应，调度一切可利用的资源完成实时任务，并控制所有实时任务协调一致运行的操作系统。提供及时响应和高可靠性是其主要特点。

 通俗来讲，在实时操作系统中，操作系统喂给CPU什么进程，CPU就必须立刻马上执行该进程。只有当该进程调度全部结束后，才能调度下一个进程！！

3.2 运行队列queue[140]

 
为何queue的大小为140？
 进程被调度，有先后顺序，存在优先级。在queue[140]中，0~99是实时优先级（不关心），100 ~ 139是不普通优先级（采用分时操作系统，每隔一段时间，进程会被从CPU上剥离）
 
活跃队列和过期队列如何实现进程切换？

  在进程被调度前，操作系统会将所有要被调度的进程PCB，按照其运行优先级添加到活跃队列中。此时CPU会按照顺序从上到下依次调度对应的进程。

  此时存在大量的进程还未全部被执行完，当时间片到达，从CPU上剥离。此时操作系统会在进程被剥离前，将当前进程的运行相关信息保存到PCB中，然后将该进程的PCB从活跃队列中移除，加载到过期队列。至于新产生的需要被调度的进程，则是直接添加到过期队列中。

  在运行队列中，操作系统是通过active指针和expired指针来维护活跃进程和过期进程的。其中active指针永远指向活跃队列，expired指针永远指向过期队列。由于进程时间片的存在，导致活跃队列上的进程越来越多，而过期队列上的进程则越来越少。
  当活跃队列上的进程全部被调度执行完后，操作系统会通过修改active指针、expired指针的指向。将active指针指向过期队列，expired指针指向活跃进程。从而实现过期队列和过期队列之间的转化，换而言之，操作系统通过修改active指针和expired指针的指向，实现了进程切换。

3. 3 操作系统如何查找非空进程

 在活跃进程和过期进程中，除了queue[140]，操作系统还为其维护了两个变量：nr_active、bitmap[5]。
 其中，nr_active表示需被调度进程的个数。
 至于bitmap[5]则是为了让操作系统快速定位待调度进程的位置。其实我们可以采用暴力的方式来依次遍历判断每一个优先级是否存在进程被掉的。但进程切换是非常频繁的，遍历queue[140]时间复杂度是常数，但还是太低效了！！

 所以在Linxu中采用了位图，bitmap[5]中维护32x5个比特位，对应140个优先级。计算机可每次读取8（或16）个比特位，快速定位需被调度的进程、及快速判断是否有进程需要被调度！！（大O(1)调度）

过期队列中两变量用途一致。