이하 설명은 CPU의 실행 단위인 프로세스와 스레드를 묶어서 "프로세스"라는 용어를 사용하겠다.
1. 멀티 프로세스 / 스레드의 동시성
컴퓨터는 동시에 여러 일을 진행한다. 크롬 탭으로 유튜브 노래를 틀면서 이렇게 글을 작성할 수도 있고, 동시에 카카오톡 pc 앱을 켜서 카카오톡도 이용하고, 그러면서도 연결된 아이폰의 문자 알림을 계속해서 받을 수 있는 것이다.
그렇다고 해서 실제로 컴퓨터가 동시에 2개 이상의 명령어를 수행하는 것은 아니다. 여러 개의 프로세스를 시분할로 번갈아가면서 수행하고 있을 뿐이다. 타자를 치는 것, 타자를 친 결과가 티스토리 에디터에 전달되는 것, 에디터에 전달된 내용이 서버에 올라가는 것, 그 내용이 다시 노트북의 화면에 나타나는 것은 전부 다른 프로세스가 담당한다. 정확히 따지자면 물론 다르겠지만 일련의 과저 키보드IO, 크롬, 커널의 네트워크 관련 프로세스, 화면IO 프로세스 등이 각 과정에 참여할 것이다. 각 프로세스의 명령어들은 CPU가 아주 짧은 시간동안 실행할 수 있는 작은 단위로 나눠져 번갈아가며 실행되고, 이 과정이 매우 빠르게 동작하면 동시에 여러 프로세스가 동작하는 것처럼 보인다. 이것이 멀티 프로세스/스레드의 진실이고 이러한 특성을 동시성이라고 부른다.
2. CPU 스케줄링?
그렇기 때문에 스케줄링은 필요하다. CPU가 실행해야 할 프로세스가 여러개가 있을 때, 어떤 프로세스를 먼저 시작할 것인지, 그 프로세스를 얼마나 오랫동안 실행할 것인지 결정하는 과정이 필요하기 때문이다.
프로세스 스케줄링을 위해 CPU는 PCB(Process Control Block)를 이용한다. PCB에는 운영체제가 프로세스를 관리하기 위한 기본적인 정보들이 들어있는데, CPU 스케줄링을 위한 정보 역시 여기에 포함된다. 대표적으로 프로세스의 우선순위, 현재 프로세스의 상태 등이 있다.
# 프로세스 상태
프로세스의 상태 다이어그램이다.
새로 생성된 프로세스 A(new)는 레디 큐에 들어간다(ready). 레디 큐에는 CPU에게 실행되기를 기다리는 프로세스들이 줄서있는 공간이다. 큐의 앞에 존재하는 프로세스들이 처리되고 A의 차례가 되면, 프로세스 A의 명령어들이 CPU에 의해 실행된다(running). 프로세스 진행을 위해 IO 작업이 필요하면 IO block이 일어나 IO 작업 대기 큐에 들어가게 되는데(waiting), IO 작업이 끝나면 다시 레디 큐로 돌아가서 CPU 처리를 기다린다. running중인 프로세스 A에게 할당된 시간이 끝나 interrupt가 발생하면 다시 레디 큐에 돌아가 자신의 차례가 되길 기다린다(ready). 프로세스의 전 과정이 끝나면 종료된다.(terminated)
레디 큐는 CPU의 작업을 대기하는 프로세스들이, 각 IO 장치의 대기 큐에는 IO장치의 입출력을 기다리는 프로세스들이 존재한다. OS에서 스케줄링의 대상이 되는 프로세스들은 이렇게 대부분 큐(queue)의 형태로 관리된다.
# 프로세스 우선순위
앞서 프로세스들은 보통 큐의 형태로 관리된다고 했지만, 모든 프로세스 스케줄링이 FIFO의 방식으로 동작하는 것은 아니다. 프로세스마다 우선순위가 다르다. 다시말해 우선순위가 높은 어떤 프로세스는 이미 레디 큐에 존재하는 프로세스보다 늦게 큐에 들어왔음에도 먼저 CPU에게 할당될 수 있다.
보통 IO bound 프로세스가 그렇다. IO bound 프로세스란 프로세스 작업의 대부분이 IO와 관련된 프로세스인데, 이 프로세스들은 실행시 CPU를 차지하는 시간이 길지 않기 때문에 CPU bound 프로세스보다 먼저 휙휙 처리해버리고 IO 작업에 집중할 수 있도록 하는 것이 낫기 때문이다. 만약 CPU bound 프로세스가 우선순위가 높다면 IO bound 프로세스는 별로 음료수 하나 사러 마트 왔는데 계산대 앞사람이 50만원어치 장을 보고 있다면 화가 나겠지 응응.
3. 스케줄링 알고리즘
본격적으로 대표적인 CPU 스케줄링 알고리즘 몇 가지를 알아보자. 프로세스 우선순위를 설명할 때와 일맥상통하는 얘기로, CPU를 사용하는 시간이 적은 프로세스를 먼저 처리하는 것이 좋다. 그래야 전체 프로세스의 대기시간을 줄일 수 있기 때문이다. 정말 이런지는.. 스케줄링 알고리즘 각각의 예시를 들면서 설명하겠다. 처리에 각각 4초, 2초, 1초가 걸리는 프로세스 A,B,C가 있다고 가정하겠다.
3-1) FCFS : First Come First Serve
비선점형 FCFS는 레디 큐에 삽입된 프로세스 순서대로 처리하는 (설명하기 민망할 정도로) 단순한 알고리즘이다. A -> B -> C 순서대로 프로세스가 레디큐에 삽입되었다고 했을 때 실행 순서 다이어그램은 다음과 같다.
평균 대기시간은 B가 4초, C가 6초로 약 3.3초이다. 보면 알겠지만 C는 빡쳐있는 상태일 것이다. 내 실행시간은 1초밖에 안되는데 6초를 기다려야한다니 환장할 노릇이다.
3-2) SJF : Shortest Job First
그런 C의 마음을 달래주기 위해 고안한 알고리즘이다. 무식한 선착순이 아닌, 가장 짧은 실행시간을 가진 프로세스가 가장 먼저 실행된다.
이렇게 되면 프로세스들의 평균 대기시간이 획기적으로 줄어든다. 게다가 preemtive 방식일 경우, 이 알고리즘은 이론상 평균 대기시간의 측면에서 가장 완벽한 CPU 스케줄링 방식이 된다.
그러나 프로세스가 종료까지 얼마나 많은 시간이 걸릴진 아무도 예상하지 못한다. 전반적인 경향성을 살펴서 비슷하게 만들어볼 수는 있으나, SJF를 완전히 구현하는 것은 이론상의 얘기일 뿐이다.
3-3) Round Robin
FCFS에 타임 슬라이스의 개념이 추가된 스케줄링 알고리즘이다. 레디 큐의 삽입 순서대로 프로세스를 실행하되, 정해진 타임 슬라이스만큼의 시간이 지나면 해당 프로세스의 실행을 멈추고 프로세스를 레디 큐의 맨 뒤로 보내는 것이다. 다음은 같은 상황에서 타임슬라이스가 1일 때 라운드로빈의 동작 다이어그램이다.
타임 슬라이스에 대해 정해진 규약은 없다. 다만 너무 길면 FCFS와 다를게 없어지고, 너무 짧으면 Context Switching의 오버헤드가 커지게 된다. 현대 스케줄링 방식은 기본적으로 이같은 RR 방식을 베이스로 깔고간다.
더해서 타임 슬라이스가 끝난 후 프로세스가 완료되기까지 잔여시간을 계산에서 그 잔여시간이 가장 짧은 프로세스를 레디큐의 앞에 할당하는 SRT(Shortest Remaining Time)도 있는데, 역시 SJF과 마찬가지로 이론상의 스케줄링이다.
3-4) 다단계 피드백 큐 스케줄링
가장 먼저 우선순위 스케줄링이 존재한다. 간단하게 우선순위가 높은 프로세스를 먼저 실행하는 것이다. 그치만 모든 스케줄링을 이렇게 적용했을 경우, 우선순위가 낮은 프로세스는 영원히 실행되지 못하는 starvation 문제가 발생한다. 이를 방지하기 위해 프로세스에 aging을 적용한다. 일정 시간이 지나도 CPU에 할당되지 않은 프로세스의 우선순위를 한 단계씩 높이는 방법이다.
이를 발전시킨게 다단계 큐 스케줄링이다. 여러 개의 레디 큐를 두는 방식이다. IO bound 프로세스는 상위 우선순위 큐에, CPU bound 프로세스는 하위 우선순위 큐에 둔다. 같은 우선순위를 가진 프로세스들은 FCFS 방식으로 동작한다. 각 큐마다 타임 슬라이스나 스케줄링 알고리즘을 다르게 적용시킬 수 있다.
이를 한단계 더! 발전시킨게 다단계 피드백 큐 스케줄링이다. 기본적 내용은 다단계 큐 스케줄링과 같으나, 여기선 프로세스들이 서로다른 우선순위의 레디 큐를 이동할 수 있다는 특징이 있다. 일단 그림을 보자
기본적으로 우선순위가 높은 프로세스가 높은 우선순위 레디큐에 존재한다. CPU는 높은 우선순위 레디큐의 프로세스부터 실행한다. 상위 레디 큐가 비워져야 그 다음 레디 큐의 프로세스들을 처리할 수 있다.
우선순위는 높지만 CPU타임을 너무 많이 쓰는 프로세스에게 많은 CPU 타임을 할당하는 것은 비효율적이다. 주어진 타임 슬라이스동안 완료되지 못한 프로세스는 하위 레디큐로 쫓아낸다. 반대로, 하위 레디큐에 있으면서 계속 CPU에게 할당받지 못하는 프로세스는 starvation상태에 있다. 얼른 실행시켜줘야 하므로 상위 레디큐로 이동시켜준다.
구현이 복잡하고 생각해야 할 것도 많은 스케줄링 방식이지만, 현대 OS에서 가장 일반적으로 사용하는 CPU 스케줄링 알고리즘이다
REFERENCE
혼자 공부하는 컴퓨터구조 + 운영체제 11장
이하 설명은 CPU의 실행 단위인 프로세스와 스레드를 묶어서 "프로세스"라는 용어를 사용하겠다.
1. 멀티 프로세스 / 스레드의 동시성
컴퓨터는 동시에 여러 일을 진행한다. 크롬 탭으로 유튜브 노래를 틀면서 이렇게 글을 작성할 수도 있고, 동시에 카카오톡 pc 앱을 켜서 카카오톡도 이용하고, 그러면서도 연결된 아이폰의 문자 알림을 계속해서 받을 수 있는 것이다.
그렇다고 해서 실제로 컴퓨터가 동시에 2개 이상의 명령어를 수행하는 것은 아니다. 여러 개의 프로세스를 시분할로 번갈아가면서 수행하고 있을 뿐이다. 타자를 치는 것, 타자를 친 결과가 티스토리 에디터에 전달되는 것, 에디터에 전달된 내용이 서버에 올라가는 것, 그 내용이 다시 노트북의 화면에 나타나는 것은 전부 다른 프로세스가 담당한다. 정확히 따지자면 물론 다르겠지만 일련의 과저 키보드IO, 크롬, 커널의 네트워크 관련 프로세스, 화면IO 프로세스 등이 각 과정에 참여할 것이다. 각 프로세스의 명령어들은 CPU가 아주 짧은 시간동안 실행할 수 있는 작은 단위로 나눠져 번갈아가며 실행되고, 이 과정이 매우 빠르게 동작하면 동시에 여러 프로세스가 동작하는 것처럼 보인다. 이것이 멀티 프로세스/스레드의 진실이고 이러한 특성을 동시성이라고 부른다.
2. CPU 스케줄링?
그렇기 때문에 스케줄링은 필요하다. CPU가 실행해야 할 프로세스가 여러개가 있을 때, 어떤 프로세스를 먼저 시작할 것인지, 그 프로세스를 얼마나 오랫동안 실행할 것인지 결정하는 과정이 필요하기 때문이다.
프로세스 스케줄링을 위해 CPU는 PCB(Process Control Block)를 이용한다. PCB에는 운영체제가 프로세스를 관리하기 위한 기본적인 정보들이 들어있는데, CPU 스케줄링을 위한 정보 역시 여기에 포함된다. 대표적으로 프로세스의 우선순위, 현재 프로세스의 상태 등이 있다.
# 프로세스 상태
프로세스의 상태 다이어그램이다.
새로 생성된 프로세스 A(new)는 레디 큐에 들어간다(ready). 레디 큐에는 CPU에게 실행되기를 기다리는 프로세스들이 줄서있는 공간이다. 큐의 앞에 존재하는 프로세스들이 처리되고 A의 차례가 되면, 프로세스 A의 명령어들이 CPU에 의해 실행된다(running). 프로세스 진행을 위해 IO 작업이 필요하면 IO block이 일어나 IO 작업 대기 큐에 들어가게 되는데(waiting), IO 작업이 끝나면 다시 레디 큐로 돌아가서 CPU 처리를 기다린다. running중인 프로세스 A에게 할당된 시간이 끝나 interrupt가 발생하면 다시 레디 큐에 돌아가 자신의 차례가 되길 기다린다(ready). 프로세스의 전 과정이 끝나면 종료된다.(terminated)
레디 큐는 CPU의 작업을 대기하는 프로세스들이, 각 IO 장치의 대기 큐에는 IO장치의 입출력을 기다리는 프로세스들이 존재한다. OS에서 스케줄링의 대상이 되는 프로세스들은 이렇게 대부분 큐(queue)의 형태로 관리된다.
# 프로세스 우선순위
앞서 프로세스들은 보통 큐의 형태로 관리된다고 했지만, 모든 프로세스 스케줄링이 FIFO의 방식으로 동작하는 것은 아니다. 프로세스마다 우선순위가 다르다. 다시말해 우선순위가 높은 어떤 프로세스는 이미 레디 큐에 존재하는 프로세스보다 늦게 큐에 들어왔음에도 먼저 CPU에게 할당될 수 있다.
보통 IO bound 프로세스가 그렇다. IO bound 프로세스란 프로세스 작업의 대부분이 IO와 관련된 프로세스인데, 이 프로세스들은 실행시 CPU를 차지하는 시간이 길지 않기 때문에 CPU bound 프로세스보다 먼저 휙휙 처리해버리고 IO 작업에 집중할 수 있도록 하는 것이 낫기 때문이다. 만약 CPU bound 프로세스가 우선순위가 높다면 IO bound 프로세스는 별로 음료수 하나 사러 마트 왔는데 계산대 앞사람이 50만원어치 장을 보고 있다면 화가 나겠지 응응.
3. 스케줄링 알고리즘
본격적으로 대표적인 CPU 스케줄링 알고리즘 몇 가지를 알아보자. 프로세스 우선순위를 설명할 때와 일맥상통하는 얘기로, CPU를 사용하는 시간이 적은 프로세스를 먼저 처리하는 것이 좋다. 그래야 전체 프로세스의 대기시간을 줄일 수 있기 때문이다. 정말 이런지는.. 스케줄링 알고리즘 각각의 예시를 들면서 설명하겠다. 처리에 각각 4초, 2초, 1초가 걸리는 프로세스 A,B,C가 있다고 가정하겠다.
3-1) FCFS : First Come First Serve
비선점형 FCFS는 레디 큐에 삽입된 프로세스 순서대로 처리하는 (설명하기 민망할 정도로) 단순한 알고리즘이다. A -> B -> C 순서대로 프로세스가 레디큐에 삽입되었다고 했을 때 실행 순서 다이어그램은 다음과 같다.
평균 대기시간은 B가 4초, C가 6초로 약 3.3초이다. 보면 알겠지만 C는 빡쳐있는 상태일 것이다. 내 실행시간은 1초밖에 안되는데 6초를 기다려야한다니 환장할 노릇이다.
3-2) SJF : Shortest Job First
그런 C의 마음을 달래주기 위해 고안한 알고리즘이다. 무식한 선착순이 아닌, 가장 짧은 실행시간을 가진 프로세스가 가장 먼저 실행된다.
이렇게 되면 프로세스들의 평균 대기시간이 획기적으로 줄어든다. 게다가 preemtive 방식일 경우, 이 알고리즘은 이론상 평균 대기시간의 측면에서 가장 완벽한 CPU 스케줄링 방식이 된다.
그러나 프로세스가 종료까지 얼마나 많은 시간이 걸릴진 아무도 예상하지 못한다. 전반적인 경향성을 살펴서 비슷하게 만들어볼 수는 있으나, SJF를 완전히 구현하는 것은 이론상의 얘기일 뿐이다.
3-3) Round Robin
FCFS에 타임 슬라이스의 개념이 추가된 스케줄링 알고리즘이다. 레디 큐의 삽입 순서대로 프로세스를 실행하되, 정해진 타임 슬라이스만큼의 시간이 지나면 해당 프로세스의 실행을 멈추고 프로세스를 레디 큐의 맨 뒤로 보내는 것이다. 다음은 같은 상황에서 타임슬라이스가 1일 때 라운드로빈의 동작 다이어그램이다.
타임 슬라이스에 대해 정해진 규약은 없다. 다만 너무 길면 FCFS와 다를게 없어지고, 너무 짧으면 Context Switching의 오버헤드가 커지게 된다. 현대 스케줄링 방식은 기본적으로 이같은 RR 방식을 베이스로 깔고간다.
더해서 타임 슬라이스가 끝난 후 프로세스가 완료되기까지 잔여시간을 계산에서 그 잔여시간이 가장 짧은 프로세스를 레디큐의 앞에 할당하는 SRT(Shortest Remaining Time)도 있는데, 역시 SJF과 마찬가지로 이론상의 스케줄링이다.
3-4) 다단계 피드백 큐 스케줄링
가장 먼저 우선순위 스케줄링이 존재한다. 간단하게 우선순위가 높은 프로세스를 먼저 실행하는 것이다. 그치만 모든 스케줄링을 이렇게 적용했을 경우, 우선순위가 낮은 프로세스는 영원히 실행되지 못하는 starvation 문제가 발생한다. 이를 방지하기 위해 프로세스에 aging을 적용한다. 일정 시간이 지나도 CPU에 할당되지 않은 프로세스의 우선순위를 한 단계씩 높이는 방법이다.
이를 발전시킨게 다단계 큐 스케줄링이다. 여러 개의 레디 큐를 두는 방식이다. IO bound 프로세스는 상위 우선순위 큐에, CPU bound 프로세스는 하위 우선순위 큐에 둔다. 같은 우선순위를 가진 프로세스들은 FCFS 방식으로 동작한다. 각 큐마다 타임 슬라이스나 스케줄링 알고리즘을 다르게 적용시킬 수 있다.
이를 한단계 더! 발전시킨게 다단계 피드백 큐 스케줄링이다. 기본적 내용은 다단계 큐 스케줄링과 같으나, 여기선 프로세스들이 서로다른 우선순위의 레디 큐를 이동할 수 있다는 특징이 있다. 일단 그림을 보자
기본적으로 우선순위가 높은 프로세스가 높은 우선순위 레디큐에 존재한다. CPU는 높은 우선순위 레디큐의 프로세스부터 실행한다. 상위 레디 큐가 비워져야 그 다음 레디 큐의 프로세스들을 처리할 수 있다.
우선순위는 높지만 CPU타임을 너무 많이 쓰는 프로세스에게 많은 CPU 타임을 할당하는 것은 비효율적이다. 주어진 타임 슬라이스동안 완료되지 못한 프로세스는 하위 레디큐로 쫓아낸다. 반대로, 하위 레디큐에 있으면서 계속 CPU에게 할당받지 못하는 프로세스는 starvation상태에 있다. 얼른 실행시켜줘야 하므로 상위 레디큐로 이동시켜준다.
구현이 복잡하고 생각해야 할 것도 많은 스케줄링 방식이지만, 현대 OS에서 가장 일반적으로 사용하는 CPU 스케줄링 알고리즘이다
REFERENCE
혼자 공부하는 컴퓨터구조 + 운영체제 11장
