[인프런 워밍업클럽 CS 2기] 3주차 발자국

3주차 학습 내용

• '그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 6~10)

• '그림으로 쉽게 배우는 운영체제' Section 8, 9, 10

'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)' Section 3(Unit 6~10)

Section 3. 알고리즘

• 정렬 - 병합정렬(Merge Sort)

  • divide and conquer - 분할 정복

    • 해결하기 힘든 문제가 발생한다면 이걸 한 번에 해결하려고 하지 말고,
      해결하기 쉬울 정도로 문제를 쪼갠 다음 하나씩 해결하라

    • 원소를 하나일 때까지 쪼개고, 역순으로 순서에 맞게 하나의 배열로 병합해줌
      (재귀함수를 호출한 모양과 비슷함)

      

  • 코드 구현

    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 = 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 > idIndex) {
    		for(let i = rightAreaIndex; i <= rightIndex; i++) {
    			tempArr[tempArrIndex++] = arr[i];
    		}
    	} else {
    		for(let i = leftAreaIndex; i <= midIndex; i++) {
    			tempArr[tempArrIndex++] = arr[i];
    		}
    	}
    }
    

  • 병합정렬 성능

    • 성능측정 부분은 Merge() 함수 내 흩어진 배열을 합치는 부분

      • 하나의 데이터와 하나의 데이터가 두 개로 합쳐질 때 비교 연산을 두 번 함

      • 두 개의 데이터와 두 개의 데이터가 네개로 합쳐질 때 비교가 네 번 이뤄짐

    • 각 단계를 거칠 때마다 영역의 수가 반으로 줄어 logn이 됨

    • 분할된 배열을 병합할 때는 n개의 데이터를 n번 비교하므로 O(nlogn) 성능이 나옴

      

  • 병합정렬 장단점

    • 장점 - 성능이 좋음(O(nlogn))

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

• 정렬 - 퀵정렬(Quick Sort)

  • 분할 정복 알고리즘으로 재귀를 사용함

  • 퀵정렬 설명

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

      
      

    • leftStartIndex는 피벗보다 큰 값을 만나면 멈춤

    • rightStartIndex는 피벗보다 작은 값을 만나면 멈춤

    • leftStartIndex, rightStartIndex의 값을 스왑해줌

    • 서로 지나쳤다면 더이상 진행하지 않음

    • 이상태에서 피벗과 rightStartIndex 값 스왑해줌

    • 피벗값을 기준으로 오른쪽, 왼쪽을 정렬해줌

  • 코드 구현

    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[index];
    	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^2)

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

    • 퀵정렬의 장단점 - 병합정렬과 동일

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

  • 재귀의 단점

    • 피보나치 수열

      
      

    • 피보나치 수열 코드

      function fibonacci(n) {
      	if(n == 0 || n == 1) return n;
      	return fibonacci(n - 2) + fibonacci(n - 1);
      }
      
      console.log(fibonacci(5));
      

    • 성능이 좋지 못함 - 반복 계산

      
      

      • 단점 - 이미 계산했던 것을 다시 또 계산하게 됨

    • 메모이제이션

      • 재귀의 문제점 해결방법

      • 계산 결과를 저장해두고 사용

      • 해시테이블 사용

      • 피보나치 수열 코드를 메모이제이션을 사용해 수정

        function fibonacci1(n) {
        	if(n == 0 || n == 1) return n;
        	return fibonacci(n - 2) + fibonacci(n - 1);
        }
        
        function fibonacci2(n) {
        	if(n == 0 || n == 1) 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(40));
        let end = new Date();
        console.log("fibonacci1 함수 실행시간 : ${end - start}ms");
        
        let start = new Date();
        console.log(fibonacci2(40, {}));
        let end = new Date();
        console.log("fibonacci2 함수 실행시간 : ${end - start}ms");
        

      • 메모이제이션 장단점

        • 장점

          • 성능 O(n)을 보임

          • 재귀덕분에 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있음

          • 중복 계산을 하지 않아서 속도가 빠름

        • 단점

          • 메모리 영역을 사용함(ex, 캐시)

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

  • 상향식 계산 방식으로, 계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장해둠

    
    

  • 코드 구현

    function fibonacci1(n) {
    	if(n == 0 || n == 1) return n;
    	return fibonacci(n - 2) + fibonacci(n - 1);
    }
    
    function fibonacci2(n) {
    	if(n == 0 || n == 1) return n;
    	
    	if(memo[n] == null) {
    		memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
    	}
    	return memo[n];
    }
    
    function fibonacci3(n) {
    	if(n <= 1) return n;
    	
    	let table = [0, 1];
    	
    	for(let i = 2; i <= n; i++) {
    		table[i] = table[i - 2] + table[i - 1];
    	}
    	return table[n];
    }
    
    let start = new Date();
    console.log(fibonacci1(40));
    let end = new Date();
    console.log("fibonacci1 함수 실행시간 : ${end - start}ms");
    
    let start = new Date();
    console.log(fibonacci2(40, {}));
    let end = new Date();
    console.log("fibonacci2 함수 실행시간 : ${end - start}ms");
    
    let start = new Date();
    console.log(fibonacci3(40));
    let end = new Date();
    console.log("fibonacci3 함수 실행시간 : ${end - start}ms");
    

  • 성능

    • 메모이제이션은 여러번의 함수 호출로 메모리 공간에 스택을 차지하고, 메모이제이션을 위한 해시 테이블 공간까지 차지하기 때문에 메모리를 더 많이 사용함

    • 타뷸레이션은 적은 메모리 사용임에도 불구하고 빠른 시간을 보임

  • 메모이제이션 vs 타뷸레이션

    • 메모이제이션

      • 재귀를 이용해 문제를 하향식으로 해결함

      • 재귀만 이용한다면 중복 계산을 하기 때문에 성능의 문제가 발생했는데 계산 결과를 저장하는 방식으로 단점을 해결함

      • 해결하기 힘든 문제를 하향식으로 접근하고, 더 많은 메모리를 이용해 성능을 향상시킴

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

    • 타뷸레이션

      • 재귀가 직관적이지 않을 때는 상향식 접근인 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 할 수 있음

'그림으로 쉽게 배우는 운영체제' Section 8, 9, 10

Section 8. 가상메모리

• 가상메모리 개요

  • 컴퓨터마다 실제 메모리 크기가 다른데, 만약 운영체제나 프로세스가 특정 크기에서 동작하도록 만들어졌다면 그 크기보다 작은 메모리를 가진 컴퓨터에서는 실행되지 않음 → 가상 메모리는 이 문제를 해결함

  • 가상 메모리

    • 프로세스는 운영체제의 영역이 어디있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 됨

    • 프로세스는 메모리 관리자에게 요청만 하면됨

    • 메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결시켜줌

    • 가상메모리의 크기는 이론적으로는 무한대이지만 실제로는 물리 메모리 크기와 CPU의 비트 수로 결정됨 (ex, 32bit CPU(대략 4GB) → 가상 메모리 크기도 4GB가 됨)

  • 가상메모리로 프로세스들 실행시키는 방법

    • 물리메모리 내용의 일부를 하드 디스크에 있는 스왑영역으로 옮기고, 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 운영체제와 프로세스 5개를 전부 실행시킬 수 있음

       

  • 동적주소변환(Dynamic Address Translation)

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

       

    • 동적 주소 변환을 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있음

    • 메모리 관리자의 역할

      • 물리 메모리를 어떻게 나눌지

      • 프로세스를 어디다 배치할지

      • 부족한 물리 메모리는 어떻게 처리할지 등등을 위해 복잡한 과정을 거침

  • 가상 메모리 시스템의 메모리 할당 방법

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

    • 할당하는 방식은 메모리 분할방식과 마찬가지로 ‘가변 분할 방식’, ‘고정 분할 방식’으로 나뉨

       

      • 가변 분할 방식(세그멘테이션)

        • 단점 - 외부 단편화

      • 고정 분할 방식(페이징)

        • 단점 - 내부 단편화

      • 각각의 단점을 보완한 ‘세그멘테이션-페이징 혼용기법 ’ 사용

    • 세그멘테이션-페이징 혼용기법

      • 가상메모리 시스템에서 가상주소는 메모리나 스왑영역 한 곳 중에 위치

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

         

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

  • 가변 분할 방식을 이용하는 세그멘테이션 기법

    • 프로그램은 함수나 모듈등으로 세그먼트 구성

      • 프로그램(사용자) 관점 메모리 - 코드, 데이터, 힙, 라이브러리, 스택 각각 구성(인접할 필요 없음)

      • 프로세스 관점 메모리 - 코드, 데이터, 힙, 스택 영역을 서로 인접한 것처럼 바라봄

    • 논리주소

      • 사용자, 프로세스, CPU가 바라보는 주소

      • 실제 물리주소로 변환은 중간에서 메모리 관리자(MMU)가 해줌

    • 메모리 관리자가 논리주소 → 물리주소 변환 방법

      • 메모리 관리자가 가지고 있는 세그멘테이션 테이블에 Base Address, Bound Address(Segment 크기) 정보가 저장되고 이걸 이용해 물리 메모리 주소를 계산함

      • 운영체제는 컨텍스트 스위칭을 할 떄마다 메모리 관리자 내에 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야함 → 굉장히 무거운 동작

      • 논리주소가 Bound Address보다 작다면, 논리주소 + Base Address 로 물리주소를 구함

      • 논리주소가 Bound Address보다 크다면, 메모리를 침범했다고 생각하고 에러를 발생

    • 세그멘테이션 장점

      • 메모리를 가변적으로 분할할 수 있고, 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있음 → 공유와 각 영역에 대한 메모리 접근보호가 편리함

    • 세그멘테이션 단점

      • 가변 분할 방식의 단점인 “외부 단편화”가 발생함

• 페이징(배치정책)

  • 고정분할방식을 이용한 페이징

  • 세그멘테이션 기법은 외부 단편화 문제가 있기 때문에 이를 해결하기 위해 고안됨

  • 페이징

    • 메모리를 할당할 때 정해진 크기의 페이지로 나눔

    • 모든 페이지는 크기가 같기때문에 관리가 편하고, 일정한 크기로 나눴기 때문에 외부 단편화 현상이 일어나지 않음

    • 논리주소공간에서의 페이징 → 페이지

    • 물리주소공간에서의 페이징 → 프레임

       

  • 페이징의 주소변환 방법

    • 메모리 관리자가 “페이지 테이블”을 통해 CPU에서 전달받은 논리주소가 몇번 페이지, 오프셋은 얼마인지 알아냄

    • 메모리 관리자 내에 Page Table Base Register(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고, 페이지 번호를 인덱스로 프레임 번호를 알아내고, 오프셋을 이용해 물리주소로 변환을 함

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

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

       

  • 세그멘테이션 vs 페이징 차이점

    • 페이지의 크기가 다름

    • 세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 가지고 있지만, 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Addresss는 필요하지 않음

      • 페이징은 이런 특성때문에 외부단편화는 발생하지 않지만 내부단편화가 발생함 (정해진 크기의 페이징보다 프로세스의 정보가 작으면 그만큼 공간이 낭비됨)

      • 세그멘테이션의 단점과 비교하면 많은 고간이 낭비되는게 아니라서 심각하게 생각하지 않음

    • 세그멘테이션은 논리적인 영역별로 세그먼트를 나눔(코드, 데이터, 스택, 힙 영역), 그러나 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역별로 나누는 것이 아니라 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없음 그래서 특정 영역만 공유하거나 권한을 부여하는게 더 어려움

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

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

      • 실제로 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장되어 있기 때문에 페이지 테이블 크기가 너무 크면 사용자 영역이 부족하게 됨 → 페이지 테이블의 크기를 적절하게 유지하는 것이 굉장히 중요함

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

  • 페이징과 세그멘테이션의 각각의 장점을 취한 방식 → 새로운 단점이 생기기도 함

    • 세그멘테이션 장점

      • 가변 분할 방식이라서 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나눠서 관리할 수 있음

      • 그에 따라 다른 프로세스와 공유하기도 편하고, 각 영역에 대한 메모리 접근보호를 하기가 쉬움

    • 페이징 장점

      • 고정분할 방식으로 메모리를 효율적으로 관리할 수 있음

  • 메모리 접근 권한

    • 메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세 가지가 있음

       

    • 프로세스는 코드 여역, 데이터 여역, 스택 영역, 힙 영역이 있는데 각 영역마다 접근 권한이 있음

       

    • 코드 영역

      • 프로그램 그 자체이기 때문에 수정되면 안되므로, 읽기와 실행 권한만 있음

    • 데이터 영역

      • 일반변수, 전역변수, 상수로 선언한 변수가 저장되기 때문에 읽기 권한이 있고, 쓰기 권한은 있거나 없거나 함 실행권한은 없음

    • 스택, 힙 영역

      • 읽기, 쓰기 권한이 있고, 실행권한은 없음

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

       

  • 페이지드 세그멘테이션

    • 세그멘테이션 기법 - 세그멘테이션 테이블은 Base Address와 Bound Address로 구성됨

    • 페이징 기법 - 페이지 테이블은 프레임 번호로 구성됨

       

    • 위의 둘을 혼합해 페이지드 세그멘테이션으로 만듦 (각각의 역할은 이름만 바꼈을 뿐 달라진 것은 없음)

      • 세그멘테이션 테이블에 권한 비트를 추가함

      • Base Address는 페이지 넘버로 바뀜

      • Bound Address는 이 세그먼트 페이지 개수로 바뀜

         

    • 페이지드 세그멘테이션의 단점은 물리메모리에 접근하기 위해서 메모리에 접근을 두 번해야 된다는 것

      • 첫번째, 세그멘테이션 테이블을 참조할 때

      • 두번째, 페이지 테이블을 참조할 때 일어남

    • 위의 단점 때문에 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용함

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

  • 프로세스가 실행될 때, 프로세스를 이루고 있는 코드영역, 데이터영역, 힙영역, 스택영역과 같은 모듈이 모두 메모리에 올라와 실행된다고 알고 있음

  • 하지만 실제로는 모든 모듈이 메모리에 올라오는 것이 아니라 필요한 모듈만 올라와서 실행됨

  • 도널드 커누스의 발견 - 90:10 법칙

    • 90%의 시간이 10% 코드에서 보내는 것 → 지역성 이론이라고 함

    • 지역성(두가지)

      • 공간의 지역성

        • 현재 위치에서 가까운 데이터에 접근할 확률이 높다는 것

      • 시간의 지역성

        • 최근 접근했던 데이터가 오래전에 접근했던 데이터보다 접근할 확률이 높음

      • goto문 - 지역성 이론에 따라 성능이 좋지 않기 때문에 쓰지 않는 것을 추천

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

         

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

      • ex, 포토샵

        • 포토샵은 본 프로그램 외에도 이미지에 효과를 주는 외부 필터들이 있는데, 이 필터들을 포토샵과 같이 메모리에 모두 올리면 메모리를 많이 차지해서 프로그램이 더 무거워짐

        • 그래서 본 프로그램만 메모리에 올리고 외부 필터들은 사용자의 요청이 있을 때만 메모리로 가져오는 것이 메모리도 절약되고, 메모리를 효율적으로 관리할 수 있고, 프로세스의 응답속도도 빨라짐

           

  • 메모리 계층구조

    • 메모리는 레지스터, 캐시, 메인 메모리, 보조저장장치로 나눌 수 있음

    • 메인 메모리에 접근하는 시간

       

      • 레지스터

        • CPU 내에 존재하고, CPU의 한사이클에 접근할 수 있어서 굉장히 빠름

      • 캐시

        • CPU의 수 사이클에서 수십 사이클에 접근 가능

      • 메인 메모리

        • CPU의 수백 사이클에 접근 가능

      • 보조저장장치(HDD, SSD)

        • CPU의 수백만 사이클에 접근 가능

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

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

  • 스왑인, 스왑아웃

     

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

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

  • 메모리 관리자는 페이지 테이블을 참조해서 물리 메모리가 있는 프레임을 알아내거나 스왑영역의 위치를 알아내야 하는데, 이를 위해 페이지 테이블에는 여러가지 비트가 있음

    • 페이지 테이블을 이루고 있는 한 행을 페이지 테이블 엔트리(PTE)라고 부름

       

    • 페이지 테이블 엔트리(PTE)

       

      • 접근 비트

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

        • 메모리에 읽거나 실행 작업을 했다면 1로 바뀌게 됨

      • 변경비트

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

        • 메모리에 쓰기 작업을 했으면 1로 바뀌게 됨

      • 유효비트

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

        • 만약 유효비트가 1이라면 페이지가 스왑영역에 있고, 0이라면 물리 메모리에 있다는 의미임

      • 읽기, 쓰기, 실행 비트

        • 권한 비트로 해당 메모리에 접근권한이 있는지 검사하는 비트

    • 프로세스가 가상 메모리에 접근요청을 했을 때

       

      • 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아냄

      • 만약 물리 메모리에 없다면 Page Fault라는 인터럽트를 발생시킴

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

      • 스왑영역에 있는 데이터가 메모리에 올라가는 작업을 시작하고, 메모리에 올라갔다면 대기상태에 있던 프로세스는 다시 실행하게 됨

    • 물리 메모리와 스왑영역에서 어떻게 참조되는가(세가지)

      • 스왑이 필요없는 경우

         

        • ex, 프로세스가 페이지 0을 요청

          • 페이지 테이블의 0번 인덱스를 살펴보면 유효비트 0, 프레임 넘버 1 → 해당 주소가 물리메모리의 1번 프레임

          • 물리 메모리에 있는 1번 프레임에 접근해 데이터를 참조함

      • 스왑영역에 있는 데이터를 참조하는 경우

        • ex, 프로세스가 페이지 2번을 요청

           

          • 페이지 테이블의 2번 인덱스를 살펴보면, 유효비트가 1이고 프레임 넘버가 2임 → 페이지가 스왑영역 2번에 있다는 뜻

          • 물리메모리에 적절히 빈 공간을 찾음

          • 스왑영역 2번에 저장된 C를 물리메모리 3번 프레임으로 가져오고

          • 페이지 테이블에서 해당 엔트리의 유효비트를 0으로, 프레임 넘버를 3으로 수정함

          • 프로세스에게 데이터를 참조하게 해줌

      • 물리메모리가 꽉찼을 때 스왑영역에 있는 데이터를 참조하는 경우

        • ex, 프로세스가 페이지 1번을 요청했다고 가정

           

          • 페이지 테이블 1번 인덱스를 살펴보면, 유효비트 1, 프레임 넘버 0 → 페이지가 스왑영역 0번에 있음

          • 물리메모리로 가져오기 위해 적절한 빈공간을 찾지만 꽉 차서 여유가 없음

          • 현재 물리 메모리에서 필요하지 않다고 판단하는 영역을 스왑영역으로 옮김

          • A가 필요하지 않다고 가정하고 스왑영역 3번으로 옮김

          • 페이지 테이블에서 0번 인덱스의 유효비트를 1, 프레임 넘버를 3으로 변경

          • 물리메모리 빈공간이 된 1번으로 B를 가져옴

          • 페이지 테이블에서 1번 인덱스의 유효비트를 0으로, 프레임 넘버를 1로 수정함

          • 프로세스에게 데이터를 참조하게 해줌

        • 스왑인(스왑영역 → 물리메모리), 스왑아웃(물리메모리 → 스왑영역) 시, 어떤게 적절한지는 운영체제가 판단함 → 페이지 교체 알고리즘

• 페이지 교체정책

  • 메모리가 꽉찼을 때, 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책임

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

    • Page Fault가 발생하면, 해당 페이지를 스왑영역에서 메모리로 불러들여야하는데 메모리가 꽉차서 공간이 없다면 메모리에 있는 페이지 중 하나를 선택해서 스왑영역으로 옮겨야함

    • 메모리에 있는 페이지를 스왑영역으로 옮길 때 어떤 페이지를 선택할지 결정하는 정책을 페이지 교체 정책이라고 부르고, 페이지 교체 정책에는 여러가지가 있음

  • 페이지 교체 정책의 방법들

    • 무작위로 선택하는 방법(Random)

      • 지역성을 고려하지 않기 때문에 자주 사용되는 페이지가 선택될 때도 있어 성능이 별로 좋지 않음

      • 그래서 거의 사용되지 않음

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

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

      • 위의 단점이 있지만 구현이 간단하고 성능도 꽤 괜찮아서 조금 변형해서 많이 쓰임

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

      • 사실상 구현이 불가능한 이론적인 선택방법

      • 구현이 불가능해서 필요가 없을 것 같지만, 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰임

    • 최근에 가장 사용이 적은 페이지를 선택하는 방법(LRU - Least Recently Used)

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

      • 실제로도 Optimum 알고리즘에 근접한 성능을 보임

      • 그러나 프로그램이 지역성을 띄지 않을땐 성능이 떨어지게됨

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

      • 많은 비트를 준비하기 어려우므로 실제 LRU를 구현할 때는 접근비트를 이용해서 LRU에 근접하게 구현함

  • Optimum vs FIFO vs LRU 비교

     

    • ex, 페이지가 A B C A C D A D C A B 순서대로 요청되는 상황

       

      • 세 방법 모두 메모리가 비어있기 때문에 처음 요청에서는 전부 Page Fault가 발생함

      • A 요청 들어옴

        • 세 알고리즘 모두 Page Fault가 일어나지 않음

      • C 요청 들어옴

        • 세 알고리즘 모두 Page Fault가 일어나지 않음

      • D 요청 들어옴

        • Page Fault 발생

          • Optimum

            • 뒤에 들어오는 요청을 훑어봄

            • 페이지 B가 가장 사용되지 않을 것을 알기 때문에 페이지 B를 스왑영역으로 옮기고, B가 있던 자리에 D를 가져옴

          • FIFO

            • 먼저 들어온 페이지가 먼저 나가기 때문에 가장 먼저 들어온 페이지 A를 스왑영역으로 보내고, A가 있던 자리에 D를 가져옴

          • LRU

            • 최근에 가장 사용이 적은 페이지가 나가기 때문에 최근에 들어온 페이지의 참조 수를 계산함

            • A 2번, B 1번, C 2번으로 B가 가장 덜 사용됐으니 B를 스왑영역으로 옮기고 B가 있던 자리에 D가 들어옴

  • 빌레이디의 역설(Belady’s Anomaly)

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

      → FIFO의 가장 큰 문제임

    • FIFO에서만 발생하며 LRU에서는 발생하지 않음

  • LRU 문제점

    • 시간을 기록해야하는 LRU는 구현이 힘듦

    • 시간을 기록할 bit가 많이 필요

    • 많은 bit가 있어도 시간이 아주 오래 지난다고 가정하면 어쩔수없이 오버플로우가 발생 → 오버플로우로 값이 초기화되면서 시간을 올바르게 표현할 수 없게됨

  • 클락 알고리즘

     

    • LRU 알고리즘과 유사하게 구현하는 방법

    • 접근비트 하나만 이용

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

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

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

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

      • 클락 핸드는 시계방향으로 돌게됨

      • 만약 Page Fault가 발생해서 스왑영역으로 보내야하는 상황이 나오면, 클락 핸드는 현재 참조하고 있는 페이지의 접근비트를 봄

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

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

    • 향상된 클락 알고리즘(Enhanced Clock Algorithm)

      • 이 알고리즘은 접근비트만 이용하는 것이 아니라 변경비트까지 봄

      • 스왑 영역으로 보내지는 순위가 가장 높은 것은 접근비트가 0이고, 변경비트도 0인 페이지임

      • 그 다음으로 접근비트가 0, 변경비트가 1인 페이지임

      • 그 다음으로 접근비트가 1, 변경비트가 0인 페이지임

      • 마지막으로 접근비트가 1, 변경비트가 1인 페이지가 교체됨

  • FIFO를 사용하는 경우

    • LRU에서는 접근비트를 이용하는데, 하드웨어적으로 접근비트를 지원하지 않는 시스템에서는 FIFO를 이용할 수 밖에 없음

    • 어쩔 수 없이 FIFO를 이용하기 위해 성능을 높이는 방법을 고안함

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

      • FIFO방식에서 자주 사용하는 페이지에게는 또 한번의 기회를 줌

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

      • 이 알고리즘은 LRU보다는 안좋고, FIFO보다는 좋음

• 스레싱과 워킹셋

  • CPU 스케줄링

    • CPU 사용률을 높이는 것이 목표

      • CPU 사용률을 높이기 위해서는 동시에 실행하는 프로세스의 수, 멀티프로그래밍의 정도를 올리는 것

      • 동시에 실행하는 프로세스의 수가 늘어나면, 어떤 프로세스가 I/O작업으로 CPU를 사용할 수 없을 때 다른 프로세스로 컨텍스트 스위칭을 해서 CPU 사용률을 높일 수 있음

      • CPU 사용률을 위해 멀티프로그래밍의 정도를 높였으면, 프로세스들이 필요로하는 공간이 있기때문에 물리메모리에 프레임을 할당해야함

      • 물리메모리의 크기는 한계가 있기 때문에 모든 프로세스의 모든 프레임을 물리메모리에 올릴 수 없고, 일부는 스왑영역에 저장됨

    • 멀티프로그래밍 정도가 늘어나는 경우에 문제가 나타남

      • 멀티프로그래밍 정도가 늘어나면 제한된 물리메모리에 모든 프로세스를 올려야하고, 당장 실행되는 프레임을 제외한 나머지 프레임들은 스왑영역에 저장되고 Page Fault가 많이 발생하게 됨

      • CPU가 작업하는 시간보다 스왑작업의 시간이 더 길어지고, CPU 사용률은 떨어지게됨

      • CPU 스케줄러는 CPU 사용률이 낮아지면, 더 많은 프로세스를 메모리에 올리게되고, 이렇게 반복하다보면 어느새 CPU 사용률이 0에 가깝게 떨어지게됨

      • 스레싱

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

        • 근본적인 원인은 물리메모리의 크기가 부족한 것

        • 하드웨어적으로 해결하려면 메모리 크기를 늘리면 됨

          • 그러나 4GB 램에서 16GB 램으로 올려도 성능향상을 느끼기 힘듦

          • 현재 메모리가 프로세스들이 작업을 하는데 충분한 크기라서 스레싱이 발생하지 않는다면 크기를 늘려도 별 다른점이 없기 때문임

        • 운영체제가 스레싱을 소프트웨어적으로 해결하기 위한 방법

          • 한 프로세스가 실행될 때 너무 많은 페이지를 할당하면 다른 프로세스가 사용할 페이지가 줄어들기 때문에 효율이 떨어지게됨

          • 반대로 너무 적은 페이지를 할당하면 빈번한 Page Fault가 발생하고, 스왑요청이 많아 스레싱이 발생하게됨

          • 이를 해결하기 위한, 프로세스가 실행되는 동안 해당 프로세스에게 맞는 적절한 페이지 수 결정 방법

            • 프로세스가 실행되면 일정량의 페이지를 할당 후, 만약 Page Fault가 발생하면 더 많은 페이지를 할당하고, 반대로 Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비되는 것이라고 판단하고 페이지를 회수함

          • 어떤 페이지를 유지할 것인지 결정 방법

            • 지역성 이론을 따름

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

            • 워킹셋은 프로세스가 준비상태에서 실행상태가 되는 컨텍스트 스위칭을 할 때 사용됨

Section 9. 입출력

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

  • 주변장치 종류

    • 그래픽카드, 하드디스크, SSD, 키보드, 마우스 등이 있음

       

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

    • 버스

       

      • Address 버스, Data 버스, Control 버스로 이루어져 있음

      • I/O 디바이스는 이 세가지 버스를 따로 받을 수 있음

    • 외부 인터페이스

      • 각 하드웨어에 맞게 존재함

    • 각종 레지스터

      • 장치의 상태와 데이터를 보관할 수 있음

      • 입출력 작업을 할 때 데이터를 저장하는 역할을 함

      • 값들은 CPU가 사용하기위해 메모리로 이동되기도 함

  • 데이터의 전송단위에 따른 주변장치 분류

    • 데이터의 전송단위가 캐릭터(글자)인지, 블록인지에 따라 나뉨

      • 캐릭터 디바이스

        • 마우스, 키보드, 사운드카드, 직별렬포트 등

        • 데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음

      • 블록 디바이스

        • 하드디스크, SSD, 그래픽카드 등

        • 데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼

  • 각 장치 세부 설명

    • 버스

       

      • 예전에는 주변장치들을 하나의 버스로 연결해서 사용함

      • CPU가 작업을 하다가 I/O 명령을 만나면 직접 입출력장치에서 데이터를 가져왔는데 입출력중에는 다른 작업을 하지 못했기 때문에 CPU사용률이 떨어짐

      • 이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러개의 버스가 추가됨

         

      • CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력작업을 맡기고 다른 작업을 실행함

      • 입출력 제어기

        • 시스템 버스, 입출력 버스로 구분하여 두 개의 채널을 가지고 있음

        • 시스템 버스

          • 고속으로 작동하는 CPU와 메모리가 사용

        • 입출력 버스

          • 주변장치가 사용

        • 입출력 버스는 세부적으로 느린장치와 빠른장치를 구분하기 위해 다시 고속 입출력 버스, 저속 입출력 버스 두 개의 채널로 나뉨 → 느린장치와 빠른장치로 구분 해 속도차이로 인한 병목현상을 해결함

    • 그래픽 카드

      • 그래픽 카드가 다루는 데이터는 매우 대용량이라 고속 입출력 버스로도 감당이 안됨

      • 그에 따라 그래픽 카드는 입출력 버스에 있지 않고, 시스템 버스에 바로 연결해 사용함

    • 입출력 제어기

      • 입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮김

      • 메모리는 CPU의 명령으로 움직이기 때문에 입출력 제어기가 메모리에 접근하기 위해서는 CPU가 필요함

         

      • 입출력 제어기가 CPU의 도움이 필요없도록 DMA(Direct Memory Access - 직접 메모리 접근) 제어기가 추가됨

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

      • Memory Mapped I/O

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

• 마우스/키보드

  • 마우스

    • 볼 마우스

      • 회전을 감지해서 움직임을 처리하는 방식

    • 광학 마우스

      • 아래쪽에 작은 카메라가 표면으로 초당 1500회가 넘는 사진을 찍어 마우스의 디바이스 컨트롤러 내 DSP(Digital Signal Processor)로 보냄

      • DSP는 이 사진을 분석해 마우스의 X축 좌표와 Y축 좌표 움직임을 캐치함

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

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

  • 키보드

    • 사용자가 키보드 버튼을 누르면 키보드의 디바이스 컨트롤러가 어떤 키를 입력 받았는지 알아냄

    • CPU에게 인터럽트를 보내고 키보드 드라이버는 운영체제에게 이벤트를 보냄

    • 운영체제는 Foreground 애플리케이션으로 이 이벤트를 전달해주고, 애플리케이션에서 해당 키에 맞는 동작을 수행함

• 하드디스크/Flash Memory(SSD)

  • 하드디스크 구조

     

    • spindle

    • platter

      • 여러개의 트랙으로 구성됨

      • 표면에 자성이 있어 N극을 띄면 0, S극을 띄면 1로 인식함

      • 보통 하드디스크의 플래터 수는 2개 이상임

      • 실린더(cylinder)

        

        • 트랙은 다시 여러개의 섹터로 나뉘는데, 섹터가 하드디스크의 가장 작은 단위임

           

    • disk Arm

      • 읽기/쓰기 헤드로 플래터의 표면을 읽음

    • read/write head

      • 헤드는 disk Arm에 고정되어 있기 때문에 모든 헤드는 항상 같이 움직임

      • 헤드가 움직이면 이 헤드들은 여러 개의 플래터를 가리키게 되는데, 이때 여러개의 플래터에 있는 같은 트랙의 집합을 실린더(cylinder)라고 부름

  • 하드디스크에서 데이터 읽어오는 예시

    • 유저프로세스가 하드디스크의 특정 섹터에 접근을 위해 요청을 보냄 (ex, 실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어라)

    • 디스크암은 헤드를 실린더 C로 이동시키는데, 이를 Seek라고 부름

    • 헤드를 실린더로 이동시키는데 걸리는 시간을 Seek Time이라고 부름 → 이것때문에 하드디스크가 굉장히 느림

    • 트랙 B의 섹터 D가 헤드에 닿을 때까지 스핀들을 회전시키고, 헤드에 섹터 D가 읽히면 작업이 끝남

  • Flash Memory

    • 요즘은 하드디스크보다 Flash Memory를 더 많이 사용함

    • 데스크탑에는 Flash Memory 이점으로 많은 사람이 SSD를 사용함

    • 핸드폰, 테블릿은 하드디스크를 넣을 큰 공간이 없어서 Flash Memory를 사용함

    • 하드디스크 vs Flash Memory

      • 하드디스크

        • 기계적으로 헤드를 움직여 속도가 많이 느리고 소음도 남

        • 자기적으로 처리하는 하드디스크는 자석을 갖다대면 데이터가 손상됨

        • 스핀들처럼 회전축같은 것들이 있어서 충격에 매우 약함

      • Flash Memory

        • 전기적으로 읽기 때문에 굉장히 빠르고 조용함

        • 자석을 갖다대도 데이터가 안전함

        • 충격에 약하지 않음

        • 그러나 특정한 지점에 데이터를 썼다면 덮어쓰기가 불가능 하다는 단점이 있음 똑같은 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야하는데, Flash Memory는 지우기 가능한 횟수가 정해져있음(읽기/쓰기를 반복하면 망가져 사용할 수 없음)

Section 10. 파일시스템

• 파일과 파일시스템

  • 파일들을 하드디스크나 SSD와 같은 저장장치에 저장됨

  • 사용자가 운영체제에게 요청 시, 운영체제가 하드디스크에 안전하게 저장함

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

  • 파일 시스템

    • 파일 관리자는 가상메모리에서 메모리 관리자가 페이지 테이블을 이용해서 가상주소를 물리주소로 변환하는 것처럼 파일 테이블을 이용해서 파일을 관리함

    • 파일 시스템의 기능

      • 파일과 디렉토리를 만듦

      • 파일과 디렉토리의 수정, 삭제를 함

      • 다른 사용자로부터 파일을 보호하기 위해 접근권한을 관리함 (요즘 운영체제는 다중 사용자 기능을 지원하기 때문에 파일을 보호하기 위해서 꼭 필요한 기능임)

      • 파일의 내용이 손상되지 않도록 무결성을 보장함

      • 예기치 못한 사고로부터 백업과 복구를 함

      • 파일을 암호화해 파일을 보호함

    • 파일시스팀 전송단위

      • 하드디스크와 Flash Memory는 블록 디바이스임 따라서 전송단위가 블록임

      • 저장 단위는 블록이지만, 사용자는 바이트 단위로 파일에 접근이 가능해야하기 때문에 파일관리자가 중간에서 관리해줌

    • 파일확장자

      • 유닉스 운영체제에는 파일확장자가 없음

      • 윈도우즈는 파일확장자가 있음

      • 파일 내부 구성

        • 헤더, 데이터로 이루어져있음

        • 헤더

          • 파일의 속성들이 담겨 있음

    • 파일 디스크립터(File Descriptor)

      • 운영체제는 파일을 관리하기 위해 정보를 보관하는 파일제어블록(File Control Block, FCB)을 가지고 있는데, 이를 파일 디스크립터(File Descriptor)라고 부름

      • 파일 디스크립터는 파일마다 독립적으로 존재하고, 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동함

      • 파일 디스크립터는 파일시스템(운영체제)이 관리하고, 사용자가 직접 참조할 수는 없음

      • 사용자는 파일시스템이 건내준 파일 디스크립터로 파일에 접근할 수 있음

    • 파일 종류 분류

      • 파일은 데이터의 집합으로, 데이터의 집합을 어떻게 구성하느냐에 따라 종류를 나눌 수 있음

      • 순차파일구조

        • 파일의 내용이 연속적으로 이어진 상태 (ex, 카세트테이프)

        • 파일시스템이 사용자에게 전달해준 파일디스크립터는 파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행함

        • 파일의 다른영역으로 가고 싶을 때 - lseek함수를 이용해 파일디스크립터 위치를 옮김

           

        • 장점

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

        • 단점

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

      • 직접파일구조

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

        • 자료구조에서 해시 테이블이라는 이름으로 불리는 방식

        • json도 이 방식임

           

        • 장점

          • 해시함수를 이용하기 때문에 데이터 접근이 굉장히 빠르다는 것

        • 단점

          • 해시함수의 선정이 굉장히 중요하기 때문에 해시함수를 잘 골라야한다는 점과 저장공간이 낭비될 수 있다는 점

      • 인덱스파일구조

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

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

           

• 디렉토리

  • 디렉토리란?

    • 파일을 하나의 공간이 아닌, 관련있는 파일을 모아둘 수 있게 하기 위함

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

    • 디렉토리는 여러층으로 구성됨

      • 최상위에 있는 디렉토리 - 루트 디렉토리

      • 유닉스, 리눅스에서는 루트 디렉토리를 “/”로 표시함, 디렉토리 별 구분을 위해서도 “/”를 사용함

      • 윈도우즈는 루트 디렉토리를 파티션 이름으로 사용하는데, 보통 “C:”으로 표시함

      • 윈도우즈는 디렉토리와 디렉토리 구분을 “\”로 함

      • 디렉토리도 파일임. 단지 일반 파일에는 데이터가 저장되어 있고, 디렉토리에는 파일 정보가 저장되어 있음

         

  • 디렉토리 구조

    • 과거 - 루트 디렉토리에만 하위 디렉토리 존재했었음

    • 파일이 많아지면서 다단계 디렉토리구조가 등장함

    • 다단계 디렉토리구조

      • 어떤 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리구조

      • 운영체제는 트리구조에서 순환이 생기는데, 바로가기 기능이 있기 때문임

         

• 파일과 디스크

  • 파일은 메모리와 비슷한데, 페이징과 같이 전체 디스크 공간을 일정한 크기로 나누고, 그 공간에 주소를 할당해 관리함

  • 일정한 크기로 나눈 공간을 파일시스템에서는 블록이라고 함 (메모리에서는 페이지라고 부름)

  • 한 블록의 크기는 1~8KB

  • 파일시스템은 파일정보를 파일테이블로 관리하는데, 파일이 시작하는 블록의 위치정보도 담겨있음

  • 파일 내 블록 분류

    • 여러 개의 블록들로 이루어져 있는 하나의 파일에서, 그 블록들이 어떻게 연결되었는지에 따라 분류됨

    • 연속할당

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

      • 파일의 시작 블록만 알면 파일의 전체를 찾을 수 있음

      • 메모리에서 세그멘테이션 기법처럼 외부 단편화가 발생하기 때문에 실제로 사용되지 않는 방식임

    • 불연속할당

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

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

      • 연결할당, 인덱스 할당이 있음

      • 연결할당

        • 파일에 속한 데이터를 연결리스트로 관리함

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

           

      • 인덱스할당

        • 테이블의 블록포인터가 데이터 블록에 직접 연결하는 것이 아니라 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결함

           

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

        • 파일의 크기가 작다면, 데이터를 바로 참조하는 블록 포인터를 이용하고, 파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있음

        • 만약 더 큰 데이터가 필요하다면, 이중 간접 포인터, 삼중 간접 포인터를 이용할 수 있음 (i-node라는 이름으로 유닉스와 리눅스에서 많이 사용되고 있음)

  • free block list

    • 빈 공간을 찾기위해 매번 모든 메모리를 찾지 않기 위해 빈 공간을 모아둠

    • 만약 특정 파일 삭제 시, 파일시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가함

회고

• 일주일 동안 스스로 칭찬하고 싶은 점, 아쉬웠던 점, 보완하고 싶은 점

  • 칭찬하고 싶은 점 : 이번주 강의가 조금 어렵게 느껴졌지만 포기하지 않고 끝까지 잘 학습한 점

  • 아쉬웠던 점 : 이번주에 회사일이 많아서 내용 중 이틀 치를 몰아서 듣게 되었는데 충분한 학습을 하지 못했다는 아쉬움이 남음

  • 보완하고 싶은 점 : 중간중간 이해가 안되는 부분들이 있었는데, 그 부분을 반복학습 해야겠습니다🙌

• 다음주에는 어떤 식으로 학습하겠다는 스스로의 목표

  • 수료식 전까지 따로 스터디 스케쥴이 없는 것 같으니 이번주 강의를 다시한번 봐야겠습니다💪