Algorithm

Recursion(재귀)

• 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다.

• 재귀함수 : 재귀적으로 정의된 함수

• 재귀함수는 콜스택이라는 메모리 가득차게 되는 경우 자동으로 종료된다.

• 기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건

  • 기저 조건이 반드시 있어야 정상적으로 수행할 수 있다.

• 재귀함수는 함수를 호출할 때마다 Call Stack이라는 메모리 공간에 호출정보가 저장된다.
  → 재귀함수는 Loop문보다 더 많은 메모리 공간을 차지한다.

Call Stack(= Stack)

• 함수가 호출되면서 올라가는 메모리 영역

• 함수가 종료되면 콜스택에서 제거된다.

• FILO(First-In Last-Out)

재귀함수를 사용하는 이유

• Loop를 대신한다기 보다는 더 복잡한 문제를 쉽게 해결하기 위해 사용된다.
  ex) Factorial

재귀함수를 쉽게 작성하는 방법

• 재귀함수 내에서 자기 자신을 호출할 때 해당 함수가 벌써 구현이 되어있다고 가정한다.

5! = 5 * 4 * 3 * 2 * 1
5 * factorial(4)
4! = 4 * 3 * 2 * 1
4 * factorial(3)

→ factorial(number) = number * factorial(number - 1)

OS

CPU Scheduling Algorithm

SJF(Shortest Job First)

• Burst Time이 짧은 작업부터 CPU를 할당한다.

문제점

• 어떤 프로세스가 얼마나 실행될지 예측하기 힘들다.
  → 예측하는 것이 거의 불가능하다.

• Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있다.
  → Burst Time이 긴 프로세스는 Burst Time이 짧은 프로세스에게 계속해서 우선순위가 밀린다.
  ⇒ 사용되지 않는다.

RR(Round Robin)

• 하나의 프로세스에게 일정 시간만 CPU를 할당하고 할당된 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하는 방식
  → 강제로 CPU를 뺏긴 프로세스는 Queue의 가장 마지막으로 밀려난다.

• Time Slice(=Time Quantum) : 프로세스에게 할당하는 일정 시간
  

• Time Slice에 따라서 RR의 성능이 좌지우지된다.

  • Time Slice를 작게 만드는 경우 Context Switching이 빈번하게 발생된다.
    → Context Switching이 빈번하게 발생함에 따라 성능이 떨어진다.

  • Time Slice가 큰 경우 FIFO와 동일하게 동작한다.

• Time Slice 예시

  • Window Time Slice : 20ms

  • Unix Time Slice : 100ms

단점

• Context Switching이 존재한다.
  → 평균 대기시간이 FIFO와 동일하다면 FIFO가 더 성능이 좋다.

MLFQ(Multi Level Feedback Queue)

• RR의 업그레이드 버전

• 주로 사용되는 CPU 스케줄링 알고리즘

• CPU Bound Process : CPU를 할당받은 시간을 대부분 CPU 연산을 수행하는 프로세스

  • CPU 사용률과 처리량이 중요

• I/O Bound Process : 대부분의 시간을 I/O 작업에 수행하고 적은 시간만 CPU 연산을 하는 프로세스
  - 응답시간이 중요
  

• MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 Time Slice를 사용한다.

• CPU Bound Process에게는 CPU 사용률을 높이기 위해 Time Slice를 높게 할당한다.

• I/O Bound Process에게는 I/O 사용률을 높이기 위해 Time Slice를 낮게 할당한다.

OS는 어떻게 CPU Bound Process와 I/O Bound Process를 구분할까?

• CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하는 경우 CPU 사용률이 낮음
  → I/O Bound Process일 확률이 높음

• CPU를 사용하는 프로세스가 실행하다가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황인 경우 CPU 사용률이 높음
  → CPU Bound Process일 확률이 높음

구현 방법

• 우선순위를 갖는 큐를 여러개 준비한다.

• 우선순위가 높으면 Time Slice가 작다.

• 우선순위가 낮아질수록 Time Slice가 커진다.