What is the sleep algorithm ()?

Question

Now I always wondered: how is the sleep () function implemented?

If we are talking about using the API from the OS, then how is the API done?

Does it all come down to using special machine code on the processor? Does this processor require a special coprocessor or other contraption, without which you cannot sleep ()?

The best-known incarnation of sleep () in C (more precisely, in the libraries that come with C compilers, such as GNU libc), although almost every language today has its own equivalent, but the implementation of sleep in some languages ​​(I think Bash) is not something what we consider in this matter ...

EDIT: after reading some of the answers, I see the process being put on a wait queue. From there, I can suggest two alternatives:

• the timer is set so that the kernel wakes up the process at the appointed time or
• whenever a time slice is allowed to the kernel, it checks the clock to see if that time has started the process.

The answers only mention alternative 1. Therefore, I ask: how does this timer behave? If this is a simple interrupt to force the kernel to wake up the process, how can the kernel ask the timer "wake me up in 140 milliseconds so that I can start the process at runtime"?

Answer 1

An “update” to the question shows some misunderstanding of how modern OSs work.

The kernel is not "allowed" by the time slice. A kernel is what gives out time slices for user processes. A "timer" is not set to wake the sleeping process - it is set to stop the current process.

In essence, the kernel is trying to honestly distribute processor time by stopping processes that have been running on the processor for too long. For a simplified image, suppose that no process is allowed to use the processor for more than 2 milliseconds. Thus, the kernel would set the timer to 2 milliseconds, and let the process start. When the timer starts an interrupt, the kernel gains control. It saves the current state of the current process (registers, instruction pointer, etc.), and the control does not return to it. Instead, another process is selected from the list of processes waiting to receive the CPU, and the process that was interrupted moved to the back of the queue.

A sleeping process is simply not in the queue for things waiting for the CPU. Instead, it is stored in a sleeping queue. Whenever the kernel receives a timer interrupt, the wait queue is checked, and processes whose time has come are transferred to the CPU queue wait queue.

This, of course, is a gross simplification. It requires very sophisticated algorithms to ensure security, fairness, balance, prioritization, and starvation prevention, doing all this quickly and with minimal memory used for kernel data.

Answer 2

There is a kernel data structure called wait queues. This is a priority queue. Whenever a process is added to the wait queue, the expiration time of the fastest waking process is calculated and a timer is set. At this time, the elapsed task is removed from the queue, and the process resumes execution.

(funny little things: in old unix implementations, there was a queue for processes for which fork () was called, but for which a child process was not created. Of course, it was called fork queue .)

NTN!

Answer 3

Perhaps the main task of the operating system is to hide the complexity of real hardware from the application writer. Therefore, any description of how the OS works risks becoming really complex, very fast. Accordingly, I am not going to deal with all the “what if” and “yes, but” with which a real operating system is needed. I will simply describe at a high conceptual level what the process is, what the scheduler does, how the timer queue works. Hope this is helpful.

Which process:

Think of a process - let's just talk about processes and move on to threads later - like "what the operating system plans." A process has an identifier - I think an integer - and you can represent this integer as an index into a table containing the entire context of this process.

Context is hardware information - registers, contents of the memory management unit, another state of equipment, which, when loaded into the machine, will allow the process to "go". There are other components of the context - lists of open files, the state of signal handlers and, most importantly, what the process expects.

Processes spend a lot of sleep time (waiting aka)

The process spends most of its time waiting. For example, a process that reads or writes to disk will spend a lot of time waiting for data to arrive or confirm output. OS people use the terms “waiting” and “sleeping” (and “blocked”) somewhat interchangeably - all this means that the process expects something before it can continue its fun journey. It is simply confusing that the OS API sleep () is used to use the underlying OS mechanisms for sleeping processes.

Processes can wait for other things: for example, network packets arrive, events of window selection or timer expiration.

Processes and planning

Processes that are waiting are considered to be inactive. They are not included in the execution queue of the operating system. But when an event occurs that the process is waiting for, it causes the operating system to move the process from a non-transition state to a runnable state. At the same time, the operating system puts a process in the execution queue, which is not really a queue - it is rather a bunch of all processes that, if the operating system decided to do this, could work.

Planning:

the operating system regularly decides which processes should be performed. The algorithm by which the operating system decides to do this is called, somewhat unsurprisingly, the scheduling algorithm. Planning algorithms range from "dead" ("everyone gets it in 10 ms, and then the next guy in the queue starts up") is much more complicated (taking into account the priority of the process, frequency of execution, deadlines, interprocess dependencies, chain locks and all kinds of other complex objects).

Timer Queue The computer has a timer. There are many ways this can be implemented, but the classic way is called a periodic timer. The periodic timer goes off at regular intervals - in most operating systems today I believe that this speed is 100 times per second - 100 Hz - every 10 milliseconds. I will use this value in the future as a specific speed, but I know that most operating systems worthy of their salt can be configured with different ticks - and many of them do not use this mechanism and can provide much better timer accuracy. But I'm distracted.

Each tick leads to an interruption of the operating system.

When the OS processes this timer interrupt, it increases its view of the system time by another 10 ms. Then he looks at the timer queue and decides which events in this queue need to be addressed.

The timer queue really is a queue of “things to solve”, which we will call events. This queue is ordered by expiration time, first speedy event.

The “event” may be something like “the process of waking X” or “going back and forth, because it may have stuck”, or “sending a keepalive packet to this fiber link over there.” No matter what was to make an operating system.

When you have a queue arranged in this way, it is easy to manage decoupling. The OS simply looks at the head of the queue and reduces the "time to expiration" of the event by 10 ms every tick. When the expiry time expires to zero, the OS cancels this event and does whatever it takes.

In the case of a sleeping process, it simply causes the process to start again.

Simple, huh?

Answer 4

A multitasking operating system has a component called a scheduler; this component is responsible for giving processor time to threads; a sleep call tells the OS not to give processor time to this thread for some time.

see http://en.wikipedia.org/wiki/Process_states for full details.

Answer 5

there are at least two different levels to answer this question. (and many other things that embarrass him, I will not touch them)

• application level, this is what the C library does. This is a simple OS call, it just tells the OS not to give processor time to this process until the time passes. The OS has a queue of suspended applications and some information about what they are waiting for (usually either time, or some data appears somewhere).

• kernel level. when the OS does not have the right to do something right now, it executes the "hlt" instruction. this instruction does nothing, but it never ends on its own. Of course, a hardware interrupt is serviced normally. Simply put, the main OS loop looks like this (very very far):

   allow_interrupts ();
   while (true) {
     hlt;
     check_todo_queues ();
   }
  

  interrupt handlers just add things to todo queues. The real-time clock is programmed to generate interrupts either periodically (at a fixed speed) or at some specific time in the future when the next process wants to wake up.

Answer 6

I don't know anything about Linux, but I can tell you what is happening on Windows.

Sleep () immediately terminates the process to return control to the OS. The OS then sets up the timer core object, which receives the signal after the time has elapsed. After that, the OS will not give this process more time until the kernel object is signaled. Even then, if other processes have a higher or equal priority, it can still wait a bit before allowing the process to continue.

A special processor code is used by the operating system to switch processes. These functions cannot be accessed by user mode code, therefore they are accessed strictly by API calls in the OS.

Answer 7

In fact, yes, there is a “special thing” - and this is important for much more than just sleep ().

Classically, on x86 it was the Intel 8253 or 8254 Programmable Timer Interval. On earlier PCs, it was a separate chip on the motherboard that could program the CPU to acknowledge an interrupt (via the Programmable Interrupt Controller, another discrete chip) after a given time interval. Functionality still exists, although it is now a tiny part of a much larger block of motherboard circuits.

OS today still programs PIT to wake it up regularly (in recent versions of Linux, every millisecond by default), and that is how the kernel can implement proactive multitasking.

Answer 8

glibc 2.21 Linux

Go to nanosleep system call.

glibc is the standard implementation for stdlib on most Linux distributions of Linux.

How to find him: first reflex:

 git ls-files | grep sleep 

It contains:

 sysdeps/unix/sysv/linux/sleep.c 

and we know that:

 sysdeps/unix/sysv/linux/ 

contains Linux features.

At the top of this file we see:

 /* 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) 

So, if you trust the comments, we do mostly.

At the bottom:

  weak_alias (__sleep, sleep) 

which basically says __sleep == sleep . The function uses nanosleep through:

 result = __nanosleep (&ts, &ts); 

After greppingg:

 git grep nanosleep | grep -v abilist 

we get a small list of interesting entries, and I think __nanosleep is defined in:

 sysdeps/unix/sysv/linux/syscalls.list 

in line:

 nanosleep - nanosleep Ci:pp __nanosleep nanosleep 

which is some supermaster DRY format processed by:

 sysdeps/unix/make-syscalls.sh 

Then from the build directory:

 grep -r __nanosleep 

Leads us to: /sysd-syscalls , which is what make-syscalls.sh generates and contains:

 #### 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 

It looks like part of the Makefile. git grep sysd-syscalls shows that it is enabled:

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

compile-syscall looks like a key part, so we find:

 # 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) 

Note that -x assembler-with-cpp is a gcc option.

#define options, such as:

 #define SYSCALL_NAME nanosleep 

and then use them at:

 #include <syscall-template.S> 

Well, this is until I continue the game to expand the macro.

I think then it generates a posix/nanosleep.o file that should be connected with everything.

Linux 4.2 x86_64 nanosleep syscall

Uses the scheduler: this is not a busy dream.

Search ctags:

 sys_nanosleep 

Leads us to kernel/time/hrtimer.c :

 SYSCALL_DEFINE2(nanosleep, struct timespec __user *, rqtp, 

hrtimer stands for High Resolution Timer. From there, the main line looks like this:

• hrtimer_nanosleep
• do_nanosleep
  • set_current_state(TASK_INTERRUPTIBLE); which is intermittent sleep
  • freezable_schedule(); that calls schedule() and allows you to start other processes
• hrtimer_start_expires
• hrtimer_start_range_ns
• TODO: reach arch/x86 time level

A few articles about this:

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