CPU 스케줄링 및 알고리즘

CPU 스케줄링이란?

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것!

프로세스 우선순위

• 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는 CPU작업이 많은 프로세스(=CPU집중 프로세스)의 우선순위보다 높다

스케줄링 큐

• CPU를 사용하고 싶은 프로세스들,메모리에 적재되고 싶은 프로세스들,특정 입출력장치를 사용하고 싶은 프로세스들을 모두 줄을 세우는 것

준비 큐

• CPU를 이용하고 싶은 프로세스들이 서는 줄

대기 큐

• 입출력장치를 이용하기 위해 대기상태에 접어든 프로세스들이 서는 줄
• 같은 장치를 요구한 프로세스들은 같은 큐에서 대기

  우선수위가 낮은 프로세스들이 먼저 큐에 삽입 되어 줄을 섰다 할지라도, 우선수위가 높은 프로세스는 그들보다 먼저 처리될 수 있다

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

선점형 스케줄링

• 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
• 장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다
• 단점 : 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다 (기존의 실행 중인 프로세스 문맥을 백업하고 새로운 프로세스 실행을 위해 문맥을 복구하는 과정)

비선점형 스케줄링

• 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스 기다리기
• 장점 : 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다
• 단점 : 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서도 무작정 기다려야 함
  -> 모든 프로세스가 골고루 자원을 이용하기 어렵다

---

CPU스케줄링의 대표적인 7가지 알고리즘

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

선입 선처리 스케줄링

• FCFS ( First Come First Served) 스케줄링
• 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 먼저 CPU를 요청한 프로세스부터 CPU 할당
• 단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 (=호위 효과)

최단 작업 우선 스케줄링

• SJF(Shortest Job First) 스케줄링
• 호위 효과를 방지하려면?
• CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
• CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식

라운드 로빈 스케줄링

• RR(Round Robin) 스케줄링
• 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
• 타임 슬라이스(Time Slice) : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
  • 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되, 정해진 시간만큼만 이용
  • 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥교환)
    

    타임 슬라이스의 중요성

    타임 슬라이스가 커진다면,
    선입 선처리 스케줄링(FCFS)의 문제점인 호위 효과(프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용)가 생길 수 있고,
    타임 슬라이스가 지나치게 작으면,
    문맥 교환에 발생하는 오버헤드 때문에 CPU의 부담이 가는 우려가 있다

최소 잔여 시간 우선 스케줄링

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

우선순위 스케줄링

• Priority Scheduling
• 프로세스들에게 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 최단 작업 우선 스케줄링, 최소 잔여 시스템 스케줄링 < 우선순위 스케줄링
• 문제점
  • 우선순위가 계속 높은 프로세스만 실행이 되어서 기아 현상(starvation)이 발생한다
  • 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입이 되었음에도 불구하고 실행이 연기 된다
• 해결책
  - 에이징 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  - 대기 중인 프로세스의 우선수위를 마치 나이 먹듯 점차 증가시키는 방법(우선순위가 낮아도 언젠가는 우선순위가 높아진다)

다단계 큐 스케줄링

• Multilevel queue 스케줄링
• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어 있으면, 그 다음 우선순위 큐에 있는 프로세스 처리
• 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다
• 하지만 프로세스들이 큐 사이를 이동할 수 없어서, 우선순위가 낮은 프로세스는 계속 연기될 여지가 있다
  -> 기아현상 재발 가능

다단계 피드백 큐 스케줄링

• Multilevel feedback queue 스케줄링
• 다단계 큐 스케줄링의 발전된 형태
• 다단계 큐 스케줄링에서는 기본적으로 큐간의 이동 불가
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
  - 타임 슬라이스 동안 실행을 다 못 끝내겠다면, 일단 낮은 우선수위로 보낸다고 이해하자
• 자연스럽게 CPU집중 프로세스의 우선순위는 상대적으로 낮아지고, 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐
• 에이징 기법을 적용하여 기아 현상을 예방할 수 있다