운영체제 (11) - CPU scheduling (2)
CPU scheduling (2)
SJF (Shortest Job First, 최단작업 우선)
알고리즘의 이름에서도 알 수 있듯이, 현재 기준으로 처리되는데 제일 짧은 시간을 갖는 프로세스를 처리하는 기법입니다. 이는 탐욕적이자, 비선점적인 기법입니다. 이는 제일 짧은 프로세스를 빠르게 처리하기에, 프로세스의 평군 waiting time을 감소시킵니다.
이론상 좋아보이지만, 문제가 있습니다. 바로 프로세스의 CPU 사용 시간을 알기 힘들다는 것입니다. 사용자에게 CPU 사용 시간을 물어보나요? ~~ 개발자에게 자유를 주었다가 null point error.. 등의 exception(software interrupt네요!)이 일어나서 시스템이 터지는 경우가 많습니다! ~~ 아무튼, 사용자 입력으로는 정확하고 이상한 값을 얻기 쉽습니다. 그렇다면, 적절한 회귀식을 세워 추정해야 하고, 이를 통해 scheduling합니다. 하지만, 너무 많은 상황 변수가 존재하기에, 시간이 길다고 측정된 매우 중요한 프로세스는 잘못하면 영영 실행되지 못할 수도 있습니다. 이는 시스템 에러가 나기 아주 좋은 상황입니다.
SRTF (Shortest Remaining Time First, 최소 잔여시간 우선)
SJF 방식은 비선점형 스케줄링이라고 했습니다. 이를 선점형으로 바꿔봅시다. 즉 운영체제가 적절하게 context-switching을 해주는데, 이러한 스케줄링 알고리즘을 SRTF (Shortest Remaining Time First, 최소 잔여시간 우선)라고 합니다. 뭔가 고정된 비선점형 스케줄링 알고리즘인 SJF보다, 조금 더 유연해보입니다. 현재 실행되고 있는 프로세스는, 최소 잔여시간인 프로세스임을 보장받습니다. 중간에, 현재 실행하는 프로세스의 남은 실행 시간보다 더 실행 시간이 짧은 프로세스가 들어온다면, 현재 프로세스에서 더 짧은 프로세스로 context-switching을 진행합니다. 선점형이라고 한 이유를 이해하셨나요?
예시 문제를 들어봅시다.
그렇다면, 만약 현재 실행하는 프로세스의 남은 실행 시간과 완벽하게 똑같이 추정된 프로세스가 들어온다면, 어떻게 하나요? 제 생각에는 바꾼다면 context-switching이라는 overhead가 생기기에, 바꾸지 않는 것이 합당해보입니다. 혹시 아시는 분이 있으시다면 댓글로 남겨주세요!
아무튼, 위 스케줄링 알고리즘은 일괄처리 시스템에는 유용합니다. 하지만 적은 response time(프로세스가 생기고 첫 실행하는데 걸리는 시간. 이는 공정성을 나타냅니다.)과, concurrency를 보장하는 시분할 시스템을 기반으로 해야하는 현대 사회에선, context-switching이 자주 일어나야 하는데, 위 기법들은 context-switching이 자주 일어나지 않습니다. 이는 현재 사용하기엔 무리가 있어 보입니다. response time을 줄이기 위해서 새로운 알고리즘이 등장합니다.
RR (Round Robin)
바로 RR 스케줄링입니다. 이는 프로세스 별로 시간(quantum, 편의상 q라고 표현하겠습니다.)을 할당합니다. 이 시간이 다 끝나면, queue에 대기하는 다음 프로세스로 context-switching을 합니다(timer interrupt로 구현되겠네요!). round robin 스케줄링을 사용한다면, 공정하게 프로세스가 각 시간별로 수행되기에, 시분할 시스템에도 유리할 뿐 아니라, response time도 줄어들 것이라 예상됩니다. 하지만 issue가 있습니다. 바로 시간을 얼마나 할당하는가에 대한 논의가 생깁니다. 만약 q가 너무 길다면, 사실상 FCFS(선입선출 구조)와 똑같을 것이고, q가 너무 작다면 context-switching이라는 overhead가 많이 발생합니다. 적절한 q를 찾는 것이 RR scheduling의 핵심입니다. 이는, turn around time(시작되고, 끝날 때까지의 시간)이 길어지지만, response time은 확실히 줄어들 것이라 예상됩니다. 일반화를 하자면, q가 길어지면 응답 시간은 늘어날 것으로 예상되지만, 평균 처리 시간은 감소할 것으로 예상됩니다. 반대로 q가 짧아지면, 응답 시간은 짧아지겠지만, 평균 처리 시간은 감소할 것으로 예상됩니다.
Priority Scheduling (우선순위 스케줄링)
또한, 프로세스별로 우선순위를 매겨 스케줄링하는 알고리즘도 존재합니다. 중요한 프로세스의 response time을 최소로 하겠다는 철학을 갖는 알고리즘입니다. 이를 선점형으로 구현한다면, 현재 실행하는 프로세스보다 더 우선순위가 높은 프로세스가 들어오면, context-switching을 합니다. 비선점형으로 구현한다면, 일단 하던 것을 다 하고 이후, 우선순위가 제일 높은 프로세스를 실행합니다.
하지만 이는 딱 봐도 큰 문제가 보입니다. 우선순위로 스케줄링을 한다면, 중요하지 못한 프로세스는 평생 실행되지 못할 수 있다(starvation, 기아 현상)는 단점이 눈에 제일 먼저 들어옵니다. 이는 너무 특권적인 알고리즘으로 보입니다. 이를 해결하기 위해, 너무 굶은 프로세스는 적절히 우선순위를 변경해 줘야 할 듯합니다. 이를 Aging 기법이라고 합니다.
RR + Priority scheduling
평균 응답률을 증가시키는 RR scheduling과, 중요한 프로세스는 빨리 실행시키자는 priority scheduling을 합치면 뭔가 좋아보입니다. 아무튼 RR + Priority scheduling 방식은 우선순위를 두되, 같은 우선순위라면 RR scheduling을 하자는 것입니다. 여러 level의 queue를 두고, 각 queue마다 priority를 다르게 설정합니다. 같은 queue라면 같은 priority를 갖고, 같은 queue level에선 RR scheduling을 합니다. 하지만 starvation 문제는 해결되지 않긴 합니다. 이를 위해 적절한 Aging 기법을 도입해야 합니다.
마무리하며
호흡이 길어지니 이만 끊고, 다음 글에서 남은 scheduling 방식에 대해 알아보겠습니다.