스케줄링 알고리즘
스케줄링 이란?
- 다중 프로그래밍을 가능하게 하는 운영 체제의 동작 기법이다. 운영 체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.
FCFS
• 가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식이다.
• 비선점형(Non-preemptive) 스케줄링이다.
• 작성이 간단하고 이해하기 쉽다.
• 평균 대기 시간(Average Waiting Time)이 길어질 수 있다.
• 응답 시간(Response Time)이 길어질 수 있다.
• 반환시간(Turnaround Time) 면에서는 좋을 수 있다.
• Convoy Effect(호위 효과)가 발생할 수 있다. -> 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 효과
SJF
• 다음 CPU burst time의 길이를 고려해서 스케줄링을 결정하는 알고리즘이다.
• 비선점형과 선점형이 따로 존재한다.
• 비선점형에서는 실행되고 있는 프로세스는 끝까지 실행한다.
• 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 다음 프로세스가 더 빨리 끝날 수 있는 프로세스라면 다음 프로세스를 실행하도록 바꾸게 된다. SRTF(Shortest Remaining Time First)라고도 부른다.
• SJF 스케줄링은 평균 대기 시간을 줄일 수 있다.
• 하지만 다음 프로세스의 CPU burst time을 예측하는 것이 어렵다는 문제가 존재한다.
비선점형 SJF(실행되고 있는 프로세스는 끝까지 실행)
선점형 SJF (실행 중이던 프로세스보다 도착한 프로세스의 남은 시간이 짧으면 해당 프로세스로 전환) – (SRT)
Round Robin
• 각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다.
• 할당 시간 내에 처리를 완료하지 못하면 다음 프로세스로 넘어가므로 선점형 방식이다.
• n개의 프로세스가 있을 때 할당 시간을 q로 설정하면, 어떤 프로세스도 (n-1)q 시간 이상을 기다리지 않아도 된다.
• 응답 시간을 빠르게 할 수 있다는 장점이 있다.
• q가 커진다면 FCFS처럼 작동한다.
• q가 매우 작아지면 process sharing이라고 부른다. 이것은 n개의 프로세스가 프로세서 속도의 1/n 씩으로 작동함을 의미한다.
Priority scheduling
• 각각의 프로세스에 우선순위 넘버가 있다.
• 가장 높은 우선순위의 프로세스에 CPU를 할당한다.
• 선점형과 비선점형이 나뉜다.
• SJF도 Priority 스케줄링이라고 할 수 있다. ( 다음 CPU burst time이 우선순위인 것처럼 작동하므로)
• 기아(Starvation) 문제가 발생할 수 있다. 기아 문제란 낮은 우선순위의 프로세스가 절대 실행되지 않는 문제를 뜻함.
• 기아문제를 해결하기 위해서 노화(aging)를 사용할 수 있다. 시간이 지날수록 프로세스의 우선순위를 높여주는 식.
Multilevel Queue
• 준비 큐가 여러 개의 큐들로 나뉜다.
• 각 큐는 각자의 스케줄링 알고리즘을 가지고 있다.
• 각 큐 사이에서 프로세스들이 이동할 수 없다.
• 일반적으로 Foreground 프로세스들은 Round Robin 방식을 사용하고, Background 프로세스는 FCFS를 사용한다.
• 기아(Starvation) 문제가 발생할 수 있다.
• 보통 CPU 시간의 80%는 Foreground의 RR, 20%는 Background의 FCFS에 할당된다.
Multilebel Feedback Queue
• Multilevel Queue와 비슷하지만, MFQ는 각 큐 간에 프로세스들이 이동할 수 있다.
인터럽트
인터럽트란 ?
- 마이크로프로세서(CPU)가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치에 예외상황이 발생하여 처리가 필요할 경우에 마이크로프로세서에게 알려 처리할 수 있도록 하는 것을 말한다.
동기적 인터럽트,비동기적 인터럽트
- 프로세스가 실행중인 명령어로 인해 발생하는 동기적 인터럽트
o 프로그램상의 문제로 인해
o 작업자가 의도적으로
o 입출력장치 같은 주변장치의 조작에 의한
o 산술연산중 발생 - 실행중인 명령어와 무관하게 발생하는 비동기적 인터럽트
o 하드디스크 읽기 오류
o 메모리 불량과 같은 하드웨어적인 오류
o 사용자가 직접 작동하는 키보드 인터럽트, 마우스 인터럽트
인터럽트 처리 과정
- 인터럽트가 발생하면 현재 실행 중인 프로세스는 일시 정지 상태가 된다.
재시작을 위해 현재 프로세스 관련 정보를 임시로 저장 - 인터럽트 컨트롤러가 실행되어 인터럽트의 처리순서를 결정
-> 여러개의 인터럽트가 동시에 발생했다면 인터럽트의 우선순위를 고려하여 중요한 인터럽트부터 처리하도록 순서를 결정 - 먼저 처리할 인터럽트가 결정되면 인터럽트 벡터에 등록된 '인터럽트 핸들러'가 실행
- 인터럽트 벡터에 연결된 핸들러가 인터럽트 처리를 마치면 일시 정지된 프로세스가 다시 실행되거나 종료된다.
-> 입출력 완료같은 경우이면일시정지된 프로세스가 다시 실행
-> 다른 프로세스가 메모리 영역 침범이나 오류 같은 경우이면 종료
인터럽트와 이중모드
이중모드란 ?
- 운영체제를 보호하기 위한 기법 -> 관리자 모드와 사용자 모드로 나뉜다.
(프로그램에서 소프트웨어 인터럽트를 발생시켜 운영체제에 위임)
- 컴퓨터 부팅 과정 – 관리자 모드
- 애플리케이션 실행 과정 – 관리자 모드
- 애플리케이션 실행중 – 사용자 모드
- 인터럽트 발생 후 처리 과정 – 관리자 모드
(하드웨어 인터럽트라 가정시->사용자가 하드웨어의 자원에 접근하는 것은 매우 위험)- 하드웨어 인터럽트 발생후 CPU로 인터럽트 신호 요청 (사용자 모드)
- CPU에서 모드 플래그를 관리자 모드 값(0)으로 변경
- 해당 하드웨어 인터럽트 서비스 루틴(ISR)으로 이동 (관리자 모드)
- 인터럽트 처리 (관리자 모드)
- 인터럽트 처리 완료 후 CPU의 모드 플래그를 다시 사용자 모드 값(1)으로 변경
- 원래의 애플리 케이션 위치로 복귀 (사용자 모드) -> 상위 5번과정.
- 인터럽트 처리 후 - 사용자 모드
