OS의 메모리관리2

Virtual memory(가상메모리)

- 한정된 physical memory의 한계를 극복하고자 디스크와 같은 보조기억장치를 활용해 더 많은 메모리를 활용할 수 있게 하는 것.

 

- virtual memory에서 paging 기법을 사용할 때 거의 demand paging 기법으로 구현된다.

   Demand paging

 - swapping + paging

 - 실제로 필요한 page만 물리 메모리로 가져오는 방식

-> physical memory의 여유공간이 얼마나 되는지 고민할 필요 x

   프로그램이 전체 다 메모리에 올라오는 것일 아니라, 동시에 많은 프로그램을 메모리에 올려 작업 수행 가능

  한꺼번에 올리는 소스의 양이 적어 disk와 memory간 I/O작업속도 빨라짐

 1) Valid-invaild bit를 사용한다.

    (전 포스팅에서 말한 페이지 문제점2 방법에서 약간의 정보가 더 추가된 것)

          

case 1) Bit = Valid

          해당 Page Table의 인덱스는 접근이 가능하며(이전에 다루었던 내용),

          또한 해당 부분은 실제 메모리에 올라와 있다는 뜻.

case 2) Bit = Invalid

          해당 Page Table의 인덱스는 접근 불가능하거나 혹은

          해당 부분은 현재 Disk에 존재한다는 뜻.

 

          만약, page 접근 요청을 하였는데 physical memory에 없는 상태

          즉, bit가 invalid 인 상태를 page fault라고 한다.

 

    2) Page fault : 지금 실행시켜야 할 page가 실제 메모리에 올라와 있지 않은 상황

                          CPU의 자원 효율성을 떨어뜨리는 현상이다.

                        -> 자원 할당받은 시간내에 CPU자원을 사용하기 보다는 I/O작업에 시간 소비

    해결법?

    Step 1) Page fault 발생하면 CPU는 운영체제에게 알리고(trap), 운영체제는 잠시동안 CPU의 작업을 멈춘다.

    Step 2) 운영체제가 Disk에서 해당 부분을 찾아 실제 메모리의 비어 있는 frame에 올리고, 

   page table의 해당 부분의 bit를 valid로 갱신한다.

    Step 3) page fault를 발생시킨 명령어를 다시 실행하여 작업을 재개한다.

       

    그림으로 보면 아래와 같다

++ 만약, 실제 메모리에 비어있는 frame이 없을 경우에는?

-> page replacement 알고리즘 사용 필요

 3) Page replacement : 요구된 페이지가 반입될 공간(frame)을 확보하기 위해 교체될 페이지(victim page)를 선택하는 알고리즘

     

다시 한번 더 page fault 해결하는 과정을 자세히 보면

      Step 1) page fault 발생후 원하는 page를 disk에서 찾는다.

Step 2) 비어 있는 frame을 찾는다.

                   비어 있는 frame이 있다면 그곳을 사용

                   비어 있는 frame이 없다면 page replacement알고리즘을 통해 victim 찾음

      Step 3) disk에서 가져온 frame을 2번 과정에서 찾은 frame에 넣고 frame table과 page table 갱신

      Step 4) 프로세스 재실행

      

page replacement를 그림으로 보면 아래와 같다

Page replacement의 범위

      ① Global replacement : victim page를 찾을 때 모든 프로세스의 모든 페이지에서 찾음

      ② Local replacement : victim page를 찾을 때 해당 프로세스 내에서만 찾음

      Page replacement algorithm의 종류

      ① FIFO algorithm :

           실제 메모리에 가장 먼저 들어온 페이지를 교체하는 방법 

           이해가 쉽고 설계가 간편하지만, 자주 사용 중인 페이지가 오래되었다는 이유만으로 교환되어버리는 불합리가 생김

또한, 벨라디의 모순이 생길수 있음

           벨라디 모순 : 프레임이 증가될수록 페이지 부재율이 감소되어야 하는데

                             오히려 페이지부재율이 증가되는 현상

② OPT(Optimal) algorithm :

           앞으로 가장 오랫동안 사용되지 않은 페이지를 교체하는 방법

           페이지 부재율이 가장 적은 방법

           단, 앞으로 어떤 페이지가 사용될 것인지 아닌지 예측하기가 힘들다

③ LRU(Least Recently Used) algorithm :

           현 시점에서 가장 오랫동안 사용되지 않은 페이지를 제거하는 방법

           참조된 시간을 기록하기 위해, 계수기(counter)나 스택(stack)을 두어야 하므로 시간 오버헤드가 발생하고, 실제 구현은 복잡하다.

(스택으로 구현 예시) : 참조되면 top으로 옮김

④ NUR(Not Used Recently) algorithm

           LRU와 비슷한 알고리즘이지만, LRU의 단점인 시간 오버헤드를 적게 하는 방법

           2개의 bit(참조 비트, 변형 비트)를 이용해 최근에 사용되지 않은 페이지를 교체하는 방법

         (참조,변형)   

         1. (0, 0) : 최근에 사용되지도 변경되지도 않은 경우 - 교체되기 좋은 page

         2. (0, 1) : 최근에 사용되지 않고 변경만 된 경우

         3. (1, 0) : 최근에 사용은 되었으나 변경되지 않은 경우

         4. (1, 1) : 최근에 사용되었고 변경도 된 경우

           

   교체의 우선순위는 1 > 2 > 3 > 4 이다.

⑤ SCR(Second Chance Replacement) algorithm

           FIFO 교체 알고리즘을 기반으로 하는 알고리즘

           페이지들을 circular queue 형태로 나타낸다.

           1개의 bit(참조 비트)를 이용해, 페이지의 참조비트가 0이면 교체하고 1이면 0으로 바꾼 후 피드백 시켜 다시 한번 더 기회를 준 후 다음에도 0이면 교체한다.

+    Thrashing : 자주 페이지 부재(page fault)가 발생하여 페이지 교체(page replacement)가 빈번하게 일어나는 현상

     

      원인?

        가상 메모리를 사용하다 보면 실제 물리 메모리 공간보다 논리적 메모리 공간이 큰 것처럼 사용할 수 있어서 효율적이다.

        효율적이라는 이유로 점점 많은 프로세스를 동시에 메모리에 올린다면, 하나의 프로세스가 할당 받는 자원의 양은 점점 작아지고 곧 할당 받는 frame의 수도 적어진다

        Frame의 수가 적어지면 그만큼 page fault가 많이 발생하고, 그럼 page replacement가 증가하면서 자원의 활용보다는 I/O작업에 시간을 더욱 쏟는 단점이 발생하며 CPU의 효율성 역시 굉장히 떨어진다.

Multi-Programming은 CPU 자원의 효율성을 높이기 위해 보다 많은 프로세스에게 CPU를 할당해주면서 

자원을 더욱 바쁘게 효율적으로 관리하는 기법

 Thrashing 해결법?

각 프로세스에게 충분한 frame 할당해줘야함, 다중 프로그래밍의 정도를 줄여야함

-참고-

기본적인 frame 할당법은 2가지로 나뉨

         ① Fixed allocation

            - Equal allocation : 프로세스 목적과 성격에 상관없이 모든 프로세스에게 고정된 양의 frame할당

            - Proportional allocation : 프로세스의 사이즈에 비례하여 frame할당

         ② Priority allocation

            - 우선순위가 높은 프로세스에게 더 많은 양의 frame할당

     

-참고-

 각 프로세스에게 필요한만큼의 page frame 수를 예측하는 법?

 -> locality(지역성)을 근거로 둔 working set(워킹셋) 통해서 예측한다.

           Locality : 프로세스가 실행되는 동안 기억장치 내의 모든 정보를 균일하게 참조하는 것이 아니라 현재 실행되는 주소 부근에서 집중적을 참조한다는 특성

            시간 지역성: 최근 참조된 기억장소가 가까운 시간내에 또 참조될 가능성이 높다는 특성

            공간 지역성: 기억장소가 참조되면 그 근처의 기억장소가 참조될 가능성이 높다는 특성     

           Working set: 실행 중인 프로세스가 일정 시간 동안에 참조하는 페이지들의 집합

                             지역성에 기반한 모델

         워킹셋의 크기가 실제 메모리보다 커지면 하나의 프로세스를 종료하는 방법을 통해 thrashing 예방 가능

4) Performance of Demand Paging

---

가상메모리의 부가 장점

1) 공유메모리 사용

  - 여러 프로세스 간의 communication의 한 가지 방법으로 공유 메모리를 사용할 수 있는데,

  - demand-paging 기법을 사용할 경우 다른 프로세스의 각각의 페이지가 같은 프레임을 가리키도록 하면 공유 메모리를 사용할 수 있다.

2) copy-on-write 메커니즘

  - 부모 프로세스를 clone하여 자식 프로세스를 생성하였을 때,

  - 처음에는 같은 메모리를 사용하도록 하다가 그곳에 Write가 발생하였을 때 메모리를 copy하는 것으로 이것 또한 공유 메모리처럼 같은 프레임을 가리키도록 하였다가 복사가 되었을 때 새로운 프레임을 할당하면 된다

3) memory mapped file

  - file을 접근하는 것을 메모리 접근하듯이 페이지를 할당하여 할 수 있도록 하는 것이며, 메모리 접근 속도가 훨씬 더 빠르므로 효율적이라 할 수 있다.

    (나중 포스팅에서 배우겠지만 file은 disk에 저장되어 있음. disk 접근 속도는 주기억장치 접근 속도보다 느리니깐)