OS NOTES

Chapter4 Threads

第四章 多线程编程！

Posted by LvKouKou on April 10, 2023

Threads

Objectives

  • To introduce the notion of a thread—a fundamental unit of CPUutilization that forms the basis of multithreaded computer systems
  • To discuss the APIs for the Pthreads, Windows, and Java threadlibraries
  • To explore several strategies that provide implicit threading
  • To examine issues related to multithreaded programming

  • To cover operating system support for threads in Windows and Linux

  • 介绍线程的概念 - CPU利用率的基本单位，构成多线程计算机系统的基础
  • 讨论 Pthreads、Windows 和 Java 线程库的 API
  • 探索提供隐式线程的几种策略
  • 检查与多线程编程相关的问题
  • 涵盖操作系统对Windows和Linux中线程的支持

Process/Thread的概念区分

  • Resource ownership - process includes a virtual address space to hold the process image

  • Scheduling/execution- follows an execution path that may be interleaved with other processes

These two characteristics are treated independently by the operating system

Separate two ideas:

  • Process: Ownership of memory, files, other resources

  • Thread: Unit of execution we use to dispatch

在上一章中我们认为进程有两个特点：

  • 资源所有权 - 进程包括用于保存进程映像的虚拟地址空间

  • 调度/执行 - 遵循可能与其他进程交错的执行路径

这两个特征由操作系统独立处理

在本章中我们分开两个想法：

  • 进程：内存、文件和其他资源的所有权

  • 线程：我们用来调度的执行单元

Process–Resource ownership

  • Have a virtual address space which holds the process image

  • Protected access to processors, other processes, files, and I/O resources

Thread–Scheduling/Execution

  • An execution state (running, ready, etc.)
  • Saved thread context when not running
  • Some per-thread static storage for local variables
  • Access to the memory and resources of its process

流程–资源所有权

  • 具有保存进程映像的虚拟地址空间

  • 对处理器、其他进程、文件和 I/O 资源的受保护访问

线程–调度/执行

  • 执行状态（正在运行、就绪等）

  • 未运行时保存的线程上下文

  • 局部变量的一些每线程静态存储

  • 访问其进程的内存和资源

1. 概述

Operating system supports multiple threads of execution within a single process

操作系统支持单个进程中的多个执行线程

每个线程是CPU使用的一个基本单元;它包括线程ID、程序计数器、寄存器组和堆栈。它与同一进程的其他线程共享代码段、数据段和其他操作系统资源，如打开文件和信号。

image-20230410093204069

image-20230410092911146

1.1 Motivation

Most modern applications are multithreaded

Threads run within application

Multiple tasks with the application can be implemented by separate threads

  • Update display
  • Fetch data
  • Spell checking
  • Answer a network request

Process creation is heavy-weight while thread creation is light-weight

Can simplify code, increase efficiency

Kernels are generally multithreaded

大多数现代应用程序都是多线程的

线程在应用程序中运行

应用程序的多个任务可以由单独的线程实现

  • 更新显示
  • 获取数据
  • 拼写检查
  • 应答网络请求

进程创建重量级，线程创建量级轻量级

可以简化代码，提高效率

内核通常是多线程的

1.2 Benefits

  • Responsiveness – may allow continued execution if part of process is blocked, especially important for user interfaces

  • Resource Sharing – threads share resources of process, easier than shared memory or message passing

  • Economy – cheaper than process creation, thread switching lower overhead than context switching

  • Scalability – process can take advantage of multiprocessor architectures

  • 响应能力——如果部分进程被阻塞，可能允许继续执行，这对用户界面尤其重要

  • 资源共享——线程共享进程资源，比共享内存或消息传递更容易，进程只能通过如共享内存和消息传递之类的技术共享资源。这些技术应由程序员显式地安排。不过，线程默认共享它们所属进程的内存和资源。代码和数据共享的优点是:它允许一个应用程序在同一地址空间内有多个不同活动线程

  • 经济——比进程创建更便宜，线程切换比上下文切换开销更低

  • 可扩展性——进程可以利用多处理器架构

2. Multicore Programming 多核编程

对于单核系统，并发仅仅意味着线程随着时间推移交错执行(图4-3)，因为处理核只能同一时间执行单个线程。不过，对于多核系统，并发表示线程能够并行运行，因为系统可以为每个核分配一个单独线程(图4-4)。

image-20230410154921112

2.1 挑战

Multicore or multiprocessor systems putting pressure on programmers, challenges include:

  • Dividing activities
  • Balance
  • Data splitting
  • Data dependency
  • Testing and debugging

Parallelism implies a system can perform more than one task simultaneously

Concurrency supports more than one task making progress

  • Single processor / core, scheduler providing concurrency

Types of parallelism

  • Data parallelism – distributes subsets of the same data across multiple cores, same operation on each
  • Task parallelism – distributing threads across cores, each thread performing unique operation

As of threads grows, so does architectural support for threading

  • CPUs have cores as well as hardware threads
  • Consider Oracle SPARC T4 with 8 cores, and 8 hardware threads per core

多核或多处理器系统给程序员带来了压力，挑战包括：

  • 划分活动（识别任务）
  • 平衡
  • 数据拆分
  • 数据依赖性
  • 测试和调试

并行性意味着系统可以同时执行多个任务

并发支持多个任务取得进展

  • 单处理器/内核，提供并发的调度程序

2.2 并行类型

并行的类型

  • 数据并行性 – 将相同数据的子集分布在多个内核上，在每个内核上执行相同的操作
  • 任务并行性 – 跨内核分配线程，每个线程执行独特的操作

随着线程的增长，线程的体系结构支持也在增长

  • CPU具有内核和硬件线程
  • 考虑具有 8 个内核和每个内核 8 个硬件线程的 Oracle SPARC T4

3. 多线程模型

有两种不同的方法来提供线程支持：User Threads and Kernel Threads

  • User threads - management done by user-level threads library
  • Three primary thread libraries:
    • POSIX Pthreads
    • Windows threads
    • Java threads
  • Kernel threads - Supported by the Kernel
  • Examples – virtually all general purpose operating systems, including:
    • Windows
    • Solaris
    • Linux
    • Tru64 UNIX
    • Mac OS X
  • 用户线程 - 由用户级线程库完成管理
  • 三个主要线程库：
    • POSIX Pthreads
    • Windows threads
    • Java threads
  • 内核线程 - 内核支持
  • 示例 – 几乎所有通用操作系统，包括：
    • Windows
    • Solaris
    • Linux
    • Tru64 UNIX
    • Mac OS X

image-20230410155617938

内核进程就是去ready队列中排队，获得CPU时间后将时间分配给用户线程的。

用户线程和内核线程之间必然存在某种关系，我们研究3种常用的关系：

  • Many-to-One
  • One-to-One
  • Many-to-Many

3.1 多对一

  • Many user-level threads mapped to single kernel thread
  • One thread blocking causes all to block
  • Multiple threads may not run in parallel on muticore system because only one may be in kernel at a time
  • Few systems currently use this model
  • Examples:
    • Solaris Green Threads
    • GNU Portable Threads
  • 许多用户级线程映射到单个内核线程
  • 一个线程阻塞导致所有阻塞
  • 因为一次只有一个线程可能位于内核中，所以多个线程可能无法在多核系统上并行运行，
  • 目前很少有系统使用此模型
  • 例子：
  • 索拉里斯绿线
    • GNU可移植线程

3.2 一对一

该模型在一个线程执行阻塞系调用时，能够允许另一个线程继续执行，所以它提供了比多对一模型更好的并发功能;它也允多个线程并行运行在多处理器系统上。这种模型的唯一缺点是，创建一个用户线程就要创建一相应的内核线程。由于创建内核线程的开销会影响应用程序的性能，所以这种模型的大多数9现限制了系统支持的线程数量。

  • Each user-level thread maps to kernel thread
  • Creating a user-level thread creates a kernel thread
  • More concurrency than many-to-one
  • Number of threads per process sometimes restricted due to overhead
  • Examples
    • Windows
    • Linux
    • Solaris 9 and later
  • 每个用户级线程映射到内核线程
  • 创建用户级线程会创建内核线程
  • 比多对一更并发
  • 每个进程的线程数有时由于开销而受到限制
  • 例子
  • Windows
    • Linux
    • Solaris 9 及更高版本

image-20230410160355292

3.3 多对多

开发人员可以创建任意多的用户线程，并且相应内核线程能在多处理器系统上并发执行。而且，当一个线程执行阻塞系统调用时，内核可以调度另一个线程来执行。

  • Allows many user level threads to be mapped to many kernel threads

  • Allows the operating system to create a sufficient number of kernel threads

  • Examples
    • Solaris prior to version 9
    • Windows with the ThreadFiber package
  • 允许将许多用户级线程映射到许多内核线程
  • 允许操作系统创建足够数量的内核线程

  • 例子

    • 版本 9 之前的 Solaris
    • 带有ThreadFiber软件包的Windows。

3.3.1 双层模型

多对多模型的一种变种仍然多路复用多个用户级线程到同样数量或更少数量的内核线程，但也允许绑定某个用户线程到一个内核线程。这个变种，有时称为双层模型(tow-level model)(图48)。优点是可以保证关键线程不会受到其他线程影响而阻塞（一对一），保证关键线程的正常运行。

  • Similar to M:M, except that it allows a user thread to be bound to kernel thread
  • Examples
    • IRIX
    • HP-UX
    • Tru64 UNIX
    • Solaris 8 and earlier
  • 与M：M类似，不同之处在于它允许用户线程绑定到内核线程
  • 例子
  • IRIX
    • HP-UX
    • Tru64 UNIX
    • Solaris 8 and earlier

image-20230410161343444

image-20230410161415939

注意看，b、c图中进程不是在running状态，但是线程处于running状态。

这是因为用户线程是都用户级线程库管理的，可以在任意时候处于running状态，但不一定真的在running。因为CPU时间需要有内核线程来分配，只有分配了CPU时间且处于running状态的用户线程才真正在running。

4. Thread Libraries 线程库

Thread library provides programmer with API for creating and managing threads

Two primary ways of implementing

  • Library entirely in user space
  • Kernel-level library supported by the OS

线程库为程序员提供了创建和管理线程的 API

两种主要的实现线程库的方式

  • 1、线程库完全在用户空间

  • 2、操作系统支持的内核级库

  • 第一种方法是，在用户空间中提供一个没有内核支持的库。这种库的所有代码和数据结构都位于用户空间。这意味着，调用库内的一个函数只是导致了用户空间内的一个本地函数的调用，而不是系统调用。
  • 第二种方法是，实现由操作系统直接支持的内核级的一个库。对于这种情况，库内的代码和数据结构位于内核空间。调用库中的一个 API函数通常会导致对内核的系统调用。

目前使用的三种主要线程库是:POSIX Pthreads、Windows、Java。

  • Pthreads作为POSIX标准的扩展，可以提供用户级或内核级的库。

  • Windows 线程库是用于 Windows操作系统的内核级线程库。

  • Java 线程 API允许线程在 Java 程序中直接创建和管理。

然而，由于大多数JVM实例运行在宿主操作系统之上，Java 线程API通常采用宿主系统的线程库来实现。这意味着在 Windows 系统上，Java 线程通常采用 Windows API来实现，而在UNIX和Linux系统中采用Pthreads来实现

5. Implicit Threading 隐式多线程

随着多核处理的日益增多，出现了拥有数百甚至数千线程的应用程序。设计这样的应用程序不是一个简单的事情:程序员不仅处理之前所列的挑战，而且还要面对其他的困难这些困难，与程序正确性有关，将在第6章和第7章中加以讨论。 针对解决这些困难并且更好支持设计多线程程序，有一种方法是将多线程的创建与管理交给编译器和运行时库来完成。这种策略称为隐式线程(implicit threading)，是一种流行趋势。在这节中，为了利用多核，我们探讨了三种可供选择的、基于隐式线程的、多线程程序的设计方法。

  • Growing in popularity as numbers of threads increase, program correctness more difficult with explicit threads
  • Creation and management of threads done by compilers and run-time libraries rather than programmers
  • Three methods explored
    • Thread Pools
    • OpenMP
    • Grand Central Dispatch

  • Other methods include Microsoft Threading Building Blocks (TBB), java.util.concurrent package

  • 随着线程数量的增加而越来越受欢迎，显式线程使程序正确性变得更加困难
  • 隐式线程：由编译器和运行时库而不是程序员完成线程的创建和管理
  • 探索了三种方法
    • 线程池
    • OpenMP
    • 大中央调度
  • 其他方法包括 Microsoft Threading Building Blocks (TBB)、java.util.concurrent 包

5.1 Thread Pools 线程池

线程池的主要思想是:在进程开始时创建一定数量的线程，并加到池中以等待工作。当服务器收到请求时，它会唤醒池内的一个线程(如果有可用线程)，并将需要服务的请求传递给它。一旦线程完成了服务，它会返回到池中再等待工作。如果池内没有可用线程，那么服务器会等待，直到有空线程为止。

即服务器先一次性创建大量的线程，下次需要线程时不用创建线程，直接在线程库中选一个。

Create a number of threads in a pool where they await work Advantages:

  • Usually slightly faster to service a request with an existing thread than create a new thread
  • Allows the number of threads in the application(s) to be bound to the size of the pool
  • Separating task to be performed from mechanics of creating task allows different strategies for running task
    • i.e.Tasks could be scheduled to run periodically
  • Windows API supports thread pools:
1
2
3
4
5

DWORD WINAPI PoolFunction(AVOID Param) {
/*
* this function runs as a separate thread.
*/
}

在等待工作的池中创建多个线程 优点：

  • 使用现有线程处理请求通常比创建新线程稍快
  • 允许将应用程序中的线程数绑定到池的大小
  • 将要执行的任务与创建任务的机制分开，允许运行任务的不同策略
    • 即任务可以安排为定期运行
  • Windows API 支持线程池：

5.2 OpenMP

5.3 Grand Central Dispatch 大中央调度

6. 多线程问题

  • Semantics of fork() and exec() system calls
  • Signal handling
    • Synchronous and asynchronous
  • Thread cancellation of target thread
    • Asynchronous or deferred
  • Thread-local storage

  • Scheduler Activations

  • fork（） 和 exec（） 系统调用的语义
  • 信号处理
    • 同步和异步
  • 目标线程的线程取消
    • 异步或延迟
  • 线程本地存储
  • 调度程序激活

6.1 系统调用 fork（） 和 exec（）

6.2 信号处理

6.3 线程撤销

6.4 线程本地存储

CATALOG
    FEATURED TAGS
    Computer-Organization NOTES Project AI OS ML PatternRecognition Blog Distributed-System ANN CPU设计 CompilationPrinciple