2024 운영체제 정리 - 4. CPU Scheduling

 

 

 

2024 운영체제 정리 - 4. CPU Scheduling  

 

 

 

 

• 1. 운영체제란
• 2. Process & Thread
• 3. IPC
• 4. CPU Scheduling  
• 5. Synchronization
• 6. Virtual Memory 

 

 

---

 

 

 

 

Process Status 

 

• New
• Ready 
• Running
• Waiting
• Terminated 

 

 

Scheduling Queue 

 

• ​프로세스들의 프로세스 제어 블록(PCB)이 링크드 리스트 형태로 연결
•  리스트의 첫 번째와 마지막 PCB를 가리키는 포인터를 포함

 

• Job Queue : 시스템 상에 있는 모든 프로세스들 
• Ready Queue : memory에 올라와 있으면서 CPU에 할당되기를 기다리는 프로세스들의 집합 
• Device Queue (Wait Queue) : 입출력 장치에서 처리되기를 기다리는 프로세스들의 집합
  • 각 입출력 장치들은 자신만의 Device Queue를 가지고 있다 

 

 

 

 

 

• 입출력 작업이 많은 프로세스의 우선순위는 CPU 작업이 많은 프로세스의 우선순위보다 높다.
  • 입출력 작업이 많은 입출력 집중 프로세스는 대기 상태에 많이 머물기 때문에 CPU 자원을 사용하는 빈도가 낮기 때문에 우선순위를 높이면 입출력 장치를 끊임없이 작동시킬 수 있다.

 

 

 

스케줄러의 종류 

 

 

• 장기 스케줄러 : Job Scheduler
  • New -> Ready 
  • 많은 프로세스 중에서 어떤 것을 메모리에 올릴지 (Ready Queue) 하드디스크에 올릴지 결정 
  • 메모리와 디스크 사이의 스케줄링 담당 
• 중기 스케줄러 : Swapper
  • Ready -> Terminated  
  • 메모리에 적재된 프로세스의 수를 조절함
  • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
• 단기 스케줄러 : CPU Scheduler / Dispatcher 
  • Ready → Running → Waiting → Ready
  • Ready Queue에 있는 프로세스를 CPU에 할당함 (=Dispatching)
  • CPU와 메모리 사이의 스케줄링 담당 

 

 

Q. 현대 OS에는 단기, 중기, 장기 스케쥴러를 모두 사용하고 있나요?

• 장기 스케줄러 : 사용하지 않는다.
  • 장기 스케줄러는 일괄처리 시스템에서 사용한다. (자원 독점)
  • 현대 운영체제에서는 대부분 시분할 방식인 Round Robin을 사용한다. (자원 독점X)
    • 시분할 방식에서 프로세스는 시작과 동시에 메모리를 할당해 Ready Queue 에 넣는다.
  • 가상 메모리의 사용으로 잘 사용하지 않는다.
• 중기 스케줄러 : 잘 사용하지 않는다
  • 가상메모리를 사용하면 프로세스의 전체가 아닌 일부만 실제 메모리에 올라와도 된다.
  • 따라서 실제 메모리 용량보다 큰 프로그램을 실행 시킬 수 있고 메모리의 크기에 제약이 없어졌다.
• 단기 스케줄러 : 여전히 사용한다.

 

 

따라서 본 포스트에서는 단기 스케줄러, 즉 CPU Scheduler에 대해서 알아본다 

 

 

 

CPU Scheduler

 

 

• CPU Scheduler는 크게 두 가지 분류로 나눌 수 있는데 1) 선점형, 2) 비선점형이 바로 그것이다 
  • 1) 비선점형 
    • CPU를 사용하고 있는 프로세스가 종료될 때까지 다른 프로세스들을 사용할 수 없도록 하는 방식
    • CPU 점유를 빼앗을 수 없는 방식이다.
    • 프로세스가 한번 CPU를 할당 받아 실행하면 실행이 끝날 때 까지 다른 프로세스에게 CPU를 넘겨주지 않는 방식이다.
      
      
  • 2) 선점형 
    • 한 프로세스가 진행되고 있을 때 정해진 시간이 지나면 다른 프로세스가 CPU를 점유할 수 있도록 하는 방식
    • CPU 점유를 빼앗을 수 있는 방식이다  
    • 프로세스 P1이 CPU를 할당받아 실행중일 때 우선순위가 높은 프로세스 P2가 등장하여 CPU를 요청하면 P1의 CPU를 뺏어서 P2에게 할당하는 방식이다.
      

 

 

 

 

• 1) 선입선처리 스케줄링 (FCFS, First Come First Served)
  • 먼저 들어온 프로세스를 먼저 처리한다 
  • 비선점 스케줄링 방식 
  • 단점 
    • 호위 효과 (Convoy Effect): 앞에 실행시간이 긴 프로세스를 실행하게 되면 상대적으로 실행시간이 짧은 프로세스들이 뒤에서 기다려야 함
• 2) 최단 작업 우선 스케줄링 (SJF, Shortest Job First)
  • 위의 문제를 해결하기 위해 실행 시간이 짧은 프로세스 먼저 수행
  • 비선점 스케줄링 방식
  • 단점
    • 기아 현상 발생 : 실행시간이 긴 프로세스는 뒤에 밀리게 됨 
• 3) 라운드 로빈 스케줄링 (RR, Round Robin)
  • FCFS + Time Slice
  • 위의 문제를 해결하기 위해 프로세스들을 정해진 시간 간격으로 잘라 번갈아가면서 수행 
    • 정해진 시간을 모두 사용하고 나서도 프로세스가 완료되지 않으면 큐의 맨 뒤에 삽입
  • 선점 스케줄링 방식 
  • 단점 
    • Time Slice에 따라 수행되는 시간이 달라짐
      • 너무 길면 FCFS와 다를 바 없음 
      • 너무 짧으면 Context Switch로 인한 오버헤드가 오히려 커짐 
• 4) 최단 잔여 시간 우선 스케줄링 (SRTF, Shortest Remaining Time First)
  • SJF + RR 
  • 남은 시간이 가장 짧은 프로세스를 우선적으로 수행
  • 선점 스케줄링 방식  
  • 단점 
    • 기아 현상 발생 
• 5) 우선 순위 스케줄링 (Priority)
  • 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
    
    • 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
  • 선점 스케줄링 방식 
  • 단점 
    • 기아 현상 발생  => 에이징 기법 사용 가능! 
      
      • 에이징 기법이란: 기아 현상을 방지하기 위해 오랫동안 대기한 프로세스의 우선 순위를 점차 높여서 실행될 수 있도록 하는 기법
• 6) 다단계 큐 스케줄링 (MQ, Multilevel Queue)
  • 우선 순위 스케줄링에서 발전된 형식 
  • 우선 순위에 따라 각각의 큐를 나누어, 우선 순위가 높은 큐부터 수행 
    • 우선 순위가 높은 큐가 비었다면, 그 다음 순위의 큐 수행하게 된다 
  • 큐 간 이동이 불가능 하다 
  • 선점 스케줄링 방식 
  • 단점 
    • 기아 효과 발생 : 큐 간 이동이 불가능하기 때문에 
• 7) 다단계 피드백 큐 스케줄링 (MFQ, Multilevel Feedback Queue)
  • 다단계 큐 스케줄링에서 발전된 형식
  • 다단계 큐 스케줄링의 한계를 극복하기 위해, 큐 간 이동을 가능하게 하여 오랫동안 대기한 프로세스의 우선순위를 높이게 하는 에이징 기법 적용
    • 상대적으로 CPU를 오래 사용하는 프로세스들에 대해선 점점 우선 순위가 낮은 큐에 삽입하도록 함 
  • 선점 스케쥴링 방식 

 

 

 

 

 

 

 

 

 

 

---

Reference

 

 

 

https://hojunking.tistory.com/52

단기 스케줄러, 중기 스케줄러, 단기 스케줄러

 

https://hojunking.tistory.com/54

Process Scheduling Algorithm(프로세스 스케줄링 알고리즘)

 

https://velog.io/@shjung53/os-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%ED%81%90

[os] 스케줄링 큐

 

https://hyunah030.tistory.com/4

[운영체제] CPU 스케줄러 - FCFS, SJF, SRT, RR, Priority Scheduling

https://velog.io/@stthunderl/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-FCFS

스케줄링 알고리즘 / FCFS

https://m.blog.naver.com/jk130694/220691821887