Computer Structure & OS(11) - CPU 스케줄링

1) CPU 스케줄링 개요

    1-1) 프로세스 우선순위

    1-2) 스케줄링 큐

    1-3) 선점형과 비선점형 스케줄링

2) CPU 스케줄링 알고리즘

    2-1) 스케줄링 알고리즘의 종류

 

 

 

 

 

 

 

1) CPU 스케줄링 개요

1-1) 프로세스 우선순위

• CPU 스케줄링(CPU scheduling) : 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 방법을 의미함
• 입출력 집중 프로세스(I/O bound process) : 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스(입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 됨)
• CPU 집중 프로세스(CPU bound process) : 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스(CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무르게 됨)
• 운영체제는 상황에 맞게, 그리고 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해 프로세스마다 우선순위(priority)를 부여함
• 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정함
• 프로세스는 우선순위를 가지고 있고, 이는 PCB에 명시됨
• 유닉스, 리눅스, macOS 등의 유닉스 체계 운영체제에서는 "ps -el" 명령을 통해 프로세스 우선순위를 직접 확인할 수 있으며, 윈도우에서는 "Process Explorer"라는 소프트웨어를 통해 우선순위 확인과 변경이 가능함

 

1-2) 스케줄링 큐

• 운영체제는 효율적인 스케줄링을 위해 스케줄링 큐(scheduling queue)를 사용함
• 운영체제는 메모리로 적재되고 싶은(새로 생성하는) 프로세스들을 큐에 삽입하여 줄을 세우고, CPU를 이용하고 싶은 프로세스들 또한 큐에 삽입하여 줄을 세우고, 특정 입출력장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세움(즉, 운영체제가 관리하는 대부분의 자원은 큐로 관리됨)
• 준비 큐(ready queue) : CPU를 이용하기 위해 프로세스들이 기다리는 줄
• 대기 큐(waiting queue) : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

 

1-3) 선점형과 비선점형 스케줄링

• 선점형 스케줄링(preemptive scheduling) : 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식을 의미함(즉, 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식임)
• 비선점형 스케줄링(non-preemptive scheduling) : 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미함(즉, 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식임)

구분	선점형 스케줄링	비선점형 스케줄링
장점	어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있음	문맥 교환의 횟수가 선점형 스케줄링보다 적기 때문에 문맥 교환에서 발생하는 오버헤드는 선점형 스케줄링보다 적음
단점	문맥 교환 과정에서 오버헤드가 발생할 수 있음	하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서도 무작정 기다릴 수 밖에 없음(모든 프로세스가 골고루 자원을 사용할 수 없음)

 

 

2) CPU 스케줄링 알고리즘

2-1) 스케줄링 알고리즘의 종류

• 선입 선처리 스케줄링(FCFS 스케줄링; First Come First Served Scheduling) : CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식(알고리즘은 준비 큐에 삽입된 순서대로 CPU를 할당함)
• 최단 작업 우선 스케줄링(SJF 스케줄링; Shortest Job First Scheduling) : 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는(혹은 CPU를 할당하는) 스케줄링 방식
• 라운드 로빈 스케줄링(round robin scheduling) : 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식(즉, 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링을 의미함)
  • 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미함
• 최소 잔여 시간 우선 스케줄링(SRT 스케줄링; Shortest Remaining Time) : 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식(최소 잔여 시간 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택됨)
• 우선순위 스케줄링(priority scheduling) : 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
  • 단, 우선순위 스케줄링은 근본적인 문제를 내포하고 있는데 바로 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있음(이를 "기아; starvation" 현상이라고 함)
  • 기아 현상을 방지하기 위한 대표적인 기법으로 에이징(aging)이 있는데 이는 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식임(즉, 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법이 에이징임)
• 다단계 큐 스케줄링(multilevel queue scheduling) : 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식(다단계 큐 스케줄링 하에서는 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리함)
• 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling) : 다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있다는 차이점이 있음(즉, 다단계 피드백 큐 스케줄링 알고리즘은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘임)