[운영체제] 가상 메모리

Virtual Memory (1), (2)

🔊 이화여자대학교 반효경 교수님의 KOCW 2014년 1학기 운영체제 강의를 들으며 정리한 노트입니다.
      캡쳐한 이미지 중 따로 출처 명시를 하지 않은 이미지 또한 반효경 교수님 강의 자료에 있음을 밝힙니다.

버츄얼 메모리 기법은 전적으로 운영체제가 관여를 하고 있다.

Demand Paging

Demand Paging : 요청이 있으면 그 페이지를 메모리에 올리겠다는 얘기다.

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시에 invalid bit이 set되어 있으면
    → "page fault"

이 챕터부터는 앞 부분에 메모리 관리 기법 중에서 페이징 기법을 사용하는걸로 가정을 한다. 그리고, 실제로도 대부분의 시스템은 페이징 기법을 사용을 하고 있다. 이때 이 페이징 기법은 프로그램이 실행될 때 그 프로세스를 구성하는 주소 공간의 페이지를 전부 메모리에 한꺼번에 올리는게 아니라 ‘디멘드 페이징 기법’ 이라는 것을 사용한다. 즉, 그 페이지가 요청이 됐을 때 그걸 메모리에 올려놓는다는 것이다.

이렇게 함으로써 얻는 효과는 위와 같다. (I/O 양의 감소 등)
프로그램을 구성하는 주소 공간 중에서 실제로 빈번히 사용되는 부분은 지극히 제한적이다. 특히 좋은 소프트웨어 일수록 방어적으로 소프트웨어를 만들기 때문에, 정말 이상한 사용자가 이상한 짓을 하더라도 문제가 생기지 않도록 하는 그런 방어적인 코드가 프로그램에서 대부분을 차지하고 있다는 것이다. 그래서, 그런 코드는 거의 대부분의 경우 사용이 안되는데 그럼에도 불구하고 그런 페이지들을 한꺼번에 메모리에 올려놓는다면 메모리가 낭비될 것이다.

거기에 비해서 디멘트 페이징을 쓴다면 필요한 것만 메모리에 올리기 때문에 I/O의 양이 상당히 감소하게 된다. 그리고, 이를 통해서 물리적인 메모리를 사용하는 양이 감소하게 되고, 그러면 현대적인 컴퓨터처럼 멀티 프로그래밍 환경 즉, 프로그램 여러개가 동시에 메모리에 올라가는 환경에서는 더 많은 프로그램, 더 많은 사용자가 동시에 메모리에 올라갈 수 있기 때문에 훨씬 효과적이라는 것이다. 그리고, 이를 통해서 더 빠른 응답시간을 기대할 수가 있겠다.

물론, 빠른 응답 시간은 생각하는 관점에 따라서는 다를 수도 있다. 프로그램이 시작될 때 메모리에 통째로 올려놓으면 그 다음부터는 디스크에 갔다 올 필요가 없으니까 응답 시간이 안 필요한 것 아니냐? 그렇게 생각할 수도 있다. 그렇지만, 여기서 빠른 응답 시간이라는 것은 시스템 전체적으로 생각하자면 어차피 한정된 메모리 공간에 여러 프로그램이 동시에 실행이 되고, 그러면 메모리에 더 빈번하게 사용될 더 의미 있는 정보를 올려놓으려면 디멘드 페이징을 쓰는게 나을 것이다. 그래서, 한정된 메모리 공간을 더 잘 사용하기 때문에 가능하면 디스크에 I/O가 더 줄어들고 메모리에서 직접 서비스하는 비율이 높아지기 때문에 그래서, 응답시간이 더 좋아진다고 생각하면 되겠다.

우리가 페이징 기법에서 각각의 페이지 테이블 엔트리마다 Valid / Invaild bit이라는게 있다고 했다.

Memory에 없는 Page의 Page Table

위 그림을 보면 하나의 프로그램을 구성하는 논리적인 메모리가 있다. 이 프로그램은 지금 여러개의 페이지들로 구성이 되있고, 페이지 테이블을 통해서 페이지들에 대한 주소 변환 정보가 담겨있고, 물리적인 메모리가 주어져 있다. 그리고, 전 챕터에서는 보지 못했던 그림이 하나 더 있다. 맨 오른쪽에 디스크가 있다Backing Store…swap area라고 하는 부분이 있다.

그래서 이 프로그램을 구성하는 이 페이지들(맨 왼쪽) 중에서 당장 필요한 부분은 디멘드 페이징에 의해서 물리적 메모리에 올라가 있을 것이고, 그렇지 않은 부분은 (맨 오른쪽) Backing store 즉, swap 영역에 내려가 있게 된다.

그래서, Valid / Invalid bit에서 Invalid의 의미는 페이지가 물리적인 메모리에 없는 경우에… 예를 들면, A, B, C, D, E, F 중에서 A, C, F는 물리적인 메모리에 올라와 있기 때문에 0, 2, 5번 페이지는 Validv로 표시돼있고, 실제로 주소 변환 정보가 의미가 있는 값이 들어있는 것이다.
반면에, 나머지 페이지들은 지금 물리적인 메모리에 올라와있지 않고, 그림과 같이 backing store에 내려가있기 때문에 Valid / Invalid bit이 Invalid로 표시돼있다.

그 다음에 또 한 가지는 이 프로그램이 사용하지 않는 주소 영역이 있을 수가 있다. 그 경우에도 페이지 테이블의 엔트리는 주소 공간의 크기 만큼 만들어지게 되고, 거기에는 Invalid로 또 표시가 된다. 즉, 이 프로그램을 구성하는 페이지는 A부터 F까지 이다. 그리고, G하고 H ..6번, 7번 페이지는 사용이 안되는 페이지 인데, 이 주소 공간에서 이 만큼의(0~7만큼의) 주소 영역을 지원해주기 때문에 페이지 테이블에는 7번까지 엔트리가 만들어지고, 그래서 사용이 안되는 이런 페이지들(G, H)에 대해서 지금 Valid / Invalid bit이 Invalidi로 표시돼있는 것이 6번, 7번의 경우이다.

1번, 3번, 4번페이지는 이 프로그램에 의해서 사용이 되는 페이지이다. 그렇지만 Invalidi로 표시돼있는데, 이것은 이 1번, 3번, 4번페이지들이 물리적인 메모리에 올라와있지 않고, 디스크의 스왑 영역에 내려와있기 때문에 Invalidi로 표시한 것이다. 그래서, 주소 변환을 통해서 물리적인 프레임 번호를 얻을 수 있는 경우에만 이렇게 Validv라고 표시가 돼있는 것이다.

그래서, 우리가 디멘트 페이징을 쓰기 때문에 프로그램을 최초로 실행시키면 이 페이지 테이블에는 전부 엔트리가 Invalidi로 표시가 되있을 것이다. 그랬다가 그 페이지가 메모리에 올라가면 Invalid로 표시됐던 비트가 Validv로 바뀌면서 해당하는 페이지 프레임 번호가 엔트리에 적히게 되는 것이다.

CPU가 논리 주소를 주고 “메모리 몇 번지를 보겠다..” 그러면 먼저 주소 변환을 하러 올 것이다. 예를 들면, (그림의) 1번 페이지에 대해서 CPU가 접근을 하려고 (주소 변환을 하려고) 봤더니 Invalidi이다. 그러면, 이 페이지1번, B가 메모리에 없다는 얘기일 것이다. 그런 경우에는 어떻게 해야될까?
일단, 그 페이지를 디스크에서 메모리로 올려야 할 것이다. 이것은 I/O 작업이다. 사용자 프로세스가 직접 못하는 일이다. 그래서, 이렇게 주소 변환을 하려고 봤는데 Invalidi로 표시된 그런 페이지에 대해서는 page fault라는 현상이 발생한다. 요청한 페이지가 메모리에 없는 경우를 “page fault가 났다” 이렇게 부르는 것이다.

page fault가 나면, CPU는 자동적으로 운영체제한테 넘어가게 된다. 이걸 페이지 폴트 트랩이 걸린다고 이야기하는데, 일종의 소프트웨어 인터럽트에 해당하는 것이다. 그래서, 그런 경우에는 운영체제가 CPU를 가지고, Fault난 페이지를 메모리에다가 올리는 그런 작업이 필요할 것이다.

그래서, 페이지 폴트에 대한 처리 루틴이 운영체제에 정의가 되있다.

Page Fault

• invalid page를 접근하면 MMU가 trap을 발생시킴 (page fault trap)

  그래서 만약에, 엔트리에 invalid로 표시된 페이지를 접근하면 주소 변환을 해주는 하드웨어가 트랩을 발생시키게 된다.

• Kernel mode로 들어가서 page fault handler가 invoke됨

  그러면 CPU가 자동적으로 운영체제한테 넘어오게 되는 것이다. 그러면, 운영체제에 페이지 폴트를 처리하는 코드..페이지 폴트 핸들러가 실행이 시작이 되는 것이다.

• 다음과 같은 순서로 page fault를 처리한다

  1. Invalid reference? (eg. bad address, protection violation) → abort process.

     운영체제에서 잘못된 요청이 아닌지? 예를 들면, 주소가 잘못되있거나, 이 프로세스가 사용하지 않는 주소라던지, 또는 접근 권한에 대한 위반을 한 경우에는 강제로 중단을 시키는 절차가 있고

  2. Get an empty page frame. (없으면 뺏어온다: replace)

     그렇지 않고, 정상적인 메모리 요청이라고 하면 그 페이지를 디스크에서 메모리로 올려줘야 될 것이다. 근데 쓰다보면 메모리라는게 다 꽉 찼을수도 있다. 만약에 비어있는 페이지 프레임이 없고, 메모리가 꽉 차 있다면 메모리에서 뭔가 페이지 하나를 쫓아내야지만 그 자리에 지금 요청한 페이지를 올려놓을 수 있을 것이다.

     그래서, 빈 페이지를 하나 획득해야되는데, 만약 없으면 하나를 쫓아내야된다는 것이다.

  3. 해당 페이지를 disk에서 memory로 읽어온다

     빈 페이지가 획득이 됐으면 디스크에서 그 페이지를 메모리로 올려놓게 된다. 디스크에서 메모리로 올려놓는 작업은 대단히 느린 작업이다.(보통 메모리보다 디스크가 수십만배에서 백만배까지 느림)

     1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)

        그래서, 이러한 페이지 폴트에 대해서 디스크 I/O를 하게 되면 이 프로세스가 CPU를 계속 가지고 있어봐야 CPU가 계속 낭비가 된다. 그래서 전에 이미 말했던 파일 입출력을 하는 경우와 마찬가지로 페이지 폴트가 난 경우에도 CPU를 페이지 폴트난 프로세스로부터 뺏어서 이 프로세스의 상태를 블럭으로 만들어주고, 당장 CPU를 사용할 수 있는 ready상태의 프로세스한테 CPU를 넘겨줘야될 것이다.

        그런데, 넘겨주기 전에 일단 디스크한테 “그 페이지를 읽어와라” 라고 디스크 컨트롤러한테 부탁을 해야될 것이다.

     2. Disk read가 끝나면 page tables entry 기록, valid/invalid bit = “valid”

        그래서, 부탁을 하고 나중에 디스크 I/O가 끝나게 되면, 다시 인터럽트가 걸려서 운영체제가 CPU를 가지고 “아, 그 페이지 폴트 처리가 끝났구나” 그러면 페이지 테이블 엔트리에다가 valid로 표시를 해놓고, 그리고 해당하는 페이지 프레임 번호를 적어놓게 되고,

     3. ready queue에 process를 insert → dispatch later

  4. 이 프로세스가 CPU를 잡고 다시 running

     그런 다음에, 나중에 이 페이지 폴트났던 프로세스가 CPU를 다시 잡게 되면, 그때 메모리 주소 변환을 하면 이번에는 페이지 폴트가 나지 않고, 정상적으로 MMU에 의해서 주소 변환이 될 것이다.

  5. 아까 중단되었던 instruction을 재개

     그러면, 이제 그 이후 부분을 계속 실행을 할 수가 있는 것이다.

Steps in Handling a Page Fault
위 내용을 보여주는 그림이다.

그림을 보면, 메모리 레퍼런스reference가 있었는데, 주소 변환을 하려고 봤더니 invalidi로 표시가 된 것이다. 그러면, 이 페이지가 메모리에 올라와있지 않다는 얘기니까 트랩② trap이 걸려서 CPU가 운영체제operation system한테 자동으로 넘어간다. 그러면, 운영체제는 Backing store에 있는 그 페이지를 물리적인 메모리로 올려놓는다③ page is on backing store, ④ bring in missing page.(만약에 빈 페이지 프레임이 없으면 뭔가를 쫓아내고 거기다 올려놔야되고) 올려놓는 작업이 다 끝났으면 해당하는 프레임 번호를 엔트리에다가 적어놓고, invalidi였던 것을 validv로 바꾸는 것이다⑤ reset page table. 그런 다음에 나중에 CPU를 다시 얻어서 주소 변환을 하게 되면⑥ restart instruction validv로 되있고, 주소 변환을 정상적으로 해서, 해당하는 물리적인 메모리의 페이지 프레임을 접근할 수가 있게 될 것이다.

이런식으로 페이지 폴트가 처리가 된다.

Performance of Demand Paging

근데, 페이지 폴트가 났을 때 디스크를 접근하는건 대단히 오래걸리는 작업이기 때문에 “페이지 폴트가 얼마나 나느냐?” 그거에 따라서 메모리 접근하는 시간이 크게 좌우가 되는 것이다.

• Page Fault Rate 0 ≤ p ≤ 1.0

  그래서, 우리가 페이지 폴트의 비율을 0에서 1 사이 값으로 볼 수가 있을 것이다.

  • if p = 0, no page faults

    만약 페이지 폴트 비율이 0이라면, 절대 페이지 폴트가 안나고, 메모리에서 다 참조가 되는 경우를 의미

  • if p = 1, every reference is a fault

    페이지 폴트 비율이 1이라면, 매번 메모리 참조할 때마다 페이지 폴트가 난다는 얘기.

    실제로 페이지 폴트 비율이 어느정도되느냐? 시스템에서 조사를 해보면 0.0xx 이런식으로 나오게 된다. 즉, 대부분의 경우는 페이지 폴트가 나지 않고, 메모리로부터 직접 주소 변환을 할 수가 있고, 그렇지 않은 특별한 경우에(메모리에 올라와 있지 않은 경우에) 페이지 폴트가 나서 디스크 접근을 필요로 한다는 것이다.

• Effective Access Time

  대부분의 경우는 페이지 폴트가 안나지만, 페이지 폴트가 한 번 났다.. 그러면 이거는 엄청난 시간을 겪어야되는 일이다.

  메모리 접근하는 시간을 우리가 페이지 폴트까지 감안해서 한 번 계산을 해보면 아래와 같이 되는 것이다.

  = (1 - p) x memory access
     + p (OS & HW page fault overhead
             + [swap page out if needed]
             + swap page in
             + OS & HW restart overhead)

(1 - p)는 페이지 폴트가 안나는 비율이 되겠다. 페이지 폴트가 안나는 비율 만큼은 메모리 접근 시간만 걸리게 되겠고,

p 페이지 폴트가 나는 비율 만큼은 그 경우에는 엄청난 시간이 걸리는 것이다. 운영체제로 CPU가 넘어가서 하드웨어적으로 페이지 폴트를 처리하는 그런 오버헤드가 있어야 되고OS & HW page fault overhead, 또 만약에 메모리에 빈 공간이 없으면 어떤 페이지 하나를 쫓아내야되고swap page out if needed, 그리고 그 자리에 디스크에서 읽어온 페이지를 올려놔야되고swap page in, 그 다음에 OS가 또 페이지 테이블에 Valid로 표시하고..그런 작업들이 다 끝나고, 나중에 CPU를 얻으면 restart를 하는OS & HW restart overhead 그런 과정이기 때문에… 페이지 폴트가 났을 때는 대단히 오버헤드가 크게 되는 것이다.

Free frame이 없는 경우

• Page replacement

  아까 빈 페이지가 없는 경우에는 뭔가를 쫓아내야된다고 말했었다. 쫓아내는 걸 ‘페이지 리플레이스먼트’ 라고 부른다.

  OS가 하는 업무이다. 어떤 페이지를 메모리에서 쫓아내고, 그 자리에 새로운 페이지를 올려놓을 것인가? 그것을 결정

  • 어떤 frame을 빼앗아올지 결정해야 함
  • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음

• Replacement Algorithm

  ‘페이지 리플레이스먼트’를 해주는 알고리즘을 ‘리플레이스먼트 알고리즘’ 이라고 부른다.

  이 알고리즘은 가능하면 페이지 폴트가 나지 않고, 메모리에서 직접 처리할 수 있게 해주면 좋을 것이다. 뭔가는 쫓겨나야되는데, 만약에 페이지를 쫓아냈더니 그 페이지가 다시 참조가 된다 그러면, 엄청난 시간을 또 겪어야되기 때문에…

  • page-fault rate을 최소화하는 것이 목표

    그래서, Replacement Algorithm은 가급적 Page Fault Rate이 낮아지도록 해야된다는 것이다. 가급적 Page Fault Rate이 0에 가깝도록 해줘야되는게 이 알고리즘의 목표가 되는 것이다.

  • 알고리즘의 평가

    • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

  • reference string의 예
    1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

    reference string이라는 것이 있고, 이것은 시간 순서에 따라서 페이지들을 서로 다른 번호를 붙여놓고 페이지들이 참조된 순서를 이렇게 나열해 놓은 것이다.

    즉, 처음에 1번 페이지가 참조되고, 그 다음에 2번 페이지, 3번, 4번 페이지.. 그 다음에 다시 1번 페이지, 2번 페이지, 5번 페이지 이런식으로 참조가 됐다는 얘기다.

    그래서 만약에, 1번 페이지가 (맨 1번째에서)이미 한번 사용이 됐는데, 이게 메모리에 올라가 있다가 Replacement Algorithm이 이걸 쫓아냈으면 여기서(5번째에서) 페이지 폴트가 또 날거고, 그렇지 않고 맨 첫번째에서 1번 페이지를 쫓아내지 않았으면, 나중에는 메모리에서 직접 참조가 될 수가 있을 것이다.

Page Replacement

그래서, 페이지 리플레이스먼트라는거는 어떤거를 쫓아낼지를 결정하고, 희생양victim이 결정이 됐으면 그 친구를 디스크로 쫓아내는 것이다. 근데, 만약에 이 프로그램이 디스크에서 메모리로 올라온 이후에 내용이 변경됐다고 하면 즉, write가 발생했다고 하면 이 친구를 쫓아내기만 하면 되는게 아니라 쫓아낼 때 변경된 내용을 메모리에서 백킹 스토어에다 써줘야된다.
근데, 아까 이 백킹 스토어에 있던 걸 메모리에 올린 다음에 이 친구가 쫓겨날 때까지 변경된게 없다 그러면, 물리적 메모리에서 지워버리기만 하면 되는 것이다.

그래서, 어떤 victim이 선정되면 일단 쫓아내고① swap out victim page 그 자리에 새로운 페이지를 올려놔야 될 것이다③ swap desired page in. 그럼 이 단계에서 쫓겨난 페이지에 대한 테이블 엔트리에는 비트를 invalidi로 바꿔줘야겠고② change to invalid, 그 다음에 메모리에 올라온 페이지에 대해서는 그 프레임 번호f를 엔트리에 적어주고 그리고, 이 비트를 validv로 바꿔주면 되는 것이다④ reset page table for new page.

이 역할을 운영체제가 하게 되는 것이다.

Optimal Algorithm

그러면 도대체 어떤 알고리즘이 가장 좋은 알고리즘이냐?
알고리즘 중에서 가장 좋은 알고리즘이 바로 이 ‘옵티멀 알고리즘’이라는 것이다.

이것은 페이지 폴트를 가장 적게하는 알고리즘이다.

근데, 실제 시스템에서는 사실 미래를 알 수가 없다. 예를 들면, 1번 페이지가 참조가 됐다 그러면 미래에 1번 페이지가 언제 참조될지를 모르기 때문에, 이것을 쫓아내야될지 말아야될지를 결정을 하기가 어려운데,

• MIN (OPT): 가장 먼 미래에 참조되는 page를 replace

  이 옵티멀 알고리즘은 미래에 참조되는 페이지들을 미리 다 안다고 가정을 하는 것이다. 그래서, 실제 시스템에서 사용될 수는 없다.

• 4 frames example
  1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

  

• 미래의 참조를 어떻게 아는가?

  • Offline algorithm

    그래서 이 알고리즘을 우리가 특별히 ‘오프라인 옵티멀 알고리즘’ 이라고 부른다.

    이 오프라인이라는 것은 실제 시스템에서 온라인으로 사용하는게 아니라 페이지 레퍼런스 스트링(1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5)을 미리 알고 있다는 가정 하에 이 알고리즘을 운영을 하는 것이다.

    그러면, 이 알고리즘이 어떻게 운영되는가? 설명을 하면, 위 그림과 같이 운영을 한다. 가장 먼 미래에 참조되는 페이지를 쫓아낸다. 그러면 한번 그 상황이 생겼을 때 어떻게 동작하는지 한번 보자.

    처음에는 메모리가 다 비어있을 것이다. 그러니까 1번 페이지는 아무리 옵티멀 알고리즘이라도 페이지 폴트가 난다. 그래서 1번이 메모리에 올라오고, 그 다음 2번도 처음 참조됐으니까 페이지 폴트가 나서 메모리에 올라오고 3번, 4번도 마찬가지다.
    그 다음에 1번이 다시 참조가 된다. 그러면 이것은 이미 메모리에 올라와있기 때문에 페이지 폴트가 나지 않고, 메모리에서 직접 참조가 된다. (위 그림에 빨간색은 페이지 폴트가 난 경우를 표시한 것이고, 연보라색은 이 참조에 대해서 페이지 폴트가 나지 않고, 메모리에서 직접 참조된 경우를 나타내고 있다)
    2번도 마찬가지다 이미 메모리에 올라와있기 때문에, 직접 참조가 된다.
    그 다음에 5번이 요청이 들어왔는데, 이 5번은 지금 메모리에 없다, 1, 2, 3, 4만 있기 때문에… 그래서 페이지 폴트가 나고, 그러면 이제 메모리가 꽉 찼기 때문에 1, 2, 3, 4중에 하나를 쫓아내야지 5번이 메모리에 올라갈 수가 있다.

    그때, 이 오프라인 옵티멀 알고리즘은 1, 2, 3, 4중에 어떤걸 쫓아내느냐 하면 가장 먼 미래에 참조되는 페이지를 쫓아낸다. 미래를 볼 수 있기 때문에 미래를 보는 것이다. 1번은 바로 다음에 참조가 된다. 그러니까 안쫓겨나고, 2번이 그 다음에 또 참조되니까 안쫓겨남, 3번이 그 다음에 참조되니까 3번도 살았다. 4번이 그 다음에 나오긴 하지만, 네 개 중에서는 가장 먼 미래에 참조되는게 4번이라는 것이다. 그래서 5번을 메모리에 보관하기 위해서 1, 2, 3, 4중에서 4번을 쫓아내고, 그 자리에 5번을 집어넣게 된다.

    이런식으로 운영을 하는게 ‘오프라인 옵티멀 알고리즘’ 이고, 이 알고리즘을 사용하는 경우에 쭉 따라가보면 총 6번의 페이지 폴트6 page faults를 발생시키게 된다.

    이게 ‘옵티멀 알고리즘’이라고 했기 때문에, 어떤 알고리즘을 쓰더라도 페이지 폴트를 6번보다 더 적게 낼 수는 없다는 의미이다. 수식을 통해서 증명을 할 수도 있지만 상식적으로 생각해보면, 가장 먼 미래에 참조되는 페이지를 쫓아내면 그게 “페이지 폴트를 가장 적게할 것이다” 라는 것을 짐작할 수 있다.

• 다른 알고리즘의 성능에 대한 upper bound 제공

  어쨋든, 이 알고리즘은 미래를 다 안다고 가정하기 때문에, 실제 시스템에서 사용하는 것은 불가능하고 다만, 실제 시스템에서 사용하는 다른 알고리즘들에 대한 성능의 upper bound를 제공한다는 것이다.

  이게 무슨 이야기냐… 아무리 좋은 알고리즘을 만들어도 이거보다 성능이 더 좋을 수가 없다는 얘기다. 내가 알고리즘을 하나 만들었다, 근데 그 성능이 오프라인 옵티멀 알고리즘하고 거의 비슷한 성능이 나왔다. 그러면 더이상 좋은 알고리즘을 만들 수가 없다는 이야기다.

  upper bound를 제공하기 때문에 참고로 사용하는 알고리즘이라는 것이고,

  • Belady’s optimal algorithm, MIN, OPT 등으로 불림

    이 오프라인 옵티멀 알고리즘을 Belady(빌레디)라는 사람이 만들어서 Belady’s optimal algorithm 이렇게도 부르고 또는, 페이지 폴트를 제일 적게 낸다고해서 MIN 알고리즘이라고도 부르고, 또 옵티멀이니까 줄여서 OPT(옵트) 이런식으로 이 알고리즘 이름을 부르기도 한다.

FIFO (First In First Out) Algorithm

여기부터는 실제 시스템에서 사용 가능한 즉, 미래를 모르는 상태에서 운영하는 알고리즘들에 대해서 나온다.

우리가 미래를 모를 때, 미래를 모르지만 미래를 잘 예측해야된다. 왜냐하면, 지금 상황이 어떤 페이지를 쫓아내면 미래에 참조가 안 될 페이지를 잘 쫓아낸 것인지를 예측해야되는 것이기 때문이다. 그러면, 미래를 모를 때 제일 참고할만한 중요한 단서가 뭘까? 미래를 모를 때는 과거를 보면 된다.

일단 FIFO 알고리즘을 먼저 설명한다. 이 알고리즘은 First In First Out(선입선출) 방식으로 운영되는 알고리즘이다.

• FIFO: 먼저 들어온 것을 먼저 내쫓음

  즉, 메모리에 먼저 들어온 페이지를 먼저 쫓아내는 방식이라는 것이다.

그림은 앞에서 봤던 동일한 레퍼런스 스트링에 대해서 메모리에 페이지 프레임이 3개 있는 경우하고, 4개 있는 경우에 FIFO 알고리즘으로 페이지 운영을 쭉 해본 것이다. 그래서 먼저 들어온 거를 만약에 쫓아내야되는 상황에서는 쫓아내는 방법이다.

이 알고리즘은 아주 특이한 성질이 하나 있다.
그게 뭐냐하면 메모리를 3페이지 프레임에서 4페이지 프레임으로 메모리 크기를 늘려주면 보통은 성능이 좋아져야될텐데, 그러나 메모리 크기를 늘려주는데 성능이 더 나빠지는 즉, 페이지 폴트 수가 더 늘어나는 이런 상황이 발생할 수가 있다는 것이다.

• FIFO Anomaly (Belady’s Anomaly)

  이러한 기이한 현상을 FIFO Anomaly다. “FIFO 알고리즘의 특이한 현상이다”해서 이렇게 부르고, 또 Belady(빌레디)라는 사람이 얘기한 것이기 때문에 Belady’s Anomaly다 이렇게도 부른다.

  • more frames ≠> less page faults

    이 현상은 메모리 프레임을 늘려줬는데 성능이 더 나빠지는 그런 경우가 발생할 수가 있기 때문에 이런 나쁜 성질을 이야기하는 것이다.

LRU (Least Recently Used) Algorithm

실제로는 FIFO 알고리즘 같이 Anomaly 같은 현상이 발생 안하고, 가장 메모리 관리나 이런데서 제일 많이 쓰는 알고리즘이 여기에 소개되는 LRU(Least Recently Used) 알고리즘이다.

가장 최근에 덜 사용된 그런 페이지를 쫓아내는 알고리즘이다.
제일 오래 전에 사용된걸 쫓아내겠다는 얘기이다.

• LRU: 가장 오래 전에 참조된 것을 지움

  먼저 들어왔지만 들어온 다음에 재사용이 되면, 최근에 사용된거니까 안쫓아낸다는 것이다.

운영을 해보자. 그림을 보면 처음에 1, 2, 3, 4가 들어올 때는 어쩔 수 없이 처음이니까 페이지 폴트가 나고, 그 다음에 1, 2는 이미 메모리에 올라와있으니까 메모리에서 직접 참조가 된다. 그 다음에 5번을 메모리에 보관하기 위해서 1, 2, 3, 4중에 뭔가 하나를 쫓아내야한다. (근데, 지금 이 알고리즘들은 온라인 알고리즘이기 때문에 미래는 모른다. 실제 시스템에서 사용하려면 미래는 모른다. 과거를 가지고 어떤걸 쫓아낼지 결정할 수가 있는데, 이 LRU 알고리즘은 가장 오래 전에 사용된 페이지를 쫓아낸다는 것이다.)

보면 1, 2, 3, 4중에 2번이 가장 최근에 사용됐다. 그렇기 때문에 2번은 살아남았고 그거보다 조금 전에 1번이 사용됐으니까 1번도 살아남았고, 그 전에 4번이 사용됐으니까 4번도 살아남았고, 가장 오래 전에 사용된게 3번이다.

그래서, 이 LRU 알고리즘은 하나를 쫓아내야될 때 가장 오래 전에 사용된 3번을 쫓아내고, 그 자리에 5번을 집어넣는 것이다.

FIFO 알고리즘인 경우에는 조금 다르다.

네 개의 페이지 프레임일 때 1, 2, 3, 4, 1, 2, 5 5번이 참조 될 때, 가장 먼저 메모리에 들어온 것은 1번이기 때문에 1번을 쫓아내고, 그 자리에 5번을 집어 넣었다. 그러니까 1번이 메모리에 들어온 이후에 들어올 때만 사용된게 아니고, 이후에(다섯번째에서) 또 사용이 되었는데도 불구하고, 단지 먼저 들어왔다는 이유로 먼저 쫓겨난게 FIFO 알고리즘이고…

LRU 알고리즘은

들어온 기준이 아니고 실제로 (들어온 것 포함해서) 들어온 이후에 사용된 것 기준으로 가장 오래전에 사용된 그런 페이지를 쫓아낸다는 것이다.

최근에 참조된 페이지가 가까운 미래에 참조될 가능성이 높은 성질을 이용하는 것이다. 프로그램이 참조하는 페이지들도 최근에 참조된 페이지가 다시 참조되는 성향이 높더라는 것이다. 그래서, 이런 LRU 알고리즘을 쓰면 비교적 page fault rate을 줄일 수가 있다는 얘기다.

LFU (Least Frequently Used) Algorithm

LFU 알고리즘은 가장 덜 빈번하게 사용된 페이지를 쫓아내자는 것이다.

• LFU: 참조 횟수(reference count)가 가장 적은 페이지를 지움

  참조 빈도.. 다른 말로 참조 횟수라고 부를 수가 있고, LFU 알고리즘은 참조 횟수가 제일 적은 페이지를 메모리에서 쫓아낸다.

  일상생활에서도 참고 할만한 성질이지만, 실제로 프로그램에서도 이런 성질이 나타나기 때문에 이런걸 활용하는 것이다.

  그래서, 과거에 참조 횟수가 많았던 페이지는 미래에 다시 참조될 가능성이 높다. 그런 페이지는 쫓아내지 말자는 것이다.

  • 최저 참조 횟수인 page가 여럿 있는 경우

    참조 횟수가 가장 적은 페이지가 동률로 여러개 있을 수도 있다.
    그런 경우에 LFU 알고리즘은 어떤걸 쫓아낸다고 특별히 명시하고 있지는 않다.

    • LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다

      아무거나 쫓아내도 참조 횟수가 제일 적은걸 쫓아낸거니까 상관은 없는데,

    • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다

    우리가 조금 더 성능을 높이고 싶다면 참조 횟수가 동률인 페이지 중에서 마지막 참조 시점이 더 오래된 것을 쫓아내는게 조금 더 나을 것이다.

  • 장단점

    • LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
    • 참조 시점의 최근성을 반영하지 못함
    • LRU보다 구현이 복잡함

LRU와 LFU 알고리즘 예제

LRU 알고리즘과 LFU 알고리즘 이 2가지 알고리즘은 장단점이 있다. 이 예제를 통해서 설명한다.

그림을 보면 페이지를 위한 레퍼런스 스트링이 쭉 주어져 있고
1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5, ...,
그 다음에 페이지 프레임Page Frames은 4개가 있다.
그리고 우측의 그림은 이 페이지들이page 1, page 2, page 3, page 4 시간에 따라서 참조된 이런(1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5, ...) 순서대로 각 페이지 별로 화살표를 표시해 놓은 것이다. 즉, 1번 페이지page 1가 먼저 4차례 참조가 됐고, 그 다음에 2번 페이지page 2가 2번 참조가 되고, 3번 페이지page 3가 또 2번 참조가 된 다음에, 다시 2번 페이지page 2가 1번, 4번 페이지page 4 1번 참조되고.. 현재시각이 여기(굵은 파란선)라는 것이다.

이(현재시각) 시점에 1, 2, 3, 4가 모두 메모리에 올라와있는 상태인데, 현재 5번 페이지가 참조가 되기 때문에 이 4개의 페이지page 1, page 2, page 3, page 4 중에 어느 하나를 쫓아내야되는 상황이다.

그럼, LRU 알고리즘은 이 중에 1번 페이지를 쫓아낸다. 왜냐하면, 현재 시점(현재시각 시점)부터 마지막 참조 시점까지의 거리가 page 4가 제일 가까우니까 page 4가 제일 우선순위가 높고, 그 다음이 page 2 그 다음이 page 3 그 다음 page 1이 제일 오래되었기 때문에 1번 페이지page 1를 쫓아내는 것이다.
근데, 이 LRU 알고리즘은 마지막 참조 시점만 보기 때문에, 그 이전에 어떤 기록을 가지고 있는지를 전혀 생각하지 않는다는게 약점이다. 즉, page 1은 가장 오래 전에 참조되긴 했지만, 굉장히 많은 참조가 과거에 있었다는 사실을 LRU는 전혀 고려하지 않는다. 그게 문제점이다.

반대로, LFU 알고리즘은 참조 횟수를 기준으로 page 1, page 2, page 3, page 4순으로 4번, 3번, 2번, 1번이니까 제일 참조 횟수가 적은 4번 페이지 page 4를 쫓아낼 것이다. 근데, 이 알고리즘은 또 문제점이 비록 4번page 4이 참조횟수가 1번이지만, 이제 막 여러번의 참조가 시작되는 그런 상황인데 이 친구page 4를 쫓아내면 이것도 또 문제가 될 것이다. 이게 LFU 알고리즘의 단점이다.

서로 간에 장단점이 있다. 그래서, 이 두 알고리즘의 장단점을 보완하는 Page replacement알고리즘에 대해서는 지난 한 20년이 넘게 대단히 많은 연구가 논문으로도 나오고 또 실제로도 시스템에서 개발이 된 바가 있다.

LRU와 LFU 알고리즘의 구현

그럼 이 알고리즘들이 어떻게 구현이 되는가? 구현 방식에 대해서 설명을 할 것이다.

LRU 알고리즘은 이와 같이 메모리 안에 있는 페이지들을 참조 시간 순서에 따라서 한 줄로 줄 세우기를 한다.
그래서, 맨 위에 있는 페이지가 가장 오래전에 참조된 페이지이고, 아래로 갈수록 참조 시점이 더 최근이고, 제일 아래쪽에 페이지는 가장 최근에 참조된 페이지다. 이게 링크드 리스트(Linked List)형태로 운영체제가 페이지들의 참조 시간 순서를 관리하는 것이다.

그래서, 만약에 어떤 페이지가 메모리에 들어오거나 또는 이 메모리 안에서 다시 참조가 되거나 하면 그 페이지는 참조 시점이 가장 최근이다.

그러니까 그 페이지는 볼 것도 없이 제일 아래쪽으로 보내면 된다.(이게 Doubly Linked List(이중 연결 리스트)형태로 만들면 최근에 참조된 위에서 두번째꺼를 맨 아래로 빼가지고, 위에서 첫번째꺼와 세번째꺼를 연결하는건 별로 어려운 일이 아니다. 그래서 이 친구New reference는 제일 아래 쪽으로 이동을 시킴)
그 다음에 replacement(리플레이스먼트)… 쫓아내야될 때는 제일 위에 있는걸 쫓아내면 되겠다.

그래서, 이 LRU 알고리즘은 이런식으로 리스트 형태로 구현을 하면 시간 복잡도가 O(1)order of 1이 된다.

O(1) 이라는건 쫓아내기 위해서 비교가 필요 없다는 얘기다.

우리가 이 LRU 알고리즘을 이런식으로 구현하지 않고, 만약에 어떤 페이지가 참조될 때마다 그 시간을 기록해놓은 다음에 어떤 페이지를 쫓아낼까 결정할 때는 시간을 다 비교해보고, 그 중에 제일 타임 스탬프가 오래된 페이지를 쫓아내는 방식으로 구현한다고 하면 매번 어떤거를 쫓아낼지를 결정하기 위해서 만약에 이 메모리의 페이지 개수가 n개 라고 하면, O(n) 의 시간이 걸린다. n개의 시간을 다 비교해보고, 가장 오래된거를 쫓아내야된다는 것이다.

근데, 이렇게 하면 대단히 비효율적이다. 이 리플레이스먼트 알고리즘이라는 것은 그때그때 어떤걸 쫓아낼지를 바로 결정해야되는데, 페이지 수가 n개…예를 들어서, 100만개가 된다면, 100만개 페이지의 참조 시간 순서를 비교해보는거는 상당히 오래 걸리는 작업이니까… 그래서 그런식으로 하는 것보다 어떤 페이지가 참조될 때마다 그 친구를 제일 아래쪽에다가 매달고 쫓아낼 때는 맨 위에 있는걸 쫓아내고 이러면 비교가 전혀 필요 없을 것이다.

그래서, LRU 알고리즘은 이런식으로 링크드 리스트 형태로 O(1)의 시간에 구현을 하는 방법을 사용하게 된다.

그러면 LFU 알고리즘은 어떻게 구현을 할 수가 있을까?

비슷하게 한 줄로 줄 세우기를 해서 구현을 생각해볼 수가 있겠다.
즉, 가장 참조 횟수가 적은 페이지가 맨 위에 있고, 밑으로 내려갈수록 참조 횟수가 더 많은 페이지를 이렇게 위치를 해놓고, 쫓아낼 때는 가장 참조횟수가 적은 페이지를 쫓아내겠다. 뭐 가능할 것 같은데… 사실은 이런 한 줄로 줄세우기를 할 수가 없다.

왜냐하면, 어떤 페이지가 참조가 됐을 때 LRU 알고리즘은 1번만 참조되도 지금 참조된 페이지가 제일 가치가 높다. 가장 최근에 참조된거니까…시간 순서로 따지는거기 때문에, 1번만 참조되면 그 친구가 왕이다. 제일 아래로 내려올 수가 있는데…

LFU 알고리즘은 이 친구New reference가 참조됐다는건 참조 횟수가 1이 늘어난 것이다. 그래서, 참조 횟수가 1이 늘어났다고해서 가장 참조 횟수가 많은 페이지가 아니다. 그래서 이 친구New reference는 제일 밑으로 내려올 수 있는게 아니라

비교를 해서 어디까지 내려갈 수 있는지를 확인해봐야 된다.

최악의 경우에는 여기 있는 페이지들이 전부 참조 횟수가 같았다고 하면, 1번의 참조로 인해서 제일 아래쪽까지 내려가야될 수도 있을 것이다. 그렇지만, 그냥 내려갈 수 있는게 아니라 하나하나 비교를 해서 내가 과연 어느 친구까지 이겨낼 수 있는가? 내가 너를 이길 수 있다. 그러면 자리 바꿈을 하고, 또 다음 친구하고 횟수적으로 싸워서 이길 수 있다면 자리 바꿈을 하고, 또 싸워서 내가 더 참조 횟수가 많네? 자리 바꿈을 하고…다시 맨 아래에 있는 친구하고 비교해보니까 이제는, 맨 아래 페이지가 참조 횟수가 더 많다 그러면 나New reference는 맨 아래로부터 두번째 자리까지 내려갈 것이다.

그래서, 이런식으로 구현을 하면

LFU 알고리즘은 이 안에 페이지의 갯수가 n개라고 하면, O(n)order of n의 시간이 걸린다.

그래서, LFU 알고리즘은 이런식으로 구현을 하지 않고…

heap(힙)이라는 자료구조를 이용해서 구현을 하게 되고, 그러면 O(log n)order of log n의 구현이 가능하다.

힙은 이런식으로 생겼다. 자식이 2개씩 있는 이러한 이진트리 형태로 되있다.(complete binary tree 이다)

그래서, 맨 위에는 참조 횟수가 제일 적은 페이지를 놓고, 부모보다는 자식이 참조 횟수가 더 많은 페이지…즉, 밑으로 갈수록 참조 횟수가 더 많은 페이지를 놓는 것이다.

그럼 이 상황에서 어떤 페이지가 참조가 됐다New reference. 그러면 참조 횟수가 1이 늘어났으니까 밑으로 내려갈 수가 있을 것이다. 근데, 한 줄로 줄세우기를 했을 때하고 다르게 이렇게 세워놓으면, 이 친구New reference하고 직계자식 2개 하고만 비교를 한다.
그래서, 둘 중에 내가 지금 1번 참조가 늘어났기 때문에, 참조 횟수가 더 많아졌다 그러면…

자리 바꿈을 하는 것이다.(아래에 있는게 위로 올라가고, 내가New reference 참조 횟수가 1 늘어났으니까 내려가고..) 그 다음에 또 더 내려갈 수 있는지 자식 둘 하고 비교를 해봐서 참조 횟수가 아직도 더 많다 그러면, 자리 바꿈을 해서 내려가는 것이다.

그래서, 언제까지 내려갈 수 있느냐? 이제는 자식 둘 보다 내가 참조 횟수가 더 많지가 않으면 여기(그림 화살표 마지막)까지만 내려갈 수가 있는 것이다. 그래서, 해당하는 경로만 따라 내려가면서 내가 어디까지 내려갈 수 있는지를 찾아보는 것이다.

근데, 이 전체가 n개라고 하면 이런 이진트리를 구성하면 높이가 log₂n 이 된다. 그래서, 비교 횟수가 많아봐야 log n이 되는 것이다. 그리고, 쫓아낼 때는 root에(맨 위에) 있는 것을 쫓아내고, 힙을 재구성하면 된다.

n하고 log n은 굉장히 다르다.

n이 100만이라고 하면 이렇게 하면 100만번의 비교가 필요할 수가 있는데,

log₂에 100만을 하면 이 값이 10에서 20사이의 숫자가 나온다. 그래서, 비교 횟수가 열 몇번으로 크게 줄어든다. 즉, 100만번 비교할게 열 몇번으로 줄어든다.

그래서, 이 알고리즘은 항상 적어도 O(log n)order of log n이하는 되어야지만 리플레이스먼트 알고리즘(Replacement Algorithm)으로 쓸 수 있지, O(n)order of n인 그런식으로는 구현이 안된다는 것이다.

다양한 캐싱 환경

• 캐싱 기법

  • 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식

    한정된 빠른 공간에다가 데이터를 저장해놓으면 다음에 똑같은 데이터에 대한 요청이 왔을 때 느린 저장장치까지 가지 않고, 캐시로부터 바로 서비스를 하면 더 빠르다.

    가상 메모리의 페이징 시스템도 한정된 빠른 공간이 물리적인 메모리(메인 메모리)고, 느린 저장장치가 Backing store(swap area)이다. 그래서, 가능하면 물리적인 메모리로부터 직접 서비스를 하고, 그렇지 않고 요청된 페이지가 물리적인 메모리에 없을 때 페이지 폴트가 났다고 하는데 그럴 때만 백킹 스토어에서 물리적인 메모리로 읽어와야되는 것이다. 이런 식의 것을 우리가 ‘캐싱 기법’이라고 한다.

  • Paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용

    일반적인 메모리 참조에서도 캐시 메모리라는 것이 사용 되고 있다. CPU에서 메모리를 접근할 때, 메모리를 직접 접근하는게 아니라 CPU하고 메인 메모리 사이에 캐시 메모리라는 좀 더 빠른 계층을 두고 있다. 그래서, CPU가 메모리를 접근할 때 메인 메모리를 접근하기 전에 혹시 요청된 내용이 캐시 메모리에 있는지를 먼저 살펴보고 없는 경우에만 메인 메모리에 요청을 하는 것도 캐싱 기법의 하나의 예로 볼 수가 있다.

    버퍼 캐싱이라는 것은 파일 시스템에 대한 Read / Write 요청을 메모리에서 빠르게 서비스하는 방식이다. 그래서, 버퍼 캐싱하고 페이징 시스템은 매체는 동일하다. 빠른 공간이라는게 물리적인 메모리에 해당하고, 느린 곳이 디스크에 해당…페이징 시스템의 경우에는 디스크의 swap area에 해당하고, 버퍼 캐싱의 경우에는 디스크의 파일 시스템에 해당한다는 점은 다르지만 어쨋든 매체는 똑같다.

    그 다음에 웹 캐싱이라는 것도 있다. 이것은 뭐냐하면, 우리가 어떤 웹페이지를 볼 때 웹페이지에 대한 요청을 하면 멀리있는 웹 서버에서 그 페이지를 가져와야 한다. 가져온 다음에 내 웹 브라우저 화면에다가 표시(display)를 한다. 만약에 동일한 URL에 대해서 지금도 요청을 했고, 잠시 뒤에 또다시 요청을 한다고 하면 그걸 멀리있는 웹 서버에서 그 웹페이지를 다시 읽어오는 것은 시간이 오래 걸리기 때문에, 내 컴퓨터에 이미 읽어온 웹페이지를 저장해놨다가 화면에 보여주면 더 빠르다. 이것도 일종의 캐싱 기법 중에 하나다.

    근데, 앞에 있는 것들은 단일 시스템에서 저장 매체들간의 속도 차이가 나서 캐싱을 한 것이고, 웹 캐싱은 시스템이 다름… 멀리 있는 컴퓨터에서 읽어오는데 지리적으로 멀리 떨어져있기 때문에 읽어오는데 시간이 걸리는 것이다.
    그래서, 그거를 매번 읽어오는게 아니라 동일한 내용이 이미 읽혀져 있으면 그걸 내 컴퓨터에 저장된걸로 보여주는 이런 방식을 웹 캐싱이라고 부른다.

• 캐시 운영의 시간 제약

  캐시에서는 리플레이스먼트 알고리즘…어떤거를 쫓아낼지를 결정하는 그런 알고리즘에 있어서 시간 제약 조건이 있다.

  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음

    어떤걸 쫓아낼지를 결정하기 위해서 너무 많은 시간을 투자해선 안된다는 것이다. 캐시 안에 N개가 있는데 그 중에 이번에 어떤걸 쫓아낼지 결정하려고 N개를 한번 씩 쭉 스캔해보는 방식… 그거를 우리가 O(N)order of n의 시간 복잡도라고 하는데 그건 오버헤드가 너무 크다는 것이다.

  • Buffer caching이나 Web caching의 경우

    • O(1)에서 O(log n) 정도까지 허용

      그래서, 대부분의 캐싱 환경에서는 O(1) 내지는 O(log n) 정도까지가 허용할 수 있는 시간 범위에 해당한다. (앞에서 봤던 LRU, LFU 알고리즘도 이러한 시간 제약 조건을 만족하고 있다)

  • Paging system인 경우

    • page fault인 경우에만 OS가 관여함
    • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
    • O(1)인 LRU의 list 조작조차 불가능

    페이징 시스템에서는 더 엄청난 제약 조건이 있다

Paging System에서 LRU, LFU 가능한가?

과연 Paging System에서 LRU나, LFU 같은 알고리즘을 사용할 수 있는가?

CPU에서 프로세스 A가 지금 러닝중이다Process A is running. 만약, 프로세스 A가 CPU를 잡고 실행 중인 경우에 이 프로세스 A의 논리적인 메모리logical memory of Process A에서 매 순간마다 인스트럭션을 하나씩 읽어와서 실행을 할 것이다.

근데, CPU에서 이 프로세스 A에 대한 논리 주소logical address를 주는데, 이거를 페이지 테이블page table을 통해서 물리적인 메모리 주소로 변환해서(검은 화살표) 물리적인 메모리physical memory에 있는 내용을 CPU로 읽어들여야 될 것이다.

근데, 만약에 주소 변환을 했는데 해당하는 페이지가 이미 물리적인 메모리physical memory에 올라와 있다 그러면, 물리적인 메모리에서 직접 이 내용을 읽어서 CPU로 가져간다. (이 과정에서 운영체제는 하는 일이 없다고 했다. 이런 주소 변환은 하드웨어적으로 일어나는 일이고, CPU를 프로세스 A가 가지고 있으면서 주소 변환을 해서 메모리 참조를 해 가는 것이다.)

반면에, 프로세스 A가 CPU에서 러닝을 하면서 주소 변환 시도를 했는데, 만약 invalidi라서 이 요청한 페이지가 물리적인 메모리에 없고 backing store에 있다(이런 경우를 페이지 폴트라고 했음). 페이지 폴트가 발생하게 되면 디스크 접근을 필요로 하기 때문에(즉, I/O를 필요로 하기 때문에) 프로세스 A가 디스크에서 메모리로 읽어오는 이 작업을 할 수가 없다. 그래서 트랩이 발생한다. 페이지 폴트 트랩이 발생하면 이 CPU의 제어권이 프로세스 A로부터 운영체제로 넘어가게 된다. 그러면, 운영체제가 디스크에 있는 (페이지 폴트가 났던)페이지를 읽어서 물리적인 메모리로 올려놓게 된다. 그 과정에서 필요하면 이(물리적인 메모리에 있는 페이지) 중에 어느 하나를 쫓아내는 리플레이스먼트를 해야되는 것이다.

근데, 어떤걸 쫓아낼지를 운영체제가 쭉 살펴보는데 LRU 알고리즘을 쓴다면 가장 오래전에 참조된 페이지를 쫓아내야되는데, 과연 운영체제가 가장 오래전에 참조된 페이지를 알 수 있는가? 만약 LFU 알고리즘을 사용한다면 이 중에서 가장 참조 횟수가 적은 페이지를 쫓아내야되는데, 과연 운영체제는 이 중에 참조 횟수가 제일 적은 페이지를 알 수 있는가?

답은 알 수가 없다…!

왜냐하면, 이 프로세스가 사용하는…요청한 페이지가 이미 메모리에 올라와있는 경우에는 운영체제한테 CPU가 안넘어간다. 하드웨어적으로 그냥 주소 변환을 해가지고 CPU로 읽어들인다. 그러면, 이 친구의(물리적 메모리에 있는 페이지의) 접근 시간을 운영체제는 모르는 것이다. 반면에, 페이지 폴트가 나면(즉, CPU 제어권이 운영체제한테 넘어오면) 운영체제는 디스크에 있던 페이지가 메모리로 올라온 시간을 알 수 있다. 그래서 이 페이징 시스템에서는 운영체제한테 주어지는 정보가 반쪽만 주어지는 것이다. 메모리에 그 페이지가 이미 있으면 운영체제가 알 수 있는 정보가 없고, 메모리에 그 페이지가 없어서 페이지 폴트가 나면 CPU 제어권이 운영체제한테 넘어와서 그 페이지가 언제 메모리로 올라왔는지 이런 정보가 주어지는 것이다.

반면에, LRU나 LFU 알고리즘은 링크드 리스트(Linked List)로 조작을 해야된다. 어떤 페이지가 메모리에 들어오면 리스트의 제일 아래쪽에 매달아준다. 이것은 페이지 폴트가 난 상황에서는 운영체제가 할 수 있다. 그렇지만, 어떤 페이지가 이미 메모리에 있는데 그 페이지가 다시 참조가 된다 그러면, 운영체제한테 CPU가 안넘어온다. 그냥 그 프로세스가 직접 이 페이지를 접근해서 하드웨어적으로 주소 변환을 해가지고 CPU안으로 가져가버렸다. 그러면 운영체제가 이러한 자료구조를 유지하면서 이 페이지의 위치를 링크드 리스트를 끊어가지고, 맨 아래로 보내고 연결해주는 이런 작업을 할 수가 없는 것이다. 이 작업을 누가 해야되느냐?

운영체제가 해야된다. 그것도 CPU를 얻어가지고… 이러한 자료구조 연결하고 이런게 다 CPU를 가지고 인스트럭션 하나하나를 통해서 할 수 있는 일인데, 메모리에 이미 있는 페이지에 대해서는 운영체제한테 CPU가 넘어오지 않기 때문에 그래서, 운영체제는 어떤 페이지가 가장 최근에 참조됐는지, 어떤 페이지에 참조 횟수가 많은지, 이런 사실을 알 수가 없기 때문에 사실 LRU나 LFU 알고리즘을 페이징 시스템 즉, 가상 메모리(Virtual Memory) 시스템에서는 사용을 할 수가 없다.

LRU, LFU 알고리즘이 여기(가상 메모리)에 맞는 알고리즘들은 아니다. 대신에 LRU, LFU 같은 알고리즘이 버퍼 캐싱이나 웹 캐싱 같은데서는 사용이 될 수 있다.

운영체제한테 정보가 반쪽만 주어지는 것이다, 페이지가 이미 메모리에 존재하면 운영체제가 알 수 있는 정보가 없고, 페이지 폴트가 났을 때만 운영체제한테 CPU가 넘어오기 때문에 비로소

이런 자료구조의 조작이 가능해지는 것이다.

그럼 페이징 시스템에서는 과연 어떤걸 쫓아낼지를 결정하기 위해서 무슨 알고리즘을 써야되느냐? 그래서 사용하는 알고리즘이 바로 아래 소개되는 ‘클락 알고리즘’이라는 것이다.

Clock Algorithm

페이징 시스템에서는 쫓아낼 거를 결정하기 위해서 LRU나 LFU같은 것은 사용을 할 수가 없고, 클락 알고리즘이라는 걸 사용을 한다.

Clock == 시계, 왜 시계를 이 알고리즘 이름에 붙였나?

이렇게 시계처럼 동그랗게 그려놓고 시곗바늘이 이동하면서 알고리즘을 운영하는걸로 생각을 할 수 있기 때문에, 일반적으로 Clock algorithm(클락 알고리즘)이라고 부른다.

• Clock algorithm

  • LRU의 근사(approximation) 알고리즘

    이것은 LRU 알고리즘을 약간 근사시킨 알고리즘이기도 함

  • 여러 명칭으로 불림

    • Second chance algorithm

      기회를 한번 더 준다는 것이다. 알고리즘의 동작을 보면 왜 Second chance인지 알 수 있다.

    • NUR (Not Used Recently) 또는 NRU (Not Recently Used)

      LRU는 가장 오래전에 참조된 페이지를 쫓아낸다. 근데, 운영체제는 가장 오래전에 참조된 페이지가 어떤건지 모른다. 그래서, 가장 오래전에 참조된 걸 쫓아내는 대신에 최근에 사용되지 않은 페이지를 쫓아내는 방법을 쓰기 때문에 “Not Recently Used replacement algorithm” 이런식으로 부른다.

  • Reference bit을 사용해서 교체 대상 페이지 선정 (circular list)

  • reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동

  • 포인터 이동하는 중에 reference bit 1은 모두 0으로 바꿈

  • Reference bit이 0인 것을 찾으면 그 페이지를 교체

  • 한 바퀴 되돌아와서도(=second chance) 0이면 그때에는 replace 당함

  • 자주 사용되는 페이지라면 second chance가 올 때 1

• Clock algorithm의 개선

  • reference bit과 modified bit (dirty bit)을 함께 사용
  • reference bit = 1 : 최근에 참조된 페이지
  • modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)

그러면 이 알고리즘이 어떻게 동작하는지 그림을 통해서 설명

그림에 보이는 각각의 사각형이 페이지 프레임들이다. 즉, 물리적인 메모리 안에 들어있는 페이지들이고… 우리가 페이지에 대해서 어떤 페이지가 지금 참조가 돼서 CPU가 그 페이지를 사용하게 되면 그 페이지의 reference bit(레퍼런스 비트, 참조 비트)라는게 하나 붙어있다. 이 레퍼런스 비트는

주소 변환을 해주는 하드웨어가 어떤 페이지에 대한 접근을 해서 만약 그 페이지가 validv라서 그 페이지를 CPU로 읽어가야된다 그럼 그 페이지에 대한 레퍼런스 비트 라는걸 1로 셋팅을 해준다. 무슨 얘기냐하면, 그 페이지가 최근에(현재) 참조가 되면 그 페이지에 이 레퍼런스 비트 라는걸 1로 셋팅해서 페이지가 참조됐다는걸 표시를 해준다. 이거는 운영체제가 하는 일이 아니고, 하드웨어가 해주는 일이다.

즉, 이미 메모리에 존재하는 페이지에 대해서 그 페이지가 참조가 되면 페이지를 CPU를 읽어들이면서 레퍼런스 비트를 1로 셋팅을 해준다는 것이다.

그러면 만약 페이지 폴트가 나서 운영체제가 어떤 페이지를 쫓아내야겠다 그러면, 이 하드웨어가 셋팅해놓은 레퍼런스 비트를 참조하는 것이다.

그래서, 만약 레퍼런스 비트가 1이다 그러면, 이 페이지가 적어도 1번 참조가 됐구나…그런데, 레퍼런스 비트가 1이라는건 최근에 참조됐다는 걸 의미한다.

왜그러냐하면, 운영체제는 메모리 안에 있는 페이지에 대해서 어떤걸 쫓아낼지 결정하기 위해서 레퍼런스 비트가 1인 페이지는 0으로 바꾸고 그 다음 페이지를 본다. 그러니까, 레퍼런스 비트가 1인 페이지는 쫓아내지 않고, 비트가 1인 것을 0으로 바꾸고 그 다음거를 조사를 해보는 것이다. 그래서 만약 이 친구(왼쪽 3시 방향)도 레퍼런스 비트가 1이다 그러면, 0으로 바꾸고 그 다음 것(4시 방향)을 본다. 그래서 만약 레퍼런스 비트가 0이다. 그러면 이 친구(4시 방향)를 쫓아낸다.

이게 어떤식의 운영을 의미하느냐? 레퍼런스 비트가 1인 것을 운영체제가 시계바늘을 돌리면서 0으로 바꾸면서 지나가고 있다. 그래서, 이 레퍼런스 비트가 0이라는 이야기는 뭐냐하면 시계바늘이 1바퀴 돌아오는 동안에 이 페이지에 대한 참조가 없었다는 이야기다. 그리고, 레퍼런스 비트가 1이라는건 시계바늘이 1바퀴 돌아오는 동안에 적어도 1번의 참조는 있었다는 이야기다.

그래서 하드웨어가 이 페이지들을 참조할 때 레퍼런스 비트를 1로 만들어놓는 역할을 하고, 운영체제는 이 하드웨어가 셋팅한 비트를 보면서 어떤걸 쫓아낼지를 결정할 때 이 Circular Linked List(원형 연결 리스트)를 쭉 돌면서 레퍼런스 비트가 1인건 0으로 바꾸고, 0인거를 쫓아내는…그 알고리즘이 클락 알고리즘(Clock Algorithm)이라는 것이다.

그렇게 되면, 레퍼런스 비트가 0인걸 쫓아내니까 가장 오래전에 참조된 페이지를 쫓아내는건 아니다. 즉, LRU하고 정확하게 일치하는 운영을 하지는 못하지만 적어도 시계바늘이 1바퀴 돌아오는 동안에 참조가 안된 페이지를 쫓아내는 즉, 오랫동안 참조가 안된 페이지를 쫓아내기 때문에 어느정도 LRU하고 비슷한 효과를 낼 수는 있다는 것이다.

그리고 링크드 리스트나 이러한 거를 통해서 페이지의 위치를 이동시키고 이런거를 운영체제가 직접할 수 없기 때문에 하드웨어의 도움을 받는 것이다. 하드웨어는 그 페이지가 참조될 때마다 달랑 비트 하나를 셋팅해주는데(valid/invalid bit 말고, reference bit를 추가로 두고), 그 비트 하나 셋팅해주는걸 보고 운영체제는 그 비트를 주기적으로 클리어 시키면서 그 비트가 0인 것을 쫓아낸다는 것이다.

1바퀴 돌아올 동안에 레퍼런스 비트가 1로 되있으면 한번 더 기회를 주고, 0으로 바꾼 다음에 그냥 살려주는 것이고…그러면 시계바늘이 다시 1바퀴 돌아가는데 0이다 그러면 쫓겨나는거고, 다시 1이라는 것은 그 1바퀴 돌아올 동안에 또 참조가 있었다는 거니까 쫓아내지를 않고… 이런식으로 운영하는게 클락 알고리즘이고…

이거는 가상 메모리(Virtual Memory)…페이징 시스템에서 일반적으로 사용하는 알고리즘이라는 것이다.

사실은 reference bit(레퍼런스 비트) 말고, modified bit라는걸 하나 더 두고 있다. 다른말로 dirty bit라고도 하는데, 이건 뭐냐하면, 어떤 메모리 페이지가 참조되는건 read로 참조가 될 수도 있지만 write로 참조가 될 수도 있는 것이다. 어떤 페이지가 메모리에서 write가 발생하면, modified bit을 하드웨어가 1로 셋팅을 해놓는다.

이거는 어디다 사용을 하느냐?

어떤 페이지(위 그림 빨간색으로 표시)가 쫓겨날 때 즉 레퍼런스 비트가 0이라서 이 페이지(위 그림 빨간색으로 표시)는 쫓아내야된다. 근데 만약에 이 페이지의 modified bit가 0이다 그러면,

이 페이지는 backing store에서 물리적인 메모리로 올라온 이후로 write가 발생 안한 것이다(modified bit가 0이면). 그래서 그런 페이지가 쫓겨날 때는 그냥 메모리에서 쫓아내기만 하면 되는 것이다. 이미 동일한 카피가 backing store에 존재하기 때문에 그런 것이다.

반면에, 어떤 페이지를 쫓아내야되는데 modified bit이 1이다 그러면, 그 페이지는 메모리에 올라온 이후로 적어도 1번은 CPU에서 write를 한거다 즉, 내용을 수정한 페이지다. 그래서 그런 페이지가 메모리에서 쫓겨날 때는 그냥 지워버리면 되는게 아니라 backing store에 수정된 내용을 반영을 한 다음에 지워버려야 된다. 그래서, modified bit라는걸 같이 두는 것이다.

그러면, 이 클락 알고리즘은 약간 더 변형할 수가 있을 것이다. 어떻게 변형하느냐 하면…

modified bit가 1인걸 쫓아내려면 디스크에다가 써주고 쫓아내야되기 때문에, 일이 더 많다. 그래서, 가능하면 modified bit가 1인거는 쫓아내지 않고, modified bit가 0인걸 우선해서 쫓아낸다면 디스크에 쫓겨나는 페이지를 써줄 필요가 없기 때문에 조금 더 빠를 수가 있겠다는 말이다.

그래서, 이 2가지 비트(reference bit, modified bit)를 같이 이용해서 클락 알고리즘을 더 개선하는 그런 방식도 사용을 할 수가 있다.

Page Frame의 Allocation(할당)

• Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?

• Allocation의 필요성
  • 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
    • 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
  • Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
    • 최소한의 allocation이 없으면 매 loop마다 page fault
• Allocation Scheme

  • Equal allocation: 모든 프로세스에 똑같은 갯수 할당

  • Proportional allocation: 프로세스 크기에 비례하여 할당

  • Priority allocation: 프로세스의 priority에 따라 다르게 할당

    CPU 우선순위가 높은 프로세스한테 페이지를 더 많이 할당해주는 방법

지금까지 LRU 알고리즘이나 LFU 알고리즘 또는 클락 알고리즘에서는 프로그램 여러개가 물리적인 메모리에 같이 올라가 있다.

A라는 프로그램 외에 B, C 라는 여러 프로그램의 페이지들도 같이 올라와 있을텐데 우리가 쫓아낼 때는 어떤 프로세스에 속한 페이지인지 무관하게 그냥 가장 오래된 페이지를 쫓아낸다거나 이런식으로 운영을 해왔다.

근데, 실제로는 어떤 프로그램이 원활하게 실행이 되기 위해서는(이 프로그램이 CPU에서 실행이 되면서 페이지 폴트를 잘 안내고 원활하게 실행이 되려면) 일련의 페이지들이 메모리에 같이 올라와있어야지만 더 효율적이 되는 것이다.

예를 들면, 인스트럭션을 실행하는데 있어서 for문 같은걸 반복하고 있다 그러면 그 for문을 구성하는 페이지가 예를 들어 3개다 그러면, 이 프로그램한테 3개의 페이지를 주면 for문을 반복하는 동안에 페이지 폴트가 안날 것이다. 또 예를 들면 for문을 100만번 돌고 있다.. 근데 이 프로그램한테 페이지 3개를 주면은 100만번 반복하는 동안에 페이지 폴트가 안나는 것이다. 그런데, for문을 구성하는 페이지가 3개인데 이 프로그램한테 페이지를 2개만 줬다 그럼, 100만번 반복하는 동안에 계속 페이지 폴트가 난다.

즉, 프로그램마다 어느정도 몇개의 페이지는 줘야지만 페이지 폴트가 잘 안나는 그런 일련의 페이지 갯수가 존재한다는 것이다. 또 프로그램이 실행하면서 인스트럭션만 실행하는게 아니라 필요에 따라서는 데이터를 접근하는 경우도 있다(메모리에서 어떤 데이터를 읽어와라). 그러면 최소한 코드에 해당하는 페이지 말고, 데이터에 해당하는 페이지도 메모리에 같이 올라와있어야지만 페이지 폴트가 덜 난다는 것이다.

그런데, 이러한 프로그램별로 페이지 얼로케이션을 해주지 않으면, 메모리에서 특정 프로그램이 페이지 프레임들을 완전히 다 장악해버리는 그런 일도 일어날 수가 있다. 어떤 프로그램이 계속 서로 다른 페이지들을 막 요청하게되면 다른 프로그램의 페이지들을 다 쫓아내고, 다 밀어내고 본인의 페이지만 메모리에 올려놓는 일이 발생할 수 있기 때문에 그렇게 되면 비효율적이라는 것이다.

그래서, 얼로케이션이라는 것은 각각의 프로그램한테 어느정도의 메모리 페이지를 나누어 주자는 것이다.

방법은 아래와 같다.

그런데 이러한 할당을 해주지 않더라도 우리가 LRU나 LFU같은 리플레이스먼트 알고리즘을 사용하다보면 알아서 어느정도씩 할당이 되는 효과가 있을 수가 있다.

어떤 프로그램이 메모리를 많이 필요로 하면, 그 프로그램의 메모리가 그 순간에는 많이 메모리에 올라오게 되고 그러면 상대적으로 다른 프로그램이 가지고 있던 페이지들이 쫓겨날 것이다. 그랬다가 또 다른 프로그램이 메모리가 많이 필요한 순간이 되면 또 다른 프로그램의 메모리 페이지들도 쫓아내고… 이런식으로 굳이 미리 할당을 하지 않고…

Global vs.Local Replacement

• Global replacement

  • Replace시 다른 process에 할당된 frame을 빼앗아 올 수 있다

  • Process별 할당량을 조절하는 또 다른 방법임

    Global Replacement 즉, 알아서 이런 알고리즘을 사용하면 그때그때 그 프로세스별로 메모리 할당량이 자동으로 조절이 되기 때문에 굳이 미리 할당하는 방법을 쓰지 않겠다는 얘기다.

  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당

    근데, LRU나 LFU같은 방법은 어느정도 그 프로그램한테 페이지를 할당하는 효과는 없다.

  • Working set, PFF 알고리즘 사용

    근데, 조금있다가 소개할 워킹셋이나, PFF 알고리즘 같은 경우에는 프로그램이 최소한 필요로 하는 그러한 페이지들을 동시에 메모리에 올려놓는 할당의 효과가 있는 그런 알고리즘들이라는 것이다.

    그래서 이와같이 할당을 하지 않고, 리플레이스먼트 알고리즘이 알아서 그때그때 할당 효과를 낼 수 있는 방법이 있고,

• Local replacement

  • 자신에게 할당된 frame 내에서만 replacement

  • FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시

    만약에 앞에 주어진 방법처럼 (아래 이미지 참고)

    

    프로그램들한테 미리 메모리 할당을 한다면, 각각의 프로그램들한테 메모리가 주어졌다 그러면, 그 프로그램 내에서 자신한테 할당된 메모리에 대해서 새로운 페이지가 필요하면 뭔가를 쫓아내고, 그 위에다가 새로운걸 올려놓고 그런 방법이 필요할 것이다.

즉, 글로벌 리플레이스먼트 방법은 다른 프로그램의 페이지도 쫓아낼 수 있는 방법이고,

로컬 리플레이스먼트 방법은 프로그램한테 할당을 해놓은 다음에 어떤 새로운 페이지로 올려놓기 위해서 쫓아내야될 때는 자신한테 할당된 페이지를 쫓아내는 방법이다.
그런데, 자신한테 할당된 페이지라 하더라도 어떤걸 쫓아낼지 결정을 해야되고, 그러면 가장 오래된 페이지를 쫓아낸다던지 하는 이런… 여기서도 여전히 LRU, LFU 같은 알고리즘을 사용할 수 있다는 것이다.

Thrashing

아까 어떤 프로그램한테 어느정도의 최소 메모리도 할당이 안됐을 때는 페이지 폴트가 자주 난다고 했다. 그래서 프로그램한테 메모리가 너무 적게 할당이 되가지고 페이지 폴트가 지나치게 자주 일어나는.. 전체 시스템에서 페이지 폴트가 아주 빈번히 일어나는 이런 상황을 Thrashing(쓰레싱) 이라고 부른다.

• Thrashing
  • 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
  • Page fault rate이 매우 높아짐
  • CPU utilization이 낮아짐
  • OS는 MPD (Multiprogramming degree)를 높여야 한다고 판단
  • 또 다른 프로세스가 시스템에 추가됨 (higher MPD)
  • 프로세스 당 할당된 frame의 수가 더욱 감소
  • 프로세스는 page의 swap in / swap out으로 매우 바쁨
  • 대부분의 시간에 CPU는 한가함
  • low throughput

쓰레싱이 어떻게해서 발생하는지를 여기서 소개하고 있다.
그림으로도 살펴보자.

Thrashing Diagram

이 그림에서 x축은 지금 메모리에 올라와있는 프로그램의 갯수이다degree of multiprogramming. 메모리에 동시에 올라가있는 프로그램이 늘어남에 따라서 CPU 이용률은 어떻게 되는가?

처음에 프로그램 하나만 메모리에 올라가있으면 CPU utilization이 대단히 낮다. 왜그러냐면, 이 친구가 메모리만 쓰는게 아니라 메모리를 쓰다가 I/O를 하러간다. 그러면 CPU는 놀아야된다. 지금 메모리에 프로그램 하나만 올라와있으니까 이 친구가 I/O를 하러가는 순간 CPU에게는 휴식시간이기 때문에 그래서, CPU utilization이 낮을 것이다.

메모리에 프로그램을 2개를 올렸다 그러면, 프로그램 하나가 I/O를 하러 갔을 때 또다른 프로그램이 CPU를 계속해서 쓸 수가 있다. 그러니까 CPU가 놀지 않고, 일하는 시간이 더 늘어날 것이다.

메모리에다가 프로그램을 2개, 3개, 4개, 8개, 10개 올려봤다. 그러면 계속 CPU utilization이 올라간다. 왜냐하면, 10개의 프로그램 중에서 9개가 I/O를 하러가더라도 레디 큐에 있는 당장 CPU만 주면 실행이 가능한 그 프로그램이 CPU를 쓰면 되기 때문에, 그래서 일반적으로 degree of multiprogramming를 올려주면 CPU utilization이 올라간다.

그런데, 계속해서 degree of multiprogramming를 올려주게 되면, 어느 지점에 이른 다음에 CPU utilization이 뚝 떨어진다. 이게 어떤 경우냐하면 바로 쓰레싱(Thrashing)이 발생한 순간이 되는 것이다.

이 쓰레싱이 왜 발생했느냐?

프로세스한테 이 페이지가 너무 적게 할당되면, 페이지 폴트가 빈번이 발생한다고 그랬다. 페이지 폴트가 빈번히 발생하다보면 CPU utilization이 낮아진다. 왜냐하면, 한번 CPU가 인스트럭션 실행하려고 하면 그 페이지가 메모리에 없다. I/O를 해야된다.

또 다른 프로그램한테 CPU가 넘어가서 이 친구가 뭔가 CPU를 쓰려고 했는데, 그 요청한 페이지가 또 메모리에 없다. 페이지 폴트가 나니까 그러니까 또 I/O를 하러 가야하고…

이런식으로 각 프로그램마다 메모리에 할당된 양이 너무 적어지게 되면…

그게, degree of multiprogramming이 너무 올라가서 생기는 현상이다. 메모리에 너무 많은 프로그램이 동시에 올라간다는 얘기는 각 프로그램이 가지고 있는 메모리 용량이 대단히 작다는 것이다. 그런 상황에서는 페이지 폴트가 빈번히 발생하게 되는 것이다.

그러면 CPU utilization은 낮아진다. CPU가 할일이 없는 것이다. 어떤 프로그램이 CPU를 잡더라도 페이지 폴트가 난다.

근데, 운영체제는 CPU utilization이 낮으니까 CPU가 놀고있다고 생각하고 프로그램을 더 메모리에 올려야겠다고 판단한다. 그러면, 또다른 프로그램이 메모리에 올라가고 그러면 Multiprogramming degree가 더 높아진다.

그러면 각 프로세스가 가지고 있는 메모리 용량이 더 적어질 것이다. 그러면 페이지 폴트는 더 자주 발생하고…

이 상황이 쓰레싱인데, 이 상황에서는 어떤 프로세스가 CPU를 잡더라도 거의 무조건 페이지 폴트가 발생하고, 그러면 메모리에서 페이지를 쫓아내고, 다시 새로운 페이지를 메모리에 올리고… 이 작업 하느라고 시간이 다 가고 실제로 CPU는 할 일이 없어서 한가한 상황이 된다는 것이다.

그게 바로 이런 상황이라는 것이다. 그래서 메모리에 너무 작은 페이지를 가지고 있게 되면… 즉, Multiprogramming degree가 너무 높아지게 되면 CPU utilization이 뚝 떨어져서 시스템이 굉장히 비효율적으로 되는 이런 상황이 발생할 수가 있다.

이걸 막기 위해서는 Multiprogramming degree를 조절해줘야된다. 동시에 메모리에 올라가있는 프로세스의 갯수를 조절해줘야되는 것이다. 그렇게 함으로써, 프로그램이 적어도 어느정도는 메모리 확보를 할 수 있게 해줘야한다.

그거를 해주는 알고리즘이 바로 Working set 알고리즘, PFF(Page-Fault Frequency) 알고리즘이라는 것이다.

Working-Set Model

• Locality of reference

  적어도 프로그램들이 메모리에서 원활하게 실행이 되려면 어느정도의 메모리 페이지는 가지고 있어야 되겠다는 것이고,
  또 한가지 추가된 설명이 뭐냐면 프로그램이 일정 시간.. 특정 시간에는 특정 메모리 위치만 집중적으로 참조하는 특징을 가지고 있다는 것이다. 그거를 reference의 Locality라고 부른다.

  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다

    예를 들면, 아까 말했듯이 어떤 for 반복문이 실행되고 있다 그러면, 그 루프가 실행되는 동안에는 그 루프를 구성하는 페이지만 집중적으로 참조가 된다. 다른 페이지는 참조가 안된다.

    또, 프로그램이 실행 되면 함수 구조로 되있다. 어떤 함수가 실행이 되고 있다 그러면 그 함수를 구성하는 페이지만 집중적으로 참조가 되고, 시간이 흘러서 그 함수가 리턴되서 다른 함수가 실행되고 있다 그러면, Locality of reference에서 집중적으로 참조되는 페이지들이 다른 함수를 구성하는 페이지로 바뀌는 것이다.

  • 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함

    그래서, 이런식으로 특정시간에 집중적으로 참조되는 page들의 집합을 locality set이라 부르고, 특별히 워킹셋 알고리즘에서는 그러한 셋을 Working-set이라고 부른다.

• Working-set Model

  어떤 프로그램이 실행되면서 그 순간에 메모리에 꼭 올라와있어야만 하는 즉, 빈번히 참조되는 그런 페이지들의 집합을 우리가 Working set이라고 부른다는 것이다.

  • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 정의함
  • Working Set 모델에서는 process의 working set 전체가 메모리에 올라와있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out (suspend)
  • Thrashing을 방지함
  • Multiprogramming degree를 결정함

그래서 워킹셋은 적어도 메모리에 한꺼번에 올라와 있도록 보장해주는 기법이 있어야지만 페이지 폴트가 잘 안난다는 것이다.

근데 아까 봤던 것처럼,

멀티 프로그래밍 디그리가 너무 높아지면 즉, 메모리에 너무 많은 프로그램이 올라가 있으면 워킹셋을 메모리에 보장할 수 없는 사태가 발생한다.

이 프로그램의 워킹셋은 페이지 5개로 구성되는데, 이 프로그램한테 페이지를 3개밖에 줄 수가 없다면… 그럴 때는 어떻게 하느냐? 구차하게 그 프로그램이 페이지 3개를 받는게 아니라, 모든 페이지를 통째로 반납하는 것이다. 나는 3개 필요없다. 5개 줄 때까지 하나도 안받겠다는 것이다.
그래서, 전체를 다 반납하고 그 프로세스가 디스크로 swap out된다는 것이다. 완전히 메모리를 잃은 상태라는 것이다. 그렇게 되면 이 프로세스의 상태는 Suspended 상태가 되는 것이다.

그래서, 이 워킹셋 모델은 이런식으로 Multiprogramming degree를 조절해서 즉, 워킹셋이 한꺼번에 메모리에 올라가는게 보장이 안된다 그러면, 그 프로세스의 메모리를 통째로 빼앗는 이런 방법을 통해서 쓰레싱을 방지하고, 또 멀티 프로그래밍 디그리를 조절하는 것이다.

그래서 워킹셋 알고리즘에 대해서 설명을 할텐데

Working-Set Algorithm

이 알고리즘은 어떻게 동작을 하느냐?

• Working set window를 통해 알아냄

  워킹셋은 미리 알 수가 없다. 정확하게 모르기 때문에 여기서도 과거를 통해서 워킹셋을 추정하는 것이다.

• window size가 Δ델타인 경우

  • 시각 t_i 에서의 working set WS (t_i)
    • Time interval [t_i - Δ, t_i] 사이에 참조된 서로 다른 페이지들의 집합
  • Working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림
    (즉, 참조된 후 Δ 시간 동안 해당 page를 메모리에 유지한 후 버림)

  그래서, 이 프로그램이 과거 Δ델타 시간동안 참조된 페이지들을 워킹셋이라고 간주해서 이 알고리즘은 과거 델타 시간동안 참조된 페이지들은 메모리에서 쫓아내지 않고, 유지를 하는 것이다.

  이 델타시간을 우리가 윈도우라고 부른다. 창문을 하나 뚫어놓는 것이다.

만약에 여기가(수직 화살표 t₁) 현재 시점이다. 그러면, 윈도우 사이즈 만큼… 이 알고리즘에서는 지금 윈도우 사이즈를 10으로 해놓은 것이다. 10으로 해놓으면 현재 시점부터 과거 10번째 참조된 페이지까지는 이 프로그램의 워킹셋이기 때문에 메모리에다가 올려놔야 된다는 것이다.
그래서, 과거 10개의 참조에 들어있는 페이지들을 봤더니 동일한 페이지가 반복 참조된 경우도 있기 때문에 서로 다른 페이지들을 나열해보면 {1,2,5,6,7} 이렇게 5개 페이지가 현재 시점에서 이 프로그램의 워킹셋이기 때문에, 워킹셋 알고리즘은 이 프로그램한테 5개의 페이지 프레임을 줄 수 있으면 {1,2,5,6,7}을 메모리에 올려놓고, 만약에 메모리 공간이 부족해서 5개 못주겠다 그러면, 구차하게 1~2개만 올려놓는게 아니라 전부다 디스크로 swap out 시키고, 이 프로그램은 suspended상태로 바뀐다는 것이다.

근데, 이 워킹셋의 크기가 그때그때 바뀐다(윈도우… 사각형의 틀을 만든다음에 이동을 시켜보자. 이동을 시켜보면). 이(t₂) 시점에서의 윈도우는 과거 10번째 참조 3부터다… 여기서부터 쭉 윈도우 내에 있는 페이지를 보면, 여기는 3하고 4 밖에 없다. 그래서, 이 순간에 워킹셋은 {3,4} 2개 라는 것이다. 그래서 이(t₂) 시점에는 이 프로그램한테 {3,4} 2개의 페이지만 할당해주면, 워킹셋을 만족한다는 것이다.

그래서, 현재부터 과거 윈도우 크기 Δ델타 이내에 들어오는 페이지들을 워킹셋으로 간주해서 그 페이지들은 메모리에 유지를 시킨다는게 워킹셋 알고리즘의 동작 방법이고, 이것을 다른말로 표현하면 참조된 페이지를 Δ델타 시간 동안만 유지하고 버리는 것하고 똑같다.

여기서 2번 페이지가 참조가 되면 이 페이지를 10이라는 시간 동안만 유지한 다음에 버리고, 또 6이라는 페이지가 참조되면 6에서부터 10번의 참조까지만 유지하고 버리고… 이게 워킹셋 알고리즘이라는 것이다.
근데, 버리려고 했는데 다시 참조가 되면 버리지 않고, 그 시점부터 또 10번의 시간 유예가 되는 것이다. 그게 이제 과거 윈도우 10만큼 유지하는거랑 똑같은 얘기다.

그래서, 워킹셋 알고리즘은 이런 방식으로 워킹셋을 유지하고,

• Working-Set Algorithm
  • Process들의 working set size의 합이 page frame의 수보다 큰 경우
    • 일부 process를 swap out시켜 남은 process의 working set을 우선적으로 충족시켜 준다 (MPD를 줄임)
  • Working set을 다 할당하고도 page frame이 남는 경우
    • swap out 되었던 프로세스에게 working set을 할당 (MPD를 키움)

워킹셋이 전부 보장이 안될 때는 그 프로그램을 swap out시켜서 적어도 메모리에 남아있는 프로그램이라도 워킹셋을 보장받게 해주는 것이고,
나중에 메모리에 여유가 생겨서 워킹셋이 전부 다 보장될 때 이 프로그램의 메모리에 올려놓게 된다는 것이다.

이런식으로, 워킹셋 알고리즘은 Multiprogramming degree를 조절하면서 워킹셋을 메모리에 보장하게 된다는 것이다.

• Window size Δ델타
  • Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
  • Δ 값이 너무 작으면 locality set을 모두 수용하지 못할 우려
  • Δ 값이 크면 여러 규모의 locality set 수용
  • Δ 값이 ∞이면 전체 프로그램을 구성하는 page를 working set으로 간주

PFF (Page-Fault Frequency) Scheme

이 방식은 워킹셋 알고리즘처럼 워킹셋을 추정하는 방식이 아니라, 직접 페이지 폴트 비율page-fault rate을 보는 것이다. 현재 시점에 이 시스템에서 페이지 폴트가 얼마나 나는지를 보고 또 특정 프로그램이 페이지 폴트를 얼마나 내는지를 본다.

그래서, 만약에 그 프로그램이 페이지 폴트를 많이 내고 있다면 이 친구의 워킹셋은 메모리에 다 보장이 안되있는 상태구나 그래서 페이지 폴트를 많이 일으키는 프로그램은 페이지를 더 주는 것이다.

• page-fault rate의 상한값과 하한값을 둔다
  • Page fault rate이 상한값을 넘으면 frame을 더 할당한다
  • Page fault rate이 하한값 이하이면 할당 frame 수를 줄인다
• 빈 frame이 없으면 일부 프로세스를 swap out

보통 일반적으로 프로그램한테 할당되는 메모리 크기가 커지게 되면, 페이지 폴트 발생하는 비율은 줄어든다. (프로그램마다 위 곡선의 가파른 정도가 다를 것이다) 어쨋든, 어떤 프로그램의 페이지 폴트 비율이 일정 수준 이상으로 발생하고 있다 그러면 페이지 폴트가 너무 빈번하다는 것…그래서 그런 상황에서는 워킹셋 보장이 안된 상황으로 봐서 이 프로그램한테 페이지 수를 더 늘려주는 것이다.
그러면 페이지 폴트 비율이 줄어들어서 어느정도 이내로 들어올 것이다.

반대로 어떤 프로그램은 지금 페이지 폴트가 너무 발생 안한다 그럼 이러한 프로그램은 지금 쓸데없이 메모리를 너무 많이 가지고 있는 것이라고 생각해서 그런 프로그램으로부터는, 메모리를 좀 빼앗아서 일정수준의 페이지 폴트를 유지하게 하는… 이런게 PFF (Page-Fault Frequency) Scheme 이라는 것이다.

여기서도 만약에 페이지 폴트 비율이 빈번한데 메모리를 더 줘야겠는데 더 줄 메모리가 없는 상황이라면 그 프로그램을 통째로 swap out 시켜서 메모리에 남아있는 프로그램이라도 페이지 폴트 비율이 일정 수준 이하로 떨어지도록 유지를 시킴으로써 쓰레싱을 방지한다.

Page Size의 결정

페이지 사이즈는 어떻게 결정되어야되는지 설명

• Page size를 감소시키면
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • Internal fragmentation 감소
  • Disk transfer의 효율성 감소
    • Seek/rotation vs. transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality의 활용 측면에서는 좋지 않음
• Trend
  • Larger page size

페이징 시스템에서는 동일한 크기의 페이지 단위로 물리적인 메모리의 프레임을 자르고 또, 가상 메모리의 프로그램을 구성하는 페이지들 주소 공간도 페이지로 자르게 되는데, 페이지 사이즈를 보통 4KB를 쓰고 있다. 근데, 메모리 주소 체계가 32비트 주소 체계에서 64비트 주소 체계로 바뀌고, 메모리 크기도 점점 커지기 때문에 페이지 사이즈가 너무 작으면 페이지 테이블이 너무 커져야 한다. 그러면 페이지 테이블이 결국 낭비기 때문에 그래서, 메모리 크기가 커지면 페이지 사이즈도 거기에 따라서 키워줄 필요가 생기는 것이다.

그래서, 최근에는 큰 크기의 페이지를 쓰는 (4KB가 아니라 더 큰)… 대용량 페이지를 사용하는 그런 메모리 시스템에 대한 얘기도 나오고 있다. 그래서, 페이지 사이즈에 따른 파급효과들을 여기서 소개하고 있다.

만약에 페이지 사이즈를 줄이게 되면, 똑같은 크기의 메모리에서 더 잘게 썰어야되는거기 때문에 페이지 갯수가 증가를 하고, 그러면 페이지 테이블 엔트리 수가 더 많이 필요하니까 페이지 테이블을 위한 메모리 낭비가 더 심해질 것이다. 대신에, 페이지 안에서 사용이 안되는 부분이 있을 수가 있는데, 그 부분이 더 줄어들 것이다. 좀 더 잘게 써니까 약간 더 효율적인 부분도 생기긴 할 것이다. 특히, 꼭 필요한 정보만 메모리에 올라오기 때문에 메모리 이용이 더 효율적일 수가 있다.
페이지 크기가 크면 페이지 안에서 아주 작은 부분만 필요하더라도 페이지 폴트가 났을 때 그 큰 페이지를 통째로 메모리에 올려야되기 때문에, 그래서 꼭 필요한 정보만 메모리에 올라오지는 않을 수가 있다는 얘기다. 반대로, Locality(지역성)의 활용 측면에서는 페이지 크기가 큰게 더 좋다. 왜냐하면, 대개 프로그램이라는게 Locality(지역성) 라는게 있다고 했고, 어떤 함수가 실행이 되면, 그 함수를 구성하는 코드들이 연달아서 순차적으로 참조가 되기 때문에 페이지 폴트가 났을 때 페이지 하나를 통째로 올려놓으면 처음에는 페이지 폴트가 났지만, 그 안에 있는 아래쪽에 있는 메모리 위치들은 메모리에 올라온 이후로 페이지 폴트를 내지 않고 참조하기 때문에 그래서 더 효율적인 측면도 있다는 것이다.
또한, Disk transfer의 효율성이 페이지 크기가 클수록 더 좋아지는데, 그게 무슨 얘기냐하면 디스크라는건 기본적으로 Seek를 해야한다. 디스크 원판이 회전을 하면서 디스크 헤드가 이동을 해서 특정 위치에 가서 그 섹터를 읽거나 써야되는데, 사실은 Seek하는 시간이 대단히 오래걸린다. 그래서, 가능하면 한번 디스크 헤드가 이동해서 많은 양의 뭉치를 읽어서 메모리에 올리는게 좋다는 것이다. 그래서 페이지가 큰게 좋은거지, 페이지가 너무 작으면 그때그때마다 페이지 폴트가 나고, 그때그때마다 디스크 헤드가 이동을 해야되는 Seek시간이 길어져서 비효율적이 될 수가 있다는 것이다.

그래서, 최근에는 페이지 크기를 점점 키워주고 있는 추세이다.

맨 위로 이동하기