CPU 스케줄링

★ 프로세스 우선순위

• 우선순위 : 우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스
• 대표적으로 입출력 작업이 많은 프로세스가 있음
• 대부분 프로세스들은 CPU와 입출력장치를 모두 사용하므로 실행 대기 실행 대기 상태를 반복하며 실행
• 입출력 집중 프로세스(I/O bound process) : 입출력 작업이 많은 프로세스, 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무름
• CPU 집중 프로세스(CPU bound process) : CPU 작업이 많은 프로세스, 대기 상태보다는 실행 상태에 더 많이 머무름
• 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU 자원을 요구한다면, 대기 상태가 더 많은 입출력 집중 프로세스를 빨리 실행시키고, 입출력 작업을 완료하기 전까지 CPU 집중 프로세스가 CPU를 사용할 수 있도록 할당하는 것이 효율적!
• 이처럼 각각의 상황에 맞게 CPU를 배분하는 것이 중요하고, 이러한 일을 해주는게 운영체제!
• PCB에 우선순위를 명시하고 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행됨

 

 

★ 스케줄링 큐

• PCB에 우선순위가 적혀있지만, 운영체제가 일일이 모든 프로세스의 PCB를 찾는건 비효율적!
  -> 프로세스들을 줄 세워서 관리 : 스케줄링 큐
  * 큐는 자료 구조 관점에서 FIFO이지만, 스케줄링에서 큐는 무조건 선입선출일 필요는 없음!
• 준비 큐 : CPU를 이용하고 싶은 프로세스들이 서는 줄
• 대기 큐 : 입출력 장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
• 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 우선순위가 높은 프로세스를 먼저 실행
• 대기 상태에 있는 프로세스들은 같은 장치를 요구한 프로세스끼리 같은 대기 큐에서 기다림
  ex) 프린터 대기 큐, 하드 디스크 대기 큐
• 입출력이 완료되어 완료 인터럽트가 발생하면 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거, 해당 PCB는 준비 큐로 이동

 

 

★ 선점형과 비선점형 스케줄링

• 선점형 스케줄링(preemptive scheduling) : 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식
• 비선점형 스케줄링(non-preemptive scheduling) : 하나의 프로세스가 자원을 독점할 수 있는 스케줄링 방식
• 선점형 스케줄링은 자원 독점을 막고 골고루 자원을 배분할 수 있으나, 문맥 교환 과정에서 오버헤드가 발생할 수 있음
• 비선점형 스케줄링은 선점형 스케줄링보다 문맥 교환 횟수가 적으므로 오버헤드는 적게 발생하지만, 하나의 프로세스가 자원을 사용하고 있다면 다른 프로세스들은 무조건 기다려야하고, 골고루 자원을 사용할 수 없음

 

 

★ 스케줄링 알고리즘의 종류

⭐︎ 선입 선처리 스케줄링(FCFS 스케줄링)

• 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
• 호위 효과 : 실행시간이 긴 프로세스가 먼저 도착하면 실행시간이 짧은 프로세스들은 긴 시간을 기다릴 수밖에 없는 현상

⭐︎ 최단 작업 우선 스케줄링(SFJ 스케줄링)

• 호위 효과를 방지하기 위해, 실행 시간이 가장 짧은 프로세스부터 실행하는 비선점형 스케줄링 방식

⭐︎ 라운드 로빈 스케줄링

• 선입 선처리 스케줄링 + 타임 슬라이스
• 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가면 CPU를 이용하는 선점형 스케줄링
• 타임 슬라이스가 지나치게 크면 선입 선처리 스케줄링처럼 호위 효과가 생길 수 있고, 타임 슬라이스가 지나치게 작으면 문맥 교환이 너무 자주 발생해 비효율적

⭐︎ 최소 잔여 시간 우선 스케줄링(SRT 스케줄링)

• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스는 남아있는 작업 시간이 가장 적은 프로세스가 선택되는 선점형 스케줄링

⭐︎ 우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식
  * 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링됨
• 기아 현상 : 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속 연기되는 현상
• 에이징 기법 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

⭐︎ 다단계 큐 스케줄링

• 우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 방식
• 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해지고, 큐별로 타임 슬라이스를 여러 개 지정하거나 다른 스케줄링 알고리즘을 사용할 수 있음
• 프로세스들이 큐 사이를 이동할 수 없으므로 기아 현상이 발생할 수 있음

⭐︎ 다단계 피드백 큐 스케줄링

• 다단계 큐 스케줄링의 발전된 형태로, 프로세스들이 큐 사이를 이동할 수 있는 스케줄링 방식
• 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고, 타임 슬라이드 동안 실행이 끝나지 않는다면 우선순위를 점차 낮추며 시간 할당량을 크게 설정하는 방법
• 프로세스들이 큐 사이를 이동할 수 있으므로 CPU를 오래 사용하는 프로세스는 자연스레 우선순위가 낮아지고, 에이징 기법을 사용해서 우선순위를 높일 수도 있음

⭐︎ HRN 스케줄링

• SJF의 약점이었던 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법
• 서비스 받을 시간이 분모에 있으므로 짧은 작업이 우선순위가 높아지는 요인이 되고 대기시간이 분자에 있으므로 긴 작업도 대기시간이 큰 경우에는 우선순위가 높아짐

대기시간 + 서비스 받을 시간 / 서비스 받을 시간