인프런 워밍업 클럽 스터디 3기 - CS 3주차 발자국
운영체제
섹션 8. 가상메모리
8-1. 가상메모리 개요
가상메모리를 사용해 프로세스는 운영체제 영역이 어디있는지, 물리메모리 크기가 얼마나 큰지 몰라도 됨. 즉, 프로그래머는 물리 메모리의 크기와 프로세스가 메모리에 어느 위치에 올라가는지 신경쓰지 않고 0x0번지에서 시작된다고 생각하고 프로그래밍을 하면 됨
프로세스 입장에서는 물리 메모리에 직접 접근할 일이 없고, 메모리 관리자에게 요청만 하면 됨
메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시킴
가상 메모리의 크기는 이론적으로는 무한대이지만, 실제로는 물리 메모리 크기와 CPU의 비트 수로 결정됨
동적주소변환(DAT)이란? 메모리 관리자는 물리 메모리 + 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환하는 것
동적주소변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있음
가변 분할 방식(세그멘테이션)
단점: 외부 단편화
고정 분할 방식(페이징)
단점: 내부 단편화
가변 분할 방식, 고정 분할 방식 둘 다 단점이 있기에 이를 보완한 세그멘테이션-페이징 혼용기법을 사용함
8-2. 세그멘테이션(배치정책)
세그멘테이션에서 프로그램은 함수나 모듈등으로 세그먼트를 구성함
사용자와 프로세스, CPU가 바라보는 주소는 논리주소. 실제 물리주소로의 변환은 중간에서 메모리 관리자(MMU)가 수행. 세그멘테이션 테이블에는 Base Address와 Bound Address 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산함
CPU에서 논리 주소 전달 → 메모리 관리자는 이 논리주소가 몇번 세그먼트인지 확인 → 메모리 관리자 내에 Segment Table Based Register를 이용해 물리 메모리내에 있는 세그멘테이션 테이블 찾음
운영체제는 컨텍스트 스위칭을 할 때마다 메모리 관리자내에 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 함
메모리 관리자는 CPU에서 받은 논리주소와 이 Bound Address의 크기를 비교함
만약 논리주소가 Bound Address보다 작다면 논리주소와 Base Address를 더해 물리주소를 구하고, 논리주소가 Bound Address보다 크다면 메모리를 침범했다고 생각하고 에러를 발생시킴
세그멘테이션
장점
메모리를 가변적으로 반할할 수 있음
코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있기에 공유와 각 영역에 대한 메모리 접근보호가 편리함
단점
가변 분할 방식의 단점인 “외부 단편화”가 발생함
8-3. 페이징(배치정책)
페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눔. 모든 페이지는 크기가 같기에 관리가 굉장히 쉬워짐. 또한 일정한 크기로 나눴기에 외부단편화 현상이 일어나지 않음. 하지만 단점으로 “내부 단편화”가 발생함
페이징에서 논리주소공간은 일정한 크기로 균일하게 나눔. 이를 “페이지”라 부름
물리주소공간도 페이지의 크기와 동일하게 나뉘는데 이를 “프레임”이라고 부름
CPU에서 논리주소 전달 → 메모리 관리자는 이 논리주소가 몇번 페이지인지, 오프셋은 얼마인지 알아냄 → 메모리 관리자 내 Page Table Base Register(PTBR)를 이용해 물리 메모리에 있는 페이지 테이블을 찾음 → 페이지 번호를 인덱스로 프레임 번호를 알아냄 → 오프셋을 이용해 물리주소로 변환
페이지 테이블에 Invalid로 표시되어 있으면 스왑영역, 즉 하드디스크에 저장되어있다는 의미. 세그멘테이션과 마찬가지로 Page Table Base Register는 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해줌
물리주소의 크기가 가상주소의 크기보다 작아도 문제 없음을 보여주기위해 물리주소공간을 적게 설정함
부족한 물리메모리는 스왑처리를 하기에 괜찮음
세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가지고 있지만, 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address는 필요하지 않음
페이징은 이러한 특징 때문에 외부단편화는 발생하지 않지만 내부단편화가 발생함
정해진 크기의 페이징보다 프로세스의 정보가 작으면 그만큼 공간이 낭비되는데 이를 내부 단편화라고 부름
세그멘테이션은 논리적인 영역별로 세그먼트를 나눔. 세그먼트별로 크기를 다르게 나눌 수 있으니 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있음. 하지만 페이징은 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라 페이지로 나누기에 논리적인 영역을 나눌 수 없음 그래서 특정 영역만 딱 떼어내서 공유하거나 권한을 부여하는게 더 어려움
페이징에서 가장 신경써야하는 것은 페이지 테이블의 크기
각 프로세스별로 페이지를 가지고 있는데, 프로세스가 많아질수록 페이지 테이블도 많아지기에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듬. 실제로 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기에 페이지 테이블의 크기가 너무 크면 사용자 영역이 부족하게 됨. 이 때문에 페이지 테이블의 크기를 적절하게 유지하는 것이 굉장히 중요함
8-4. 페이지드 세그멘테이션(배치정책)
페이지드 세그멘테이션은 세그멘테이션과 페이징을 혼합해 장점을 취한 방식
세그멘테이션은 가변 분할 방식이어서 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나눠서 관리할 수 있음. 때문에 다른 프로세스와 공유하기도 편하고, 각 영역에 대한 메모리 접근보호를 하기 쉬움
페이징은 고정 분할 방식으로 메모리를 효율적으로 관리 할 수 있음
메모리 접근 권한은 메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세 가지가 있음. 프로세스는 코드 영역, 데이터 영역, 스택 영역, 힙 영역이 있는데 각 영역마다 접근 권한이 있음
코드 영역: 프로그램 그 자체이므로 수정되면 안되기 때문에 읽기/실행 권한만 있음
데이터 영역: 일반변수, 전역변수, 상수로 선언한 변수가 저장되기에 읽기 권한이 있고, 쓰기 권한은 있거나 없거나임. 당연히 실행권한은 없음
스택&힙 영역: 읽기/쓰기 권한. 실행권한은 없음
메모리 접근 권한에 대한 검사는 가상주소에서 물리주소로 변활될 때마다 일어남. 만약 권한을 위반하면 에러를 발생시킴
페이지드 세그멘테이션
장점
메모리 관리의 효율화
세그먼트를 페이지로 나누어 효율 증ㅇ가
외부 단편화 감소
효율적인 메모리 할당
유연함
페이지 단위의 물리적 관리
동적으로 크기 조절
보안
세그먼트 단위 보호
단점
물리메모리에 접근하기 위해 메모리에 접근을 두 번 해야되기에 복잡함
세그멘테이션 테이블을 참조할 때
페이지 테이블을 참조할 때
테이블 관리
세그먼트 테이블, 페이지 테이블 모두 관리가 필요하여 관리 비용 증가
주소 변환 시간 증가
8-5. 디멘드 페이징(가져오기 정책)
프로세스를 이루고 있는 모든 모듈이 올라와 실행되는게 아니라, 필요한 모듈만 올라와서 실행됨
지역성 이론
공간의 지역성: 현재 위치와 가까운 데이터 접근할 확률이 높음
시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음
디멘드 페이징은 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책. 필요한 페이지만 메모리에 적재하여 사용하는 가상 메모리 시스템의 핵심
메모리에 접근하는 시간이 보조저장장치 쪽으로 갈수록 느려짐. 디멘드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능향상을 위해선 스왑영역으로 데이터를 이동시키는 것을 최소화 시켜야함
접근 비트: 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트. 메모리에 읽기나 실행 작업을 했다면 1로 바뀜
변경 비트: 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트. 메모리에 쓰기 작업을 했으면 1로 바뀜
유효 비트: 페이지가 물리 메모리에 있는지 알려주는 비트. 만약 유효비트가 1이라면 페이지가 스왑영역에 있고 0이라면 물리 메모리에 있다는 의미
읽기/쓰기/실행 비트: 권한비트로 해당 메모리에 접근권한이 있는지 검사하는 비트
프로세스가 가상 메모리에 접근요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아내는데 만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킴
Page Fault가 발생하면 보조저장장치의 스왑영역에 접근하게 되고 해당 프로세스는 대기상태가 됨
그럼 스왑영역에 있는 데이터가 메모리로 올라가는 작업을 시작하고 메모리로 올라갔다면 대기상태에 있던 프로세스는 다시 실행하게됨
8-6. 페이지 교체정책
프로세스는 데이터 접근을 위해 메모리를 참조하는데 해당 데이터가 메모리에 없으면 Page Fault가 발생함. Page Fault가 발생하면 해당 페이지를 스왑영역에서 메모리로 불러들여야하는데 메모리가 꽉 차서 공간이 없다면 메모리에 있는 페이지 중에 하나를 선택해서 스왑영역으로 옮겨야함
메모리에 있는 페이지를 스왑영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책을 페이지 교체 정책이라고 함
무작위로 선택하는 방법(Random): 지역성을 고려하지 않기에 자주 사용되는 페이지가 선택될 때도 있어 성능이 별로 좋지 않음. 그래서 거의 사용되지 않음
메모리에 들어온지 가장 오래된 페이지를 선택하는 방법(FIFO): 페이지 교체 정책에서는 자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지 교체되면 공평하지 않음. 하지만 구현이 간단하고 성능도 꽤 괜찮아서 조금 변형해서 많이 쓰임
앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법(Optimum): 이 방법은 사실상 구현이 불가능한 이론적인 선택방법. 다른 알고리즘과 성능 비교를 할때 참조용으로 쓰임
최근에 가장 사용이 적은 페이지를 선택하는 방법(LRU - Least Recently Used): 지역성 이론의 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다는 결론. 실제로도 Optimum 알고리즘에 근접한 성능을 보임. 하지만 프로그램이 지역성을 띄지 않을땐 성능이 떨어짐
FIFO의 가장 큰 문제는 빌레이디라는 사람이 제시한 빌레이디의 역설
빌레이디의 역설이란 Page Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상을 말함. 빌레이디의 역설은 FIFO에서만 발생하며 LRU에서는 발생하지 않음
클락 알고리즘
LRU와 유사하게 만든 알고리즘. 클락 알고리즘은 접근비트 하나만 이용함. 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화함. 접근비트의 초기값은 0으로 설정되어있고 만약 페이지가 참조되었다면 1로 설정됨. 그럼 일정 시간간격마다 페이지가 참조되었는지 참조되지 않았는지 확인할 수 있음
클락 알고리즘은 페이지를 원형으로 연결함. 스왑 영역으로 옮길 페이지를 포인터로 가르키는데 이 포인터를 클락 핸드라고 부름. 클락 핸드는 시계 방향으로 돎
만약 Page Fault가 발생해서 스왑영역으로 보내야하는 상황이 나오면 클락 핸드는 현재 참조하고있는 페이지의 접근비트를 봄. 만약 접근비트가 1이라면 해당 접근비트를 0으로 바꾸고 클락 핸드가 다음 페이지를 가르킴. 반복하다가 접근비트가 0인 페이지를 발결하면 해당 페이지를 스왑 영역으로 보냄
향상된 클락 알고리즘의 경우 접근비트만 이용하는 것이 아니라 변경비트까지 봄
부득이하게 FIFO를 사용해야하는 경우가 있음
LRU에선 접근비트를 이용하는데 하드웨어적으로 접근비트를 지원하지 않는 시스템에선 FIFO를 이용할 수 밖에 없음. 어쩔 수 없이 FIFO를 사용하는 경우도 생기기에 FIFO의 성능을 높이기 위한 방법이 고안됨. 위 사진의 단점 때문에 2차 기회 페이지 교체 알고리즘이 고안됨
2차 기회 페이지 교체 알고리즘은 FIFO 방식에서 자주 사용하는 페이지에게는 또 한 번의 기회를 줌. FIFO 방식과 동일하게 동작하지만 만약 Page Fault 없이 페이지 접근만 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜주는 방식
8-7. 스레싱과 워킹셋
CPU 스케줄링의 목표는 CPU 사용률을 높이는 것
CPU 사용률을 높이기 위해서는 동시에 실행하는 프로세스의 수. 즉, 멀티프로그래밍 정도를 올려야함
동시에 실행하는 프로세스의 수가 늘어나면 어떤 프로세스가 I/O 작업으로 CPU를 사용할 수 없을 때 다른 프로세스로 컨텍스트 스위칭을 해서 CPU사용률을 높일 수 있음
멀티프로그래밍 정도가 올라가면 제한된 물리메모리에 모든 프로세스를 올려야하고 당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑영역에 저장되고 Page Fault가 많이 발생하게 됨
그러면 CPU가 작업하는 시간보다 스왑작업의 시간이 더 길어지고 CPU의 사용률은 떨어지게됨
CPU 스케줄러는 CPU 사용률이 떨어지면 더 많은 프로세스를 메모리에 올리게되고, 이렇게 반복하다 보면 어느새 CPU 사용률이 0에 가깝게 떨어지게 됨
CPU 사용률을 높이려 했지만 오히려 더 떨어지는 상황을 스레싱 이라고 함
하드웨어적으로 해결하려면 메모리 크기를 늘리면 됨. 하지만 무작정 메모리의 크기를 늘린다고 성능이 좋아지지는 않음. 그 이유는 현재 메모리가 프로세스들이 작업을 하는데 충분한 크기라서 스레싱이 발생하지 않는다면 크기를 늘려도 별 다른점이 없기 때문
한 프로세스가 실행될 때 너무 많은 페이지를 할당하면 다른 프로세스가 사용할 페이지가 줄어들기 때문에 효율이 떨어지게됨. 반대로 너무 적은 페이지를 할당하면 빈번한 Page Fault가 발생하고 스왑 요청이 많아 스레싱이 발생하게 됨
이를 해결하기 위해 프로세스가 실행되면 일정량의 페이지를 할당하고 만약 Page Fault가 발생하면 더 많은 페이지를 할당함. 반대로, Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비되는 것이라고 판단하고 페이지를 회수함
이렇게 하면 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정됨
현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올림
이를 워킹셋이라고 부름. 워킹셋은 프로세스가 준비상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용됨
섹션 9. 입출력 장치
9-1. 주변장치(I/O 디바이스, 저장장치)
주변장치는 그래픽 카드, HDD, SSD, 키보드, 마우스 등등 여러가지가 있음
주변장치들은 메인보드에 있는 버스로 연결됨
실제로 하나의 버스는 Address 버스, Data 버스, Control 버스로 이루어짐. 그래서 I/O 디바이스는 이 세 가지 버스를 따로 받을 수 있음. 그리고 각 하드웨어에 맞게 외부 인터페이스가 존재함. 또 장치의 상태와 데이터를 보관할 수 있는 각종 레지스터들이 존재함. 레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할을 함. 이 값들은 CPU가 사용하기 위해 메모리로 이동되기도 함
캐릭터 디바이스
마우스, 키보드, 사운드 카드, 직병렬 포트 등
데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음
블록 디바이스
HDD, SSD, 그래픽 카드 등
데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼
여러 주변장치는 메인보드 내의 버스로 연결
예전에는 주변장치들을 하나의 버스로 연결해서 사용함. CPU가 작업을 하다가 I/O 명령을 만나면 직접 입출력 장치에서 데이터를 가져왔는데 입출력중에는 다른 작업을 하지 못했기 때문에 CPU 사용률이 떨어짐. 이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러 개의 버스가 추가됨
CPU는 I/O명령을 만나면 입출력 제어기에게 입출력작업을 맡기고 다른 작업을 실행함
입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분함
시스템 버스는 고속으로 작동하는 CPU와 메모리가 사용하고 입출력 버스는 주변장치가 사용함
입출력 버스는 세부적으로 느린장치와 빠른장치를 구분하기 위해 다시 고속 입출력 버스와 저속 입출력 버스로 나뉨
느린 장치와 빠른 장치를 구분해 속도차이로 인한 병목현상을 해결함
그래픽 카드는 다루는 데이터가 매우 대용량이라 고속 입출력 버스로도 감당이 안됨. 그래서 그래픽 카드는 입출력 버스에 있지않고 시스템 버스에 바로 연결해 사용함
입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮김. 메모리는 CPU의 명령으로 움직이기에 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요함.
입출력 제어기가 CPU의 도움이 필요없도록 DMA 제어기가 추가됨
DMA는 직접 메모리 접근이라는 뜻. 입출력 제어기는 DMA로 데이터를 직접 메모리에 저장하거나 가져올 수 있음. CPU와 DMA가 사용하는 메모리가 겹쳐지지 않도록 CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나누는데 이를 Memory Mapped I/O라고 부름
9-2. 마우스/키보드
광학 카메라는 초당 1500회가 넘는 사진을 찍어 마우스의 디바이스 컨트롤러내 DSP로 보냄
DSP는 이 사진을 분석해 마우스의 X축, Y축 좌표 움직임을 캐치함
DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어감 → 마우스 드라이버는 운영체제에게 이벤트 신호 전송 → 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달 → 해당 애플리케이션은 마우스 이벤트 처리
키보드 또한 사용자가 키보드를 누르면 → CPU에게 인터럽트를 보내고 → 키보드 드라이버는 운영체제에게 이벤트를 보냄 → 그럼 운영체제는 Foreground 애플리케이션으로 이 이벤트를 전달 → 애플리케이션에서 해당 키에 맞는 동작을 수행함
9-3. 하드디스크/Flash Memory(SSD)
하드디스크(HDD)
동작 원리
자기 디스크를 기계적으로 회전
헤드로 데이터 읽기/쓰기
자기적 방식으로 데이터 저장
장점
저렴한 가격
대용량 저장 가능
수명이 긴 편
단점
느린 속도
물리적 충격에 약함
소음/발열 발생
전력 소비 큼
SSD(Solid State Drive)
동작 원리
반도체(플래시 메모리) 사용
전기적 방식으로 데이터 저장
기계적 부품 없음
장점
매우 빠른 속도
충격에 강함
소음 없음
전력 소비 적음
단점
상대적으로 비쌈
수명 제한(P/E 사이클)
용량당 가격이 높음
섹션 10. 파일시스템
10-1. 파일과 파일시스템
파일들은 하드디스크나 SSD와 같은 저장장치에 저장됨. 메모리와 마찬가지로 사용자가 직접 저장을 하게 되면 중요한 정보를 훼손할 수 있기에 사용자가 운영체제를 통해 요청하면 운영체제가 안정하제 저장해줌
운영체제는 파일을 관리하기 위해 파일관리자를 뒀는데 이를 파일시스템이라고 함
파일시스템의 기능
파일과 디렉토리 생성
파일과 디렉토리 수정/삭제
파일 권한 관리 - 다른 사용자로부터 파일을 보호하기 위해 접근 권한을 관리함. 요즘 운영체제는 다중 사용자기능을 지원하기 때문에 파일을 보호하기 위해 꼭 필요한 기능
무결성 보장 - 파일의 내용이 손상되지 않도록 무결성 보장
백업과 복구 - 예기치 못한 사고로부터 백업과 복구를 함
암호화 - 파일을 암호화해 파일을 보호하는 것
파일 시스템은 하드 디스크나 Flash Memory 같은 저장장치에 저장되기 때문에 전송 단위가 블록임
저장장치의 전송 단위는 블록이지만 사용자는 바이트 단위로 파일에 접근이 가능해야함. 이는 파일 관리자가 중간에서 관리해줌
운영체제는 파일을 관리하기 위해 정보를 보관하는 파일제어블록(File Control Block, FCB)을 가지고 있는데 이를 파일 디스크립터(File Descriptor)라고 부름. 파일 디스크립터는 파일마다 독립적으로 존재하고 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동함. 파일 디스크립터는 파일시스템(운영체제)이 관리하고 사용자가 직접 참조할 수는 없음
파일은 데이터의 집합으로 볼 수 있는데 이 데이터의 집합을 어떻게 구성하느냐에 따라 종류를 나눌 수 있음
순차파일구조 - 파일의 내용이 연속적으로 이어진 형태
장점: 모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순함
단점: 특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸림
직접 파일구조 - 저장하려는 데이터를 해시함수를 통해 저장위치를 결정하는 파일구조
장점: 해시함수를 이용하기에 데이터 접근이 굉장히 빠름
단점: 해시함수의 선정이 굉장이 중요하기에 해시함수를 잘 골라야 한다는 점과 저장공간이 낭비될 수 있다는 점. 예를 들어 흔히 쓰이지 않는 성씨가 있다면 해당 성씨에 저장되는 데이터는 굉장히 적음
인덱스 파일구조 - 인덱스 파일구조는 순차접근과 직접접근 방식의 장점을 취한 것으로 두 가지 방식 모두 가능함
10-2. 디렉토리
파일을 하나의 공관에만 보관하면 파일이 많아지면서 굉장히 복잡해짐. 그래서 관련있는 파일을 모아둘 수 있도록 디렉토리가 등장함. 디렉토리는 1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있음
디렉토리는 여러 층으로 구성되는데 최상위에 있는 디렉토리를 루트 디렉토리라고 부름. 유닉스나 리눅스의 경우 루트 디렉토리를 “/”로 표시. 윈도우는 보통 “C:”으로 표시
디렉토리도 파일임. 단지 일반 파일에는 데이터가 저장되어있고 디렉토리에는 파일 정보가 저장되어있음
다단계 디렉토리는 어떠한 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리구조
우리가 쓰는 운영체제에서는 트리 구조에서 순환이 생기는데 그 이유는 바로가기 기능이 있기 때문
윈도우즈에서는 바로가기를 통해 특정 디렉토리에서 다른 디렉토리로 바로 이동할 수 있기에 순환이 있는 트리구조
10-3. 파일과 디스크
파일시스템은 페이징과 같이 전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당해 관리함
일정한 크기로 나눈 공간을 메모리에선 페이지라 부르고 파잀시스템에선 블록이라고 부름. 한 블록의 크기는 1~8kb 정도. 파일시스템은 파일정보를 파일테이블로 관리하는데 여기엔 파일이 시작하는 블록의 위치정보도 담겨있음
하나의 파일은 여러 개의 블록으로 이루어져 있는데 이 블록들을 어떻게 연결하는지에 따라 연속할당, 불연속할당으로 나뉨
연속할당: 파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식
파일의 시작 블록만 알면 파일의 전체를 찾을 수 있음. 이 방식은 메모리에서 세그멘테이션 기법처럼 외부 단편화가 발생하기 때문에 실제로 사용되지 않는 방식
불연속할당: 디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식
이 분산된 블록은 파일시스템이 관리. 불연속방식으로는 “연결 할당”과 “인덱스 할당”이 있음
연결 할당
연결리스트로 구성하여 하나의 노드의 포인터를 이용해 다른 노드로 이동하여 모든 노드를 순환할 수 있음. 연결 할당은 파일에 속한 데이터를 연결리스트로 관리. 파일테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식
인덱스 할당
인덱스 할당방식은 테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아니라 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결함. 인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기에 테이블을 확장할 수 있음. 덕분에 파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터를 이용하고 파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있음. 만약 더 큰 데이터가 필요하다면 이중 간접 포인터, 삼중 간접 포인터를 이용할 수 있음. 이 방식은 i-node라는 이름으로 유닉스와 리눅스에서 많이 사용됨
알고리즘&자료구조
섹션 3. 알고리즘
삽입정렬(Insertion Sort)
정렬되지 않은 영역에서 데이터를 하나씩 꺼내어 정렬된 영역 내 적절한 위치에 삽입하여 정렬하는 알고리즘
장점: 이해와 구현이 간단함
단점: 성능이 좋지 않음. 큰 데이터일수록 매우 비효율적임
시간복잡도
O(n²)
병합정렬(Merge Sort)
분할해서 정복 하는 방식. 리스트를 절반으로 나누고 정렬한 후 병합하는식으로 진행됨
장점: 성능이 좋음. 큰 데이터에도 효율적임
단점: 이해와 구현이 어려움. 메모리 공간을 차지함
시간복잡도
O(n log n)
퀵정렬(Quick Sort)
분할해서 정복하는 방식. 피벗을 기준으로 재귀를 활용함
장점: 병합정렬보다 평균적으로 속도도 빠르고, 메모리 공간도 덜 차지함
단점: 피벗 선택에 따라 성능이 변하기에 불안정할 수 있음
시간복잡도
평균 - O(n log n), 최악 - O(n²)
동적 프로그래밍 - 메모이제이션
재귀를 사용한 하향식 접근 방법. 이전에 계산한 결과를 저장하여 재사용하는 기법으로 중복 계산을 피해 성능 향상
장점: 중복 계산 방지, 직관적인 구현, 필요한 결과만 저장
단점: 재귀로인한 스택 오버플로우
동적 프로그래밍 - 타뷸레이션
하위 문제부터 해결하는 상향식 접근 방법. 반복문을 사용함
장점: 메모이제이션에 비해 메모리 사용이 적음
단점: 모든 하위 문제를 계산해야함, 덜직관적인 구현, 때에 따라 불필요한 계산이 있을 수 있음
회고
3주 동안 나름 열심히하여 뿌듯하다.
댓글을 작성해보세요.
