OSTEP과 함께 가상화에 대해 알아보자 (1)

까막이의 몸부림·2026년 8월 22일

OS OSTEP 가상화 메모리 스케줄링 프로세스

OS

목록 보기

2/3

운영체제가 뭔데?

CPU, 메모리, 디스크 등 시스템의 자원을 호율적으로 관리하는 것이 운영체제의 역할이다.

한 마디로 자원 관리자.

가상화?

OS가 한정된 자원(CPU, 메모리 등)을 효율적으로 사용하기 위해, 그리고 안전하게 격리하여 사용하기 위해 가상화 하여 사용한다.

CPU 가상화

소규모의 CPU 집합을 여러 개의 CPU가 존재하는 것처럼 변환하여 동시에 많은 수의 프로그램을 실행시키는 것을 CPU 가상화라고 한다.

메모리 가상화

각 프로세스는 자신만의 가상 주로 공간을 갖고, 운영체제는 이 가상 주소 공간을 물리 메모리에 매핑한다.
실제 물리 메모리는 공유 자원이고, 운영체제에 의해 가상화 되어 관리된다.

그런데 문제가 있당??

병행성

프로그램이 한 번에 많은 일을 동시에 하려고 할 때 발생하는 것이 병행성 문제이다.
각 명령어는 원자적으로 실행되지 않기 때문에 운영체제, 또는 멀티스레드에서 병행성 문제가 생길 수 있다.

영속성

DRAM 같은 장치들은 데이터를 휘발성 있게 저장히기 때문에 데이터 손실을 막기 위해 영속적으로 저장 가능한 하드웨어/소프트웨어 저장장치가 필요하다.
또한, 쓰기 중의 다양한 문제에 대비하여 저널링, Copy-On-Write 등을 사용하고, 효율적인 디스크 작업을 위해 B-Tree 등 다양한 종류의 자료 구조를 활용한다.

OS를 어떻게 설계하는 것이 바람직한지?

운영체제는 위와 같이 CPU, 메모리, 디스크와 같은 물리 자원을 가상화 하고, 병행성과 같은 문제를 처리하고, 파일을 영속적으로 저장한다.
운영체제 설계에 있어 가장 중요한 목표는 오버헤드를 최소화 하는 것, 즉 성능이다.
또한, 프로그램 간의 보호를 위한 isolation이 필요하다.
계속해서 문제 없이 실행되어야 하는 신뢰성, 에너지-효율성, 보안, 이동성 등이 운영체제의 목표이다.

운영체제의 역사

단순 라이브러리 : 초창기에는 단순히 자주 사용되는 함수들을 모아놓은 라이브러리 형태.
보호 : 운영체제 코드는 장치를 제어하기 때문에 기존의 라이브러리 형태가 아닌 시스템 콜 형태로 구현.
시스템 콜 : 제어를 운영체제에 넘길 때 하드웨어 특권 수준을 상향 조정한다. 일반적인 user mode가 아니라 trap handler를 이용해 kernel mode로 격상시킨다. 따라서 운영체제는 시스템의 하드웨어를 자유롭게 접근하며 작업할 수 있게 된다.
멀티프로그래밍 : 한 번에 하나의 프로그램만 실행시키는 것이 아니라, 여러 작업을 메모리에 담아 빠르게 번갈아가며 실행하여 CPU 사용률을 향상. 한 번에 여러가지 작업을 하게 됨으로써 메모리 보호와 병행성 문제에 대한 관리가 중요해졌다.
현대 : 다양한 OS의 출범 및 PC 보급.

프로세스

프로세스라 함은... 그거지 그거

실행 중인 프로그램.

(프로세스 입장에서) 하드웨어 구성 요소

메모리 : 명령어 및 데이터가 저장. 프로세스가 접근 가능한 메모리 주소 공간 제공.
레지스터 : 명령어들이 직접 읽거나 갱신.
- 프로그램 카운터 : 현재 어느 명령어가 실행 중인지.
- 스택 포인터 : 함수의 변수 스택 관리.
- 프레임 포인터 : 리턴 주소를 저장하는 스택을 관리.

하나의 OS에 여러 개의 프로세스가 떠있을 텐데?

자원을 여러 프로세스가 돌아가며 사용하게 함으로써, 원하는 수 만큼 프로세스를 동시에 실행하는 시분할 기법.
CPU를 공유하기 때문에 각 프로세스의 성능이 낮아짐.
모든 현대 운영체제들이 채택 중.

프로세스 API

운영체제는 프로세스에 대한 기본 기능을 제공.

Create : 새로운 프로세스를 생성할 수 있는 방법 제공.
Destroy : 프로세스를 강제로 제거할 수 있는 방법 제공.
Wait : 프로세스의 대기 인터페이스 제공.
각종 제어 : 일시정지, 재시작 등의 기능 제공.
Status : 프로세스 상태 정보를 얻어내는 기능.

프로세스 생성

프로그램 실행 시, 운영체제는 디스크에 저장되어있는 프로그램 코드와 정적 데이터를 메모리, 프로세스의 주소 공간에 load한다.
stack 메모리 영역을 할당한다. 스택은 지역 변수, 함수 인자, 리턴 주소 등을 저장하기 위해 사용된다.
heap 메모리 영역을 할당한다. 힙은 동적으로 할당된 데이터(연결 리스트, 해시 테이블, 트리 등)를 저장하기 위해 사용된다.
입출력과 관계된 초기화 작업을 수행한다. Unix에서는 프로세스들이 STDIN, STDOUT, STDERR에 해당하는 파일 디스크립터를 갖는다.
프로그램 실행 준비를 마치면, 프로그램의 시작 지점에서부터 실행을 시작한다. 운영체제는 CPU를 새로 생성된 프로세스에게 넘기게 되고, 프로그램 실행이 시작된다.

프로세스 상태

간단하게 세 상태 중 하나로 존재한다.

Running : 실행 상태. 명령어를 실행 중이다.
Ready : 준비 상태. 실행할 준비가 되어있지만, 운영체제가 다른 프로세스를 실행하고 있는 등의 이유로 대기 중이다.
Blocked : 수행 중단 중. 프로세스가 다른 사건(디스크 입출력 완료 등) 완료까지 기다리는 상태이다.
그 외에도
initial : 프로세스가 생성되는 중인 초기 상태.
zombie / final : 프로세스는 종료되었지만, 메모리에 남아있는 상태. ~~보통 내가 회사 장비에서 실수했을때 많이 보임~~

자료 구조

프로세스 리스트

프로세스 상태를 파악하기 위해 준비 상태의 프로세스들에 대한 자료 구조.

레지스터 문맥

프로세스가 중단되었을 때, 해당 프로세스의 레지스터 값들을 저장.
이후에 복원하여 운영체제가 프로세스 실행을 재개할 수 있다. (문맥 교환)

Process API

Unix는 프로세스 생성을 위해 for()와 exec() 시스템 콜을 사용하며, wait() 시스템 콜을 사용하여 프로세스를 종료한다.

fork()

프로세스를 생성한다.
호출하면 부모(메인) 프로세스의 복사본 프로세스가 생성된다. 이를 자식 프로세스라고 한다.
자식 프로세스는 자신만의 주소 공간, 레지스터, PC 값, PID 값 등을 갖는다는 점에서 부모 프로세스와는 다른 프로세스이다.
fork()로부터 부모 프로세스는 생성된 자식 프로세스의 PID를 반환 받고, 자식 프로세스는 0을 반환받는다. 이러한 값의 차이로 인해 부모와 자식 프로세스가 서로 다른 코드를 실행하도록 만들 수 있다.

wait()

부모 프로세스가 자식 프로세스의 종료를 대기한다.
호출한 위치에서 자식 프로세스의 종료 시점까지 자신의 실행을 중지시킨다.

exec()

자기 자신이 아닌 다른 프로그램을 실행해야 할 때 사용한다.
실행 파일의 이름과 인자를 받아, 해당 실행 파일의 코드와 정적 데이터를 읽어 현재 실행 중인 프로세스의 코드 segment와 정적 데이터 부분을 덮어 씌운다.
힙과 스택, 주소 공간들은 새로운 프로그램의 실행을 위해 초기화 된다.
프로세스의 argv와 같은 인자를 전달하여 프로그램을 실행시킨다.
새로운 프로세스를 생성하는 것이 아니라, 현재 실행 중인 프로그램을 다른 실행 중인 프로그램으로 대체하는 것.

API는 왜 쓸까용?

쉘 구현을 위해 fork와 exec 분리가 필요

쉘은 명령어 실행을 위해 fork()로 새로운 자식 프로세스를 만든다.
그리고 exec()의 변형으로 프로그램을 실행시키고, wait()으로 명령어가 끝나기를 기다린다.
자식 프로세스가 종료되면 wait()으로부터 return하고 다음 명령어를 기다린다.
이 과정에서 fork()와 exec()가 분리됨으로써 쉘은 명령어 입출력을 재지정 처리하기 쉬워진다.
Unix의 pipe가 유사한 방식으로 구현되었다.

암튼 fork()와 exec() 조합이 프로세스 생성/조작에 있어 강력한 방법이다~

Direct Execution

기본적으로 CPU 가상화를 위해서는 물리적인 CPU를 여러 프로세스에서 잠깐씩 돌아가며 실행시켜 CPU 시간을 나누어 씀으로써 구현 가능하다.
즉, CPU 가상화를 구현하기 위한 핵심적인 저수준 기법.
그러나 이는 성능 저하, 제어 문제가 있다.

Limited Direct Execution

제한적 직접 실행

직접 실행 : 프로그램을 CPU 상에서 그냥 직접 실행시키는 것.
직접 실행 문제점 : 운영체제가 원치 않는 일을 하지 않는다는 것 보장 어려움. 프로세스 실행 시, 운영체제가 어떻게 프로그램 실행을 중단/다른 프로세스로 전환하는지.

issue 1 : 제한된 연산

직접 실행의 장점 : 빠르게 실행되는 것.

프로그램이 하드웨어 CPU에서만 실행도기 때문이다.
단, 그렇기 때문에 디스크 입출력 요청이나 CPU/메모리 등 자원에 대한 추가 할당 요청 수행 시의 문제가 있다.

만약 프로세스가 원하는대로 하도록 방치하면?

바람직하지 않음.

user/kernel mode 도입

user mode에서 실행되는 코드는 할 수 있는 일이 제한된다.
- 입출력 요청 X. (예외 발생 및 프로세스 제거)
- 자원 접근 권한 일부 제한.
kernel mode에서는 특수한 명령어를 포함해 모든 작업 수행 가능하다.
- 입출력 요청 및 자원 접근 가능.

사용자 프로세스가 디스크 입출력 실행을 해야 한다면?

시스템 콜 사용.
- 파일 시스템 접근, 프로세스 생성/제거, 다른 프로세스와의 통신, 메모리 할당 등 가능.
- 실행을 위해 trap 명령어 실행 :
- 하드웨어는 호출한 프로세스의 필요 레지스터들을 각 프로세스의 kernel stack에 저장.
- 커널 안으로 분기 및 특권 수준을 kernel mode로 상향.
- 완료 시, return-from-trap을 호출하여 다시 user mode로 하향, 호출한 사용자 프로그램으로 return. 이때, 레지스터 값들을 스택에서 pop하여 user mode 프로그램의 실행을 다시 시작.

trap table

커널이 임의의 코드를 실행하기 위해서는 접근 권한 검사가 끝난 뒤 분기 필요. 즉, trap이 코드 어디를 실행해야하는지 모른다.
그래서 커널은 부팅 시(kernel mode로 동작하기에 원하는대로 제어 가능)에 트랩 테이블을 만들고 이를 이용해 시스템을 통제.
명령어를 이용해 하드웨어에 trap handler 위치를 알려준다. 하드웨어는 해당 위치를 기억하고 있다가 시스템 콜과 같은 사건이 발생했을때 어느 코드로 분기하여 실행해야 할지 알 수 있다.

간단히 하자면

부팅 시, 커널은 트랩 테이블 초기화, CPU는 나중에 사용을 위해 테이블 위치 기억.
프로세스 실행 시, return-from-trap을 이용해 새로운 프로세스를 위한 노드를 할당하여 프로세스 리스트에 삽입, 메모리 할당 등 작업 후, CPU를 user mode로 전환하고 프로세스 실행.
프로세스가 시스템 콜 호출 시, 운영체제로 다시 trap.
운영체제가 시스템 콜 처리.
return-from-trap을 이용해 다시 제어를 프로세스에 넘김.
프로세스는 자기 할 일 하고 main()에서 return. 일반적으로 스텁 코드로 리턴하고, 스텁 코드가 프로그램 종료시킴.
종료 시, exit() 호출, 운영체제로 트랩.
운영체제가 정리 작업을 하고 종료.
(안 간단함)

issue 2: 프로세스 간 전환

간단히 프로세스 간 전환이 가능해야 한다.
CPU에서 프로세스가 실행 중이라는 것은, 운영체제가 실행 중이지 않다는 것이기 때문에 프로세스 간 전환이 안 된다.

협조 방식 : 시스템 콜 기다리기

옛날 방식.
너무 오랫동안 실행될 가능성이 있는 프로세스는 운영체제 구동을 위해 주기적으로 CPU를 포기할 것이라고 가정.

yield 시스템 콜 : 운영체제에게 제어를 넘겨 운영체제가 다른 프로세스를 실행할 수 있게 한다.

또 다른 경우로는... 프로그램이 비정상적인 행위를 하게 되면 운영체제로 제어가 넘어간다.(트랩)

비협조 방식 : 운영체제가 전권을 행사

프로세스의 협조가 없는 상황에서 CPU의 제어를 획득하는 방식이다.

타이머 인터럽트

수 밀리 초마다 인터럽트를 발생시킨다.
인터럽트가 발생하면 수행 중이던 프로세스는 중단되고, 운영체제의 인터럽트 핸들러가 실행된다.
운영체제는 하드웨어에게 타이머 인터럽트 발생 시 실행할 코드를 미리 알려줘야 한다.
인터럽트 발생 시, 하드웨어는 프로세스 상태를 저장해 나중에 return-from-trap으로 프로그램을 다시 시작할 수 있게 한다. (시스템 콜이 호출되었을 때와 마찬가지)

문맥의 저장과 복원

협조/비협조적인 경우 모두 운영체제가 제어권을 다시 획득했을때 프로세스를 계속 실행할건지, 다른 프로세스로 전환할 것인지가 스케줄러에 의해 결정된다.

문맥 교환

운영체제가 실행 중인 프로세스의 범용 레지스터 값, PC, 현재 커널 스택 포인터를 커널 스택에 저장.
실행될 프로세스의 범용 레지스터 값, PC,를 복원하고, 커널 스택을 해당 프로세스의 커널 스택으로 전환.
이를 통해 운영체제는 인터럽트된 프로세스 문맥에서 전환 코드를 호출, 실행될 프로세스 문맥으로 return 가능.
return-from-trap을 실행하면 실행 예정이던 프로세스가 실행 중이 된다.

총 두 번의 레지스터 저장/복원이 일어난다.
첫 번째 : 타이머 인터럽트 발생 시.

실행 중인 프로세스의 레지스터 값이 저장, 저장 장소는 해당 프로세스의 커널 스택.

두 번째 : 운영체제가 프로세스 전환 결정 시.

커널 레지스터는 운영체제에 의해 해당 프로세스의 프로세스 구조체에 저장. (실행 예정인 프로세스로부터 커널로 트랩 된 것처럼 만듦)

병행성 걱정

시스템 콜 처리 중에 타이머 인터럽트가 발생하면 병행성 문제가 생길 수 있다.

간단한 처리 방법 : 인터럽트 불능화

하나의 인터럽트 처리 중에는 다른 인터럽트는 CPU에 전달되지 않게 한다.
단, 이 방식은 너무 오래 불능화하면 인터럽트를 놓치는 묹제점.

lock 기법

내부 자료 구조에 동시에 접근하는 것을 방지하여, 커널 안에서 동시에 다수의 활동이 진행될 수 있게 허용.

CPU Scheduling

워크로드에 대한 가정

워크로드 : 일련의 프로세스들이 실행하는 상황.

이를 결정하여 정교하게 스케줄링 정책을 손질해야 한다.

스케줄링 평가 항목

스케줄링 평가 항목 : 워크로드에 대한 가정 외에도 스케줄링 정책의 비교를 위해 결정해야 함.

다양한 평가 기준이 존재.

반환 시간 : 작업이 완료된 시각에서 작업이 시스템에 도착한 시간을 뺀 시간. 성능 측면에서의 평가 기준.
공정성 : 예를들어 Jain's Fairness Index에 따라 측정.
반환 시간과 공정성은 스케줄링에서 서로 상충되는 목표.

선입선출

FIFO : 선입선출

단순하고 구현하기 쉽다.
convoy effect : 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상.

FCFS : 선도착선처리

최단 작업 우선

SJF : 최단 작업 우선.

FIFO의 convoy effect 문제 완화. 작업 실행 시간이 다른 경우.
이미 실행시간이 긴 작업이 먼저 도착하여 실행되고 있고, 이후에 짧은 작업들이 도착 시, SJF라도 긴 작업 먼저 이미 작업하고 그 후에 짧은 작업들이 작업 되는 문제.

최소 잔여시간 우선

STCF : 최단 잔여시간 우선

SJF와 같은 문제 발생 시에, 긴 작업을 중지하고 짧은 작업이 도착했을때 그 작업들을 먼저 실행하기로 할 수 있다.
SJF에 선점 기능 추가.
새로운 작업이 들어오면, 남아있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고, 가장 적은 잔여 실행 시간을 가진 작업을 스케줄한다.

반환 시간이 전부인가?

새로운 평가 기준 -> 응답 시간
응답 시간 : 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간.

라운드 로빈

Round-Robin : 하나의 작업을 일정 시간(타임 슬라이스/스케줄링 퀀텀) 동안 실행한 후, 실행 큐의 다음 작업으로 전환하는 방식.

응답 시간 문제를 해결.
- 타임 슬라이스의 길이가 짧을수록, 응답 시간 기준으로 성능이 좋아짐.
- 너무 짧으면 문맥 교환 비용이 전체 성능에 영향을 미침.
- 즉, 타임 슬라이스의 길이는 문맥 교환 비용을 상쇄할 수 있을 만큼 길어야 하지만, 응답 시간이 너무 길어지면 안 된다.
- 문맥 교환 비용 : 레지스터 저장/복원 작업, CPU 캐시, TLB, 분기 예측 등. 작업이 전환되면 갱신되어야 하므로 매우 큰 성능 비용 유발.
응답 시간이 평가 기준이면 RR이 좋고, 반환 시간이 측정 기준이면 최악.
작은 시간 단위로 모든 프로세스에게 CPU를 분배하는 공정한 정책.

입출력 연산의 고려

프로세스가 입출력 작업하는 동안 실행될 다른 작업을 스케줄 해야 한다.
입출력 완료 시에도 인터럽트 하여 어떤 작업을 올릴지 결정.
하나의 프로세스가 입출력 작업을 하는 동안, 다른 프로세스가 CPU를 사용하게 할 수 있다. (연산의 중첩)

But

각 작업의 실행 시간을 알고 있다면 스케줄링에 큰 도움이 되겠지만, 범용 운영체제에서 작업의 길이에 대해 알 수 있는 길은 없다.
아무것도... 없었다.

Multi-Level Feedback

멀티 레벨 피드백 큐 : CTSS에 사용된느 가장 유명한 스케줄링 기법.

해결하려고 하는 문제 :
- 짧은 작업을 먼저 실행시켜 반환 시간 최적화.
- 응답 시간 최적화.
작업 실행 시간 등과 같은 프로세스에 대한 정보가 없을 때 어떻게 적절히 스케줄링 할 수 있을까?

MLFQ : 기본 규칙

MLFQ 기본 알고리즘

여러 개의 큐로 구성되어 있으며, 각각 다른 우선순위가 배정된다. 실행 준비 된 프로세스는 이중 하나의 큐에 존재.
높은 우선순위 큐에 존재하는 작업이 선택 된다.
큐에 여러 작업이 있을 수 있는데, 이는 같은 우선순위를 가진다. 이 작업들 내에서는 Round-Robin 스케줄링 사용.
우선순위 정하는 방식 :
- 각 작업의 특성에 따라 동적으로 우선순위 부여.
- 입출력을 기다리며 반복적으로 CPU를 양보하는 경우, 우선순위 높게 유지.
- 긴 시간 동안 CPU를 집중적으로 사용하는 경우, 우선선위 낮춤.

시도 1: 우선순위의 변경

예 1: 한 개의 긴 실행 시간을 가진 작업

타임 슬라이스 1이 지나면 작업의 우선순위를 한 단계 낮춤.
타임 슬라이스 2가 지나면 가장 낮은 순위를 가지게 되고, 계속 머무름.

예 2: 짧은 작업과 함께

긴 작업이 낮은 우선순위 큐에서 계속 실행되고 있고, 짧은 작업이 들어왔을 때, 짧은 작업이 가장 낮은 우선순위 큐에 놓여져 빠르게 실행되게 된다.
이 짧은 작업 또한 타임 슬라이스 경과에 따라 우선순위가 낮아지지만, 기존의 긴 작업과 같은 우선순위에 놓이기 전에 종료된다.
스케줄러는 짧은/긴 작업인지는 알 수 없기 때문에 일단 짧은 작업이라 가정하여 높은 우선순위로 동작시키다가, 진짜 짧은 작업이면 빨리 동작이 끝나고 종료, 긴 작업이라면 천천히 우선순위가 낮아진다.

예 3: 입출력 작업에 대해서는?

프로세스가 타임 슬라이스 소진 전에 프로세서를 양도하면 같은 우선순위를 유지하게 된다.
자주 입출력을 수행하면 타임 슬라이스 소진 전에 CPU를 양도하게 된다. 그런 경우에 우선순위를 유지한다. (대화형 작업을 빨리 실행)

현재 MLFQ의 문제점

기아 상태 발생 가능 :
- 시스템에 너무 많은 대화형 작업이 존재하면 모든 CPU 자원을 소모.
- 긴 실행 시간 작업은 CPU 시간을 할당받지 못하고 굶어죽ㅜ
스케줄러를 자신에게 유리하게 동작하도록 프로그램 작성 가능 (어뷰징;;) :
- 예를 들면 타임 슬라이스가 끝나기 전에 아무 파일이나 입출력 하게 하여 CPU 양도.
- 그러면 같은 큐에 머무르며 더 높은 CPU 시간을 얻게 된다.
프로그램은 시간 흐름에 따라 특성이 변할 수 있음 :
- CPU 위주 작업이 대화형 작업으로 변할 수 있음.
- 다른 대화형 작업과 비슷하게 처리됨.

시도 2: 우선순위의 상향 조정

1, 3 문제 해결.

우선순위 상향 조정 : cpu 위주 작업을 조금이라도 진행하도록 보장하여 기아 문제를 방지해야 한다.

일정 시간이 지나면 시스템의 모든 작업을 최상위 큐로 이동.
- 프로세스는 굶비 않는다는 것을 보장.
- CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우, 우선순위 상향 받을 수 있음.
부두 상수 : 여기서의 일정 시간을 의미. 정확하게 결정하기 위해선 흑마술이 필요;
- 너무 크면 긴 실행 시간을 가진 작업은 굶음. 너무 작으면 대화형 작업이 적절하게 CPU 시간 활용 못 함.

시도 3: 더 나은 시간 측정

2 문제 해결.

주어진 단계에서 시간 할당량을 소진하면 우선순위가 낮아지게 한다.

각 단계에서 CPU 총 사용량을 측정하여 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순의 큐로 강등한다.
즉, 타임 슬라이스가 끝나기 직전에 입출력 명령을 내려 CPU 시간 독점하는 것을 막는다.

MLFQ 조정과 다른 쟁점들.

대부분의 MLFQ 기법은 큐 별로 타임 슬라이스 변경이 가능하다.

우선순위가 높은 큐는 짧은 타임 슬라이스를 주어, 대화형 작업으로 구성하고 빠르게 교제하게 할 수 있다.
낮은 우선순위는 CPU 중심의 오래 실행되는 작업을 포함하여 오래 실행되도록 한다.

Lottery Scheduling

비례 배분 스케줄러

반환 시간/응답 시간을 최적화하기보다 각 작업에 CPU의 일정 비율을 보장하는게 목적.
좋은 예 중 하나 : 추첨 스케줄링.

기본 개념 : 추첨권이 당신의 몫을 나타낸다

추첨권 : 프로세스가 받아야 할 자원의 몫.

각 프로세스가 일정 비율만큼 추첨권을 갖고 있고, 타임 슬라이스가 끝날 때마다 스케줄러가 추첨권을 선택하여 선택된 프로세스에 할당.
할당 결과가 원하는 비율(추첨권 비율)을 정확히 보장하지는 않지만, 작업이 진행될수록 원하는 비율에 가까워진다.

무작위 방법이 의외로 좋은 이유;

특이 사항 대응이 된다. ex) 최악의 경우가 발생하지 않는다.
관리해야 할 상태 정보가 적어 매우 가볍다.
매우 빠르다;;;;

추첨 기법

추첨권 화폐

사용자가 작업들에 개인의 화폐 가치로 추첨권을 자유롭게 할당.
시스템이 자동적으로 화폐 가치를 변환.

추첨권 양도

양도를 통해 일시적으로 다른 프로세스에게 추첨권을 넘겨줄 수 있다.
client 프로세스가 server에게 작업 요청 및 빠른 작업을 위해 추첨권을 양도할 수 있다.
요청 완수 시, server는 다시 client에게 추첨권을 반환.

추첨권 팽창

프로세스가 일시적으로 자신이 소유한 추첨권을 늘이거나 줄일 수 있다.
프로세스들이 서로 신뢰할 때 유용하며, 많은 CPU 시간이 필요로 하는 프로세스가 시스템에 이를 알리고 혼자 추첨권의 가치를 상향 조정한다.

구현

추첨 스케줄링의 구현

난수 발생기, 프로세스 집합 자료 구조, 추첨권의 개수만으로 단순하게 구현 가능하다.
난수로 추첨권 선택 후, 리스트를 순회하며 카운터 값을 이용해 당첨자를 찾는다.

불공정 지표

두 작업을 거의 동시에 종료시키고 싶을 때, 추첨 스케줄링의 무작위성 때문에 한 작업이 다른 작업보다 먼저 종료될 수 있다.
이때 이 차이를 불공정 지표라고 한다.
작업이 충분한 기간 동안 실행되어야 불공정이 낮아진다, 즉 원하는 결과에 가까워진다.

추첨권 배분 방식

추첨권 할당 방식에 따라 시스템 동작이 크게 달라지는데, 이는 기본적으로 사용자가 가장 잘 알고 있다고 가정한다.
즉, 사용자에게 추첨권을 나눠준 뒤, 사용자가 알아서 작업에 배분하도록.
이는 해결책이 아니다. 주어진 작업 집합에 대한 추첨권 할당 문제는 미해결 떡밥ㅡㅡ

왜 결정론적 방법을 사용하지 않는가?

보폭 스케줄링

무작위성을 이용하면 단순하지만 짧은 기간 실행될때 정확한 비율 보장이 어렵다.
결정론적 공정 배분 스케줄러인 보폭 스케줄링을 고안.
시스템의 각 작업은 보폭(stride)을 갖고 있음. 보폭은 임의의 큰 값을 추첨권 개수로 나눠 계산.
프로세스가 실행될 때마다 pass 값을 보폭만큼 증가시켜 얼마나 CPU를 사용하였는지를 추적.
보폭과 pass 값을 사용해 어느 프로세스를 실행시킬지 결정.
- 가장 작은 pass 값을 가진 프로세스를 선택.
각 스케줄링 주기마다 정확한 비율로 CPU 배분이 가능.

근데 왜 추첨 스케줄링 씀?

추첨은 상태 정보가 필요 없다.
보폭에서는 새로운 작업이 들어왔을때 pass가 0이 되어 CPU 독점하는 등의 문제 발생 가능.
추첨에서는 그러한 문제가 없고 CPU 사용 현황, pass 값 등 유지가 필요 없음.
추첨에서는 새 프로세스 쉽게 추가 가능.

Multi-CPU Scheduling

배경 : 멀티프로세서 구조

하드웨어 캐시

메인 메모리에서 자주 사용되는 데이터의 복사본을 저장하여 프로그램을 빠르게 실행.
캐시는 지역성에 기반.
- 시간 지역성 : 데이터가 한 번 접근되면 나중에 다시 접근되기 쉽다.
- 공간 지역성 : 접근된 데이터의 주변 데이터는 접근되기 쉽다.
이를 통해 무엇을 캐시에 저장할지 추측하여 동작.

캐시 일관성 문제

CPU1에서 작업하다가 캐시에서만 특정 데이터를 변경했는데, 이후 CPU2로 이동하면 당연히 CPU1의 캐시가 아닌 메모리에서 데이터를 가져오게 된다. 즉, 변경 결과 미반영.
하드웨어에 의한 기본적인 해결책 : 여러 프로세스들이 하나의 메모리에 갱신할때 항상 공유하게.
- 버스 스누핑 : 캐시는 자신-메모리 버스의 통신 상황을 계속 모니터링. 캐시 변경 발생 시, 자신의 캐시에서 삭제(무효화)하거나, 갱신.

동기화 이슈슈슈

CPU들이 동일한 데이터에 접근할 때, 올바른 연산 결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 동기화 기법들이 사용된다.
여러 CPU가 하나의 데이터에 접근하여 작업할 때, lock을 이용하여 올바르게 동작하게 해야 한다.

하지만...

성능 측면에서 문제가 있다.
CPU가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느려진다.

마지막 문제점: 캐시 친화성

캐시 친화성

CPU에서 프로세스가 실행될 때, 캐시와 TLB에 상태 정보를 올려놓게 된다.
다음 번 프로세스 실행 시, 동일한 CPU에서 실행되는 것이 당연히 좋다.
매번 다른 CPU에서 실행 시, 필요한 정보를 다시 탑재해야 한다.
멀티 프로세서 스케줄러는 스케줄링 결정 시, 가능한 한 프로세스를 동일한 CPU에서 실행하도록 해야 한다.

단일 큐 스케줄링

SQMS (단일 큐 멀티프로세스 스케줄링)

단순하게 모든 작업을 단일 큐에 넣는다.
확장성 결여 : lock은 SQMS 코드가 단일 큐에 접근할 때 올바른 결과가 나오게 하지만, CPU 개수가 증가할수록 성능을 크게 저하시킬 수 있다.
캐시 친화성 : 각 CPU는 공유 큐에서 다음 작업을 선택하기 때문에 각 작업은 CPU를 옮겨다니며 캐시 친화적이지 못하게 진행된다.

멀티 큐 스케줄링

MQMS (멀티 큐 멀티프로세스 스케줄링)

CPU마다 큐를 하나씩 둔다.
작업이 시스템에 들어오면 하나의 스케줄링 큐에 배치된다.
각각 독립적으로 스케줄 되기 때문에 단일 큐 방식의 정보의 공유 및 동기화 문제를 피한다.
SQMS보다 확장성이 좋다.
- CPU 개수가 증가할수록 큐의 개수도 증가하므로 lock과 cache 경합은 문제되지 않는다.
- 캐시 친화적이다.
그러나 워크로드의 불균형이 발생한다.
- 작업의 개수/양이 불균형할때 한 쪽 CPU가 작업을 끝마치고 유휴 상태가 될 수 있다.
작업을 다른 CPU로 이주시켜 개선할 수 있다.
이주의 필요 여부는 어떻게 결정?
- 작업 훔치기 : 작업의 개수가 낮은 큐가 다른 큐에 많은 작업이 있는지 확인. 워크로드 균형을 맞추기 위해 작업을 가져온다.
- but 큐를 너무 자주 검사하면 높은 오버헤드로 확장성 문제.

Linux 멀티프로세서 스케줄러

O(1) 스케줄러

멀티 큐
우선순위 기반. 시간에 따라 우선순위를 변경하여 가장 높은 작업을 선택.
상호작용을 가장 우선시.

CFS

멀티 큐
결정론적 비례배분 방식.
CFS는 Completely Fair Scheduler라는 뜻으로, CPU 시간을 최대한 공정하게 배분.

BFS

단일 큐
비례배분 방식.
EEVDF라는 방식에 기반을 둠.
BFS는 뜻이 브레인...뻑...

진짜요?

까막이의 몸부림

이전 포스트

OS 정리

다음 포스트