인프런 워밍업 클럽 - CS Day 6
AlgorithmRecursion(재귀)어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다.재귀함수 : 재귀적으로 정의된 함수재귀함수는 콜스택이라는 메모리 가득차게 되는 경우 자동으로 종료된다.기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건기저 조건이 반드시 있어야 정상적으로 수행할 수 있다.재귀함수는 함수를 호출할 때마다 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) OSCPU Scheduling AlgorithmSJF(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 : 20msUnix 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가 커진다.
