Part I - 操作系统调度(翻译)

chenxull · · 592 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Part I - 操作系统调度

简介

多线程程序是如何正确的调度工作的,在这里作者给出了很多详细的例子一步步深入。

OS Scheduler

您的程序只是一系列需要一个接一个顺序执行的机器指令。为了实现这一点,操作系统使用了线程的概念。线程的任务是说明并顺序执行分配给它的指令集。执行一直持续到线程不再有指令可执行。这就是为什么我称线程为“执行路径”

您运行的每个程序都创建一个进程,每个进程都有一个初始线程。线程能够创建更多的线程。所有这些不同的线程彼此独立运行,调度决策是在线程级别而不是在进程级别做出的。线程可以并行运行(每个线程在单个内核上轮流运行),也可以并行运行(每个线程在不同内核上同时运行)。线程还保持自己的状态,以允许安全、本地和独立地执行它们的指令。

如果有线程可以执行,操作系统调度器负责确保内核不空闲。它还必须制造一种错觉,以为所有可以执行的线程都在同时执行。在创建这种错觉的过程中,调度程序需要运行优先级高于低优先级线程的线程。然而,优先级较低的线程不能缺少执行时间。调度程序还需要通过做出快速而明智的决策来尽可能减少调度延迟。

Executing Instructions

程序计数器(PC)有时被称为指令指针(IP),它允许线程跟踪下一条要执行的指令。在大多数处理器中,PC指向下一条指令,而不是当前指令。

Listing1

goroutine 1 [running]:
   main.example(0xc000042748, 0x2, 0x4, 0x106abae, 0x5, 0xa)
       stack_trace/example1/example1.go:13 +0x39                 <- LOOK HERE
   main.main()
       stack_trace/example1/example1.go:8 +0x72                  <- LOOK HERE

复制代码

这些数字代表从各自函数顶部偏移的PC值。+0x39PC偏移值表示如果程序没有死机,线程将在示例函数中执行的下一条指令。如果控制碰巧回到main功能,则0+x72PC偏移值是主功能内部的下一条指令。更重要的是,指针之前的指令告诉你正在执行什么指令。

下面是源码:

package main

func main() {
	example(make([]string, 2, 4), "hello", 10)
}
func example(slice []string, str string, i int) {
	panic("want stack trace")
}

复制代码

十六进制数+0x39代表example函数内部指令的PC偏移量,该偏移量比该函数的起始指令低57(10进制)字节。在下面的清单3中,您可以从二进制文件中看到示例函数的objdump。找到列在底部的第12条指令。请注意,该指令上方的代码行是panic的的调用。

Listing3

TEXT main.example(SB) stack_trace/example1/example1.go
func example(slice []string, str string, i int) {
  0x104dfa0		65488b0c2530000000	MOVQ GS:0x30, CX
  0x104dfa9		483b6110		CMPQ 0x10(CX), SP
  0x104dfad		762c			JBE 0x104dfdb
  0x104dfaf		4883ec18		SUBQ $0x18, SP
  0x104dfb3		48896c2410		MOVQ BP, 0x10(SP)
  0x104dfb8		488d6c2410		LEAQ 0x10(SP), BP
	panic("Want stack trace")
  0x104dfbd		488d059ca20000	LEAQ runtime.types+41504(SB), AX
  0x104dfc4		48890424		MOVQ AX, 0(SP)
  0x104dfc8		488d05a1870200	LEAQ main.statictmp_0(SB), AX
  0x104dfcf		4889442408		MOVQ AX, 0x8(SP)
  0x104dfd4		e8c735fdff		CALL runtime.gopanic(SB)
  0x104dfd9		0f0b			UD2              <--- LOOK HERE PC(+0x39)
复制代码

Thread States

A Thread can be in one of three states: Waiting, Runnable or Executing.

  • 等待:这意味着线程停止并等待一些东西来继续。这可能是因为等待硬件(磁盘、网络)、操作系统(系统调用)或同步调用(原子、互斥体)。这些类型的延迟是性能不佳的根本原因。
  • 可运行:这意味着线程需要时间在内核上,这样它就可以执行分配给它的机器指令。如果您有很多线程需要时间,那么线程必须等待更长时间才能获得时间。此外,随着更多线程争夺时间,任何给定线程获得的单独时间量都会缩短。这种调度延迟也可能是性能不佳的原因。
  • 执行:这意味着线程已经被放置在一个核心上,并且正在执行它的机器指令。与应用程序相关的工作正在完成。这是每个人都想要的。

Types Of Work

线程可以做两种类型的工作。第一种叫做CPU-Bound ,第二种叫做IO-Bound。

  • CPU-Bound :这种工作不会造成线程可能处于等待状态的情况。这是一项不断进行计算的工作。将圆周率计算到第n位的线程将是CPU-Bound 。
  • IO-Bound:这种工作会造成线程进入等待状态,这项工作包括请求通过网络访问资源或对操作系统进行系统调用。需要访问数据库的线程将是IO绑定的。我将包括同步事件(互斥体、原子),这些事件会导致线程作为这个类别的一部分等待。

Context Switching

如果您运行在 Linux, Mac or Windows上,那么您运行在一个具有抢占式调度程序的操作系统上。这意味着一些重要的事情。

  • 首先,这意味着当涉及到在任何给定时间选择运行什么线程时,调度器是不可预测的。线程优先级和事件(如在网络上接收数据)使得无法确定调度程序将选择什么样的操作和时间。
  • 第二,这意味着你绝不能基于你有幸经历过但不能保证每次都发生的感知行为来编写代码。允许自己思考很容易,因为我已经看到这种情况以同样的方式发生了1000次,这是有保证的行为。如果您的应用程序需要确定性,则必须控制线程的同步和编排

内核中线程的物理切换被称为上下文切换,当调度程序从内核中取出一个执行线程并用一个可运行线程替换它时,就会出现Context Switching。从运行队列中选择的线程将进入执行状态。被拉的线程可以移回可运行状态(如果它仍然能够运行),或者移回等待状态(如果由于输入输出绑定类型的请求而被替换)。

Context Switching是昂贵的。

如果您有一个专注于 IO-Bound work的程序,那么上下文切换将是一个优势。一旦一个线程进入等待状态,另一个处于可运行状态的线程将取代它的位置。这使得核心总是在工作。这是scheduling最重要的方面之一。如果有工作要做(线程处于可运行状态),不要让内核空闲。

如果您的程序专注于面向CPU-Bound work的工作,那么上下文切换将是一场性能噩梦。由于Thead总是有工作要做,Context Switching 正在阻止这项工作取得进展。这种情况与面向 IO-Bound 负载形成了鲜明的对比。

Less Is More

在处理器只有一个内核的早期,调度并不太复杂。因为您只有一个处理器和一个内核,所以在任何给定时间只能执行一个线程。其想法是定义一个调度周期,并尝试在该周期内执行所有的可运行线程。没问题:用调度周期除以需要执行的线程数。

例如,如果您将调度器周期定义为10ms(毫秒),并且有2个线程,那么每个线程都有5毫秒。如果你有5个线程,每个线程得到2毫秒。然而,当您有100个线程时会发生什么?给每个线程10微秒的时间片是行不通的,因为您将在上下文切换中花费大量时间。

你需要的是限制时间片可以有多短。在最后一种情况下,如果最小时间片是2毫秒,并且有100个线程,调度器周期需要增加到2000毫秒或2秒。如果有1000个线程,现在您会看到一个20秒的调度周期。在这个简单的例子中,如果每个线程使用它的完整时间片,那么所有线程运行一次需要20秒。

请注意,这是一个非常简单的世界观。在做出调度决策时,调度程序需要考虑和处理更多的事情。您可以控制应用程序中使用的线程数量。当有更多的线程需要考虑,并且与输入输出相关的工作正在发生时,就会有更多的混乱和不确定的行为。事情需要更长的时间来安排和执行。

这就是为什么游戏规则是“少即是多”。处于可运行状态的线程越少,意味着调度开销越少,每个线程随着时间推移获得的时间越多。处于可运行状态的线程越多,意味着每个线程随着时间流逝获得的时间越少。这意味着随着时间的推移,你完成的工作也越来越少。

Find The Balance

您需要在拥有的内核数量和为应用程序获得最佳吞吐量所需的线程数量之间找到一个平衡。谈到管理这种平衡,线程池是一个很好的答案。我将在第二部分中向您展示,这在Go中不再是必需的。我认为这是Go让多线程应用程序开发变得更容易的一件好事。

在go编码之前,我在的C与C++程序设计学习与实验系统和C#写代码。在该操作系统上,使用IOCP((IO Completion Ports))线程池对于编写多线程软件至关重要。作为一名工程师,您需要计算出您需要多少个线程池以及任何给定池的最大线程数,以最大化您所获得的内核数的吞吐量。

当编写与数据库通信的网络服务时,每个内核3个线程的神奇数量似乎总能在NT上提供最佳吞吐量。换句话说,每个内核3个线程最小化了上下文切换的延迟成本,同时最大化了内核上的执行时间。当创建一个IOCP线程池时,我知道对于我在主机上识别的每个内核,从最少1个线程和最多3个线程开始。

如果我每个内核使用2个线程,完成所有工作需要更长的时间,因为我有空闲时间,而我本来可以完成工作。如果我每个内核使用4个线程,也需要更长的时间,因为我在上下文切换中有更多的延迟。无论出于什么原因,每个内核3个线程的平衡似乎总是NT上的神奇数字.

如果您的服务正在做许多不同类型的工作呢?这可能会造成不同且不一致的延迟。也许它还会产生许多需要处理的不同的系统级事件。也许不可能找到一个对所有不同的工作负荷始终有效的神奇数字。当谈到使用线程池来调整服务的性能时,找到正确的一致配置可能会变得非常复杂。

##Cache Lines

从主内存访问数据的延迟成本非常高(约100到约300个时钟周期),以至于处理器和内核都有本地缓存来将数据保存在需要它的硬件线程附近。根据所访问的缓存,从缓存中访问数据的成本要低得多(约3到约40个时钟周期)。如今,性能的一个方面是如何高效地将数据输入处理器,以减少这些数据访问延迟。编写改变状态的多线程应用程序需要考虑缓存系统的机制。

使用cache line在处理器和主存储器之间交换数据。cache line是在主存储器和高速缓存系统之间交换的64字节内存块。每个内核都有自己需要的cache line,这意味着硬件使用value semantics。这就是多线程应用程序中内存突变会造成性能噩梦的原因。

当并行运行的多个线程访问相同的数据值或者甚至彼此接近的数据值时,它们将访问同一高速缓存行(cache line)上的数据。在任何内核上运行的任何线程都将获得同一缓存行的自己的副本。

如果给定内核上的一个线程对其缓存行的副本进行了更改,那么通过硬件,同一缓存行的所有其他副本都必须被标记为脏的。当线程试图对脏缓存行进行读或写访问时,需要主存储器访问(大约100到大约300个时钟周期)来获得缓存行的新副本。

也许在双核处理器上这没什么大不了的,但是并行运行32个线程的32核处理器在同一高速缓存行上访问和更改数据呢?一个有两个物理处理器,每个处理器有16个内核的系统怎么样?由于处理器间通信的延迟增加,情况会更糟。应用程序将会在内存中反复运行,性能将会非常糟糕,而且很可能你不会明白为什么。

这被称为缓存一致性问题,也引入了错误共享等问题。当编写将改变共享状态的多线程应用程序时,必须考虑缓存系统。

Scheduling Decision Scenario 调度基本决策

想象一下,我让你根据我给你的高级信息编写操作系统调度程序。想想这个你必须考虑的场景。请记住,这是调度程序在做出调度决策时必须考虑的许多有趣的事情之一。

您启动应用程序,主线程被创建并在核心1上执行。当线程开始执行其指令时,因为需要数据,所以正在检索高速缓存行(cache lines )。线程现在决定为一些并发处理创建一个新线程。问题是这样的。一旦线程被创建并准备就绪,调度器应该:

  • 上下文切换核心1的主线程?这样做有助于提高性能,因为这个新线程需要已经缓存的相同数据的可能性非常大。但是主线程没有得到它的完整时间片。
  • 在主线程的时间片完成之前,线程是否要等待内核1变得可用?线程没有运行,但是一旦启动,获取数据的延迟将被消除。
  • 让线程等待下一个可用的内核吗?这意味着所选内核的缓存行将被刷新、检索和复制,从而导致延迟。然而,线程会更快地启动,并且主线程可以完成它的时间片。 这些是操作系统调度程序在做出调度决策时需要考虑的有趣问题。幸运的是,不是我做的。我能告诉你的是,如果有一个空闲的内核,它将被使用。当线程可以运行时,您希望它们运行。

小结

这篇文章的第一部分提供了在编写多线程应用程序时,关于线程和操作系统调度器的一些见解。这些也是Go计划程序要考虑的事情。在下一篇文章中,我将描述Go调度器的语义以及它们如何与这些信息相关联。最后,通过运行几个程序,您将看到所有这些都在起作用。


有疑问加站长微信联系(非本文作者)

本文来自:掘金

感谢作者:chenxull

查看原文:Part I - 操作系统调度(翻译)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

592 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传