进程、线程调度模型及其在Windows2000中的实现

类别:软件工程 点击:0 评论:0 推荐:

进程/线程模型

 

在传统的操作系统中,每个进程有一个自己的地址空间以及一个单一的控制流程。事实上,这几乎就是传统操作系统中进程的定义。

 

但是,现实中有很多情况下需要在同一个地址空间中完成并行的任务,比如Web服务器程序,虽然使用多进程方式编程也可以很好地实现服务器,但进程间的数据共享由于需要跨越地址空间而显得十分不方便,同时进程间切换的开销也不可小视。

 

其实这些问题的本质在于两个概念:

1.   资源的分组

2.   指令的执行流程

 

所谓资源分组,是指操作系统以什么为最小单位给用户程序分配资源以及对这些资源进跟踪。这里提到的资源,指的是打开文件、同步对象、管道等,以及进程最重要的标志:地址空间。

在现代操作系统中,进程就是所谓的资源分配的最小单位。一个进程拥有自己独立的地址空间、内核对象表(记录打开文件、同步对象等等)、进程句柄等。

而所谓指令流程,实际上指的是操作系统调度占用CPU的实体,我们称之为“线程”(thread of execution)。

每个线程拥有自己的用户栈、核心栈、程序计数器等,线程与传统的进程类似,也有运行、挂起、就绪等状态,在状态间的转换也类似。但与传统进程所不同的是,线程没有独立的地址空间,所有属于同一个进程的线程共享同一个线性地址空间。

 

由此可知,在线程模型下,操作系统进行资源分配是以进程为单位,而当操作系统进行任务调度时,则以线程为单位进行。当然这并不是说进程和线程间没有直接关系。恰恰相反,进程与线程间的关系非常密切。线程要占用CPU执行预定任务,没有资源是不可能的完成任务的;同时,只有资源而没有指令流的进程也是没有意义的。所以结果是,一个进程至少包含一个线程(称为主线程或初始线程),而一个线程只属于一个进程。

 

线程模型的优点

 

线程的出现,使得在同一个进程环境下进行多道程序设计成为可能。由于同一个进程所属的线程间共享同一地址空间,所以线程间可以能过直接传递指针来传递数据,而这在传统的进程模型下是不可能实现的。不单如此,线程间还可以共享内核对象,使得许多任务得以简化。

比如,同步对象的使用。在传统操作系统中,要将一个同步对象的句柄传递给另一个进程,有两条路可以走:通过父子进程间的继承关系(如Unix中的fork系统调用)或是通过对象命名,然后再在另一个进程中以同样的名字打开。

这两条路那一条都不是很方便。问题的关键在于,同步对象的句柄值只是每个进程对象表中的索引,在另一个进程中是无效的。但在线程模型下,这个问题就迎刃而解了。因为(同一进程中的)线程间共享同一张内核对象表,所以同一个同步对象的句柄对各线程来说都是有效的,传递时只要直接传句柄值就行了。

 

另一个比较实际的例子是字处理软件。假设现在正在编辑一篇重要文章,为了减少由于断电而造成的损失,软件被设定为每隔1分钟自动存盘一次。

如果在传统操作系统下,由于一个进程只有一个执行流,每当2分钟的间隔到达后,进程转向响应定时器软中断(在Unix下为进程收到信号,并执行信号处理过程),这样所有的处理用户输入的代码被挂起,直至磁盘读写完成,信号处理程序返回为止。如果很不幸地,文章非常长,或者用户在软盘或网络驱动器上工作,每次保存文章所花时间为50秒(如果是61秒用户就幸运了,但没人想要这样的幸运),那么用户几乎没有时间去编辑文章,这样的软件特性显然毫无用处。

其实,在用户等待磁盘操作完成的时候,虽然进程对用户的输入无响应,但CPU确实是空闲的(假定没有忙碌的后台进程),理论上CPU应该可以响应用户输入。这样,我们就回到了多任务系统的设计初衷:提高CPU利用率。

我们先来讨论两个不使用线程模型的解决方案:多进程编程和使用异步系统调用。

如果使用多进程方式,则由主进程新建一个工作进程,将需要保存的数据传递给工作进程以进行保存操作。如果需要保存的数据量非常大,内存间的数据复制是一个可观的开销。当然,在较新的操作系统如System V中,由于采用COW(Copy On Write)技术,这个性能损失可以略过。另一个改进办法是使用共享内存,在一些不使用fork方式新建进程的操作系统上这是个好办法。

若使用异步系统调用,则需要编写一系列信号处理程序。主程序在运行时跟踪并记录当前状态,在信号出现时转到信号处理程序,处理完成后根据处理前的状态继续运行。这种方案采用的是有限状态自动机的思想,可以避免多进程操作时的同步及数据传递问题,但它使得程序变得相当复杂。

这两种办法都是可行的,但前者通讯开销比较大,后者如果运行在多CPU主机上,则无法充分利用CPU资源。

 

若使用线程模型,则没有上述两个问题。字处理进程可以采用两个线程,前后界面线程和后台工作线程。界面线程负责响应用户输入,工作线程平进处于挂起状态,并且由主线程定时把它唤醒进行数据保存工作。这样,用户可以在几乎无察觉的情况下定时保存文档。

 

线程的实现

 

由上文的定义,线程为进程中的一个或多个指令执行流,这个机制在现代操作系统的实现主要可分为两大类。即根据操作系统内核是否对线程可感知,分为内核线程和用户线程。

实际上,上文所说的线程是操作系统调度的基本单位,实际上指的只是内核线程。所谓内核线程,其建立与销毁都是由操作系统负责、通过系统调用完成的。操作系统在调度时,参考各进程内的线程运行情况做出调度决定,如果一个进程中没有就绪态的线程,那么这个进程也不会被调度占用CPU。

事实上在Windows 2000中,操作系统进行调度时根本就不理采线程是属于哪个进程的,只是将所有的就绪线程统一排成若干个优先级队列,然后进行调度。在这个情况下,线程的确成了调度的最小单位,所以有时线程也被称为“轻量级进程”。

与内核级线程相对应的,是用户级线程。这类实现多见于一些历史悠久的操作系统(如Unix系列),为了在操作系统中加入线程支持,采用了在用户空间增加运行库来实现线程。这些运行库被称为“线程包”。

用户线程是不能被操作系统所感知的,也就是说操作系统还是一如既往地进行进程调度,就像根本没有线程一样。每当用户进程获得CPU控制权,线程运行库决定该从哪里开始运行,即运行哪一个用户线程。理所当然地,各用户线程之间是非抢占式,一个用户线程会一直运行直至它主动放弃CPU(线程退出、等待同步对象或执行阻塞式系统调用)或是整个进程被操作系统重新调度。

 

用户级线程的优点在于它进行调度时不需要陷入操作系统内核,免去了上下文切换的开销,因而可以达到较高的性能。

 

当然,实现用户级线程有一些比较复杂的问题需要解决。

首先,需要处理阻塞式系统调用。如果没有采取适当的措施,只要某一个线程执行了一个阻塞式的系统调用(如Read),则整个进程就会被操作系统所挂起,直至操作完成,这就违背了线程设计的初衷,因为其它线程无法得到CPU的控制权。

一个解决方案是使用异步系统调用进行替换。在一些操作系统如Unix中,系统支持异步调用并且提供查询系统调用状态的系统调用(Unix中为Select)。这样的话,可以对原来的系统调用库进行改造,用以实现线程包。

Select调用可以查询当前系统调用(如Read)是否安全,即是否会发生阻塞。如果会发生阻塞,则线程包的运行库不会发出真正的系统调用,而是把当前线程挂起,转而执行另一个线程。然后,在下次运行库获得控制权的时候再次检查该调用是否安全,做出是否发出系统调用的决定。

这个解决方案要求线程运行库(run-time)在用户线程每次进程系统调用的时候获取控制权,然后再决定是转发系统调用还是进行用户线程调度。也就说,它得改写原有的系统调用的用户库,插入用来与线程运行库交互的代码。这些插入的代码被称为外套(jacket)或是封装器(wrapper)。

其次的问题发生在出现缺页异常的时候。当出现缺页异常时,操作系统会把通过把外部页读入内存或是别的什么方法,使发生异常的页变为可读。但问题在于,操作系统并不知道用户线程的存在,一旦发生缺页,操作系统会挂起整个进程。

另一个问题就是线程间的非抢占式调度问题。在进程不会切换的情况下,用户线程如果不进行系统调用,那么线程运行库就会不获得控制权,该线程就会保持运行直至其自愿放弃CPU。这使得用户线程间不能轮流使用CPU。

一个可能的解决方案就是由系统传递时钟中断到进程,即操作系统定时给线程运行库发送信号,使其得到控制权并做定时调度成为可能。但这样做的缺点是开销过大。

还有的问题就是用户级线程无法利用多CPU系统的并行处理能力。

 

从实际程序设计模型的角度上来看,用户级线程也有它的弱点。

现在设想有一个多线程的Web服务器程序,接收网络请求并提供服务。理所当然地,它会产生大量的系统调用,而且大部分都是阻塞式的。特别是在等待用户请求的时候,那些系统调用都不是在相对较短的时间内可以解除的。那样的话,每次线程运行库获得控制权时所执行的大量Select大部分都是徒劳无功的。

这就意味着,在一个系统调用较少的程序里,用户线程的性能可以更小一些。但是,在计算密集的程序里,用多线程方式编程又有多大意义呢?这也成了那些反对用户级线程的人的主要理由之一。

 

至于内核线程,由于它是操作系统的一部分,避免了用户级线程所遇到的大量复杂的实现性问题。上文提到过,内核线程有时也被称为轻量级进程,意即它的实现概念与早期的进程有些类似。

内核线程的优势在于其实现的简洁性,一切工作在内核中完成,避免了针对用户库的大量修改。

 

Microsoft Windows 2000中线程的实现

 

在Windows 2000中,线程的实现采用的是内核线程。

当Windows 2000进程被创建时,操作系统为其建立一个默认的初始线程,线程从该可执行文件的入口点开始运行。之后,其它所有的线程都是由初始线程运行时动态调用Win32API创建的。创建线程的API – CreateThread有六个参数,分别是安全信息、线程堆栈大小、线程入口点、入口点参数、创建选项和一个指向用于接收线程ID的变量的指针。

Windows 2000之所以只为每个线程创建一个初始线程,是因为大部分的高级语言都没有用于多线程编程的语义,不能定义多个初始线程。所以所有的额外线程都被设计为需要动态创建。

线程入口点其实指的是新线程开始运行的第一条指令的位置,理论上它可以位于用户空间的任何一处(不考虑内存保护机制),在C语言的语义中即为一个指向函数的指针。另外,操作系统也设计该入口函数带一个参数,为32位值,没有定义其类型(其实也没有必要定义其类型,类型检查是编译器干的事情)。

线程可以创建时可以选择其初始状态:运行或挂起。一个线程可以被创建为挂起状态,然后再进行一些初始化工作,再调用ResumeThread把它激活。

 

Windows 2000中线程的性能良好。

内核线程的弱点之一就是在调度时要进行多次上下文切换,在用户态和内核态之间的多次切换会清空MMU的TLB(由于页表的切换)而产生很多页表查寻操作;在i386的一些操作系统上,还会造成段的切换,开销很大。

这里得提一下Windows 2000的内存策略。它把4GB线性内存地址空间分为高端的2GB和低端的2GB(在Windows 2000 Advanced Server 及以上的系统中可以设置为1GB+3GB),其中高端内存用于在各个进程间共享,存放系统内核;低端用于用户空间。在这种设计下,用户代码陷入内核只是造成特权级的改变,操作系统代码还是位于同一个内存空间,而内存页表无需改变,这样就大大降低了系统调用的开销。当然,这样设计也有缺点,它减少了用户程序可用的地址空间(这就是为什么AD Server要支持3GB内存的原因)。

所以,由于Windows 2000中系统调用的开销较小,所以其内核线程可以达到较理想的性能。

其实Windows 2000还提供了另一个线程的解决方案,即一个线程可以拥有一个或多个纤程(Fiber)。这就是用户线程的一个实现。纤程间的调度都是在用户空间内完成的,实际上是由用户自己完成的。关于纤程的讨论已经超出本文范围。

 

综上所述,线程是现代操作系统中非常重要的特征之一,它在应用程序模型中起的作用也是非常巨大的。而综合比较线程的两种实现方式:用户线程和内核线程,其后者显然更具优势。事实上,比较成功的操作系统诸如Windows 2000等,采用的正是内核线程。

参考书目

1.      《Modern Operating System: Second Edition》 , Andrew S. Tanenbaum

2.      《Operating Systems: Internals and Design Principles 3rd Edition》, William Stallings

本文地址:http://com.8s8s.com/it/it34173.htm