Process Scheduling

프로세스 스케쥴링(Process Scheduling)

 

프로세스 스케쥴링은 운영체제에서 프로세스들을 관리하고 실행시키는 방식을 결정하는 중요한 기능 중 하나입니다.
프로세스 스케쥴링 알고리즘은 CPU를 효율적으로 활용하고, 프로세스들의 우선순위들을 관리하며,
다양한 시스템 상황에 대응하여 적절한 처리 방식을 선택하는 데 사용됩니다.

프로세스 스케쥴링 알고리즘은 대개 다음과 같은 요소들을 고려하여 결정됩니다.

• 프로세스의 우선순위
• CPU 사용 시간 할당량
• 프로세스의 상태(대기 상태, 실행 상태, 준비 상태)
• 프로세스 간의 관계(자원 공유, 상호 차단 등)
• 시스템 자원 상황(메모리, I/O 등)

---

선점형 스케쥴링(Preemtive)

운영체제가 강력하고 강제적인 권한을 가지고 있으며, 잦은 문맥교환으로 오버헤드가 많이 발생합니다.

1. Round Robin
   • 각 프로세스는 실행할 고정 시간인 양자(Quantum)를 할당 받습니다.
   • 각 프로세스에게 일정한 시간을 할당하고 할당된 시간이 지나면 다른 프로세스에게 CPU를 넘기는 방식의
     스케줄링 기법입니다.
   • 할당된 시간이 끝나지 않았더라도 다른 프로세스가 CPU를 요청하면, 선점하여 CPU를 넘겨줍니다.
   • 시분할 시스템에서 주로 사용되며, 모든 프로세스에게 공정한 CPU 할당을 보장합니다.
     
     
2. SRT(Shortest Remaining Time)
   • CPU 점유시간이 가장 짧은 프로세스를 CPU에 먼저 할당하는 방식입니다.
   • 비선점 스케쥴링인 SJF 기법을 선점 형태로 변경한 기법입니다.
     
     
3. Multi-Level Queue
   • 프로세스를 여러 개의 큐로 분할하고 각 큐마다 우선순위를 부여하여 스케줄링을 하는 방식입니다.
     각 큐는 자체적인 스케줄링 알고리즘을 가지며 우선순위가 높은 큐에서부터 순서대로 처리됩니다.
     
     
4. Multi-level Feedback Queue
   • 프로세스 생성 시 가장 높은 우선 순위 준비 큐에 등록되며 등록된 프로세스는 FCFS 순서로
     CPU를 할당 받아 실행되고 할당된 시간이 끝나면 다음 단계의 준비큐로 이동
   • 단계가 내려갈수록 시간 할당량이 증가하고 가장 하위 큐는 Round Robin 방식으로 운영

 

비선점형 스케쥴링(Non-Preemtive)

 

1. FCFS(First Come First Served)
   • CPU 스케줄링 알고리즘 중 가장 간단한 방법 중 하나입니다. 이 방법은 프로세스가 CPU를 요청하는 순서대로
     처리하는 방식으로 먼저 도착한 프로세스가 먼저 실행 됩니다.
   • CPU 사용시간이 긴 프로세스가 먼저 도착하는 경우 뒤에 있는 짧은 프로세스가 오래 기다려야 하는
     상황이 발생할 수 있습니다. 따라서 FCFS 스케줄링은 시스템에 따라 적합하지 않은 경우도 있습니다.
     
     
2. SJF(Shortest Job First)
   • 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식입니다. 이 방식은 프로세스의 실행 시간을 미리 알고 있을 때 효과적으로 사용됩니다.
   • 대기 시간이 짧은 프로세스를 먼저 실행하여 전체적인 대기 시간을 최소화하고  CPU를 효율적으로 사용합니다.
   • 실행시간이 짧은 프로세스가 계속해서 도착하는 경우에는 실행시간이 긴 프로세스가 계속해서 대기해야 하는
     상황이 발생하는 기아 현상이 발생할 수 있습니다.
3. HRN(High Response Ration Next)
   • 대기시간과 서비스 시간(실행 시간)을 고려하여 우선순위를 결정하는 방식입니다.
   • 우선 순위를 결정할 때 대기시간과 서비스 시간(실행 시간)의 비율을 고려합니다.
     (대기 시간 + 실행 시간) / 실행 시간
     이 방식은 대기 시간이 짧은 프로세스보다는 서비스 시간이 긴 프로세스를 우선적으로 처리하도록 하여
     기아현상을 방지할 수 있고 대기 시간과 응답시간을 최소화합니다.
     
     
4. Priority(우선 순위)
   • 프로세스마다 우선순위를 부여하여 높은 우선순위를 가진 프로세스에게 먼저 자원을 할당합니다.
   • 우선순위가 낮을 경우 기아현상(starvation)이 발생할 수 있습니다.
     
     
5. 기한부(Deadline)

• 프로세스에게 일정한 시간을 주어 그 시간 안에 완료하도록 하는 기법이나 부담이 매우 큰 기법입니다.