WHY
면접 질문 3에서 프로세스의 상태와 CPU 스케줄러의 역할을 살펴보았다.
이번 질문은 CPU 스케줄링의 알고리즘을 물어보면서 선점형, 비선점형, 우선순위의 관점에서
스케줄링 기법을 이해하는지 물어보는 것이다.
어떤 기준으로 CPU 스케줄링을 선택해야 하는지
사용자와 시스템 관점에서 어떤 기준을 선호하게 되는지
선점형 방식과 비선점형 방식의 기존 스케줄링의 단점과 보완점
우선순위 스케줄링 방식을 통해 프로세스의 운영방식을 이해했는지를 살펴볼 수 있는 좋은 질문이라고 생각한다.
따로 해당 질문을 받은 경험이 없다.
스케줄링 알고리즘의 평가 기준들
CPU 사용률(Utilization)
전체 시스템 시간 중에서 CPU가 작업을 처리하는 시간의 비율이다.
유휴 시간이 적을수록 CPU 사용률이 높다.
CPU 사용률을 극대화하려는 많은 노력이 있지만 현재는 90% 정도가 최대 사용률이라고 한다.
처리량(Throughput)
CPU가 단위 시간당 작업을 마친 프로세스의 수이다.
CPU 사용률이 높고 프로세스들에 적정한 시간을 공평하게 제공했다면 처리량이 높다.
정확한 계산은 어려운 편이라고 한다.
응답 시간(Response Time)
대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간이다.
짧을수록 좋다.
대기 시간(Waiting Time)
프로세스가 준비(ready) 큐에서 대기하는 시간들의 총합이다.
대기시간이 짧을수록 좋다.
반환 시간(Turnaround Time) [ 대기 시간 + 실행 시간]
프로세스의 시작부터 끝날 때까지 걸리는 시간이다.
CPU스케줄링의 평가 기준은 위와 같다.
절대적인 기준으로 스케줄링을 택하는 것은 현명하지 못하다.
사용자 측면에서는 입출력이 중요하기에 사용자 측면에서는
대기시간, 응답 시간, 반환 시간을 줄여줄 수 있는 스케줄링을 활용해야 한다.
이를 OS에서는 "전면 프로세스"로 둔다. 상호작용을 위한 프로세스인 것이다.
시스템 측면에서는 시스템의 자원을 최대한 활용할 수 있는 처리량 + CPU 사용률이 높게 해주는
스케줄링을 활용해야 한다.
이를 OS에서는 "후면 프로세스"로 어떠한 상호작용 없이 순수 로직을 처리하는 프로세스를 의미한다.
사용자 프로세스는 전면프로세스로 처리되고 시스템 프로세스는 후면 프로세스로 동작하는 것이 적합한 것이다.
이를 위해서 OS는 전면 프로세스용 스케줄링과 후면 프로세스용 스케줄링을 관리하면 좋을 것이다.
선점형과 비선점형 스케줄링을 살펴보고 이 둘을 혼합해서 활용하는 우선순위 스케줄링을 살펴보자.
비선점형(Non-preemptive) 스케줄링
프로세스가 자발적으로 대기(IO바운드)로 넘어가거나 종료될 때까지 CPU를 점유하는 방식이다.
대체적으로 스케줄러의 호출 빈도가 낮다. 그래서 문맥 교환의 오버헤드가 낮다.
일괄 처리 시스템에 적합하다.
FCFS(First Come First Served)
단순한 알고리즘으로 단순 Queue로 준비 큐를 둔다.
먼저 자원을 요청한 프로세스들이 Queue에 들어가고 스케줄러는 먼저 들어온 프로세스를 선택해서
CPU 자원을 할당한다.
모든 프로세스의 우선순위는 동일하며 "먼저 들어온 순서"로 프로세스들이 처리된다.
입출력 작업에 대해서 따로 대기로 보내지 않는 경우 이 시간은 그대로 CPU 유휴시간으로 이어진다.
[ CPU 사용률 저하 ]
콘보이 효과라고 하여 CPU 사용시간이 긴 프로세스에 의해 다른 프로세스의 대기 시간이 늘어나는 단점이 있다.
[ 처리량 측면에서 좋지 않다.]
SJF(Shortest Job First) : 최단 프로세스 우선 스케줄링.
최단시간으로 처리될 수 있는 작업(프로세스)에 우선순위를 준다.
시간이 오래 걸리는 작업이 있고 간단한 작업이 있다면 간단한 작업부터 처리하는 것이다.
FCFS가 가지는 콘보이 효과에 대해서 보완한 것이다.
하지만 운영체제가 프로세스의 종료 시간을 예측하기란 어려운 일이다. [ 불확실성이 높고, 구현이 어렵다. ]
사용자가 언제든지 프로그램을 실행시킬 수 있는 현대적인 컴퓨팅 환경에서는 더더욱 계산하기가 어렵다.
긴 작업 시간이 남은 프로세스를 배척하여 공평성에 위배되는 측면도 있다.
이에 대해서 에이징(Aging)기법으로 프로세스의 양보성에 대한 상한선을 부여할 수 있으나
기준에 대한 고려가 필요하다는 문제가 있다.
기아 현상 + 프로세스 종료 예측시간에 대한 어려움으로 사용성이 낮다.
HRN (Highest Response Ratie Next) 스케줄링
SJF의 기아 현상을 보완한 우선순위 알고리즘을 적용한다.
최고 응답률 우선 스케줄링이라고 불리며 서비스를 받기 위해 대기한 시간에 우선순위 가중치를 부여해주는 것이다.
우선순위 = (대기 시간 + CPU 사용시간) / (CPU 사용시간)인 것이다.
대기 시간에 대한 우선순위 가중치로 기아현상을 완화시켜준다.
하지만 공평성(CPU 사용시간)에 대한 문제는 남게 된다.
선점형(Non-preemptive) 스케줄링
운영체제가 더 높은 우선순위에 강제적으로 CPU 자원을 할당할 수 있는 스케줄링이다.
시분할(타임 슬라이스로 프로세스에 CPU 자원 시간 부여) 시스템을 고려하여 만든 알고리즘이다.
[ 전체적인 프로세스에 CPU 자원을 할당해줌으로써 응답성을 높이고 대기 시간을 줄여주는 것이다. ]
사용자 친화적인 전면 프로세스에 주로 사용된다.
Round Robin 라운드 로빈 스케줄링
프로세스는 할당받은 시간(타임슬라이스) 동안 작업을 진행하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 간다.
선점형 알고리즘의 가장 단순한 방식으로 우선순위가 없다.
프로세스 교체에 대한 "오버헤드"가 타임슬라이스와 관계되어 있다.
타임슬라이스 크기를 잘 설정해줘야 오버헤드가 줄어든다.
Shortest Remaining Time : SJF에 라운드 로빈을 적용.
기본 라운드 로빈은 준비 큐에서 프로세스를 뽑을 때 우선순위를 고려하지 않았다.
SRT는 "남아있는 작업 시간"으로 우선순위를 부여한다.
남아있는 작업 시간이 적은 프로세스를 준비 큐에서 선택하는 것이다.
운영체제로 하여금 프로세스의 남은 작업 시간을 예측하기가 어려우며 아사 현상이 발생할 수 있다는 단점이 존재한다.
우선순위 스케줄링
하나의 스케줄링으로만 프로세스를 관리하는 것은 상당히 비효율적이다.
사용자에게는 전면 프로세스를 시스템에게는 후면 프로세스를 집중할 수 있도록 스케줄링을 배치하면 좋을 것이다.
사용자에게는 시분할 스케줄링(선점형)으로 응답성을 높이는 방식을 제공해주고
시스템에는 프로세스를 빠르게 처리하면서 문맥 교환으로 인한 오버헤드를 줄여주는 스케줄링 방식을 선택하도록
하는 것이다.
다단계 큐 스케줄링(multi-level queue)
우선순위에 따라서 준비 큐를 여러 개 사용하는 방식이다.
위의 그림과 같이 그룹별 프로세스에 대해서 "우선순위" 가중치를 다르게 부여하는 것이다.
큐 사이에 우선순위를 부여할 수 있고, 각 큐로 하여금 적합한 스케줄링 알고리즘(선점 or 비선점)을 가지는 것이다.
EX. 하나의 큐는 전면 프로세스(사용자 친화적) 용으로 두고 하나의 큐는 후면 프로세스(시스템 친화적)로 두어서 프로세스의 우선순위에 대한 스케줄링 다양성을 부여하는 것이다.
다단계 큐 스케줄링의 경우 프로세스가 큐에 영구적으로 할당되어 다른 큐로 이동하지 못한다는 아쉬운 점이 있다..
[ 해당 프로세스는 큐의 우선순위에 고정되는 것 ].
이러한 점이 유연성을 떨어뜨린다.
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
다단계 큐 스케줄링의 유연성을 제공하는 방식이다.
프로세스는 우선순위가 다른 큐로 이동이 가능하다. [ 큐 사이의 프로세스 이동이 가능! ]
IO Burst의 경우 우선순위가 높은 큐로 이동시키고, CPU Burst의 경우 낮은 우선순위 큐로 이동시키면서
프로세스 처리의 유연성을 높이는 것이다.
Aging 등의 방식을 적용해서 대기 시간이 긴 프로세스도 높은 우선순위 큐에 올려서 기아 상태를 방지하는 장점을 얻을 수 있다.
하지만 큐의 수, 큐가 가지는 알고리즘, 우선순위 조절, 프로세스의 이동 등 관리의 복잡함이 증가된다.
마무리
1~4의 면접 질문을 통해
프로세스, 스레드,
멀티 스레딩, 멀티 프로세싱,
CPU 스케줄러, 프로세스 상태,
CPU 스케줄링
을 살펴보았다.
운영체제의 관점에서 CPU라는 자원을 어떻게 효율적으로 활용하는지를 살펴보았다!
아직 프로세스와 관련된 문제가 모두 해결된 것은 아니다.
시분할 시스템으로 인해서 프로세스가 교체되고, 프로세스 간의 통신에서 공유되는 데이터로 인해서 생기는 문제를
살펴보지 않았다.
다음 질문에서는 데이터 동기화 이슈의 배경과 데이터 동기화를 위한 기법들을 살펴보겠다.
문제가 되는 정보가 있다면 말씀해주시면 바로 반영하겠습니다!
참고자료
책
- 쉽게 배우는 운영체제
블로그
'면접질문[CS] > 알고리즘 & OS' 카테고리의 다른 글
| 임계구역을 보호하기 위한 기법 3가지[뮤텍스, 세마포어, 모니터] [ 운영체제(OS) 면접질문 6] (1) | 2021.12.24 |
|---|---|
| 동기화, 경쟁 조건(Race Condition), 임계 구역(Critical Section) [ 운영체제(OS) 면접질문 5] (0) | 2021.12.23 |
| CPU 스케줄링 & 선점형, 비선점형 스케줄링 [ 운영체제(OS) 면접 질문 3] (0) | 2021.12.21 |
| 멀티프로세싱(multiprocessing)과 멀티스레딩(multithreading)의 차이점 [ 운영체제(OS) 면접질문 2] (1) | 2021.12.16 |
| 프로세스(Process)와 스레드(Thread)의 차이점. [ 운영체제(OS) 면접 질문 1] (0) | 2021.12.15 |
