연습문제

01

시스템 내 전체 프로세스의 수를 조절하는 것으로, 장기 스케줄링 또는 작업 스케줄링이라고 불리는 스케줄링 수준은?
고수준 스케줄링
고수준 스케줄링 단계에서는 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정한다.

02

어떤 프로세스에 CPU를 할당하고 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 스케줄링 수준은?
저수준 스케줄링
고수준 스케줄링과 반대로 가장 작은 단위의 스케줄링
고수준 스케줄링이 전체 손님 수를 조절하는 단계라면, 저수준 스케줄링은 각 손님의 주문과 그에 따른 요리 제공 순서를 미세하게 조절하는 단계

03

어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링은?
선점형 스케줄링
운영체제가 필요하다고 판단하면 실행 상태에 있는 프로세스의 작업을 중단시키고 새로운 작업을 시작할 수 있다. 선점형 스케줄링 방식의 대표적인 예로는 인터럽트 처리를 들 수 있다.

04

현재 입출력을 진행하는 프로세스로, 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 불리는 것은?
전면 프로세스
GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스

05

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링 알고리즘은?
FCFS 스케줄링

First Come First Served 스케줄링
준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링 알고리즘 (선입선출 스케줄링)
테이블이 하나만 있는 레스토랑에 비유할 수 있다.

• 장점: 단순하고 공평
• 단점:
  ☝🏻 콘보이 효과(convoy effect) 또는 호위 효과: 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제. 즉, 컨베이어 벨트에 작업물이 한 줄로 늘어서 있을 때 앞의 작업이 오래 걸려서 뒤의 작업이 지연되는 현상과 같다.
  ✌🏻 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다. 시분할 시스템에서는 입출력을 요청한 프로세스를 대기 상태로 보내어 처리할 수 있지만, 일괄 작업 시스템에서는 프로세스의 상태 변화가 없기 때문에 작업 효율이 떨어진다.

06

준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 스케줄링 알고리즘은?
SJF 스케줄링

Shortest Job First 스케줄링
준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식(최단 작업 우선 스케줄링)
SPF(Shortest Process First) 또는 최단 프로세스 우선 스케줄링 이라고도 함

• 장점: 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아진다. 먼저 도착한 큰 작업으로 인해 작은 작업이 지연되는 FCFS 스케줄링보다 평균 대기 시간이 줄어들어 시스템의 효율성이 높아지는 것
• 단점:
  ☝🏻 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
  현대의 운영체제에서는 프로셋의 작업 길이를 추정하는 것이 어렵기 때문
  ✌🏻 공평하지 못하다.
  프로세스 P2는 P3보다 준비 큐에 먼저 도착하지만 가장 나중에 실행되었다. 만약 프로세스 P3같은 작은 작업이 계속 준비 큐에 들어오면 프로세스 P2의 작업이 계속 연기되는데 이를 아사starvation 현상 또는 무한 봉쇄infinite blocking 현상이라고 한다. 작업 시간이 길다는 이유만으로 계속 뒤로 밀린다면 공평성이 현저히 떨어진다.

07

SJF 스케줄링 알고리즘 단점으로 크기가 큰 작업이 계속 뒤로 밀리는 현상은?
아사 현상

08

아사 현상을 해결하는 방법은
HRN(Highest Response Ratio Next) 스케줄링은 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘, 최고 응답률 우선 스케줄링이라고도 한다.
서비스를 받기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링한다.
프로세스의 우선순위를 결정하는 기준은 아래와 같다.
우선순위 = (대기 시간 + CPU 사용 시간)/ CPU 사용 시간

09

서비스를 받기 위해 대기한 시간과 CPU 사용 시간을 고려하여 우선순위를 정하는 스케줄링 알고리즘은?
HRN 스케줄링

10

프로세스가 할당받은 시간(타임 슬라이스)동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 다음 자기 차례가 올 때까지 기다리는 선점형 스케줄링 알고리즘 중 가장 단순한 것은?
라운드 로빈 방식(Round Robin, RR)
순환 순서 방식으로 번역
FCFS 스케줄링과 유사한데, 차이점은 각 프로세스마다 CPU를 사용할 수 있는 최대 시간, 즉 타임 슬라이스가 있다는 것. 프로세스는 자신에게 주어진 타임 슬라이스 동안만 작업할 수 있으며, 작업이 다 끝나지 않으면 큐의 뒤쪽tail에 다시 삽입된다.
RR 스케줄링은 우선순위가 적용되지 않으 ㄴ가장 단순한 선점형 스케줄링 방식이다.

11

타임 슬라이스의 크기와 문맥 교환의 관계는?
타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요하다.

• 타임 슬라이스가 큰 경우
  : 타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다. 이 경우 FCFS 스케줄링과 다를 게 없는데, 실제로 라운드 로빈 스케줄링에서 타임 슬라이스가 무한대이면 FCFS 스케줄링이 된다. 타임 슬라이스가 1,000밀리초(1초)인 시스템에서 비디오 플레이어와 워드프로세서가 동시에 실행된다고 가정했을 떄, 비디오 플레이어 1초, 워드프로세서 1초씩 두 프로그램이 1초 간격으로 실행되어 비디오가 끊겨 보이고 워드프로세서의 반응 속도가 매우 느릴 것이다.
• 타임 슬라이스가 작은 경우
  : 타임 슬라이스를 1밀리초와 같이 매우 작은 값으로 설정하면 사용자는 여러 프로그램이 동시에 실행되는 것처럼 느낄 것이다. 그러나 타임 슬라이스를 너무 작게 설정하면 시스템의 전반적인 성능이 떨어진다. 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생한다.

12

기본적으로 라운드 로빈 방식을 사용하지만, CPU를 할당받은 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 것을 선택하는 스케줄링 알고리즘은?
SRT(Shortest Remaining Time) 스케줄링
SJF 스케줄링과 라운드 로빈 스케줄링 혼합한 방식(최소 잔류 시간 우선 스케줄링)

13

우선순위에 따라 준비 큐를 여러 개 사용하여 고정형 우선순위를 적용하는 스케줄링 알고리즘은?
다단계 큐(multilevel queue) 스케줄링
프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정된다.

14

우선순위에 따라 준비 큐를 여러 개 사용하며, 프로세스가 CPU를 사용한 후 우선순위가 낮아지는 특징을 가진 스케줄링 알고리즘은?
다단계 피드백 큐(multilevel feedback queue) 스케줄링

15

다단계 피드백 큐 스케줄링에서 마지막 큐에 잇는 프로세스(우선순위가 가장 낮은 프로세스)의 타임 슬라이스 크기는?
무한대

16

다단계 피드백 큐 스케줄링에서 우선순위가 낮아질수록 타임 슬라이스의 크기는 어떻게 변하는가?
프로세스의 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다.

17

다단계 피드백 큐 스케줄링에서 마지막 큐(우선순위가 가장 낮은 큐)는 어떤 스케줄링 알고리즘처럼 작동하는가?
FCFS 스케줄링 알고리즘

심화문제

01

스케줄링의 단계와 그 특징은?
작업 대기 -> 보류 프로세스 -> 활성 프로세스 -> 실행 프로세스 -> 작업 종류 순
그 중간에 보류, 활성화, 대기 또는 타임아웃, 프로세스 선정의 과정이 있음
작업 대기에서 보류 프로세스 과정에선 고수준 스케줄링이 적용되는데, 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정한다. 시스템의 전체 프로세스 수가 결정되며 메인프레임과 같은 큰 시스템에서 규모가 큰 일괄 작업을 처리할 때 사용된다.
보류 프로세스에서 활성 프로세스 과정에선 중간 수준 스케줄링이 적용되는데 시스템의 부하를 조절하려면 중간 수준의 스케줄링을 고려해야 한다.
시스템ㅇ에 과부하가 걸려서 전체 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보낸다. 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화된다.
활성 프로세스에서 실행 프로세스 과정에선 저수준 스케줄링이 적용된다. CPU스케줄러가 필요에 따라 준비 상태에 있는 프로세스를 실행 상태로 옮기기도 하고, 대기 상태로 보내기도 하며, 타임아웃으로 준비상태로 돌려보내기도 한다.

02

스케줄링의 목적
CPU 스케줄링 목적 6가지
1. 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안된다.
2. 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
3. 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
4. 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다. 또한 시스템 자원이 늘어나느 경우 이 혜택이 시스템에 반영되게 해야한다.
5. 다섯째, 반응 시간 보장. 응답이 업는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
6. 여섯째, 무한 연기 방지. 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

03

선점형 스케줄링과 비선점형 스케줄링을 비교하시오

• 선점형 스케줄링 방식은 실행 상태에 있는 작업을 중단시키고 새로운 작업 실행 가능, 비선점형 스케줄링은 실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능
• 선점형은 시분할 방식 스케줄러에서 사용, 비선졈형은 일괄 방식 스케줄러에서 사용
• 장점: 선점형은 프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템이 적합, 비선점형은 CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
• 단점: 선점형은 문맥 교환의 오버헤드가 많고, 비선점형은 기다리는 프로세스가 많아 처리율이 떨어진다.
• 중요도 측면: 선전혐은 중요도가 높↑, 반면 비선점형은 낮↓

04

스케줄링 알고리즘의 선택 기준에 대해 설명하시오

• CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 축정하는 방법. 가장 이상적인 수치는 100%이지만 실제로는 여러가지 이유로 90%에도 미치지 못한다.
• 처리량: 시스템이 정상적으로 작동한다면 일정 시간 후 작업이 끝난다. 처리량은 단위 시간당 작업을 마친 프로세스의 수로, 이 수치가 클수록 좋은 알고리즘이다.
• 대기 시간: 작업을 요청하더라도 실제 작업이 이루어지기 전까지는 대기 시간이 필요하다. 대기 시간은 작업을 요청한 프로세스가 작업을 싲가하기 전까지 대기하는 시간으로 이 시간이 짧을 수록 좋다.
• 응답 시간: 대화형 시스템에서는 사용자의 요구에 얼마만에 반응하는 지가 중요하다. 응답 시간은 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간으로 이 시간 역시 짧을 수록 좋다.
• 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간. 반환 시간 = 대기 시간+ 실행 시간

05

FCFS, SJF, HRN 스케줄링의 특징
⚽통점: 모두 비선점형 스케줄링 방식

• FCFS(First Come First Served)스케줄링: 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식, 선입선출 스케줄링이라고도 함. 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스가 실행할 수 있다. 게다가 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
• SJF(Shortest Job First) 스케줄링: 연습문제 6번참고
• HRN(Highest Response Ratio Next): 연습문제 8번참고

06

라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐 스케줄링의 특징
⚽통점: 모두 선점형 스케줄링 방식

• Round Robin 스케줄링: 한 프로세스가 할당받은 타임 슬라이스 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식. 선점형 알고리즘 중 가장 단순하고 대표적인 방식. 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행. 우선순위가 적용되지 않은 가장 단순한 선점형 스케줄링 방식
• SRT(Shortest Remaining Time) 스케줄링: 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 프로세스를 선택한다. 하지만 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가된다. 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사현상이 일어날 수 있다.
• 다단계 큐(Multilevel Queue) 스케줄링: 우선순위에 따라 준비 큐를 여러개 사용하는 방식. 우선순위는 고정형 우선순위를 사용하며, 상단의 큐에 잇는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다. 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있을뿐더러 우선 순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있따.
• 다단계 피드백 큐 스케줄링은 프로세스가 CPU를 한 번씩 할당받아 실행될 떄마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다. 또한 우선순위에 따라 타임 슬라이스의 크기가 다르다. 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정한다.

07

아사 현상과 에이징에 대해 설명하시오
starvation현상은 작업시간이 길다는 이유로 작업이 계속 연기되는 현상, 이를 완화하기 위해 에이징aging이 있다.
에이징은 프로세스가 양보할 수 있는 상한선을 정하는 방식이다. 즉 프로세스가 자신의 순서를 양보할 떄마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정하는 것이다.

08

타임 슬라이스의 크기를 정하는 것과 시스템 효율성에 대해 설명하시오
연습문제 11번 참고