운영체제 프로세스 스케줄링

 

 

비선점 방식:  특정 프로세스가 CPU 자원을 사용하고 있을 때, 처리가 끝날 때까지 자원을 점유.

선점 방식: 어떤 프로세스가 CPU 자원을 사용 중이지만, 우선순위 등의 상황으로 다른 프로세스가 사용 중인 CPU 자원을 가져갈 수 있음.

 

▶  FCFS (First Come First Served)

 ★ [비선점] 스케줄링

  - Ready Queue에 들어온 순서대로 CPU를 할당받음.

  - CPU 자원을 사용 중인 프로세스의 처리가 끝날 때까지 다른 프로세스는 대기.

 

->  프로세스가 들어온 순서에 따라 반환시간과 대기시간은 달라질 수 있다.

->  Convoy Effect (호위 효과): Ready Queue에 들어온 순서대로 비선점 방식의 처리를 하므로 처리 중인 프로세스의 자원 점유 시간이 길수록 늦게 들어온 프로세스는 오래 기다릴 수밖에 없는 상황을 의미. 

 

Convoy Effect는 CPU와 장치 이용률을 저하시키는 원인.

 

 

▶  SJF (Shortest Job First)

 ★ [비선점] 스케줄링

  - Ready Queue에 대기 중인 프로세스 중에서 "처리 시간이 가장 짧은 프로세스" 선택.

  - FCFS 대비 평균 대기시간을 감소시킬 수 있지만, 만약 처리 시간이 압도적으로 긴 프로세스가 있다면 예측 불가.

  - 모든 프로세스의 처리 시간을 이전부터 판단하기 어려운 점이 문제.

 

 

 

▶  Priority (우선순위 스케줄링)

 ★ [비선점, 선점] 스케줄링

  - 프로세스마다 할당된 "우선순위" 값을 바탕으로 CPU 자원을 할당할 프로세스 선택.

  - 우선순위 기준은 시스템에 따라 다를 수 있음 (낮은 값이 높은 우선순위 OR 높은 값이 높은 우선순위)

  - 같은 우선순위를 가졌을 경우, Ready Queue에 먼저 도착한 프로세스를 선택.

  - 상대적으로 높은 우선순위를 가진 프로세스가 계속 들어오면 낮은 프로세스는 무한정 대기. (기아 현상)

 

  - 예시는 낮은 값이 높은 우선순위.

 

 

 

▶  Round-Robin

 ★ [선점] 스케줄링

  - "시분할 시스템" 목적으로 설계. 대화식 사용자에게 알맞은 응답 시간을 보장.

  - 정해진 할당 시간 동안 프로세스에 자원 할당. 시간이 만료되면 다음 프로세스에 자원 제공.

  - 자원을 뺏긴 프로세스는 Ready Queue의 마지막 위치(인덱스)에 들어감.

  - 입/출력 인터럽트로 인해 유휴 상태가 된 프로세스의 경우 CPU 자원은 다음 프로세스에 넘어감.

  - 할당 시간의 크기가 성능에 영향을 주기 때문에 적절한 크기 설정이 중요.

 

  ★ Context Switching (문맥 교환): 인터럽트 발생 시 프로세스의 상태를 기억하고, 제어권을 인터럽트 처리 루틴에 이관. 

    할당 시간이 짧으면 프로세스 처리 과정에서 문맥 교환이 많이 발생할 수 있음 --> 성능 저하.

 

 

 

▶  SRT (Shortest Remaining Time)

 ★ [선점] 스케줄링

  - SJF에서 "선점" 방식이 도입된 구조.  --> 시분할 시스템에서 유용.

  - Ready Queue에 프로세스가 새로 도착한 시점을 기준으로 "남은 처리 시간이 짧은 프로세스 선점". 

  - 각 프로세스에 대한 처리 시간을 기억하고 있어야 하며 선점할 프로세스의 선택도 고려해야 함 (임계치 등).

 

 

▶  HRRN (Highest Response Ratio Next)

 ★ [비선점] 스케줄링

  - SJF의 단점을 보완하고자 "시스템 응답시간"을 우선순위로 사용하는 방법.

  - CPU 자원을 할당받은 프로세스는 완료될 때까지 자원을 이용한다.

  - 다음 차례가 될 프로세스는 이전 프로세스 처리 완료 시점을 기준으로 "대기시간"과 "처리시간"의 계산으로 선정.

 

 

 

▶  다단계 큐 (Multi-level Queue)

 ★ 각각의 Queue 스케줄링 방식에 따라 다름

  - 프로세스를 특성에 맞는 그룹으로 나누고, 각각에 독립적인 Queue를 구성. 스케줄링 방법도 각자 다를 수 있음.

  - 각 그룹은 우선순위가 고정적으로 정해져 있다. 따라서 "그룹 A > 그룹 B"의 우선순위면 그룹 A의 Queue에 있는 모든 프로세스는 그룹 B의 Queue에 있는 프로세스보다 우선한다.

 

 

 

▶  다단계  피드백 큐 (Multi-level Feedback Queue)

 ★ [선점] 스케줄링

  - Queueing Network 구조: 첫 단계부터 N 단계의 FCFS 구조 Queue + 마지막 Round-Robin.

  - 새로 들어온 프로세스는 첫 단계의 Queue에 FCFS 방식으로 추가 (첫 단계는 최상위 단계).

  - 수행 중이던 프로세스가 선점되어 CPU 자원을 뺏기면, 하위 단계 Queue에 재배치된다.

  -  마지막 단계의 Queue까지 도달한 프로세스는 Round-Robin 방식으로 처리될 때까지 순환한다.

  

 

 

-끝-