<운영체제 TIL 목록>
1. 운영체제란? 목적? 분류?
2. 인터럽트란? 컴퓨터 시스템 동작원리로 알아보자.
3. 하드웨어, 메모리 및 메모리 보안 방법?
4. 프로그램의 구조, 실행 과정?
5. 인터럽트, 문맥 교환(컨택스트 스위칭), PCB 정의와 차이?
7. 프로세스 생성? 자식 부모 관계를 이용한 협력?
8. 스레드, 멀티스레드란? 프로세스와의 차이?
9. CPU 스케줄링이란? 왜 필요? 알고리즘 종류, 평가 기준?
10. ''업데이트 예정"
1. CPU 스케줄링의 필요성
그냥 cpu를 프로세스에게 I/O 작업을 요청할 때 까지 주면 안될까? 아니면 시분할 방식으로 적당~히 나눠주면 안될까? 생각할 수 있다. 하지만 전자를 택하면 CPU 버스트(Burst) 작업이 긴 프로세스(CPU 바운드 프로세스)가 cpu를 너무 오래 갖고 있게 되어 문제가 된다. 또한 후자를 택하면 CPU 버스트 작업이 오래 진행되지 않더라도, CPU 사용이 비효율적으로 실행될 수 있다. I/O 버스트가 빈번하게 일어나는 I/O 바운드 프로세스가 비효율적으로 CPU를 배당받을 수 있기 때문이다. CPU 바운드 프로세스와 I/O 바운드 프로세스가 언제나 같은 레디큐에 있는 것 조차 I/O 바운드 프로세스에겐 차별일 수 있다. 왜 그럴까?
용어 정리
- CPU 버스트(Burst): 프로그램이 I/O를 한번 수행한 후 다음 번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 일련의 작업.
- I/O 버스트(Burst): I/O 작업 요청이 된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업.
- CPU 바운드 프로세스(CPU Bound Process): I/O 작업을 거의 수행하지 않아 CPU 작업이 길게 나타나는 프로세스.
- I/O 바운드 프로세스(I/O Bound Process): I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스.
이는 운영체제가 대화형 특징을 가진 소프트웨어이기 때문이다. UX의 질을 고려해야하기 때문에 I/O 작업이 CPU 버스트에 비해 우선순위를 받아야한다. 거기다 I/O 바운드 프로세스는 대체로 CPU 바운드 프로세스 보다 많다. 중요도가 높은 작업들이 낮은 작업에게 cpu 우선권을 밀리지 않아야하더라도 신경써야할 것이 많은데 I/O 버스트 작업에 CPU 버스트 작업보다 많다면 더 머리 아파지는 상황이다. 거기다 I/O 장치의 사용 효율도 고려해야한다. 운영체제는 하드웨어를 효율적으로 관리해야하기 때문이다. 효율은 즉 쉬지 않고 돌리는 것과 같다. I/O 장치를 효율적으로 사용하려면 I/O 작업이 많아야하고, 이는 I/O 버스트 작업이 빈번하게 일어나야한다는 뜻이다. 위와 같은 근거들에 의해 cpu 스케줄링은 필요하다.
필요성
- 근거1: 운영체제는 User interactive 특징을 가지고 있기 때문에 I/O 버스트가 CPU 버스트보다 중요도가 높다.
- 근거2: 중요도가 높은 I/O 버스트는 CPU 버스트 보다 훨씬 많다. *CPU 버스트가 차별을 많이 받으면 안된다.
- 근거3: I/O 장치 사용 효율을 고려해야한다. 운영체제는 하드웨어 또한 효율적으로 관리해야하기 때문이다.
결론
CPU 스케줄링할 때 CPU 버스트가 짧은 프로세스에게 먼저 CPU를 사용할 수 있도록 하며 CPU 버스트가 긴 프로세스가 차별을 많이 받지 않는 스케줄링이 필요하다.
자 이제 스케줄링 알고리즘에 대해 알아보고 뭐가 좋은지 비교까지 해볼까요? 각 종류에 대해 알아보기 전에 비교를 할 수 있는 도구에 대해 먼저 알아보고 가면 좋을듯하네요. 도구를 잘 익히면 재료를 잘 이해하고 익힐 수 있죠 ㅎㅎ
2. 스케줄링의 성능 평가 지표
스케줄링 성능 평가 지표에는 크게 두가지, 작게 다섯가지가 있습니다. 시스템 관점에서 스케줄링을 평가할 땐 CPU Utilization(CPU 이용률)과 Throughput(처리량)을 사용합니다. CPU는 컴퓨터에서 희귀하고 비싼 물건이기에 사용 효율을 높여야해요. 즉 쉴새 없이 일을 시켜야한다는거죠. 시스템 입장에선 전체 시간 중에 CPU가 일한 시간 즉 CPU 이용률이 많을 수록 스케줄링이 잘됬다고 볼 수 있습니다. 그림3을 보세요 현재 CPU 이용률이 95%군요! CPU를 잘쓰고 있는겁니다 ㅎㅎ
그렇다면 시스템은 CPU 이용률만 생각하면 될까요? 만약 CPU는 쉴새 없이 일했지만, 정작 끝낸 일이 없다면 어떨까요? 운영체제와 같은 대화형 소프트웨어는 I/O 작업이 많기에 끝낸 일이 쉴새 없이 많아야합니다. 단위 시간동안 CPU 버스트를 완료한 프로세스의 개수(Throughput=처리량) 또한 시스템의 스케줄링 성능 평가 지표가 되죠.
자 방금은 시스템 관점에서 스케줄링 성능 평가 지표를 알아봤습니다. 이 두가지만 가지고 스케줄링을 평가할 수 있다고 생각하면 오산입니다. 왜냐하면 운영체제의 목적은 자원의 효율적인 관리 뿐 아니라 형평성도 고려해야하고 특히 사용자에게 interative 인상을 줘야합니다. 형평성과 User-Interactive를 생각하려면 프로그램 개개의 관점 또한 살펴야합니다. 지금부터는 사용자 관점의 스케줄링 성능 평가 지표를 살펴보죠:)
바로 각 용어에 대해 설명하면 지루하니 예시를 들며 살펴보도록하죠. 여긴 고급 이탈리아 레스토랑입니다. 주방장(cpu)가 있고 여러분(사용자 프로그램)은 요리를 주문 했습니다. 근데 앞에 손님들이 많아 요리가 늦게 들어가나 보군요. 이때는 Ready 큐에서 기다립니다. 알림이 왔습니다 여러분의 요리를 주방장cpu가 요리하기 시작했군요! 방금까지 기다린 시간이 Response time(응답 시간)입니다. 프로세스가 준비 큐에 들어온 후 첫번째 CPU를 획득하기까지 걸린 시간이죠.
주방장 cpu가 여러분이 밥먹을 때 설명하느라 처음부터 끝까지 옆에 있다고 가정해보죠. 그럼 당신의 요리 만들어지고 당신이 그걸 다먹을때까지 당신은 주방장 cpu를 사용하게 됩니다. 당신이 밥을 다먹고 다음 요리를 기다린다고 가정하죠. (1) 이때 다른 손님의 음식도 조리되야하기에 당신은 다시 기다려야합니다. (2) 다른분들의 음식이 조리된 후 당신의 음식이 조리되기 시작한다는 알림이 떳어요! 자 방금 봤던 (1)번부터 (2)번까지의 시간이 Waiting time(대기 시간)입니다. 프로세스가 준비 큐에서 기다려왔던 시간입니다.
(3) 주방장이 음식을 가져와서 당신이 먹는 밥을 설명하며, 밥을 다먹길 기다립니다. 당신을 이후 2번째 코스 요리를 다먹었죠(참고로 N번까지 많이 남았습니다). (1), (2), (3)번을 모두 합해서 Turnaround time(소요 시간)이라고 합니다. Ready 큐에서 기다린 시간과 실제로 CPU를 사용한 시간을 합한 값이죠.
*용어 정리
1) 시스템 관점
- CPU Utilization(CPU 이용률): 전체 시간 중에 CPU가 일을 한 시간.
- Throughput(처리량): 단위 시간 동안 CPU 버스트를 완료한 프로세스의 개수
2) 사용자 관점
- Turnaround time(소요 시간): Ready 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합.
- Waiting time(대기 시간): Amount of time a process has been waiting in the ready queue.
- Response time(응답 시간): 프로세스가 준비 큐에 들어온 이후 첫번째 CPU를 획득하기까지 기다린 시간.
3. 스케줄링 알고리즘의 두가지 모습
자 이제 스케줄링 알고리즘 평가 도구를 알았으니 스케줄링 알고리즘에 대해 알아볼까요? 그 전에! 스케줄링 알고리즘 분류 도구 딱 2가지만 알고 가도록하죠. 멀리 안남았습니다! 신기하게도 모든 스케줄링 알고리즘들은 비선점형 & 선점형으로 나뉘어지는 경우가 많아요. 잠깐! 선점형이 뭘까요? 선점형은 preemtive의 한국어 번역입니다. preemtive는 '우선권이 있는'이라고 이해하면 됩니다(그림4 참조). '선점형 방식=(cpu 빼앗기)우선권이 있는 방식'으로 이해해보도록 하죠!
비선점형 방식은 프로세스가 스스로 CPU를 반납하기 전엔 cpu를 빼앗기지 않는 방식이에요. 옛날엔 프로그램을 한번 돌리면 그 프로그램이 끝날때 까지 아무 것도 할 수 없는 시절이 있었대요. 딱 이러한 것이 비선점형 스케줄링 알고리즘이겠죠? 너무 극단적인 예를 들었지만 현대에도 비선점형 방식은 많습니다 ㅎㅎ.
두번째는 선점형 방식이에요. 선점형 방식은 프로세스가 CPU를 계속 사용하기 원하더라도 강제로 뺏을 수 있는 스케줄링 방법이에요. 운영체제가 시분할 방식으로 cpu 할당을 관리하면 선점형 방식을 이용하는 거겠죠?
* 용어 정리
1) 선점형(preemptive=우선권이 있는)
- 장점: 중요도 높은것이 빠르게 처리
- 단점: 중요도 낮은게 차별 받음
2) 비선점형(nonpreemptive=우선권이 없는)
- 장점: 프로세스들이 비슷한 cpu 버스트 시간을 가질 때, 소요시간, 대기시간이 짧아짐.
- 단점: 평균 응답 시간이 길다.
4. 스케줄링 알고리즘
드디어 스케줄링 알고리즘을 배울 차례가 됬습니다. 우린 평가 & 분류 도구를 알았으니 이를 가지고 스케줄링 알고리즘을 맛있게 요리해보도록 하죠. 처음부터 어려운 것을 설명하면 머리아프니 가장 오래된 것 부터 최근 것 위주로 설명하겠습니다. 가장 오래됬다는건 가장 간단하다와 유사하게 해석될 수 있습니다. 가장 간단한 스케줄링 알고리즘에 대해 알아보겠습니다.
1. 선입 선출 스케줄링 알고리즘(FCFS, First Come First Served)
선입선출 스케줄링 알고리즘은 프로세스가 온 순서대로 cpu를 할당 받는 알고리즘입니다. 프로세스 중요도가 높든 cpu 버스트가 길든 선입선출 스케줄링 앞에선 모두가 평등합니다. 자신이 cpu를 할당 받고 스스로 내놓기 전까지 계속 사용합니다. 자신의 일이 끝나거나 I/O를 해야하면 그제서야 내놓게 되죠. 선입선출(First Come First Served)는 두가지 장점이 있습니다. 우선 구현이 굉장히 쉽죠. 들어온 순서대로 넣으면 됩니다. 그리고 비슷한 CPU 버스트 시간을 가진 프로세스들을 스케줄링할 때 평균 소요, 대기 시간이 적습니다. 예를들어 CPU 버스트가 10인 프로세스 5개가 온다고 하죠. 시스템콜이 없다는 가정하에, 이들은 대기 시간이 0, 10, 20, 30, 40, 50입니다. 평균 30이죠. 소요시간도 비슷합니다. 이에 비해 라운드로빈이라는 스케줄링 알고리즘은(시분할 방식입니다) cpu 할당 시간이 1이면 평균 대기 & 소요 시간이 50이 됩니다. 이렇듯 FCFS는 균일한 CPU 버스트 시간을 가진 프로세스가 준비 큐에 있을 때 낮은 평균 대기 & 소요 시간을 보이죠.
FCFS는 구현의 단순함과 특정 조건의 준비큐 상황에서 낮은 평균 대기 및 소요 시간의 장점을 가지지만, 심각한 단점이 존재합니다. 프로세스들의 소요 & 대기 시간의 편차가 큽니다. 위 문단의 예에서 봤다 싶이 두번째와 마지막은 40씩이나 차이나요. 편차가 크다는 것은 불이익을 받는 프로세스가 존재한다는 뜻입니다. 또한 프로세스가 처음 cpu를 할당 받는 시간인 응답시간의 평균이 높아집니다. 사용자의 입장에선 마치 모든 프로그램이 동시에 동작되는 듯한 느낌을 받아야하는데, 하나씩 순서대로 켜지는 느낌이 들겠죠. 마지막으로 CPU 버스트가 긴 프로세스가 CPU 버스트가 짧은 프로세스보다 먼저 Ready 큐에 들어오게 되면 CPU 버스트가 짧은 프로세스가 긴 대기시간을 가지게 됩니다. 이는 Ready 큐 전체 효율에도 영향을 미칩니다. CPU 버스트가 긴 프로세스 뒤에 짧은 프로세스가 많다면 그만큼 평균 대기시간이 길어지는 것이죠(그림5 참조). 이를 콘보이 이펙트(Convoy effect)라고 부릅니다. Convoy는 후송대라는 뜻을 가집니다. 먼저 후딱 못가고 다른 것에 의해 이끌려가니 문맥상 비슷하죠? 콘보이 이펙트가 일어나면 악영향을 끼치는 지표가 I/O이용률입니다. CPU 버스트가 짧은 프로세스가 빨리 실행되어 I/O를 실행시키면 I/O 장치들을 놀게하지 않아 하드웨어 이용 효율이 좋아집니다. 하지만 CPU 버스트가 긴 프로세스가 오면 I/O 장치가 놀 확률이 높아지죠. 자 FCFS를 정리해보죠.
*용어 정리
- 정의: 온 순서대로 cpu를 할당 받는 방법
- 장점
- 구현이 단순
- 비슷한 CPU 버스트 시간을 가진 프로세스들을 스케줄링할 때 평균 소요, 대기 시간이 적음.
- 단점
- CPU 버스트가 긴 프로세스가 늦게오면, 평균 대기 시간이 길어진다.
- 평균 응답 시간이 길어진다.
- I/O 장치의 이용률이 하락한다.
- 콘보이 현상(Convoy 현상): CPU 버스트가 짧은 프로세스가 긴 프로세스보다 늦게 도착해 오랜 시간을 기다려야 하는 현상.
2) 최단작업 우선(Shortest-Job First: SJF), 우선순위 스케줄링
최단작업 우선, 우선순위 스케줄링은 특징이 매우 비슷합니다. 각각을 공통점과 차이점과 함께 알아보죠. 최단작업 우선 스케줄링은 CPU 버스트가 가장 짧은 프로그램에게 제일 먼저 CPU를 할당하는 방식입니다. 간단하군요. 하지만 걱정이 있습니다. CPU 버스트가 가장 짧을지 어떻게 알죠? 어떻게 예측할까요? 이는 과거 cpu 버스트 예측 시간과 과거 cpu 실행 시간에 적절한 가중치를 주어 다음 cpu 버스트 예측 시간을 판단하는 방식으로 진행합니다. 식을 봐볼까요?
그림 6을 통해 우리는 CPU 버스트 시간 예측 법을 알 수 있습니다. 더 시간이 지난 실제 실행 값일 수록 더 낮은 가중치를 주는 방식이죠. 이러한 예측 법을 이용하는 SJF를 이용하면 콘보이 이펙트가 일어나지 않습니다. 짧은 CPU 버스트 시간이 예측되는 프로세스에게 먼저 우선권을 주기 때문이죠. 이로 인해 프로세스들의 평균 대기 시간이 짧아지게 됩니다. 실제로 SJF는 평균 대기 시간이 가장 짧은 스케줄링 알고리즘이죠.
과연 평균 대기 시간이 짧을 수록 좋은 알고리즘일까요? SJF는 심각한 형평성 문제를 가집니다. CPU 버스트가 긴 시간 앞에 계속해서 버스트가 짧은 프로세스가 오면 전자는 무한정 대기할 수도 있습니다. 이를 Starvation=기아현상이라고 부르죠. CPU 버스트가 긴 프로세스가 cpu를 얻지 못하고 굶는 상황입니다.
위 문단들은 SJF와 Priority 스케줄링 알고리즘이 공통적으로 같는 특징입니다. Priority가 CPU 버스트 시간이 된다면 두개는 동일하다고 볼 수 있죠. 두개는 기아현상 해결법 유무에서 차이가 있습니다. Priority 스케줄링 알고리즘은 노화(aging) 기법으로 이를 해결합니다. cpu를 할당 받지 못하는 시간에 비례해서 우선 순위에 가중치를 더해주는 방법입니다.
* 용어 정리, 최단작업 우선(SJF)
- 정의: CPU 버스트가 가장 짧은 작업 먼저 CPU를 할당한다.
- 비선점형: CPU 버스트가 더 짧은 작업이 와도 현재 CPU 할당권을 보장받음.
- 선점형: CPU 버스트가 더 짧은 작업이 오면 CPU 할당권이 이양됨.
- 장점
- 프로세스들의 평균 대기 시간을 최소화 하는 알고리즘.
- 단점
- CPU 버스트 시간을 미리 알 수 없음. Tn+1 = a*tn + (1-a)*Tn (T=예측 시간, t=실제 시간, a=가중치)
- 기아 현상(Starvation): CPU 버스트가 긴 작업이 CPU 버스트가 짧은 작업의 지속적인 유입으로 CPU를 계속 할당 받지 못하는 상태.
*용어 정리, 우선순위(Priority) 스케줄링
- 정의: 준비 큐에서 기다리는 프로세스 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU 할당하는 방식.
- 비선점형: 우선순위가 더 높은 프로세스가 Ready 큐로 들어와도 현재 CPU 제어권이 보장됨.
- 선점형: 우선순위가 더 높은 프로세스가 Ready큐로 들어오면 현재 CPU 제어권이 이양됨.
- 장점
- 프로세스들의 평균 대기 시간이 짧아짐.
- 단점
- 기아 현상이 발생. 물론 이는 노화(aging) 기법을 활용하여 해결 가능.
3) 라운드 로빈(Round Robin) 스케줄링
시분할 시스템의 기반이 되는 라운드 로빈 스케줄링입니다! FCFS, SJF, Priority 스케줄링 알고리즘은 각각 장점이 있었지만 응답시간의 형평성을 해결할 수 없는 치명적인 단점이 있었죠. 왜 치명적이냐고요? 운영체제는 user-interative 특징을 가지기 때문이죠. 따라서 프로세스는 Response time이 빨라야합니다. 라운드 로빈은 균일한 cpu 부스트 시간을 가진 Ready 큐와 같은 비현실적인 환경이 아니라, 상이한 cpu 부스트 시간을 가진 환경에서 강점을 가집니다. 이러한 형평성 은 응답 시간 뿐 아니라 소요 & 대기 시간에서도 영향을 끼칩니다. 라운드 로빈에 대해 알아보죠!
라운드 로빈은 timer 장치에 의해 구현됩니다. 운영체제가 timer에 할당 시간(CPU를 연속적으로 사용할 수 있는 최대 시간)을 설정하면, 프로세스가 해당 시간을 초과해서 cpu를 사용시 timer interrupt를 설정하죠. 이후 디스패처(아래 용어 참조)에 의해 컨텍스트 스위칭이 일어나죠. 이때 할당 시간을 길게 조절하면 마치 FCFS와 같이 스케줄링이 동작하게 되지만, 적절하게 짧게 설정하면 I/O 바운드 프로세스가 빠르게 CPU를 할당 받고 I/O 작업을 하러 갈 수 있게 됩니다. 즉 평균 소요 및 대기 시간이 짧아지겠죠. 이때 평균 & 소요 대기 시간의 형평성도 보장됩니다. 더 자세히 알아볼까요?
CPU 바운드 job이 라운드 로빈에서 cpu를 얻게 되면 아마 할당 시간을 다쓰게 될겁니다. 그렇다면 해당 프로세스의 총 소요 시간도 길어지게 되죠. 비슷하게 I/O 바운드 잡에 cpu를 얻게 되면 할당 시간 이내에 I/O를 하러 갈 확률이 높기 때문에 총 소요 시간도 작아지게 됩니다. 즉 CPU 부스트 시간과 총 소요 시간이 비례한거죠. CPU 바운드 잡은 I/O를 안하기 때문에 CPU를 뺏기면 다시 레디큐로 가게 될 것입니다. 그럼 해당 프로세스의 총 대기 시간도 길어지게 되겠죠. 정리하면 CPU 부스트 시간과 총 소요 & 대기 시간이 비례하게됩니다. 이는 사용자 관점에서 스케줄링이 형평성 있게 진행되는 모습이죠.
라운드 로빈은 형평성 뿐 아니라 응답 시간에도 강점을 가집니다. 프로세스가 된 프로그램은 레디 큐 맨뒤로 들어간다 가정합시다. 이때 프로세스는 (레디큐 내 PCB 갯수 - 1)*할당 시간 내에는 무조건 CPU 제어권을 얻게 됩니다. SJF, Priority 스케줄링 알고리즘과는 달리 보장된 짧은 응답시간을 가지게되죠.
물론 라운드 로빈 또한 단점이 있습니다. 할당 시간을 지나치게 짧게 두면 컨텍스트 스위칭이 자주 일어나 오버헤드가 커집니다. 배보다 배꼽이 더 커진 격이죠. 이는 적절한 할당 시간 설정으로 해결됩니다. 또한 균일한 CPU 버스트 시간을 가진 Ready 큐 집합에선 소요 & 할당 시간이 FCFS, SJF 및 Priority 스케줄링 알고리즘보다 큽니다. 하지만 실제 컴퓨터는 상이하고 불규칙적인 CPU 버스트 시간을 가진 프로세스들이 Ready 큐에 들어오기 때문에, 이는 문제가 되지 않습니다. 자 라운드 로빈에 대해 알아봤으니 용어 정리를 해볼까요?
*용어 정리
- 정의: 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 주어진 시간이 지나면 해당 프로세스로부터 CPU를 회수해 준비 큐에 있는 다른 프로세스에게 할당.
- 철학: CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것.
- 할당 시간(Time Quantum): CPU를 연속적으로 사용할 수 있는 최대 시간.
- 할당 시간을 수십 밀리 초 정도의 규모로 보통 설정함. 이는 대화형 프로세스가 CPU를 한번 할당받기까지 지나치게 오래 기다리지 않을 정도의 규모임.
- 장점
- 여러 종류의 이질적인 프로세스가 실행되는 환경에서 효과적. CPU 버스트 시간에 비례해 소요 & 대기시간이 늘어나 형평성이 맞기 때문.
- 평균 응답 시간이 가장 빠름. 대화형 시스템에 좋음.
- 단점
- 할당 시간을 너무 짧게 하면 컨택스트 스위칭 오버헤드가 커진다.
- CPU 버스트가 비슷한 프로세스들을 스케줄링 할 때, 평균 대기 시간과 평균 소요 시간이 길어짐.
*용어 정리, 디스패처
- 새롭게 선택된 프로세스가 CPU를 할당 받고 작업을 수행할 수 있도록 환경 설정 하는 운영체제 코드
- 현재 진행중이던 프로세스의 상태를 PCB로 저장해놓고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘겨주는 과정 수행
- 디스패치 지연시간: 하나의 프로세스를 정지시키고, 다른프로세스에게 CPU를 전달하기까지 걸린시간.
4) 각 스케줄링 알고리즘 비교
| FCFS | SJF / Priority | Round Robin | |
| 소요 시간(Turnaround time) | 짧음 in CPU 버스트 시간 균일 집단 |
짧음 | 보통 |
| 대기 시간(Waiting time) | 짧음 in CPU 버스트 시간 균일 집단 |
가장 짧음 | 보통 |
| 응답 시간(Response time) | 길다. | CPU 버스트 짧으면 빠름 CPU 버스트 길면 느림 |
빠름 |
| 형평성 | Convoy effect | 기아 현상 | GOOD CPU 버스트 길면 소요 & 대기 길어짐. CPU 버스트 짧으면 소요 & 대기 짧아짐 |
후.. 임시저장이 안되서 다시씁니다 ㅠㅠ 피같은 나의 글들 ㅠㅠ 하지만 더 잘 쓸 수 있다는 생각을 하며 글을 이어가보도록 해보겠습니다 ㅎㅎ 자 우린! 방금 여러가지 스케줄링 알고리즘들을 살펴봤습니다! FCFS, SJF, Priority, 라운드 로빈이 있었죠. 각각 장단점들이 있었습니다! 만약 여러분들이 여기서 하나의 알고리즘을 고르라하면 어떤 것을 고르실건가요? 답정너 질문이였지만 아마 라운드 로빈을 고르실겁니다 ㅎㅎ 운영체제의 user-interative한 특성 때문이죠. 근데 라운드 로빈도 단점이 있는데도 고르실건가요? cpu 바운드 job이 운영체제에 남아있는 상황에선 라운드로빈은 쓸데 없는 컨택스트 스위칭만 일으킬겁니다. 이런 상황에선 FCFS를 쓰는게 훨씬 좋죠. 질문 자체가 문제였다고요? 하나의 알고리즘만 골르라고 하지 않았냐구요? 맞습니다 ㅎㅎ 앞과 같은 이유로 실제로는 여러 큐를 섞어서 사용하죠!
4) 멀티레벨 큐
멀티레벨 큐는 준비 큐를 여러개로 분할해 관리하는 스케줄링 기법입니다. 전위 큐를 라운드 로빈 방식으로 구성하고, 후위 큐를 FCFS 방식으로 구성할 수 있죠. 이렇게 되면 라운드 로빈(RR로 하겠습니다) 큐에 CPU 버스트가 짧은 I/O 바운드 job을 넣으면 되고 FCFS 큐에 CPU 버스트가 긴 CPU 바운드 job을 넣으면 되죠. 이와 같이 구성하면 각 프로세스가 의미 효율적으로 컨택스트 스위칭을 하게 됩니다. 또한 CPU 바운드 job은 Response time의 중요도가 낮기 때문에 FCFS의 단점이 상쇄도기도 합니다. 이렇듯 멀티레벨 큐의 목적은 성격이 다른 프로세스들을 별도로 관리하는 것에 있습니다.
큐는 두개 이상이 될 수 있지만 CPU는 하나이기 때문에 CPU를 누구에게 주어야할지도 스케줄링이 되야합니다(CPU가 2개 이상이여도 같습니다). 이를 해결하는 가장 간단한 방법은 우선순위가 높은 큐에 cpu를 할당하는 고정 우선순위 방식(fixed priority scheduling)입니다. CPU 버스트가 짧은 I/O 바운드 job이 존재하는 RR 큐가 우선순위가 높고 FCFS 큐가 낮게 설정되죠. 이렇게되면 RR 큐 내에 있는 프로세스들이 전부 cpu를 사용한 후에 FCFS 큐에 있는 프로세스가 cpu를 사용할 수 있게됩니다. 문제가 있는 것 같다고요? 맞습니다. Starvation 문제가 생깁니다. RR 큐에 작업이 계속 들어오면 FCFS 큐에 있는 작업들은 cpu를 할당 받지 못해 굶게됩니다. 이러한 방식을 해결하기 위해 타임 슬라이스(time slice) 방식이 사용됩니다. 큐 마다 cpu를 사용할 수 있는 시간 비율을 설정하게 되면 FCFS 큐도 굶지 않겠죠. 예를 들어, RR 큐는 cpu의 80%, FCFS 큐는 cpu의 20% 시간을 할당 받는 방식입니다.
멀티레벨 큐의 Starvation 방식을 해결할 수 있는 방법이 타임 슬라이스 방법 밖에 없을까요? 이전에 개별 알고리즘들이 Starvation 현상이 있었을 때 어떤 방식으로 해결했는지 기억나시나요? Priority 스케줄링은 이를 노화(aging) 기법으로 해결했습니다. 멀티레벨 큐를 잘 활용하면 노화 기법을 흉내낼 수 있습니다. 이를 멀티레벨 피드백 큐라고 하죠!
5) 멀티레벨 피드백 큐
멀티레벨 피드백 큐는 프로세스들을 여러 큐에 세운다는 점에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다릅니다. 운영체제가 프로세스의 성격을 알아내는 방법은 뭘까요? 얘가 CPU 바운드 job인지 I/O 바운드 job인지 알 수 있는 방법이 뭘까요? CPU를 한번 할당 했는데 계속 달라고 하면 아마 그 프로세스는 CPU 바운드 job일 확률이 높습니다. 멀티레벨 피드백 큐는 이러한 원리를 이용해서 구현됩니다.
멀티레벨 피드백 큐의 과정을 상세히 살펴보죠. 모든 프로세스들은 처음엔 맨위 라운드로빈 큐(할당시간 5)에 들어오게 됩니다. 빠른 Response time이 보장되겠군요! 이후 해당 큐를 거친 후에도 I/O 장치 큐가 아닌 준비 큐로 다시 들어오려하면 기회를 한번 더줍니다. 두번째 라운드로빈 큐(할당시간 10)으로 가게 되죠. 만약 두번째 큐 이후에도 다시 CPU를 바로 얻으려한다면 이는 CPU 바운드 job일 확률이 높습니다. 그 다음엔 FCFS 큐로 들어가게 됩니다.
멀티레벨 피드백 큐는 여러개의 라운드 로빈 큐와 FCFS 큐를 연결하여 노화(aging) 기법을 구현합니다. 이러한 방식은 라운드 로빈 스케줄링과 멀티레벨 피드백 큐를 한층 더 발전 시킵니다. 짧은 프로세스일 수록 더 빨리 서비스 받을 수 있게하고, 긴 작업이 필요한 프로세스일 수록 문맥교환 없이 CPU 작업에 열중하게 할 수 있는 환경을 만들어줍니다.
자 이제 스케줄링 알고리즘에 대해 알겠습니다! 다음번 포스팅에는 운영체제의 꽃중 하나인 Process synchronization에 대해 알아보겠습니다:) 모두들 즐코 언쟝!
'운영체제(OS)' 카테고리의 다른 글
| [운영체제] 8. 스레드, 멀티스레드란? 프로세스와의 차이? (0) | 2022.02.22 |
|---|---|
| [운영체제] 7. 프로세스 생성? 자식 부모 관계를 이용한 협력? (0) | 2022.02.22 |
| [운영체제] 6. 프로세스란? 5 or 6가지 상태? 스케줄러? (0) | 2022.02.20 |
| [운영체제] 5. 인터럽트, 문맥 교환(컨텍스트 스위칭), PCB 정의와 차이? (0) | 2022.02.19 |
| [운영체제] 4. 프로그램의 구조, 실행 과정? Easy with TMI (0) | 2022.02.18 |
