운영체제

📚 CS Study

 

운영체제

✅  프로세스 ( Process ) 

✏️ 프로세스가 무엇인가 ?

프로세스는 실행중인 프로그램으로 디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 상태이다. 프로세스는 운영체제로부터 주소 공간, 파일, 메모리 등을 할당 받는다.

 

✏️프로세스의 메모리구조는 어떻게 생겼나 ?

스택영역 : 지역변수, 매개변수, 리턴 값 등이 임시로 저장되어 고정된 크기의 공간이다. 주로 함수가 불렸을 때 데이터를 저장했다가 함수가 종료될 때 데이터를 반환한다.

힙 영역 : 프로세스가 동작중에 동적으로 데이터를 할당하는 공간이다.

데이터 영역 : 데이터 영역에는 프로그램이 시작될 때 생성되는 전역변수, 정적변수 등이 저장된다.

• Blocked State Symbol 영역 : 데이터 영역에는 BBS 영역이 포함되어 있다. BSS 영역은 초기화 되지 않은 정적변수와 전역변수가 저장된다. 초기화 되지 않은 변수들은 값을 저장할 필요가 없기 때문에 공간의 낭비를 줄이기 위해 BSS 영역을 구분한다.

코드영역 : 코드 영역은 프로그램의 명령을 저장한다.

 

✏️ 프로세스가 가지는 모든 상태

NEW : 새롭게 생성된 프로세스가 가지는 상태

READY : 준비 큐에서 운영체제에 의해 CPU에 로드되길 기다리는 상태

RUNNING : CPU에 로드되어 실행중인 상태

WATING : I/O 이벤트가 발생했을 때 해당 이벤트가 처리되는 동안, 혹은 어떤 이벤트를 기다릴 때 Device queue에서 대기하는 상태

TERMINATED : 프로세스가 종료되고 CPU에서 제거되었을 때의 상태

 

✏️ 인터럽트와 트랩의 차이

인터럽트는 하드웨어에 의해 발생된다. 하드웨어 장치가 CPU를 사용해야 할 때, 인터럽트를 발생시킨다.

트랩은 소프트웨어에 의해 발생된다. 어떤 소프트웨어가 CPU에게 소프트웨어 동작에 필요한 동작을 요구할 때 트랩을 발생시킨다.

 

✏️ 시스템 콜이란 

시스템 콜은 프로세스가 트랩을 발생시킬 수 있도록 하기 위해  OS에서 제공하는 인터페이스이다.

프로세스는 시스템 콜을 발생시켜 자신이 직접 인터럽트 작업을 수행하지 않고 운영체제가 이 작업을 수행하도록 한다. 운영체제는 요청받은 시스템 콜을 ISR(Interrupt Service Routine) 에서 찾아 미리 정의된 시스템 콜 처리 작업을 수행한다.

 

✏️ PCB ( Process Control Block ) 이란?

PCB는 프로세스에 대한 정보를 담고 있는 자료구조이다. 이 PCB를 사용해서 프로세스를 관리한다. PCB는 프로세스의 생성과 함께 만들어진다.

PCB가 가지고 있는 정보

• 프로세스 ID
• 프로세스 상태
• 프로그램 카운터
• 계정정보
• 스케줄링 정보
• 부모 프로세스와 자녀 프로세스에 대한 카운터
• 레지스터 정보
• 입출력 상태

 

✏️ 컨텍스트 스위치란 

컨텍스트 스위치는 CPU를 점유하던 프로세스가 인터럽트에 의해 다른 프로세스로 교체할 때, 기존 프로세스의 레지스터 값을 저장하고 새로운 프로세스의 레지스터값을 CPU 레지스터로 로드하는 것을 말한다.

이 때, 레지스터 값을 저장하고 새로운 값으로 레지스터를 채우는 동안 CPU는 다른 작업을 할 수 없으므로 큰 오버헤드가 발생한다.

 

✏️ Orphan 프로세스와 Zombie 프로세스란

Orpahn 프로세스는 자녀 프로세스가 종료되기 전에 부모 프로세스가 wait 시스템 콜로 기다리지 않고 종료된 상태를 말한다. 리눅스 운영체제의 경우에는 Orphan 프로세스를 막기 위해 부모 프로세스가 먼저 종료된 자녀 프로세스를 루트 프로세스인 init 프로세스의 자식으로 편입시키고 주기적으로 wait 시스템콜을 호출하여 자녀 프로세스들의 상태를 회수한다.

Zombie 프로세스는 자녀 프로세스가 종료되었지만 부모 프로세스가 해당 프로세스를 회수하지 못한 경우를 말한다. 자녀 프로세스는 종료됐지만 부모 프로세스가 wait을 하지 않은 상태에서 발생한다.

 

✏️ 좀비 프로세스의 문제 

좀비 프로세스는 종료된 프로세스이기 때문에 CPU를 사용하지는 않지만 더 이상 사용하지 않는 리소스를 반환하지 않고 커널의 프로세스 테이블에 관리되어 불필요한 공간을 차지한다.

 

✏️ 프로세스 간 통신 방법

여러 프로세스가 서로 통신하기 위해서는 공유 메모리 방법이나 메세지 패싱 방법을 사용해야 한다.

공유 메모리는 한 프로세스에 공유 메모리를 설정하고 다른 프로세스들이 해당 메모리에 접근하여 버퍼를 통해 데이터를 공유하는 방식이다.

메세지 패싱 방법은 커널 영역에 통신을 위한 메일 박스를 만들어두고 이곳을 버퍼로 삼아 프로세스들이 데이터를 주고 받는다.

 

✏️ CPU 스케줄러란

Ready 큐에서 CPU에 로드되길 기다리는 프로세스들 중 어떤 프로세스를 로드할 것인지 결정한다. 단기 스케줄러라고도 한다.

 

✏️ 장기 스케줄러란

job 스케줄러라고 부른다. 메모리에 있는 프로세스중 어떤 프로세스를 준비 큐에 넣을지 결정되는 스케줄러이다. 또한 메모리에 올라와 있는 프로세스의 숫자를 제어해서 dgree of multiprogramming을 관리한다.

 

✏️ 다른 스케줄러 ?

중기스케줄러가 있다. 만약 메모리에 너무 많은 프로세스가 올라오게 되면 중기 스케줄러는 메모리에 있는 프로세스를 강제로 디스크의 스왑 영역에 저장한다. 이를 swap-out 이라고 한다.

 

✏️ 멀티 태스킹과 멀티 프로세싱의 차이

멀티 태스킹은 하나의 프로세서가 운영체제의 스케줄링을 받아 여러 작업을 빠르게 번갈아가면서 실행하는 방식이다.

멀티 프로세싱은 여러 프로세서가 여러 작업을 병렬적으로 수행하는 것을 말한다.

 

 

✅ Thread ( 스레드 )

✏️ 스레드가 무엇인가

프로세스가 수행하는 작업의 실행단위이다. 스레드는 프로세스 내부에 존재하며 프로세스가 할당받은 자원을 사용하여 작업을 수행한다.

 

✏️ 스레드와 프로세스의 차이

스레드는 프로세스 내에서 실행된다. 한 프로세스는 여러 스레드를 가질 수 있고, 이 스레드들은 해당 프로세스의 자원을 일부 서로 공유합니다. 프로세스는 생성시 코드영역, 데이터 영역, 힙 영역, 스택영역을 할당받는다. 스레드는 여기서 스택 영역만 각 스레드가 독립적으로 유지하고 나머지 영역들을 프로세스 내의 스레드들이 함께 공유한다.

 

✏️ 각 스레드가 독립적인 스택 영역을 가지는 이유

스택 영역을 따로 관리하기에 각 스레드는 서로 다른 작업을 수행할 수 있다. 함수 호출 시 한 스레드가 호출한 함수에 대한 스택정보가 다른 스레드에 영향을 준다면 스레드를 사용하는 의미가 없다. 각 스레드는 프로세스의 작업 흐름을 담당해야하므로 서로 다른 작업 흐름을 가지는 것이 허용되어야 한다. 이를 위해 스택영역을 독립적으로 가지고 이와 더불어서 프로그램 카운터 레지스터 역시 독립적으로 가지게 된다.

 

✏️ 멀티 스레딩과 사용하는 이유

멀티 스레딩은 하나의 프로그램을 여러개의 스레드로 구성해서 여러 스레드가 한 프로세스를 병렬적으로 실행할 수 있도록 하는 방법이다. 한  프로세스 내부의 스레드는 서로 힙 영역을 공유하기 때문에 별 다른 통신 기술을 사용하지 않고도 스레드끼리 데이터를 공유할 수 있다. 또한 스레드는 서로 공유하는 영역이 많이 때문에 CPU 캐시의 hit 비율이 더 높고 이 때문에 멀티프로세싱보다 컨텍스트 스위칭의 비용이 더 저렴하다.

 

✏️ 사용자 수준 스레드와 커널 수준 스레드의 차이

사용자 수준 스레드는 사용자 영역의 스레드 라이브러리를 통해 구현된다. 모든 구현과 동작은 사용자 영역에서 진행되기 때문에 커널은 사용자 수준 스레드의 존재 유무를 알지 못한다.

커널 수준 스레드는 운영체제가 생성하고 관리한다.

 

✏️ 멀티 스레딩의 문제점

멀티 스레딩을 사용하게 되면 모든 스레드들이 데이터 영역, 힙 영역, 코드 영역을 공유하게 된다. 이 때 다수의 스레드가 데이터 영역과 힙 영역의 데이터에 동시에 접근하게 되면 동기화 문제가 발생한다. 이를 해결하기 위해 Mutex나 Semaphore 같은 방법을 사용한다.

 

 

✅ CPU 스케줄링

✏️ 선점형 스케줄링과 비선점형 스케줄링의 차이

선점형 스케줄링은 CPU에 할당된 프로세스가 작업이 완전히 끝나지 않도록 강제적으로 기존 프로세스를 새로운 프로세스로 교체해버리는 스케줄링 방법이다.

비선점형 스케줄링은 반대로 CPU에 할당된 프로세스의 작업이 완전히 끝난 이후에 CPU에 할당되는 프로세스를 교체하는 스케줄링 방법이다.

 

✏️ FCFS 스케줄링 알고리즘

준비 큐에 먼저 도착한 프로세스를 CPU에 할당하는 프로세스로 선택하는 스케줄링 알고리즘이다.

 

✏️ FCFS를 자주 사용 할까?

아니다. FCFS 알고리즘은 항상 먼저 도착한 프로세스를 선택하기 때문에 만약 가장 늦게 도착한 프로세스가 얼마 걸리지 않는 작업을 수행하는 프로세스일경우 문제가 생긴다. 해당 프로세스가 실제로 작업에 필요한 시간은 짧지만 실행을 위해 준비 큐에서 오랫동안 기다려야 하는 큰 취약점을 가지고 있다.

 

✏️ SJF 알고리즘은 어떨까?

SJF 알고리즘은 수행시간이 가장 짧은 프로세스를 우선적으로 처리하여 준비 큐의 프로레스들의 대기시간을 최소화하는 알고리즘이다. 따라서 운영체제의 스케줄링에 가장 적합한 알고리즘이라고 할 수 있다.

 

✏️ 이 알고리즘은 자주 사용 할까?

아니다. 실제로 어떤 프로세스의 수행시간을 실행하지 않고 알아낼 수 있는 방법이 없기 때문에 구현이 불가능한 알고리즘이다. 하지만 다음 프로세스의 수행시간이 이전 수행시간과 비슷할 것이라는 가정을 하여 수학적 예측을 통해 구현할 수는 있다.

 

✏️ 그렇다면 실제로는 어떤 알고리즘을 주요 사용할까 

RR 이나 Priority 스케줄링을 함께 사용한다. RR 스케줄링은 Time quantum 이라고 부르는 타임 스태프를 사용해서 스케줄링을 한다.

 

운영체제는 준비 큐에 있는 프로세스들을 정확히 Time quantum 시간 만큼만 CPU에 할당시키고 시간이 끝나면 곧바로 다음 프로세스와 교체시킨다. 이렇게 스케줄링을 하면 다수의 프로세스를 여러번에 나눠서 실행할 수 있기 때문에 반응속도가 중요한 시스템에서 유용하게 사용될 수 있다.

 

Priority 스케줄링은 준비 큐에 있는 프로세스들을 우선순위에 따라 CPU에 할당하는 알고리즘이다. 새로운 프로세스가 준비 큐에 도착했을 때, 우선순위가 높다면 도착시간과는 관계없이 먼저 선택된다.

 

✏️ RR 알고리즘의 단점은 ?

Time Quantum 에 의존적이다. 만약 Time quantum이 준비 큐에 있는 각 프로레스의 수행시간보다 길다면, FCFS과 동일한 스케줄링이 된다. 반대로 Time quantum이 너무 짧다면, 프로세스의 컨텍스트 스위칭이 지나치게 많이 발생할 수 있다.

 

✏️ Priority 스케줄링 단점은?

우선순위에 따라 스케줄링을 하게되면 우선순위가 상대적으로 낮은 프로세스가 실행되지 못하고 장시간동안 준비 큐에 남아있을 수 있다. 이런 현상을 Stravation 혹은 Identinite Blocking 이라고 한다. 

 

✏️ 이 문제는 어떻게 해결 ?

두 가지 방법이 있다. 첫번째는 Aging기법을 사용하여 준비 큐에 오래 머무는 프로세스의 우선순위를 점진적으로 높여주는 방식이다. 다른 방법은 RR 알고리즘을 섞어서 사용하는 것이다. RR은 공정하게 모든 프로세스에게 CPU를 점유하게 한다. 우선순위에 따라 프로세스들이 정렬되고 프로세스들에 대해 RR을 사용한다면 큐의 뒤에 위치한 프로세스도 CPU 점유의 기회를 받을 수 있게 된다.

 

✏️ 멀티 레벨 큐란 ?

준비 큐를 여러개의 큐로 구성하고 새로운 프로세스가 들어올 때마다 중요도에 따라 각각 다른 큐에 넣어 관리하는 알고리즘이다. 각 큐는 서로 다른 스케줄링 알고리즘을 사용한다. 하지만 각 프로세스가 한 큐에서 다른 큐로 이동할 수 없어 유연하지 못한 스케줄링 기법이다.

 

✏️  멀티 레벨 피드백 큐란 ?

여러 큐로 나눈 준비 큐의 상위 계층에 time quantum 을 두어 CPU 사용시간에 따라 프로세스의 위치를 바꿔주고 스케줄링 알고리즘을 단계별로 다르게 적용하는 알고리즘이다.

 

✏️ 실시간 스케줄링에는 어떤 방법이 있을까

Rate Monotonic 스케줄링이 있다. 이 알고리즘은 프로세스의 우선순위에 따라 CPU에 프로세스를 스케줄링한다. 이 때, 우선순위는 각 프로세스가 가지는 CPU 요청 주기에 따라 주기가 짧은 프로세스가 높은 우선순위를 가지게 된다.

다음은 Earlist Deadline First 스케줄링이다. 이 알고리즘은 각 프로세스의 마감시간을 기준으로 우선순위를 부여한다. 마감시간이 빠르면 높은 우선순위가 부여된다. 각 프로세스들은 자신이 실행가능한 상태가 되면 시스템의 자신의 마감시간을 알리고 이 마감시간으로 우선순위를 부여하게 된다. 이 알고리즘은 이론적으로 완벽하지만 프로세스가 교체되면서 발생하는 컨텍스트 스위칭의 오버헤드 때문에 딜레이가 생겨 실제로는 구현이 불가능하다.

 

✅ 동기화 

✏️ Race Condition이란

스레드가 데이터에 어떤 순서로 접근하는지에 따라 실행결과가 달라지는 상황

 

✏️ 임계구역이 무엇이고 임계구역 문제 해결을 위한 필수 요구 조건

임계구역은 어떤 코드의 영역에서 다수의 프로세스가 서로 데이터를 공유하는 부분. 한번에 여러 스레드가 접근하여 데이터를 변경하면 동기화 문제가 발생한다.

임계구역 문제를 해결하기 위해서는 세가지 요구조건을 만족시켜야 한다.

• 상호배제 : 어떤 프로세스가 임계 구역에 있다면 다른 스레드는 임계구역으로 진입할 수 없습니다.
• 임계구역에 스레드가 없고 다수의 스레드가 임계구역 진입을 위해 대기중이라면 하나의 스레드를 적절하게 골라 임계구역에 진입시켜야 한다.
• 한번 임계구역에 진입했던 스레드는 다음 실행에 대한 제한을 받아야 한다.

 

✏️ 임계구역 문제를 해결하기 위한 하드웨어적인 방법

Test&Set과 Compare-and-Swap이 있다. 두 방법 모두 임계구역 진입을 위한 원자적인 연산을 보장한다. 이를 통해 상호배제와 진행조건을 만족시킨다. 하지만 한번 임계구역에 진입했던 스레드가 다시 임계구역으로 재진입하는 것을 제한하지 않기 때문에 한정 대기 요구조건을 만족시키지는 못한다.

 

✏️ 세마포어란 

Wait, Signal의 원자적 명령을 사용해서 공유자원 문제를 해결한다. 세마포어는 정수값을 가지고 이 값이 임계구역 내에 접근이 가능한 자원의 개수를 의미한다. 어떤 스레드가 자원을 획득하면 세마포어의 값이 감소하고, 방출하면 세마포어의 값이 증가한다.

 

✏️ 세마포어의 단점

스레드가 임계구역에 자리가 생길 때까지 무한루프를 돌며 기다리게 하는 스핀락으로 구현되어 있다. 이 때문에 불필요한 CPU Time을 사용한다는 단점이 있다.

 

✏️ 그럼 뮤텍스란 무엇인가

뮤텍스는 락을 획득한 스레드만이 락을 방출할 수 있는 반면에 세마포어는 signal 함수에 의해 락을 획득하고 있지 않은 스레드도 세마포어의 값을 증가시켜 다른 스레드를 임계구역으로 진입시킬 수 있다.

 

✏️ DeadLock이란

프로세스나 스레드가 서로의 자원을 얻기 위해 무한정하게 대기하고 있는 상태

 

✏️ DeadLock의 발생조건

4가지 조건

• 상호배제 : 한 스레드만 자원에 접근할 수 있다.
• 점유대기 : 이미 하나의 자원을 점유하고 있는 상태에서 다른 스레드에 할당된 자원을 점유하려는 스레드가 존재해야한다.
• 비선점 : 한 스레드에 할당된 자원은 스스로 방출할 때까지 선점될 수 없다.
• 순환대기 : 자원을 점유하려는 스레드들이 순환형태로 자원 점유를 위해 대기해야 한다.

 

✏️ DeadLock을 해결할 수 있는 방법

4가지 방법

• 예방 : 교착 상태가 발생하는 네 조건중 하나만 해결한다.
• 회피 : 자원 할당 그래프나 은행원 알고리즘을 통해 교착상태가 발생하지 않도록 한다.
• 회복 : 발생한 교착상태를 해결한다.
• 무시 : 교착상태를 무시한다.

 

✏️ 자원 할당 그래프 알고리즘이란

각 스레드가 공유자원을 그래프의 정점으로 만든다. 한 스레드가 다른 스레드에게 요청을 할 때는 요청 간선을 두 스레드 사이에 만든다. 그리고 한 스레드가 자원을 획득하면 할당선을 만들게 된다. 이 때 각 정점들 사이에 사이클이 발생하면 교착상태가 발생했다고 판단한다.

 

✏️ 은행원 알고리즘이란

안전상태와 불안정상태 개념을 사용한다. 안전상태는 스레드가 요구한만큼 자원할당이 가능한 상태를 말하고, 이때는 교착상태가 발생하지 않는다. 불안정상태는 요구받은 만큼의 자원을 가지고 있지 않은 상태를 말한다. 운영체제는 자원 할당 요청을 받았을때 해당 자원을 할당한 이후에 안전상태가 유지되는지 미리 검사한다. 그리고 안전상태가 유지되는 자원 요구만을 수락하고 불안정 상태를 만드는 요청은 모두 거절한다.

 

✅ 메모리

✏️ MMU란?

CPU와 메모리 사이에서 주소의 영역을 설정하는 역할을 한다. MMU 내부에는 재배치 레지스터가 존재해서 CPU가 요구하는 메모리의 위치와 실제 메모리상의 프로그램의 위치를 맞춰준다. 즉, 논리적 주소를 물리적 주소로 변환하는 작업을 한다.

 

✏️ Swapping이란?

현재 실행 중이지 않은 메모리에 올라온 프로세스 디스크에 임시 저장하고 필요할 때 다시 불러오며 메모리를 더 효율적으로 사용하기 위한  방법이다.

 

✏️ Swapping의 문제점 

임시 저장을 디스크에 하기 때문에 스왑의 속도가 오래걸린다. 실제로 사용할 때는 전체 프로세스를 스와핑하는것이 아니라 프로세스의 일부인 페이지만 스왑하거나 디스크내의 파일시스템과 분리된 스왑공간을 만드는 방식으로 구현한다.

 

✏️ 연속 메모리 할당 방법

- 최초적합 : 메모리의 시작이나 끝지점부터 탐색하면서 요청받은 프로세스를 할당할 수 있는 공간이 발견되면 곧바로 할당

- 최적적합 : 전체 메모리에 남은 공간을 다 확인해보고 요청받은 프로세스를 할당할 수 있는 가장 작은 공간에 할당

- 최악적합 : 전체 메모리에 남은 공간을 다 확인해보고 요청받은 프로세스를 할당할 수 있는 가장 큰 공간에 할당

 

✏️ 메모리단편화에 대해서

내부 단편화는 프로세스를 동일한 크기의 페이지로 분할할 때, 페이지를 모두 다 사용하지 않고 마지막 페이지의 일부만을 사용하여 페이지 내부에 빈 공간이 남게되는 상태이다. 외부 단편화는 프로세스를 연속 메모리에 할당할 때, 흩어진 빈 공간을 합치면 프로세스를 로드할 수 있는 만큼의 여유공간이 있지만 각각의 빈 공간들이 요청받은 프로세스를 할당할 수 있는 크기를 가지지 못해 프로세스를 로드할 수 없는 상태

 

✏️ 페이지 테이블이란

한 프로세스에 대한 논리주소와 물리 주소를 맵핑한 정보를 가진 테이블이다. 페이지 테이블은 메인 메모리에 저장되고 각 프로세스들은 PTBR ( Page Table Base Register )를 사용해서 페이지 테이블의 포인터를 저장한다. 따라서 프로세스가 변경될 때는 페이지 테이블을 교체하는 것이 아니라 포인터 주소만 바꿔서 오버헤드를 최소화한다.

 

✏️ TLB를 왜 쓰고 어떻게 쓰는건지 ?

페이지 테이블의 관점에서 CPU가 요청하는 주소가 실제 페이지까지 도달하기 위해서는 메모리를 두번 읽어야 한다. 먼저 레지스터에 저장된 페이지 테이블 포인터를 읽어 메인 메모리에 있는 페이지 테이블을 읽고, 페이지 테이블에 맵핑된 물리주소에 접근해 값을 가져올 때 한번 더 메모리를 읽게 된다. 이 때 발생하는 지연시간을 최소화하기 위해서 TLB를 사용한다.

 

CPU 요청하는 주소를 찾기 위해 바로 페이지에 접근하지 않고 TLB에 해당 논리주소에 대한 맵핑 주소가 있는지 확인한다. 만약 맵핑정보가 존재한다면 페이지 테이블을 거치지 않고 곧바로 맵핑된 물리 주소에 접근한다. 만약 정보가 없다면 페이지 테이블을 읽어 물리주소를 확인한 뒤 작업을 수행한다.

 

✏️ 공유페이지란?

똑같은 코드 영역을 사용하는 다수의 프로세스가 있을 때 하나의 페이지만 유지하고 각 프로세스의 페이지 테이블이 해당 페이지를 가르키게 하는 기법이다. 이를 통해 여러 프로세스가 중복으로 사용하는 페이지를 하나만 유지하여 메모리 공간을 절약할 수 있다.

 

✏️ 요구페이징이란 ?

프로세스의 페이지를 모두 메모리에 로드해서 사용하는 것이 아니라 당장 사용할 페이지만 로드하여 사용하는 방법이다. 페이지 테이블의 엔트리에 valid bit을 추가하는 것으로 구현한다. 만약 CPU에 접근하려는 페이지가 메모리에 없다면 invalid bit 를 표시하고 메모리에 존재한다면 valid bit 로 표시한다.

 

✏️ 페이지 폴트가 일어났을 때 어떤 일이 일어나는지 ?

CPU가 요청한 논리주소가 페이지 테이블 상에 invalid 비트로 설정되어 있다면 페이지 테이블이 CPU로 인터럽트를 보낸다. 인터럽트를 받은 CPU는 운영체제에게 Page Fault Routing을 요구한다. 운영체제는 backing store 혹은 스왑 공간에서 CPU가 원하는 페이지를 메모리로 가져온다. 그리고 페이지 테이블의 valid bit를 valid로 바꿔준다.

 

✏️ 지역성의 원리

시간적 지역성은 최근에 참조한 메모리 주소를 다시 참조할 가능성이 높다는 것이고, 공간적 지역성은 어떤 메모리 주소를 참조했을 때 다음에 참조할 메모리는 해당 주소 근처에 있을 확률이 높다는 것이다.

 

✏️ 페이지 교체 알고리즘의 종류

FIFO : 가장 먼저 메모리에 올라왔던 페이지를 디스크로 내보낸다.

OPT : 현재 메모리에 있는 프로세스 중 가장 오랫동안 사용되지 않은 페이지를 선택 ( SJF와 마찬가지로 구현 불가능 )

LFU : 일정 주기동안 참조횟수가 가장 적은 페이지를 선택

LRU : 마지막으로 가장 오랫동안 참조되지 않은 페이지를 선택