OS의 메모리 관리

이전에는 OS의 자원관리 기능 중 프로스세스관리(스케줄링, 동기화, 교착상태해결)에 대해 배웠고, 이제는 자원 관리 기능 중 기억장치 관리에 대해 배울 것이다.

그 전에 알아야 할 몇 가지 배경들이 있다

1. 운영체제는 각 프로세스들을 메모리 각각의 공간에 할당하고, 프로세스가 다른 프로세스에 접근하는 것을 막는다.

  메모리에 프로세스가 올라가 있는 상태 그림

  

-> 메모리에서 프로세스 시작 위치를 저장하는

    base register

-> 프로세스에게 할당된 메모리 크기 저장하는

    limit register

두 개의 레지스터 값을 통해 프로세스들의 메모리

공간을 나눈다.

2. 주소바인딩

    

  - 주소바인딩이란? 프로세스가 접근해야 하는 값과 함수에 대한 주소가 정해지는 것

 

   프로그램이 컴파일 되어 메모리에 올라간 후, CPU에 의해 명령어가 한 문장씩 실행되게 되는데 CPU가 명령문을

   실행함으로써 발생하는 주소를 logical address 혹은 virtual address라고 한다.

   그리고,

   실제 접근해야 하는 메모리 주소를 physical address라고 한다.

   (컴파일 : 원시코드에서 목적코드로 옮기는 과정. 예를 들면 c++에서 기계어로)

   logical address와 physical address는 프로그램이 실행되는 과정 중 어느 시점에 바인딩이 되냐에 따라 다르다.

   

1) 컴파일 시점

2) 로드 시점

3) 실행 시점

  

   1) 컴파일 시점 주소 바인딩

   - 컴파일 될 때, 컴파일러에서 명령어들과 변수의 메모리 주소가 정해지는 것.

   - 여기서 정해지는 주소는 실제 메모리 주소이기 때문에, 이 때의 logical address와 physical address는 같다.

 -> 컴파일 시점에 주소가 결정이 나면 프로그램을 다른 시스템에서 실행하였을 때 해당 시스템의 메모리를 어디서부터 할당해주는지를 나타내는 Starting Point가 다르거나 이미 그 주소에 다른 프로그램이 실행 중이라면 이 프로그램은 실행을 할 수 없게 된다.

   2) 로드 시점 주소 바인딩

     - 프로그램이 컴파일 되고, 메모리에 올라갈 때 CPU에서 주소 계산이 일어난 후 주소가 발생하는 것

     - 컴파일 된 프로그램 내의 각 변수나 명령어의 주소는 특정 값을 기준으로 정해진다.

 -> 프로그램이 올라간 메모리 주소의 base register 값에 특정 값을 더하여 주소를 만들어 냄.

     - CPU 내에서 계산되고 발생한 logical address는 physical address와 같다.

     

-> 로드 시점 주소 바인딩으로 주소가 정해진 프로그램은 한번 메모리에 올라가면 종료될 때까지 그 위치에 존재하게 된다.

 

   3) 실행 시점 주소 바인딩

     - 매번 명령어가 실행될 때마다 주소가 계산되는 것

     - 프로그램 메모리 위치가 매번 바뀌기 때문에 이러한 방법을 사용한다.

-> CPU에서 나온 임의의 주소가 MMU라는 곳을 거쳐 실제 주소로 바뀌어 접근하게 된다.

 CPU에서 발생한 주소가 logical address이고 MMU를 통해 바뀐 주소가 메모리의 실제 주소인 physical address이므로

 실행 시점 주소 바인딩에서는 두 주소가 다르다.

MMU(Memory-Management Unit) : CPU가 메모리 접근하는 것을 관리하는 하드웨어 부품

3. 위 프로그램이 실행되는 과정 그림을 보면, 프로그램은 컴파일 후 메모리에 올리는 로드 과정과, 라이브러리 파일을 연결해주는 링킹 과정을 통해 최종적으로 메모리에 올라감을 확인할 수 있다.

   그 외, 프로그램은 메모리 공간에 올라가서도 지속적으로 메모리 공간을 차지 하는 것이 아니라 

   운영체제에 의해 swapping되기도 하는데 이것들에 관련되어서 간략하게 말해보겠다.

  1) Dynamic Loading 

      - Dynamic Loading은 한정적인 메모리 공간으로 인해 생겨난 방법

      - 메모리 공간이 한정되어있고 그 공간의 크기가 그렇게 크지 않았을 때 프로세스의 모든 모듈들을 올리기에는 공간이 부족하여 해당 모듈이 필요하면 그때그때 올려주는 방법이 Dynamic Loading

      - 이 방법을 사용하게 되면 이용되지 않는 모듈은 메모리 공간에 올라가지 않기 때문에 그만큼의 메모리 공간을 절약할 수 있게 된다.

      - 하지만 현재는 가상 메모리 기법(뒤에서 배울건데, 미리 말하자면 paging)을 사용하여 메모리 공간이 충분히 많다고 가정을 하고 로드를 하기 때문에 이 방법은 사용되지 않고 있다.

  2) Dynamic Linking

- 기존 링크 과정은 라이브러리 파일을 서로 다른 프로그램이 사용할 때 매번 프로세스 메모리 공간에 해당 라이브러리를 확보하여 프로세스에 함께 올렸다. 

  하지만 이는 같은 라이브러리 파일이 메모리 공간에 여러 번 올라감으로 메모리 공간의 낭비로 이어지게 된다. 

  그리하여 나온 방법이 Dynamic Linking

- 실행되기 전까지는 링킹이 되지 않고 실행이 될 때 특정 라이브러리 파일이 최초로 한 번 메모리에 올리고 이 라이브러리를 사용하는 프로세스들은 라이브러리의 위치를 가리키는 stub 포인트를 갖게 되어 라이브러리를 참조한다. 

   -> 라이브러리가 메모리에 여러 번 올라가는 것을 방지하여 메모리 낭비를 막는다.

  3) Swapping

- 프로세스 스케줄링에서 중기스케줄링에 해당하는 것.

- 우선순위가 높거나 중요한 프로세스가 메모리에 올라가려 할 때 공간이 부족하면 현재 메모리 위에 올라가 있는 프로세스 중 수많은 알고리즘 중 하나를 이용하여 어떤 프로세스를 잠시 디스크에 저장을 하고 우선순위가 높은 프로세스를 먼저 수행한다.

       이 프로세스가 작업을 마치면 디스크에 있던 프로세스를 다시 메모리에 올리게 됩니다.

     - 우선순위가 높거나 중요한 프로세스가 중간에 들어가는 것을 Swap-in이라 하며 

  자리를 내어주어 디스크로 빠지게 되는 과정을 Swap-out 이라 한다.

         -> Swap-out 된 프로세스가 다시 메모리에 올라갈 때는 원래 있던 자리로 돌아가지 않을 수 있다.

     - 수많은 알고리즘 중 상황에 맞는 알고리즘을 고르는 것과 디스크와 메모리 간의 속도 차로 인해 발생하는 이슈들이 존재

대강, 메모리에 관련한 주소, 로드, 링킹 등에 대에 배웠다면

진짜로 운영체제가 메모리를 어떻게 관리하는지에 대해서 배우겠다.

Memory-Management Strategies

- 효율적인 기억장치 운용을 위해서는 프로그램이나 데이터를 언제 주기억장치로 반입하고, 어디에 배치하며, 완료된 작업의 프로그램이나 데이터는 어떻게 제거할 것인가를 결정하는 관리가 필요하다.

- 기억장치 관리 정책은 3가지 반입전략, 배치전략, 교체전략이 있다.

  

  반입전략 : 프로그램이나 데이터를 주기억장치에 언제 적재할 것인지를 결정하는 전략

  배치전략 : 반입되는 프로그램이나 데이터, 즉 입력되는 작업을 주기억장치의 어디에 위치(할당)시킬 것인지 결정하는 전략

  교체전략 : 새로 반입되는 작업에 필요한 기억장소를 확보하기 위해 적재된 어떤 프로그램과 교체할 것인가를 결정하는 전략

  

각각의 전략들에 대해 자세히 살펴보면

1. 반입전략(Fetch Strategic)

 1) 요구 반입(Demand) : 프로그램이나 데이터의 참조가 요구될 때만 적재 (ex) demand paging(다음 포스팅에서 배움)

 2) 예상 반입(anticipatory) : 요구될 가능성이 프로그램이나 데이터를 예상해서 적재

                                    명령어와 데이터가 메모리에 적재되는 과정

2. 배치전략(Placement Strategic)

 - 메모리 할당 단위는 Byte 단위가 아니라 시스템의 Block 단위

 - 2가지 할당 방법이 존재

1) 연속할당(Continuous Memory Allocation):  연속된 공간의 메모리를 프로세스에 할당해 주는 방법

   ① 최초 적합(first-fit) : 가용공간 중에서 첫 번째 분할 영역에 배치

   ② 최적 적합(best-fit) : 가용공간 중에서 배치 후 남는 공간, 단편화가 가장 적은 곳에 배치

   ③ 최악 적합(worst-fit) : 가용공간 중에서 배치 후 남는 공간, 단편화가 가장 큰 곳에 배치

          

      최초적합과 최적적합이 speed와 storage utilization면에서 최악보다 더 낫다.

 

     위에서 말했듯이, 메모리는 시스템의 block단위로 할당되는데

     block단위로 할당하다 보니 메모리 낭비가 일어난다 -> 단편화

    단편화(Fragmentation) : 기억장치 공간에서 프로그램이나 작업에 할당할 수 없는 조각난 공간

    - 내부 단편화 : 분할된 영역에 프로그램이나 작업이 할당된 후 남는 기억공간

    - 외부 단편화 : 분할된 영역이 작아 프로그램이나 작업을 할당 받지 못하는 기억공간

           예) 메모리 공간이 총 100이고, 3개의 프로세스에게 메모리 공간이 그림처럼 할당 되어있을 때

현재 여유 공간의 총합은 10+10+30=50, 하지만 이 때 다른 프로세스가 메모리 공간 40요구시 할당 불가

외부 단편화 해결방법

ⓛ 압축(compaction) : 할당된 메모리 공간들을 한쪽으로 모아 연속된 공간을 확보하는 것

                                   집약 또는 쓰레기 수집이라고 한다.

                                   실행시간에 주소 바인딩이 일어나는 프로그램들만 가능

② 통합(coalescing) : 기억장치 내에 인접되어 있는 단편화 공간을 하나의 공간으로 합치는 것

   2) 비연속 할당 : 가상메모리를 활용해서 할당하는 방법 

 후에, 가상메모리에 대해 더 자세히 다룰 거임.

 가상메모리는 보조기억장치, 실제 메모리가 주기억장치에 저장된 것

ⓛ 페이징(paging)

         - 프로그램 공간인 logical memory는 page라는 일정한 크기의 블록, physical memory은 frame이라는 블록으로 분할한 후 Page table을 이용하여 페이지의 logical address와 프레임의 physical address를 사상시켜 관리하는 방법

         - page 크기와 frame크기는 같으며, page table의 인덱스 수는 page수와 같다.

   - 외부단편화는 없지만, 내부단편화가 생길 수 있다.  

     

   - 페이지의 가상 주소(virtual address)를 프레임의 실주소(physical address)로 변환하는 과정을 자세히 다루면

     가상주소는 페이지 번호(p)와 변위(d), 실제주소는 프레임 번호(f) + 변위(d)

     

   

 수행중인 프로세스가 가상 주소 참조

↓

페이징 기법을 통해 페이지 p가 프레임 f에

있음을 알아냄

↓

실주소 알아냄

32byte physical address 4byte page일때의 예시

   - Page table 역시 메모리에 올라가 있다.

           이때 Page Table Base Register(PTBR)는 Page table의 메모리 위에서의 시작 점을 의미하고

           Page Table Length Register(PTLR)는 Page table의 크기를 나타내며 이 두 값으로 잘못된 주소 접근을 방지한다.

   - paging의 문제점 1

           Page Table이 메모리에 올라가 있기 때문에 데이터나 명령문에 접근하기 위해서는 두 번의 메모리 Access가 일어나게 된다(페이지 테이블에 한번, 페이지테이블을 통해 실제 메모리에 한번) -> 비효율적

           **그래서 이 문제를 해결하기 위해 Translation-Look aside Buffer(TLB) 방법사용**

            Page table을 고속의 연관기억장치에 넣는 방법이다.

TLB : 일종의 캐시의 역할을 하는 레지스터

           메모리의 여러 번 접근을 막고자, page table의 내용을 TLB에 저장하여 바로 메모리에 접근할 수 있도록 한다.

           시작은 비어있는 TLB로 Page table을 통해 메모리를 두 번 Access 하게 되지만 한번 Access된 Page table의 정보는 TLB에 저장되어 다음부터는 TLB를 통해 메모리에 바로 Access 하는 것을 가능

   

   - paging의 문제점 2

            Logical memory 가 page단위로 나누어지면, 앞서 말했듯이 내부 단편화가 일어날 수 있다.

             

**그래서 이 문제를 해결하기 위해 Valid-Invalid Bit를 사용**

현재 프로세서에 사용되고 있는 page을 경우 v로 표시(접근 허용), 사용되고 있지 않으면 i로 표시(접근 불가) 

-> 실제로는 0과 1로 저장

           예를 들어 v로 표시되어 있는 entry는 0번 page가 2번 frame에 실제 올라가 있다는 것을 의미

                          i로 표시되어 있으면 6번 page는 프로세스에서 사용되지 않는 영역이거나, 아직은 사용되지 않고 backing store (swap area)에 저장되어 있는 경우

   - paging의 문제점 3

            공통의 코드를 갖는 여러 프로세스들이 page table을 가질 때 중복의 문제 발생할 수 있다.

           

 **그래서 이 문제를 해결하기 위해 하나의 공통된 코드 부분 page만 메모리에 올려 공유**

예를 들어 위의 P1, P2, P3는 ed1, ed2, ed3의 같은 code를 가지고 있는 page다. 

따라서 ed1, ed2, ed3는 각각의 page table에 주소 변환이 3, 4, 6으로 동일하게 매핑되어 물리 메모리에 1개씩만 올라간다.

   - 페이징과, 페이징 방법의 문제점에 대해 배웠다면 페이지 테이블의 다른 3가지 구조도 보자.

페이지 테이블구조1. Hierarchical Page table(계층적구조)

             : 기본 Page table 구조는 Logical address를 하나의 테이블에 담았다면, 계층적 구조는 그 Logical address를 다시 여러 테이블로 나눈 구조이다.

             예시) 두 table로 구성한 Two-level Page table 구조.

 페이지 테이블구조2. Hashed Page table

             : Logical address 중 페이지 번호 p를 hash function의 입력값으로 넣어 나온 결과값으로 hash table을 검사하여 해당하는 physical memory를 찾는 구조

             같은 hash 결과값에 대해서는 리스트를 이용해 하나의 hash table위치에 연결해 놓는다.

  예시)

  페이지 테이블 구조3. Inverted page table(역전구조)

              : Physical address의 입장에서 만들어진 테이블 구조다.

               첫 번째 프레임은 테이블의 첫 번째에 저장되며 테이블은 각 프레임은 어떤 프로세스와 대응되는지에 대한 정보를 담고 있다. 

   그러므로 이전에는 테이블에 단순히 몇 번째 프레임인지에 대한 정보만을 담고 있었다면 이번에는 프로세스 번호인 pid 값도 담고 있다.

             역전 구조 테이블은 프로세스 당 하나가 아닌 전체적으로 하나만 갖고 있어도 되는 장점을 갖고 있지만 테이블의 크기가 크기 때문에 그만큼 검색에 소요되는 시간이 늘어나게 된다.

비연속할당의 페이징 기법 다음 세그멘테이션 기법

② 세그멘테이션(segmentation)

         - 페이징 기법은 logical memory – page, physical memory- frame이라는 단위로 나누었지만, 세그멘테이션은 모두 고정된 크기가 아닌 가변크기인 세그먼트(segment) 단위로 나누는 방법이다.

         - 세그먼트 단위는 일련의 논리적 구조 단위이다.

           예를 들어 main program, function, method, object, stack, symbol table, local variables 같은 단위로 이루어져 있다

   - 각 세그먼트는 고유한 이름과 길이를 가진다.(이름은 번호로 대체)

   - 주소변환을 위해 세그먼트테이블(segment table)을 사용

세그먼트 테이블 구성: 세그먼트 번호(s), 한계주소(limit), 기준주소(base)

세그먼트 테이블의 구조는 페이지 테이블의 구조와 다르다.

           페이징은 모두 같은 크기여서 따로 크기에 대한 정보를 가지고 있지 않지만, 세그멘테이션은 크기가 모두 달라서 크기를 알려주기 위해 해당 segmentation의 시작점을 알리는 base 정보와 끝을 알리는 limit을 가지고 있어야 한다. 

   - 내부 단편화는 없지만 외부 단편화가 발생

   - 세그멘테이션의 가상주소를 실주소로 변환하는 과정을 보자

     가상주소는 세그먼트 번호 번호(s) + 변위(d), 실제주소는 세그먼트 번호 기준 + 변위

변위(d)가 한계주소크기(limit = 세그먼트 크기)을 초과하는 지 검사를 통해 잘못된 주소 접근을 막는다.

3. 교체전략(Replacement Strategic)

   (ex) page replacement(다음 포스팅에서 배움)

비할당기법에 사용되는 virtual memory에 관한 설명을 다음 포스팅에서 더 자세히 하겠다.

특히 virtual memory를 이용한 paging 방법중 demand paging에 대해