线程 Threads

一、概述

MEMO:进程和线程有什么区别？

进程(Process)的两个特性：

Unit of Resource ownership （资源拥有单位）

• 给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件， I/O设备）
• 有状态、优先级、调度

Unit of Dispatching （调度单位）

• 进程是由一个或多个程序的一次执行
• 可能会与其他进程交替执行

线程(Thread)： 进程内一个执行单元或一个可调度实体。

资源拥有单元称为进程（或任务），调度的单位称为线程、又称轻型进程（ light weight process）。

线程只拥有一点在运行中必不可省的资源（程序计数器、一组寄存器和栈） ，但它可与同属一个进程的其它线程共享进程拥有的全部资源。 （拥有少量资源，共享进程的全部资源）

• 不拥有系统资源（只拥有少量的资源，资源是分配给进程）
• 一个进程中的多个线程可并发执行（进程可创建线程执行同一程序的不同部分）
• 系统开销小、切换快。（进程的多个线程都在进程的地址空间活动）

• 有执行状态（状态转换）
• 不运行时保存上下文
• 有一个执行栈
• 有一些局部变量的静态存储
• 可存取所在进程的内存和其他资源
• 可以创建、撤消另一个线程

单线程与多线程进程

二、多线程模型

1.用户级线程 user-level thread

用户级线程：不依赖于OS核心（内核不了解用户线程的存在），应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。

如：数据库系统informix，图形处理Aldus PageMaker。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。

• 用户线程的维护由应用进程完成；
• 内核不了解用户线程的存在；
• 用户线程切换不需要内核特权；
• 用户线程调度算法可针对应用优化；
• 一个线程发起系统调用而阻塞，则整个进程在等待。（一对多模型中）

Three primary thread libraries: POSIX Pthreads 、 Win32 threads、 Java threads

2.内核级线程 kernel-level thread

内核级线程：依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。一个线程发起系统调用而阻塞，不会影响其他线程。时间片分配 给线程，所以多线程的进程获得更多CPU时间。

• 内核维护进程和线程的上下文信息；
• 线程切换由内核完成；
• 时间片分配给线程，所以多线程的进程获得更多CPU时间；
• 一个线程发起系统调用而阻塞，不会影响其他线程的运行。

Examples ：Windows XP/2000 及以后、Solaris、Linux、POSIX Pthreads、Mac OS X

3.多对一模型 Many-to-One

4.一对一模型 One-to-One

EG:Windows NT/XP/2000、Linux、Solaris 9 and later

5.一对多模型 One-to-Many

EG:IRIX、HP-UX、Solaris 9 before

 

三、线程库

1.Pthread

POSIX标准为线程创建和同步定义的API

2.Java线程

JVM

3.Implicit Threading 隐藏多线程

多核系统多线程编程，一个应用程序有可能有几百个甚至上千的线程，这样的程序面临许多挑战：

编程挑战：任务分解、任务的工作量平衡、数据分割、数据依赖、测试与调试

程序执行顺序的正确性问题：同步、互斥

策略：隐私线程Implicit Threading，当前一种流行趋势。

将线程的创建与管理交给编译器和运行时库来完成

几种隐私线程的设计方法：

• Thread Pools（线程池）
• Fork Join
• OpenMP，用于共享内存并行系统的多处理器程序设计的一套指导性编译处理方案。OpenMP支持的编程语言包括C、C++和Fortran。
• Grand Central Dispatch（GCD，大中央调度），Apple for its macOS and iOS operating systems.
• Intel Thread Building Blocks（TBB），Intel开发的构建多线程库，open source ；TBB是一个可移植的C++库，能够运行在Windows、Linux、Macintosh以及UNIX等系统上 。
• Java

---

1.进程和程序的区别：进程有状态，程序没有状态。

2.进程调度是把它的状态改变：Ready and Running（从准备到运行）

3.子进程不会继承父进程的什么：process ID

4.TCB（线程控制块）存储：The machine state（寄存器、程序计数器）

5.多对一模型中，如果一个线程block了，整个进程都会block

6.若一个用户进程通过read系统调用读取一个磁盘的数据：a、b

a.若该文件的数据不在内存、则该进程进入等待状态（磁盘运行读取，CPU不工作）

b.请求read系统调用会导致CPU从用户态切换到核心态

c.read系统调用的参数应包含文件的名称🙅  文件的区名

 7.不管系统是否支持线程，进程都是资源分配的基本单位

用户级线程不需要内核的支持（内核不了解用户线程的存在）

8.下列选项中会导致进程从执行态变为就绪态的事件是 D

A、执行P（wait）操作    B、申请内存失败

C、启动I/O设备                D、被高优先级的进程抢占

9.操作系统中提供了一种进程间的通信机制，把一个进程的标准输出和另一个标准输入连接起来，这种机制称为管道

---

CPU调度

一、Basic Concepts 基本概念

CPU调度（CPU scheduling） = 处理机调度 = 进程调度（Process scheduling）

内容：选择一个进程分配给CPU运行 

CPU scheduling decisions may take place when a process（调度的时机）:

1. Switches from running to waiting state.从运行到等待

2.Switches from running to ready state.从运行到就绪

3.Switches from waiting to ready.从等待到就绪

4.Terminates.终止

两种调度方式：

非抢占式（Nonpreemptive）调度:调度程序一旦把处理机分配给某进程后便让它一直运 行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。如上1 、4

抢占式（Preemptive）调度:当一个进程正在运行时，系统可以基于某种原则，剥夺已 分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则 、时间片原则。如上2、3

MEMO:超指数分布

调度程序：

Dispatcher module gives control of the CPU to the process selected by the shortterm scheduler; this involves:

• switching context
• switching to user mode
• jumping to the proper location in the user program to restart that program

Dispatch latency（调度延迟） – time it takes for the dispatcher to stop one process and start another running调度程序停止一个进程到启动一个进程所需要的时间

Linux命令：vmstat

 

二、Scheduling Criteria 调度准则

1.面向用户(User-oriented)的准则和评价

周转时间Turnaround time ：进程从提交到完成所经历的时间。包括：在CPU上执行，就绪队 列和阻塞队列中等待。

• 周转时间 T=完成时间-提交时间
• 平均周转时间=∑周转时间/进程数
• 带权周转时间W= T(周转时间)/t(CPU执行时间)
• 平均带权周转时间=∑W/进程数

响应时间Response time ：从进程提出请求到首次被响应（而不是输出结果）的时间段（在分 时系统环境下）

等待时间Waiting time – 进程在就绪队列中等待的时间总和

截止时间：开始截止时间和完成截止时间－－实时系统，与周转时间有些相似。

公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长进程等待很长时间。

优先级：可以使关键任务达到更好的指标

2. 面向系统的调度性能准则

吞吐量Throughput ：单位时间内所完成的进程数，跟进程本身特性和调度算法都有关系 －－批处理系统

• 平均周转时间不是吞吐量的倒数，因为并发执行的进程在时间上可以重叠。如：在2 小时内完成4个进程，而每个周转时间是1小时，则吞吐量是2个进程/小时

处理机利用率CPU utilization：使CPU尽可能的忙碌

各种设备的均衡利用：如CPU繁忙的进程和I/O繁忙的进程搭配－－大中型主机

3. 调度算法本身的调度性能准则

• 易于实现
• 执行开销比较小

4.最优准则

• 最大的CPU利用率 Max CPU utilization
• 最大的吞吐量 Max throughput
• 最短的周转时间 Min turnaround time
• 最短的等待时间 Min waiting time
• 最短的响应时间 Min response time
• 公平

 

三、Scheduling Algorithms 调度算法

First-Come, First-Served (FCFS) Scheduling先来先服务调度

Shortest-Job-First (SJF) Scheduling 短作业优先调度

Priority Scheduling 优先权调度

Round Robin (RR) 时间片轮转调度

Multilevel Queue Scheduling 多级队列调度

Multilevel Feedback Queue Scheduling多级反馈队列调度

高响应比优先调度算法 Highest Response Ratio Next(HRRN)

响应比R = (等待时间 + 要求执行时间) / 要求执行时间（考研用） 

1.先到先服务调度FCFS

FCFS算法（非抢占）

• 按照进程或作业提交顺序形成就绪状态的先后次序，分派CPU
• 当前进程或作业占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式 ）
• 在进程或作业唤醒后（如I/O完成），并不立即恢复执行，通常等到当前 作业或进程出让CPU
• 最简单的算法

FCFS的特点

• 比较有利于长进程，而不利于短进程。
• 有利于CPU Bound的进程，而不利于I/O Bound的进程。
• 平均等待时间通常较长
• 

2.最短作业优先调度SJF

又称为“短进程优先”SPF(Shortest Process First)；这是对FCFS算法的改进，其目标是减少 平均周转时间。

SJF算法:

对预计执行时间短的作业（进程）优先分派处理机。

Two schemes:

nonpreemptive – once CPU given to the process it cannot be preempted until completes its CPU burst

preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF)如果新进程到达时，CPU运行时间小于当前执行进程的剩余时间，则抢占。

SJF is optimal – gives minimum average waiting time for a given set of processes.最小平均等待时间

SJF的变形：

最短剩余时间优先SRT(Shortest Remaining Time)-基于抢占的SJF算法

• 允许比当前进程剩余时间更短的进程来抢占

最高响应比优先HRRN(Highest Response Ratio Next)

• 响应比R = (等待时间 + 要求执行时间) / 要求执行时间
• 是FCFS和SJF的折衷