서론
뭐 이래 많음?
많다. FCFS, RR, SJF, HRRN, MLQ, MFQ 그 외에도 많을 것이다. 근데 확실하게 말할 수 있는 것은 스케줄링도 결국 자원을 “효율적”으로 사용하려고 만들어진 것이다. 사람 생각 다 똑같다.
본론
그림으로 보는 스케줄링의 개념
스케줄링은 말 그대로 스케줄링이다. 나라는 사람도 장기, 중기, 단기 계획이 있듯 스케줄링도 이러한 개념을 따른다. 봐봐 사람다 똑같잖어
결국 스케줄링은 자원을 사용하는 시간을 나눈 것이라고 봐도 무방할 것 같다. 왜냐하면 “cpu를 100%만큼 쓸꺼야”와 “cpu를 10초 동안 쓸게” 는 다르기 때문이다. 솔직히 전자는 너무 추상적이고, 100%의 수치도 상대적이다. 그래서 필자입장에서 설명할 때는 시간이라고 못 박아 놓고 시작한다. 그래서 결론은 “스케줄링은 얼마나 공평하게 시간을 잘 나눌 것인가”에 대한 이론이다. 아래의 개념에서 알 수 있듯 대충 short time scheduling이 우리가 가장 많이 접하고, 알아야 하는 내용이다. 프로그램이 만들어져서 ready → running을 기다리는 것이다.
ready Queue로 들어오는 것들의 순서를 정해주는 작업 = 스케줄링
이해하고 있어야 하는 내용
1.
선점
a.
왜? 선점이라고 하는데 내 기준에서는 강탈이라고 이해했다. 뺏을 수 있으면? 정해진 시간만큼 일을 못하게 할 수 있다.
2.
비선점
a.
왜? 비선점이라고 하는데 내 기준에서는 못뺏음. 이라고 이해했다. 즉, 정해진 시간에 온전히 일할 수 있는 것이다. 조퇴는 가능하나, 퇴학은 안된다.
3.
우선순위
a.
왜? 이건 정말 크게 이해하고 있어야 한다. 결국 필자의 경우 이런 공식으로 접근했다.
공평하다
= 특정한 조건을 통하여 분배가 가능
= 특정한 조건이 뭐가 있을까?(들어온 순서, 짧은 순서, 정해진 시간)
= 이걸 뭐라고 부를까? 우선순위
= 즉, 우선순위에 의해서 공평성이 결정된다.
4.
cpu 상태 전이
a.
왜? 전이도를 알아야 스케줄링이 특정 상태를 변화시킨다는 것을 이해할 수 있다.
5.
context switching
a.
왜? 젤 중요하다. 이게 이해 못하겠으면 외워서라도 알고 있어야한다.
운영체제 관점에서 context switching은 pcb에 현재하고 있던 작업 내용을 saving하고 ready queue에서 자원을 할당 받아야 하는 process의 작업 내용을 restoring 하는 작업을 말한다. 즉, 해당작업을 저장하고, 저번에 중단했던 종단점부터 다시 작업을 시작하는 것
개략적인 알고리즘들
상세히 보는 알고리즘
명칭 | FIFO = FCFS | SJF | RR | SRT | MLQ | MLFQ |
정책 | 비선점 | 비선점 | 선점 | 선점 | 선점 | 선점 |
가정 | X | 동일 도착 시간 | X | 도착시간이 달라도 실행시간 이짧다면 뺏을 수 있음 | X | X |
특징 | X | X | 정해진 사용 시간 | SJF의 선점 방식 | Ready Queue를 여러개 만들어서 사용 | 일정 시간 일하면 우선순위가 낮은 큐로 보내버림 |
방식 | 선입선출 | FIFO + 가장 짧은 실행 시간 | FCFS + 사용 시간 | SJF + 선점 | 큐 여러개 | 이동 가능 큐 여러개 |
장점 | 쉬움 | 짧은 평균 대기 시간 | 빠른 응답시간 | 짧은 평균 대기 시간 | 프로세스 ready Queue마다 우선순위 다르게 부여 가능 | MLQ의 발전 된 형태 |
단점 | convoy Effect | 도착시간이 안 동일 하면 FIFO랑 똑같음 | 짧게 잡으면 overhead 커지고, 크게 잡으면 FIFO랑 동일해짐 | 기아 현상 발생 우려 | 기아현상 발생 우려 |
결론
사람 생각 다 똑같다. 라는 결론에 도달 할 수 있었다. 결국 공평하게 얼마나 cpu를 사용하게 할지 고민하다 보니 자연스럽게 아래와 같은 사고가 된 것을 알 수 있었다.
1. “먼저 도착하면?” → 대기 시간이 길어지더라
2. “실행 시간이 더 짧은 애들을?” → 잘못하니 기아현상이 나더라
3. “시간 동일하게?” → 시간은 얼마나 줘야하는거야? 길게 잡으니깐 FIFO랑 똑같아지던데?
4. “사용하는 자원에 따라?” → 특정 자원 사용량이 몰리니깐 기아현상 나더라
5. “동일하게 사용하고 뒤로 한 칸 밀어 볼까?” ⇒ 일정 시간만 쓰고 다음 우선순위를 주자
저런 그림을 이해하고 나서 다시 스케줄링 알고리즘을 보니 엄청 쉽게 느껴졌다. 결국 다 똑같구나. 그리고 결국 모든 CS 문제에서 특정 자원을 사용할 땐 결국 Queue를 사용하는 방법이 정답에 가깝다는 것을 느낄 수 있었다.