(운영체제) 4 - CPU 스케줄링 연습문제

### 연습문제 ###

1. 시스템 내 전체 프로세스의 수를 조절하는 것으로, 장기 스케줄링 또는 작업 스케줄링이라 불리는 스케줄링은 무엇인가?

고수준 스케줄링

2. 어떤 프로세스에 CPU를 할당하고 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 스케줄링 수준은 무엇인가?

저수준 스케줄링

3. 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링은 무엇인가?

선점형 스케줄링

4. 현재 입출력을 진행하는 프로세스로, 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 불리는 것은 무엇인가?

전면 프로세스

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

FCFS(First Come First Served) 스케줄링

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

SJF(Shortest Job First) 스케줄링

7. SJF 스케줄링 알고리즘의 단점으로 크기가 큰 작업이 계속 뒤로 밀리는 현상을 무엇이라 하는가?

기아, 아사

8. 아사 현상을 해결하는 방법을 설명하시오.

프로세스가 대기한 시간을 우선순위에 반영하여 더 오래 대기한 프로세스가 CPU를 선점할 확률을 높이는 방법이 있다. 이것을 구현한 것이 HRN(High Response Ratio Next) 스케줄링이다.

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

HRN(High Response Ratio Next) 스케줄링

10. 프로세스가 할당받은 시간(타임 슬라이스)동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 다음 자기 차례가 올 때까지 기다리는 선점형 스케줄링 알고리즘 중 가장 단순한 것은 무엇인가?

라운드 로빈(Round Robin) 방식

11. 타임 슬라이스의 크기와 문맥 교환의 관계를 설명하시오.

타임 슬라이스가 작을수록 프로세스 교체가 더 자주 일어나 문맥 교환에 의해 발생하는 오버헤드가 커진다. 그러나 대화형 프로세스 같은 경우 타임 슬라이스가 작아야 반응 시간이 빠르기 때문에 타임 슬라이스를 작게하되 문맥 교환에 따른 오버헤드를 고려하여 적절한 크기를 유지해야한다.

12. 기본적으로 라운드 로빈 방식을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 것을 선택하는 스케줄링 알고리즘은 무엇인가?

SRT(Shortest Remaining Time) 스케줄링

13. 우선순위에 따라 준비 큐를 여러 개 사용하여 고정형 우선순위를 적용하는 스케줄링 알고리즘은 무엇인가?

다단계 큐 스케줄링

14. 우선순위에 따라 준비 큐를 여러 개 사용하며, 프로세스가 CPU를 사용한 후 우선순위가 낮아지는 특징을 가진 스케줄링 알고리즘은 무엇인가?

다단계 피드백 큐 스케줄링

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

책에서는 우선순위가 가장 낮은 준비 큐의 슬라이스는 무한대로 설정하여 FCFS 스케줄링 방식으로 사용한다고 하였다. 백그라운드에서 돌아가는 프로세스의 경우 사용자와 상호작용이 없기 때문에 FCFS 방식으로 일괄처리를 해도 괜찮다고 했다. 그러나 우선 운영체제마다 다르게 구현되었을 것이고 꼭 무한대일 필요는 없는것 같다. 우선순위에 따라 타임 슬라이스를 유연하게 가져가서 시스템 효율성을 높인다는 점이 중요하다.

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

더 커진다. 타임 슬라이스가 커지면 반응 속도가 느려지는데, 우선순위가 낮은 후면 프로세스나 CPU 집중 프로세스의 경우 사용자와 상호작용이 없으므로 타임슬라이스를 크게하여 문맥교환에 따른 오버헤드를 굳이 만들 필요 없다는 이유 때문이다.

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

FCFS(First Come First Served) 스케줄링. 라운드 로빈 방식에서 타임 슬라이스를 무한대로 늘리면 FCFS 알고리즘이 된다.

### 심화문제 ###

1. 스케줄링의 단계와 그 특징을 설명하시오.

고수준 스케줄링 : 시스템이 프로세스를 받아들일지 말지를 결정하여 전체 프로세스 수를 조절하는 스케줄링 레벨

중간수준 스케줄링 : 시스템 과부하가 생기면 준비 상태의 프로세스를 대기 상태로 보내고 다시 여유가 생기면 대기 상태의 프로세스를 준비 상태로 올리는 동작

저수준 스케줄링 : 실제 프로세스를 실행하는 스케줄링이다. 프로세스에 CPU 사용을 할당하고 상태를 제어하는 스케줄링

2. 스케줄링의 목적을 설명하시오.

공평성 : 모든 프로세스에게 공평하게 자원이 돌아가야한다.

확장성 : 새로운 자원이 추가되었을 때 시스템이 그 혜택을 받을 수 있도록 하고 새로운 프로세스가 추가되어도 안정적으로 시스템이 돌아가도록 해야한다.

안정성 : 우선순위에 따라 중요한 프로세스가 먼저 실행되어야한다.

효율성 : 시스템 자원이 놀지 않도록 최대한 사용해야 한다.

반응시간 보장 : 적절한 시간안에 프로세스 요구에 응해야한다.

무한연기 방지 : 특정 프로세스가 너무 오랫동안 자원을 할당받지 못하는 기근 현상이 일어나지 않아야한다.

3. 선점형 스케줄링과 비선점형 스케줄링을 비교하여 설명하시오.

• 선점형 스케줄링

  • CPU가 프로세스에 의해 사용중이더라도 운영체제가 내쫓을 수 있는 스케줄링 방식
  • 빠른 응답시간을 요구하는 시분할 시스템에 적합하다.
  • 문맥 교환에 따른 오버헤드가 발생한다.

• 비선점형 스케줄링

  • CPU가 선점되면 해당 프로세스가 종료되기 전까지 기다려야 하는 스케줄링 방식
  • 문맥 교환에 따른 오버헤드가 적다.
  • 빠른 응답시간을 요구하는 시분할 시스템에는 적합하지 않고 사용자와 상호작용이 없는 후면 프로세스 혹은 배치 시스템에 적합하다.

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

• CPU 사용률

  • 스케줄링의 목적 중 하나인 효율성에 관련된다.
  • CPU 사용 효율을 극대화해야한다.

• 대기 시간

  • 준비 큐 도착 후 실행 시작 전까지 걸리는 시간
  • 대기시간이 짧을수록 효율적인 알고리즘이다.

• 응답 시간

  • 준비 큐 도착 후 첫 응답까지 걸리는 시간
  • 대화형 프로세스, 시분할 프로세스에서 특히 중요하다.

5. FCFS, SJF, HRN 스케줄링의 특징을 설명하시오.

모두 비선점형 알고리즘이다.

FCFS는 도착한 순서대로 무식하게 CPU를 할당하는 방식이다. SJF는 실행 시간이 가장 짧은 프로세스에 우선적으로 CPU를 할당한다. HRN 알고리즘은 SJF에서 나타날 수 있는 실행시간이 긴 프로세스의 기아를 막기 위해 대기시간을 우선순위 결정에서 고려한 알고리즘이다.

6. 라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐 스케줄링의 특징을 설명하시오.

모두 선점형 알고리즘이다.

• 라운드 로빈

  • 단순하게 준비 큐의 가장 앞에 있는 프로세스부터 순서대로 실행한다.
  • 타임슬라이스 시간만큼의 사용이 끝나면 다시 준비큐의 가장 마지막에 삽입된다.

• SRT

  • 남은 시간이 가장 짧은 프로세스에게 CPU를 할당한다.
  • 타임슬라이스 시간만큼의 사용이 끝나면 다시 준비큐의 가장 마지막에 삽입된다.
  • 공평성을 위배한다는 문제점이 있다.

• 다단계 큐

  • 우선순위 레벨별로 준비 큐를 따로 둔다.
  • 우선순위가 높은 큐의 프로세스가 모두 종료되어야 낮은 우선순위의 프로세스들이 CPU를 사용할 수 있다.
  • 우선순위가 낮은 프로세스들의 기아 현상이 발생할 수 있다.

• 다단계 피드백 큐

  • 다단계 큐에서 나타나는 우선순위가 낮은 프로세스의 기아 현상을 방지하기 위해 만들어졌다.
  • CPU 사용이 끝난 프로세스는 우선순위가 낮은 준비 큐에 삽입된다.
  • 우선순위에 따라 타임 슬라이스를 다르게 가져가며 낮은 우선순위 큐 일수록 타임 슬라이스가 크다.

7. 아사 현상과 에이징에 대해 설명하시오.

특정 프로세스가 다른 프로세스에 밀려 CPU를 사용하지 못하고 계속해서 뒤로 밀리는 현상이다. 에이징은 이를 완화하기 위해 대기시간이 긴 프로세스에 우선순위 가중치를 주어 CPU 사용 확률을 높이는 방법이다.

8. 타임 슬라이스의 크기를 정하는 것과 시스템 효율성에 대해 설명하시오.

우선순위별로 타임 슬라이스의 크기를 다르게 하여 시스템 효율성을 높일 수 있다. 커널 프로세스와 같이 중요한 프로세스는 기근이 생기지 않도록 타임 슬라이스 크기를 작게 가져가는 것이 좋다. 또한 대화형 프로세스나 전면 프로세스와 같이 사용자와 상호작용하는 프로세스의 경우 응답시간이 빨라야하므로 타임 슬라이스를 작게 가져가야한다. 그러나 압축과 같은 일괄처리 프로세스, 사용자와 상호작용이 없는 후면 프로세스는 타임 슬라이스의 크기를 크게하여 문맥교환에 따른 오버헤드를 줄이는 것이 시스템 효율성을 높이는 방법이다.