[운영체제] 8. 스케줄링 알고리즘
1. 스케줄링 알고리즘의 선택 기준
1) 스케줄링 알고리즘 종류
비선점형 알고리즘
• FCFS (First Come First Served) 스케줄링
• SJF (Shortest Job First) 스케줄링
• HRN (Highest Response Ratio Next) 스케줄링
선점형 알고리즘
• 라운드 로빈 (Round Robin) 스케줄링
• SRT (Shortest Remaining Time) 스케줄링
• 다단계 큐 (Multi-Level Queue) 스케줄링
• 다단계 피드백 큐 (Multi-Level Feedback Queue) 스케줄링
비선점형 및 선점형 가능
• 우선순위 (Priority) 스케줄링
2) 스케줄링 알고리즘의 평가 기준
CPU 사용률
• 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
• 이상적인 수치는 100%이지만, 실제로는 90%에도 못 미침
처리량
• 단위 시간당 완료된 프로세스 수
• 값이 클수록 좋은 알고리즘
대기 시간
• 프로세스가 작업을 요청한 후 실제 실행이 시작될 때까지 기다린 시간
• 값이 짧을수록 좋음
응답 시간
• 프로세스 시작 후 첫 번째 출력(반응)이 발생하기까지 걸리는 시간
• 값이 짧을수록 좋음
반환 시간
• 프로세스가 종료되어 자원을 모두 반환하는 데 걸리는 시간
• 반환 시간 = 대기 시간 + 실행 시간
2. 스케줄링 알고리즘 상세 설명
1) FCFS (First Come First Served) 스케줄링
• 도착 순서대로 CPU를 할당하는 비선점형 방식
• 한 번 실행되면 프로세스가 끝날 때까지 실행됨
• 모든 프로세스가 동일한 우선순위를 가짐
• 단점: 긴 작업이 먼저 실행되면 짧은 작업의 대기 시간이 길어짐
• 문제: 입출력 작업을 요청할 경우 CPU가 쉬게 되어 비효율적
2) SJF (Shortest Job First) 스케줄링
• 실행 시간이 가장 짧은 프로세스부터 CPU를 할당하는 비선점형 방식
• 장점: 평균 대기 시간을 최소화
• 단점: 실행 시간이 긴 프로세스는 계속 뒤로 밀릴 수 있음 (기아 현상 발생)
• 해결책: 에이징(aging) 기법 적용
3) HRN (Highest Response Ratio Next) 스케줄링
• SJF의 기아 현상을 해결한 비선점형 알고리즘
• 우선순위 = (대기 시간 + 실행 시간) / 실행 시간
• 장점: 대기 시간이 긴 프로세스의 우선순위를 높여 기아 현상을 완화
• 단점: 공평성이 떨어져 많이 사용되지 않음
4) 라운드 로빈 (Round Robin) 스케줄링
• 프로세스가 일정한 시간(타임 슬라이스) 동안 CPU를 사용 후 대기 큐로 이동하는 선점형 방식
• 장점: 공평하고 기아 현상이 없음
• 단점: 타임 슬라이스가 짧으면 문맥 교환 비용이 증가
• 비교: FCFS와 평균 대기 시간이 같다면 FCFS보다 비효율적 (문맥 교환 추가됨)
5) SRT (Shortest Remaining Time) 스케줄링
• 현재 실행 중인 프로세스보다 실행 시간이 짧은 새로운 프로세스가 도착하면 교체하는 선점형 방식
• 장점: 평균 대기 시간을 최소화
• 단점: 실행 시간 예측이 어렵고, 긴 프로세스는 계속 대기할 가능성 있음 (기아 현상 발생 가능)
• 현실에서 거의 사용되지 않음
6) 우선순위 (Priority) 스케줄링
• 프로세스의 중요도에 따라 우선순위를 부여하는 방식
• 방식: 비선점형 또는 선점형 가능
• 장점: 높은 우선순위 프로세스를 먼저 실행 가능
• 단점: 낮은 우선순위 프로세스가 무기한 대기할 가능성 있음 (기아 현상 발생)
• 해결책: 에이징 기법 사용
7) 다단계 큐 (Multi-Level Queue) 스케줄링
• 프로세스를 여러 우선순위 레벨로 구분하여 실행하는 방식
• 특징: 각 레벨은 독립적인 스케줄링 알고리즘 사용
• 단점: 높은 우선순위의 프로세스가 계속 도착하면 낮은 우선순위 프로세스는 실행 기회가 적음 (기아 현상 발생 가능)
• 활용 사례: 실시간 시스템에서 많이 사용됨
8) 다단계 피드백 큐 (Multi-Level Feedback Queue) 스케줄링
• 다단계 큐에서 프로세스가 다른 큐로 이동할 수 있도록 설계된 방식
• 특징: CPU를 할당받을 때마다 우선순위를 낮추는 방식으로 동작
• 장점: 기아 현상이 발생하지 않음
• 활용: 대부분의 현대 운영체제에서 사용됨
3. 인터럽트 처리
1) 인터럽트 (Interrupt) 개념
• 하드웨어에서 발생하는 신호에 의해 프로그램 실행을 중단하고 즉시 처리해야 하는 이벤트
종류:
• 트랩 (Trap): 프로세스 실행 중 발생하는 동기적 인터럽트 (예: 0으로 나누기 오류)
• 비동기적 인터럽트: 외부 이벤트로 인해 발생 (예: 키보드 입력, 마우스 이동)
2) 인터럽트 처리 방식
• 폴링 (Polling): CPU가 주기적으로 장치 상태를 확인하여 인터럽트 발생 여부 확인 (비효율적)
• 인터럽트 방식: 이벤트 발생 시 CPU에 신호를 보내서 처리하는 방식 (효율적)
이 내용은 휴넷사회복지평생교육원의 운영체제 강의를 듣고 정리한 것입니다.