운영체제

가상메모리 개요

• 운영체제나 프로세스가 메모리의 크기보다 클 때 실행되지 않는 문제를 해결하기 위해 나옴.

• 메모리보다 크기가 큰 운영체제와 프로세스들을 처리할 때, 가상 메모리 시스템은 물리 메모리 내용의 일부를 하드 디스크의 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와 처리함.

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

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

• 가상 메모리 분할 방식에는 가변 분할 방식(세그멘테이션)과 고정 분할 방식(페이징)이 있음.

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

세그멘테이션(배치정책)

• 메모리 관리자는 세그멘테이션 테이블로 관리를 함

  • 세그멘테이션 테이블은 Base Address와 Bound Address가 저장되고, 이걸 이용해 물리 메모리 주소를 계산함.

    • CPU가 논리주소 123번지 요청 → 메모리 관리자는 123번지가 몇번 세그먼트인지 알아냄 → Segment Table Base Register(메모리 관리자 내)를 이용해서 세그멘테이션 테이블(물리 메모리내)을 찾음 → 세그멘테이션 테이블에서 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾음. → 메모리 관리자는 논리 주소와 Bound Address의 크기를 비교함.

      • → 논리주소 < Bound Address ⇒ 논리주소 + Base Address = 물리주소

      • → 논리주소 > Bound Address ⇒ 메모리 침범, 에러 발생시키고 종료 시킴.

  • 운영체제는 컨텍스트 스위칭을 할 때마다 Segment Table Base Register를 해당 프로세스의 것으로 바꿔줘야 하기 때문에 컨텍스트 스위칭은 무거운 작업임

• 장점

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

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

• 단점

  • 외부 단편화 발생

    • 외부 단편화 : 프로세스의 크기별로 할당된 메모리에 프로세스가 작업을 종료하고 메모리에서 내려가고 메모리에 공백이 생겼을 때, 공백된 크기보다 큰 크기의 프로세스가 메모리 할당 요청을 할 때 연속된 공간이 아니기 때문에 새로운 프로세스에게 할당 할 수 없는 현상을 말함.

    • 조각모음으로 해결할 수 있지만, 오버헤드가 발생하는 큰 작업임.

페이징(배치정책)

• 메모리를 할당 할 때, 정해진 크기의 페이지로 나누는 방식.

• 모든 페이지는 크기가 같기 때문에 관리가 굉장히 쉽고 또한 일정한 크기로 나눴기 때문에 외부 단편화가 발생하지 않음.

• 페이지 : 논리 주소 공간을 일정한 크기로 균일하게 나눈 것

• 프레임 : 물리 주소 공간을 페이지의 크기와 동일하게 나눈 것

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

  • 페이지 테이블에는 인덱스와 프레임이 있음.

    • CPU에서 논리 주소 전달 → 메모리 관리자는 논리주소가 몇번 페이지인지, 오프셋은 얼마인지 알아냄. → Page Table Base Register(메모리 관리자내)를 이용해서 페이지 테이블(물리 메모리)을 찾음 → 페이지 테이블에서 페이지 번호를 인덱스로 프레임 번호를 알아내고, 오프셋을 이용해 물리주소로 변환함.

      • 물리 주소 = 프레임 번호 + 오프셋

    • 페이지 테이블에 Invalid로 표시되어 있으면 하드디스크의 스왑 영역에 저장되어 있다는 의미

    • Page Table Base Register는 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해줌

• 세그멘테이션과의 차이점

  • 세그멘테이션

    • 프로세스마다 크기가 달라 Bound Address를 가지고 있음

    • 논리적인 영역별로 크기를 다르게 세그먼트를 나눌 수 있음.

  • 페이징

    • 페이지의 크기가 동일해서 크기를 표현하는 Bound Address가 필요 없음

    • 크기가 고정되어 있어 논리적인 영역별로 나눌 수 없음.

• 페이징에서 가장 신경 써야 하는 것은 페이지 테이블의 크기

   

  • 각 프로세스마다 페이지 테이블을 가지고 있는데, 프로세스가 많아질 수록 페이지 테이블도 많아지기 때문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듬.

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

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

• 장점 : 외부단편화가 발생하지 않음

• 단점 : 내부단편화가 발생함

  • 내부단편화 : 정해진 크기의 페이징보다 프로세스의 정보가 작으면 낭비되는 공간이 발생하는 것

페이지드 세그멘테이션(배치정책)

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

• 메모리 접근 권한

  • 메모리의 특정 번지에 부여된 권한

     

    • 코드 영역 : 프로그램 그 자체 -> 읽기/실행 권한 O

       

    • 데이터 영역 : 일반변수, 전역변수, 상수로 선언한 변수가 저장 -> 읽기(쓰기) 권한 O / 실행 권한 X

       

    • 힙 영역 : 읽기/쓰기 권한 O / 실행 권한 X

       

    • 스택 영역 : 읽기/쓰기 권한 O / 실행 권한 X

  • 메모리 접근 권한에 대한 검사 가상주소 → 물리주소로 변환될 때 마다 일어나는데, 만약 권한을 위반한다면, 에러를 발생 시키고 종료 시킴.

• 페이지드 세그멘테이션 : 세그멘테이션 테이블(세그먼트 번호 / Base Address / Bound Address) + 페이지 테이블(인덱스 / 프레임)

  • 세그멘테이션 테이블에서

    • 권한 비트 추가

    • Base Address → 페이지 넘버 : 이름 변경

    • Bound Address → 페이지 개수 : 이름 변경

• 논리 주소 0x12300번지 접근 요청시,

  • 논리 주소를 이용해 몇 번 세그먼트인지 알아냄.

  • 세그멘테이션 테이블에서 1번 인덱스를 참조

  • 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사

    • 접근 권한 위반시 → 프로세스 종료

    • 위반 하지 않으면 → 페이지 넘버와 페이지 개수 가져옴

  • 페이지 넘버로 페이지 테이블에 접근해서 프레임 번호 가져옴

  • 논리 주소에서 오프셋을 알아내고

  • 오프셋 + 프레임 번호 위치 = 물리 주소

• 물리 메모리에 해당 프레임이 없다면, 스왑 영역에서 물리 메모리로 가져옴.

• 단점 : 물리 메모리에 접근 하기 위해서 메모리에 접근을 2번 해야함.

  • 세그멘테이션 테이블 참조할 때

  • 페이지 테이블 참조 할 때

  디맨드 페이징(가져오기 정책)

• 프로세스가 실행 될때 프레세스를 이루고 있는 코드/데이터/힙/스택과 같은 모듈 중 필요한 모듈만 메모리에 올라와서 실행됨.

• 지역성 이론 2가지

  • 공간의 지역성 : 현재 위치에서 가까운 데이터에 접근할 확률이 높음

  • 시간의 지역성 : 현재 기준으로 최근 접했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음

  • 지역성 이론은 조만간 쓸 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능을 향상 시킴

• 디맨드 페이징 : 조만간 필요할 것 같은 데이터를 메모리고 가져오고 쓰지 않을 것 같은 데이터는 스왑 영역으로 이동 시키는 정책

• 메모리 계층 구조에는 레지스터/캐시/메인메모리/보조저장장치가 있고, 왼쪽에서 오른쪽으로 갈수록 느리다.

• 디맨드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능 향상을 위해선 스왑영역으로 데이터를 이동시키는 것을 최소화 시켜야 함.

• 가상 메모리의 크기 = 물리 메모리 크기 + 스왑 영역

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

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

• CPU에서 논리 주소를 요청하면, 메모리 관리자는 페이지 테이블을 참조해서 물리 메모리가 있는 프레임을 알아내거나 스왑영역의 위치를 알아냄

  • 페이지 테이블에는 프레임 넘버 외에도 여러가지 비트가 있음

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

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

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

  • 읽기/쓰기/실행 비트 : 권한 비트, 해당 메모리에 접근 권한이 있는지 검사하는 비트

• 프로세스가 가상 메모리에 접근 요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아내는데, 물리 메모리에 없다면 Page Fault 라는 인터럽트를 발생 시킴

• Page Fault가 발생하면,

  • 보조저장장치의 스왑영역에 접근하게 되고, 해당 프로세스는 대기상태가 됨.

  • 스왑 영역에 있는 데이터가 메모리에 올라가는 작업을 시작하고

  • 메모리에 올라갔다면 대기 상태에 있던 프로세스는 실행하게 됨

• 스왑인과 스왑아웃을 할 때 어떤게 적절한지는 운영체제가 판단함. 판단 하는 것을 페이지 교체 알고리즘이라 부름

페이지 교체 정책

• 프로세스는 데이터 접근을 위해 메모리를 참조하는데, 해당 데이터가 메모리 없으면 Page Fault가 발생함.

• 페이지 교체 정책 : 메모리에 있는 페이지를 스왑 영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책

• 페이지 교체 정책의 여러가지 방법

  • Random

    • 무작위로 선택하는 방법

    • 자주 사용되는 페이지가 선택 될 때가 있어 성능에 별로 좋지 않음

    • 많이 사용되지 않음

  • FIFO

    • 메모리에 들어온지 가장 오래 된 페이지를 선택하는 방법

    • 장점 : 구현이 간단하고 성능도 꽤 괜찮음

    • 단점 : 자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지가 교체 되면 공평하지 않음.

    • 조금 변형해서 많이 쓰임

  • Optimum

    • 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법

    • 사실상 구현이 불가능함

    • 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰임

  • LRU

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

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

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

    • 단점

      • 프로그램이 지역성을 뛰지 않을 땐 성능이 떨어지게 됨.

      • 페이지 테이블 엔트리는 여러 개의 비트와 페이지 넘버가 저장된다고 했는데 이곳에 시간을 기록하려면 비트가 많이 필요하게 됨.

    • LRU를 구현할 때는 접근 비트를 이용해서 LRU에 근접하게 구현함.

    • 많은 비트가 필요하기 때문에 오버 플로우 발생함

• 빌레이디의 역설

  • Page Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상

  • FIFO에서만 발생함

• 클락 알고리즘

  • LRU와 유사하게 구현하는 방법을 고안한 알고리즘

  • 접근 비트 하나만 이용함

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

    • 접근 비트의 초기값은 0으로 되어 있고, 페이지가 참조되었다면 1로 설정함.

    • 일정 시간 간격마다 페이지가 참조되었는지 참조되지 않았는지 확인할 수 있음.

    • 페이지를 원형으로 연결함.

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

    • 클락핸드는 시계방향으로 돌고 있음.

    • 만약 page fault가 발생해서 스왑 영역으로 보내야 하는 상황이 나오면,

      • 클락 핸드는 현재 참조하고 있는 페이지의 접근 비트를 봄.

      • 해당 페이지의 접근 비트가 1이라면 0으로 바꾸고 클락 핸드가 다음 페이지를 가르킴.

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

• 향상된 클락 알고리즘

  • 접근 비트만 이용하는 것이 아니라 변경 비트도 보는 알고리즘

  • 스왑영역으로 보내지는 높은 순위

    • 접근 비트 0, 변경 비트 0인 페이지

    • 접근 비트 0, 변경 비트 1인 페이지

    • 접근 비트 1, 변경 비트 0인 페이지

    • 접근 비트 1, 변경 비트 1인 페이지

• 부득이하게 FIFO를 사용해야 하는 경우

  • 하드웨어적으로 접근비트를 지원하지 않는 시스템에서 사용

  • FIFO 성능 높이는 방법 고안

  • 2차 기회 페이지 교체 알고리즘

    • 자주 사용되는 페이지에게는 또 한번의 기회를 주는 것임.

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

    • 성능 : LRU보다 안좋고, FIFO보다 좋음.

스레싱과 워킹셋

• 멀티프로그래밍 정도가 늘어날 수록 프로세스를 메모리에 올릴 공간이 부족해짐

• 그럼 당장 실행되지 않는 프레임은 스왑 영역에 저장되고 Page Fault가 많이 발생하게 됨.

• 그럼 CPU가 작업하는 시간보다 스왑 작업의 시간이 더 길어지고 CPU사용률이 떨어짐

• 스레싱

  • CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황

  • 원인 : 물리 메모리의 크기 부족

  • 하드웨어적 해결 : 물리 메모리 늘리기 / 스레싱이 발생하지 않으면 다른 점이 없음

  • 소프트웨어적 해결 : 프로세스가 실행되면, 일정량의 페이지를 할당하고 Page Fault의 발생 빈도수에 따라 페이지의 크기를 조절함.

• 워킹셋

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

  • 프로세스가 준비상태에서 실행상태가 되는 실행 컨텍스트를 할 때 사용됨.

주변장치(I/O디바이스와 저장장치)

• 주변장치 : 그래픽카드, 하드디스크, SSD, 키보드, 마우스, ...

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

• 하나의 버스(I/O버스) 구성 : Address 버스, Data 버스, Control 버스

• 레지스터 : 장치의 상태와 데이터 보관, 입출력 작업시 데이터 저장 역할, 값들은 CPU가 사용하기 위해 메모리로 이동 되기도 함.

• 주변장치 데이터의 전송단위에 따라 2가지로 나눌수 있음.

  • 캐릭터 디바이스 : 캐릭터(글자) → 마우스, 키보드, 사운드 카드, 직병렬포트

    • 상대적으로 적은 양의 데이터 전송

  • 블록 디바이스 : 블록 → 하드디스크, SSD, 그래픽카드

    • 많은 양의 데이터 전송

• 예전에는 주변장치들을 하나의 버스에 연결해서 사용했기 때문에 I/O 명령을 만나면 작업을 처리하는 중에는 다른 작업이 불가능하여 CPU 사용률이 떨어졌음.

• CPU사용률을 높이고자, 입출력 제어기와 여러 개의 버스가 추가 되면서 I/O명령을 만나 작업을 처리하는 중에 다른 작업을 할 수 있게 됨.

• 입출력 제어기는 2개의 채널이 있음

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

  • 입출력 버스 : 주변장치가 사용 / 세부적으로 느린장치와 빠른장치를 구분하기 위해 두개의 채널로 나눠짐

    • 고속 입출력 버스 : HDD

    • 저속 입출력 버스 : 마우스, 키보드

    • 두개의 채널을 이용하여 속도 차이로 인한 병목현상 해결함

• 그래픽카드가 다루는 데이터는 매우 대용량이라, 고속 입출력으로도 감당이 되지 않기 때문에 시스템 버스에 바로 연결하여 사용함

• 입출력 제어기는 입출력 버스에서 온 데이터를 메모리로 옮김

  • 입출력 제어기가 CPU의 도움이 필요 없도록 DMA 제어기가 추가됨

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

  • CPU와 DMA가 사용하는 메모리 영역이 겹치지 않도록 메모리 영역을 나눔

마우스와 키보드

• 마우스

  • 볼마우스 : 마우스 안에 있는 볼의 회전을 감지해서 움직임을 처리함

  • 광학마우스

    • 아래에 작은 카메라가 있고, 사진을 찍어 마우스 디바이스 컨트롤내에 DSP로 보냄 → 그 사진을 기반으로 마우스의 x축 좌표와 y축 좌표 움직임을 캐치함

  • DSP가 마우스의 움직임과 클릭 같은 데이터를 감지 → 디바이스 컨트롤러가 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어감.

  • 마우스 드라이버는 운영체제에게 이벤트 신호를 줌 → 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달 → 해당 애플리케이션은 받은 마우스 이벤트 처리

• 키보드

  • 사용자가 키보드 버튼 누르면 → 키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄 → CPU에게 인터럽트를 보냄 → 키보드 드라이버는 운영체제에게 이벤트를 보냄 → 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달 → 해당 애플리케이션은 받은 키보드 이벤트 처리

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

• 하드디스크

  • 단점

    • 느림

    • 자기적으로 처리하기 때문에, 자석을 갖다대면 데이터가 손상됨.

    • 충격에 매우 약함

• 플래시 메모리(SSD)

  • 전기적으로 읽기 때문에 조용하고 빠름

  • 단점

    • 특정한 지점의 데이터를 썼다면 덮어쓰기가 불가능함

      • 똑같은 지점에 데이터를 쓰려면 기존에 있는 데이터를 지우고 다시 써야 하는데, 지우기 횟수가 정해져 있음. 똑같은 지점에 지우기/쓰기를 반복하면 망가짐

파일과 파일 시스템

• 사용자가 저장 요청을 하면 운영체제가 안전하게 저장해줌

• 운영체제는 파일을 관리하기 위해 파일 관리자를 둠 → 파일 시스템

• 파일 관리자는 파일 테이블을 이용해서 파일을 관리함

• 파일 시스템의 기능

  • 파일과 디렉토리 생성

  • 파일과 디렉토리 수정/삭제

  • 파일 권한 관리

  • 무결성 보장

  • 백업과 복구

  • 암호화

• 파일 시스템은 HDD나 플래시 메모리(SSD)에 저장되기 때문에 전송 단위가 블록임

• 사용자는 바이트 단위로 접근 해야 하기 때문에 파일 관리자가 중간에서 변환해줌.

• 확장자로 파일의 성격을 알 수 있음

• 파일의 구조

  • 헤더 : 파일의 속성이 담겨져 있음

  • 데이터

• 파일 디스크립터 : 운영체제가 파일을 관리하기 위해 정보를 보관하는 파일 제어 블록(FCB)

  • 파일마다 독립적으로 존재

  • 저장 장치에 존재하다가 파일이 오픈 되면 메모리로 이동함

  • 파일 시스템(운영체제)이 관리함

• 파일 : 데이터의 집합

  • 데이터의 집합 어떻게 구성하느냐에 따라 종류가 달라짐

    • 순차 파일 구조

      • 파일의 내용이 연석적으로 이어진 형태

      • ex) 카세트 테이프 -> 1번부터 100번까지 순차적으로 곡을 실행함

      • 장점 : 모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순함

      • 단점 : 특정 지점에 바로 이동이 어려워 데이터 삽입/삭제시 탐색하는데 시간이 많이 걸림

    • 직접 파일 구조

      • 저장하려는 데이터를 해시함수를 통해 저장 위치를 결정하는 파일 구조

      • 장점 : 해시함수를 이용하기 때문에 데이터 접근이 빠름

      • 단점 : 해시함수의 선정이 굉장히 중요하고 저정공간이 낭비 될 수 있음.

    • 인덱스 파일 구조

      • 순차 접근과 직접 접근의 장점을 취한 것으로 두 가지 방식 모두 가능

      • ex) 음악 재생 프로그램의 재생 목록

        • 재생 목록 : 순차 데이터로 저장

        • 2번 노래 듣고 싶음 -> 인덱스 테이블의 2번에 접근해 블록 번호 알아냄 -> 순차 데이터의 해당 블록 데이터로 이동해 재생함

디렉토리

• 관련 있는 파일의 집합체

• 1개 이상의 파일을 가질 수 있고, 자식 디렉토리도 가질 수 있음

• 최상위 디렉토리 = 루트 디렉토리

• 유닉스와 리눅스

  • 최상위 디렉토리 표시 : "/"

  • 디렉토리와 디렉토리 구분 : "/"

• 윈도우

  • 최상위 디렉토리 표시 : 파티션 이름으로 함 ex) "C:"

  • 디렉토리와 디렉토리 구분 : "\"

• 디렉토리 헤더 : 디렉토리 정보가 시작하는 위치를 가르킴

• 초기에는 단순 구조로 루트에만 하위 디렉토리가 생성 가능했다가 다단계 디렉토리 구조 등장했다.

  • 어떠한 디렉토리에서도 하위 디렉토리 생성 가능 ⇒ 트리 구조

  • 바로 가기 기능 때문에 순환이 있는 트리 구조임

파일과 디스크

• 파일 시스템은 메모리와 비슷하게 디스크를 일정한 크기로 공간을 나눔.

• 일정한 크기로 나눈 공간을 블록이라고 함. (블록 크기 : 1~8KB 정도)

• 파일 시스템은 파일 정보를 파일 테이블로 관리함.

• 파일 제어 테이블

  • 파일 정보

  • 위치 정보(블록 포인터) : 파일이 시작하는 블록 정보

• 하나의 파일은 여러 개의 블록으로 이루어져 있음.

• 블록을 어떻게 연결 하는지에 따라 2가지로 나뉨

  • 연속 할당

    • 파일을 구성하는 블록을 디스크에 연속적으로 저장하는 방식

    • 장점 : 파일의 시작 지점만 알면 파일의 전체를 찾을 수 있음

    • 단점 : 메모리의 세그멘테이션 기법처럼 외부단편화가 발생함 → 사용되지 않음

  • 불연속 할당

    • 디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식

    • 분산된 블록은 파일 시스템이 관리함.

    • 불연속 할당은 또 2가지로 나눠짐.

      • 연결 할당

        • 자료 구조의 연결 리스트로 관리

        • 파일 테이블에는 시작 블록에 대한 정보만 저장, 나머지는 연결 리스트를 이용해 다른 블록에 접근하는 방식

      • 인덱스 할당

        • 파일 제어 테이블의 블록 포인터가 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결함.

        • 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에, 테이블 확장 가능

        • 파일 크기가 작다면 → 데이터를 바로 참조하는 블록 포인터 이용

        • 파일 크기가 크다면 → 간접 포인터를 이용해 많은 데이터에 접근 가능

        • 더 큰 데이터가 필요하다면 → 이중 간접 포인터, 삼중 간접 포인터 이용 가능

• 디스크의 블록을,

  • 1KB로 나누면 → 낭비 되는 공간 줄일 수 있음, 관리해야 할 블록 수 증가

  • 8KB로 나누면 → 관리해야 할 블록 수는 적지만, 내부 단편화로 낭비되는 공간이 많아짐

• 디스크에 파일을 저장할 때 마다 빈 공간을 찾으려 모든 공간을 탐색하는 방식은 비효율적임.

• 파일시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있음.

  • 파일 삭제시 → 파일 테이블의 헤더 삭제, free block list에 추가함.

  • 사용했던 블록의 데이터는 남아 있기 때문에, 범죄를 저질러 파일을 삭제하였다고 하더라도 포렌식으로 파일을 복구 할 수 있음.

자료구조와 알고리즘

정렬 - 삽입정렬

• 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘

• 정렬되지 않은 영역의 가장 앞에 있는 원소를, 정렬된 영역의 가장 뒤에 있는 원소부터 역순으로 비교함

• 배열 [4, 1, 5, 3, 6, 2]이 있다.

  • 가장 첫 번째 수인 4만 정렬되어 있다고 가정함.

  • 정렬된 영역의 마지막 데이터인 4 와, 정렬되지 않은 영역의 첫번째 데이터인 1을 비교함.

  • 4는 1보다 크므로 4를 오른쪽 인덱스에 덮어쓰기 해줌.

  • 더 비교할 대상이 없다면, 4의 자리에 1을 덮어 쓰기 해줌.

  • 반복해줌

function 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;
    }
}

let arr = [4, 1, 5, 3, 6, 2];
console.log("===== 정렬전 =====");
console.log(arr);

InsertionSort(arr);

console.log("===== 정렬후 =====");
console.log(arr);

• 삽입 정렬의 성능 : O(n)의 성능

• 장점 : 이해가 쉽고 구현이 간단함

• 단점 : 성능이 좋지 못함.

정렬 - 병합정렬

• 분할 정복 알고리즘

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

• 배열을 반으로 계속 나눠 중간을 기준으로 원소를 비교하여 작은 값이 앞에 오도록 정렬하여 병합 시켜줌

function MergeSort(arr, leftIndex, rightIndex) {
    // leftIndex가 0, rightIndex가 7로 가정,
    if (leftIndex < rightIndex) { // 기저 조건 ⇒ 배열의 원소가 1개일 때까지 분할하기 위함
        // 0 < 7 참
        let midIndex = parseInt((leftIndex + rightIndex) / 2); // 3
        MergeSort(arr, leftIndex, midIndex);
        MergeSort(arr, midIndex + 1, rightIndex);
        Merge(arr, leftIndex, midIndex, rightIndex);
    }
}
  
function Merge(arr, leftIndex, midIndex, rightIndex) {
    let leftAreaIndex = leftIndex;
    let rightAreaIndex = midIndex + 1;
  
    let tempArr = [];
    tempArr.length = rightIndex + 1;
    tempArr.fill(0, 0, rightIndex + 1);
  
    let tempArrIndex = leftIndex;
    
    while (leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
        if (arr[leftAreaIndex] <= arr[rightAreaIndex]) {
            tempArr[tempArrIndex] = arr[leftAreaIndex++];
        } else {
            tempArr[tempArrIndex] = arr[rightAreaIndex++];
        }
        tempArrIndex++;
    }

    if (leftAreaIndex > midIndex) {
        // 만약 오른쪽 배열 병합이 덜 끝났으면,
        for (let i = rightAreaIndex; i <= rightIndex; i++) {
            tempArr[tempArrIndex++] = arr[i];
        }
    } else {
        // 만약 왼쪽 배열 병합이 덜 끝났으면,
        for (let i = leftAreaIndex; i <= midIndex; i++) {
            tempArr[tempArrIndex++] = arr[i];
        }
    }
    
    for (let i = leftIndex; i <= rightIndex; 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);

• 각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에, logn으로 말할 수 있음.

• 병합 정렬의 성능 : O(nlogn)

• 장점 : 성능이 O(nlogn)으로 버블정렬과 선택정렬, 삽입정렬보다 좋음.

• 단점 : 이해와 구현이 어려움

정렬 - 퀵정렬

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

• 정렬하기 전에 배열에 있는 숫자 중 하나를 "피벗"으로 설정함.

  • 피벗을 정하는 방법에는 여러가지가 있음.

• 피벗을 제외한 배열의 양쪽에서 값을 비교하여,

• 오른쪽으로 이동하는 인덱스의 값이 피벗보다 크다면 멈추고

• 왼쪽으로 이동하는 인덱스의 값이 피벗보다 작다면 멈추고

• 각 인덱스가 멈추면 두 인덱스의 값을 교환함.

• 반복하다가 값을 비교하는 인덱스가 서로를 지나치면 피벗과 왼쪽으로 이동하는 인덱스의 값을 교환 해주는 방식

function quickSort(arr, left, right) {
    if (left <= right) { // 기저조건
        let pivot = divide(arr, left, right); // 정렬된 피벗의 위치(인덱스) 리턴
        quickSort(arr, left, pivot - 1); // 왼쪽 영역 정렬
        quickSort(arr, pivot + 1, right); // 오른쪽 영역 정렬
    }
}

function divide(arr, left, right) {
    let pivot = arr[left]; // 여기서 가장 왼쪽의 값을 피봇으로 하기로 했기 때문에 이렇게 지정
    let leftStartIndex = left + 1;
    let rightStartIndex = right;
    
    while (leftStartIndex <= rightStartIndex) {
        while (leftStartIndex <= right && pivot >= arr[leftStartIndex]) { // 왼쪽 영역의 작은값인지 확인
            leftStartIndex++;
        }

        while (rightStartIndex >= left + 1 && pivot <= arr[rightStartIndex]) { // 오른쪽 영역의 큰값인지 확인
            rightStartIndex--;
        }

        if (leftStartIndex <= rightStartIndex) {
            // leftStartIndex가 rightStartIndex를 지나치지 않으면 교환
            swap(arr, leftStartIndex, rightStartIndex);
        }
    }

    swap(arr, left, rightStartIndex);
    return rightStartIndex;
}

function swap(arr, index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

let 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);

• 퀵 정렬의 성능

  • 피벗이 매번 배열의 반을 가르는 평균적인 경우 → O(nlogn)

  • 피벗이 한쪽으로 치우치는 경우(최악의 경우) → O(n²)

  • 최악의 경우가 발생할 확률이 극히 낮기 때문에 평균적인 성능을 말함

  • 병합 정렬이 더 좋아 보이지만, 실제로 비교하면 퀵정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됨.

• 장점 : 성능이 O(nlogn)으로 버블정렬과 선택정렬, 삽입정렬보다 좋음.

• 단점 : 이해와 구현이 어려움

동적 프로그래밍 - 메모이제이션

• 계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법

• 계산하려는 데이터가 있는지 "검색"하고, 없다면 함수를 호출해 계산을 하고 그 결과를 "저장"시키면 됨.

• 자료구조 중 데이터 검색과 삽입이 빠른 해시 테이블을 사용하는 것이 적절함.

// 메모이제이션 적용 전 -> O(n2)
function fibonacci1(n) {
    if (n === 0 || n === 1) return n;
    return fibonacci1(n - 2) + fibonacci1(n - 1);
}

// 메모이제이션 적용 후 -> O(n)
function fibonacci2(n, memo) {
    if (n === 0 || n === 1) return n;

    if (memo[n] == null) {
        memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
    }

    return memo[n];
}

• 메모이제이션을 적용 전의 성능 → O(n²)

• 메모이제이션을 적용 후의 성능 → O(n)

• 메모이제이션의 장단점

  • 장점 : 재귀적인 기법으로 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있고, 중복 계산을 하지 않아 속도가 빠름.

  • 단점 : 속도를 위해서 메모리 영역을 사용함. 재귀함수를 사용하는 것이기 때문에 오버헤드가 큼

동적 프로그래밍 - 타뷸레이션

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

   

function fibonacci3(n) {
    if (n <= 1) return n;

    let table = [0, 1];

    for (let i = 2; i <= 2; i++) {
        table[i] = table[i - 2] + table[i - 1];
    }

    return table[n];
}

• 적은 메모리 사용임에도 불구하고 앞에 만들었던 fibonacci2보다 빠른 시간을 보임.

• 메모이제이션과 타뷸레이션 방식중 어느것이 좋은가?

  • 상황에 따라 다름.

  • 분할 정복을 해결할 때, 재귀가 더 직관적이라면, 메모이제이션을 사용하는 것이 더 유리함

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

회고

• 칭찬하고 싶은 점 : 인프런 워밍업 클럽을 포기하지 않고 완주했다!

• 아쉬웠던 점 : 재귀를 이해했다고 생각했는데, 아니었다🥲

• 보완하고 싶은 점 : 강의를 다시 여러번 들어보려고 한다. 특히 병합정렬이 여전히 이해가 되지 않는다