스케줄링 문제
1. 스케줄링에 대해 설명하고 하는 이유에 대해 말해보자.
- 여러 프로세서가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 것을 말하며,
다중 프로그래밍에서 프로세서(CPU)를 할당할 프로세스를 선택할 때 전략이 필요하기 때문
2. 선점 스케줄링과 비선점 스케줄링의 차이점을 말해주세요
선점형 스케줄링은 어떤 프로세스가 CPU를 할당받아 실행되고 있는 중에도 다른 프로세스에 의해 언제든 CPU 점유를 빼앗길 수 있습니다. 이는 문맥교환 오버헤드가 크며, 대화형 시스템 또는 리얼타임 시스템에 적합합니다
반면, 비선점형 스케줄링은 선점형 스케줄링과 반대로 다른 프로세스가 절대 CPU를 빼앗을 수 없습니다. 그렇기 때문에, 프로세스의 실행이 완료되고 CPU를 반납해야지 다음 차례의 프로세스가 실행될 수 있습니다. 문맥교환 오버헤드가 작으며, 일괄처리 시스템에 적합합니다. 단점은 하나의 프로세스가 오랫동안 CPU를 잡는 경우도 있어 처리율이 낮아질 수 있습니다.
3. FCFS 특징과 문제점을 말해주세요
- 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로
- 비 선점형 스케줄링
- 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않는다.
- 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다.
- 문제점 : convoy effect
3-1) convoy effect란?
- 쇼요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 부정적인 현상을 의미한다. 짧은 작업을 먼저 처리하는 방식으로 CPU burst time이 짧은 프로세스에게 CPU를 선할당함.
4. 프로세스의 상태 전이를 설명해 주세요.
- 승인 (Admitted) : 프로세스 생성이 가능하여 승인됨
- 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.
- 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.
- 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.
- 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.
5. 스케줄링은 언제 발생하나요?(스케줄링 시점에서)
A. 크게 4개의 시점에서 발생합니다.
running -> waiting 시점은 보통 I/O 요청이 일어나거나 자식 프로세스가 종료 대기를 할 때 입니다.
running -> ready 시점은 인터럽트(Interrupt) 가 발생했을 때 입니다.
waiting -> ready 시점은 I/O가 완료되었을 때 입니다.
running -> terminate 시점은 프로세스가 완전히 종료되었을 때 입니다.
위에서부터 차례대로 1 ~ 4 의 번호를 매기면 1과 4는 비선점 스케줄링이고 2와 3은 선점 스케줄링 입니다.
6. 선점형 스케줄링 기법은 뭐가 있고 특징들을 말해줄 수 있나
SRT는 Shortest Remaining Time 의 약자로, CPU 점유시간이 가장 낮은 프로세스에 먼저 CPU를 할당하는 기법입니다. 단, 선점형 스케줄링이므로 중요한 프로세스가 있거나 남은 실행 프로세스의 실행 시간이 짧은 경우 현재 실행중인 프로세스를 중단하고 해당 프로세스로 옮겨 실행합니다.
RR(Round Robin) 기법은 프로세스들 사이에 우선순위를 두지 않고 순서대로 일정 시간 단위만큼 할당하는 기법입니다. 문맥 교환의 오버헤드가 큽니다.
MLQ는 Multi-Level Queue의 약자로, 프로세스들을 특정 우선순위 그룹으로 분류한 후 각각의 다른 Ready Queue를 사용하는 기법입니다. 각각의 Ready Queue 내부는 RR 기법을 사용하고, 하위 Ready Queue의 프로세스를 실행하고 있더라도 상위 Ready Queue에 프로세스가 들어오면 상위 프로세스에 CPU를 할당합니다.
7. 비선점형 스케줄링 기법은 뭐가 있고 특징들을 말해줄 수 있는지
A. 비선점형 스케줄링에는 크게 FIFO, SJF, HRN 세 가지 기법이 존재합니다.
FCFS는 First-In-First-Out(큐와 같음) 으로, 선입선출의 방식입니다. 즉, 먼저 Ready Queue에 들어온 프로세스부터 처리합니다. 대신, 비선점형 스케줄링이므로 아무리 작업시간이 길어도 해당 프로세스를 계속 실행해야합니다.
SJF는 Shortest Job First 의 약자로, 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스부터 CPU를 먼저 할당하는 방식입니다. 단점은 실행시간이 긴 프로세스는 짧은 프로세스들에게 밀려 무한히 대기해야 할 수 있습니다
HRN은 Highest Response-Ratio Next 의 약자로, SJF 기법을 보완하고자 대기시간과 실행시간을 이용하여 우선순위를 계산하고, 이러한 우선순위에 맞게 프로세스를 실행하는 기법입니다. 장점은 무한히 대기해야 하는 프로세스의 비율을 낮출 수 있습니다.
8. 스케줄링 알고리즘을 비교하기 위한 여러 기준이 있는데 아는 대로 말해주세요.
- Cpu 이용률, 처리량,총 처리 시간, 대기 시간, 응답 시간이 있는데 이중에서도 cpu 이용률과 처리량을 최대화하고 총 처리시간, 대기시간 응답시간을 최소화 하는 것이 바람직하다. 대부분 평균 측정 시간을 최적화 하려고 한다.
9. 우선순위 스케줄링 같은 경우 주 문제점이 무엇이고 해결방안을 말해주세요.
- 무한 봉쇄 또는 기아상태: 실행 준비는 되어 있으나 cpu를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주 할 수 있다.
- 즉, 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 나온다.
- 해결 방안으로는 노화가 있다. 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
- 다른옵션으로는 라운드 로빈과 결합한다. 시스템이 우선순위가 가장 높은 프로세스를 실행하고, 우선순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용한다.
10. SJF 기법과 SRT 기법의 비교
- SJF는 프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료시 까지 점유 SRT는 가장 짧은 시간이 소요되는 프로세스를 먼저 수행
11. 문맥 교환(文脈交換, context switch)이란 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업을 말한다.
'CS 스터디 > 운영체제' 카테고리의 다른 글
| 2번째 주제 스레드와 프로세스 (0) | 2022.07.03 |
|---|