🌟 본 게시물은 이화여자대학교 반효경 교수님 강의를 참고로 작성한 게시물 입니다. 틀린 내용은 꼬옥 지적 부탁드립니다 ! 🌟
1. Multilevel Queue (SingleCore Cpu 기준)
✔️ Multilevel Feedback Queue보다 프로세스 차별적인 방식
✔️ Ready queue를 여러 개로 분할
- foreground (interactive)
- background (batch - no human interaction)
✔️ 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR (라운드 로빈)
- 사용자와 대화하는 프로세스이기 때문에 응답시간이 짧은 것이 중요하다
- background - FCFS (선입선출)
- 사용자와 대화없이 CPU만 사용하는 batch형 작업이기 때문에 응답시간이 빠를 필요가 없다
✔️ 큐에 대한 스케줄링이 필요
- Fixed priority scheduling
- serve all from foreground then from background
- Possibility of starvation
- 우선순위가 높은 작업이 종료되지 않으면 우선순위가 낮은 프로세스는 영원히 실행되지 못하는 문제가 발생할 수 있다.
- Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
- starvation을 막기위해 전체 CPU 사용시간을 우선순위가 높은 foreground 작업에 80% 할당하고 우선순위가 낮은 background 작업에 20%를 할당하게 한다.
2. Multilevel Feedback Queue (SingleCore Cpu 기준)
✔️ 프로세스가 다른 큐로 이동할 수 있음
✔️ 에이징(aging)을 이와 같은 방식으로 구현할 수 있음
✔️ Multilevel-feedback-queue scheduler를 이루고 있는 요소들
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫓는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
✔️ 처음 실행되는 작업은 우선순위를 가장 높게 받음
2.1 Multilevel Feedback Queue 예시
✔️ Three queues:
- Q0 - time quantum 8 milliseconds
- Q1 - time quantun 16 milliseconds
- Q2 - FCFS (선입선출)
✔️ Schduling
- 새로운 작업이 Q0으로 들어간다.
- CPU를 잡아서 할당 시간 8milliseconds 동안 수행된다
- Q0에서 할당받은 시간내에 작업을 다 끝내지 못했으면 Q1로 내려간다.
- Q1에 줄서서 기다렸다가 CPU를 할당받고 16ms 동안 수행된다.
- Q1에서 할당받은 시간내에 작업을 끝내지 못한 경우 Q2로 쫓겨난다.
3. 멀티코어 CPU의 경우 고려해야할 점
CPU가 여러 개인 경우 스케줄링은 더욱 복잡해진다.
✔️ Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
- 반드시 특정 프로세스에세 수행되어야 하는 프로세스가 있는 경우에는 문제가 복잡해진다.
✔️ Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
✔️ Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
✔️ Asymmetric multiprocessing
- 비대칭형 다중 처리기
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따라 움직이는 방식
- 대칭형 다중 처리기
- CPU가 각자 알아서 스케줄링하는 방식
4. Real-Time Scheduling
✔️ Hard real-time systems
- Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
✔️ Soft real-time computing
- Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
✔️ EDF (Earlist Deadline scheduling)
- 실시간 환경에서는 먼저 온 요청보다 데드라인이 다가온 요청을 먼저 처리하는 스케줄링
- 연성 실시간 시스템처럼 일반 작업과 VOD 작업 등이 혼합된 환경에서는 데드라인이 존재하는 프로세스에게 일반 프로세스보다 높은 우선 순위를 할당한다.
5. Thread Scheduling
✔️ Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄링할지 결정
- 이 경우에 운영체제는 해당 thread의 존재를 알지 못한다.
✔️ Global Sheduling
- Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
6. Process Synchronization
멀티 프로세서 시스템의 경우 메모리 주소공간을 공유하는 CPU 프로세스가 여럿 있는 경우 Race Condition의 가능성이 있다. 아래 내용들은 Race Condition 발생 원인과 이를 해결하기 위한 프로세스 동기화 방법이다.
✔️ Race Condition?
여러 프로세스들이 동시에 공유데이터에 접근하여 경쟁하는 상태이다.
여러 프로세스가 동시에 공유데이터에 접근하게되면 데이터의 불일치 문제를 발생시킬 수 있다.
일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘이 필요하다
✔️ OS에서 Race Condition은 언제 발생하는가?
- Kernel에서 수행 중 인터럽트 발생 시
- Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
- N 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
‼️ 한 프로세스가 공유 데이터를 사용하고 있을 때 다른 프로세스가 접근하면 안되는 이유 ‼️
- 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 ciritical section이 존재한다.
- 이 경우에 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
✔️ Race Condition은 어떻게 방지하는가?
- Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
- 커널 모드에서 수행 중일 때는 CPU를 선점하지 않고 커널모드에서 사용자 모드로 돌아갈 때 CPU를 선점하는 방식
- Multiprocessor에서 shared memory 내의 kernel data
- 방법 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
- 방법 2) 커널 배우에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법