프로세스와 스레드의 차이
프로세스
- 실행중인 프로그램으로, 디스크로부터 메모리에 적재되어 cpu의 할당을 받을 수 있는 것을 말합니다.
- 하드디스크에 있는 프로그램이 실행되면, 메모리 할당이 이루어지고, 할당된 메모리 공간에 바이너리 코드가 올라가게 됩니다. 이 순간부터 프로세스라고 말할 수 있습니다.
프로세스 메모리 구조
- 텍스트 영역: 컴파일된 기계어가 저장되는 영역
- 데이터 영역: 전역변수, static 변수가 저장되는 영역
- DATA: 초기화된 전역변수가 저장되는 영역
- BBS: 초기화되지 않은 전역변수가 저장되는 영역 - 힙 영역: 동적 할당을 위한 메모리 영역
- 스택 영역: 지역변수, 매개변수, return 주소가 저장되는 영역
프로세스 제어 블록(Process Control Block: PCB)
프로세스의 중요한 정보를 담고있는 운영체제의 자료구조입니다. 운영체제는 프로세스들을 관리하기 위해서 프로세스의 생성과 동시에 고유한 PCB를 생성합니다. 프로세스는 CPU를 할당받아 작업을 처리하다가도 프로세스 전환이 발생하면 진행하던 작업을 저장하고 CPU를 반환해야 하는데, 이때 작업의 진행 사항을 모두 PCB에 저장하게 됩니다. 그리고 다시 CPU를 할당받으면 PCB에 저장되어 있던 내용을 불러와서 종료시점부터 다시 작업을 수행합니다. 운영체제는 빠르게 PCB에 접근하기 위해서 프로세스 테이블을 사용하여 각 프로세스의 PCB를 관리합니다.
PCB에 저장되는 정보
- 프로세스 ID
- 프로세스 상태
- 프로세스 카운터: 다음에 실행할 명령어의 주소
- CPU 레지스터: CPU에서 사용한 레지스터의 정보를 잃지 않기 위해 PCB에 그 값을 저장
- CPU 스케쥴링 정보: 프로세스의 우선순위, 스케줄 큐에 대한 포인터
- 메모리 관리 정보: 페이지 테이블, 세그먼트 테이블의 정보
- 입출력 상태 정보: 프로세스에 할당된 입출력 장치들과 열린 파일 목록
- 어카운팅 정보: CPU 사용 시간, 시간 제한
프로세스 상태
- new: 프로세스가 생성되는 단계
- ready: 프로세스가 CPU의 할당을 기다리는 상태
- running: CPU를 할당받아 작업 수행하는 상태
- blocked: CPU를 할당받아도 작업을 수행할 수 없는 상태(I/O 작업)
- terminated: 프로세스의 실행 종료
- suspended: 프로세스의 중지 상태
- suspended ready: ready 상태의 프로세스가 디스크로 스왑아웃
- suspended blocked: blocked 상태의 프로세스가 디스크로 스왑아웃
스레드
프로세스의 실행 단위입니다. 한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 주소공간이나 자원을 공유할 수 있습니다. 스레드는 스레드 ID, 프로그램 카운터, 레지스터 집합, 스택으로 구성됩니다. 같은 프로세스의 다른 스레드와 코드 영역, 데이터 영역, 그리고 운영체제의 자원을 공유합니다.
멀티 스레딩
하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고, 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것을 멀티 스레딩이라고 합니다. 이 경우 각각의 스레드는 독립적인 작업을 수행해야 하기 때문에 각자의 스택과 PC 레제스터 값을 갖습니다.
스택을 스레드마다 독립적으로 할당하는 이유
스택은 함수 호출 시 전달되는 인자와 되돌아갈 주소 값, 지역변수를 저장하기 위한 메모리 공간입니다. 스택 메모리 공간이 독립적이라는 것은 독립적인 함수 호출이 가능하다는 것이고, 독립적인 실행 흐름의 추가가 가능하다는 것입니다. 스레드의 정의에 따라 독립적인 실행 흐름을 추가하기 위한 최소한의 조건으로 독립된 스택을 할당합니다.
PC Register를 스레드마다 독립적으로 할당하는 이유
PC값은 스레드가 명령어의 어디까지 수행했는지를 나타냅니다. 스레드가 CPU를 할당받아 작업을 수행하다가 스케줄러에 의해 선점 당할 수 있는데, 이때 작업이 어디까지 수행했는지 기억할 필요가 있기 때문에, PC값을 스레드마다 독립적으로 할당해야 합니다.
멀티 스레드
멀티 스레딩의 장점
프로세스를 이용하여 동시에 처리하던 일을 스레드로 구현할 경우 메모리 공간과 시스템 자원 소모가 줄어듭니다. 스레드 간에 통신이 필요한 경우 별도의 자원을 사용하는 것이 아니라 데이터 영역 또는 힙 영역을 이용해서 데이터를 주고 받을 수 있습니다. 그렇기 때문에 프로세스 간의 통신 방법에 비해 스레드 간의 통신 방법이 훨씬 간단합니다. 심지어 스레드의 context switch는 프로세스의 context switch와는 달리 캐시 메모리를 비우지 않아도 되기 때문에 빠릅니다.(메모리를 공유하기 때문에) 따라서 시스템의 처리량이 향상되고, 자원 소모가 줄어들면서 프로그램의 응답시간이 단축됩니다. 이러한 장점 때문에 여러개의 프로세스로 할 수 있는 작업을 하나의 프로세스를 스레드로 나누어서 수행하는 것입니다.
멀티 스레딩의 문제점
멀티 프로세스 기반으로 프로그래밍을 할 때는 자원을 공유하지 않기 때문에, 동일한 자원에 동시에 접근할 일이 없지만, 멀티 스레딩 기반으로 프로그래밍을 할 때는 이 부분을 신경 써줘야 합니다. 서로 다른 스레드는 데이터 영역과 힙 영역을 공유하기 때문에, 한 스레드에서 다른 스레드가 사용중인 변수나 자료구조에 접근해서 엉뚱한 값을 가져오거나 수정할 수 있습니다. 그렇기 때문에 동기화 작업이 필요합니다. 동기화를 통해서 작업 처리 순서를 컨트롤 하고, 공유 자원의 접근을 컨트롤 하는 것입니다. 하지만 이로 인해서 병목현상이 발생하여 성능이 저하될 가능성이 높기 때문에, 과도한 락으로 인한 병목현상을 줄여야 합니다.
병목현상
시스템 내의 데이터 처리속도가 지연됨에 따라, 다음에 오는 데이터 처리가 지연되는 현상입니다. 즉, 일부분에 의한 전체 하향 평준화를 말합니다.
예를 들어, 스레드 A가 공유 자원인 자원1에 접근하기 위해서 락을 걸어두었는데, 스레드 B, 스레드 C가 자원1에 접근을 하기 위해서는 앞에 처리가 끝날 때까지 줄줄이 기다려야 합니다.
멀티 스레드 vs 멀티 프로세스
멀티 스레드는 멀티 프로세스보다 적은 메모리 공간을 차지하고 문맥 전환이 빠르다는 장점이 있지만, 오류로 인해 한 스레드가 종료가 되면 전체 스레드가 종료가 될 수 있다는 점과 동기화 문제가 있습니다. 반면에 멀티 프로세스는 한 프로세스가 종료되어도 다른 프로세스에 영향을 주지 않고 정상적으로 수행된다는 장점이 있지만 멀티 스레드보다 많은 메모리 공간과 CPU 시간을 차지한다는 단점이 있습니다. 두 방식 모두 여러개의 작업을 동시에 수행한다는 점에서 같지만, 적용해야 하는 시스템에 따라서 적합한지, 부적합한지가 구분이 됩니다. 그렇기 때문에 적용해야 하는 시스템에 따라서 적합한 동작 방식을 선택하고 적용해야 합니다.
스케줄러
프로세스를 스케줄링 하기 위한 Queue에는 세 가지 종류가 존해합니다.
- Job Queue: 시스템 내에 있는 모든 프로세스의 집합
- Ready Queue: 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
- Device Queue: Device I/O 작업을 대기하고 있는 프로세스의 집합
각 Queue에 프로세스들을 넣고 빼주는 스케줄러에도 세 가지 종류가 존자합니다.
장기 스케줄러(Long-term scheduler or job scheduler)
메모리는 한정되어 있는데, 많은 프로세스들이 메모리에 한꺼번에 올라가게 되는 경우 디스크에 임시로 저장이 됩니다. 이 곳에 있는 프로세스들 중에서 어떤 프로세스에 메모리를 할당하고 ready queue에 보낼지를 결정하는 역할을 합니다.
- 메모리와 디스크 사이의 스케줄링을 담당
- 프로세스에 메모리를 할당합니다.
- 실행중인 프로세스의 수를 제어
- 프로세스의 상태를 new -> ready로 바꿉니다.
단기 스케줄러(Short-term scheduler or CPU scheduler
- CPU와 메모리 사이의 스케줄링을 담당
- ready queue에 있는 프로세스 중 어떤 프로세스를 running 시킬지 결정
- 프로세스에 CPU를 할당합니다.
- 프로세스의 상태를 ready -> running -> waiting -> ready
중기 스케줄러(Medium-term scheduler or Swapper)
- 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫒아냄
- 프로세스에게서 메모리를 반환 받습니다.
- 현재 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러
- 실행중인 프로세스의 수 제어
- 프로세스의 상태 ready -> suspended
Suspended
외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태입니다. 프로세스가 디스크로 스왑아웃 됩니다. blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready 상태로 돌아갈 수 있지만, suspended 상태는 외부적인 이유로 정지되었기 때문에 스스로 돌아갈 수 없습니다.
CPU 스케줄러
스케줄링 대상은 Ready Queue에 있는 프로세스들입니다.
FCFS(First Come Fist Served)
특징
- 먼저 온 순서대로 처리
- 비선점형(No-Preemptive) 스케줄링
일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않습니다. 할당되었던 CPU가 반환될 때만 스케줄링이 이루어집니다.
문제점
- convoy effect(호위효과): 소요시간이 긴 프로세스가 먼저 들어오게 되면 효율성이 낮아집니다.
SJF(Shortest-Job-First)
특징
- 다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 CPU를 먼저 할당합니다.
- 비선점형 스케줄링
문제점
- starvation(기아현상): CPU 사용시간이 긴 프로세스는 영원히 CPU를 할당받을 수 없습니다.
SRTF(Shortest Remaining Time First)
특징
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어집니다.
- 선점형 스케줄링
현재 수행중인 프로세스의 남은 CPU burst time보다 더 짧은 CPU burst time을 가진 프로세스가 도착하면 CPU를 뺏깁니다.
문제점
- starvation
- 운영체제가 프로세스의 CPU burst time을 정확히 예측하기 힘듭니다.
Priority Scheduling
특징
- 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링입니다. 우선순위는 정수로 표현하게 되고, 작은 숫자가 우선순위가 높습니다.
- 선점형 스케줄링 방식
더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추로 CPU를 선점합니다. - 비선점형 스케줄링 방식
더 높은 우선순위의 프로세스가 도착하면 ready queue의 head에 넣습니다.
문제점
- starvation
해결책
- aging
아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주는 방법입니다.
Round Robin
특징
- 현대적인 CPU 스케줄링
- 각 프로세스는 동일한 크기의 할당 시간을 갖게 됩니다.
- 할당 시간이 지나면 프로세스는 선점 당하고 ready queue의 제일 뒤에 가서 다시 줄을 섭니다.
- RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 경우에 효율적
- RR이 가능한 이유는 프로세스의 context를 save 할 수 있기 때문입니다.
장점
- 응답속도가 빨라집니다.
- 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가하기 때문에, 공정한 스케줄링이라고 할 수 있습니다.
주의할 점
설정한 time quantum(타임 퀀텀)이 너무 커지면 FCFS와 같아집니다. 또 너무 작아지면 스케줄링 알고리즘 목적에는 이상적이지만 잦은 context switch로 overhead가 발생합니다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요합니다.
동기와 비동기 차이
Sync vs Async
일반적으로 동기와 비동기의 차이는 메소드를 실행시킴과 동시에 반환되는 값을 기대하는 경우 동기라고 표현하고, 그렇지 않은 경우를 비동기하고 표현합니다. 동시라고 하는 것은 실행되었을 때 값이 반환되기 전까지는 blocking되어 있다는 의미입니다. 비동기의 경우, blocking 되지 않고 이벤트 큐에 넣거나 백그라운드 스레드에 해당 task을 위임하고 바로 다음 코드로 넘어가기 때문에 기대되는 값이 바로 반환되지 않습니다.
프로세스 동기화
Critical Section(임계구역)
동일한 자원에 동시에 접근하는 작업(e.g. 공유하는 변수 사용, 동일 파일을 사용하는 등)을 실행하는 코드 영역을 Critical Section 이라고 합니다.
Critical Section Problem(임계구역 문제)
Requirements(해결을 위한 기본조건)
- Mutual exclusion(상호 배제)
한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없습니다. - Bounded wating(한정된 대기)
어떤 프로세스도 무한 대기를 하지 않아야 합니다. 다른 프로세스의 기아를 방지하기 위해, 한 번 임계구역에 들어간 프로세스는 다음번 임계 구역에 들어갈 때 제한을 두어야 합니다. - Progress Flexibility(진행)
임계 구역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러 개라면 어느 것이 들어갈지 결정해줘야 합니다.
해결책
Mutex Lock(Spin Lock)
Critical Section에 진입하는 프로세스는 Lock을 획득하고 Critical Section을 빠져나올 때, Lock을 반환해서 공유자원에 동시에 접근이 되지 않도록 합니다.
멀티 코어 환경이고, 임계구역에서의 작입이 컨텍스트 스위칭보다 더 빨리 끝나는 경우에 효율적입니다.
단점
Busy waiting: 어떤 프로세스가 임계 구역에 접근하기 위해서 Lock이 풀릴때까지 무한 루프를 돌면서 계속 상태를 확인해야하는 문제입니다. 만약 싱글 코어일 경우 CPU를 쓸데없이 소모시키므로, 다른 프로세스가 생산적으로 사용할 수 있는 시간을 감소시킵니다.
Semaphores(세마포)
임계구역에 동시에 접근할 수 있는 프로세스의 수가 1개 이상이 될 수 있습니다. 동기화 대상의 개수를 정해줄 수 있는데, 일반적으로 세마포의 값이 0이면 자원에 접근할 수 없고, 0보다 크면 접근이 가능합니다. 프로세스가 임계구역에 하나 들어오면 세마포의 값을 1 감소시키고, 나가면 다시 값을 1 증가시키는 방식입니다.
종류
- 바이너리 세마포
세마포의 값이 1인 경우로, 뮤텍스 락과 비슷하게 동작합니다.
동기화 대상 - 카운팅 세마포
양의 정수인 세마포 값을 가지는 경우입니다.
세마포어도 뮤텍스처럼 busy waiting이 있습니다.
busy waiting 해결
임계구역 진입을 위해 무한루프를 돌며 대기하는 것 대신, 프로세스를 중지시키고 큐에 넣습니다.
1. 세마포 값이 0이하면 프로세스를 중지시키고 wating queue에 넣습니다.
2. 어떤 프로세스가 임계 구역에서 나오면 signal()함수로 대기 큐에 있는 프로세스를 waiting queue에서 빼고 깨워 ready queue에 넣습니다.
시그널 메커니즘
wait & signal를 이용해서 순서를 정해줄 수 있습니다. wait & signal 연산 순서를 바꿔서 실행하거나 둘 중 하나라도 생략하면 교착 상태가 발생할 수 있습니다.
교착상태
둘 이상의 프로세스가 임계구역 진입을 무한정 기다리고 있고, 임계구역에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되어야만 빠져나올 수 있는 상황을 말합니다.
뮤텍스와 세마포어의 차이
뮤텍스는 락을 걸어둔 프로세스만이 임계 구역을 나갈때 락을 해제할 수 있지만, 세마포어는 락을 걸지 않은 프로세스도 signal을 사용해서 락을 해제할 수 있습니다.
모니터
상호 배제를 프로그램으로 구현한 것으로, 공유자원과 공유 자원 접근함수로 이루어져 있으며, 2개의 큐를 가지고 있습니다.
- 상호 배제 큐(Mutual Exclusion Queue)
공유 자원에 하나의 프로세스만 진입하도록 하는 큐입니다. - 조건 동기 큐(Conditional Synchronization Queue)
공유 자원의 Lock 이 해제되기를 기다리는 프로세스가 대기하는 큐로, 이미 공유자원을 사용하고 있는 프로세스가 특정한 호출 wait()을 통해 조건 동기 큐로 들어갈 수 있습니다.
- synchronized: 이 키워드를 적어주기만 하면 상호 배제의 원리를 만족시키는 함수로 만들어줍니다.
- wait(): 진입한 스레드를 조건 동기 queue에 블록 시킵니다.
- notify(): 대기하고 있는 스레드 중 하나를 깨웁니다.
- notifyAll(): 대기하고 있는 스레드를 모두 깨웁니다.
이진 세마포어만 가능합니다. 직접 키해제와 공유자원의 접근 처리를 해줘야하는 세마포와는 다르게 모니터는 키의 획득과 해제를 모두 처리해주어서 간단합니다.
메모리 관리 전략
메모리 관리 배경
각각의 프로세스는 독립적인 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있습니다. 운영체제만이 운영체제의 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않습니다.
Swapping
메모리 관리를 위해 사용되는 기법입니다. 다중 프로그래밍 환경에서 CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억 장치(e.g. 하드디스크)로 내보내고 다른 프로세스의 메모리를 불러 들입니다. 이 과정을 스왑이라고 합니다. 주 기억장치(RAM)로 불러오는 과정을 swap-in, 보조 기억장치로 내보내는 과정을 swap-out 이라고 합니다.
단편화(Fragmentation)
프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼의 작은 자유공간들이 늘어나게 되는데, 이것이 단편화입니다. 단편화는 2가지 종류로 나뉩니다.
- 외부 단편화
메모리 공간 중 사용하지 못하게 되는 일부분으로, 메모리에서 사이사이 남는 공간들을 모두 합치면 충분한 공간이 되는 부분들이 분산되어 있을때 발생한다고 볼 수 있습니다. - 내부 단편화
프로세스가 사용하는 메모리 공간에 포함된 남는 부분입니다. 예를들어, 메모리 분할 자유 공간이 100이 있고 Process A 가 98 사용하게 되면 2 라는 차이가 존재하고, 이 현상을 내부 단편화라고 합니다.
압축
외부 단편화를 해소하기 위해 프로세스가 사용하는 공간들을 한쪽으로 몰아, 자유공간을 확보하는 방법론이지만, 작업효율이 좋지 않습니다.
페이징
하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 메모리 관리 방법입니다. 외부 단편화와 압축 작업을 해소하기 위해 생긴 방법론이로, 물리 메모리는 frame 이라는 고정 크기로 분리되어 있고, 논리 메모리는 페이지라 불리는 고정 크기의 블록으로 분리됩니다.
페이징 기법을 사용함으로써 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 프레임에 적절히 배치됨으로 외부 단편화를 해결할 수 있는 큰 장점이 있습니다.
하나의 프로세스가 사용하는 공간은 논리 메모리에서 여러개의 페이지로 나뉘어서 관리되고, 개별 페이지는 순서에 상관없이 물리 메모리에 있는 프레임에 mapping 되어 저장된다고 볼 수 있습니다.
단점
내부 단편화 문제의 비중이 늘어나게 됩니다. 예를 들어, 페이지 크기가 1024B이고 프로세스 A가 3172B의 메모리를 요구한다면 3개의 페이지 프레임 하고도 100B가 남기 때문에 총 4개의 프레임이 필요한 것입니다. 결론적으로 4번째 페이지 프레임에는 924B의 여유공간이 남게 되는 내부 단편화 문제가 발생하는 것입니다.
세그멘테이션
페이징에서처럼 논리 메모리와 물리 메모리를 같은 크기의 블록이 아닌, 서로 다른 크기의 논리적 단위인 세그먼트로 분할합니다. 세그먼트 테이블에는 각 세그먼트의 시작 물리 주소와 세그먼트의 길이를 저장합니다.
단점
서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 자유 공간들이 많은 수의 작은 조각들로 나누어져 못 쓰게 될 수도 있습니다.(외부 단편화)
가상 메모리
다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야 합니다. 가상메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있습니다.
가상 메모리 개발 배경
실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 메모리 용량보다 큰 프로그램은 실행시킬 수 없었습니다. 또한, 여러 프로그램을 동시에 메모리에 올리기에는 용량의 한계와 페이지 교체 등의 성능 이슈가 발생하게 됩니다.
프로그램의 일부분만 메모리에 올릴 수 있다면
- 물리 메모리 크기에 제약받지 않게 됩니다.
- 더 많은 프로그램을 동시에 실행할 수 있게 됩니다. 이에 따라 응답시간은 유지되고, CPU 이용률과 처리율이 높아집니다.
- swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행됩니다.(=프로세스의 일부분만 swap 하도록 처리)
가상 메모리가 하는 일
가상 메모리는 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것으로 정리할 수 있습니다. 이로써 작은 메모리를 가지고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공할 수 있습니다.
가상 주소 공간
- 한 프로세스가 메모리에 저장되는 논리적인 모습을 가상메모리에 구현한 공간입니다. 프로세스가 요구하는 메모리 공간을 가상메모리에 제공함으로써 현재 직접적으로 필요치 않은 메모리 공간은 실제 물리 메모리에 올리지 않는 것으로 물리 메모리를 절약할 수 있습니다.
- 예를 들어, 한 프로그램이 실행되며 논리 메모리로 100KB가 요구되었다고 가정합니다. 하지만 실행까지에 필요한 메모리 공간(힙 영역, 스택 영역, 코드, 데이터)의 합이 40KB라면, 실제 물리 메모리에는 40KB만 올라가 있고, 나머지 60KB 만큼은 필요시에 물리메모리에 요구합니다.
프로세스간의 페이지 공유
가상 메모리는
- 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 합니다. 각 프로세스들은 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있습니다.
- 프로세스들이 메모리를 공유하는 것을 가능하게 하고, 프로세스들은 공유 메모리를 통해 통신할 수 있습니다. 이 또한, 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있습니다.
- fork()를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 합니다.
요구 페이징(Demand Paging)
프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라 하며, 가상 메모리 시스템에서 많이 사용됩니다. 그리고 가상 메모리는 대개 페이지로 관리됩니다. 요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재됩니다. 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않습니다.
프로세스 내의 개별 페이지들은 페이저에 의해 관리됩니다. 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어 옮으로써, 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 줄일 수 있습니다.
페이지 교체
요구 페이징에서 언급된대로 프로그램 실행시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하게 되면, 원하는 페이지를 보조기억장치에서 가져오게 됩니다. 하지만, 만약 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 이뤄져야 합니다.
기본적인 방법
물리 메모리가 모두 사용중인 상황에서의 메모리 교체 흐름입니다.
1. 디스크에서 필요한 페이지의 위치를 찾습니다.
2. 빈 페이지 프레임을 찾습니다.
i. 페이지 교체 알고리즘을 통해 희생될 페이지를 고릅니다.
ii. 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정합니다.
3. 비워진 프레임에 새 페이지를 읽어오고, 프레임 번호를 페이지 테이블에 저장합니다.
4. 사용자 프로세스 재시작
참고
페이지 교체 알고리즘
FIFO 페이지 교체
가장 간단한 페이지 교체 알고리즘으로, FIFO(first-in-first-out)의 흐름을 가집니다. 즉, 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다는 것입니다.
장점
- 이해하기 쉽고, 프로그램하기도 쉽습니다.
단점
- 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있습니다.(초기 변수 등)
- 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있습니다.
- Belady의 모순: 페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순이 존재합니다.
최적 페이지 교체(Optimal Page Replacement: OPT)
Belady의 모순을 확인한 이후 최적 교체 알고리즘에 대한 탐구가 진행되었고, 모든 알고리즘보다 낮은 페이지 부재율을 보이며 Belady 모순이 발생하지 않습니다. 이 알고리즘의 핵심은 앞으로 가장 오랫동안 사용하지 않을 페이지를 찾아 교체 하는 것입니다. 주로 비교 연구 목적을 위해 사용합니다.
장점
- 알고리즘 중 가장 낮은 페이지 부재율을 보장합니다.
단점
- 구현의 어려움이 있습니다. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문입니다.
LRU 페이지 교체(LRU Page Replacement)
LRU(Least-Recently-Used)
최적 알고리즘의 근사 알고리즘으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체합니다. 대체적으로 FIFO 알고리즘보다 우수하고, OPT 알고리즘보다는 그렇지 못한 모습을 보입니다.
LFU 페이지 교체(LFU Page Replacement)
LFU(Least-Frequently-Used)
참조 횟수가 가장 적은 페이지를 교체하는 방법입니다. 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘입니다.
- 어떤 프로세스가 특정 페이지를 집중적으로 사용하다, 다른 기능을 사용하게되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되는 시점이 발생할 수 있습니다.
- 최적 페이지 교체를 제대로 근사하지 못하지 때문에, 잘 쓰이지 않습니다.
MFU 페이지 교체(MFU Page Replacement)
MFU(Most-Frequently-Used)
LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.
- 최적 페이지 교체를 제대로 근사하지 못하지 때문에, 잘 쓰이지 않습니다.
캐시의 지역성
캐시의 지역성 원리
캐시 메모리는 속도가 빠른 장치와 느린 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리입니다. 이러한 역할을 수행하기 위해서는 CPU가 어떤 데이터를 원할 것인가를 어느 정도 예측할 수 있어야 합니다. 캐시의 성능은 작은 용량의 캐시 메모리에 CPU가 이후에 참조할, 쓸모있는 정보가 어느 정도 들어있느냐에 따라 좌우되기 때문입니다.
이때 적중율(Hit rate)을 극대화 시키기 위해 데이터 지역성(Locality)의 원리를 사용합니다. 지역성의 전제조건으로 프로스램은 모든 코드나 데이터를 균등하게 Access하지 않는다는 특성을 기본으로 합니다. 즉, Locality란 기억 장치 내의 정보를 균일하게 Access 하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성인 것입니다.
이 데이터 지역성은 대표적으로 시간 지역성과 공간 지역성으로 나뉩니다.
- 시간 지역성(Temporal Locality): 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성입니다.
- 공간 지역성(Spatial Locality): 대부분의 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성입니다.
캐시는 프로세서(CPU) 가까이에 위치하면서 빈번하게 사용되는 데이터를 놔두는 장소입니다. 하지만 캐시가 아무리 가까이 있더라도 찾고자 하는 데이터가 어느 곳에 저장되어 있는지 몰라 모든 데이터를 순회해야 한다면 시간이 오래 걸리게 됩니다. 즉, 캐시에 목적 데이터가 저장되어 있다면 바로 접근하여 출력할 수 있어야 캐시가 의미 있어진다는 것입니다.
그렇기 때문에 캐시에 데이터를 저장할 때 특정 자료구조를 사용하여 묶음으로 저장하게 되는데 이를 캐싱 라인이라고 합니다. 프로세스는 다양한 주소에 있는 데이터를 사용하므로 빈번하게 사용하는 데이터의 주소 또한 흩어져 있습니다. 따라서 캐시에 저장하는 데이터에는 데이터의 메모리 주소 등을 기록해 둔 태그를 달아놓을 필요가 있습니다. 이러한 태그들의 묶음을 캐싱 라인이라고 하고 메모리로부터 가져올 때도 캐싱 라인을 기준으로 가져옵니다. 종류로는 대표적으로 세 가지 방식이 존재합니다.
- Direct Map
메인 메모리를 캐시의 크기로 각각의 블록을 캐시의 정해진 위치에 매핑하는 방식입니다. 각 캐시 블록은 지정된 캐시 라인에만 저장될 수 있습니다. 그래서 캐시 메모리에 데이터가 있는지 찾으려면 비교는 한번만 해도 되어서 빠르지만, 충돌이 그만큼 자주 일어난다는 단점이 존재합니다. - FUll Associative
태그와 관계없이 비어있는 캐시 메모리를 탐색해서 집어넣고 데이터가 있는지 찾을때도 순차적으로 탐색해서 가져오는 방식입니다. 충돌의 위험은 적겠지만 비교할 때마다 순차탐색 시간이 발생하므로 오래 걸립니다. - Set Asscociative
FUll Associative와 Direct Map의 장점들을 고려하여 만들어진 방식입니다. 테이블을 여러개 만들면 같은 태그의 메모리라도 다른 테이블의 태그에 저장하면 되는 원리라서 테이블의 개수에 따라 n-way set associative라고 부릅니다. 이렇게 하면 n번만큼 탐색해서 Direct Map보단 시간이 조금 더 걸리겠지만 충돌위험은 더 줄어들게 됩니다.
