小土刀

【计算机系统导论】6.2 进程与线程

进程(抽象1)和线程(抽象2)都是抽象。以五种抽象作为展开的脉络

消息(抽象5)


  • 单处理器调度(长期、中期、短期)
  • 多处理器调度(粒度、设计问题、进程调度、县城调度)
  • 并行处理(进程创建、竞争条件、信号量)
  • 进程控制(执行模式、进程创建、进程切换)
  • 进程和线程(多线程、线程特性)
  • 并发原理(竞争条件、进程交互、互斥要求)
  • 互斥(硬件支持、中断禁用、专用机器指令)
  • 信号量(互斥、生产者/消费者问题、信号量的实现)
  • 消息传递(同步、寻址、消息格式、排队原则、互斥)
  • 读者-写者问题
  • 死锁原理(可重用资源、可消耗资源、死锁条件)
  • 死锁预防(互斥、占有且等待、不可抢占、循环等待)
  • 哲学家就餐(信号量解决)
  • UNIX 的并发机制(管道、消息、共享内存、信号量信号)
  • Linux 内核并发机制(原子操作、自旋锁、信号量、屏障)
  • Windows 并发机制(等待函数、分派器对象、临界区、轻量级读写锁和条件变量)

操作系统是控制程序在处理器上执行和管理该处理器资源的软件。操作系统具有许多功能,包括进程调度和存储管理,但这些功能的实现离不开处理器硬件的支持。事实上,所有处理器都或多或少具备这种能力,如虚拟存储器管理硬件和进程管理硬件。这些硬件包括专用寄存器、缓冲器以及完成基础资源管理任务的电路。

操作系统最重要的功能之一是进程或任务的调度,操作系统决定在给定时间内运行哪个进程。一般情况下,硬件不断中断运行进程,使操作系统做出新的调度裁决,从而使处理器时间被几个进程公平分配。

操作系统的另一个重要功能是存储管理。大多数当代操作系统都包含虚拟存储器的功能,虚拟存储器有两个优点:1)进程在主存中运行时不需要将程序的全部指令和数据一次性地装入主存;2)程序可用的总存储空间可以大大超过系统的实际主存容量。虽然存储管理是用软件完成的,但操作系统依赖于处理器中的硬件支持,包括分页管理硬件和分段管理硬件。

我们可以把操作系统看成是用于说明指令系统层没有的体系结构特性的解释器。其主要部分有虚拟内存、虚拟输入/输出指令和用于并行处理的一些工具。

虚拟内存是一种体系结构特性,它的目的是为了允许程序使用比计算机的物理内存更多的地址空间,或者是提供一个一致的和灵活的内存保护及共享机制。虚拟内存的实现方式有页式、段式和段页式。在页式虚拟内存中,地址空间被分成大小相等的虚拟页。其中的某些页被映射到物理页帧,其他的页则不映射。对映射页的访问将由 MMU 转换到正确的物理地址。引用一个没有映射的页将产生一个缺页。

在操作系统曾,最重要的输入 / 输出抽象是文件。文件由一系列的字节活着逻辑记录组成,读写文件时并不需要知道磁盘、磁带和其他输入/输出设备是如何工作的。文件可以顺序访问,也可以通过记录号或者主键进行随机访问。目录可以用来把文件分成组。文件可以保存在连续的扇区中或者零散地分布在磁盘上。在后一种情况下(这种情况在硬盘上经常发生),需要使用数据结构来定位文件的块。系统可以通过使用链表活着位图来掌握空闲的磁盘存储区的情况。

并行处理通常采用多个进程分时使用一个 CPU 的方式来模拟和实现。如果不对进程间通信加以控制,将会导致竞争条件。为了解决这一问题,引入了同步原语,信号量就是同步原语的一个简单的例子。使用信号量,可以很容易并且很完美地解决生产者-消费者问题。

UNIX 和 XP 是复杂操作系统的两个例子。它们都支持分页和内存映射文件。它们也都支持层次型的文件系统,其中文件都是由字节序列组成的。最后一点,UNIX 和 XP 都支持进程和线程以及用于进程和线程的同步机制

进程

是一个系统抽象,给应用程序一个假象,好像它是系统中唯一的 job

机制:创造,销毁,挂起,上下文切换,发送信号,IPC 等等

如何在多个进程间共享系统资源?

进程管理

进程创建

进程销毁

进程状态

PCB

竞争条件

进程同步

子进程

非本地跳转

进程调度

线程

线程是一个处理器抽象,假装每个执行的上下文都有一个处理器。

Process is the unit of resource ownership, while Thread is the unit of instruction execution

如何在不同进程的线程中共享 cpu?
如何在相同进程的线程的共享 cpu?

单线程与多线程

用户线程和内核线程

对比

协程

编程珠玑番外篇-Q 协程的历史,现在和未来 http://blog.youxu.info/2014/12/04/coroutine/

计算机科学是一门应用科学,几乎所有概念都是为了理解或解决实际问题而生的。协程 (Coroutine) 的出现也不例外。协程的概念,最早可以追溯到写作 COBOL 语言编译器中的技术难题。

从磁带到协程
COBOL 是最早的高级语言之一。编译器则是高级语言必不可少的一部分。现如今,我们对编译器了解,已经到了可以把核心内容浓缩成一本教科书的程度。然而在六十年代,如何写作高效的语言编译器是那个时代绕不过的现实问题。比如,1960 年夏天,D. E. Knuth 就是利用开车横穿美国去加州理工读研究生的时间,对着 Burroughs 205 机器指令集手写 COBOL 编译器。最早提出“协程”概念的 Melvin Conway 的出发点,也是如何写一个只扫描一遍程序 (one-pass) 的 COBOL 编译器。众多的“高手”纷纷投入编译器书写,可见一门新科学发展之初也是筚路蓝缕

以现代眼光来看,高级语言编译器实际上是多个步骤组合而成:词法解析,语法解析,语法树构建,以及优化和目标代码生成等等。编译实质上就是从源程序出发,依次将这些步骤的输出作为下一步的输入,最终输出目标代码。在现代计算机上实现这种管道式的架构毫无困难:只需要依次运行,中间结果存为中间文件或放入内存即可。GCC 和 Clang 编译器,以及 ANTLR 构建的编译器,都遵循这样的设计。

在 Conway 的设计里,词法和语法解析不再是两个独立运行的步骤,而是交织在一起。编译器的控制流在词法和语法解析之间来回切换:当词法模块读入足够多的 token 时,控制流交给语法分析;当语法分析消化完所有 token 后,控制流交给词法分析。词法和语法分别独立维护自身的运行状态。Conway 构建的这种协同工作机制,需要参与者“让出 (yield)”控制流时,记住自身状态,以便在控制流返回时能够从上次让出的位置恢复(resume)执行。简言之,协程的全部精神就在于控制流的主动让出和恢复。我们熟悉的子过程调用可以看作在返回时让出控制流的一种特殊的协程,其内部状态在返回时被丢弃了,因此不存在“恢复”这个操作。

自顶向下,无需协同
虽然协程是伴随着高级语言诞生的,它却没有能像子过程一样成为通用编程语言的基本元素。

从 1963 年首次提出到上个世纪九十年代,我们在 ALOGL, Pascal, C, FORTRAN 等主流的命令式编程语言中都没有看到原生的协程支持。协程只稀疏地出现在 Simula,Modular-2 (Pascal 升级版) 和 Smalltalk 等相对小众的语言中。协程作为一个比子进程更加通用的概念,在实际编程却没有取代子进程,这一点不得不说是出乎意外的。如果我们结合当时的程序设计思想看,这一点又是意料之中的:协程是不符合那个时代所崇尚的“自顶向下”的程序设计思想的,自然也就不会成为当时主流的命令式编程语言 (imperative programming) 的一部分。

正如面向对象的语言是围绕面向对象的开发理念设计一样,命令式编程语言是围绕自顶向下(top-down)的开发理念设计的。在自顶向下的理念指导下,程序被切分为一个主程序和大大小小的子模块,每一个子模块又可能调用更多子模块等等。C 家族语言的 main() 函数就是这种自顶而下思想的体现。在这种理念指导下,各模块形成层次调用关系,而程序设计就是制作这些子过程。在“自顶向下”这种层次化的理念下,具有鲜明层次的子过程调用成为软件系统最自然的组织方式,也是理所当然。相较之下,具有执行中让出和恢复功能的协程在这种架构下无用武之地。可以说,自上而下的设计思想从一开始就排除了对协程的需求。其后的结构化编程(Structural Programming) 思想,更是进一步强化了“子过程调用作为唯一控制结构”的基本假设。在这样的指导思想下,协程一直没有成为当时编程语言的一等公民。

尽管从提出到上世纪 90 年代,协程在编程语言中没有普遍成为一等公民,但作为一种易于理解的控制结构,协程的概念渗入到了软件设计的许多方面。在结构化编程思想一统天下之时, D. Knuth 曾经专门写过一篇 “Structured Programming with GOTO” 来为 GOTO 语句辩护。在他列出的几条 GOTO 可以方便编程且不破坏程序结构的例子中,有一个(例子7b)就是用 GOTO 实现协程控制结构。相比较之下,不用 GOTO 的“结构化”代码反而失去了良好的结构。当然,追求实际结果的工业界对于学界的这场要不要剔除 GOTO 的争论并不感冒。当时许多语言都附带了不建议使用的 GOTO 语句,显得左右逢源。这方面一个最明显的例子就是 Java:其语言本身预留了 goto 关键字,其编译器却没有提供任何的支持,可以说在 goto 这场争论中做足了中间派。

实践中,协程的思想频繁应用于任务调度和流处理上。比如,UNIX 管道就可以看成是众多命令间的协同操作。当然,管道的现代实现都是以 pipe() 系统调用和进程间的通信为基础,而非简单遵循协程的 yield/resume 语法。

许多协同式多任务操作系统,也可以看成协程运行系统。说到协同式多任务系统,一个常见的误区是认为协同式调度比抢占式调度“低级”,因为我们所熟悉的桌面操作系统,都是从协同式调度(如 Windows 3.2, Mac OS 9 等)过渡到抢占式多任务系统的。实际上,调度方式并无高下,完全取决于应用场景。抢占式系统允许操作系统剥夺进程执行权限,抢占控制流,因而天然适合服务器和图形操作系统,因为调度器可以优先保证对用户交互和网络事件的快速响应。当年 Windows 95 刚刚推出的时候,抢占式多任务就被作为一大买点大加宣传。协同式调度则等到进程时间片用完或系统调用时转移执行权限,因此适合实时或分时等等对运行时间有保障的系统。

另外,抢占式系统依赖于 CPU 的硬件支持。 因为调度器需要“剥夺”进程的执行权,就意味着调度器需要运行在比普通进程高的权限上,否则任何“流氓(rogue)”进程都可以去剥夺其他进程了。只有 CPU 支持了执行权限后,抢占式调度才成为可能。x86 系统从 80386 处理器开始引入 Ring 机制支持执行权限,这也是为何 Windows 95 和 Linux 其实只能运行在 80386 之后的 x86 处理器上的原因。而协同式多任务适用于那些没有处理器权限支持的场景,这些场景包含资源受限的嵌入式系统和实时系统。在这些系统中,程序均以协程的方式运行。调度器负责控制流的让出和恢复。通过协程的模型,无需硬件支持,我们就可以在一个“简陋”的处理器上实现一个多任务的系统。我们见到的许多智能设备,如运动手环,基于硬件限制,都是采用协同调度的架构。

协程的复兴和现代形式
编程思想能否普及开来,很大程度上在于应用场景。协程没有能在自顶向下的世界里立足,却在动态语言世界里大放光彩,这里最显著的例子莫过于 Python 的迭代器和生成器。

回想一下在 C 的世界里,循环的标准写法是 for (i = 0; i < n; ++i) { … }。 这行代码包含两个独立的逻辑, for 循环控制了 i 的边界条件, ++i 控制了 i 的自增逻辑。这行代码适用于 C 世界里的数组即内存位移的范式,因此适合大多数访问场景。到了 STL 和复杂数据结构的世界,因为许多数据结构只支持顺序访问,循环往往写成: for (i = A.first(); i.hasNext();i = i.next()) { … }

这种设计抽象出了一个独立于数据结构的迭代器,专门负责数据结构上元素访问顺序。迭代器把访问逻辑从数据结构上分离出来, 是一个常用的设计模式 (GoF 23个设计模式之一).我们在 STL 和 Java Collection 中也常常看到迭代器的身影。

在适当的时候,我们可以更进一步引入一个语法糖(脚注:这里牵涉到一个外部迭代器和内部迭代器的问题。限于篇幅不在此讨论)将循环写成: for i in A.Iterator() {func(i)}。

事实上,许多现代语言都支持类似的语法。这种语法抛弃了以 i 变量作为迭代指针的功能,要求迭代器自身能够记住当前迭代位置,调用时返回下一个元素。读者不难看到,这种架构就是我们在文章开始提到的语法分析器的架构。正因为如此,我们可以从协程的角度来理解迭代器:当控制流转换到迭代器上时,迭代器负责生成和返回下一个元素。一旦下一个元素准备就绪,迭代器就让出控制流。这种特殊的迭代器实现在 Python 中又被成为生成器。以协程的角度切入的的好处是设计大大精简。实际上,在 Python 中,生成器本身就是一个普通的函数,和普通函数的唯一不同是它的返回语句是协程风格的 yield。这里,yield 一语双关,既是让出控制流,也是生成迭代器的返回值。

以上我们仅仅讨论了生成器的最基本的特性。实际上,生成器的强大之处在于我们可以像 UNIX 管道一样串联起来,组成所谓的生成器表达式。如果我们有一个可以生成 1,2,3 … 的生成器 N,则 square = (i 2 for i in N) 就是一个生成平方数的生成器表达式。注意这里圆括号语法和](http://en.wikipedia.org/wiki/List_comprehension) 方括号语法的区别,square = [i 2 for i in N] 是生成一个具体的列表。我们可以串联这些生成器表达式,最终的控制流会在这些串联的部分间转换,无需我们写作复杂的嵌套调用。当然,yield 只是冰山的一角,现代的 Python 语言还充分利用了 yield 关键字构建了 yield from 语句,(yield) 语法等等,使得我们无困难的将协程的思想融入到 Python 编程中去。限于篇幅这里不再展开。

我们前面说过,协程的思想本质上就是控制流的主动让出和恢复机制。在现代语言里,可以实现协程思想的方法很多,这些实现间并无高下之分,所区别的就是是否适合应用场景。理解这一点,我们对于各种协程的分类,如半对称/对称协程,有栈与无栈协程等具体实现就能提纲挈领,无需在实现细节上纠结。

协程在实践中的实现方式千差万别,一个简单的原因,是协程本身可以通过许多基本元素构建。基本元素的选取方式不一样,构建出来的协程抽象也就有差别。比如, Lua 语言选取了 create, resume 和 yield 作为基本构建元素, 从调度器层面构建出所谓的“非对程”协程系统。而 Julia 语言绕过调度器,通过在协程内调用 yieldto 函数完成了同样的功能,构建出了一个所谓的对称协程系统。尽管这两个语言使用了同样的 setjmp 库,构造出来的原语却不一样。又比如,许多 C 语言的协程库都使用了 ucontext 库实现,这是因为 POSIX 本身提供了 ucontext 库,不少协程实现是以 ucontext 为蓝本实现的。这些实现,都不可避免地带上了 ucontext 系统的一些基本假设,比如协程间是平等的,一般带有调度器来协调协程等等(比如 libtask 实现,以及云风的 coroutine 库)。Go 语言的一个鲜明特色就是通道(channel)作为一级对象。因此,resume 和 yield 等在其他语言里的原语在 go 里都以通道方式构建。我们还可以举出许多同样的例子。这些风格的差异往往和语言的历史,演化路径,和要解决的问题相关,我们不必苛求他们的协程模型一定要如此这般。

总的来说,协程为协同任务提供了一种运行时抽象。这种抽象非常适合于协同多任务调度和数据流处理。在现代操作系统和编程语言中,因为用户态线程切换代价比内核态线程小,协程成为了一种轻量级的多任务模型。我们无法预测未来,但是可以看到,协程已经成为许多擅长数据处理的语言的一级对象。随着计算机并行性能的提升,用户态任务调度已经成为一种标准的多任务模型。在这样的大趋势下,协程这个简单且有效的模型就显得更加引人注目。

异常

硬件与操作系统必须协同工作才能按照我们期望的方式处理异常。硬件一般暂停指令流中导致异常的指令,同时执行完该指令前的所有指令,清除该指令后的所有指令,并且设置一个寄存器描述异常发生的原因,保存导致异常发生的指令的地址,然后跳转到预先确定的地址开始执行。操作系统则查看异常发生的原因并才去相应的操作。对于一个未定义指令异常、硬件错误异常或算数溢出异常,操作系统通常终止执行的程序并返回原因描述。对于 I/O 设备请求活操作系统服务调用,操作系统保存程序的当前状态,执行期望的任务,然后重新载入程序继续运行。在 I/O 设备请求的情况下,我们可能需要在继续执行发出 I/O 设备请求的任务前先运行另一个任务,因为该任务一般在 I/O 完成之后才能继续执行。这就是保存和恢复任务状态如此重要的原因。一个最重要且频繁出现的异常是页缺失与 TLB 异常。

在操作系统开始进行异常处理和保存处理器所有状态位的时候,操作系统特别脆弱。例如,如果在操作系统中正在处理第一个异常时,另一个异常又发生了,控制单元将重写异常程序计数器,就不能返回引起缺页的那条指令。我们可以通过提供禁止异常 disable exception 和使能异常 exception enable 来避免这种错误的发生。当异常第一次发生时,处理器设置一个位,禁止其他异常的发生;这可以与处理器设置管理态位同时进行。随后操作系统保存足够的状态,如果有另一个异常发生——异常程序计数器 EPC 和异常引发寄存器也能正确恢复。异常程序计数器和异常引发寄存器是协助处理异常、TLB 缺失以及缺页的两个特殊控制寄存器。而后操作系统可以重新允许异常发生。这些步骤保证了异常不会使处理器丢失任何状态,因此也就不会出现无法重新执行中断指令的情况。

陷阱

中断

系统调用

故障

信号

机制

进程组

发送与接收信号

中断信号

消息传递

消息传递是一个沟通抽象,假装可靠的传输(甚至是有序的)

您的支持是对我创作最大的鼓励!

热评文章