인프런 워밍업 클럽 스터디 2기 CS 3주차 발자국
운영체제
섹션8
- 가상메모리 개요
컴퓨터마다 메모리의 크기는 다르다.
만약 운영체제 혹은 프로세스가 4GB메모리를 기준으로 만들었다면 그 이하의 메모리를 가진 컴퓨터에서는 실행되지 않을 것이다.
위와 같은 문제를 가상메모리는 완벽히 해결하였다.
프로세스(프로그램)를 만드는 개발자는 물리적인 메모리의 크기를 생각하지 않고 개발한다.
그 이유는 프로세스 관리자가 서로를 연결시키기 때문에 직접적인 연결을 생각할 필요가 없는 것이다.
이론적으로 가상메모리는 크기가 무한대이지만 거의 2^(CPU의 비트수)로 생각한다.
만약 4GB 메모리가 4GB짜리 5개의 프로세스를 실행시킨다면 일반적으론 부족할것이다.
하지만 물리메모리에 있는 스왑영역을 통해 그때마다 필요한 프로세스만 가져와서 실행시키고 다시 넣는다면 4GB메모리로도 모두 실행시킬 수 있다.
메모리 관리자는 물리영역+스왑영역을 합쳐서 가상주소를 물리주소로 바꾼다. 이 과정을 DAT(동적주소변환)이라고 한다.
메모리를 사용하기 위해 가변 분할 방식(세그멘테이션)과 고정 분할 방식(페이징)이 있다.
각각의 단점과 장점이 있기 때문에 둘이 합친 혼용기법을 사용한다.
매핑 테이블로 관리되면 프로세스와 메모리+스왑영역이 1:1 느낌으로 관리된다.
3주차에 시작된 질문항
1. 세그멘테이션과 페이징이 뭐지
2.뭔가 그림으로 보면 어느정도 이해가 되기는 하는데 글로 혼용기법을 서술을 못하겠다...
- 세그멘테이션(배치정책)
세그멘테이션에서 프로그램은 함수나 모듈등으로 세그먼트를 구성한다.
사용자 관점에서 보면 코드 세그먼트, 데이터가 들어있는 데이터 세그먼트 등으로 있다.
사용자,프로세스,CPU관점에서는 모두 논리주소를 사용한다. MMU가 논리주소를 물리주소로 바꾸는 것이다.
MMU는 세그멘테이션 테이블을 통해 알맞는 물리 메모리에 할당한다.
MMU는 CPU에게서 받은 논리주소(세그멘테이션 테이블)가 Bound address보다 작다면 둘이 더해 물리주소를 구하고 아니라면 메모리 침범으로 생각해서 에러를 낸다.
세그멘테이션은 여러 영역을 모듈로 처리할 수 있다는 장점이 있고 공유와 메모리 접근보호가 편리하다.
단점으로 외부 단편화가 있다.
1. 진지하게 외부 단편화가 기억이 안난다.. 다시 보고 와야겠다
2.어째서 메모리 침범인지 까먹었다..
- 페이징(배치정책)
메모리를 할당할 때 메모리를 일정한 페이지로 나눈다.
일정하게 나누기 때문에 외부단편화가 일어나지 않는다.
논리주소공간 : 사용자와 프로세스가 바라보는 주소공간
물리주소공간 : 실제 메모리에서 사용되는 공간
페이징에서 논리주소공간을 일정하게 나누는 것을 페이지라고 부른다.
물리주소공간도 페이지와 동일한 크기로 나뉘는데 이것은 프레임이라고 부른다.
여기도 메모리 관리자가 테이블을 가지고 있는데 이를 페이지 테이블이라고 부른다.
CPU요청->MMU확인->메모리의 테이블 참조->프레임 번호 알아내기->물리주소 변환
페이지 테이블에 invalid로 써있으면 스왑영역에 있다는 뜻이다.
예를 들어 4GB메모리면 16mb씩 256개의 페이지가 생긴다.
그 뒤 물리주소공간도 16mb로 나눈다.
페이지 테이블에는 페이지 배열의 인덱스가 된다, 해당 인덱스로 가면 프레임을 얻을 수 있다.
페이지 넘버 = 논리주소 / 페이지 크기
오프셋 = 논리주소 % 페이지 크기
둘의 차이점
페이지의 크기
1. 자꾸 앞내용을 까먹어서 무슨 단어였지 찾아보는 상황이 많아지고 있다...
2. 뭔가 이해가 되기는 하는데 각각의 이론끼리 연결되는 느낌이 들지가 않는다..
-페이지드 세그멘테이션(배치정책)
세그멘테이션과 페이징은 각각의 장단점이 있다.
메모리 접근권한 : 메모리에 부여된 권한으로 읽기, 쓰기, 실행이 있다.
프로세스에서 각 영역마다 권한이 다르다.
세그멘테이션 테이블과 페이지 테이블을 합쳐 페이지드 세그멘테이션이 만들어진다.
세그멘테이션 테이블에 권한 비트가 추가되고 Base address가 페이지 넘버로 바뀌고 Bound Address가 페이지 개수로 바뀐다.
만약 접근 권한을 위반한 요청을 하면 프로세스를 종료시킨다.
- 디맨드 페이징(가져오기 정책)
90:10이라는 법칙이 있다, 이것은 작동시간의 90%가 10%의 코드에서 사용된다는 법칙이다.
지역성 이론
ㄴ공간의 지역성 : 현재 위치와 가까운 데이터에 접근할 확률이 높음
ㄴ시간의 지역성 : 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음
지역성 이론은 쓰일 것 같은 데이터를 메모리에 두고 아닌 데이터는 스왑 영역에 두는 것이다.
레지스터<캐시<메인 메모리<보조저장장치 순으로 데이터를 가져오는 시간이 걸린다.
디멘드 페이징은 자주 쓰일 것 같은 데이터를 스왑영역(보조저장장치)에 넣는 것을 줄이는 것이다.
가상메모리의 크기는 메인메모리+스왑영역이다
메인->스왑은 스왑아웃이라 하고
스왑->메인을 스왑인이라고 한다.
페이지 테이블을 통해 물리메모리와 스왑영역에서 호출된 데이터를 가져오는 과정(스왑인, 스왑아웃)을 결정하는 것은 페이지 교체 알고리즘에 따라 결정된다.
1.스왑인과 스왑아웃을 사용하는 과정을 서술하려고 했는데 머릿속에서 정리가 되지를 않는다..
- 페이지 교체정책
page fault가 생겼고 현재 메모리가 가득 차있을 때 메모리에서 스왑 영역으로 페이지를 넣고 가져와야 한다.
이 과정에서 어떤 페이지를 스왑영역으로 옮길지를 결정하는 것이 페이지 교제정책이다.
정책도 여러가지가 있다.
랜덤 -> 당연히 성능이 좋지 않다
가장 오래된 페이지 선택 -> FIFO가 여기서는 적절하지 않다 -> 하지만 성능이 무난하고 구현이 간단해서 약간 변형해서 쓰인다
앞으로 가장 쓰이지 않을 페이지 선택 -> 구현은 불가능하지만 성능 비교용으로 쓰인다
최근 가장 사용이 적은 페이지 선택(LRU) -> 3번에 가장 가까운 성능을 보인다 -> 허나 지역성이 없으면 성능이 떨어진다
LRU : 이론상 시간 기록용으로 비트를 많이 사용해야하지만 실제로는 구현할 때 접근비트를 이용한다
성능은 확실히 LRU가 좋지만 시간을 기록하는 비트의 수가 너무 많이 필요하기도 하고 시간이 지나면 언젠가는 오버플로우가 생기기에 사용이 힘들다.
대신 Clock Algorithm을 사용한다
Clock Algorithm은 접근비트를 사용하며 일정 시간 간격마다 접근 비트를 0으로 초기화한다.
만약 페이지가 참조되었다면 1로 초기화한다.
Clock Algorithm은 페이지를 원형으로 연결한다.
스왑 영역으로 옮길 페이지를 Clock hand라고 한다.
page fault가 발생하면 Clock hand는 계속 시계방향을 돌아가며 값이 0인 페이지를 만날때까지 돈다.
만약 발견하면 최근에 접근하지 않았다는 뜻이니 스왑영역으로 옯긴다.
Enhanced Clock Algorithm라는 것도 있는데 변경비트와 접근비트 둘 다 사용한다.
무조건 LRU만 사용할수는 없다. 만약 하드웨어에서 접근비트를 지원하지 않는다면 FIFO를 사용할 수도 있다.
FIFO의 개선점인 2차 기회 페이지 교체 알고리즘도 있다.
- 스레싱과 워킹셋
운영체제는 CPU사용량을 늘리려고 한다.
운영체제는 사용량을 늘리려고 멀티프로그래밍 정도를 늘리려고 하는데 무작정 늘려버리면 오히려 스왑작업이 많아져서 사용량이 줄어들게 된다. -> 이런 상황을 스레싱이라고 한다.
스레싱의 원인은 물리메모리의 크기가 작은 것이다.
물론 물리메모리를 늘리면 해결이 되긴 하지만 무작정 늘린다고 해결되지는 않는다.
페이지가 많든 적든 항상 문제는 있다.
해결방법은 만약 page fault가 있으면 페이지를 추가하면 되고 page fault가 너무 적게 발생하면 메모리가 낭비되는 상황이 벌어진다고 생각되서 페이지가 줄어든다.
적정 페이지수가 결정되었다면 어떤 페이지를 유지할지 결정해야 한다.
현재 사용중인 페이지들은 자주 사용될 확률이 높기 때문에 이를 통째로 메모리에 올리는데 이를 워킹셋이라고 부른다.
섹션9
-주변장치(I/O 디바이스, 저장장치)
그래픽카드,SSD,마우스 등 여러가지가 있다.
주변장치들은 메인보드에 있는 버스로 연결된다.
하나의 버스는 Adress, Data, Control버스로 이루어져 있다.
각 하드웨어에 맞게 외부인터페이스가 존재하고 레지스터, 컨트롤러, 로직 등이 있다.
주변장치는 두가지로 나눌 수 있다.
캐릭터 디바이스 - 마우스, 키보드, 사운드 카드 등
블록 디바이스 - 하드디스크, SSD, 그래픽카드 등
캐릭터 디바이스 - 적은 양의 데이터 전송
블록 디바이스 - 많은 양의 데이터 전송
옛날에는 버스 하나에서 썼었는데 주변장치 하나 확인하면 다른 장치를 못써서 현재는 여러개의 버스가 추가되었다.
시스템 버스 ->입출력 제어기 -> 주변장치 구조이지만 그래픽카드는 시스템버스에 직접적으로 연결한다.
메모리가 입출력 제어기에 직접 연결하기 위해 DMA를 추가하고 사용하는데 이를 Memory Mapped I/O라고 한다.
-마우스/키보드
마우스는 현재는 바닥에 달린 마우스가 초당 1500회 가까히 사진을 찍은 후 마우스 안에 DSP가 사진을 분석하여 X,Y자표를 분석한다. 그 후 마우스 드라이버에게 값을 보내고 드라이버가 운영체제에게 값과 안터럽트를 보낸다.
키보드도 동일하게 작동한다.
-하드디스크/Flash Memory(SSD)
하드디스크에는spindle이라고 하는 막대가 있고 그곳에는 platter라는 원판들이 붙어있다.
disk arm이 platter의 값을 읽는다.
platter > track > sector구조로 되어있다.
Flash Memory
요즘은 하드디스크보다 플래시 메모리를 많이 사용한다
Flash Memory는 읽기도 빠르고 자석 및 충격으로 인한 손상이 거의 없다.
대신 덮어쓰기의 횟수가 정해져 있다.
섹션10
-파일과 파일시스템
사용자가 메모리를 직접 접근해서 데이터를 저장한다면 중요한 공간도 침범당할 수 있어서 사이에 운영체제를 둔다.
사용자가 요청하면 운영체제가 안전하게 저장한다.
운영체제는 파일을 관리하기 위해 파일 관리자(파일 시스템)를 두었다.
관리자는 파일 테이블을 이용해서 저장하고 찾는다.
파일 시스템의 기능
파일과 디렉토리 생성
파일과 디렉토리 수정/삭제
파일 권한 관리
무결성 보장
백업과 복구
암호화
파일 시스템은 블록디바이스에 블록 단위로 저장한다.
사용자는 바이트 단위로 볼려고 하기에 파일 관리자가 중간에 있다.
윈도우즈는 유닉스와 다르게 파일 확장자가 있고 항상 다르다.
파일은 헤더와 데이터로 나누어져있다.
헤더에는 파일의 속성들이 들어있다.
운영체제는 파일 제어 블록을 가지고 있다.
파일 제어 블록은 모든 파일마다 있고 오픈되면 메모리로 이동한다.
파일 제어 블록은 운영체제가 관리하고 사용자는 접근할 수 없다.
순차파일구조
카세트테이프
들어온 순서대로 작동하기에 공간의 낭비가 없고 구조가 단순하다.
허나 특정지점으로 바로 이동이 어렵다.
집접파일구조
해시함수를 통해 저장위치를 정하는 방식
json도 이 방식
데이터 접근이 매우 빠르다
해시함수를 잘 골라야 하며 저장공간이 낭비될 수 있다.
인덱스 파일구조
앞선 두 가지 방식을 합친 것
노래 재생목록 같은 경우
-디렉토리
파일을 하나에 공간에 저장하면 너무 복잡할 것이다.
그렇기에 디렉토리가 생겼다.
디렉토리는 파일을 가질 수 있고 자식 디렉토리도 가질 수 있다.
가장 위에 있는 디렉토리를 루트 디렉토리라고 한다.
루트 디렉토리를 "/"로 표현하고 디렉토리를 구분할때도 /를 사용한다.
윈도우즈는 루트 디렉토리를 C:로 표현하며 \로 구분한다.
디렉토리도 파일이며 일반 파일에는 데이터가 있고 디렉토리에는 파일 정보가 저장되어 있다.
디렉토리 구조
처음에는 루트 디렉토리에만 하위 디렉토리를 만들 수 있었으나 디렉토리가 너무 많아져서 결국 다단계 디렉토리가 생겼다.
현재는 다단계 디렉토리를 사용하며 트리구조에서 순환이 생긴다.
바로가기 기능 때문에 순환이 생긴다.
-파일과 디스크
파일시스템은 공간을 나누고 주소로 관리한다는 면에서 메모리와 비슷하다.
파일시스템은 블록 단위로 나누는데 이는 1~8kb정도이다.
파일시스템은 파일테이블로 관리하는데 여기에는 파일의 시작 위치 정보도 있다.
파일은 블록을 어떤 방식으로 연결하냐에 따라 연속할당과 불연속할당으로 나누어진다.
연속할당 : 블록들을 디스크에 연속적으로 저장하는 방식, 시작블록만 알면 나머지도 알 수 있으나 내부단편화가 발생한다.
->그래서 사용을 안한다.
불연속할당 : 디스크의 비어있는 공간에 집어넣고 파일시스템이 두가지 방식으로 관리한다.
불연속할당(연결할당) : 연결리스트 구조
불연속할당(인덱스할당) : 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결한다, 테이블의 크기가 부족할 경우 사용하기 좋다.(유닉스와 리눅스에서 사용)
디스크는 블록으로 단위가 나뉜다, 여기도 블록의 크기에 따라 외부단편화가 생기거나 관리해야할 블록의 수가 많아진다.
빈공간을 찾을 때 항상 모든 공간을 찾는것보다는 빈공간 리스트를 만들고 삭제한 후에 리스트에 빈 공간의 주소를 추가하는 방식이 좋다.
알고리즘
https://github.com/asdf1596/cs_inflearn_club/tree/main/dev
섹션3
- 삽입정렬
삽입 정렬도 두 영역으로 나눠서 진행된다.
5|1,3,2,4
5,5|3,2,4 (1)
1,5|3,2,4
1,5,5|2,4(3)
1,3,5|2,4
1,3,5,5|4(2)
1,3,3,5|4(2)
1,2,3,5|4
1,2,3,5,5(4)
1,2,3,4,5
삽입정렬 - 구현
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, 6, 3, 5, 2];
console.log(arr);
InsertionSort(arr);
console.log(arr);시간복잡도 : O(n^2)
장점 : 구현하기 쉽다
단점 : 시간이 오래 걸린다
- 병합정렬
정렬해야 할 것을 아주 잘게 나눈 다음 정렬하고 병합하고를 반복하는 정렬방법이다.
병합정렬 - 구현
function MergeSort(arr, leftIndex, rightIndex) {
if (leftIndex < rightIndex) {
let midIndex = parseInt((leftIndex + rightIndex) / 2);
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 = rightIndex + 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(arr);
MergeSort(arr);
console.log(arr);시간복잡도 : 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) {
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(arr);
quicksort(arr, 0, arr.length - 1);
console.log(arr); 시간복잡도 : O(nlogn), O(n^2)
장점 : 성능이 훨씬 좋다
단점 : 이해와 구현이 어려움
- 동적 프로그래밍-메모이제이션
앞선 방법들은 재귀를 통해 문제를 나누어서 해결했었다.
하지만 재귀는 콜스택을 차지하는 단점 외에도 다른 단점이 있다.
예 :
피보나치 수열이라는 것이 있다.
현재 수와 이전 수를 더해서 다음 수를 만들어내는 구조의 수열이다.(1,1,2,3,5,8,13....)
function fibonacci(n) {
if (n == 1 || n == 0) return n;
return fibonacci(n - 2) + fibonacci(n - 1);
}
console.log(fibonacci(5));만약 이 수열을 간단한 재귀로 구현한다면 겹치는 계산이 너무 많다.(O(n^2))
해결방법을 결과를 계산하고는 저장해서 적재적소에 사용하도록 코딩하는 것이다.
function fibonacci1(n) {
if (n == 1 || n == 0) return n;
return fibonacci1(n - 2) + fibonacci1(n - 1);
}
function fibonacci2(n, memo) {
if (n == 1 || n == 0) return n;
if (memo[n] == null) {
memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
}
return memo[n];
}
let start = new Date();
console.log(fibonacci1(5));
let end = new Date();
console.log(end - start);
let start2 = new Date();
console.log(fibonacci2(5, {}));
let end2 = new Date();
console.log(end2 - start2);시간복잡도 : O(n)
속도는 빠르긴 하지만 메모리를 차지한다.
- 동적 프로그래밍-타뷸레이션
메모이제이션 - 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있으며 중복 계산을 하지 않아서 속도가 빠르다.
타뷸레이션 - 상향식 계산 방법으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장해둠
상황에 따라 둘을 적절하게 사용이 가능하다.
메모이제이션 - 메모리를 사용하면서 성능을 향상시킨다. 재귀가 직관적일때는 메모이제이션이 유리하다.
타뷸레이션 - 재귀가 직관적이지 않을 때 유리하다.
댓글을 작성해보세요.
