CS 스터디 5회차 - (1)

CS Study 5회차가 밝았다.

<4>-<6>까지.

먼저 <4> CPU 스케줄링 부터 알아보자.


📘 CPU 스케줄링
$\rarr$ 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것.

CPU 스케줄링은 컴퓨터 전체 성능과도 직결되는 아주 중요한 문제다.

프로세스들한테 CPU를 제대로 분배를 못하면 꼭 실행이 되어야 하는 프로세스가 실행이 안 되거나 당장 급하지 않은 프로세스들만 실행되는 무질서한 상태가 반복될 수 있기 때문이다.

가장 공정한 CPU 스케줄링은 무엇일까?

CPU를 사용하고 싶어하는 프로세스들이 차례대로 돌아가면서 사용하면 될까?

아니다.

프로세스마다 우선순위가 다르기 때문이다.

프로세스마다 빨리 처리해야 되는 프로세스가 있고, 천천히 처리해도 되는 프로세스가 있다.

그렇다면 어떤 프로세스가 우선순위가 높고 낮을까.

사용자가 직접 설정할 수도 있고 운영체제가 내부적으로 정해준 우선순위도 있다.

단적인 예시를 말하자면,

입출력작업이 많은 프로세스를 입출력 집중 프로세스(IO Bound Process)라고 한다.

CPU 작업이 많은 프로세스는 CPU 집중 프로세스(CPU Bound Process)라고 하는데,

입출력 집중 프로세스의 우선순위가 CPU 집중 프로세스의 우선순위보다 높다.

대부분의 프로세스는 CPU와 입출력장치를 모두 사용하면서 실행된다.

예를 들어, CPU를 사용했다가 보조기억장치를 사용하고 CPU를 사용하다가 모니터를 사용하기도 한다. 이런식으로 보통 입출력장치와 CPU를 번갈아 사용하게 된다.

그런데 프로세스마다 입출력장치를 유독 많이 사용하는 프로세스가 있고

CPU만 유독 많이 사용하는 프로세스도 있다.

입출력장치를 유독 많이 사용하는, 입출력 집중 프로세스 같은 경우에는 CPU 집중 프로세스에 비해서 대기 상대에 더 많이 머무르게 된다.

그렇기 때문에 입출력 집중 프로세스에 우선순위를 높여서 빨리 처리를 해 버리는게 CPU 집중 프로세스에 CPU를 좀 더 집중적으로 할당할 수 있게 되는 것.

쉽게 말해, CPU를 많이 안 쓰는 입출력 집중 프로세스부터 빨리 처리하고 난 뒤에 CPU 집중 프로세스에 CPU를 몰빵하겠다라는 것이다.

이렇게 상황에 맞게 프로세스가 요구하는 자원과 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해서 운영체제가 부여하는 것이
우선 순위이다.

우선순위는 프로세스의 PCB에 저장된다.

그래서 운영체제는 PCB를 보고 PCB 기반으로 어떤 프로세스가 CPU를 얼마나 많이 사용하게 될 건지를 결정하게 된다.

우선순위가 높은 프로세스는 더 빨리 더 자주 실행할 수 있다.

참고로, 프로세스 우선순위는 간단한 명령어라든지 프로그램으로서 확인이 가능하다.

일부 프로세스 같은 경우에는 우선순위를 사용자가 직접 설정을 해 줄 수도 있다.

프로그램 우선순위를 높여서 좀 더 빨리 실행되도록 하겠다 이런 식으로.

📘 스케줄링 Q

PCB 마다 우선순위가 적혀있지만 운영체제 입장에서 다음에 CPU를 사용할 프로세스를 선정하기 위해서 일일이 모든 PCB를 뒤져보는 것은 비효율적이다.

당장 동시에 실행되는 프로세스만 해도 많이 있을텐데 모든 PCB를 확인하는 것은 시간이 많이 걸리는 일 일것이다.

그래서 운영체제가 사용하는 것이 스케줄링 Q 다.

스케줄링 Q는 어떤 자원을 이용하고 싶어하는 프로세스들이 서는 줄이라고 이해하면 된다.

운영체제가 프로세스들한테 묻는다.

어떤 자원을 쓰고 싶냐?

그럼 CPU를 쓰고 싶은 프로세스, 메모리를 쓰고 싶은 프로세스 등 여러가지로 나뉠 것이다.

운영체제는 프로세스들에게 스케줄링 Q라고 하는 줄에 서라고 말한다.

그림으로 표현하자면 이렇게 볼 수 있다.

참고로, Q라고 하는 자료구조는 원래 자료구조 관점으로 봤을 때는 먼저 삽입된 데이터가 먼저 나가는 선입선출(FIFO)의 구조이지만

스케줄링 Q에서 말하는 Q는 반드시 선입선출일 필요는 없다는 것을 알아두자.

프로세스들마다 요구하는 자원이 다른 것처럼

스케줄링 Q에서 Q의 종류도 다양하다.

그 중 준비큐와 대기큐가 가장 대표적인 스케줄링 큐의 종류다.

📌 준비큐는 CPU를 이용하고자 하는 프로세스들이 서는 줄을 의미한다.

📌 대기큐는 입출력장치를 이용하고 싶은 프로세스들이 서는 줄을 의미한다.

지금 동시에 실행중인 프로세스가 여러개가 있다고 가정했을 때 CPU 자원은 한정되어 있기 때문에 이 프로세스들끼리 CPU를 번갈아가며 써야한다.

그래서 이 프로세스들은 준비 상태로 접어들어서 CPU의 할당을 기다리게 된다.

그리고 준비상태에 접어든 프로세스들 중에서 자기 차례가 되면 디스패치 돼서 CPU를 할당받고 실행을 하게 된다.

이게 실행상태다.

그리고 자기 실행 차례가 끝나면 타이머 인터럽트가 발생해 다시 준비 상태가 되고 준비큐에 삽입이 된다.

그러면 다음으로 우선순위가 높은 프로세스가 디스패치 돼서 실행상태에 접어든다.

그리고 또 자신의 실행 차례가 끝나면 타이머 인터럽트가 발생을 한다. 이때 입출력장치를 써야 한다면 이때부터는 CPU를 사용할 필요가 없기 때문에 대기 큐에 들어가서 대기 상태에 접어들게 된다.

대기 큐에서 입출력작업을 기다리다가 입출력 작업이 끝났다면,
입출력 완료 인터럽트가 실행되게 되고 다시 준비상태에 접어들게 된다.

운영체제는 이런 흐름으로 프로세스를 관리한다고 이해하면 된다.

다음으로 알아볼 것은 선점형 스케줄링, 비선점형 스케줄링이다.

선점형 스케줄링은 preemptive scheduling, 비선점형 스케줄링은 non-preemptive scheduling이라고 한다.

선점형, 비선점형은 운영체제 커널을 이해할 때 아주 중요한 개념이다.

어떤 프로세스가 자기 차례가 돼서 CPU를 할당 받아서 CPU를 이용하고 있다고 가정해보자.

이 프로세스는 현재 실행 상태에 있는 게 된다.

근데 어떤 프로세스가 나타나

저 지금 너무너무 급하게 처리해야 될 게 있는데 잠깐 CPU 좀 써도 될까요? 라고 부탁을 한다.

이런 상황은 충분히 일어날 수 있다. 언제든지 더 급한 프로세스는 생길 수 있으니까.

이럴 땐 두가지 선택을 할 수가 있는데

하나는 현재 CPU를 사용중인 프로세스로부터 CPU 자원을 빼앗아 다른 더 급한 프로세스한테 할당하는 방식이 있고

또 하나는 현재 CPU를 사용하고 있는 프로세스의 작업이 끝날 때까지 기다리라고 하는 것이다.

이것들을 선점형과 비선점형 스케줄링이라고 부른다.

선점이라는 것 자체가 남보다 앞서서 차지한다라는 뜻을 의미하고

다른 말로 바꾼다면 프로세스 하나가 CPU 자원을 독점해서 사용할 수 없다는 뜻과도 같다.

준비상태에 있다가 내 차례가 될 때까지 기다리고 내 차례가 되면 CPU를 사용하고 끝나면 다시 준비상태가 되는 것도 선점형 스케줄링이다.

선점형 스케줄링은 자원의 독점을 막을 수 있고, 프로세스들한테 자원을 골고루 분배할 수 있다는 장점이 있다.

단점이 있다면 그만큼 문맥 교환이 많이 발생하기 때문에 문맥교환에서의 오버헤드가 발생할 수 있다는 것이다.

비선점형의 장단점은 선점형 스케줄링의 장단점을 반대로 생각하면 된다.

자원을 독점적으로 사용할 수 있기 때문에, 모든 프로세스들이 자원을 골고루 이용하기는 힘들지만 문맥교환에서 발생하는 오버헤드는 작다.

이제 CPU 스케줄링 알고리즘에 대해 알아보자.


📘 CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘의 종류는 되게 다양하고 운영체제마다 서로 다른 스케줄링 알고리즘을 사용하고 있다.

책에서는 대표적인 7가지 알고리즘을 알아볼테지만 더 다양한 알고리즘들이 있다는 것도 알고는 있도록 하자.

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

📌 선입 선처리 스케줄링
$\rarr$ FCFS(First Come First Served)라고도 부른다.
단순히 준비큐에 삽입된 순서대로 처리해주는 스케줄링이다.

비선점 방식의 스케줄링이고, 말 그대로 먼저 요청한 프로세스의 순서대로 CPU를 사용한다.

직관적이고 공정해보이는 방식이지만 큰 부작용도 있는데,

프로세스들이 CPU를 할당 받기 위해 기다리는 시간이 매우 길어진다는 점이다.

이것을 호위효과(convoy effect)라고 한다.

📌 최단 작업 우선 스케줄링
$\rarr$ SJF(Shortest Job First)
준비큐에 삽입된 프로세스 중 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 먼저 실행하는 스케줄링 방식이다.
먼저 말했던 선입 선처리 스케줄링의 단점인 호위효과를 방지하는 방식이기도 하다.

이 최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 때도 있다.

이 내용은 조금 더 뒤에 설명하겠다.

📌 라운드 로빈 스케줄링
$\rarr$ RR(Round Robin) 스케줄링.
라운드 로빈 스케줄링은 말 그대로 쭉 돌아가면서 무엇을 한다는 것을 의미한다.

차례대로 뭘 한다라고 할 때 라운드 로빈이라는 용어를 사용한다.

라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스라고 하는 개념이 더해진 것이다.

타임 슬라이스가 뭐냐면,

각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 말한다.

정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.

정해진 시간을 모두 사용하였음에도 아직 완료되지 않았다면 다시 큐의 맨 뒤에 삽입하는 방식이다(문맥 교환)

예를 들어보자.

그림에서 보이는 것처럼 프로세스 A, B, C의 실행 시간이 각각 다음과 같고 타임 슬라이스는 4라고 가정을 해보자.

A는 4만큼 실행을 했지만 아직 끝나지 않았다.

그 뒤엔 문맥교환을 한다. B는 3만큼만 실행하면 되기 때문에 3만큼 실행해주고 이제 C로 넘어간다.

C 또한 타임 슬라이스보다 길기 때문에 타임 슬라이스만큼만 실행해주고 다시 문맥교환을 한다.

그리고 기다리고 있던 A를 다시 타임 슬라이스만큼 실행해준다. 이번에도 A는 끝나지 않았기 때문에 다시 대기한다.

그리고 문맥교환을 통해 C를 실행해준다. C의 실행이 이번엔 끝났기 때문에 기다리고 있던 A만 다시 처리해준다.

이게 라운드 로빈 방식이다.

라운드 로빈 스케줄링에서 타임 슬라이스의 크기는 매우 중요하다.

타임 슬라이스가 너무 커져버리면 앞서 설명했던 선입 선처리 스케줄링과 다를바가 없어져 호위효과가 일어날 수 있고

타임 슬라이스가 지나치게 작으면 문맥 교환에 발생하는 오버헤드 때문에 CPU의 부담이 커지게 되기 때문이다.

그래서 라운드 로빈 방식에서 꼭 고려해야 되는 것은 타임 슬라이스의 크기다.

📌 최소 잔여 시간 우선 스케줄링
$\rarr$ SRT(Shortest Remaining Time).
앞에서 설명했던 최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합친 스케줄링 방식이다.

정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택한다.

📌 우선순위 스케줄링
$\rarr$ 프로세스들한테 우선순위를 부여하고 가장 우선순위가 높은 프로세스부터 실행하는 스케줄링 알고리즘이다.

우선순위가 같은 프로세스들이 있다고 한다면 먼저 준비큐에 들어가있던 순서대로, 선입선처리로 스케줄링 된다.

최단작업 우선 스케줄링이나 최소 잔여시간 스케줄링 같은 경우에도 넓은 의미에서는 모두 우선순위 스케줄링이라고 할 수 있다.

우선순위 스케줄링은 개념은 이해하기 쉬운데, 부작용이 있다.

우선순위 스케줄링 방식이 갖고 있는 근원적인 부작용인데,

기아현상(Starvation)이라고 하는데, 아사현상이라고도 부른다.

우선순위가 높은 프로세스부터 무조건 먼저 실행하겠다는 스케줄링 방식이기 때문에 우선순위가 낮은 프로세스는 준비큐에 먼저 삽입되었음에도 불구하고 계속해서 실행이 연기될 수 있다.

우선순위가 낮은 프로세스는 끝끝내 실행이 안 될수도 있다.

이렇게 되면 결국 굶어 죽는다. 그래서 기아현상, 아사현상이라고 부른다.

물론 이 기아현상을 해결하는 방법도 있다.

대표적인 해결방법에 에이징(Aging)이 있다.

에이징은 오랫동안 대기한 프로세스의 우선순위를 마치 나이를 먹는 것처럼 점차 증가시켜서 우선순위를 높여주는 방법이다.

이렇게 에이징 기법을 사용하면 우선순위가 낮았던 프로세스도 점점 우선순위가 높아져 결국 언젠가는 실행이 된다.

📌 다단계 큐 스케줄링
$\rarr$ 멀티레벨 큐(Multilevel queue) 스케줄링이라고도 부른다.
이 멀티레벨 큐 스케줄링은 우선순위 스케줄링의 발전된 형태다.

우선순위별로 여러개의 준비큐를 사용하는 방식이다.

우선순위 0번, 1번, 2번 이런식으로 우선순위별로 큐를 여러개 만들어서 우선순위별로 프로세스를 큐에다가 넣어주는 거다.

우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비었다면 그 다음 높은 큐에 있는 프로세스들을 처리한다.

이렇게 큐를 여러개 두면 프로세스 유형별로 우선순위를 구분하는 것이 쉬워진다는 장점이 있다.

어떤 큐에는 우선순위가 비교적 높아야 되는 입출력 집중 프로세스가 삽입될 수 있고, 또 어떤 큐에는 우선순위가 비교적 낮아도 상관 없는 CPU 집중 프로세스가 삽입 될 수도 있다.

하지만 단점도 존재한다.

이 다단계 큐 스케줄링에서는 기본적으로 프로세스가 큐 간에 이동이 불가능하다.
우선순위가 낮은 프로세스는 계속해서 우선순위가 낮은 큐에 머물러야 하기 때문에 다시 기아현상이 발생할 수도 있다.

이 단점을 해결하기 위한 마지막 스케줄링을 알아보자.

📌 다단계 피드백 큐 스케줄링
$\rarr$ 다단계 피드백 큐(multilevel feedback queue) 스케줄링은 다단계 큐 스케줄링과 비슷하게 동작하지만, 앞서 다단계 큐 스케줄링의 단점을 보완해 프로세스들이 큐 사이를 이동할 수 있다는 점에서 차이가 있다.

일단 다단계 피드백 큐 스케줄링에서 새롭게 준비 상태가 된 프로세스가 있으면 먼저 우선순위가 높은 큐에다 삽입을 한다.

그리고 일정 시간, 타임 슬라이스만큼 CPU를 할당 받아서 사용을 하게 한다.

실행을 한다.

이 때 실행이 끝났다면, 더 이상 스케줄링 할 게 없지만

만약 실행이 덜 끝나 CPU가 더 필요하다면 우선순위가 다음으로 높은 곳에다 삽입을 해준다.

그럼 이제 그 우선순위가 다음으로 높은 곳에서 실행을 하고 실행이 끝났다면 완전히 끝나는 거고, 여전히 더 필요하다면 다음 우선순위가 높은 곳으로 삽입을 해 실행을 한다.

CPU를 많이 사용해야 하는 프로세스일 수록 우선순위가 자연스럽게 낮아지도록 만드는 것이다.

CPU 집중 프로세스는 CPU를 많이 사용해야 하기 때문에 처음엔 높은 우선순위 큐에 삽입되더라도 어차피 CPU를 많이 사용해야 하기 때문에 점차 낮은 우선순위 큐로 이동될 것이고,

CPU를 비교적 적게 사용하는 입출력 집중 프로세스 같은 경우엔 높은 우선순위 큐에서 실행이 끝나버릴 것이다.

마지막으로 정리하자면,

다단계 피드백 큐 스케줄링은 어떤 프로세스의 CPU 시간이 길면 우선순위가 자연스럽게 낮아질 수 있도록 만드는 방식인 동시에 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 에이징 기법을 적용해 우선순위를 높일 수도 있는 방식이다.

이 스케줄링 방식이 CPU 스케줄링 방식의 가장 일반적인 형태로 알려져 있다.

이번 챕터는 여기까지 하도록 하겠다.