进程、线程、协程#

进程资源分配的基本单位 （内核态）线程，逻辑上的一个执行流，逻辑cpu，操作系统调度的基本单位 协程一个任务单位

进程的特征#

• 动态性
• 并发性
• 独立性
• 异步性
• 结构性

进程的组成#

PCB、 进程地址空间（代码段，数据段）、 从操作系统申请到的资源

pcb组成#

struct task_struct {
/*
进程状态
*/
/*
标识符字段
进程标识符 线程标识符 进程组标识符 会话id
*/
/*
家族亲缘关系
指向进程组领头进程的引用
指向进程组的链表
指向父进程
指向子进程的链表
指向相邻兄弟的引用
指向领头线程的引用
*/
/*
指向内核栈和thread_info的引用
*/
/*
struct thread_struct thread;
保存上下文
*/
/*
cwd
*/
/*
进程调度信息
*/
/*
文件描述符表
struct files_struct *files;
*/
/*
内存描述符
*/
/*
进程标记
反应进程状态的信息，但不是运行状态，用于内核识别进程当前的状态，以备下一步操作
*/
/*
实现调试的字段
*/
/*
信号处理
*/
...
}

进程和程序区别#

• 一对一
• 一对多: 一个进程在周期内多次调用exec切换不同程序执行
• 多对一：一个多进程架构的程序如浏览器，每一个窗口对应一个独立的进程

状态模型#

三态模型#

五态模型#

linux状态模型#

控制原语#

进程控制是使用原语来实现的

创建#

创建原语#

1. 申请空白PCB
2. 为进程分配所需资源
3. 初始化PCB
4. 将PCB插入就绪队列（创建态→就绪态）

引起进程创建的事件#

• 用户登录
• 作业调度（有新的作业将要运行）
• 提供服务
• 应用请求（用户进程主动请求创建子进程）

终止#

撤消原语#

• 从PCB集合中找到终止进程的PCB
• 若进程正在运行，立刻剥夺CPU，将CPU分配给其他进程
• 中止其所有子进程
• 将该进程所有资源归还给父进程或是操作系统
• 删除PCB

引起进程中止的事件#

• 正常结束
• 异常结束
• 外界干预

进程的阻塞和唤醒#

阻塞原语和唤醒原语必须成对使用

阻塞原语#

• 找到要阻塞进程对应的PCB
• 保护进程运行现场，将进程设置为阻塞态，暂时停止进程运行
• 将PCB插入对应事件的等待队列

引发阻塞的事件#

• 需要等待系统分配某种资源
• 需要等待合作的其他进程完成工作

唤醒原语#

• 在事件队列中找到对应的PCB
• 将PCB从等待队列移除，设置为就绪态
• 将PCB插入就绪队列，等待被唤醒

引发唤醒的事件#

• 等待的事件发生

进程的切换#

切换原语#

• 将运行环境信息存入PCB
• PCB移入相应队列
• 选择另一个进程执行，并更新其PCB
• 根据PCB回复进程所需的运行环境
• 运行环境：进程运行中的临时变量等

引起切换的事件#

当前进程时间片到 更高优先级的进程到达 当前进程主动让出时间片 当前进程中止

IPC#

• 管道
• 消息
• 共享内存
• 信号量
• 信号
• 套接字

调度#

三级调度层次#

• 高级调度 作业调入内存
• 中级调度 把挂起的作业暂时交换到外存
• 低级调度 分配到cpu资源

抢占式调度 非抢占式调度#

指标#

• 公平(会不会饥饿)
• CPU利用率
• 系统吞吐量
• 周转时间 平均周转时间 带权平均周转时间
• 响应时间 平均响应时间 带权平均响应时间
• 响应比
• 调度开销

（单核）调度策略#

• FCFS
• SJF（SRTF）(抢占式)
• 高响应比优先
• RR
• 优先级调度
• 多级队列
• MLFQ 多级反馈队列
• 随机调度
• 彩票调度（步长调度）

比较#

多核/多处理机调度策略#

• Asymmetric Multiprocessing/Symmetric Multiprocessing
• Single Queue/Queue Per Core
• Processor Affinity
  • Cache Affinity
  • Soft Affinity
  • Hard Affinity
• Load Balancing
  • Push Migration
  • Pull Migration
• 联系多核处理器 多处理器系统 多处理机操作系统已广为流行多年，相应地也必然存在着多种调度方式，特别是自20世纪 90年代以来，已出现了多种调度方式，其中有许多都是以线程为基本调度单位的。比较有代表 性的进程（线程）调度方式有自调度方式、成组调度方式、专用处理机分配调度方式和动态调 度方式等。 1．自调度方式 （1）自调度机制。 在多处理机操作系统中，自调度（self-scheduling）方式是最简单的一种调度方式，它是直 接由单处理机操作系统中的调度方式演变而来的。在系统中设置一个公共的进程或线程就绪队 列，所有的处理机在空闲时都可以到该队列中取一进程（或线程）来运行。在自调度方式中， 可采用在单处理机操作系统中所用的调度算法，如FCFS调度算法、最高优先级优先（highest priority first，HPF）调度算法和抢占式HPF调度算法等。 1990年，鲁特内格（Leutenegger）等人曾对在多处理机操作系统中的FCFS、HPF和抢占式 HPF这3种调度算法进行了研究，发现：在单处理机操作系统中，FCFS调度算法并不是一种好的 调度算法；然而在多处理机操作系统中，当把它用于线程调度时，其反而优于另外两种调度算 法。这是因为，线程本身是一个较小的运行单位，继其后而运行的线程不会有很大的时延；加 之在系统中有多个（如N个）处理机，这使后面的线程的等待时间又可进一步减少为1/N。FCFS 调度算法简单、开销小，目前已成为一种较好的自调度算法（方式）。 （2）自调度方式的优点。 自调度方式的主要优点表现为：首先，系统中的公共就绪队列可按照单处理机操作系统 中所采用的各种方式加以组织；其调度算法也可沿用单处理机操作系统中所用的算法，即很容 易将单处理机操作系统中的调度机制移植到多处理机操作系统中，故自调度方式仍然是当前多 处理机操作系统中较常用的调度方式。其次，只要系统中有任务，或者说只要公共就绪队列不 空，就不会出现处理机空闲的情况，也不会发生处理机忙闲不均的现象，这有利于提高处理机 的利用率。 （3）自调度方式的缺点。 自调度方式的缺点不容忽视，主要表现在以下3个方面。 ① 瓶颈问题。在整个系统中只设置一个就绪队列供多个处理机共享，这些处理机必须互斥地 访问该队列，这很容易造成系统瓶颈。当系统中处理机数目不多时，该问题并不严重；但当系统 中处理机数目达到数十个乃至数百个时，如果仍用单就绪队列，就会产生严重的瓶颈问题。 ② 低效性。当线程阻塞后再重新就绪时，它只能进入这唯一的就绪队列，但却很少可能仍 在阻塞前的处理机上运行。如果在每个处理机上都配有高速缓存，则此时在其中保留的该线程 的数据已经失效，而在该线程新获得的处理机上又须重新建立这些数据的复制。一个线程在其 整个生命期中可能要多次更换处理机，这使高速缓存的使用效率变得很低。 ③ 线程切换频繁。通常，在一个应用中的多个线程都属于相互合作型，但在采用自调度方 式时，这些线程很难同时获得处理机而同时运行，这会使某些线程因其合作线程未获得处理机 运行而阻塞，进而被切换下来。 2．成组调度方式 为了解决在自调度方式中线程被频繁切换的问题，鲁特内格提出了成组调度（group scheduling）方式。该方式将一个进程中的一组线程分配到一组处理机上去执行。在成组调度 时，可考虑采用以下两种方式为应用程序分配处理机时间。 （1）面向所有应用程序平均分配处理机时间。 假定系统中有N个处理机和M个应用程序，每个应用程序中至多含有N个线程，则每个应用 程序至多可有1/M的时间去占有N个处理机。例如，有4台处理机及2个应用程序，其中，应用程 序A中有4个线程，应用程序B中有1个线程。这样，每个应用程序可占用4个处理机一半（1/2） 的时间。图10-8 （a）所示为此时处理机的分配情况。从图10-8（a）中可以看出，使用这种分 配方式在应用程序A运行时，4个处理机都在忙碌；而在应用程序B运行时，则只有1个处理机忙 碌，其他3个空闲。因此，将有3/8 （即37.5%）的处理机时间被浪费。 （2）面向所有线程平均分配处理机时间。 由于应用程序A中有4个线程，应用程序B中只有1个线程，因此，应为应用程序A分配4/5的 时间，而为应用程序B只分配1/5的时间，如图10-8 （b）所示。此时，将只有15%的处理机时间 被浪费。可见，按线程平均分配处理机时间的方法更有效。 成组调度方式的主要优点是：如果一组相互合作的线程能并行执行，则可有效减少线程阻 塞情况的发生，从而可以减少线程的切换，使系统性能得到改善；此外，因为每次调度都可以 解决一组线程的处理机分配问题，因而可以显著降低调度频率，从而减少调度开销。可见，成 组调度方式的性能优于自调度方式，目前其已获得广泛的认可，并被应用到了多种多处理机操 作系统中。 3．专用处理机分配调度方式 1989年，塔克（Tucker）提出了专用处理机分配（dedicated processor assigement）调度方式。 该方式是指在一个应用程序执行期间，专门为该应用程序分配一组处理机，每个线程配一个处理 机。这组处理机仅供该应用程序使用，直至该应用程序完成。很明显，这会造成处理机的严重浪 费。例如，有一个线程为了和另一个线程保持同步而阻塞起来时，为该线程所分配的处理机就会 空闲。但把这种调度方式用于并发程度相当高的多处理机操作系统中，则是因为下述理由。 首先，在具有数十个乃至数百个处理机的高度并行的系统中，每个处理机的投资费用在整 个系统中只占很小的一部分。对系统的性能和效率来说，单个处理机的利用率已远不像在单处 理机系统中那么重要。 其次，在一个应用程序的整个运行过程中，由于每个进程或线程专用一个处理机，因此可 以完全避免进程或线程的切换，从而大大加速了程序的运行。 塔克在一个具有16个处理机的系统中，运行两个应用程序：一个是矩阵相乘程序，另一个 是快速傅里叶变换程序。每个应用程序所含线程数是可以改变的（从1个到24个）。 图10-9所示为应用程序的加速比与线程数之间的关系。当每个应用程序中含有7～8个线程 时，可获得最高加速比；当每个应用程序中的线程数大于8个时，加速比开始下降。这是因为该 系统中总共只有16个处理机，当两个应用程序都各含有8个线程时，正好是每个线程都能分到1 个处理机；当超过8个线程时，就不能保证每个线程都能分到1个处理机，因而会出现线程切换 问题。可见，线程数越多时切换越频繁，这反而会使加速比下降。因此，塔克建议：同时运行 的应用程序所含的线程数总和不应超过系统中处理机的总数。 由许多相同的处理机所构成的同构型多处理机操作系统，其处理机的分配与单处理机操作 系统中的请求调页式内存分配非常相似。例如，在某时刻应把多少个处理机分配给某应用程序 这一问题，十分类似于将多少个内存物理块分配给某进程。再如，在进行处理机分配时存在着 一个活动工作集的概念，它又类似于请求调页中的工作集。当所分配的处理机数少于活动工作 集时，将会引起线程的频繁切换，这很类似于在请求调页时，当所分配的物理块数少于其工作 集数时，便会引起页面的频繁换入/换出的情况。 4．动态调度方式 动态调度方式允许进程在执行期间动态地改变其线程的数目。这样，OS和应用程序就能够 共同进行调度决策。OS负责将处理机分配给作业，而每个作业负责将分配到的处理机再分配给 自己的某一部分可运行任务。 在这种方法中，OS的调度责任主要限于处理机的分配，并遵循以下原则。 （1）空闲则分配。当一个或多个作业对处理机提出请求时，如果系统中存在空闲的处理 机，则将它（们）分配给这个（些）作业，以满足作业的请求。 （2）新作业绝对优先。所谓新作业，是指新到达的、还没有获得任何一个处理机的作业。 对于请求处理机的多个作业，系统首先会将处理机分配给新作业，如果系统内已无空闲处理 机，则从已分配获得多个处理机的任何一个作业中收回一个处理机，将其分配给新作业。 （3）保持等待。如果系统的任何分配方式都不能满足一个作业对处理机的请求，则作业会 保持未完成状态，直到有处理机空闲并可分配给它使用，或者作业自己取消了这个请求。 （4）释放则分配。当作业释放了一个（或多个）处理机后，即为这个（或这些）处理机扫 描处理机请求队列，并首先为新作业分配处理机，其次按FCFS原则分配剩余的处理机。 动态调度方式优于成组调度方式和专用处理机分配方式，但其开销之大有可能会抵消它的 一部分优势，因此在实际应用中应慎重选择具体的调度方式

linux调度#

• o(1)调度
• cfs
• bfs