[ 운영체제 ] 스케줄링

1.3 스케줄링

멀티 프로세스 환경에서는 여러 프로세스가 모두 실행되어야 하지만, CPU자원은 한정적이다.

그래서 스케줄링을 통해 모든 프로세스를 공평하게 실행해 한정된 자원을 효율적으로 활용하는 것이 OS의 주요 목적이다.

 

 

1.3.1 스케줄링의 목적

스케줄링의 주요 목적은 멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행하는 것

 

💡  스케줄링의 목적 5가지

• 공평성
  특정 프로세스가 실행되지 않는 경우가 없도록 모든 프로세스가 공평하게 실행되어야 한다.
  
  
• 효율성
  자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 스케줄링해야 한다.
  
  
• 안정성
  높은 우선순위의 프로세스를 먼저 처리하도록 스케줄링한다.
  
  
• 반응 시간 보장
  일정 시간 내에 응답할 수 있도록 스케줄링한다. 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으로 볼 수 있다.
  
  
• 무한 연기 방지
  특정 프로세스에 대한 처리가 무한히 연기되지 않도록 스케줄링한다.

 

1.3.2 스케줄링의 단계

💡  스케줄링의 단계

• 장기 스케줄링(잡 스케줄링, 승인 스케줄링)
  준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절한다.
  
  
• 중기 스케줄링
  메모리에 로드된 프로세스 수를 동적으로 조절한다.
  메모리에 프로세스가 많이 로드되면 스왑 아웃해서 일부 프로세스를 통째로 저장한다.
  
  
• 단기 스케줄링(CPU 스케줄링)
  준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘으로 결정한다.
  즉, 어떤 프로세스를 디스패치할지 결정하는 스케줄링

 

 

☝🏻 스케줄러 관점에서의 프로세스 스케줄링

 

 

1. 스케줄러가 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에 디스패치 -> 이때 스케줄링 알고리즘 사용
2. CPU에서 프로세스를 실행
   A  프로세스 수행이 완료되는 프로세스를 종료
   B  일정 시간을 초과하면 인터럽트 발생 -> 준비 큐로 들어가 준비 상태가 됨
   C  입출력 요청이 들어오면 인터럽트 발생 -> 프로세스는 대기 큐로 들어가 대기 상태가 됨 -> 입출력이 완료되면 준비큐로 들어감
3. fork() 호출시에 자식 프로세스 생성 -> 자식 프로세스는 준비 큐로 들어감

 

⏬  스왑 아웃, 스왑 인, 스와핑

스왑 아웃

메모리 공간보다 많은 프로세스가 로드되는 경우 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장 공간으로 옮겨 저장하는 것
"책상이 좁아서 당장 읽지 않는 책을 서랍에 넣는 것"

 

스왑 인

스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 통때로 다시 메모리에 로드하는 것

"서랍에 넣어뒀던 책이 필요할 때 다시 책상으로 가져오는 것"

 

스와핑

스왑 아웃과 스왑 인처럼 프로세스를 통째로 메모리 영역과 저장 공간으로 옮기는 것

"서랍에 책을 넣고 빼는 과정"

 

1.3.3 스케줄링 알고리즘

CPU 스케줄러(단기 스케줄러)가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는 데 사용

 

💡  스케줄링 기준

• CPU 사용률 : CPU를 놀리지 않고 사용하는지
• 처리량 : 단위 시간당 실행한 프로세스 수
• 응답 시간 : 프로세스가 요청이 발생했을 때 응답까지 걸리는 시간
• 반환 시간 : 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간
• 대기 시간 : 프로세스가 대기 큐에서 대기하는 시간의 총합

 

비 선점형 스케줄링

실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미

 

💡  비 선점형 스케줄링에 해당하는 알고리즘

• FCFS(First Come First Served)
  준비 큐에 먼저 들어온 프로세스가 우선순위를 가진다. 먼저 들어온게 먼저 실행!
  
  
• SJF(Shortest Job First)
  실행 시간이 짧은 프로세스가 우선순위를 가진다.
  평균 대기 시간이 가장 짧지만, 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아상태가 될 수 있다.
  
  
• HRRN(Highest Response Ratio Next)
  CPU 처리 기간과 해당 프로세스의 대기 시간을 동시에 고려해 선정한다. SJF의 단점을 고려해 만든 알고리즘이다.
  

☝🏻 기아상태란? 우선순위가 높은 프로세스에 밀려 순위가 낮은 특정 프로세스가 계속 실행되지 못하는 것을 말한다.

 

 

 

선점형 스케줄링

스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있음을 의미한다.

 

💡  선점형 스케줄링에 해당하는 알고리즘

• RR(Round Robin)
  비 선점형과 달리 우선순위가 없다.
  모든 프로세스를 순서대로 일정 시간 동안 실행하고, 일정 시간을 초과하면 다른 프로세스를 실행한다.
  * 일정 시간은 '시간 단위'를 의미하며 타임 퀀텀, 타임 슬라이스라고도 한다.
  프로세스를 반복 수행하기 때문에 콘텍스트 스위칭이 빈번하게 일어나 오버헤드가 많이 발생하지만 응답 속도가 빠르다.
• SRTF(Shortest Remaining Time First)
  준비 큐에서 대기 시간이 가장 짧게 남은 프로세스가 우선 순위를 가진다.
  예를 들어 A프로세스가 실행 중에 대기 시간이 더 짧은 B프로세스가 들어오면 B프로세스가 CPU를 점유한다.
  평균 대기시간이 짧다.
  대기 시간이 긴 프로세스는 기아 상태가 될 수 있다.
  
  
• 멀티 레벨(multi level)
  준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다.
  분리한 큐는 각각 우선순위가 있고 각자 다른 스케줄링 알고리즘을 적용한다.
  foreground 큐와 backgroud 큐로 나뉜다.
  foreground는 응답 속도를 중요시, background는 성능을 중요시한다.
  

☝🏻 SJF와 SRTF 모두 실행시간이 짧은 프로세스가 우선순위를 가지지만
SJF는 프로세스 실행 중간에 다른 프로세스가(실행 시간이 짧아도) CPU를 가로챌 수 없고,
SRTF는 실행 중간에라도 지금 실행중인 프로세스보다 다른 프로세스가 실행 시간이 짧으면 CPU를 더 짧은 프로세스가 점유하도록 한다.