CPU 스케줄링

프로세스 큐와 큐잉 다이어그램

• 프로세스 큐 : 운영체제는 프로세스들의 목록을 필요에 따라 적절한 방식으로 관리해야함.

이들은 전통적으로 큐 (queue)의 이름으로 관리하는데, 큐는 First-Come First-Served (FCFS)의 의미를 가지지만 여기서는 단순히 프로세스들의 목록 또는 집합으로 간주.

• 레디 큐 : 레디 큐는 프로세스들 중에서 Ready 상태의 프로세스들의 목록. 언제든 실행할 수 있는 상태로서 CPU에 의해 차례를 기다리고 있는 상태. picoKernel의 레디 큐에는 Ready 상태의 스레드 목록인 threadReadyList가 이에 해당.
• 디바이스 큐 : 각 입출력 장치마다 하나씩 존재. 특정 입출력 장치에서 원하는 작업이 실행될 때까지 대기하는 프로세스들의 목록
• 세마포/메일박스 : 디바이스 큐는 특정 입출력 장치만을 위한 것이 아닌, 세마포나 메일박스와 같이 운영체제 내부의 논리적 객체들에 대해서도 적용됨.
• 큐잉 다이어그램(queueing diagram) : 프로세스들이 여러 큐를 거쳐가는 과정.

 

뮤텍스(Mutex)? 상호 배제(mutual exclusion)

한 스레드, 프로세스에 의해 소유될 수 있는 key를 기반으로 한 상호배제기법

세마포(Semaphore)? 현재 공유자원에 접근할 수 있는 스레드, 프로세스 수를 나타내는 값을 두어 상호배제를 달성하는 기법

뮤텍스(Mutex)와 세마포어(Semaphore)의 차이 (tistory.com)

뮤텍스(Mutex)와 세마포어(Semaphore)의 차이

 

 

• picoKernel 스레드들의 큐잉 다이어그램

picoKernel에는 뮤텍스와 세마포마다 대기 큐가 있고 별도의 입출력 장치를 위한 대기 큐는 사용하지 않음.

입출력 장치마다 뮤텍스를 하나씩 사용하고 프로세스가 특정 입출력 장치를 사용하는 것은 해당 뮤텍스를 확보함으로써 사용 권한을 획득한 것으로 처리함.

picoKernel의 스케줄링 정책으로는, 레디 큐에는 우선 순위가 높은 것이 먼저 선택되도록 하고 뮤텍스와 세마포의 대기 큐는 FCFS 규칙에 따라 대기중인 스레드 중 하나가 선택되도록 함.

 

단기 스케줄러와 디스패처

• 단기 스케줄러 (short-term scheduler)

CPU 스케줄러라고도 하며, 레디 큐에서 CPU에 의해 실행될 프로세스를 선택함.

단기 스케줄러는 일반적으로는 작게는 5ms, 길게는 100ms 정도의 주기로 한 번씩 호출되어 실행됨.

• 디스패처(dispatcher) : 스케줄러에 의해 선택된 프로세스를 실제 실행되는 상태로 전환시키는 주체

현대 운영체제에서는 일반적으로 스케줄러와 디스패처는 커널 내에서 별도 구분 형태로 존재하지 않고, 커널을 구성하는 함수들에 개념적으로만 존재함.

 

스와핑과 중기 스케줄러

가상메모리는 큰 저장 공간인 디스크를 메모리의 일부인 것처럼 활용하는 것.

메모리가 부족하면 프로세스들 중에서 일부를 디스크의 특정 영역에 일시적으로 현재 메모리 내용을 저자해 두었다가 여분이 생기면 다시 메모리에 그대로 적재하여 실행을 계속할 수 있게 함.

이러한 과정을 **스와핑 (swapping)**이라 함. 스와핑을 수행하는 주체를 스와퍼라고 함.

 

스왑 : 메모리에 있던 프로세스를 하나 선택하여 스왑 디바이스(디스크 등)에 기록하고, 스왑 디바이스에 기록되어 있던 프로세스를 메모리에 적재하는 과정. 서로 맞바꾸는 의미가 있음.

 

메모리에 적재된 프로세스 내용을 그대로 스왑핑 영역에 기록하는 작업을 스왑 아웃 (swap out)이라 하고, 그 반대 작업을 스왑인(swap in)이라고 함.

 

 

• 디맨드 페이징 (demand paging) : 스와핑을 프로세스 단위로 처리하지 않고, 프로세스가 차지하고 있는 메모리 영역을 일정한 크기의 페이지 단위로 나누어 처리함.

즉, 스와핑 대상을 페이지라는 작은 단위로 선택함. 이런 작업을 하는 주체를 페이저(pager)라고 함.

 

 

 

• 중기 스케쥴러 (medium-term scheduler) : 스와퍼나 페이저를 지칭.

스와핑 작업은 디스크 입출력 작업을 수반하므로 너무 빈번하게 일어나면 디스크 입출력에 많은 시간을 낭비함. 일반적으로 수백 밀리 초 이상의 주기로 실행됨.

 

현대의 운영체제는 대부분 스와핑보다는 페이징을 사용함.

페이징을 사용하면서도 필요에 따라 일부 프로세스를 완전히 스왑아웃 시키는 경우가 있는데, 프로세스 개수가 너무 많아서 프로세스 당 할당되는 메모리의 양이 지나치게 적고, 페이지 스왑인/아웃이 지나치게 빈번히 발생하면 일부 프로세스를 일정 시간 동안 완전히 스왑아웃시키게 된다.

 

잡 큐와 장기 스케줄러

잡큐와 장기 스케줄러는 요즘 운영체제에서는 적용하지 않는 기능.

잡이라는 용어는 초창기 운영체제인 멀티프로그래밍 시스템에서 사용하던 용아.

잡 : 사용자로부터 실행 요청은 받았지만 아직 프로세스로 생성되지 못하고 대기 중인 것을 잡이라고 지칭.

 

 

선점형 스케줄링과 선점형 커널

스케줄링 작업이 필요한 시점

 

구분	발생 원인	현재 프로세스	비선점형 스케줄링	선점형 스케줄링
1. 프로세스 종료	시스템콜 함수 호출	계속 실행 불가	ㅇ	ㅇ
2. waiting 상태로 전환	시스템콜 함수 호출	계속 실행 불가	ㅇ	ㅇ
3. 실행 순서 양보	시스템콜 함수 호출	자발적으로 레디큐로 이동	ㅇ	ㅇ
4. 할당시간 만료	타이머 인터럽트	강제로 레디큐로 이동	x	ㅇ
5.외부 장치에 의해 Ready 프로세스 추가	디바이스 인터럽트	강제로 레디큐로 이동	x	ㅇ
6. 시스템 콜에 의해 Ready 프로세스 추가	시스템콜 함수 호출	강제로 레디큐로 이동	x	o
7. 프로세스 생성	시스템콜 함수 호출	강제로 레디큐로 이동	x	o

2. waiting 상태로 전환

실행중인 프로세스가 waiting 상태로 전환될 때

(입출력 작업을 요청하여 이것이 완료될 때까지 기다리거나, 일정한 시간이 흐른 뒤 깨어나기 위해 sleep을 요청하거나, 사용하기 위해 요청한 뮤텍스가 이미 다른 프로세스에 의해 사용중이거나, 메시지를 수신하려고 하는데 아직 수신할 메시지가 도착되지 않은 경우 등.)

 

 

4. 실행중인 프로세스가 할당된 시간이 만료되어 ready 상태로 전환

(할당 시간이 만료되는 시점은 할당된 시간만큼으로 설정된 하드웨어 타이머의 타임아웃 인터럽트가 발생하는 시점)

 

5. waiting 상태의 프로세스가 외부 장치에 의해 발생되는 이벤트에 의해 대기 조건이 충족되어 ready 상태로 전환될 때

(외부 장치의 이벤트 예로는, 프로세스가 요청한 디스크 읽기 작업이 완료된 시점에 발생하는 인터럽트, 프로세스가 일정한 시간동안 sleep 상태에 있다가 깨어나도록 하기 위해 설정한 타이머의 타임아웃 인터럽트 등)

 

6. waiting 상태의 프로세스가 현재 실행 중인 프로세스가 발생시킨 이벤트에 의해 대기 조건이 충족되어 ready 상태로 전환될 때

 

⠀ ⠀⠀⠀⡤ ⠴⠒ ⠶ ⢄
⠀⠀⠀⠀⡞⠀⠀    ⠀⠀ ⠙⢤⡀
⠀⠀⠀⠀⢸⢀⣀⠀⠀⢀⣀⡀⠀ ⢱
⠀⠀⠀⠀⢸⢹⣸⡃⠀⠹⣼⠇⠀ ⡆⠀
⠀⢀⡠⠔⠋⠀⠀⠀⠀⠀⠀⠀⠀ ⢸⠀⠀
⠣⡤⠔⠒⠊⢉⣉⣉⣉⡉⠁    ⢸
⠀⠀⠑⠒⠊⡏⠁⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀   ⠀⠀⣸⠀⠀⠀⠀⠀⠀⠀⢸
⠀⠀⠀⢰⢱⠆⣀⣀⣀⣰⡡⢒⡸⠃

(현재 실행중인 프로세스에 의한 이벤트의 예로는, waiting 상태의 프로세스가 기다리고 있는 뮤텍스를 해제해 주거나, 메시지 수신을 위해 waiting 상태에 있는 프로세스에게 메시지를 전송하는 경우 등)

 

7. 새로운 프로세스가 생성되어 ready 상태로 전환될 때

(실행중인 프로세스가 프로세스의 생성을 요청한 경우)

 

• 자발적인 요청 vs 강제적으로 실행되는 스케줄링

1,2,3은 실행 중인 프로세스가 스스로의 필요에 의해 시스템 콜 함수를 호출하고 더 이상 실행할 수 없어서 다른 프로세스로의 문맥 교환이 필요한 경우.

but, 4,5,6,7은 실행중인 프로세스는 계속 실행할 수 있는 상태인데도 불구하고 강제로 스케줄링 작업이 실행되는 경우.

운영체제에 따라서 선점형 스케줄링을 지원하는 것이 있고 비선점형 스케줄링만 지원하는 것이 있음

 

• 선점형 스케줄링 (preemptive scheduling) : 위의 7가지 중 어떠한 경우라도 적절한 스케줄링 작업을 실행하고 필요에 따라 다른 프로세스로 문맥을 교환하도록 함.
• 비선점형 스케줄링 (non-preemptive scheduling) : 실행 중인 프로세스가 자발적으로 요청한 경우에 한해서 스케줄링을 실행하고, 나머지 경우에는 스케줄링 작업 없이 현재 실행하던 프로세스가 실행을 계속 하도록 함. 실행 중인 프로세스가 계속 실행할 필요가 있으면 문맥교환 x 

Ready 시점 : 0 : p1, 1 : p2, 2 : p3

우선순위 : p1<p2<p3

 

	0	1	2	3	4	5	6
선점형	p1	p2	p3	→	p2	p1
비선점형	p1→		p3→		p2→

 

시간 0에서 p1이 실행하다가 시간 1에서 p2가 레디큐에 등록된다.

선점형 스케줄링에서는 우선순위가 p1보다 높은 p2가 먼저 실행하지만,

비선점형 스케줄링에서는 이미 실행중인 p1이 완료된 시점에 우선순위가 가장 높은 p3이 선택되어 다음으로 실행됨

.

선점형 스케줄링을 구현하는 것이 바람직하나 구현 방법이 비선점형 스케줄링에 비해 복잡함.

시스템 콜 함수의 처리 과정(1,2,3,6,7)에서 스케줄링에 의해 적절히 다른 프로세스로 문맥 교환 구현은 비교적 간단하나, 하드웨어 인터럽트 처리 과정 (4,5) 에서의 문맥 교환은 신중하게 처리해야함.

 

 

• 크리티컬 섹션 문제

만약 실행 중인 프로세스가 프로세스들 간에 공유하는 데이터를 변경하는 중에 인터럽트가 발생.

인터럽트 처리 과정에서 스케줄링에 의해 다른 프로세스로 변경되었다고 가정할 때, 만약 이 프로세스가 다시 문제의 그 데이터를 변경하고자 한다면 데이터 자체의 일관성이 유지되지 못하는 문제.

위에 반해 시스템 콜 함수의 처리 과정에서만 스케줄링이 이루어진다면 공유 데이터를 변경하는 작업이 진행되는 중에는 시스템 콜 함수를 호출하지 않으면 크리티컬 섹션 문제가 발생하지 않음.

picokernel에는 4,5 경우에 해당하는 하드웨어 인터럽트를 처리하는 부분이 업고, 나머지 시스템 콜 함수를 처리하는 경우들에 대해서는 필요에 따라 스케줄링을 실행함. 간편하지

 

 

• 비선점형 스케줄링

유닉스를 포함한 대부분의 운영체제에서는 선점형 스케줄링을 지원함.

커널모드로 전환되는 당시 유저모드에서 실행 중이었다면 스케줄링을 통해 즉시! 다른 프로세스로 전환될 수 있음. 프로세스 간에는 독립 메모리 공간을 사용하므로 크리티컬 섹션 문제가 발생하지 않음. 그러나 커널 모드에서 실행 중일 때에는 중간에 다른 프로세스로 전환하게 되면 데이터 일관성 문제가 발생 가능.

시스템 콜 함수라는게 애초에 커널에서 관장.

 

마지막 그림처럼 P1이 요청했던 시스템 콜 처리를 마저 실행하고 P3을 실행하면 시점을 놓치는 상황이라면,

P3은 레디큐에 등록된 시점에 즉시 스케줄링에 의해 선택되어 실행되어야 함.

우선 순위가 높은 프로세스가 레디 큐에 등록되면 비록 커널부분을 실행중이라 하더라도 즉시 그 프로세스가 실행되도록 해주는 방식의 커널을 선점형 커널(preemptive kernel)이라고 함.

 

이왕이면 선점형 커널이 굳.

그러나 !!!!!

복잡한 문제가 포함됨.

p1의 시스템 콜 처리 내용 중에 커널의 중~~요한 데이터를 변경하는 작업이 포함되어 있었고 실행 중이었슴.. 근데 p3이 레디큐에 추가됐다고 바로 p3으로 변경.

만약 p3이 p1과 동일한 시스템 콜을 호출했다면 변경중이던 커널의 데이터는 중첩되어 데이터 일관성의 문제가 생길 수 있음.

따라서 최근에 운영체제는 커널이 중첩되어 실행될 수 있다는 가정 하에 개발됨.

 

 

 

스케줄링 평가 기준

• cpu 활용률 (utilization)

cpu의 활용률을 높이는 것 중요

• 턴어라운드 시간 (turnaround time)

특정 프로세스에 대해 실행을 요청한 시점과 완전히 종료된 시점까지의 시간을 의미.

(실제 실행시간 외 레디큐에서 대기시간, 디바이스 큐에서 입출력을 위한 대기시간도 포함)

• 응답시간 (response time)

실행이 요청된 시점부터 입출력이 시작된 시점까지의 시간

• 대기시간 (waiting time)

특정 프로세스에 대해 레디 큐에서의 대기 시간만을 의미

• 처리율(throughput)

단위 시간당 완료한 프로세스들의 개수

 

 

스케줄링 정책

• FCFS (First-Come First-Served) 스케줄링

프로세스들을 레디 큐에 들어온 순서대로 실행. FIFO와 비슷한 개념이쥬

구현하기가 간단함. 레디 큐는 리스트로 구현하고, ready 프로세스를 추가할 때는 리스트의 끝에, 스케줄링은 리스트의 첫 프로세스를 선택하면 됨.

• SJF(shortest job first) 스케줄링

레디 큐의 프로세스들 중에서 실행할 계산 작업 단위가 가장 짧은 프로세스를 먼저 실행.

평균 대기시간을 평가 기준으로 잡는다면 SJF가 최적의 스케줄링.

SJF를 구현하기 위해서는 레디 큐를 짧은 실행시간의 프로세스가 먼저 선택되는 우선순위 큐로 구현하면 됨. SJF는 SPN(Shortest Process Next)로 부르기도 함.

 

• SRTF (Shortest Remaining Time First) 스케줄링

SJF를 약간 변형한 것. 레디 큐에 새로운 프로세스가 추가되는 시점에, 지금 실행되던 프로세스의 잔여 실행 시간과 레디큐의 프로세스들의 남은 실행 시간을 비교하여 가장 작은 값을 선택.

SJF가 비선점형 스케줄링인데 반해 SRTF는 선점형 스케줄링.

 

• 라운드로빈 (round-robin, time-sliced) 스케줄링

레디 큐의 프로세스들을 일정한 할당 시간 단위 (quantum)로 돌아가면서 실행.

선택된 프로세스는 실행을 위해 할당된 시간을 가지며, 이 시간이 경과하면 다시 레디큐로 돌아가 삽입되고 다음 프로세스가 선택되어 실행됨.

FCFS와 마찬가지로 리스트 구현. 할당시간이 만료되면 실행되는 프로세스를 강제로 리스트의 끝에 추가, 리스트의 첫 프로세스를 실행 프로세스로 선택하면 됨.

이 방식은 짧은 계산 작업 단위에 대해 응답 시간을 단축하는 효과가 있으므로 대화형 시스템에 적합.

 

• 실시간 스케줄링

실시간 프로세스는 주로 특수 목적 컴퓨터 시스템에서 적용됨. 실행결과가 제대로 출력되는 것 뿐만 아니라 실행되는 시점도 지정된 시간 내에 실행이 완료되어야 하는 조건을 만족해야함.

이러한 방식에서는 실행 마감 시한이 이른 것을 먼저 실행하는 방식 (EDF : earlist Deadline First)이나

실행 주기가 짧은 것을 먼저 실행하는 방식 (RM : Rate Monotonic)등을 사용함.

• 우선순위 (priority) 스케줄링

각 프로세스에 적절한 우선순위가 부여되고 스케줄러는 우선 순위가 가장 높은 프로세스를 먼저 선택하여 실행함.