[OS] 스케줄링 알고리즘, 인터럽트
스케줄링 알고리즘
다중 프로그래밍을 가능하게 하는 운영 체제의 스케줄링 기법은 여러가지 알고리즘으로 구현될 수 있다.
비선점 프로세스 스케줄링
FCFS (= First Come First Served Scheduling, 선입 선처리 알고리즘)
- 단순히 준비 큐에 삽입되는 순서대로 프로세스를 처리한다.
- 프로세스들이 기다리는 시간이 매우 길어질 수 있다. (convoy effect)
SJF (= Shortest Job First Scheduling)
- 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당한다.
- 평균 대기시간을 최소화하는 것을 최적으로 둔다.
- 요구 시간이 짧은 프로세스가 항상 우선시되므로, 기아 상태(starvation)가 발생할 수 있다.
- 선점형으로 구현될 수도 있다. (aging 기법)
- aging : 기다린 시간이 긴 프로세스에 카운트를 사용해 우선순위를 높여 처리하는 기법
선점 프로세스 스케줄링
Round robin
- 시분할 시스템을 위해 설계되었다.
- 단위 시간(타임 슬라이스)동안 돌아가며 CPU를 사용하게 하는 선점형 스케줄링 방식이다.
- 타임 슬라이스의 시간 단위는 10 ms ~ 100 ms 정도로, 시간 단위동안 수행된 프로세스는 준비 큐의 끝으로 밀려나게 된다.
- 타임슬라이스가 커지면 FCFS와 같아지고, 작아지면 문맥 전환(Context Switching)이 자주 일어나 Overhead가 증가한다.
SRT(=shortest remaining time)
- SJF 스케줄링을 비선점에서 선점 형태로 수정한 스케줄링 알고리즘
- 현재 작업 중인 프로세스를 중단시키고 새로 들어온 프로세스의 처리를 시작하는 방식이다.
- 정해진 타임 슬라이스만큼 CPU를 사용하되, 다음 프로세스로는 잔여 작업 시간이 가장 짧은 프로세스가 선택된다.
- SJF와 동일하게, starvation 문제가 발생한다.
- 문맥 교환을 위한 오버헤드가 발생한다.
우선순위 스케줄링
프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.
- Starvation이 발생할 수 있다.
- 우선순위가 자주 바뀌면 Overhead가 발생할 수 있다.
Multilevel Queue
- 커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘
- 프로세스 유형별로 우선순위를 구분해 실행할 수 있다.
- 큐별로 타임 슬라이스를 여러 개 지정하거나, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.
Multilevel Feedback Queue
- 다단계 큐 스케줄링에서 한 단계 발전된 방식이다.
- 다단계 큐 스케줄링에서는 프로세스가 하나의 큐에 영구적으로 할당되지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아탈 수 있다.
- 작업들이 서로 다른 유형의 작업들로 분류될 경우 사용된다.
인터럽트
개념
CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치에 예외상황이 발생하여 처리가 필요할 경우에 CPU에게 알려 처리할 수 있도록 하는 것을 말한다. 이때 실행 중인 프로세스를 대기(Waiting/Ready)상태로 변경한다.
동기적 / 비동기적 인터럽트
- 동기적 인터럽트
- = 사용자 인터럽트
- 실행 중인 명령어로 발생
- 비동기적 인터럽트
- 하드디스크 읽기 오류, 메모리 불량 - 하드웨어 오류와 사용자가 작동하는 키보드 인터럽트, 마우스 인터럽트 등이 있다.
처리 과정
- 인터럽트가 발생하면 현재 실행중인 프로세스는 일시정지되며, 재시작하기 위해 상태 정보를 PCB(Process Control Block)에 임시 저장한다.
- ISR(Interrupt Service Routine)이 실행되고, 인터럽트 처리 순서가 이에 의해 결정된다.
- 먼저 처리할 인터럽트가 결정되면 인터럽트 벡터에 등록된 인터럽트 핸들러 (해당 이벤트를 처리할 함수의 시작 주소) 실행
- 핸들러가 인터럽트 처리를 마치면, 인터럽트 발생 시 저장해둔 PC를 복구해 이전에 수행중이던 위치로 돌아가 실행된다.
인터럽트와 이중 모드
이중 모드는 운영 체제(의 자원을) 보호하기 위한 기법으로, 운영체제가 커널 모드와 사용자 모드를 전환하며 일 처리를 하는 것이다.
운영체제가 실행될 때, 그리고 인터럽트가 발생할 때 커널 모드가 실행된다. 외에 사용자 프로그램이 실행될 때는 유저 모드로 실행된다.
Leave a comment