sleep() 背后的算法是什么？

Question

现在有个问题我一直想知道： sleep() 是如何实现的？

如果这一切都是为了使用操作系统的 API，那么 API 是如何制作的呢？

这一切是否都归结为在 CPU 上使用特殊的机器代码？ 该 CPU 是否需要特殊的协处理器或其他小玩意，没有它们就无法 sleep() ？

sleep() 最著名的化身是 C 语言（更准确地说，是在 C 编译器附带的库中，例如 GNU 的 libc），尽管当今几乎每种语言都有其等效项，但某些语言中 sleep 的实现（认为 Bash）不是我们在这个问题中看到的......

编辑：在阅读了一些答案后，我看到该进程被放置在等待队列中。 从那里，我可以猜测两种选择，要么

1. 设置一个计时器，以便内核在适当的时间唤醒进程，要么
2. 每当内核被允许一个时间片时，它会轮询时钟以检查是否到了唤醒进程的时间。

答案只提到替代方案1。因此，我问：这个计时器的行为如何？ 如果这是一个简单的中断来让内核唤醒进程，那么内核如何要求计时器“在 140 毫秒内唤醒我，以便我可以将进程置于运行状态”？

Answer 1

问题的“更新”表明了对现代操作系统如何工作的一些误解。

内核没有“允许”时间片。 内核是为用户进程分配时间片的东西。 “计时器”未设置为唤醒睡眠进程 - 它设置为停止当前正在运行的进程。

本质上，内核试图通过停止在 CPU 上运行时间过长的进程来公平分配 CPU 时间。 简单来说，假设任何进程使用 CPU 的时间都不允许超过 2 毫秒。 因此，内核会将计时器设置为 2 毫秒，并让进程运行。 当定时器触发中断时，内核获得控制权。 它保存正在运行的进程的当前状态（寄存器、指令指针等），并且控制权不会返回给它。 相反，会从等待分配 CPU 的进程列表中挑选另一个进程，并且被中断的进程会移至队列的末尾。

睡眠进程不在等待CPU 的队列中。 相反，它存储在睡眠队列中。 每当内核收到定时器中断时，就会检查睡眠队列，并将到达时间的进程转移到“等待CPU”队列。

当然，这是一种粗略的简化。 它需要非常复杂的算法来确保安全性、公平性、平衡、优先级、防止饥饿，快速完成这一切，并使用最少的内核数据内存。

Answer 2

有一个称为睡眠队列的内核数据结构。 这是一个优先级队列。 每当一个进程被添加到睡眠队列中时，就会计算最早被唤醒的进程的过期时间，并设置一个计时器。 此时，过期的作业将从队列中取出，进程恢复执行。

（有趣的琐事：在较旧的 UNIX 实现中，有一个已调用 fork() 但尚未创建子进程的进程队列。它当然被称为fork 队列< /em>。）

呵呵！

Answer 3

也许操作系统的主要工作是向应用程序编写者隐藏真实硬件的复杂性。 因此，任何关于操作系统如何工作的描述都面临着变得非常复杂、非常快的风险。 因此，我不会处理真正的操作系统需要处理的所有“如果”和“是的但是”。我只是在高概念层面上描述什么是进程，什么是进程调度程序的作用，计时器队列的工作原理，希望这对

什么是进程：有

帮助，我们先来讨论一下进程，稍后再讨论线程。进程有一个 ID（认为是一个整数），您可以将该整数视为包含该进程的所有上下文的表的索引。

上下文 是硬件信息 - -寄存器、内存管理单元内容、其他硬件状态——当加载到机器中时，将允许进程“运行”。还有上下文的其他组件——打开文件的列表、信号处理程序的状态，以及，这里最重要的是，进程正在等待的事情

进程花费大量时间休眠（也称为等待）

进程花费大量时间等待。 例如，读取或写入磁盘的进程将花费大量时间等待数据到达或被确认在磁盘上。 操作系统人员在某种程度上可以互换使用术语“等待”和“睡眠”（以及“阻塞”）——所有这些都意味着该进程正在等待某些事情发生，然后才能继续其愉快的方式。 令人困惑的是，操作系统 API sleep() 恰好使用底层操作系统机制来休眠进程。

进程可以等待其他事情：例如网络数据包到达、窗口选择事件或计时器到期。

进程和调度

正在等待的进程被称为不可运行。 它们不会进入操作系统的运行队列。 但是当进程正在等待的事件发生时，它会导致操作系统将进程从不可运行状态转移到可运行状态。 同时，操作系统将进程放入运行队列，这实际上不是一个队列 - 它更像是所有进程的一堆，如果操作系统决定这样做，可以 运行。

调度：

操作系统定期决定应该运行哪些进程。 毫不奇怪，操作系统决定这样做的算法被称为调度算法。 调度算法的范围从极其简单（“每个人都运行 10 毫秒，然后队列中的下一个人开始运行”）到复杂得多（考虑进程优先级、执行频率、运行时期限、进程间依赖、链锁和各种其他复杂的主题）。

定时器队列
计算机内部有一个计时器。 有很多方法可以实现这一点，但经典的方法称为周期性计时器。 周期性计时器以固定的时间间隔滴答——在当今的大多数操作系统中，我相信这个速率是每秒 100 次——100 Hz——每 10 毫秒。 我将在接下来的内容中使用该值作为具体速率，但要知道大多数有价值的操作系统都可以配置不同的滴答声 - 并且许多操作系统不使用此机制，并且可以提供更好的计时器精度。 但我离题了。

每个刻度都会导致操作系统中断。

当操作系统处理此计时器中断时，它会将系统时间再增加 10 毫秒。 然后，它查看计时器队列并决定需要处理该队列上的哪些事件。

计时器队列实际上是一个“需要处理的事情”的队列，我们​​将其称为事件。 该队列按到期时间排序，最早的事件排在前面。

“事件”可以是“唤醒进程 X”，或者“去那边踢磁盘 I/O，因为它可能已经卡住了”，或者“在那边的光纤通道链路上发送一个保活数据包”。 无论操作系统需要做什么。

当队列以这种方式排序时，管理出队就很容易。 操作系统只是查看队列的头部，并在每个时钟周期将事件的“到期时间”减少 10 毫秒。 当过期时间变为零时，操作系统会将该事件出列，并执行所需的操作。

对于睡眠进程，它只是使进程再次运行。

很简单吧？

Answer 4

至少有两个不同的层次来回答这个问题。 （还有很多其他与之混淆的东西，我不会碰它们）

1. 应用程序级别，这就是 C 库的作用。 这是一个简单的操作系统调用，它只是告诉操作系统在时间过去之前不要为该进程提供 CPU 时间。 操作系统有一个挂起的应用程序队列，以及一些关于它们正在等待什么的信息（通常是时间，或者一些数据出现在某处）。

2. 内核级别。 当操作系统现在没有任何事情可做时，它会执行“hlt”指令。 该指令不执行任何操作，但它永远不会自行完成。 当然，硬件中断是正常服务的。 简而言之，操作系统的主循环看起来像这样（从非常非常远的地方看）：

   allow_interrupts(); 
     而（真）{ 
       hlt; 
       check_todo_queues(); 
     } 
      
   
     
   中断处理程序只是将事情添加到待办事项队列中。   实时时钟被编程为定期（以固定速率）生成中断，或者在下一个进程想要唤醒时在未来的某个固定时间生成中断。

Answer 5

多任务操作系统有一个称为调度程序的组件，该组件负责将CPU时间分配给线程，调用sleep告诉操作系统在一段时间内不要将CPU时间分配给该线程。

有关完整详细信息，请参阅 http://en.wikipedia.org/wiki/Process_states。

Answer 6

我对Linux一无所知，但我可以告诉你Windows上会发生什么。

Sleep() 导致进程的时间片立即结束，将控制权返回给操作系统。 然后，操作系统设置一个计时器内核对象，该对象在时间流逝后收到信号。 然后，操作系统将不再给该进程任何时间，直到内核对象收到信号。 即使如此，如果其他进程具有更高或相同的优先级，它仍然可能会等待一段时间才让该进程继续。

操作系统使用特殊的CPU机器代码来进行进程切换。 这些函数无法通过用户模式代码访问，因此只能通过操作系统的 API 调用来严格访问它们。

Answer 7

本质上，是的，有一个“特殊的小玩意”——它的重要性不仅仅是 sleep() 。

传统上，在 x86 上，这是 Intel 8253 或 8254“可编程间隔定时器”。 在早期的 PC 中，这是主板上的一个独立芯片，可以由 CPU 进行编程，以在预设时间间隔后发出中断（通过“可编程中断控制器”，另一个分立芯片）。 该功能仍然存在，尽管它现在只是更大的主板电路块中的一小部分。

今天的操作系统仍然对 PIT 进行编程以定期唤醒它（在最新版本的 Linux 中，默认情况下每毫秒唤醒一次），这就是内核能够实现抢占式多任务处理的方式。

Answer 8

glibc 2.21 Linux

转发到 nanosleep 系统调用。

glibc 是大多数 Linux 桌面发行版上 C stdlib 的默认实现。

如何找到它：第一反应是：

git ls-files | grep sleep

这包含：

sysdeps/unix/sysv/linux/sleep.c

并且我们知道：

sysdeps/unix/sysv/linux/

包含Linux细节。

在该文件的顶部我们看到：

/* We are going to use the `nanosleep' syscall of the kernel.  But the
   kernel does not implement the stupid SysV SIGCHLD vs. SIG_IGN
   behaviour for this syscall.  Therefore we have to emulate it here.  */
unsigned int
__sleep (unsigned int seconds)

因此，如果您信任评论，我们基本上就完成了。

在底部：

 weak_alias (__sleep, sleep)

基本上是__sleep == sleep。 该函数通过以下方式使用 nanosleep：

result = __nanosleep (&ts, &ts);

在 greppingg: 之后，

git grep nanosleep | grep -v abilist

我们得到了一小部分有趣的事件，我认为 __nanosleep 定义在：

sysdeps/unix/sysv/linux/syscalls.list 

on the line:

nanosleep   -   nanosleep   Ci:pp   __nanosleep nanosleep

这是一些超级 DRY 魔法格式解析为：

sysdeps/unix/make-syscalls.sh

然后从构建目录：

grep -r __nanosleep

引导我们到： /sysd-syscalls 这是 make-syscalls.sh 生成并包含的内容：

#### CALL=nanosleep NUMBER=35 ARGS=i:pp SOURCE=-
ifeq (,$(filter nanosleep,$(unix-syscalls)))
unix-syscalls += nanosleep
$(foreach p,$(sysd-rules-targets),$(foreach o,$(object-suffixes),$(objpfx)$(patsubst %,$p,nanosleep)$o)): \
        $(..)sysdeps/unix/make-syscalls.sh
    $(make-target-directory)
    (echo '#define SYSCALL_NAME nanosleep'; \
     echo '#define SYSCALL_NARGS 2'; \
     echo '#define SYSCALL_SYMBOL __nanosleep'; \
     echo '#define SYSCALL_CANCELLABLE 1'; \
     echo '#include <syscall-template.S>'; \
     echo 'weak_alias (__nanosleep, nanosleep)'; \
     echo 'libc_hidden_weak (nanosleep)'; \
    ) | $(compile-syscall) $(foreach p,$(patsubst %nanosleep,%,$(basename $(@F))),$($(p)CPPFLAGS))
endif

它看起来像是生成文件。 git grep sysd-syscalls 显示它包含在：

sysdeps/unix/Makefile:23:-include $(common-objpfx)sysd-syscalls 

compile-syscall 看起来是关键部分，所以我们发现：

# This is the end of the pipeline for compiling the syscall stubs.
# The stdin is assembler with cpp using sysdep.h macros.
compile-syscall = $(COMPILE.S) -o $@ -x assembler-with-cpp - \
                   $(compile-mkdep-flags)

注意 -x assembler-with- cpp 是一个 gcc 选项。

#define 的参数如下：

#define SYSCALL_NAME nanosleep

然后在以下位置使用它们：

#include <syscall-template.S>

好的，这就是我现在要进行的宏扩展游戏。

我认为这会生成 posix/nanosleep.o 文件，该文件必须与所有内容链接在一起。

Linux 4.2 x86_64 nanosleep syscall

使用调度程序：这不是一个繁忙的睡眠。

搜索 ctags：

sys_nanosleep

引导我们到 kernel/time/hrtimer.c：

SYSCALL_DEFINE2(nanosleep, struct timespec __user *, rqtp,

hrtimer 代表高分辨率计时器。 从那里开始，主线看起来像：

• hrtimer_nanosleep
• do_nanosleep
  • set_current_state(TASK_INTERRUPTIBLE); 这是可中断睡眠
  • freezable_schedule(); 调用 schedule() 并允许其他进程运行
• < code>hrtimer_start_expires
• hrtimer_start_range_ns
• TODO：达到 arch/x86 计时级别
• TODO：上述步骤是直接在系统调用中断处理程序中完成，还是在常规中完成内核线程？

关于它的几篇文章：

• https:// /geeki.wordpress.com/2010/10/30/ways-of-sleeping-in-linux-kernel/
• http://www.linuxjournal.com/article/8144