CS 3주차 발자국

운영체제

가상 메모리

개요

• 프로세스는 운영체제 영역이 어디 있는지, 물리 메모리 크기가 얼마나 큰지 몰라도 됨.

  → 프로그래머는 물리 메모리의 크기와 프로세스가 메모리의 어느 위치에 올라가는지 신경쓰지 않아도 됨.

• 프로세스는 메모리 관리자를 통해서 메모리에 접근

  • 프로세스 입장에서는 물리 메모리에 직접 접근하지 않고 메모리 관리자에게 요청만 하면 됨.

  • 메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결 시켜 줌.

• 가상 메모리의 크기는 이론적으론 무한대지만, 물리 메모리의 크기와, CPU의 bit수에 의해 결정.

  • 32bit CPU인 경우엔 $2^{32}$의 값인 4GB

• 예를 들어, 운영체제와 4GB 프로세스 5개를 실행하기 위해서는 적어도 20GB가 필요.

  • 가상 메모리 시스템은 물리 메모리 내용의 일부를 하드디스크 내 스왑 영역에 옮기고 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 운영체제와 프로세스를 모두 실행 할 수 있음.

• 메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상주소를 물리 주소로 변환.

  → 동적 주소 변환(DAT, Dynamic Address Translation)

• 동족 주소 변환을 거치면 프로세스는 마음대로 사용자의 데이터를 물리 메모리에 배치 할 수 있음.

• 가상 메모리는 운영체제 영역을 제외한 나머지 메모리 영역을 일정한 크기로 나누어서 프로세스에게 할당

  • 가변 분할 방식(세그멘테이션)

  • 고정 분할 방식(페이징)

  • 세그멘테이션-페이징 혼용 기법

• 가상 메모리 시스템에서 가상 주소는 메모리나 스왑영역 중 한 곳에 존재

  • 메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리.

     

세그멘테이션

• 가변 분할 방식을 사용하는 메모리 할당 기법

관점에 따른 메모리

• 세그멘테이션에서 프로그램은 함수나 모듈 등으로 세그먼트를 구성.

• 프로세스 입장에서는 각 영역을 서로 인접한 것 처럼 바라봄.

메모리 처리 방식

• 사용자와 프로세스, CPU가 바라보는 주소는 논리 주소.

• 중간에 메모리 관리자가 물리 주소로 변환을 진행.

• 메모리 관리자는 세그멘테이션 테이블이라는 정보를 갖고 있음.

  • Base Address / Bound Address 정보가 저장하고 이를 이용해 물리 메모리 정보를 계산

  • Bound Address는 세그먼트의 크기를 나타냄

• CPU에서 논리 주소를 전달 해주면 메모리 관리자는 해당 논리 주소가 몇번째 세그먼트인지 파악.

• 메모리 관리자 내에서 Segment Table Base Register를 이용해서 물리 메모리내에 있는 세그멘테이션 테이블을 찾고 세그먼트 번호를 인덱스로 사용하여 Base Address와 Bound Address를 찾음

  • 참고로 컨텍스트 스위칭이 발생하면 운영체제는 메모리 관리자 내의 Segment Table Base Register를 해당 프로세스의 것으로 바꿔주는 작업을 진행.

• 메모리 관리자는 cpu에게서 받은 논리 주소와 Bound Address 크기를 비교.

  • 논리 주소가 Bound Address 보다 작다면 논리 주소와 Base Address를 더해 물리 주소를 계산.

  • 논리 주소가 Bound Address 보다 크다면 메모리를 침범했다 생각하여 에러를 발생.

     

장/단점

• 장점

  • 메모리를 가변적으로 분할 할 수 있음.

  • 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근 보호가 편리

• 단점

  • 외부 단편화 발생

페이징

• 고정 분할 방식.

• 세그멘테이션의 단점은 외부 단편화를 해결하기 위해 고안.

• 메모리를 정해진 크기의 페이지를 나눔

메모리 처리 방식

• 논리 주소 공간

  • 사용자와 프로세스가 바라보는 주소 공간

  • 일정한 크기로 균일하게 나누어짐.

    → 페이지라고 부름

• 물리 주소 공간

  • 실제 메모리에서 사용 되는 주소 공간

  • 페이지의 크기와 동일하게 누님

    → 프레임이라고 부름

주소 변환 방식

• 메모리 관리자는 페이지 테이블을 갖고 있음.

• cpu에서 논리 주소를 전달해 주면 메모리 관리자는 논리 주소가 몇번 페이지인지, 오프셋은 몇인지 계산.

• 메모리 관리자 내의 Page Table Base Register(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리 주소로 변환

• 만약 페이지 테이블에 프레임이 Invalid로 표시되어 있으면 스왑 영역(하드 디스크)에 저장되어 있다는 의미.

페이징과 세그멘테이션의 차이

• 페이지의 크기

  • 세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 갖고 있음

  • 페이징은 모든 페이지 크기가 동일하여 크기를 표현하는 Bound Address가 필요 하지 않음.

• 영역 나누는 방식

  • 세그멘테이션은 논리적인 영역별로 세그먼트를 나눔

    • 힙 영역 / 데이터 영역 / 스택 영역 / 힙 영역

  • 페이징은 크기가 고정되어 있어 논리적인 영역별로 나누지 않고 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없음.

    • 특정 영역만 떼어내어 공유하거나 권한을 부여하는게 어려움.

장/단점

• 장점

  • 모든 페이지는 크기가 같기 때문에 관리가 굉장히 쉬움

• 단점

  • 내부 단편화 발생(메모리 낭비)

• 각 프로세스마다 페이지 테이블을 갖고 있어 프로세스가 많아질수록 페이지 테이블도 많아진다.

  • 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듦.

  • 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장 되어 있어 페이지 테이블 크기가 너무 크면 사용자 영역이 부족해 짐.

  • 페이지 테이블의 크기를 적절하게 유지하는 것이 중요.

페이지드 세그멘테이션

• 세그멘테이션과 페이징을 혼합해 장접을 취한 방식

• 세그멘 테이션의 장점

  • 가변 분할 방식이라 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나누어서 관리.

  • 다른 프로세스와 공유가 쉽고 각 영역에 대한 메모리 접근 보호를 하기가 쉬움.

• 페이징

  • 고정 분할 방식으로 메모리를 효율적으로 관리.

  • 오버헤드가 적음.

메모리 접근 권한

• 메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세가지가 존재.

• 프로세스는 코드, 데이터, 스택, 힙 영역이 있는데 각 영역마다 권한이 존재.

  • 코드영역은 읽기와 실행만 가능

  • 데이터 영역은 읽기 권한이 있고 쓰기 권한은 있거나 없을수도 있다.

  • 스택과 힙 영역은 일기 쓰기 권한이 있음.

• 접근 권한에 대한 검사는 가상 주소에서 물리 주소로 변환될 때마다 발생.

• 권한을 위반한다면 에러를 발생

단점

• 물리 메모리에 접근하기 위해서 메모리에 접근을 두번 진행 해야함

  • 세그먼 테이션 테이블 참조 / 페이지 테이블 참조

  • 현대 운영체제는 페이징과 페이지드 세그먼테이션 기법을 적절히 섞어서 사용

디멘드 페이징

• 메모리 가져오는 방식

• 프로세스를 이루고 있는 코드, 데이터, 힙, 스택 영역과 같은 모듈이 모두 메모리에 올라와 실행 하는것이 아니라 필요한 모듈(일부)만 올라와서 실행됨

• 프로그램이 실행될때 90%의 시간이 10%의 코드에서 보내는 것을 발견.

  → 90:10 법칙

  → 지역성 이론

지역성 이론

• 공간의 지역성

  • 현재 위치와 가까운 데이터에 접근할 확률이 높음

• 시간의 지역성

  • 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음

• 지역성 이론은 조만간 쓰일 데이터를 메모리에 올리고 당분간 쓰이지 않을 데이터는 스왑 영역으로 보내 성능을 향상 시킴

• 디멘드 페이징은 조만간 필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을것 같은 데이터는 스왑영역으로 보내는 정책.

메모리 가져오기 정책

• 스왑 인

  • 스왑 영역에서 물리 메모리로 데이터를 가져 오는 것

• 스왑 아웃

  • 물리 메모리 영역에서 스왑 영역으로 데이터를 보내는 것

• 페이지 테이블의 비트 처리

  • 페이지 테이블의 한 행을 페이지 테이블 엔트리(Page Table Entry, PTE)라고 함

  • 페이징에서 확인한 인덱스와 프레임 뿐만 아니라 다양한 비트들이 존재.

    • 비트 종류

      • 접근 비트

        • 페이지가 메모리에 올라온 후 데이터의 접근이 있었는지 알려주는 비트

        • 작업 진행했으면 1, 그렇지 않으면 0

      • 변경 비트

        • 페이지가 메모리에 올라온 후 데이터의 변경이 있는지 알려주는 비트

        • 쓰기를 했으면 1, 그렇지 않으면 0

      • 유효 비트

        • 페이지가 물리 메모리에 있는지 알려주는 비트

        • 페이지가 스왑영역에 있으면 1, 물리 영역에 있으면 0

      • 읽기/쓰기/실행 비트

        • 권한 비트

        • 해당 메모리에 접근 권한이 있는지 확인하는 비트.

      • 프레임

• 프로세스가 가상메모리에 접근 요청을 할때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾음.

  • 물리 메모리에 없으면 Page Fault 발생

  • Page Fault가 발생하면 보조 저장 장치의 스왑 영역에 접근하고, 프로세스는 대기 상태로 변경

  • 스왑 영역에 있는 데이터가 메모리로 올라가는 작업을 진행하고, 메모리에 올라가면 대기 상태의 프로세스는 다시 실행.

페이지 교체 정책

• 메모리가 꽉 찼을때 스왑 영역으로 보내는 정책 방식.

교체 방식 종류

• 무작위 선택 방식

  • 성능이 좋지 않아 별로 사용되지 않음

• FIFO

  • 메모리에 들어온 가장 오래된 페이지를 교체하는 방식

• Optimum

  • 앞으로 가장 오랫동안 쓰이지 않을 페이지를 교체 하는 방식

  • 이론적으로만 존재하고 구현이 불가능한 이론적인 방식

  • 다른 알고리즘과 성능 비교용으로 사용

• LRU(Least Recently Used)

  • 최근에 가장 사용이 적은 페이지를 선택하는 방법

  • 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다는 결론을 이용

  • Optimum 알고리즘에 근접한 성능

  • 프로그램이 지역성을 띄지 않을땐 성능이 떨어짐

빌레이디의 역설(Belady’s Anomaly)

• Page Fault를 줄이려고 메모리를 늘리고 페이지 수를 늘렸지만, 오히려 Page Fault가 더 많이 발생하는 현상

• FIFO 방식에서만 발생하며 LRU에서는 발생하지 않음.

• LRU가 가장 좋은 방식. 그러나 LRU에는 큰 단점이 있는데 바로 시간을 기록해야 한다는 점.

  • 최근 사용을 적게한 페이지를 알려면 일정 시간동안 사용된 페이지들을 조회해야함. 그래서 시간이 필수적.

  • 하지만 시간 데이터는 비트가 많이 필요하며 시간이 지나면 비트가 초기화 되는 문제가 발생 가능성이 높음.

  • 이를 방지하기 위해 Clock Algorithm 도입 하여 적용

Clock Algorithm

• 접근 비트 하나만 사용

• 일정 시간마다 모든 페이지의 접근 비트를 0으로 초기화

• 페이지가 참조 되었다면 1로 설정

• 페이지를 원형으로 연결

   

• 스왑 영역으로 옮길 페이지를 포인터로 가르키는데 포인터를 클락 핸드라고 함.

• 클락 핸드는 시계 방향으로 동작

• Page Fault가 발생하면 클락 핸드는 현재 참조하고 잇는 접근 비트를 확인하여 값을 변경하고 다음 페이지로 이동.

• 이를 반복하다가 접근 비트가 0인 페이지를 발견 하면 해당 페이지를 스왑 영역으로 보냄.

향상된 시계 알고리즘(Enhanced Clock Algorithm)

• 접근 비트 뿐만 아니라 변경 비트도 확인.

• 스왑 영역으로 보내지는 순서는

  1. 접근비트가 0 변경 비트도 0

  2. 그 다음은 접근 비트가 1 변경 비트가 0

  3. 그 다음은 접근 비트가 1 변경 비트도 1

FIFO를 사용 하는 경우

• 하드웨어적으로 접근 비트를 사용하지 못하는 경우에 사용

• 성능을 높이기 위해 2차 기회 페이지 교체 알고리즘을 고안

• FIFO 방식에서 자주 사용하는 페이지에게는 한번의 기회를 주는 방식

• Page Fault없이 한번에 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장 시켜주는 방식.

성능 순서

LRU > 2차 기회 페이지 교체 알고리즘 > FIFO

스레싱과 워킹셋

스레싱

• CPU 스케쥴링의 목표는 CPU 사용률 향상 이고, CPU 사용률 향상은 동시에 실행사는 프로세스의 수 높이는 것.

• 프로세스 실행 공간인 메모리가 필요한데 모든 프로세스를 담을 수 없어 스왑 영역에 일부 저장.

• 멀티 프로그래밍이 늘어나면 스왑 영역도 많이 필요하여 CPU가 작업하는 시간보다 스왑 작업의 시간이 더 길어져 CPU 사용률이 떨어지는 문제 발생

  → CPU 스케쥴링은 더 많은 프로세스를 실행시키고 다시 문제가 반복되어 오히려 CPU 사용률이 떨어지는 문제 발생

  → 스레싱

• 스레싱의 원인은 물리 메모리의 크기 부족

  • 메모리의 크기를 늘리면 하드웨어적으로 해결 됨

  • 무작정 메모리를 늘린다고 성능이 좋아 지지는 않음

워킹셋

• 프로세스가 실행되면 일정량의 페이지를 할당하고 Page Fault가 발생하면 더 많은 페이지를 할당.

• 반대로 Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비된다고 판단하여 페이지를 회수

• 프로세스가 실행되는 동안 해당 프로세스에 맞는 적절한 페이지 수가 결졍 됨.

• 적절한 페이지수가 결정됐다면 어떤 페이지들을 유지할 것인지 알아야 함

  → 지역성 이론을 따름

• 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 관리

  → 워킹셋

• 워킹셋은 프로세스가 준비 상태에서 실행상태가 되는 컨텍스트 스위칭이 될때마다 사용

입출력 장치

주변장치

• 그래픽 카드, HDD, SSD, 키보드, 마우스 등 다양

내부 구조

• 주변 장치들은 메인보드에 있는 버스로 연결

• 버스는 Address, Data, Control 버스로 이루어져 있음

   

• 하드웨어에 맞게 외부 인터페이스가 존재

• 장치의 상태와 데이터들을 보관하는 레지스터가 존재

• 레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할을 함

  • CPU가 사용하기 위해 메모리로 이동되기도 함

• 주변장치는 캐릭터 디바이스와 블록 디바이스 2가지로 나뉨

• 데이터의 전송 단위가 캐릭터(글자)냐 블록이냐로 나눈 것

• 캐릭터 디바이스

  • 마우스, 키보드, 사운드 카드, 직병렬 포트

  • 데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음

• 블록 디바이스

  • 하드디스크, SSD, 그래픽 카드

  • 데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼

• 여러 주변 장치는 메인보드내 하나의 버스로 연결해서 사용했음

• CPU가 작업을 하다 I/O명령을 만나면 직접 입출력 장치에서 데이터를 가져오는 방식이였음

• 입출력 중에는 다른 작업을 하지 못하여 CPU 사용률이 떨어짐

• 이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러개의 버스가 추가됨

• CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기도 다른 작업을 진행

  • 입출력 제어기는 두개의 채널 시스템 버스와 입출력 버스로 구분

    • 시스템 버스는 고속으로 작동하는 CPU와 메모리가 사용

    • 입출력 버스는 주변 장치가 사용

    • 입출력 버스는 느린 장치와 빠른 장치를 구분하기 위해 고속 입출력 버스와 저속 입출력 버스로 구분됨

• 입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮김. 메모리는 CPU의 명령으로 움직이기 때문에 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요.

• 그래서 입출력 제어기가 CPU의 도움이 필요없도록 DMA(Direct Memory Access) 제어기가 추가 됨.

  • 입출력 제어기는 데이터를 직접 메모리에 저장하거나 가져올 수 있음.

• CPU와 DMA가 사용하는 메모리가 겹치지 않도록 각 메모리 영역을 나누는데 이를 Memory Mapped I/O라고 부름.

   

하드 디스크와 플래시 메모리

하드 디스크

• 스핀들(spindle)이라는 막대와 스핀들에는 플래터(platter)라는 원판들이 붙어 있는 구조

• 플래터는 자기화된 원판으로 이루어져있는데 디스크암(disk arm)이 읽기/쓰기 헤드(read/wirte head)로 플래터의 포면을 읽음

• 플래터는 여러개의 트랙(track)으로 구성되어 있고 표면에 자성이 있기 때문에 표면이 N극을 띄면 0, S극을 띄면 1로 인식

• 헤드가 움직이면 이 헤더들은 여러개의 플래터를 가리키게 되는데 이때 여러 개의 플래터에 있는 같은 트랙의 집합을 실린더(cylinder)라고 함

• 트랙은 다시 여러개의 섹터(sector)로 나누는데 하드디스크의 가장 작은 단위

• 헤드를 실린더의 원하는 위치로 이동하는데 이를 seek라고 함

• 헤드를 실린더로 이동시키는데 걸리는 시간을 Seek Time이라고 함

  • 이때문에 하드 디스크가 느림

     

Flash memory

• 하드 디스크보다 더 많이 사용

• SSD가 대표적

• 전기적으로 읽어 빠르고 조용

• 자성에 안전

• 충격에 강함

• 특정한 지점에 데이터를 썻다면 덮어 씌우기가 불가능

• 특정한 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야 하지만 플래시 디스크는 지우기 가능한 횟수가 정해져있음.

알고리즘

삽입 정렬(Insertion Sort)

• 정렬된 영역과 정렬되지 않는 영역을 나누어서 정렬되지 않은 영역의 데이터를 하나씩 뽑아서 정렬된 영역내 적절한 위치에 삽입하여 정렬하는 알고리즘

• 예시

  [4, 1, 5, 3, 6, 2]
  // 정렬된 영역: [4]
  // 정렬되지 않은 영역 [1, 5, 3, 6, 2]
  
  // 1. 각 영역의 첫번째 인덱스 4와 1을 비교
  // 4가 1보다 크므로 4를 오른쪽 인덱스에 덮어 씌워줌
  [4, 4, 5, 3, 6, 2]
  // 삽입할 데이터 1를 정렬된 데이터와 비교하려고 하지만 4를 오른쪽에 덮어 씌웠으니 존재하지 않음.
  // -> 4의 위치에 1을 삽입
  [1, 4, 5, 3, 6, 2]
  // 정렬된 영역 [1, 4]
  // 정렬되지 않은 영역 [5, 3, 6, 2]
  
  // 2. 정렬되지 않은 영역의 첫번째 인덱스의 데이터를 정렬된 영역의 마지막 인덱스의 데이터와 비교
  // -> 4와 5를 비교
  // 4는 보보다 작으므로 자리 변경하지 않음. 5또 한 마찬가지
  [1, 4, 5, 3, 6, 2]
  // 정렬된 영역 [1, 4, 5]
  // 정렬되지 않은 영역 [3, 6, 2]
  
  // 3. 정렬되지 않은 영역의 첫번째 인덱스의 데이터를 정렬된 영역의 마지막 인덱스의 데이터와 비교
  // -> 5와 3을 비교
  // 5는 3보다 크므로 오른쪽에 덮어씌워줌
  [ 1, 4, 5, 5, 6, 2]
  
  // 다시 정렬된 영역의 뒤에서 2번째 값인 4와 3을 비교.
  // -> 4가 3보다 크므로 오른쪽에 덮어씌워줌
  [1, 4, 4, 5, 6, 2]
  
  // 그리고 다시 4의 이전 데이터인 1과 3을 비교
  // -> 1은 3보다 더 작으므로 덮어씌우지 않음
  // -> 3을 마지막 인덱스에 덮어 씌워줌
  [1, 3, 4, 5, 6, 2]
  // 정렬된 영역 [1, 3, 4, 5]
  // 정렬되지 않은 영역 [6, 2]
  
  // 이런식으로 정렬 진행
  
  

코드 예시

• 코드

  const insertionSort = (arr) => {
    // 첫번째 인덱스는 정렬되어 있는 상태로 가정.
    for (let i = 1; i < arr.length; i++) {
      let insertingData = arr[i];
      let j;
      for (j = i - 1; j >=0; j--) {
        if (arr[j] > insertingData) {
          arr[j + 1] = arr[j]
        } else {
          break;
        }
      }
      arr[j + 1] = insertingData;
    }
  }
  
  const arr = [4, 2, 44, 56, 1, 0, 65];
  console.log('> > > 정렬 전 < < <')
  console.log(arr);
  insertionSort(arr);
  
  console.log('> > > 정렬 후 < < <')
  console.log(arr);
  

• 결과

  > > > 정렬 전 < < <
  [
    4, 2, 44, 56,
    1, 0, 65
  ]
  > > > 정렬 후 < < <
  [
     0,  1,  2, 4,
    44, 56, 65
  ]
  

삽입 정렬의 성능

• 시간 복잡도

  • $O(n^2)$

장 단점

• 이해와 구현이 간단함

• 성능이 좋지 못함.

병합 정렬(Merge Sort)

• 조금 복잡한 정렬 알고리즘

• 재귀로 정렬하는 알고리즘

• 분할 정복 알고리즘에 속함

• 배열들의 데이터를 최소한을 쪼갠 후 각 단계 별로 병합을 하면서 정렬을 진행하는 방식

   

코드 예시

• 코드

  const mergeSort = (arr, leftIdx, rightIdx) => {
    // 배열의 원소가 1개일때까지 분할
    if (leftIdx < rightIdx) {
      // 기저 조건
      let middleIdx = parseInt((leftIdx + rightIdx)/2);
  
      // 왼쪽 영역 재귀적 호출로 정렬
      mergeSort(arr, leftIdx, middleIdx);
      // 오른쪽 영역 재귀적 호출로 정렬
      mergeSort(arr, middleIdx + 1, rightIdx);
  
      // 병합.
      merge(arr, leftIdx, middleIdx, rightIdx);
    }
  };
  
  const merge = (arr, leftIdx, middleIdx, rightIdx) => {
    let leftAreaIdx = leftIdx;  // 왼쪽 영역의 시작 인덱스
    let rightAreaIdx = middleIdx + 1; // 오른쪽 영역의 시작 인덱스
  
    let tempArr = new Array(arr.length).fill(0);
  
    let tempArrIdx = leftIdx;
    while(leftAreaIdx <= middleIdx && rightAreaIdx <= rightIdx) {
      if (arr[leftAreaIdx] <= arr[rightAreaIdx]) {
        // 왼쪽 영역의 값이 오른쪽 영역의 값보다 작으면 tempArr에 넣어주고, 왼쪽 영역의 인덱스 값을 올려준다.
        tempArr[tempArrIdx] = arr[leftAreaIdx++];
      } else {
        // 오른쪽 영역의 값이 왼쪽 영역의 값보다 작으면 tempArr에 넣어주고, 오른쪽 영역의 인덱스 값을 올려준다.
        tempArr[tempArrIdx] = arr[rightAreaIdx++];
      }
  
      tempArrIdx++;
    }
  
    if (leftAreaIdx > middleIdx) {
      // 오른쪽 영역이 병합이 덜 되었다면 tempArr에 나머지 값들을 넣어 준다.
      for (let i = rightAreaIdx; i <= rightIdx; i++) {
        tempArr[tempArrIdx++] = arr[i];
      }
    } else {
      // 왼쪽 영역이 병합이 덜 되었다면 tempArr에 나머지 값들을 넣어 준다.
      for (let i = leftAreaIdx; i <= middleIdx; i++) {
        tempArr[tempArrIdx++] = arr[i];
      }
    }
  
    for (let i = leftIdx; i <= rightIdx; i++) {
      arr[i] = tempArr[i]
    }
  }
  
  let arr = [3, 5, 2, 4, 1, 7, 8, 6];
  
  console.log('> > > 정렬 전 < < <');
  console.log(arr);
  
  mergeSort(arr, 0, arr.length - 1);
  
  console.log('> > > 정렬 후 < < <');
  console.log(arr);
  
  

• 결과

  > > > 정렬 전 < < <
  [
    3, 5, 2, 4,
    1, 7, 8, 6
  ]
  > > > 정렬 후 < < <
  [
    1, 2, 3, 4,
    5, 6, 7, 8
  ]
  

병합 정렬의 성능

• merge()함수내에 흩어진 배열을 합치는 경우의 성능을 평가

• 하나의 데이터와 하나의 데이터가 두 개로 합쳐질때 비교 연산을 두 번 진행

  • 두개의 데이터와 두개의 데이터가 네개로 합쳐질때 비교 연산을 네번 진행

  ⇒ 각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 $logn$이라 할 수 있음

• 분할된 데이터를 병합 할때는 n개의 데이터를 n번 비교하므로 $O(nlogn)$의 성능을 가짐

장 단점

• 성능이 좋음

• 이해와 구현이 어려움

퀵 정렬(Quick Sort)

• 분할 정복 알고리즘

• 재귀를 사용

• 정렬하기 전 배열에 있는 데이터 하나를 피벗으로 선택

  • 피벗의 선택 기준은 다양

• 피벗의 왼쪽에서 오른쪽으로 이동하는 데이터(leftStartIdx)와 배열의 오른쪽 끝에서 왼쪽으로 이동하는 데이터(rightStartIdx)를 설정

1. leftStartIdx를 오른쪽으로 이동시키면서 피벗보다 큰 값을 만나면 멈춤

2. leftStartIdx가 멈추면 rightStartIdx를 왼쪽으로 이동 시키면서 피벗보다 작은 값을 만나면 멈춤.

3. leftStartIdx의 값과 rightStartIdx의 값을 서로 교환(swap)

4. 다시 1부터 반복

5. 반복 하던 도중 leftStartIdx가 rightStartIdx의 값보다 커지면 더이상 이동하지 않고 멈춤.

6. 피벗과 rightStartIdx의 값의 위치를 교환 해줌

7. 그러면 피벗을 기준으로 좌측의 값은 피벗보다 작은 값들이 모여있고, 우측에는 피벗의 값보다 큰 값으로 모여있음.

8. 이제 왼쪽, 오른쪽의 데이터들을 다시 처음부터 반복하여 정렬 진행.

코드 예시

• 코드

  const quickSort = (arr, left, right) => {
    if (left <= right) {
      // 피벗을 정렬하도록 설정. 피벗의 값은 배열의 첫번째 데이터로 설정한다고 가정 하여 진행.
      let pivot = divide(arr, left, right);
  
      quickSort(arr, left, pivot - 1);
      quickSort(arr, pivot + 1, right);
    }
  }
  
  const divide = (arr, left, right) => {
    // 배열의 왼쪽 값을 피벗으로 설정
    let pivot = arr[left];
    let leftStartIdx = left + 1;
    let rightStartIdx = right;
  
    while(leftStartIdx <= rightStartIdx) {
      while (leftStartIdx <= right && pivot >= arr[leftStartIdx]) {
        // pivot보다 작은 값을 만날때까지 진행
        leftStartIdx++;
      }
  
      while (rightStartIdx >= (left + 1) && pivot <= arr[rightStartIdx]) {
        // pivot보다 큰 값을 만날때까지 진행
        rightStartIdx--;
      }
  
      if (leftStartIdx <= rightStartIdx) {
        // 인덱스가 서로 지나치지 않은 경우
        swap(arr, leftStartIdx, rightStartIdx);
      }
    }
  
    swap(arr, left, rightStartIdx);
  
    return rightStartIdx;
  }
  
  const swap = (arr, idx, idx2) => {
    let tmp = arr[idx];
    arr[idx] = arr[idx2];
    arr[idx2] = tmp;
  }
  
  const arr = [5, 3, 7, 2, 6, 4, 9, 1, 8];
  
  console.log('> > > 정렬 전 < < <')
  console.log(arr);
  
  quickSort(arr, 0, arr.length - 1);
  
  console.log('> > > 정렬 후 < < <')
  console.log(arr);
  
  

• 결과

  > > > 정렬 전 < < <
  [
    5, 3, 7, 2, 6,
    4, 9, 1, 8
  ]
  > > > 정렬 후 < < <
  [
    1, 2, 3, 4, 5,
    6, 7, 8, 9
  ]
  

퀵 정렬의 성능

• 피벗을 기준으로 배열을 반으로 나눔.

  • 데이터가 한개가될때까지 나눔 → $logn$

  • 해당 작업을 n개반큰 작업을 해야 하므로 $nlogn$

  • 따라서 시간 복잡도는 $\theta(nlogn)$

  • 하지만 위의 경우는 평균적인 경우

• 피벗이 중간이 아닌 한쪽에 치우쳐 있는 경우에는 $O(n^2)$

• 하지만 대부분은 성능이 좋은 피벗을 선택하여 최악의 경우가 발생할 확률은 극히 낮음.

• 성능만 보면 병합 정렬이 더 좋다고 볼 수 있음.

  • 퀵정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됨.

장 단점

• 성능이 좋음

• 이해와 구현이 어려움.

동적 프로그래밍

• 재귀를 사용하면 함수가 호출되어 콜스텍의 영역을 차지하는 단점 이외에도 성능에 크게 영향을 미치는 단점이 존재

  • 피보나치 수열이 대표적 예

  • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

  • 이를 재귀 함수로 구현 하면 아래와 같다.

    const fibonacci = (n) => {
      if (n === 0 || n === 1) return n;
      return fibonacci(n - 2) + fibonacci(n - 1);
    }
    
    console.log(fibonacci(5));
    

  • 하지만 해당 코드를 보면 중복되는 결과가 호출되는 상황이 발생한다.

     

  → 중복되는 계산으로 인해 시간이 낭비됨.

  → 이를 줄이는 방식은 계산 결과를 저장하여 같은 결과를 계산할때 저장된 결과를 사용.

메모이제이션(Memoization)

• 계산하려는 데이터가 있는지 검색하고, 없으면 계산을 하고 저장.

• 중복 계산을 하지 않아서 속도가 빠름

• 해시 테이블을 사용.

• 하향식 계산 방식

코드 예시

• 파보나치 수열을 메모이제이션을 활용해 구현

• 자바스크립트의 객체를 활용

• 코드

  const fibonacci = (n) => {
    if (n === 0 || n === 1) return n;
    return fibonacci(n - 2) + fibonacci(n - 1);
  }
  
  const fibonacci2 = (n, memo) => {
    if (n === 0 || n === 1) return n;
  
    if (!memo[n]) {
      memo[n] = fibonacci2(n -  2, memo) + fibonacci2(n - 1, memo);
    }
  
    return memo[n];
  }
  
  console.time();
  console.log(fibonacci(40));
  console.timeEnd();
  
  console.time();
  console.log(fibonacci2(40, {}));
  console.timeEnd();
  
  

• 결과

  102334155
  default: 2.716s
  102334155
  default: 0.141ms
  

• 재귀 방법보다 훨씬 속도가 빠르다.

성능

• 계산하는 값이 커질수록 성능이 발휘함

• 재귀적으로 구현하면 성능은 $O(2^n)$, 메모이제이션을 사용하면 $O(n)$의 성능을 가짐.

장 단점

• 빠른 속도

• 메모리를 사용하는 단점

타뷸레이션

• 상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장

코드 예시

• 코드

  /**
   * 타뷸레이션 방식으로 피보나치 수열 구현
   * @param {number} n 
   * @returns 
   */
  const fibonacci3 = (n) => {
    if (n <= 1) return n;
  
    let table = [0, 1];
  
    for (let i = 2; i <=n; i++) {
      table[i] = table[i - 2] + table[i - 1];
    }
  
    return table[n]
  }
  
  console.time();
  console.log(fibonacci(40));
  console.timeEnd();
  
  console.time();
  console.log(fibonacci2(40, {}));
  console.timeEnd();
  
  console.time();
  console.log(fibonacci3(40));
  console.timeEnd();
  

• 결과

  102334155
  default: 1.786s
  102334155
  default: 0.259ms
  102334155
  default: 0.201ms
  

타뷸레이션 성능

• 적은 메모리 사용인데에도 빠른 시간을 보여줌.

메모이제이션과 타뷸레이션의 비교

• 메모이제이션을 통한 피보나치 함수는 여러 번의 함수 호출로 메모리 공간의 스택을 차지하고 메모이제이션을 위한 공간까지 차지하기 때문에 메모리를 더 많이 사용한다.

• 타뷸레이션을 통한 피보나치 함수는 적은 메모리 사용인데도 불구하고 빠른 시간을 보인다.

• 더 좋은 방식은?

  • 메모이제이션은 문제를 하향식으로 해결하여 복잡한 문제를 쉽게 해결할 수 있는 장점이 있다.

  • 재귀만 이용한다면 중복 계산을 하기 때문에 성능에 문제가 발생하는데, 계산 결과를 저장하는 방식으로 단점을 해결했다.

  • 그렇기 때문에 분할 정복을 해결할 때 재귀가 더 직관적이라면 메모이제이션을 이용하는 것이 유리하다.

  • 하지만 재귀가 직관적이지 않은 문제라면, 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 해결할 수 있다.