운영체제 교착상태 및 메모리 관리

Chpter 07 Deadlock (교착상태)

• 시스템은 경쟁하는 프로세스들 사이에 분산되어 있는 유한한 수의 자원들로 구성된다

  • CPU주기, 메모리 공간, 파일, 입출력 장치 등

---

- 정상적인 작동 모드 하에서, 프로세스는 다음순서로 자원을 이용해야 한다.

1. 요청 
    * 프로세스는 자원을 요청해야 한다. 요청이 즉시 허용되지 않으면 자원을 얻을 때까지 대기 
2. 사용 
    * 프로세스는 자원에 대한 작업을 실행할 수 있다. 
3. 방출 
    * 프로세스가 자원을 방출(반납)한다. 

---

교착상태

• 운영체제 혹은 소프트웨어의 잘못된 자원 관리로 인하여 둘 이상의 프로그램이 함께 멈추어 버리는 현상을 말한다.

• 교착상태에 빠진 프로세스들은 결코 실행을 끝낼 수 없으며, 시스템 자원이 묶여 있어 다른 작업을 시작하는 것도 불가능하다.

• 식사하는 철학자 문제를 확인해 보는 것도 좋다.

필요조건

• 상호배제 (mutual conditions)

  • 한번에 한 프로세스마 자원을 사용할 수 있다.

  • 다른 프로세스가 그 자원을 요청하면, 요청 프로세스는 자원이 방출될 때까지 반드시 지연되어야 한다.

• 정유하면서 대기 (hold-and-wait)

  • 프로세스는 최소한 하나의 자원을 점유하고, 현재 다른 프로세스에 의하여 점유된 자원을 추가도 얻기 위해 반드시 대기하고 있어야 한다.

• 비선점 (no preemption)

  • 자원들은 선점할 수 없어야 한다. 즉 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 task를 종료한 후 그 프로세스에의해 자발적으로만 방출될 수 있다.

• 순환대기

  

  • P0, P1, P2순으로 프로세스의 집합이 존재해야 한다. 즉 P1은 P0의 자원을 기다리고, P2는 P1의 자원 해제를 기다리고 있어야 한다.

교착상태 처리 방법 (Method for Handling Deadlock)

1. 시스템이 교착상태가 되지 않도록 보장

   • 교착상태 예방 기법

   • 교착상태 회피 기법

2. 시스템이 교착상채가 될 수 있도록 허용하되 회복시키는 방법

   • 교착상태 탐지 알고리즘 && 교착상채 회복 알고리즘

3. 교착상태 문제를 무시하고 교착상태가 발생하지 않는다고 가정

   • 문제를 무시하고, 교착상태가 시스템에서 결코 발생하지 않은 척한다.

   • 성능저하 -> 시스템 중단 -> 인위적인 재시작

   • 유닉스와 윈도우를 포함한 대부분의 OS에서 사용하고 있는 방법

교착상태 예방 기법

• 상호배제 부정

  • 자원이 공유 가능하면 배타적인 접근을 요구하지 않으므로 교착상태가 발생하지 않는다.

  • 하지만 공유가 불가능한 자원에 대해서는 반드시 성립되어야 한다.

  • 일반적으로 상호배제 조건을 인정하지 않고 교착상태를 예방하는 것은 불가능 하다.

• 점유하며서 대기 부정

  • 프로세스가 자원을 요청할 때마다 다른자원들을 점유하지 않도록 보장한다.

  • 프로세스가 실행되기 전에 각 프로세스가 요청하는 모든 자원들을 함께 할당

  • 프로세스가 자원을 전혀 가지고 있지 않을 떄만 자원을 요청할 수 있도록 허용한다.

    • 단, 프로세스가 자원을 더 요청하려면 자신에게 할당된 모든 자원을 반납해야 한다.

  • 많은 자원들이 할당된 후 오랜시간 동안 사용하지 않을 수 있기 때문에 자원의 이용률이 낮다.

  • 인기 자원들이 필요한 프로세스가 최소한 하나가 항상 다른 프로세스에게 할당되어 무한정 대기하는 기아상태가 나타날 수 있다.

• 비선점 부정

  • 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

  • 처리비용 증가 (기존작업 무효, 요청 반납이 무한정 반복될 수 있다)

  • CPU레지스터나 메모리 공간처럼 그 상태가 쉽게 저장되고 후에 복원될 수 있는 자원에 적용된다.

  • 일반적으로 프린터나 테이프 드라이브등 적용될 수 없는 자원도 존재한다.

• 순환대기 부정

  • 모든 자원들에게 순서를 부여하고 각 프로세스가 열거된 상태에서 오른차순으로 자원을 요청한다.

    • 큰 번호로만 자원을 요구하도록 한다.

  • 프로그램을 작성하기가 어렵고 자원이 낭비될 수 있다.

교착상태 회피 기법

• 안전상태

  • 시스탬 상태가 안전하다는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원(최대 요구 개수까지)을 교착상태를 야기시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다.

  • 시스템이 안전 순서를 찾을 수 있다면 시스템은 안전하다.

  

• 자원할당 그래프

  • 만약 각 자원 타입마다 단지 하나의 인스턴스를 갖는 자원 할당 시스템을 갖고 있다면, 우리는 교착상태 회피를 위해 사용할 수 있다.

  • 우리의 시스템은 자원이 반드시 미리 예약되어야 함을 유의해야 한다.

  • 사이클이 없다면 자원을 할당해도 시스템은 안정상태가 된다.

  • 사이클이 발견되면 시스템을 불안전 상태로 만들 것이다. 그러므로 프로세스는 자인의 요청이 충족될 때까지 반드시 대기해야 한다.

은행원 알고리즘

• PPT문제 풀이 요망

교착상태 탐지 알고리즘

• 각 자원 타입이 한 개씩 있는 경우

• 모든 자원들이 한 개의 인스턴스만 있다면, 대기 그래프라고 하는 자원 할당 그래프의 변형을 사용해 교착상태 탐지 알고리즘을 정의할 수 있다.

• 대기 그래프가 사이클을 포함하는 경우에만 시스템에 교착상태가 발생함하기 때문에 교착상태를 탐지하기 위해 시스템은 대기 그래프를 유지할 필요가 있고, 주기적으로 사이클을 탐지하는 알고리즘을 호출한다.

• O(n^2)의 연산을 요구한다.

• 각 타입의 자원을 여러개 가진 경우

  • PPT 문제 풀이 요망 (은행원 알고리즘 변형)

• 탐지 알고리즘의 사용

  • 교착상태가 자주 발생하며 탐지 알고리즘도 자주 호출되어야 한다.

  • 할당 요청을 허용할 수 없을 때마다 교착상태 탐지를 호출하면 연산 시간 부담이 커지게 된다.

  • 따라서 대부분의 범용OS들은 교착상태를 무시하지만 비행시스템, 우주비행 등 교착상태를 반드시 해결해야 하는 시스템에는 적용되야 한다.

교착상태로부터 회복

• 탐지 알고리즘에 의해 교착상태가 존재한다고 결정되면 2가지 방법을 통해 해걀한다.

  • 순환 대기를 탈피하기 위해 한 개 이상의 프로세스를 중지

  • 교착 상태의 프로세스들로부터 자원을 선점

• 프로세스 종료

  • 교착 상태 프로세스들을 모두 중지

    • 확실하게 교착상태 순환을 해결하지만 비용이 많이 든다.

  • 교착 상태가 해결될 때까지 한 프로레스씩 중지 (부분 종료)

    • 각 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출하여 프로세스들이 아직도 교착상채에 있는지를 확인해야 하기 때문에 부담이 크다.

• 자원선점

  • 프로세스들로부터 자원들을 선점하여 이들을 교착 상태가 해결될 때까지 다른 프로세스들에게 주어야 한다.

  • 해결해야 할 사항

    • 희생자의 선택 - 비용을 최소화하기 위해 선점의 순서를 결정해야 한다.

    • 롤백 - 선택된 프로세스를 안전한 상태로 롤백시키고 다시 시작해야 한다.

    • 기아 - 기아가 발생하지 않는 것을 보장해야 한다. (교수님이 구체적인 해결방법을 소개하지 않음)

---

Chapter 8 Memory Management

• 주 메모리와 처리기에 내장되어 있는 레지스터들은 CPU가 직접 접근할 수 있는 유일한 저장장치이다.

• 모든 실행되는 명령어와 자료들은 주 메모리와 레지스터에 있어야 한다.

  • 실행을 위해 메모리로 들어오기를 기다리고 있는 디스크 상의 프로세스 집합들이 입력 큐에 배치

  • 시스템은 입력 큐에서 하나의 프로세스를 선택해서 메모리에 적재

  • 프로세스가 실행될 때 기억 장치의 명령이 자료를 접근

  • 대부분의 시스템에서 사용자 프로세스는 메모리의 임의 장소에 상주될 수 있다.

주소의 할당 -> 한 주소 공간에서 다른 주소 공간으로 사상시키는 것

• 컴파일 시간 바인딩 (absolute code)

  • 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다.

  • 만일 이 위치가 변경되어야 한다면 이 코드는 다시 컴파일 되어야 한다.

• 적재 시간 바인딩 (relocatable code)

  • 프로세스가 메모리 내에 적재될 위치가 컴파일 시간에 알려지지 않는 경우

  • 재배치 코드를 생성하고 최종 바인딩은 적재 시간까지 연기

  • 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다.

• 실행시간(수행시간) 바인딩

  • 프로세스가 실행 중간에 메모리 세그먼트에서 다른 세그먼트로 이동될 수 있다면 바인딩은 실행시간까지 연기

  • 이러한 일이 가능하려면 특별한 하드웨어를 사용해야 한다.

논리 대 물리 주소공간 (Logical-Versus Physical-Address Space)

• 논리적 주소

  • CPU가 생성하는 주소

• 물리적 주소

  • 메모리에 나타나는 주소

• Memory Managment Unit (MMU)

  • 가상 주소에서 물리 주소로의 사상을 수행하는 하드웨어 장치 (base register)

동적 적재 (Dynamic Loading)

• 루틴이 호출될 떄까지 메모리에 적재되지 않고 재배치 가능한 적재형태로 디스크에서 대기

• 사용되지 않는 루틴은 적재 되지 않는다.

• 운영체제로부터 특별한 자원을 필요로 하지 않는다.

Swapping

• 프로세스는 필요한 경우 임시로 보조 메모리로 보내어졌다가 다시 메모리로 돌아올 수 있다.

• 교체시간의 대부분은 전송시간

연속 메모리 할당 (Contiguous Memory Allocation)

• 주 메모리는 운영체제 뿐만 아니라 여러 사용자 프로세스를 수용해야 하며 각 영역은 목적에 맞도록 관리되어야 한다.

• 사용자 프로세스에 의한 변화로부터 운영체제의 코드 및 데이터 보호가 필요

• 기준 레지스터와 한계 레지스터의 사용

메모리 할당 (Memory Allocation)

• 외부 단편화 (external fragmentation)

  • 프로세스들이 메모리에 적재되고 제거될 때, 자유 공간은 작은 조각으로 나누어짐으로써 메모리에 많은 수의 작은 자유 공간들이 존재한다.

• 외부 단편화 해결

  • 아주 작은 가용 공간은 큰 요구에 포함시켜 할당

    • 할당된 기억공간은 요구된 메모리보다 약간 더 클 수 있다. -> 여기서 남는 부분이 내부 단편화

  • 압축 (compaction)

    • 메모리의 내용들을 적절하게 움직여서 모든 자유 공간을 하나의 큰 블록으로 만든다.

    • 재배치가 동적이고 수행시간에 이루워지는 경우에만 가능

    • 압축하는 시간이 오래 걸리기 때문에 사용하지 않는다.

<br>

• 최초 적합 - 충분히 큰 첫번째 가용 공간에 할당

• 최적 적합 - 충분히 큰 가용 공간들 중에서 가장 작은 가용 공간을 할당

• 최악 적합 - 가장 큰 가용 공간을 할당

Paging

• 외부 단편화는 기억장소가 연속되지 않고 산재된 많은 블록이 흩어져 있을때 발생한다.

• 특정 프로세스에 할당된 기억 장소는 연속되어 있어야 하므로 산재된 불연속의 기억장소는 사용할 수 없다.

• 페이징은 논리주소 공간이 한 연속적인 공간에 모여 있어야 한다는 제약을 없앤다.

• 전통적으로 하드웨어에 의존적이다.

• 페이지 테이블

  • 각 페이지에 대해 실제 메모리에서 시작주소를 포함

• 페이지 번호

  • 페이지 테이블의 index로 사용

• 페이지 변위

  • 해당 페이지에서의 데이터 시작 주소

• 특징

  • 외부 단편화는 발생하지 않는다. -> 내부 단편화는 발생한다. (프레임 단위로 할당되므로)

  • 페이징 자체는 동적 재배치 형태 -> 모든 논리 주소는 페이징 하드웨어에 의해 물리 주소로 사상

  • 메모리에 대한 사용자 인식과 실제 내용이 서로 다르다. -> 운영체제에 의해 물리적 메모리의 할당 및 접근관리

• 페이지 테이블의 구현

  • 페이지 테이블을 메모리에 유지 -> 메모리 위치에 접근하는데 많은 시간이 소요

  • Translation look-aside buffers (TLBs)

    • 매우 빠른 연관 메모리로 구성

    • 주소가 연관 메모리에 있으면 대응되는 프레임 번호를 얻고 없으면 메모리에 있는 페이지 프레임 번호를 얻는다.

      • 연관 메모리 -> RAM 보다 가격이 비싸며 탐색 시간이 중요한 응용에 사용된다. 즉 탐색하고자 하는 데이터의 전부 또는 일부분이 주어졌을 때 그 데이터가 저장된 메모리 주소를 반환.

메모리 보호

• 페이지화 된 환경에서 메모리의 보호는 각 프레임과 연관된 보호 비트에 의해 구현된다.

• 이 비트들은 페이지 테이블에 속해있으며, 한 비트는 이 페이지가 읽기, 쓰기 또는 읽기 전용임을 정의할 수 있다.

• 메모리에 대한 모든 접근은 페이지 테이블을 거치므로, 주소 변환과 함께 읽기 전용 페이지에 쓰기 연산이 실행되지 않도록 검사하는 작업도 실행된다.

• 페이지 테이블의 각 엔트리에는 유효/무효 비트가 하나 더 있다.

• 비트가 유효이면 합법적인 페이지, 무효이면 그 페이지는 프로세스의 논리주소공간에 속하지 않음을 나타낸다.

페이지 테이블의 구조 (Structure of the Page Table)

• 큰 논리 주소 공간을 지원하는 시스템의 경우에 페이지 테이블은 상당히 크다.

• 페이지 테이블 구성 방법

  • 다단계 페이징

  • 해싱 페이지 테이블

  • 역 페이지 테이블

계층적(다단계) 페이징

• 2단계 페이징 기법

  • 페이지 테이블 자체가 다시 페이징 된다.

• 해시형 페이지 테이블

  • 주소공간이 32비트보다 커지면 가상주소를 해시값으로 사용한다.

  • 해시 페이지 테이블의 각 항목은 연결리스트를 가지고 있고 각 원소는 가상페이지번호, 맵핑되는 페이지 프레임번호, 연결 리스트상의 다음원소를 가리키는 포인터 값을 가진다.

    1. 가상 주소의 가상 페이지 번호를 해싱한다.

    2. 해당 해시값의 연결 리스트의 첫 번째 원소와 가상 페이지 번호를 비교한다.

    3. 일치하면 그에 대응하는 페이지 프레임 번호를 사용하여 물리주소를 얻는다.

    4. 일치하지 않으면 연결 리스트의 그 다음 원소들은 탐색해가며 일치하는 가상 페이지 번호를 찾는다.

• 역 페이지 테이블

• 메모리의 각 실제 페이지에 대해 하나의 엔트리 -> 실제 메모리 위치를 저장한 페이지의 가상 주소로 사상

• 시스템에는 하나의 페이지 테이블만 존재 -> 실제 메모리의 각 페이지에 하나의 항목만을 가진다.

• 페이지를 참조할 때 테이블을 찾는데 필요한 총 시간은 증가한다. (성능이 떨어짐)

세그멘테이션 (Segmentation)

• 메모리를 크기가 변할 수 있는 세그먼트 모임으로 생각

• 메모리의 사용자 관점을 지원하는 메모리 관리 기법

• 프로그램은 여러 세그먼트들로 구성된다.

Chapter 9 Virtual Memory

가상메모리

• 물리 메모리부터 사용자 논리 메모리를 분리

• 프로세스의 전체가 완전히 메모리 내에 존재하지 않아도 수행이 가능한 기법

• 프로그램을 일부분만 메모리에 올려 놓고 실행할 수 있다면

  • 프로그램은 물리 메모리 크기에 제약 받지 않는다.

  • CPU의 이용률과 처리율의 증가

  • 프로그램을 메모리에 올리고 스왑하는데 필요한 입출력들이 적어지므로 보다 빨리 수행될 수 있다.

요구 페이징

• 필요한 프로그램만 메모리에 적재하는 방법으로 가상 메모리 시스템에서 많이 사용된다. 요구 페이징을 사용하는 가상 메모리에서는 페이지들이 실행 과정에서 실제로 필요해질 때 적재된다.

• 즉 초기에 필요한 것들만 적재하고 실행과정에서 실제로 필요할 때 적재하는 기법, 한번도 접근되지 않은 페이지는 물리 메모리에 전혀 적재되지 않는다.

• 실제 필요한 페이지들만 메모리로 읽어오므로 시간 남비와 메모리 공간 낭비를 줄일 수 있다.

• 프로세스가 메모리에 존재하는 페이지들만 접근하는 한 실행은 정상적으로 진행된다.

• 프로세스가 메모리에 올라와 있지 않는 페이지를 접근하려고 하면 페이지 부재 트랩을 발생시킨다.

• 요구 페이징 시스템에서 페이지 부재율을 낮게 유지시키는 것이 상당히 중요하다.

  • ex) 평균 페이지 부재 서비스 시간이 8ms, 메모리 접근 시간이 200ns

  • 컴퓨터는 요구 페이징 때문에 40배나 느려지는 현상이 나타난 것이다.

Copy-on-Write

• 처리되고 있는 프로세스들 중에는 같은 자원을 공유하는 경우가 종종 있다.

• 각각의 자원영역을 두고 처리하는 것이 이상적이지만, 자원영역은 한정되어 있기 때문에 상황에 따라서는 공유가 되어야 한다.

• 문제는 자원을 공유받는 주체 프로세스가 자원에 대해서 임의의 수정을 요구하는데서 문제가 방생한다.

• 주체 프로세스 입장에서는 병 영향을 받지 않지만, 이걸 같이 공유하는 프로세서 입장에서는 수정하기 이전의 자원이 중요한 역할일 수 있기 때문

• 따라서 평소에는 자원을 공유해서 같이 사용하다가 수정이 필요한 시점에 자원의 복사본을 사용하도록 한다.

• 이후에는 프로세서에서 포인터만 변경시켜서 사용한다.

페이지 교체 (page replacement)

• FIFO 페이지 교체 알고리즘

• 최적 페이지 알고리즘

• LRU 페이지 교체 알고리즘

• LRU 근사 페이지 교체 알고리즘

• 계수-기반 페이지 교체 알고지즘

FIFO 페이지 교체 알고리즘 (First-in-First-out Replacement Algorithm)

• 가장 간단한 페이지 대치 알고리즘

• 각 체이지에 메모리 안으로 들어온 시간을 연관

  • 큐를 사용할 수도 있음

• 페이지가 교체되어야 할 때 가장 오래된 페이지를 선택

• 이해하기 쉽고 프로그램하기 좋다.

• 프에임의 수가 많아진다고 성능이 좋아지는 것은 아니다. (Belady’s anomaly)

최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm)

• 앞으로 가장 오랜 기간 동안 사용되지 않은 페이지를 교체

• 모든 알고리즘 가운데 페이지 부재율이 가장 낮다.

• 현실적으로 최적 페이지 교체 알고리즘은 구현하기 어렵다. (참조열에 대한 미래지식을 알기 어렵기 때문 / 주로 비교 연구를 위해 사용)

LRU 페이지 교체 알고리즘 (Least Recently Used Page Replacement Algorithm)

• 오랜 기간 동안 사용되지 않은 페이지를 교체

• LRU 페이지 교체 알고리즘의 구현 - 카운터의 사용, 스택의 사용

• Belady’s anomaly가 없다.

• 하드웨어의 자원이 필요하다.

• 카운터의 사용

  • 각 페이지 항목 마다 사용 시간 필드를 넣고 CPU에 논리 클럭이나 카운터를 추가

    • 메모리 접근시미다 시간증가

    • 페이지에 대한 참조가 있을 떄마다 시간 레지스터의 내용을 페이지의 사용 시간 필드에 복사

    • 가장 작은 시간 값을 가진 페이지를 교체

• 스택 사용

  • 페이지 번호의 스택을 유지

    • 페이지가 참조할 때마다 페이지 번호를 스택의 top에 유지

    • bottom에 있는 페이지가 가장 오래 전에 사용된 페이지

LRU 근사 페이지 교체 알고리즘

• 시스템들이 LRU페이지 교체를 위한 하드웨어 지원을 충분히 할 수 없다.

• 다른 페이지 교체 알고리즘 요구 -> 많은 시스템들이 참조 비트의 형태 지원

• 부가적 참조 비트 알고리즘

  • 각 페이지의 대해 8비트 유지

  • 타이머 인터럽트가 제어를 운영체제에 넘기면 참조 비트를 8비트의 높은 자리로 이동하고 다른 비트를 오른쪽으로 이동

  • 가장 낮은 번호를 가진 페이지를 대치

• 이차적 기회 알고리즘

  

  • 페이지가 선택 될 때마다 참조비트를 확인한다.

  • 잠조 비트가 0이면 페이지를 교체하고 1이면 다시 한번 기회를 주고 다음 FIFO페이지로 넘어간다.

  • 한 번의 기회를 받게 되면 참조 비트는 해제되고 도착시간이 현재시간으로 재설정 된다.

  • 그 페이지는 다른 모른 페이지들이 교체될때까지 (또는 기회를 받을 때 까지) 교체되지 않는다.

  • 이차 기회 알고리즘은 순환큐를 이용하거나 FIFO를 이용한다.

계수 기반 페이지 교체

• LFU 알고리즘

  • 각 페이지마다 참조 회수에 대한 계수기를 두고 가장 작은 수를 가진 페이지가 대치된다.

• MFU 알고리즘

  • 가장 작은 계수를 가진 페이지가 방금 들어온 것이므로 앞으로 더 사용될 것이라는 것에 근간을 둔것

페이지 버퍼링 알고리즘 (Page Buffering Algorithm)

• 여러 개의 자유 프레임을 풀에 넣어 가지고 있다가 페이지 교체가 필요할 때, 자유 프레임에 새로운 페이지를 읽어 들이고, 희생될 프레임을 찾은 뒤 그 프레임을 디스크에 기록하고 자유 프레임 풀에 추가한다.

Allocation of Frames

최소 프레임 수

• 기억 장소 할당에는 제한이 있엇서 총 유효 프레임 수보다 많이 할당할 수 없지만 할당 가능한 최소 프레임이 있다.

• 몇 개의 프레임만 할당하면 당연히 성능이 떨어지므로 할당해야 할 최소 프레임 수가 존재

  • 명령어 집합 구조(instruction set architecture)에 의해 정의된다.

Priority allocation

• 우선 순위의 고려

  • 우선 순위가 높은 프로세스에 많은 기억 장소를 할당하여 수행 속도를 높이는 것이 바람직

• 비례 할당법을 사용하되 할당하는 프레임 수를 프로세스의 상대적 크기가 아닌 우선 순위를 고려하거나 둘 모두를 고려하거나, 우선 순위가 높은 프로세스가 교체할 프레임을 우선 순위가 낮은 프로세스에 할당 된 프레임 중에서 선택하도록 함.

전역 대 지역 할당

• 전역 교체

  • 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 대상으로 찾는 경우이다. 전역교체에는 한 프로세스에 할당된 프레임의 수는 변할 수 있다. 전역 교체 방법에서는 다른 프로세스들이 그 프로세스의 프레임을 교체하지 않는다는 전제하에 프로세스가 매번 다른 프로세스의 프레임을 할당 받게 되면 그 프로세스에 할당된 페이지 수가 증가하게 된다.

• 지역 교체

  • 각 프로세스가 그 프로세스에 할당된 프레임들 중에서 교체될 희생자를 선택할 수 있는 경우이다.

  • 프로세스에 할당된 프레임의 수는 변하지 않는다.

Thrashing

• 프로세스가 실제로 사용하는 프레임 수만큼의 프레임을 가지지 못해 계속적으로 페이지 부재가 발생함해 계속적으로 페이지 교체가 일어나는 현상

• 프로세스 실헹 시간보다 페이지 교체 시간이 더 클 때 발생

• 프로세스 실행보다 페이지 교체에 보내는 시간이 더 크기 때문

1. 다중 프로그래밍 정도가 높아짐에 따라 CPU 이용률이 높아진다.

2. CPU이용률이 최대값에 도달했을때, 다중 프로그래밍 정도가 그 이상으로 커지만 쓰레싱이 일어나게 되고 CPU 이용률은 급격이 떨어진다.

3. 운영체제는 CPU 이용률을 감시하면서, CPU 이용룰이 너무 낮아지면 새로운 프로세스를 시스템에 더 추가해서 다중 프로그램밍의 정도를 높인다.

4. 이 때 전역 페이지 교체 알고리즘을 사용하여 어떤 프로레스의 페이지인지에 대한 고려 없이 교체를 수행한다.

• 쓰레싱은 지역교환 알고리즘이나 우선순위 교환 알고리즘을 사용하여 제한할 수 있음

• 작업 집합 모델 사용

  • 운영체제는 각 프로세스의 작업집합을 감시하고 각 프로세스에게 작업집합의 크기에 맞는 충분한 프레임을 할당

  • 이렇게 할당하고도 여분의 놀고 있는 프레임이 있다면 또 새로운 프로세스를 시작시킬 수 있다.

  • 실행중인 프로세스의 수가 너무 많이지면 운영체제는 프로세스들 중 하나를 선택하여 그 프로세스의 페이지를 빼앗거나 연기시켜 그 프레임을 다른 프포세스에게 할당한다.

  • 중단된 프로세스는 후에 다시 실행이 재개된다. 이 방법은 쓰레싱을 방지하고 CPU의 이용률을 최적화 한다.

  • 작업 집합 모델의 어려운 점은 작업 집합을 추적하는 일이다.

  • 작업 집합은 메모리 참조마다 한쪽에서 새로운 페이지들이 추가 되고 다른 한쪽에서는 오랜된 참조 페이지로 부터 제외된다.

  • 이를 효율적으로 관리하기 위해 일정 간격 타이머 인터럽트와 참조 비트를 쓰면 어느정도 유사한 모델을 근사화 할 수 있다.

  • 이 방법 또한 어느 페이지가 사용되었는지 근사치를 알 뿐 정확하지 않다. 따라서 과거 기억 비트수를 늘리고 타이머 인터럽트 빈도를 높이면 불확실성을 줄일 수 있지만 자주 발생하는 인터럽트의 처리의 오버해드는 증가한다. (성능이 떨어진다.)

페이지 부재율 조절

• 페이지 부재율이 너무 높으면 그 프로세스가 더 많은 프레임을 필요로 하는 것이고 너무 잦으면 프로세스가 너무 많은 프레임을 갖고 있다는 것

• 페이지 부재율의 상한과 하안을 두고 상한을 넘으면 프레임을 더 할당하고 하한보다 낮으면 프레임을 회수

• 페이지 부재율이 증가되고 유효 프레임이 없으면 한 프로세스를 선택하여 중지