공부하는 개발 블로그

◆ 32비트 주소 체계 -> 2^32가지의 서로 다른 메모리 주소.

메모리 주소: 바이트 단위로 부여 -> 2^32 바이트의 메모리 공간에 서로 다른 주소를 할당

◆ 4KB(= 2^12 byte)를 하나로 묶음 : page

한 page내에서 주소를 구별하기 위해서는 12bit가 필요. => 32비트 중 하위 12비트는 내부 주소

7.1 주소 바인딩

◆ 논리적 주소(logical address=가상 주소=virtual address): 프로세스의 독자적인 주소공간.

◆ 물리적 주소(physical address): 물리 메모리에 실제 올라가는 위치. 낮은 영역 - 운영체제. 높은 영역 - 사용자 프로세스

◆ 주소 바인딩(address binding): 논리주소를 물리적 메모리 주소로 연결하는 작업

1) 컴파일 타임 바인딩: 컴파일 시점에 물리 메모리의 어느 곳에 위치할지 결정. 비현실적. 잘 사용 X

2) 로드 타임 바인딩: 프로그램이 시작될때 결정. loader에 의해 결정. 컴파일러가 재배치 가능한 코드(reloca-table code)를 생성한 경우만 가능

loader: 사용자프로그램을 메모리에 적재시키는 프로그램.

3) 실행 시간 바인딩(execution time binding, run tmie binding): 프로그램을 실행한 뒤에도 프로그램이 위치한 물리적 메몰 ㅣ상의 주소가 변경될 수 있는 바인딩 방식. CPU가 주소를 참조할때마다 주소 매핑 테이블을 확인. 하드웨어적 지원이 필요(base register, limit register, MMU)

MMU(Memory Management Unit)의 작동 원리

논리주소 = offset from 메모리 시작 주소

논리주소 + 재배치 레지스터(relocation register, 기준 레지스터) -> 물리 주소

프로세스마다 고유한 주소고간을 가지고 있으므로, 같은 논리 주소라도 현재 CPU에서 실행되는 프로세스에 따라 실제 물리 주소는 다름.

MMU는 context swtich 때마다 재배치 레지스터(relocation register)를 프로세스에 알맞게 설정한다.

다중 프로그래밍 환경의 경우, 물리 메모리에 여러 프로세스가 동시에 존재한다. => 프로세스의 메모리 영역을 넘는 곳을 접근할 수 있다. => limit register(한계 레지스터)를 통해 자신의 메모리 영역을 넘는지 확인.

정리

1) CPU가 프로세스의 논리 주소값이 한계 레지스터 값보다 작은지 확인한다.

2) 작다면 논리 주소 + 재배치 레지스터 -> 물리 주소를 구한다.

3) 작지 않다면, 트랩(SW 인터럽트)을 발생시켜 프로세스를 강제종료한다.

7.2 메모리 관리 관련 용어

1) 동적 로딩: 프로세스의 주소공간 전체를 메모리에 올리지 않고 필요할 때마다 루틴 단위로 적재하는 방식. 운영체제의 도움 없이 프로그램 자ㅔ에서 구현 가능. 운영체제가 라이브러리를 통해 지원할 수도 있음.

2) 동적 연결: 컴파일을 통해 생성된 object file과 라이브러리 파일을 연결하는 것을, 프로그램 실행 직전까지 지연시키는 것. 라이브러리 호출시 stub*을 통해 해당 라이브러리가 메모리에 이미 존재하는지 살펴본다. 존재하지 않으면 디스크에서 동적 라이브러리 파일을 찾아 메모리에 적재한 후 수행한다. 여러 프로그램이 공통으로 사용하는 라이브러리를 한 번만 적재하므로 효율적. 운영체제의 지원이 필요하다.

*stub: 동적 연결을 위해서 실행 파일의 라이브러리 호출 부분에 라이브러리 루틴을 찾기 위해 존재하는 작은 코드.

3) 중첩(overlays)

프로세스의 주소 공간을 분할하여 실제 필요한 부분만 적재하는 기법.

동적 로딩과 비슷하나 목적이 다름.

중첩: 프로그램의 크기가 너무 커서 하나의 프로세스조차 메모리에 올리지 못해서 사용

동적 로딩: 다중 프로그래밍 환경에서 메모리 이용률을 향상시키기 위해 그때그때 필요한 부분만 올림.

4) 스왑핑(swapping)

메모리에 올라온 프로세스의 주소 공간 전체를 디스크의 스왑 영역에 일시적으로 내려 놓는 것.

swap area(= 백킹 스토어(backing store): 디스크의 파일 시스템과 별도로 존재하는 일정 영역. 프로세스가 수행중일 때 일시적으로 저장하는 공간. 다수의 사용자 프로세스를 담을 수 있을정도로 충분히 커야함. 일정 접근 속도가 보장되어야함. 특정한 이유로 프로셋를 잠시 내려놓는 것.

swap in: 메모리로 올리기

swap out: 메모리에서 내리기

swapper라고 불리는 중기 스케줄러가 수행.

swapping을 통해 메모리 위의 프로세스 수를 조절할 수 있음. -> 메모리 위의 프로세스에게 충분한 메모리 공간 제공

컴파일 타임 바인딩과 로드 타임 바인딩의 경우 원래의 자리로 돌아가야함.

실행 시간 바인딩의 경우 아무 고간이나 가능.

swapping에 소요되는 시간은 디스크 탐색 시간(seek time)이나 회전 지연 시간(rotational latency)보다는 디스크 섹터에서 실제 데이터를 읽고 쓰는 전송 시간(transfer time)이 대부분.

7.3 물리적 메모리의 할당 방식

운영체제 상주 영역: 인터럽트 벡터 존재. 낮은 주소

사용자 프로세스 영역: 높은 주소

사용자 프로세스 영역의 관리 방법

1) 연속 할당: 물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스

분할 방법에 따라

(1)고정 분할 방식

물리 메모리를 영구적 분할로 나누고 각 분할에 하나의 프로세스 적재.

분할의 크기는 모두 같을수도, 다를수도

=> 동시에 올릴 수 있는 프로그램의 수, 수행가능한 프로그램의크기 제한.

외부조각(external fragmenation)*, 내부 조각(internal fragmentation)* 발생

(2)가변 분할 방식

프로그램의 크기를 고려하여 메모리 할당. -> 내부조각 발생 X.

하지만 프로그램이 종료되면 중간에 빈 공간이 발생 -> 외부조각 발생할 수 있음.

동적 메모리 할당 문제(dynamic storage-allocation problem): 프로세스를 메모리에 올릴 때 물리 메모리의 어느 공간에 올릴 것인가?

-1) 최초 적합(first-fit): 들어갈 수 있는 공간 중 가장 앞 주소. 시간측면에서 효율적.

-2) 최적 적합(best-fit): 들어갈 수 있는 가장 작은 가용 공간. 가용공간이 크기 순으로 정렬되지 않은 경우 탐색의 오버헤드. 하지만 작은 외부조각으로 효율적.

-3) 최악 적합(worst-fit): 들어갈 수 있는 가장 큰 가용 공간. 최적 적합과 같이 탐색의 오버헤드. 큰 프로그램이 들어갈 수 있는 공간 소진.

=> 최초/최적 적합 주로 사용

컴팩션(compaction): 사용중인 메모리 영역을 한쪽으로 몰아서 가용 공간을 크게 만드는 것. 현재 수행중인 프로세스를 많이 옮겨야해서 비용이 많이 든다. 주소가 바뀌므로 실시간 바인딩의 경우만 적용 가능하다.

* ◆ 외부조각(external fragmenation): 프로그램의 크기가 분할보다 커서 못 들어감. -> 버려지는 공간. but 더 작은 프로그램은 실행 가능.

* ◆ 내부 조각(internal fragmentation): 프로그램의 크기가 분할보다 작아서 남음. -> 낭비되는 공간

2) 불연속 할당: 하나의 프로세스를 물리적 메모리의 여러 영역에 분산해 적재. 페이징/세그멘테이션/페이지드 세그멘테이션

7.4 페이징 기법

paging: 프로세스의 주소 공간을 동일한 사이즈의 페이즈 단위로 나누어 물리 메모리를 불연ㅅ옥적으로 저장하는 방식.

프로세스 전체를 올릴 필요가 없으므로 일부는 backing store에 일부는 물리 메모리에 혼재시키는 것이 가능.

물리 메모리를 페이지와 동일한 크기의 frame으로 나눔.  -> 빈 프레임만 있다면 어디든 들어갈 수 있으므로 동적 메모리 할당문제가 발생하지 않음.

페이지마다 논리주소를 물리 주소로 바꾸는 작업이 필요하므로 복잡. : 페이지 테이블.

프로세스가 가질 수 있는 페이지 주소만큼의 엔트리를 갖는다.

논리주소와 물리주소가 같은 크기로 나누어지므로 외부 조각 발생 X. 하지만 프로세스의 크기가 페이지 크기의 배수가 아니므로 내부조각 발생 가능.

1) 주소 변환 기법

페이지 테이블[인덱스] = 기준 주소(base address)

2) 페이지 테이블의 구현

페이지 테이블 기준 레지스터: 페이지 테이블의 위치

페이지 테이블 길이 레지스터: 페이지 테이블의 길이

-> 주소 변환을 위해서는 2번의 메모리 접근이 필요(테이블 위치 확인 + 테이블에서 페이지 주소 확인)

◆ TLB(Translation Look-aside Buffer): 고속 주소 변환용 캐쉬

병렬 탐색*이 가능한 assosciative register 이용.

*병렬 탐색: 한 번에 TLB내의 모든 항목을 동시에 탐색할 수 있는 기능

EAT(Effective memory access time):

메모리에 접근하는 시간을 1, 연관 레지스터에 접근하는 시간 e, 요청된 페이지가 연관 레지스터에 존재할 확률 a:

(1+e)*a + (2+e)(1-a) = 2 + e - a

3) 계층적 페이징

32 bit 컴퓨터 -> 2^32byte(=4GB)의 주소공간을 갖는 프로그램 지원

페이지의 크기가 4KB라면, 4GB/4KB = 1M개의 페이지 테이블 항목 필요.

각 페이지 테이블 항목이 4byte씩 필요하다면 프로세스당 페이지 테이블을 위해 1M * 4byte = 4MB의 크기의 메모리공간이 필요하다.

◆ 2단계 페이지 테이블에서의 비트 구조

최하위 12 비트: 페이지 내에서의 offset

내부 페이지 테이블 자체도 하나의 프레임에 들어가있으므로 4KB이다.

페이지 테이블의 항목의 크기가 4byte이므로 4KB/4B = 1K개의 항목을 갖게 된다.

=> 중간 10 bit: 두번째 페이지 테이블에서의 인덱스를 위한 비트

=> 32-12-10=10bit: 첫번째 페이지 테이블에서의 인덱스를 위한 비트

EAT:

4단계 페이지 테이블에서 메모리 접근시간이 100ns, TLB 접근 시간이 20ns, 페이지 주소 변환 정보가 TLB에 존재할 확률 98%

0.98* (100+20) + 0.02*(100*5 + 20)  = 128 ns

5번의 메모리 접근: 5*100 ns 보다 훨씬 적음.

4) 역페이지 테이블

물리적 메모리의 페이지 프레임 하나당 하나의 항목을 두는 방식.

물리적 주소에 대한 페이지 테이블. 시스템 전체에 페이지 테이블 하나.

각 엔트리는 프로세스 번호, 논리 페이지 번호를 담음.

요청된 주소가 물리 메모리에 존재하는지 전체적으로 탐색해야하므로 비효율적 -> 연관 레지스터를 통해 병렬 탐색 수행.

5) 공유 페이지

공유 코드를 담은 페이지.

공유 코드(=재진입코드, 순수 코드): 여러 프로세스에서 공통으로 사용될 수 있도록 작성된 코드. read-only. 모든 프로세스에서 동일한 논리 주소를 가져야한다.

<-> 사유 페이지(private page)

6) 메모리 보호

보호 비트(protection bit): 읽기/쓰기/읽기전용

유효-무효 비트(valid-invalid bit): valid이면 물리 프레임에 존재. 무효인 경우 스왑 영역에 존재

7.5 세그멘테이션

의미단위로 나누어서 적재 -> 크기가 균일 X

논리적 주소: <세그먼트 번호, 오프셋> 형태

세그먼트 테이블의 각 항목에는 기준점과 한계점 존재. 크기가 다 다르기 때문.

세그먼트 테이블 기준 레지스터(Segment Table Base Register : STBR)

세그먼트 테이블 길이 레지스터(Segment Table Length Register : STLR): 프로세스의 세그먼트 개수

1) 세그먼트 주소가 세그먼트 테이블의 길이보다 작은가?

2) 작으면 한계점과 오프셋 비교

3) 크다면 예외상황 발생

보호비트, 유효비트 존재.

공유 세그먼트 존재.

장점: 페이징에 비해 공유와 보안 측면에서 효율적.

단점: 크기가 일정하지 않으므로 외부조각, 동적 메모리 할당 문제 발생.

7.6 페이지드 세그멘테이션

세그먼트를 동일한 크기의 페이지로 나눔.

외부의 세그멘트 테이블 + 내부의 페이지 테이블 이용.

각 entry는 segment | page index | offset 의 구조로 이루어져있다.

segment에는 page table의 주소가 들어있다.

CPU 스케줄
선점형 : CPU를 빼앗길 수 있다
비선점형 : CPU를 빼앗기지 않는다.
1)FCFS(First Come First Served)
프로세스가 하나씩 끝나므로 평균 대기시간/소요시간은 짧음.
프로세스별로 CPU 버스트/ I/O버스트 시간이 다른 경우 프로세스마다 편차가 심함.
대표적 단점
convoy effect(콘보이 현상): CPU 버스트가 짧은 프로세스가 나중에 도착해서 오랜 시간을 기다려야하는 것.
2.SJF(Shortest-Job First) : CPU 버스트가 짧은 순. 평균 대기시간이 가장 짧음(선점형/비선점형 중 비선점형이 더 짧음)
SRTF(shorted Remaining Time First): 도중에 CPU 버스트가 더 짧은 프로세스가 오면 CPU를 빼앗아서 할당함.
기아(starvation) 현상: CPU 버스트가 짧은 프로세스가 계속 도착하면, CPU 버스트가 긴 프로세스는 계속 처리되지 못함.
CPU 버스트 시간은 실제로 알 수 없으므로, 예측.
T_n+1 = alhpa * t_n + (1-alpha)*T_n
T_n: 예측시간, t_n: 실제 CPU 버스트 시간

3) 우선순위 스케줄링
aging(노화): 대기 시간이 길어지면 우선순위를 조금씩 높임.

4) 라운드 로빈
할당시간이 너무 긺: FCFS와 차이가 없음
할당시간이 너무 짧음: context switch 오버헤드가 크다.
-> 수십 ms: 대화형 프로세스의 대기시간이 너무 길지 않을 정도.
여러 이질적인 프로세스를 처리할때 유용
SJF보다 평균 대기시간은 길지만 응답시간은 짧음.
할당시간 초과: 타이머 인터럽트를 통해 CPU회수
중간 산출물이 없으므로 평균 대기시간/소요시간은 길지만, 응답시간은 짧음.


5) 멀티레벨 큐
준비큐를 여러개로 분할하여 관리하는 스케줄링 기법
성격이 다른 프로세스를 관리하기 위함.
전위 큐 : 빠른 응답이 필요한 대화형 프로세스. 라운드 로빈
후위 큐: 응답 속도가 주요하지 않은 계산 프로세스. FCFS

어떤 큐를 먼저 사용할것인가?
고정 우선순위 방식 : 전위 큐 > 후위 큐
타임 슬라이스 : 전위 큐 80%, 후위 큐 20%. 기아 현상 해결

6) 멀티레벨 피드백 큐
멀티레벨 큐 + 하나의 프로세스가 다른 큐로 이동 가능.
노화(aging) 등 구현 가능

7) 다중처리기 스케줄링(multi-processor scheduling)
CPU가 여러 개인 환경
-1) 대칭형 다중처리: 각 CPU가 알아서 스케줄링 결정
-2) 비대칭형 다중처리 : 하나의 CPU가 스케줄링 담당.

8) 실시간 스케줄링
경성 실시간 시스템(hard real-time system) : 정해진 시간 내에 완료되야하는 시스템
연성 실시간 시스템(soft real-time system) : 데드라인이 존재하지만 지키지 않는다고 위험 상황이 발생하지 않는 시스템
EDF(Earliest Deadline First): 데드라인이 얼마 남지 않은 요청 먼저
연성 실시간 + 일반 작업의 경우: 데드라인이 존재하는 프로세스에 우선순위 할당

5.스케줄링 알고리즘의 평가
큐잉 모델: 확률 분포를 통해 프로세스의 도착률과 CPU의 처리율을 바탕으로 CPU의 처리량(throughput). 프로세스의 평균 대기 시간 계산.
시뮬레이션
구현 및 실측
트레이스(trace): 실제 시스템에서 추출한 CPU 입력값. 몇 초에 어떤 프로세스가 도착하고 CPU 버스트 시간이 얼마이다.

경우의 수 계산하기
1. 완전탐색을 설계
  1) 모든 선택지를 포함
  2) 두 개 이상의 선택지에 포함되지 않음
2. 이전 조각에서 결정한 것들에 대한 입력을 없애거나 줄임. 남아 있는 조각들을 고르는 경우의 수만 반환
3. 메모이제이션

5.1 프로세스의 개념

★ 프로세스 : 수행중인 프로그램. 디스크에 실행 파일로 존재하던 프로그램이 메모리에 올라가서 수행되는 것

◆ 문맥(context): 프로세스의 주소공간(코드, 데이터, 스택 상태)를 비롯해 레지스터에 어떤 값을 가지고 있었는지, 시스템 콜 등을 통해 커널에서 수행한 일의 상태, 그 프로세스에 관해 커널이 관리하고 있는 각종 정보(PCB)

1) 하드웨어 문맥 :  CPU의 수행상태. 프로그램 카운터, 레지스터값.

2) 프로세스의 주소 공간코드, 데이터, 스택으로 구성되는 자신만의 주소 공간

3) 커널 상의 문맥 : 운영체제가 프로세스를 관리하기 위한 자료구조 (PCB, 커널 스택)





5.2 프로세스의 상태

1) 실행(running): 프로세스가 CPU를 보유하고 기계어 명령을 실행하는 상태.  CPU는 하나이므로 여러 프로세스가 동시에 실행된다고 해도 실제 실행 상태의 프로세스는 유일

2) 준비(ready): CPU만 보유하면 당장 명령을 실행할 수 있지만 CPU를 할당 받지 못한 상태.

3) 봉쇄(blocked, wait, sleep): CPU를 할당 받아도 명령을 실행할 수 없는 상태.

이외의 일시적 상태

시작(new) : 자료 구조는 생성되었지만 메모리 획득을 승인받지 못한 상태

완료(terminated): 프로세스가 종료되었으나 프로세스와 관련된 자료구조를 완전히 정리하지 못한 상태



◆ 문맥 교환(context switch): 수행중이던 프로세스의 문맥을 저장하고 새로운 프로세스의 문맥을 세팅하는 과정.

CPU  디스패치: 준비 상태의 프로세스들 중에서 CPU를 할당 받을 프로세스를 선택하고 실제로 CPU의 제어권을 넘겨 받는 과정



★

5.3 프로세스 제어 블록(PCB)

운영체제가 시스템 내의 프로세스들을 관리하기 위해 프로세스당 유지하는 정보들을 담는 커널 내의 자료구조

구성 요소:

- 프로세스의 상태

- program counter(CPU 수행 관련 하드웨어 값)

- CPU 레지스터(CPU 수행 관련 하드웨어 값)

- CPU 스케줄링 정보

- 메모리 관리 정보(code, data, stack의 위치 정보)

- 자원 사용 정보

-입출력 상태정보



★

5.4 문맥 교환

하나의 사용자 프로세스로부터 다른 사용자 프로세스로 CPU의 제어권이 이양되는 과정.

원래  CPU를 보유하던 프로세스는 context를 자신의 PCB에 저장. 새롭게 CPU를 할당 받을 프로세스는 자신의 context를 하드웨엉로 복원.

시스템 콜이나 인터럽트로 커널 모드로 넘어가는 것은 해당 X. 이 경우에도 문맥의 일부를 PCB에 저장하긴 하나 다른 사용자 프로세스로 변환되는 것이 아니기 때문.

문맥 교환에 소요되는 시간은 오버헤드로 작용. -> 따라서, 시분할 시스템에서 타이머의 CPU 할당 시간을 적절히 조절하는 것이 중요. 너무 짧으면, 문맥 교환 오버헤드가 큼. 너무 길면, 시분할의 의미가 퇴색



5.5 프로세스 스케줄링을 위한 큐

1) 작업 큐(job queue): 시스템 내의 모든 프로세스를 관리하기 위한 큐. 프로세스의 상태와 무관하게 모든 프로세스가 속함. 작업 큐에 있다고 메모리 할당 받은 것은 아님

2) 준비 큐: CPU를 할당 대기.

3) 장치 큐: 장치마다 서비스를 대기하는 큐. 자원마다 존재. 여기에 속한 프로세스는 봉쇄상태.

큐는 프로세스의 PCB를 연결리스트로 연결한 형태

큐헤더 - 큐의 가장 앞 부분



5.6 스케줄러

어떤 프로세스에게 자원을 할당할지 결정하는 운영체제 커널의 모듈

1) 장기 스케줄러(=작업 스케줄러. job scheduler) : 어떤 프로세스를 준비 큐에 삽입할지 결정 - 프로세스의 메모리 할당하는 문제에 관여. 시작 상태의 프로세스 중 어떤 프로세스를 준비큐에 넣을지 결정. 속도가 느려도 됨. 메모리에 동시에 올라가는 프로세스의 수 조절.(시작 상태의 프로세스에 메모리를 할당할지 결정하므로) 하지만, 현대의 시분할 시스템은 장기 스케줄러 사용 안함. 바로 준비 큐에 넣음.

2) 단기 스케줄러(=CPU 스케줄러) : 준비 상태의 프로세스 중 어떤 프로세스를 다음 번에 실행 상태로 만들 것인가 결정.== 준비 큐의 프로세스 중 어떤 프로세스에게 CPU를 할당할 것인가. 시분할 시스템에서 타이머 이터럽트시 단기 스케줄러 호출,. 빈번하게 호출되므로 빨라야함.

3) 중기 스케줄러: 현대의 시분할 시스템에서 이용. 너무 많은 프로세스가 메모리에 적재되어 CPU 수행에 당장 필요한 프로세스의 주소 공간도 올려두기 어려울 때, 메모리에 있는 프로세스 중 일부를 통째로 디스크에 저장.(스왑 아웃: swap out). 0순위: 봉쇄 상태의 프로렛 -> 준비큐로 이동하는 프로세스

프로세스의 상태 : 중지 상태(suspended) - 외부적인 이유로 프로세스가 정지된 상태(중지 준비 상태. 중지 봉쇄상태)

5.7 프로세스의 생성
자식 프로세스는 부모 프로세스의 주소공간을 복사하여 시작
unix의 fork()
pid 제외하고 모든 것이 똑같음. fork()시 원본은 양수, 복사본은 0 return
프로세스 종료 :
1) 자발적 종료 - exit() 시스템 콜
2) 비자발적 종료 -자식의 프로세스를 부모가 강제 종료 : abort()
자원의 한계치를 넘는 자원 요구/ 더 이상 작업이 필요 없는 경우 / 부모 프로세스의 종료

5.8 프로세스 간의 협력
원칙적으로 다른 프로세스의 메모리 공간 참조 불가.

IPC(Inter-process comunication): 하나의 컴퓨터 안에서 실행 중인 서로 다른 프로세스 간의 통신
1) 메시지 전달(message passing): 공유 변수 X.
commnication link 생성 -> 커널에 시스템 골 방식을 send, receive  요청.
comunication link.는 자동 생성. 하나의 프로세스에게는 - 하나의 링크만 존재.
간접통신: 메일박스/포트로부터 전달받음. 여러 프로세스가 메일박스르 공유하는 경우, 어느 프로세스가 받는가?(P1, P2, P3가 공유할 때 P1이 보냄. 수신자는 P2? p3?)
-> 해결책: 둘만 사용하는 링크 만들기/임의로 수신자 지정 / receive를 각 시점에서 한 프로세스만 가능하도록

2) 공유 메모리
시스템 콜을 통해 본인의 주소 공간 일부 공유
동일한 물리적 메모리에 매핑/

2) 공유 메모리(shared memory) : 공유 변수 O.

1. 완전탐색 방법을 생각한다

2. 전체 답이 아니라 앞으로 남은 부분문제에 대한 답을 반환하도록 수정한다.

3. 이전에 구한 답에서 필요한 정보만 남긴다. 입력을 최대한 줄여서 중복을 늘린다.(메모이제이션을 적용했을 때 효율 증가)

4. 메모이제이션