Cracking the coding interview--Q18.2

February 18, 2013
作者:Hawstein
出处:http://hawstein.com/posts/18.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

How can you measure the time spent in a context switch?

译文:

你如何测量一次上下文切换所需时间?

解答

这是一个棘手的问题,让我们先从可能的解答入手。

上下文切换(有时也称为进程切换或任务切换)是指CPU 的控制权从一个进程或线程切换到另一个。 (参考资料) 例如让一个正在执行的进程进入等待状态(或终止它),同时去执行另一个正在等待的进程。 上下文切换一般发生在多任务系统中,操作系统必须把等待进程的状态信息载入内存, 同时保存正在运行的进程的状态信息(因为它马上就要变成等待状态了)。

为了解决这个问题,我们需要记录两个进程切换时第一条指令和最后一条指令的时间戳, 上下文切换就是这两个时间戳的差。

来看一个简单的例子,假设只有两个进程:P1和P2。

P1正在执行,而P2在等待。在某个时刻,操作系统从P1切换到P2。假设此时, P1执行到第N条指令,记录时间戳Time_Stamp(P1_N),当本来在等待的P2 开始执行第1条指令,说明切换完成,记录时间戳Time_Stamp(P2_1)。因此, 上下文切换的时间为:Time_Stamp(P2_1) - Time_Stamp(P1_N)

思路非常简单。问题在于,我们如何知道上下文切换是何时发生的? 进程的切换是由操作系统的调度算法决定的。我们也无法记录进程中每个指令的时间戳。

另一个问题是:许多内核级线程也做上下文切换,而用户对于它们是没有任何控制权限的。

总而言之,我们可以认为,这最多只能是依赖于底层操作系统的近似计算。 一个近似的解法是记录一个进程结束时的时间戳,另一个进程开始的时间戳及排除等待时间。

如果所有进程总共用时为T,那么总的上下文切换时间为: T - (所有进程的等待时间和执行时间)

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview