[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로, 프레임 넘버를 변경한다.

      • 이제 물리메모리에 공간이 생겼기 때문에 스왑 영역에 있는 필요한 영역을 물리메모리로 가져온다.

        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에 추가한다.

    • 이렇게 처리하면 사용자는 파일이 삭제된 것처럼 느껴지는데 사용했던 블록의 데이터는 그대로 남아있다.

    • 범죄를 저질러서 증거를 인멸하더라도 포렌식을 통해 데이터를 복구할 수 있다.

[자료구조와 알고리즘]

[java로 실습한 것은 깃허브에 올려두었다.]

• 정렬 - 삽입정렬

  • 동작

    • 선택 정렬과 마찬가지로 배열을 두 영역으로 나눠서 진행

    • 정렬되지 않은 영역에서 데이터(가장 앞에 있는 숫자)를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘

    • 정렬되지 않은 영역의 첫 번째 원소를 정렬된 영역의 가장 뒤에 있는 원소부터 역순으로 비교

  • 성능

    • 버블정렬, 선택정렬과 같은 패턴 : 이중 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)]