혼자 공부하는 컴퓨터 구조 + 운영체제 Section 11. CPU 스케줄링

강의 링크

CPU 스케줄링 개요

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

프로세스 우선순위

• 빨리 처리해야 하는 프로세스가 존재 (=프로세스마다 우선순위가 다름)
  • e.g. 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는 CPU 작업이 많은 프로세스(=CPU 집중 프로세스)의 우선순위보다 높다
• PCB에 프로세스 우선순위 작성되어 있음
  • e.g. ps -el (Linux) 명령어로 우선순위 확인 가능
  • BUT 운영체제가 모든 PCB를 일일이 확인하는 것은 비효율적

스케줄링 큐

• CPU를 쓰고 싶은 프로세스, 하드 디스크를 쓰고 싶은 프로세스, 프린터를 쓰고 싶은 프로세스 등
• 스케줄링에서의 큐는 반드시 선입선출 방식일 필요는 없음
  • 같은 큐 내에서도 우선순위 별로 처리

• 대기 큐
  • 같은 장치를 요구한 프로세스들은 같은 큐에서 대기
  • e.g. 프린터 대기 큐, CD-ROM 대기 큐, 하드 디스크 대기 큐, ...

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

• 선점형 스케줄링 (preemptive scheduling)
  • 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 우선순위가 높은 다른 프로세스에 할당
  • 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있음 (+)
  • 문맥 교환에서의 오버헤드가 발생 (-)
• 비선점형 스케줄링 (non-preemptive scheduling)
  • 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 우선순위가 높더라도 기다려야 함
  • 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적음 (+)
  • 모든 프로세스가 골고루 자원을 이용하기는 어려움 (-)

CPU 스케줄링 알고리즘

선입 선처리 스케줄링

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

최단 작업 우선 스케줄링

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

라운드 로빈 스케줄링

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

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

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

우선순위 스케줄링

• 프로세스들에 우선순위를 부여, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 ⊂ 우선순위 스케줄링
• 근본적인 문제점: 기아(starvation) 현상
  • 우선순위 높은 프로세스만 주구장창 실행
  • 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기
• 방지 기법: 에이징(aging)
  • 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  • 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
    • 우선순위가 낮아도 언젠가는 우선순위가 높아진다

다단계 큐 스케줄링

• multilevel queue
• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리

다단계 피드백 큐 스케줄링

• multilevel feedback queue
• 다단계 큐 스케줄링의 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
  • 다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동 불가
    • 우선순위가 낮은 프로세스는 계속해서 실행 연기 우려
    • 기아 현상 발생 가능
• 타임 슬라이스 동안 실행이 끝나지 않는다면 낮은 우선순위 큐로 이동
• 자연스럽게 CPU 집중 프로세스의 우선 순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐
• 에이징 기법 적용 가능

• 즉 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식
• CPU 스케줄링 방식으로 알려져 있음