[운영체제] 스케줄링 알고리즘

비선점형

• FCFS 스케줄링 (First Come First Serve) = FIFO
• SJF 스케줄링
• HRN 스케줄링

선점형

• 라운드 로빈 스케줄링
• SRT 스케줄링
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링

선택 기준

• CPU 사용률
  • 이상적인 수치는 100%
  • 최대한 많이 활용해야 좋음
• 처리량
  • 단위 시간 당 작업을 마친 프로세스의 수
  • 효율성을 중시
• 대기시간
  • 프로세스 생성 후 실행 전까지의 시간
• 응답시간
  • 첫 작업의 첫 출력이 나올 때 까지의 시간 (반응)
• 실행시간
  • 프로세스 작업이 시작한 후 끝날때 까지 걸리는 시간
• 반환 시간
  • 프로세스 실행 전 대기시간부터 종료될 떄 까지 걸리는 시간
• 평균 대기 시간
  • 모든 프로세스의 대기시간의 합 나누기 프로세스의 수

스케줄링 알고리즘

비선점 방식

1. FCFS (Fisrt Come First Serve ) = FIFO
   • 비선점형 방식
   • 하나의 프로세스가 끝나야 다음 프로세스 진행
   • 큐가 하나
   • 모든 프로세스의 우선순위가 동일
   • 효율성이 떨어짐
2. SJF (Shortest Job First)
   • 작업 시간이 가장 짧은 프로세스 먼저 작업
   • 최단 작업 우선 스케줄링
   • 콘보이 효과를 완화 (FCFS의 단점 완화)
   • 작업시간이 긴 프로세스는 계속 뒤로 밀리게 됨 → 공평성 저하 → 아사현상
   • 프로세스 종료 시간을 예측하기 어려움
   → 아사현상 막기 = 에이징(aging)
3. 프로세스가 양보하는 상한성을 정함 (최대 n살까지만 양보)
4. HRN 스케줄링 (Highest Response Ratio Next)
   • 아사현상 해결을 위해 탄생 → 완전 해결은 안됨 (여전히 cpu 시간 짧은게 유리)
   • 최고 응답률 스케줄링
   • 프로세스가 CPU를 받기 위해 기다린 시간과 CPU사용시간을 고려하여 스케줄링
   • 우선순위 = (대기시간 + CPU사용시간) / 대기시간
   • CPU 이용 시간과 반비례 → CPU 이용 시간이 적을수록 순위가 높음
   • 대기 시간과는 비례

선점 방식

1. 라운드 로빈 스케줄링 방식
   • 할당받은 타임슬라이스 동안 작업을 하다가 완료 못하면 맨 뒤로 가서 다시 기다리는 방식
   • 모든 프로세스 작업이 완료 될 때 까지 순환
   • FCFS와 평균 대기 시간이 같다면 이게 오히려 비효율정 → 문맥교환이 FCFS보다 많음
   • 타임슬라이스는 가능한 작게 하나, 너무 작으면 안됨 → 적당한 크기로 결정
   • 평균 대기시간 = ( P1 + P2 + P3 ) / 3
     • P1, P2, P3 = (프로세스 끝난 시간 - 대기시간 - 도착시간)의 값
2. SRT 우선 스케줄링 (Shortest Remaining Time)
   • 남아있는 작업 시간이 가장 적은 프로세스를 선택
   • 남은 프로세스의 남은 작업시간을 주기적으로 계산해야 함
   • 우선순위를 계속 변경하면서 문맥교환이 생김
   • 운영체제가 프로세스 끝날 시간 계산하기 어려움
   • 아사현상이 일어남

우선순위 스케줄링

• 적용
  • SJF : CPU 작업 시간이 적은 것이 높음
  • HRN : 대기시간이 긴, 작업시간이 짧은 것이 높음
  • SRT : 남은 작업 시간이 짧은 것이 높음
• 장점
  • 프로세스 중요도를 기준으로 반영
• 단점
  • 공평성 위배
  • 아사현상 발생
  • 우선순위를 변경하며 오버헤드가 발생 (우선순위 계산, 문맥교환 등)

우선순위 알고리즘 분류

• 고정 우선순위 알고리즘
  • 한번 부여받은 우선순위가 종료될 떄 까지 고정
  • 단순 구현 가능
  • 시시가각 변하는 시스템 상활을 반영하지 못해 효율설 떨어짐
• 변동 우선순위
  • 일정 시간마다 우선순위가 변함
  • 일정 시간마다 우선순위를 새로 계산
  • 구현이 복잡하다
  • 시스템 상황 반영하여 요율적 운영 가능

우선순위 알고리즘 종류

• 다단계 큐 스케줄링
  • MLQ : Multi-Level Queue
  • 고정형 우선순위
  • 준비 큐를 여러개 사용
  • 우선순위에 따라 우선순위 큐에 삽입
  • 상단 큐의 작업이 끝나야 다음 큐 작업 시작
• 다단계 피드백 큐
  • MLFQ : Multi Level Feedback Queue
  • 프로세스가 CPU에 한번 할당받아지면 우선순위가 낮아짐
  • → 우선순위가 낮은 프로세스의 실행 연기 완화
  • 우선순위가 낮아져도 커널 프로세스가 일반 프로세스에 삽입되지 않음
  • 우선순위에 따라 타임 슬라이스 크기가 다름 (우선순위와 타임슬라이스 반비례)→ 우선순위가 낮으면 CPU를 잘 못얻으니, 그만큼 더 오래 작업할 수 있도록
  • → 낮을수록 크게 가짐. 마지막 큐는 무한대 타임 슬라이스를 가짐
  • 마지막 큐는 FCFS 방식
  • → 더 내려갈 큐가 없어서