sleep() 뒤에 있는 알고리즘은 무엇입니까?

sleep() 뒤에 있는 알고리즘은 무엇입니까?

여기서 항상 궁금했던 것이 있습니다: sleep()은 어떻게 구현됩니까?

OS에서 API를 사용하는 것이 전부라면 API는 어떻게 만들어질까요?

이 모든 것은 CPU에 특별한 기계 코드를 사용하는 것으로 요약됩니까? CPU에 특별한 보조 프로세서나 sleep()이 없으면 사용할 수 없는 기타 기구가 필요합니까?

sleep()의 가장 잘 알려진 화신은 C(정확히 말하면 GNU의 libc와 같은 C 컴파일러에 부속된 라이브러리)입니다.오늘날 거의 모든 언어가 동등한 기능을 가지고 있지만, 일부 언어(생각컨대 Bash)에서의 sleep 구현은 이 질문에서 우리가 보고 있는 것이 아닙니다.

EDIT: 몇 가지 답변을 읽으면 프로세스가 대기열에 있는 것을 알 수 있습니다.거기서 두 가지 대안을 짐작할 수 있다.

1. 커널이 적절한 시간에 프로세스를 웨이크업하도록 타이머가 설정됩니다.
2. 커널이 타임 슬라이스를 허용할 때마다 프로세스를 웨이크업할 시간이 되었는지 확인하기 위해 클럭을 폴링합니다.

답변에는 대안 1만 언급되어 있습니다.따라서 이 타이머는 어떻게 동작합니까?커널이 프로세스를 웨이크업 하는 단순한 인터럽트라면 커널은 어떻게 타이머에 "프로세스를 실행 상태로 만들 수 있도록 140밀리초 후에 웨이크업"을 요구할 수 있습니까?

문제의 "업데이트"는 최신 OS의 구조에 대한 오해를 나타내고 있습니다.

커널은 타임슬라이스를 "허용"할 수 없습니다.커널은 사용자 프로세스에 타임 슬라이스를 제공하는 것입니다."타이머"는 sleeve 프로세스를 기동하도록 설정되어 있지 않습니다.현재 실행 중인 프로세스를 정지하도록 설정되어 있습니다.

기본적으로 커널은 CPU에 너무 오래 있는 프로세스를 정지함으로써 CPU 시간을 균등하게 분배하려고 합니다.예를 들어 간단한 그림에서는 어떤 프로세스도 CPU를 2밀리초 이상 사용할 수 없다고 가정합니다.따라서 커널은 타이머를 2밀리초로 설정하고 프로세스를 실행합니다.타이머가 인터럽트를 기동하면 커널이 제어됩니다.실행 중인 프로세스의 현재 상태(레지스터, 명령 포인터 등)를 저장하며 제어는 반환되지 않습니다.대신 CPU를 할당받기 위해 대기 중인 프로세스 목록에서 다른 프로세스가 선택되고 중단된 프로세스가 큐의 뒤로 이동합니다.

sleep 프로세스는 단순히 CPU를 기다리는 대기열에 포함되지 않습니다.대신 sleep 큐에 저장됩니다.커널이 타이머 인터럽트를 받을 때마다 sleep 큐가 체크되고 시간이 된 프로세스가 "CPU 대기" 큐로 전송됩니다.

물론 이것은 엄청난 단순화입니다.보안, 공정성, 균형, 우선순위 부여, 기아 방지, 커널 데이터에 사용되는 최소한의 메모리로 모든 작업을 신속하게 수행하기 위해서는 매우 정교한 알고리즘이 필요합니다.

glibc 2.21 Linux

전송 .nanosleep시스템 콜을 실행합니다.

glibc는 대부분의 Linux 데스크톱 Distros에서 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);

그리핑 후:

git grep nanosleep | grep -v abilist

의 작은 을 볼 수 있는데, 제 에는 그런 것 요. 그리고 제 생각엔__nanosleep다음에서 정의됩니다.

sysdeps/unix/sysv/linux/syscalls.list 

회선:

nanosleep   -   nanosleep   Ci:pp   __nanosleep nanosleep

이는 다음과 같이 해석되는 슈퍼 드라이 매직 포맷입니다.

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 나노 슬립 시스템 스콜

스케줄러를 사용합니다.비지 sleep이 아닙니다.

검색 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()할 수 합니다.
• 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

운영체제의 주요 업무는 실제 하드웨어의 복잡성을 애플리케이션 라이터로부터 숨기는 것입니다.따라서 OS가 어떻게 동작하는지에 대한 설명은 매우 복잡하고 빠르게 진행될 위험이 있습니다.따라서 실제 운영체제가 다루어야 하는 모든 "가정"과 "예"에 대해서는 다루지 않습니다.프로세스의 개요, 스케줄러의 동작, 타이머 큐의 동작에 대해 대략적으로 설명하겠습니다.이게 도움이 됐으면 좋겠네요.

프로세스란?

프로세스(프로세스에 대해서는 잠시 이야기하고 스레드에 대해서는 나중에 설명하겠습니다)는 "운영 체제가 스케줄 하는 것"이라고 생각합니다.프로세스에는 ID(정수)가 있으며, 이 정수는 해당 프로세스의 모든 컨텍스트를 포함하는 테이블의 인덱스로 간주할 수 있습니다.

콘텍스트는 하드웨어 정보(레지스터, 메모리 관리 유닛의 내용, 기타 하드웨어 상태 등)로, 머신에 로드되면 프로세스가 "시작"됩니다.컨텍스트에는 열려 있는 파일의 리스트, 신호 핸들러 상태, 그리고 가장 중요한 것은 프로세스가 기다리고 있는 것 등 다른 컴포넌트가 있습니다.

프로세스는 수면(대기)에 많은 시간을 소비합니다.

프로세스는 대부분의 시간을 대기하는 데 소비합니다.예를 들어, 디스크에 읽거나 쓰는 프로세스는 데이터가 도착하거나 디스크에서 삭제될 때까지 기다리는 데 많은 시간을 소비합니다.OS 담당자는 '대기 중'과 '절전 중'(및 '차단')이라는 용어를 어느 정도 번갈아 사용합니다.이 모든 것은 프로세스가 계속 진행되기 전에 어떤 일이 일어나기를 기다리고 있다는 것을 의미합니다.OS API sleep()이 sleep 프로세스에 기본 OS 메커니즘을 사용하는 것은 혼란스러울 뿐입니다.

프로세스는 네트워크 패킷이 도착하거나 윈도우 선택 이벤트가 발생하거나 타이머가 만료될 때까지 대기할 수 있습니다.

프로세스 및 스케줄링

대기 중인 프로세스는 실행할 수 없다고 합니다.운영 체제의 실행 큐에 들어가지 않습니다.그러나 프로세스가 대기 중인 이벤트가 발생하면 운영 체제가 프로세스를 실행 불가능 상태에서 실행 불가능 상태로 전환합니다.동시에 운영체제는 실행 큐에 프로세스를 배치합니다.이것은 실제로는 큐가 아닙니다.이것은 운영체제가 실행하기로 결정하면 실행될 수 있는 모든 프로세스의 더미에 가깝습니다.

스케줄링:

operating system은 정기적으로 어떤 프로세스를 실행할지 결정합니다.오퍼레이팅시스템이 그렇게 결정하는 알고리즘을 스케줄링 알고리즘이라고 부르는 것은 당연합니다.스케줄링 알고리즘은 데드 심플('모두 10밀리초 동안 실행 후 큐의 다음 사용자가 실행')에서 훨씬 더 복잡한 것(프로세스 우선순위, 실행 빈도, 런타임 마감, 프로세스 간 의존관계, 연쇄 잠금 및 기타 모든 복잡한 주제를 고려)까지 다양합니다.

타이머 큐A 컴퓨터에는 타이머가 내장되어 있습니다.이를 구현할 수 있는 방법은 여러 가지가 있지만 일반적으로는 정기 타이머라고 불립니다.정기 타이머는 정기적으로 틱하고 있습니다.오늘날 대부분의 운영체제에서는 이 레이트는 10밀리초마다 100회(100Hz)라고 생각합니다.구체적인 환율로 이 값을 사용하겠습니다만, 가치가 있는 대부분의 operating system은 다른 틱으로 구성할 수 있습니다.많은 operating system은 이 메커니즘을 사용하지 않기 때문에 타이머의 정밀도가 크게 향상됩니다.하지만 나는 주제에서 벗어났군.

체크 표시를 할 때마다 운영 체제가 중단됩니다.

OS는 이 타이머 인터럽트를 처리할 때 시스템 시간을 10ms 더 늘립니다.그런 다음 타이머 큐를 보고 해당 큐에서 처리해야 할 이벤트를 결정합니다.

타이머 큐는 이벤트라고 하는 "처리할 필요가 있는 것"의 큐입니다.이 큐는 만료 시간, 가장 빠른 이벤트 순으로 정렬됩니다.

"이벤트"는 "프로세스 X를 웨이크업" 또는 "디스크 I/O가 막혀서 저쪽에서 킥" 또는 "저쪽 파이버 채널 링크로 킵얼라이브 패킷을 전송"과 같은 경우가 있습니다.운영체제가 해야 할 일이라면 무엇이든.

이렇게 큐를 주문하면 큐잉을 쉽게 관리할 수 있습니다.OS는 큐의 선두만 보고 이벤트의 "만료 시간"을 틱마다 10ms씩 단축합니다.유효기간이 0이 되면 OS는 해당 이벤트를 큐 해제하고 필요한 모든 작업을 수행합니다.

sleep 프로세스의 경우 프로세스를 다시 실행할 수 있게 합니다.

간단하죠?

sleep 큐라고 불리는 커널 데이터 구조가 있습니다.우선 순위 큐입니다.sleep 큐에 프로세스가 추가될 때마다 가장 빨리 깨어날 프로세스의 유효시간을 산출하여 타이머를 설정한다.이 때 만료된 작업이 큐에서 해제되고 프로세스가 실행을 재개한다.

(오래된 trivia: 오래된 UNIX 구현에서는 fork()가 호출되었지만 하위 프로세스가 생성되지 않은 프로세스에 대한 큐가 있었습니다.물론 포크 큐라고 불렸습니다.)

HTH!

이 질문에 대답할 수 있는 최소한 두 가지 수준이 있습니다.(그 밖에도 혼란스러운 것은 많이 있습니다만, 저는 만지지 않습니다.)

1. 어플리케이션 레벨, 이것이 C 라이브러리가 하는 일입니다.이것은 단순한 OS 호출이며, OS에 시간이 지날 때까지 CPU에 시간을 주지 않도록 지시할 뿐입니다.OS에는 일시정지된 애플리케이션의 큐와 대기 중인 애플리케이션에 대한 정보가 있습니다(보통 시간 또는 데이터가 어딘가에 표시됨).

2. 커널 레벨OS가 지금 당장 할 일이 없을 때는 'hlt' 명령을 실행합니다.이 명령어는 아무 것도 하지 않지만, 혼자서는 절대 끝나지 않습니다.물론 하드웨어 인터럽트는 정상적으로 처리됩니다.간단히 말하면 OS의 메인 루프는 다음과 같습니다(매우 멀리서 보면).

   allow_interrupts();반면 (참) {hlt;체크_도도_도입();}

   인터럽트 핸들러는 simpy를 사용하여 ToDo 큐에 항목을 추가합니다.실시간 클럭은 정기적으로 인터럽트를 생성하도록 프로그램되어 있습니다(고정 환율로).또, 다음의 프로세스가 기동하고 싶은 장래의 일정 시간까지 인터럽트를 생성하도록 되어 있습니다.

본질적으로, 네, "특별한 기즈모"가 있습니다 - 그리고 그것은 단지 잠자는 것 이상에 중요합니다.

일반적으로 x86에서는 Intel 8253 또는 8254 "Programmable Interval Timer" 입니다.초기 PC에서는 CPU에 의해 미리 설정된 시간 간격 후에 인터럽트('프로그래머블 인터럽트 컨트롤러'를 통해)를 인식하도록 프로그래밍할 수 있는 메인보드의 개별 칩이었습니다.현재는 메인보드 회로의 큰 덩어리의 극히 일부이지만, 이 기능은 아직 존재합니다.

오늘날 OS는 PIT를 정기적으로 웨이크업하도록 프로그래밍하고 있습니다(Linux의 최신 버전에서는 기본적으로 밀리초마다 1회).이것이 커널이 프리엠프티브 멀티태스킹을 구현하는 방법입니다.

멀티태스킹 운영체제에는 스케줄러라고 불리는 컴포넌트가 있습니다.이 컴포넌트는 스레드에 CPU 시간을 주는 역할을 합니다.콜 슬립은 OS가 당분간 이 스레드에 CPU 시간을 주지 않도록 합니다.

자세한 것은, http://en.wikipedia.org/wiki/Process_states 를 참조해 주세요.

Linux에 대해서는 아무것도 모르지만 Windows에서 무슨 일이 일어나는지 알려줄 수 있습니다.

sleep()을 지정하면 프로세스의 타임슬라이스가 즉시 종료되어 OS에 제어가 반환됩니다.그런 다음 OS는 타이머 커널 객체를 설정합니다.이 객체는 시간이 경과한 후에 시그널링됩니다.그러면 OS는 커널 객체가 시그널링될 때까지 이 프로세스에 더 이상 시간을 주지 않습니다.그래도 다른 프로세스가 우선순위가 높거나 동일한 경우 프로세스를 계속 진행하기 전에 잠시 대기할 수 있습니다.

특수한 CPU 머신 코드는 OS에 의해 프로세스 스위칭에 사용됩니다.이러한 함수는 사용자 모드 코드로 액세스할 수 없으므로 OS에 대한 API 호출로 엄격하게 액세스됩니다.

언급URL : https://stackoverflow.com/questions/175882/whats-the-algorithm-behind-sleep