마지막 발자국
알고리즘삽입정렬졍렬된 영역과 정렬되지 않은 영역으로 구분한다.정렬되지 않은 영역에서 데이터를 하나씩 꺼내 정렬된 영역 내 적절한 위치에 삽입하는 알고리즘성능O(n²)장점이해와 구현이 간단단점성능이 좋지 않다void SelectionSort(int* arr, int size) { for(int i = 1; i < size; i++) { int insertingData = arr[i]; int j; for(j = i - 1; j >= 0; j--) { if(arr[j] > insertingData) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = insertingData; } } 병합 정렬 ( Merge Sort)분할정복하는 방법의 정렬 방식 : 해결하기 힘든 문제가 발생하면 한번에 해결하지 않고 해결하기 쉬울 정도로 쪼갠 다음 하나씩 해결병합 정렬은 재귀로 정렬하는 알고리즘병합 정렬 성능 : O(nlogn);장점성능이 좋음단점이해와 구현이 어려움void MergeSort(int* arr, int leftIndex, int rightIndex) { if(leftIndex < rightIndex) { int midIndex = (int)((leftIndex + rightIndex) / 2); MergeSort(arr,leftIndex, midIndex); MergeSort(arr, midIndex + 1, rightIndex); Merge(arr, leftIndex, midIndex, rightIndex); } } void Merge(int* arr, int leftIndex, int midIndex, int rightIndex) { const int tempSize = rightIndex + 1 - leftIndex; int tempArr[tempSize] = {0}; int leftAreaIndex = leftIndex; int rightAreaIndex = midIndex + 1; int tempArrIndex = leftIndex; while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) { if(arr[leftAreaIndex] <= arr[rightAreaIndex]) { tempArr[tempArrIndex++] = arr[leftAreaIndex++]; } else { tempArr[tempArrIndex++] = arr[rightAreaIndex++]; } } if(leftAreaIndex > midIndex) { for(int i = rightAreaIndex; i <= rightIndex; i++) { tempArr[tempArrIndex++] = arr[i]; } } else { for(int i = leftAreaIndex ; i <= midIndex; i++) { tempArr[tempArrIndex++] = arr[i]; } } for(int i = leftIndex; i <= rightIndex; i++) { arr[i] = tempArr[i]; } } 퀵 정렬(Quick Sort)분할 정복 알고리즘퀵 정렬의 성능 : O(nlogn) / 최악의 경우 O(n²) : 피벗이 배열을 반으로 가르지 않고 한쪽에 쏠리는 경우성능만 보면 병합 정렬이 더 좋다고 볼 수 있지만 퀵 정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가받음void QuickSort(int* arr, int left, int right) { if(left <= right) { int pivot = Divide(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } } int Divide(int* arr, int left, int right) { int pivot = arr[left]; int leftStartIndex = left + 1; int 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 ,leftStartInex, rightStartIndex); } } swap(arr, left, rightStartIndex); return rightStartIndex; } void Swap(int* arr, int index1, int index2) { int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } 동적 프로그래밍메모이제이션(memoization)계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법피노나치 수열을 재귀함수로만 구현하면 중복된 계산이 많기에 성능이 좋지 않다.int Fibonacci(int n) { if(n == 0 || n == 1) return n; return Fibonacci(n - 2) + Fibonacci(n - 1); } 계산하려는 데이터가 있는지 검색하고 없다면 함수를 호출해 계산을 하고 그 결과를 저장한다.빠른 데이터 탐색, 삽입, 삭제가 빠른 해시 테이블을 이용.Key에 계산하려는 값을 Value에 계산 결과를 저장하여 계산하려는 값의 검색.#include<unordered_map> using namespace std; unordered_map<int, int> um_memo; int Fibonacci(int n) { if(n == 0 || n == 1) return n; if(um_memo.count(n) > 0) { return um_memo[n]; } else { um_memo[n] = Fibonacci(n - 2) + Fibonacci(n - 1); return um_memo[n]; } } 재귀를 통한 피보나치 수열 시간 복잡도 : O(2^n)메모이제이션을 통한 피보나치 수열 시간 복잡도 : O(n)메모이제이션은 속도가 향상되지만, 메모리를 그만큼 사용한다.타뷸레이션(Tabulation)계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법 / 상향식 계산 방식에 사용된다.메모이제이션은 재귀를 통해 함수를 호출하기에 콜스택에 함수 호출이 쌓이는 메모리적인 비용이 더 든다.#include<unordered_map> using namespace std; unordered_map<int, int> um_tb; int Fibonacci(int n) { if(n <= 1) return n; um_tb[0] = 0; um_tb[1] = 1; for(int i = 2; i <= n; i++) { um_tb[i] = um_tb[i - 2] + um_tb[i - 1]; } return um_tb[n]; } 가상메모리가상메모리 개요프로세스는 가상 메모리를 통해 실행된다. (0X0번지)물리 메모리의 주소를 몰라도 메모리 관리자를 통해 가상 메모리를 통해 물리 메모리로 연결된다.동적 주소 변환 (Dynamic Address Translation) : 메모리 관리자는 메모리와 하드디스크 내 스왑 영역을 합쳐서 프로세스사 사용하는 가상 주소를 물리주소로 변환한다.메모리 관리자의 역할물리 메모리를 어떻게 나눌지프로세스를 어디다 배치할지부족한 물리 메모리는 어떻게 처리할지등의 문제를 처리해야 하기에 복잡한 과정을 거친다.메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리한다.세그멘테이션(배치정책)가변분할 방식세그멘테이션에서 프로그램은 함수나 모듈등으로 세그먼트를 구성한다.코드 영역 : 메인 코드가 있는 세그먼트데이터 영역 : 전역 변수들이 있는 세그먼트힙 영역 : 힙 영역이 있는 세그먼트스택 영역 : 스택 영역이 있는 세그먼트각 세그먼트들은 서로 인접할 필요가 없다.사용자와 프로세스, CPU가 바라보는 주소는 논리주소라고 한다.실제 물리 주소로의 변환은 중간에서 메모리 관리자(MMU)가 해준다.메모리 관리자가 논리주소를 물리주소로 변환해주는 방법메모리 관리자는 세그멘테이션 테이블이라는 것을 가지고 있다.세그멘테이션 테이블에는 Base Address와 Bound Address정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산한다.CPU에서 메모리를 전달해주면 메모리 관리자는 이 논리 주소가 몇번 세그먼트인지 알아낸다.메모리 관리자 내에 Segment Table Base Register를 이용해서 물리 메모리 내에 있는 세그멘테이션 테이블을 찾고세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾는다.운영체제는 컨텍스트 스위칭을 할 때마다 메모리 관리자 내에 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.컨텍스트 스위칭은 이런 작업까지 하기에 굉장히 무거운 동작이다.Bound Address는 세그먼트의 크기를 나타낸다.메모리 관리자는 CPU에서 받은 논리주소와 이 Bound Address의 크기를 비교한다.만약 논리 주소가 Bound Address보다 작다면 논리 주소와 Base Address를 더해 물리 주소를 구하고논리 주소가 Bound Address보다 크다면 메모리를 침범했다고 생각하고 에러를 발생시킨다.장점메모리를 가변적으로 분할할 수 있다코드 영역, 데이터 영역, 스택 영역, 힙 영역등을 모듈로 처리할 수 있기에 공유와 각 영역에 대한 메모리 접근 보호가 편리하다. / 영역별로 분할돼서 관리가 쉬움단점가변 분할 방식의 단점인 외부 단편화가 발생한다.페이징(배치정책)세그멘테이션의 외부단편화를 해결하기 위해 고안되었다.페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다. / 내부단편화가 발생페이지 : 논리 주소 공간에서 일정한 크기로 균일하게 나뉜 것.프레임 : 물리 주소 공간에서 일정한 크기로 균일하게 나뉜 것.메모리 관리자는 페이지 테이블을 가진다.메모리 관리자는 CPU에서 전해주는 논리 주소가 몇 번 페이지인지, 오프셋은 얼마인지 알아낸다.메모리 관리자 내에 있는 PTBR(Page Table Base Register)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리주소로 변환을 한다.오프셋은 계산을 통해 쉽게 구할 수 있다.페이지 테이블에 Invalid로 표기되어 있으면 스왑 영역에 저장되어 있다는 의미이다.컨텍스으 스위칭이 발생할 때마다 PTBR을 헤딩 프로세스의 것으로 업데이트 해준다.페이지 넘버 = 논리 주소 / 페이지 크기페이지 넘버는 논리주소를 페이지 크기로 나눈 몫으로 구할 수 있다.오프셋 = 논리주소 % 페이지 크기오프셋은 논리 주소를 페이지 크기로 나눈 나머지이다.페이지 넘버를 페이지 테이블의 인덱스로 사용하여 프레임을 구한 후 해당 프레임 위치에서 오프셋을 더해주면 물리주소로 변환이 완료된다.세그멘테이션과 페이징의 차이프로세스마다 크기가 달라 Bound Address를 가지고 있지만, 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address는 필요하지 않다.세그멘테이션은 외부단편화가 발생하고 페이징은 내부단편화가 발생한다.외부단편화가 더 많은 공간이 낭비되기에 내부단편화는 심각하게 생각하지는 않는다.세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다. / 코드, 데이터, 힙, 스택페이징은 페이지의 크기가 고정되어 있기에 논리적인 영역을 나눌 수 없다. 그래서 특정 영역만 떼어내서 공유하거나 권한을 부여하는게 더 어렵다. 페이징에서 가장 신경써야 하는 것은 페이지 테이블 크기이다.각 프로세스마다 페이지 테이블을 가지고 있는데 프로세스가 많아질수록 페이지 테이블도 많아지기에 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기에 페이지 테이블 크기가 너무 크면 사용자 영역이 부족해진다. 그렇기에 페이지 테이블의 크기를 적절하게 유지하는 것이 중요하다.페이지드 세그멘테이션(배치정책)세그멘테이션과 페이징을 혼합해 장점을 취한 방식이다. 새로운 단점도 생기긴 했다.메모리 접근 권한메모리의 특정 번지에 부여된 권한으로 읽기, 쓰기, 실행 세 가지가 있다.프로세스는 데이터 영역별로 접근 권한이 있다.코드 : 프로그램 그 자체이므로 수정하면 안됨 | 읽기 / 실행 권한데이터 : 일반변수, 전역변수, 상수로 선언한 변수가 저장된다 | 읽기 / (쓰기) 권한스택, 힙 : 읽기 / 쓰기 권한메모리 접근 권한에 대한 검사는 가상주소에서 물리주소로의 변환이 있을 때마다 일어나는데만약 권한을 위반하면 에러를 발생시킨다.페이지드 세그멘테이션의 세그멘티테이션 테이블은 권한비트, 페이지 넘버, 페이재 개수루 구성된다.가상주소가 들어오면 몇 번 세그먼트인지 알아낸다.그 이후 가상주소의 요청 권한을 확인한 후 위반된 경우 프로세스를 종료시킨다.위반되지 않으면 페이지 넘부와 페이지 개수를 가져온 후 페이지 넘버로 페이지 테이블에 접근해서프레임 번호를 가져오고 물리 메모리 내에 해당 프레임에 접근해 그 위치에서 페이지 개수를 더해 물리주소를 구한다.만약 물리 메모리에 해당 프레임이 없다면 스왑 영역에서 물리 메모리로 가져온다.페이지드 세그멘테이션의 단점은 물리메모리에 접근하기 위해서 메모리에 접근을 두 번해야 된다는 것이다.첫번째는 세그멘테이션 테이블을 참조할 때 두번째는 페이지 테이블에 참조할 때이다.현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 혼용한다.디맨드 페이징(가져오기 정책)코드, 데이터, 힙, 스택 영역의 모든 데이터들이 메모리에 올라오는 것이 아니다.필요한 메모리 일부만 올라와서 실행된다.컴퓨터 과학자 도널드 커누스가 발견한 90:10 법칙⇒ 90%의 시간이 10%의 코드에서 보내는 것을 의미이것을 지역성 이론이다.공간의 지역성현재 위치와 가까운 데이터에 접근할 확률이 높음시간의 지역성최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음goto문 지향의 이유는 코드의 구조파악이 어려운 것도 있지만지역성 이론에 따라 성능에 좋지 않기 때문. / 지역성 이론을 위배지역성 이론은 조만간 사용될 것 같은 데이터만 메모리에 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킨다.디맨드 페이징 : 조만간 필요할 것 같은 데이터를 메모리로 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책이다. / 지역성 이론을 구현한 정책디맨드 페이징은 스왑영역을 보조저장장치에 저장하는데 성능 향상을 위해서는 스왑 영역으로 데이터를 이동시키는 것을 최소화 시켜야한다.가상 메모리 = 메인 메모리 + 하드디스크 내 스왑영역스왑영역에서 물리 메모리로 데이터를 가져오는 것을 스왑인이라 부른다.반대는 스왑아웃이라 부른다.페이지 테이블의 한 행을 페이지 테이블 엔트리(PTE)라고 부른다.페이지 테이블 엔트리에는 프레임 뿐 아니라 여러 정보를 담은 비트로 이루어져 있다.접근 비트 | 변경 비트 | 유효 비트 | 읽기 / 쓰기 / 실행 비트 | 프레임접근 비트 : 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트. 메모리에 읽기나 실행 작업을 했다면 1로 바뀐다.변경 비트 : 페이지가 메모리에 올라온 후 데이터의 변경 있었는지 알려주는 비트. 메모리에 쓰기 작업을 했다면 1로 바뀐다.유효 비트 : 페이지가 물리 메모리에 있는지 알려주는 비트. 만약 유효비트가 1이라면 페이지가 스왑영역에 있고 0이라면 물리 메모리에 있다는 의미.읽기 / 쓰기 / 실행 비트 : 권한비트로 해당 메모리에 접근 권한이 있는지 검사하는 비트.프로세스가 가상 메모리에 접근 요청을 했을 때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾는데 만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킨다. Page Fault가 발생하면 보조저장장치의 스왑 영역에 접근하게 되고 해당 프로세스는 대기상태가 된다. 스왑영역에 있는 데이터가 메모리로 올라가는 작업을 시작하고 메모리로 올라갔다면 대기상태에 있던 프로세스는 다시 실행된다.페이지 교체정책페이지 교체정책프로세스가 데이터 참조를 요청했는데 Page Fault가 발생하는 경우 스왑 영역으로 옮길 페이지를 결정하는 정책무작위로 선택하는 방법 : 지역성을 고려하지 않기에 자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다. / 거의 사용되지 않음FIFO : 가장 오래된 페이지 선택 / 자주 쓰이는 페이지가 교체되면 공평하지 않을 수 있음 구현이 간단하고 성능도 꽤 괜찮아서 변형해서 많이 사용된다.Optimum : 앞으로 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법. 사실상 구현이 불가능한 이론적인 선택 방법이다. / 뭐가 가장 사용되지 않을지 알 방법이 없음. / 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰인다.LRU (Least Recently Used) : 최근에 가장 사용이 적은 페이지를 선택하는 방법. 접근 비트를 통해 LRU에 근접하게 접근한다. / Optimum에 가장 근접한 성능을 보임 최근에 들어온 페이지의 참조 수를 계산해서 판별Clock Algorithm : 접근 비트를 원형으로 연결하고 클락 핸드를 통해 페이지들의 접근 비트를 순회하면서 접근 비트가 0인 경우(데이터 접근 X) 해당 페이지를 스왑 영역으로 보낸다.Enhanced Clock Algorithm : 접근 비트, 변경 비트를 이용 두 비트를 통해 스왑 영역으로 보내질 우선순위 결정하드웨어적으로 접근비트를 지원하지 않는 시스템에선 FIFO를 이용할 수 밖에 없기에 FIFO의 성능을 높이기 위한 방법을 고안함FIFO의 자주 사용하는 페이지가 교체될 수 있다는 단점을 해결하기 위헤 2차 기회 페이지 교체 알고리즘을 고안 / 자주 사용하는 페이지에게 또 한번의 기회를 제공 Page Fault없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시키는 방법LRU > 2차 기회 페이지 교체 알고리즘 > FIFO스레싱과 워킹셋스레싱제한된 물리 메모리에 의해 스왑 영역에 데이터가 많이 저장되고 Page Fault가 많이 발생하게 되면 CPU 사용률이 떨어진다. CPU 스케줄러에 의해 CPU 사용률을 올리기 위해 더 많은 프로세스를 메모리에 올리게 되고 이를 반복하게 되면 CPU 사용률이 0에 가깝게 떨어지는데 이를 스레싱이라고 한다.근본적인 원인은 물리 메모리의 크기가 작은것이다.하드웨어적인 해결 방법메모리 크기를 늘린다. 스레싱 발생 지점이 늦춰진다.스레싱이 발생하지 않는다면 메모리 크기를 늘려도 성능에 별 차이 없다.워킹셋소프트웨어적인 해결 방법프로세스가 실행되면 일정량의 페이지를 할당하고 만약 Page Fault가 발생하면 더 많은 페이지를 할당한다. Page Fault가 너무 적게 발생하면 메모리가 낭비되는 것이라 판단하고 페이지를 회수한다. 이렇게 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수가 결정된다. 지역성 이론에 따라서 어떤 페이지들을 유지할 것인가가 결정된다. 현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기에 하나의 세트로 묶어서 메모리에 올리는데 이를 워킹셋이라 부르고 워킹셋은 프로세스가 준비상태에서 실행상태가 되는 컨텍스트 스위칭을 할 때 사용된다.입출력 장치주변장치(I/O 디바이스, 저장장치)주변 장치들은 메인보드에 있는 버스로 연결된다.하나의 버스는 Address 버스, Data 버스, Control 버스를 따로 받을 수 있다.각 하드웨어에 맞게 외부 인터페이스가 존재한다.장치의 상태와 데이터를 보관할 수 있는 각종 레지스터들이 존재.이 레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할.이 값들은 CPU가 사용하기 위해 메모리로 이동되기도 한다.데이터의 전송단위가 캐릭터(글자)냐 블록이냐로 나뉜다.캐릭터 디바이스마우스, 키보드, 사운드 카드, 직렬/병렬 포트등데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음블록 디바이스하드디스크, SSD, 그래픽 카드 등데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼예전에는 주변장치들을 하나의 버스로 연결해서 사용했다. CPU 가 작업을 하다 I/O명령을 만나면 직접 입출력 장치에서 데이터를 가져왔는데 입출력중에는 다른 작업을 하지 못하기에 CPU 사용률이 떨어졌다.이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러 개의 버스가 추가됐다.CPU 는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 실행한다.입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분한다.시스템 버스는 고속으로 작동하는 CPU와 메모리가 사용하고입출력 버스는 주변장치가 사용.입출력 버스는 세부적으로 느린 장치와 빠른장치를 구분하기 위해 고속 입출력 버스와 저속 입출력 버스로 나눈다. 느린 장치와 빠른 장치를 구분해 속도 차이로 인한 병목 현상을 해결했습니다.그래픽 카드가 다루는 데이터는 매우 대용량이라 고속 입출력 버스로도 감당이 안된다. 그래픽 카드는 입출력 버스에 있지 않고 시스템 버스에 바로 연결해 사용한다.기존에는 입출력 제어기가 여러 주변 장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮긴다. 근데 메모리는 CPU의 명령으로 움직이기 때문에 입출력 제어기가 메모리에 접근하기 위해서는 CPU가 필요하다. 입출력 제어기가 CPU의 도움이 필요 없도록 DMA 제어기가 추가되었습니다.DMA (Direct Memory Access)의 약자로 직접 메모리 접근이라는 뜻.입출력 제어기는 DMA로 데이터를 직접 메모리에 저장하거나 가져올 수 있습니다.CPU와 DMA가 사용하는 메모리가 겹치지 않도록 CPU가 사용하는 메모리 영역과 DMA가 사용하는 메모리 영역을 나누는데 이를 Memory Mapped I/O 라고 부른다. 마우스/키보드광학 마우스는 아래쪽에 작은 카메라가 달려있고, 표면으로 초당 1500회가 넘는 사진을 찍어 마우스의 디바이스 컨트롤내 DSP (Digital Signal Processor)로 보낸다. DSP는 이 사진을 분석해 마우스의 X축 좌표와 Y축 좌표 움직임을 캐치한다. DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어간다. 마우스 드라이버는 운영체제에게 이벤트 신호를 주는데 운영체제는 이 이벤트를 Foreground 애플리케이션으로 전달해주고 해당 애플리케이션은 받은 마우스 이벤트를 처리한다.키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아낸다. CPU에게 인터럽트를 보내고 키보드 드라이버는 운영체제에게 이벤트를 보낸다. 그럼 운영체제는 Foreground 애플리케이션으로 이 이벤트를 전달해주고 애플리케이션에서 해당 키에 맞는 동작을 수행한다. 하드디스크/Flash Memory(SSD)주변장치 중 블록 디바이스의 한 종류하드디스크 구조스핀들(spindle)이라는 막대가 있다.스핀들에는 플래터(platter)라는 원판들이 붙어있다.플래터는 자기화된 원판으로 이루어져 있는데 디스크암이 읽기/쓰기 헤드로 플래터의 표면을 읽는다.플래터는 여러 개의 트랙으로 구성되어 있고 표면에 자성이 있기에 표면이 N극을 띄면 0, S극을 띄면 1로 인식한다. 보통 하드디스크의 플래터 수는 2개 이상이다. 헤드는 디스크암에 고정되어 있기에 모든 헤드는 항상 같이 움직인다. 헤드가 움직이면 이 헤드들은 여러 개의 플래터들을 가리키게 되는데 이때 여러 개의 플래터에 있는 같은 트랙의 집합을 실린더라고 부른다. 트랙은 다시 여러 개의 섹터로 나뉘는데 이 섹터가 하드디스크의 가장 작은 단위이다.하드디스크에서 데이터를 읽어오는 예시유저 프로세스가 하드디스크의 특정 섹터에 접근하고 싶어서 이러한 요청을 보낸다.하드디스크의 섹터를 읽어라는 명령을 내리면 디스크암은 헤드를 실린더로 이동시키는데 이를 ‘Seek’라고 부르며 헤드를 실린더로 이동시키는데 걸리는 시간을 Seek Time이라고 부르는데 이것 때문에 하드디스크가 굉장히 느린것이다. 헤드를 목표 지점까지 움직이는 시간은 수 ms인데 다른 전자장비들은 ns단위로 움직이니 상대적으로 굉장히 느리게 느껴짐. 디스크암을 움직여 헤드를 실린더까지 보냈으면 트랙의 섹터가 헤드에 닿을때까지 스핀들을 회전시킨다. 그러다가 헤드에 섹터가 읽히면 작업이 끝난다.Flash Memory(SSD)하드 디스크는 기계적으로 헤드를 움직여 속도가 많이 느리고 소음도 났지만 Flash Memeory는 전기적으로 읽기 때문에 굉장히 빠르고 조용하다. 또한 자기적으로 처리하는 하드디스크는 자석을 갖다 대면 데이터가 손상되지만 Flash Memory는 안전하다.하드디스크는 스핀들처럼 회전축 같은 것들이 있어서 충격에 매우 약하지만 Flash Memory는 그렇지 않다. Flash Memory의 가장 큰 단점은 특정한 지점에 데이터를 썼다면 덮어쓰기가 불가능 하다는 것. 똑같은 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야 하는데 Flash Memory는 지우기 가능한 횟수가 정해져있다. 그래서 똑같은 지점에 지우기/쓰기를 계속하면 망가진다.파일과 파일 시스템파일은 사용자 요청에 따라 운영체제에 의해 안전하게 저장된다. / 악의적인 사용자에 의한 훼손 가능성 때문에파일 시스템운영체제가 파일을 관리하기 위한 파일 관리자.파일 시스템은 파일 테이블을 이용해서 파일을 관리한다.파일 시스템의 기능파일과 디렉토리 생성파일과 디렉토리 수정/삭제파일 권환 관리 : 다른 사용자로부터 파일을 보호하기 위함 / 요즘 운영체제는 다중 사용자 기능을 지원하기 때문에 파일 보호를 위해 필요한 기능무결성 보장 : 파일의 내용이 손상되지 않도록.백업과 복구 : 예기치 못한 사고로부터 백업과 복구를 한다.암호화파일 접근 방법파일을 관리하는 하드디스크나 Flash Memory(SSD)는 블록 디바이스입니다. 파일 시스템은 전송 단위는 블록이지만, 사용자는 바이트 단위로 파일에 접근이 가능해야 한다. 파일 관리자가 이를 중간에서 관리해준다.파일 구조파일은 헤더와 데이터로 이루어져 있다. 헤더 : 파일의 속성들이 담겨져 있다.파일 이름파일 식별자파일 유형파일 크기시간저장 위치접근 권한소유자파일제어블록(File Control Block, FCB) | (File Descriptor)운영체제는 파일을 관리하기 위해 정보를 보관한다.파일 디스크립터(File Descriptor)라고도 부른다.파일마다 독립적으로 존재하고 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동한다. 파일 디스크립터는 파일 시스템(운영체제)이 관리하고 사용자가 직접 참조할 수는 없다. 사용자는 파일 시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있다.파일의 종류파일의 데이터 집합을 어떻게 구성하느냐에 따라 종류가 구분된다.순차파일구조파일의 내용이 연속적으로 이어진 형태장점 : 모든 데이터가 순서대로 기록되기에 공간의 낭비가 없고 구조가 단순하다.단점 : 특정 지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 많이 걸린다는 것.직접파일구조저장하려는 데이터를 해시함수를 통해 저장 위치를 결정하는 파일구조.해시테이블 방식이며 요즘 많이 쓰이는 데이터 포맷인 json도 이 방식이다.장점 : 해시함수를 이용하기에 데이터 접근이 굉장히 빠르다.단점 : 해시함수의 선정이 굉장히 중요하기에 해시함수를 잘 골라야 한다. / 저장 공간이 낭비될 수 있다.인덱스파일구조순차접근과 직접접근 방식의 장점을 취한 것.두 가지 방식 모두 가능하다.인덱스 테이블을 통해 원하는 순차 데이터의 블록 번호로 접근할 수 있다. 디렉토리파일을 한 공간에 보관하면 파일이 많아지며 관리가 복잡해진다. 그래서 관련있는 파일을 모아둘 수 있도록 디렉토리가 생겼다.디렉토리는 1개 이상의 파일을 가질 수 있고 자식 디렉토리도 가질 수 있다. 최상위에 있는 디렉토리를 루트 디렉토리라 부르며, 그 하위 디렉토리는 자식 디렉토리라고 부른다.윈도우에서는 루트 디렉토리는 파티션 이름으로 사용한다. 보통 C:으로 표시한다. 디렉토리와 디렉토리 구분은 \로 한다.디렉토리도 파일이다. 일반 파일에는 데이터가 저장, 디렉토리에는 파일 정보가 저장되어 있다.디렉토리에서 헤더는 디렉토리 정보가 시작하는 위치를 가리킨다..는 현재 디렉토리를 의미하며..는 상위 디렉토리를 가리킨다.디렉토리는 순환이 있는(바로 이동하기) 트리 구조이다.파일과 디스크파일 시스템은 메모리와 비슷하다.전체 디스크 공간을 일정한 크기를 나누고 그 공간에 주소를 할당해 관리한다.일정한 크기로 나눈 것을 블록이라고 부른다. 한 블록의 크기는 1~8KB정도이다.파일 시스템은 파일 정보를 파일 테이블로 관리하는데 파일이 시작하는 위치 정보도 담겨있다.하나의 파일은 여러 개의 블록으로 이루어져 있는데 이 블록들을 연결한 방식에 따라 연속할당과 불연속할당으로 나눠진다.연속할당파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식이다. 파일의 시작 블록만 알면 파일의 전체를 찾을 수 있다.세그멘테이션처럼 외부단편화가 발생하기에 사용되지 않는다.불연속할당디스크에 비어있는 공간에 데이터를 분산해 저장하는 방식이다. 이 분산된 블록은 파일시스템이 관리한다.연결 할당파일에 속한 데이터를 연결리스트로 관리한다.파일 테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근하는 방식인덱스 할당테이블의 블록 포인터가 데이터 블록에 직접 연결하는 것이 아닌 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결한다.인덱스 할당은 데이터가 많아서 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결하기에 테이블을 확장할 수 있다.파일 시스템 저장/삭제 방식디스크에 파일을 저장할 때 빈 공간을 찾으려고 모든 공간을 뒤지는 방식은 비효율적이다.파일 시스템은 효율적인 관리를 위해 빈 공간을 모아둔 free block list를 가지고 있다. 특정 파일을 삭제할 경우 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가한다. 데이터는 지워진 게 아니라 복구가 가능한 형태이다.
