[워밍업 클럽 3기 CS 전공지식] 3주차 회고
[3 주차 시작하기 전 다짐]
아침에 일어나서 주어진 강의 분량을 다 듣기
틈날 때 강의 듣기
저녁에 집에 와서 다시 듣기 또는 실습 진행
강의 들으면서 강의 노트도 실시간으로 작성하기!
강의 노트 작성 후 당일에 정리하기
[3 주차 회고]
칭찬할 점
스터디 계획에 맞춰서 모든 강의를 들었다.
=> 뿌듯하다.
아쉬운 점
강의를 듣고 정리를 하는 것이 어려웠다.
모든 내용이 다 중요해 보이고 알아야 하지 않을까 라는 생각에 내용 정리라고 하기에는 모든 내용을 적기만 했다.
=> 강의를 듣고 어떻게 정리해야 할 지 고민을 해봐야겠다.
역시 한 번 듣고 이해하는 건 어렵다. 반복해서 들어야 한다.
=> 스터디가 끝나고 나서도 반복해서 강의를 들어야겠다.
[강의 내용 정리]
[운영체제]
[가상메모리]
가상메모리 개요 (한 번 더 정리하기) - 부족한 물리메모리를 가상메모리를 이용해서 해결하는 방법
운영체제나 프로세스가 4GB 메모리에서 동작하도록 만들어졌다면 이보다 작은 메모리를 가진 컴퓨터는 실행되지 않는다.
이런 문제를 '가상메모리'는 완벽하게 해결했다.
프로세스는 물리메모리에 직접 접근할 일이 없고 메모리 관리자(MMU)에게 요청만 하면 된다.
메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시켜 준다.
가상메모리 시스템은 저장 공간보다 많은 프로세스가 있을 경우
물리메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리메모리로 가져와 실행시킨다.
동적 주소 변환(Dynamic Address Translation)
메모리 관리자는 물리메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주소를 물리 주소로 변환한다.
동적 주소 변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리메모리에 배치할 수 있다.
가상메모리 시스템에서는 운영체제 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당
메모리 분할 방식과 마찬가지로 가변 분할 방식과 고정 분할 방식으로 나뉜다.
가변 분할 방식
가상메모리 시스템에서는 가변 분할 방식을 이용한 세그멘테이션
단점
외부 단편화가 있다.
고정 분할 방식
고정 분할 방식을 이용한 페이징
단점
내부 단편화가 있다.
이 단점들을 보완한 '세그멘테이션-페이징 혼용' 기법을 사용한다.
가상 메모리 시스템에서 가상 주소는 메모리나 스왑 영역 한 곳 중에 위치
메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리
[가상메모리가 메모리 분할하는 방법] - 가상메모리가 메모리를 어떻게 분할하는지 알아보자
세그멘테이션(배치정책)
가변 분할 방식 이용
프로그램은 함수나 모듈 등으로 세그먼트를 구성
논리 주소
사용자와 프로세스, CPU가 바라보는 주소
물리 주소로 변환은 중간에서 메모리 관리자가 해준다.
메모리 관리자가 논리 주소를 물리 주소로 변환해주는 방법
메모리 관리자는 세그멘테이션 테이블이라는 것을 가진다.
세그멘테이션 테이블
Base Address 와 Bound Address 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산한다.
CPU에서 논리 주소를 전달해주면 메모리 관리자는 해당 논리 주소가 몇 번 세그먼트인지를 알아낸다.
메모리 관리자 내에 Segment Table Base Register(물리메모리n번지에 저장되어 있음, CPU를 사용하고 있는 프로세스의 물리주소값?이 저장되어 있음) 이용해서 물리메모리 내에 있는 세그멘테이션 테이블을 찾는다.
세그먼트 번호를 인덱스로 Base Address 와 Bound Address 를 찾는다.
Bound Address 는 세그먼트의 크기를 나타낸다.
메모리 관리자는 CPU에서 받은 논리 주소와 Bound Address 의 크기를 비교한다.
if (논리 주소 < Bound Address) 물리 주소 = 논리 주소 + Base Address
else if (논리 주소 > Bound Address) 메모리를 침범했다고 생각하고 에러를 발생시킨다.
장점
메모리를 가변적으로 분할할 수 있다.
코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있기 때문에 공유와 각 영역에 대한 메모리 접근 보호가 편리하다.
단점
가변 분할 방식의 단점인 '외부 단편화'가 발생한다.
페이징(배치정책)
고정 분할 방식을 이용한 페이징
세그멘테이션의 단점인 '외부 단편화'를 해결하기 위해 고안되었다. -> 조각모음은 오버헤드가 크다.
메모리를 할당할 때 정해진 크기의 페이지로 나눈다.
장점
모든 페이지는 크기가 같기 때문에 관리가 쉽다.
일정한 크기로 나눴기 때문에 외부 단편화 현상이 일어나지 않는다.
단점
'내부 단편화' 발생한다.
논리 주소 공간
사용자와 프로세스가 바라보는 주소 공간
페이징에서는 논리 주소 공간을 일정한 크기로 균일하게 나눈다.
이것을 '페이지'라고 부른다.
물리 주소 공간
실제 메모리에서 사용되는 주소 공간
페이지의 크기와 동일하게 나뉘는데 '프레임'이라고 부른다.
페이징에서 주소 변환을 어떻게 하는지 알아보자
세그멘테이션과 마찬가지로 메모리 관리자는 테이블을 가지고 있다.
이를 '페이지 테이블'이라고 부른다.
페이징의 주소 변환
1. CPU에서 논리 주소를 전달
2. 메모리 관리자는 논리 주소가 몇 번 페이지인지, 오프셋은 얼마인지 알아낸다.
3. 메모리 관리자 내에 Page Table Base Register(PTBR)를 이용해서 물리메모리에 있는 페이지 테이블을 찾는다.
4. 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리주소로 변환한다.
오프셋은 계산을 통해 쉽게 구할 수 있다.
페이지 테이블에 Invalid 로 표시되어 있으면 스왑 영역, 즉 하드디스크에 저장되어 있다는 의미이다.
5. 세그멘테이션과 마찬가지로 Page Table Base Register 는
운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해준다.
세그멘테이션과 페이징 차이점
페이지 크기
세그멘테이션
프로세스마다 크키가 달라 Bound Address 를 가지고 있다.
외부 단편화 발생한다.
페이징
모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address는 필요하지 않다.
외부 단편화는 발생하지 않지만 내부 단편화가 발생한다.
페이지 크기 때문에 생긴 차이
세그멘테이션
논리적인 영역별로 세그먼트를 나눈다.
세그먼트마다 크기를 다르게 나눌 수 있으니 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다.
페이징
페이지의 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라
페이지로 나누기 때문에 논리적인 영역을 나눌 수 없다.특정 영역만 딱 떼어내서 공유하거나 권한을 부여하는 게 어렵다.
페이징에서 신경써야 할 것
각 프로세스마다 페이지 테이블을 가지고 있다.
프로세스가 많아질수록 페이지 테이블도 많아지기 때문에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.
메모리 관리자가 참조하는 페이지 테이블도 물리메모리의 운영체제 영역에 저장되어 있기 때문에
페이지 테이블의 크기가 너무 크면 사용자 영역이 부족하게 된다.때문에 페이지 테이블의 크기를 적절하게 유지하는 것이 중요하다.
페이지드 세그멘테이션(배치정책)
세그멘테이션과 페이징을 혼합해 장점을 취한 방식
세그멘테이션 장점
가변 분할 장식으로 코드, 데이터, 스택, 힙 영역을 세그먼트로 관리할 수 있다.
다른 프로세스와 공유하기 편하고 각 영역에 대한 메모리 접근 보호를 하기 쉽다.
페이징 장점
고정 분할 방식으로 메모리를 효율적으로 관리할 수 있다.
오버헤드가 적다.
메모리 접근 권한
메모리의 특정 번지에 부여된 권한
읽기(Read), 쓰기(Write), 실행(Execute) 세 가지가 있다.
예시
0x0~0x1000까지는 읽기 권한만 설정
0x1000~0x2000까지는 읽기, 쓰기 권한 설정
프로세스 영역마다 접근 권한이 있다.
코드 영역 : 읽기/실행 권한
프로그램 그 자체이므로 수정되면 안된다.
데이터 영역 : 읽기/(쓰기) 권한
일반 변수, 전역 변수, 상수로 선언한 변수가 저장된다.
실행 권한은 없다.
스택, 힙 영역 : 읽기/쓰기 권한
실행 권한은 없다.
메모리 접근 권한에 대한 검사
가상주소에서 물리주소로 변환될 때마다 일어난다.
권한을 위반하면 에러를 발생 시킨다.
테이블 구성
세그멘테이션 테이블에 권한 비트 추가
Base Address는 페이지 넘버로 변경 (페이지 테이블의 인덱스를 가리킴)
Bound Address는 페이지 개수로 바뀜
페이지 테이블은 프레임 번호로 구성
단점
물리메모리에 접근하기 위해서 메모리에 접근을 두 번해야 한다.
첫 번째 메모리 접근은 세그멘테이션 테이블을 참조
두 번째 메모리 접근은 페이지 테이블을 참조
이런 단점 때문에 현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 사용한다.
메모리 계층 구조
메모리는 레지스터, 캐시, 메인메모리(RAM), 보조저장장치(HDD, SSD) 로 나눌 수 있다.
레지스터
CPU 내에 존재하고 CPU의 한 사이클에 접근할 수 있어서 빠르다.
캐시
CPU의 수 사이클에서 수십 사이클에 접근할 수 있다.
메인메모리
수백 사이클이 걸린다.
보조저장장치
수백만 사이클이 걸려 오래 걸린다.
메모리에 접근하는 시간이 보조저장장치 쪽으로 갈수록 느려진다.
디맨드 페이징(가져오기 정책)
프로세스가 실행될 때 모든 모듈(코드, 데이터, 힙, 스택 영역)이 메모리에 올라오는 것이 아니라 필요한 모듈만 올라와서 실행된다.
조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑 영역으로 이동시키는 정책이다.
=> 지역성 이론을 구현한 정책지역성 이론
조만간 쓰일 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑 영역으로 보내 성능을 향상시킨다.
스왑 영역을 보조저장장치에 저장하는데 성능 향상을 위해서는 스왑 영역으로 데이터를 이동시키는 것을 최소화해야 한다.
보조저장장치에 접근하는 건 최대한 적을 수록 좋다.
스왑 영역에서 물리메모리로 데이터를 가져오는 것을 스왑인이라고 부른다.
물리메모리에서 스왑영역으로 데이터를 보내는 것을 스왑아웃이라고 부른다.
페이지 테이블
가상주소가 주어지면 메모리 관리자는 페이지 테이블을 참조해서 물리메모리가 있는 프레임을 알아내거나 스왑영역의 위치를 알아내야 하는데 이를 위해 페이지 테이블에 여러가지 비트가 있다.
접근 비트
페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트
메모리에 읽거나 실행 작업을 했다면 1로 바뀐다.
변경 비트
페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트
메모리에 쓰기 작업을 했으면 1로 바뀐다.
유효 비트
페이지가 물리모리에 있는지 알려주는 비트
1이라면 페이지가 스왑 영역에 있고 0이라면 물리메모리에 있다.
권한 비트
읽기/쓰기/실행
해당 메모리에 접근 권한이 있는지 검사하는 비트
프레임
가상 메모리 주소가 물리메모리와 스왑영역에 참조되는 세 가지 상황
1. 스왑이 필요없는 경우
페이지가 물리메모리에 있다.
2. 스왑 영역에 있는 데이터를 참조하는 경우
페이지가 스왑영역에 있다는 뜻
그럼 물리메모리에 적절히 빈 공간을 찾는다.
스왑 영역에 저장된 것을 물리메모리 프레임으로 가져오고
페이지 테이블에서 해당 엔트리의 유효비트를 0으로 프레임 넘버를 수정한다.
그리고 프로세스에게 데이터를 참조하게 해준다.
3. 물리메모리가 꽉 찼을 때 스왑 영역에 있는 데이터를 참조하는 경우
페이지가 스왑영역에 있다는 뜻
물리메모리로 가져오기 위해 적절히 빈 곳을 찾지만 꽉 차서 여유가 없다.
그럼 현재 물리메모리에서 필요하지 않다고 판단하는 영역을 스왑 영역으로 옮긴다.
물리메모리에 필요없는 영역을 스왑영역으로 옮기면 페이지 테이블에서 해당 영역의 유효 비트를 1로, 프레임 넘버를 변경한다.
이제 물리메모리에 공간이 생겼기 때문에 스왑 영역에 있는 필요한 영역을 물리메모리로 가져온다.
페이지 테이블에서 옮겨온 영역의 유효비트를 0으로 프레임 넘버를 수정한다.
그리고 프로세스에게 데이터를 참조하게 해준다.
페이지 교체정책
스왑 영역에서 물리메모리로 가져오는 스왑인과 물리메모리에서 스왑영역으로 보내는 스왑아웃을 할 때 어떤게 적절한 지는 운영체제가 판단한다.
이 판단하는 것을 페이지 교체 알고리즘이라고 부르고 페이지 교체 알고리즘에 대해서는 알아보자.
메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 보낼 지 결정하는 페이지 교체 정책
첫 번째 : 무작위로 선택
무작위로 선택해서 교체
지역성을 고려하지 않기 때문에 자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다.
거의 사용되지 않는다.
두 번째 : 메모리에 들어온 지 가장 오래된 페이지를 선택하는 방법
FIFO(First In First Out)
자주 쓰이는 페이지가 먼저 들어왔다는 이유로 해당 페이지가 교체되면 공평하지 않다.
구현이 간단하고 성능도 괜찮아서 조금 변형해서 많이 쓰인다.
세 번째 : 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법
Optimum
사실상 구현이 불가능한 이론적인 선택하는 방법
앞으로 누가 가장 사용되지 않을지 모른다.
구현이 불가능해서 필요 없을 것 같지만 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰인다.
네 번째 : 최근에 가장 사용이 적은 페이지를 선택하는 방법
LRU(Least Recently Used)
Optimum 알고리즘에 근접한 성능을 보인다.
페이지 테이블 엔트리는 여러 개의 비트와 페이지 넘버가 저장되지만 이곳에 시간을 기록하려면 비트가 많이 필요하게 된다.
많은 비트를 준비하기는 어려우니 LRU를 구현할 때는 접근 비트를 이용해서 LRU에 근접하게 구현한다.
Page Fault 발생
메모리에 페이지가 없고 스왑 영역에 페이지가 있는 경우
Optimum
이후에 어떤 요청이 있는지 전부 알고 있기 때문에 뒤를 훑어본다.
FIFO
먼저 들어온 페이지가 먼저 나간다.
LRU
최근에 가장 사용이 적은 페이지가 나간다.
최근에 들어온 페이지의 참조 수를 계산한다.
LRU 와 유사하게 구현하는 방법 - 클락 알고리즘(Clock Algorithm)
클락 알고리즘은 접근 비트 하나만 이용한다.
일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화한다.
접근 비트의 초기값은 0으로 설정되어 있다.
만약 페이지가 참조되었다면 1로 설정된다.
그럼 일정 시간 간격마다 페이지가 참조 되었는지 참조되지 않았는지 확인할 수 있다.
클락 알고리즘은 페이지를 원형으로 연결한다.
스왑영역으로 옮길 페이지를 포인터로 가리키는데 이 포인트를 '클락 핸드'라고 부른다.
클락 핸드는 시계 방향으로 돈다.
만약 Page Fault 가 발생해서 스왑영역으로 보내야하는 상황이 나오면 클락 핸드는 현재 참조하고 있는 페이지의 접근 비트를 본다.
만약 접근비트가 1이라면 해당 접근비트를 0으로 바꾸고 클락핸드가 다음 페이지를 가리킨다.
반복하다가 접근비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.
메모리에서 접근비트가 0인 페이지를 스왑영역으로 보냄
2차 기회 페이지 교체 알고리즘
FIFO 방식에서 자주 사용하는 페이지에게 또 한 번의 기회를 준다.
FIFO 방식과 동일하게 동작하지만 만약 Page Fault 없이 페이지 접근에 성공했다면
해당 페이지를 큐의 맨 뒤로 이동 시켜 수명을 연장 시켜주는 방식이다.LRU 보다는 성능이 좋지 않고 FIFO 보다는 성능이 좋다.
[스레싱과 워킹셋]
스레싱
CPU 사용률을 높이려고 했지만 더 떨어지는 상황
멀티 프로그래밍 정도(동시에 실행하는 프로세스의 수)가 늘어나면 제한된 물리메모리에 모든 프로세스를 올려야 하고
당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑 영역에 저장되고 Page Fault 가 많이 발생한다.
그러면 CPU 가 작업하는 시간보다 스왑 작업의 시간이 더 길어지고 CPU 사용률은 떨어진다.CPU 스케줄러는 CPU 사용률이 낮아지면 더 많은 프로세스를 메모리에 올리게 되고 프로세스를 더 실행시켜 CPU 사용률을 올린다.
이렇게 반복하다 보면 어느새 CPU 사용률이 0에 가깝게 떨어진다.
근본적인 원인은 물리메모리의 크기가 부족한 것이다.
하드웨어적으로 해결
메모리 크기를 늘린다.
소프트웨어적으로 해결
프로세스가 실행되면 일정량의 페이지를 할당
Page Fault 가 발생하면 더 많은 페이지를 할당
Page Fault 가 너무 적게 발생하면 메모리가 낭비되는 것이라고 판단해 페이지를 회수
프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정됨
적절한 페이지 수를 결정했다면 어떤 페이지들을 유지할 것인지 알아야 한다.
지역성 이론을 따른다.
현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 메모리에 올린다.
이를 워킹셋이라고 부른다.
워킹셋은 프로세스가 준비 상태에서 실행 상태가 되는 컨텍스트 스위칭을 할 때 사용한다.
[입출력 장치]
주변장치(I/O 디바이스, 저장장치)
그래픽 카드, 하드디스크, SSD, 키보드, 마우스 등이 여러 가지가 있다.
주변 장치 내부구조
주변 장치들은 메인보드에 있는 버스로 연결한다.
하나의 버스는 Address 버스와 Data 버스, Control 버스로 이루어져 있다.
장치의 상태와 데이터를 보관할 수 있는 각종 레지스터들이 존재한다.
이 레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할을 한다.
CPU가 사용하기 위해 메모리로 이동하기도 한다.
주변 장치 2가지
데이터의 전송 단위가 캐릭터(글자), 블록으로 나눈다.
캐릭터 디바이스
마우스, 키보드, 사운드 카드, 직렬/병렬 포트 등이 있다.
데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작다.
상대적으로 적은 양의 데이터를 전송한다.
블록 디바이스
하드디스크, SSD, 그래픽 카드 등이 있다.
데이터 전송 단위가 블록(범위)으로 상대적으로 크기가 크다.
많은 양의 데이터를 전송한다.
입출력 제어기(I/O Controller)
CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 실행한다.
입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분한다.
시스템 버스
고속으로 작동하는 CPU와 메모리가 사용한다.
그래픽 카드
대용량 데이터로 고속 입출력 버스로 감당이 안된다.
입출력 버스에 있지 않고 시스템 버스에 바로 연결해 사용한다.
입출력 버스
주변장치가 사용한다.
세부적으로 느린 장치와 빠른 장치를 구분하기 위해 고속 입출력 버스와 저속 입출력 버스가 있다.
느린 장치와 빠른 장치를 구분해 속도 차이로 인한 병목 현상을 해결했다.
하드디스크/Flash Memory(SSD)
주변 장치 중 블록 디바이스의 한 종류 하드디스크
기계적으로 헤드를 움직여 속도가 많이 느리고 소음이 난다.
자기적으로 처리해서 자석을 가져다 대면 데이터가 손상된다.
스핀들처럼 회전축 같은 것들이 있어서 충격에 매우 약하다.
블록 디바이스의 또 다른 종류 SSD
하드디스크보다 Flash Memory를 더 많이 사용한다.
전기적으로 읽기 때문에 굉장히 빠르고 조용하다.
충격에 약하지 않다.
데이터 손상이 되지 않는다.
단점
특정한 지점에 데이터를 썼다면 덮어쓰기가 불가능하다.
똑같은 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야하는데
지우기 가능한 횟수가 정해져 있다.똑같은 지점에 지우기/쓰기를 계속하면 망가져 사용할 수 없다.
[파일 시스템]
파일과 파일시스템
파일은 하드디스크나 SSD와 같은 저장장치에 저장된다.
사용자가 운영체체를 통해 요청하면 운영체제가 안전하게 저장해준다.
운영체제는 파일을 관리하기 위해 파일 관리자를 뒀는데 이를 파일시스템이라고 한다.
파일 관리자
파일 테이블을 이용해서 파일을 관리한다.
파일 시스템의 기능
파일과 디렉토리 생성
파일과 디렉토리 수정/삭제
파일 권한 관리
다른 사용자로부터 파일을 보호하기 위해 접근 권한을 관리
무결성 보장
파일의 내용이 손상되지 않도록 무결성을 보장
백업과 복구
예기치 못한 사고로부터 백업과 복구
암호화
파일을 암호화해 파일을 보호
파일 시스템 전송 단위 블록
하드디스크와 Flash Memory(SSD) 같은 저장 장치에 저장되기 때문에 단위가 블록이다.
저장 장치의 전송 단위는 블록이지만 사용자는 바이트 단위로 파일에 접근 한다.
이는 파일 관리자가 중간에서 관리해준다.
파일
헤더와 데이터로 이루어져 있다.
헤더에는 파일의 속성들이 담겨져 있다.
운영체제는 파일을 관리하기 위해 파일 제어 블록(File Control Block,FCB)에 정보를 보관한다.
이를 파일 디스크립터(File Descriptor)라고 부른다.
파일 시스템(운영체제)이 관리한다.
사용자가 직접 참조할 수 없다.
사용자는 파일 시스템이 건네준 파일 디스크립터로 파일에 접근할 수 있다.
파일은 데이터의 집합으로 어떻게 구성하느냐에 따라 종류를 나눌 수 있다.
순차 파일 구조
파일의 내용이 연속적으로 이어진 형태
장점
모든 데이터가 순서대로 기록되기 때문에 공간의 낭비가 없고 구조가 단순하다.
단점
특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸린다.
직접 파일 구조
저장하려는 데이터를 해시 함수를 통해 저장 위치를 결정하는 파일 구조
자료구조에서 해시 테이블이라는 이름으로 불리는 방식
예시: 데이터 포맷인 json
장점
해시 함수를 이용하기 때문에 데이터 접근이 빠르다.
단점
해시 함수의 선정이 중요하다.
해시 함수를 잘 골라야 한다는 점과 저장 공간이 낭비될 수 있다.
인덱스 파일 구조
순차 접근과 직접 접근 방식의 장점을 취한 것 -> 두 가지 방식 모두 가능
디렉토리
관련 있는 파일을 모아둘 수 있다.
1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있다.
여러 층으로 구성되어 있다.
최상위에 있는 디렉토리를 루트 디렉토리라고 부른다.
유닉스나 리눅스의 경우 루트 디렉토리를 "/"로 표시하고
디렉토리와 디렉토리 구분을 위해서도 "/"를 사용한다.
윈도우즈의 경우 루트 디렉토리는 파티션 이름으로 사용하는데 보통 "C:"로 표시한다.
디렉토리와 디렉토리 구분을 "\"로 한다.
디렉토리도 파일이다.
일반 파일에는 데이터가 저장되어 있다.
디렉토리에는 파일 정보가 저장되어 있다.
디렉토리 구조
초기 파일 시스템의 디렉토리는 단순한 구조
루트 디렉토리에만 디렉토리가 존재할 수 있다.
다른 디렉토리에서는 하위 디렉토리는 만들 수 없다.
파일이 많아지면서 다단계 디렉토리 구조 등장
디렉토리에서 하위 디렉토리를 만들 수 있는 트리 구조이다.
우리가 쓰는 운영체제는 트리 구조에서 순환이 생긴다.
바로가기 기능 때문이다.
윈도우즈는 바로가기 아이콘을 만들어 특정 디렉토리에서 다른 디렉토리로 바로 이동하는 기능이 있기 때문에 순환이 있는 트리 구조이다.
파일과 디스크
전체 디스크 공간을 일정한 크기로 나누고 그 공간에 주소를 할당해 관리한다.
일정한 크기로 나눈 공간을 파일 시스템에서는 블록이라고 부른다.
한 블록의 크기는 1~8KB 이다.
파일 시스템은 파일 정보를 파일 테이블로 관리하는데 파일이 시작하는 블록의 위치 정보도 담겨있다.
하나의 파일은 여러 개의 블록으로 이루어져 있다.
이 블록들을 어떻게 연결하는 지에 따라 "연속할당"과 "불연속할당"으로 나눌 수 있다.
"연속 할당"
파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식
파일의 시작 블록만 알면 파일의 전체를 찾을 수 있다.
외부 단편화가 발생, 사용되지 않는 방식이다.
"불연속할당"
디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식
분산된 블록은 파일 시스템이 관리한다.
불연속 방식으로 "연결 할당"과 "인덱스 할당"이 있다.
"불연속할당(연결할당)"
파일에 속한 데이터를 연결리스트로 관리
파일 테이블에 시작 블록에 대한 정보만 저장
연결리스트를 이용해 다른 블록에 접근하는 방식
시작 위치에서 null을 만날 때까지 데이터를 참조하면 모든 데이터를 얻을 수 있다.
"불연속할당(인덱스할당)"
테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아니라
데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블을 확장할 수 있다.
디스크
일정한 크기의 블록으로 나뉘고 블록의 크기는 1~8KB 이다.
디스크를 1KB 로 나누면 낭비되는 공간을 줄일 수 있지만 관리해야 할 블록의 수도 많아진다.
8KB 로 나누면 관리해야 하는 블록의 수는 적지만 내부 단편화로 낭비되는 공간이 많아진다.
파일 시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있다.
특정 파일을 삭제한다면 파일 시스템은 파일의 모든 정보를 지우는 것이 아니다.
파일 테이블의 헤더를 삭제하고 free block list에 추가한다.
이렇게 처리하면 사용자는 파일이 삭제된 것처럼 느껴지는데 사용했던 블록의 데이터는 그대로 남아있다.
범죄를 저질러서 증거를 인멸하더라도 포렌식을 통해 데이터를 복구할 수 있다.
[자료구조와 알고리즘]
정렬 - 삽입정렬
동작
선택 정렬과 마찬가지로 배열을 두 영역으로 나눠서 진행
정렬되지 않은 영역에서 데이터(가장 앞에 있는 숫자)를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘
정렬되지 않은 영역의 첫 번째 원소를 정렬된 영역의 가장 뒤에 있는 원소부터 역순으로 비교
성능
버블정렬, 선택정렬과 같은 패턴 : 이중 for문
O(n제곱)
장점
이해가 쉽고 구현이 간단하다.
단점
성능이 좋지 않다.
정렬 - 병합정렬
해결하기 힘든 문제가 발생한다면 한 번에 해결하려 하지 말고,
해결하기 쉬울 정도로 문제를 쪼갠 다음 하나씩 해결 - 분할 정복(divide and conquer)예시 8개 요소를 정렬해야 한다면
4개로 반으로 쪼갠다.
2개로 반으로 쪼갠다.
1개로 반으로 쪼갠다.
1개부터 2개로 올라갈 때 정렬을 한다.
재귀 함수를 호출한 모양과 비슷하다.
병합정렬은 재귀로 정렬하는 알고리즘
성능
성능을 평가하는 부분은 흩어진 배열을 합치는 부분이다.
하나의 데이터와 하나의 데이터가 두 개로 합쳐질 때 비교 연산을 두 번 한다.
두 개의 데이터와 두 개의 데이터가 네 개로 합쳐질 때 비교가 네 번 이루어 진다.
각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 logn이다.
=> 분할된 배열을 병합할 때는 n개의 데이터를 n번 비교하므로 n, nlogn 곱해서 O(nlogn) 성능이 나온다.
장점
성능은 O(nlogn)으로 지금까지 배운 정렬보다 성능이 훨씬 좋다.
단점
재귀적인 기법으로 이해하기 어렵다.
구현이 어렵다.
정렬 - 퀵정렬
병합정렬과 같이 분할 정복 알고리즘
재귀를 사용한다.
한 번 진행될 때마다 피벗이 정렬되고 정렬된 배열을 좌우로 나눠서 같은 방식으로 재귀 호출을 해 모든 배열을 정렬한다.
동작 전 준비
정렬하기 전 배열에 있는 숫자 중 하나를 '피벗'으로 설정
피벗 설정은 여러 가지가 있는데 설명은 배열의 가장 왼쪽에 있는 값을 피벗으로 설정
배열의 시작과 끝을 가리키는 left 와 right 로 설정
피벗을 제외한 배열의 양쪽에서 값을 비교하기 위한 변수 필요
왼쪽에서 오른쪽으로 이동하는 변수를 leftStartIndex
오른쪽에서 왼쪽으로 이동하는 변수를 rightStartIndex
동작
1. leftStartIndex가 이동, 오른쪽으로 이동하다가 피벗보다 큰 값을 만나면 멈춘다.
2. rightStartIndex가 이동, 왼쪽으로 이동하다가 피벗보다 작은 값을 만나면 멈춘다.
3. leftStartIndex 의 값과 rightStartIndex 의 값을 교환해준다. (swap)
4. 1~3 반복
5. leftStartIndex 와 rightStartIndex 가 서로의 방향으로 이동하다 보면 결국에는 서로 지나치게 된다. 그러면 더이상 이동하지 않고 멈춘다.
6. 피벗과 rightStartIndex 의 값을 교환해준다.
피벗이 중간에 위치하게 된다.
7. 피벗 왼쪽에 있는 배열을 1~6 반복하면 왼쪽의 모든 데이터가 정렬된다.
8. 피벗 오른쪽에 있는 배열을 1~6 반복하면 오른쪽의 모든 데이터가 정렬된다.
성능
피벗을 기준으로 반을 나눈다. -> 수가 1개 남을 때까지 반으로 나눈다.
=> logn나눠진 단계를 배열의 원소 수 n만큼 진행
평균적인 경우 세타(nlogn)
피벗이 매번 배열의 반을 가르는 경우
최악의 경우
피벗이 중간이 아닌 한쪽으로 치운친 경우 - 피벗이 배열을 반 가르지 않고 한 쪽에 쏠리는 경우
O(n제곱)
하지만 대부분의 경우 좋은 피벗을 선택하고 최악의 경우가 발생할 확률은 극히 낮다.
그래서 평균적인 성능을 말하면 된다.
성능만 보면 병합정렬이 더 좋아보이지만 실제로 비교하면 퀵 정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가된다.
장점
성능은 O(nlogn)으로 지금까지 배운 정렬보다 성능이 훨씬 좋다.
단점
재귀적인 기법으로 이해하기 어렵다.
구현이 어렵다.
동적 프로그래밍 - 메모이제이션
이전에 재귀를 이용해서 큰 문제를 작은 문제로 분할해서 해결했고 이를 분할 정복이라고 했다.
하지만 재귀를 사용하면 함수가 호출되어 콜스택의 영역을 차지하는 단점 외에도 성능에 크게 영향을 미치는 단점이 있다.
예시
피보나치 수열
재귀를 이요해서 하향식 계산을 해서 간단하게 문제를 해결할 수 있다.
그런데 이미 계산했던 걸 또 다시 계산하는 경우가 발생한다.
이 중복 계산으로 인해 낭비되는 시간을 줄여야 한다.
계산 결과를 저장하면 된다. 같은 계산이 필요할 때 저장된 결과를 사용하면 된다.
그러면 함수의 호출 수가 줄어들고 성능이 향상된다.
메모이제이션
계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법
동작
계산하려는 데이터가 있는지 '검색'하고 없다면 함수를 호출해서 계산을 하고 그 결과를 '저장' 시키면 된다.
해시 테이블의 자료구조를 사용한다.
해시 테이블 장점
빠른 데이터 탐색, 삽입, 삭제
해시 테이블의 key로 계산하려는 값을, value로 계산 결과를 저장해주면 계산하려는 값의 검색을 아주 빨리 할 수 있다.
결과만 보면 재귀, 메모이제이션 성능 차이를 못 느낀다.
계산할 값이 커질 수록 엄청나게 차이가 난다.
피보나치 재귀 성능 O(2의 제곱)
피보나치 메모이제이션 성능 O(n)
메모이제이션 기법이 강력하지만 속도를 위해서 메모리(공간)을 사용한다.
동적 프로그래밍 - 타뷸레이션
분할 정복을 하기 위해서 하향식 계산 방식인 메모이제이션을 이용했다.
메모이제이션 장점
재귀적인 기법으로 어려운 문제를 단순히 푼다.
계산 결과를 해시 테이블에 저장하고 재사용하기 때문에 속도가 빠르다.
메모이제이션 단점
함수를 여러 번 호출하는 재귀를 사용하기 때문에 함수 하나를 호출하는 것보다 오버헤드가 더 크다.
타뷸레이션
상향식 계산 방식으로 계산에 필요하지 않을 수도 있는 값도 미리 계산해 테이블에 저장한다.
계산되어 저장된 값을 필요할 때 사용해 빠르게 계산한다.
피보나치 구현 비교
메모이제이션
여러 번의 함수 호출로 메모리 공간에 스택을 차지
해시 테이블 공간까지 차지하기 때문에 메모리 더 많이 사용
타뷸레이션
적은 메모리 사용인데도 빠른 시간으로 해결한다.
분할 정복을 해결할 때 재귀가 더 직관적이라면 메모이제이션을 이용하는 것이 유리하다.
재귀가 직관적이지 않을 경우 상향식 접근인 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 해결할 수 있다.
※ '강의 내용 정리' 출처
[인프런 / 그림으로 쉽게 배우는 운영체제 (감자) / 섹션 8~10]
[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 3 (유닛 6~10)]
답변 0