[기술면접 대비] 3. CS 공통 - 운영체제

[프로세스 관련]

프로세스란?
커널의 관리 하에 실행 중인 프로그램. 한 시스템 내의 작업의 단위.

프로그램은 디스크에 저장된 파일의 내용과 같은 수동적 개체라면 프로세스는 능동적인 개체.

프로세스 문맥 : CPU 상태(Program Counter, Register), 메모리 영역(code, data, heap, stack), 관련 커널 데이터(PCB, kernel stack-커널 영역에 프로세스 별로 별도의 커널스택을 생성) 

각종 자원(H/W 또는 S/W resource)을 요청하고 받을 수 있음

 

PCB란? 
프로세스 생성시 생성됨. 프로세스 관리에 필요한 정보 저장(Linked List 형태로 구성되어있음)
PID, Parent PID. 프로세스 상태, CPU 정보(CPU register context, Program Counter), 메모리 관리 정보, 입출력 상태 정보, 스레드를 가진다면 TCB 리스트 등
PCB 참조 및 갱신 속도는 OS의 성능을 결정짓는 주요 요소 중 하나

 

프로세스의 상태
created(new), ready, waiting, running, terminated
created : job이 커널에 등록되고 PCB 생성. 메모리 할당 못 받음 
ready : 프로세서(CPU) 외에 모든 자원을 할당 받음(admitted 됨). 
running : ready 상태의 프로세스가 dispatch(schedule)로 CPU를 할당받아 실제로 실행되는 상태

waiting : running 중이던 프로세스가 I/O 자원 등을 요청해 block 또는 asleep 됨. wake up 후에 ready로 감
terminated : 프로세스 수행이 끝난 후 exit 됨. 커널 내에 일부 PCB정보 외에 모든 자원을 반납함 
suspended : 메모리가 뺏긴 상태. 메모리 관점의 상태 (ready 또는 blocked 상태와 suspended 상태가 공존 가능)

page swap out, 일반 사용자의 일시정지 등 외부적인 이유로 메모리를 빼앗겨 프로세스 수행이 정지됨.

block 상태는 자신이 요청한 event에 의함(스불재), suspended는 외부에서 강제함.

* running -> ready 의 경우 : Interrupt 발생 (할당받은 time quantum 을 다 사용한 경우 등), 

* running -> waiting의 경우 : CPU외부 자원(보조기억 장치 등) I/O 요청 또는 event에 대한 응답대기

* blocked 상태에서 처리를 기다리는 queue는 커널의 메모리 공간에 자원당 각각 관리함

 ex) Disk I/O queue, keyboard I/O queue, Resource queue(공유데이터)

 

부모 프로세스와 자식 프로세스 

fork() 명령을 통해 부모 프로세스의 복사본인 자식 프로세스가 생성됨. 그 후 exec()명령으로 자식 프로세스를 분가시킴. 부모 프로세스는 자식 프로세스가 너무 많은 리소스를 사용하거나, 더이상 자식 프로세스가 필요 없거나, 부모 프로세스가 terminate될 때 abort()명령으로 자식 프로세스를 강제로 죽일 수 있다.

부모-자식의 트리 구조를 가진다.

자원 공유는 모두 공유, 일부 공유, 공유하지 않음 의 경우가 있다.

자식 프로세스와 부모 프로세스가 동시에 수행되거나, 자식 프로세스가 terminate 될 때까지 부모 프로세스가 기다릴 수 있다.

 

인터럽트란? 인터럽트의 종류, 처리 과정
예상치 못한 외부에서 발생한 이벤트. 현재 실행중인 프로세스와 무관한 외부의 개입이 kernel mode의 권한을 요청하는 것. 하드웨어와 소프트웨어 둘 다 인터럽트 발생 가능
timer interrupt(프로세스 스위칭), console,기계 오류 등

 

트랩이란?
소프트웨어 기반 이벤트. 현재 프로세스가 일으키는 kernel mode 권한 요청
잘못된 명령이나 데이터 사용(0으로 나누기, 오버플로우 등) 등으로 인한 에러 핸들링, 유저 프로그램의 system call 등  

 

context switching 과 overhead
Interrupt 또는 system call에 의해 OS커널이 프로세스를 스위칭 할 때, 실행 중이던 프로세스의 정보를 메모리의 kernel stack에 있는 PCB에 저장 또는 CPU로 복구하는 과정
이에 소요되는 비용이 overhead. OS 성능에 영향을 큰 줌.
context 스위칭이 빈번하다 = 프로세스 스위칭이 빈번하다 > 이러한 overhead를 줄이기 위해 스레드 사용 가능

 

스레드란? 프로세스와 스레드의 차이
하나의 프로세스를 다수의 실행단위로 나눈 것.
프로세스는 각각이 고유한 자원을 독립적으로 가지지만, 스레드는 프로세스의 리소스 (코드, data, heap)를 공유하고 stack과 제어정보(register set, PC)만 독립적으로 가짐 
스택은 독립적인 함수 호출 즉 독립적인 실행 흐름을 보장하기 위해 독립적으로 관리된다.

TCB의 내용 : TID, PCB의 메모리 주소, 스레드의 상태, CPU 정보(CPU register context, Program Counter), Stack Pointer 등

 

멀티 스레드의 장점
자원을 공유하기 때문에 자원 소모를 줄일 수 있고 프로세스를 생성하거나 프로세스 간의 context switching 에 드는 오버헤드를 줄일 수 있다. 사용자 응답시간이 단축되고(일부 스레드가 지연돼도 다른 스레드는 작업 가능), 병렬 처리를 통해 성능을 향상시킬 수 있다.

멀티코어 CPU(물리적)를 사용하는 경우는 중간에서 OS가 지원해준다.

hyper threading 각 코어가 멀티 register sets을 가짐(하드웨어가 지원하는 스레드 기능). 이 상황에서 멀티 스레드를 사용할 경우 overhead를 폭발적으로 줄일 수 있음

 

멀티 스레딩의 유의점

Concurrency Problem 서로 의존성을 가지는 thread의 경우, 각자 실행 순서나 context switching의 시점에 따라 결과가 달라지는 등의 문제가 발생. 

이러한 문제는 Synchronization 동기화와 Mutual exclusion 상호배제를 통해 Critical Section을 보호해야 함. 

 

CPU 스케쥴링
여러개의 프로세스에 자원을 할당할 프로세스를 선택해야 함. 시스템의 성능을 향상시키려는 목적.
성능 지표 : 응답시간(요청 후 응답을 받기까지 시간), 작업 처리량(주어진 시간 동안 완료된 작업의 수), 자원 활용도(자원이 활용된 시간/주어진 시간) 는 시스템의 목적에 맞게 고려할 것.
* Waiting Time 대기시간 (실행 시작 시간-도착 시간), Response Time응답시간 (응답 시간-도착 시간), Turnaround Time 반환시간 (실행 종료 시간-도착 시간), Burst Time 실행시간 (실행 종료 시간 - 실행 시작 시간)

 

단게(빈도)에 따른 스케쥴링
Long-term :  job scheduling에 사용됨(다중 프로그래밍의 정도를 결정), 시분할 시스템은 job을 모두 커널에 등록하기 때문에 상대적으로 덜 중요함(오늘날의 시스템은 new 대신 바로 ready로 다 보냄)
mid-term : 메모리 할당 결정에 사용됨 (스와핑) 
short-term : 프로세서를 할당해주는 프로세스 스케쥴링에 사용됨 (ready->running), 속도가 중요함

 

스케쥴링 정책관련 용어
선점 (preemptive) : 자원을 뺏길 수 있음 , 비선점(non-preemptive) : 스스로 반납하기 전까지 자원을 뺏을 수 없음
정적 우선순위 (static priority) : 프로세스 생성시 결정된 우선순위 유지. 동적 우선순위(dynamic priority) : 프로세스 상태에 따라 우선순위 변경 

 

대표적인 스케쥴링 알고리즘
FCFS(First-Come-First-Service) : 비선점, 도착시간을 기준으로 선착순 할당, 스케쥴링이 복잡하지 않아 스케쥴링 오버헤드가 작음, batch system(I/O없이 CPU만 주구장창 사용하는 시스템)에 적합하지만 평균 응답시간이 길다. 또한 실행 시간이 긴 프로세스가 먼저 도착하면 실행 시간이 짧은 프로세스들이 오래 기다려야 하는 문제가 있음(convoy effect).
SPN 또는 SJF : 비선점 실행시간이 가장 작은 프로세스를 먼저 처리, 평균 대기시간을 최소화 할 수 있지만 실행 시간이 큰 친구는 영원히 대기하는 무한대기 현상(starvation)이 발생, 프로세스의 burst time을 정확이 알 수 없으므로 평균적인 기록을 통해 예측해야 하며 복잡하다. 얘를 선점 방식으로 바꿔주면 STCF(shortest Time to Completion First) 방식이 됨.
RR(Round Robin) : 선점, FCFS를 기반으로 하지만 자원 사용 제한 시간(time quantum)을 두고 할당된 시간이 지나면 자원을 반납하고 맨 뒤로 가서 다시 기다림. 특정 프로세스의 독점을 방지하고 response time이 좋아져 시분할 시스템에 적합하지만, Turnaround Time이 중요한 프로그램에는 가장 나쁜 선택이 될 수 있다. 

Time quantum 이 너무 크면 FCFS와 다를바가 없고 너무 작으면 context switching 오버헤드가 커지므로 이를 적절한 크기로 나누는 것이 핵심

 

비동기적 병행적 관련 이슈 및 용어

공유 데이터 (Shared/Critical data) : 여러 프로세스들이 공유하는 데이터
임계 영역(Critical section) : 공유 데이터에 접근하는 코드영역

Atomic Operation 

더이상 쪼갤 수 없는 수행, 즉 수행 중에 쫓겨나지 않음을 보장함. ex) 메모리 로드와 할당

Race condition 

공유 자원에 대해 여러 개의 프로세스가 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태.

1) 커널모드 running 중 인터럽트 발생. (기존 커널모드와 interrupt handler의 자원 공유)

해결책 > 커널 모드 running 중 인터럽트가 발생해도 인터럽트 처리를 유보시킴

2) 프로세스가 system call을 해서 커널 모드로 작업 수행 중에 context switching이 발생(프로세스가 독립적으로 메모리를 가지고 있어도 둘 다 동일한 커널 메모리를 공유)

해결책> 프로세스가 커널모드에서 동작 중에 time quantam이 끝나도 preempt를 막음

3) 멀티 프로세스/스레드 환경에서 shared memory 내의 공유 자원 접근

해결책 > lock 등의 여러 기법 등장

 

해결 조건

1. Mutual Exclusion
상호배제. 둘 이상의 프로세스가 동시에 임계영역에 진입하는 것을 방지.

2. Progress 

진행. critical section에 이미 진입한 프로세스 외의 다른 프로세스가 다른 프로세스의 임계영역 진입을 막을 수 없음

3. Bounded waiting
한정대기. 프로세스의 임계영역 진입을 무한정 기다리게 두면 안됨.

 

spinlock

정수변수 S와 초기화 연산 P(S), V(S)은 OS가 아토믹한 연산을 보장하며(중간에 preemption 일으키지 않음) P연산은 S가 0이면 대기하다(lock이 선점된 상태) S가 1이 되는 순간(lock을 해제한 상태) S를 소비해서 0을 만들고(lock을 걸고) 임계영역에 진입, V연산은 lock 을 해제(임계영역에서 나올 때 S의 값을 1로 변경)하는 역할을 한다.

단점! 멀티 프로세서 시스템에서만 사용 가능, 여전한 busy waiting 문제

 

세마포어

SW 해결책(데커 피터슨, 다익스트라 알고리즘 등)이 가지는 복잡성과 busy waiting 문제, HW 해결책(TAS)이 가지는 busy waiting 문제를 해결하기 위해 OS가 지원하는 해결방안.

뮤텍스와 유사한 이진 세마포어와 유한한 n개의 자원의 개수를 표헌할 수 있는 카운팅 세마포어가 있다.

busy waiting을 해결하기 위해 ready queue를 추가한 방식. block() & wakeup()

기존의 P(S)연산은 CPU를 점유하고 반복문을 돌며 lock 권한을 대기하던 것을 세마포어에서는 lock을 얻지 못하면 block()상태로 자원에 해당하는 ready queue에 들어가므로 불필요한 CPU 점유를 막음.

V(S)연산은 ready queue에 기다리는 프로세스가 있다면 하나를 뽑아 임계영역을 양도하고, 없다면 S값을 변경하고(lock 해제) 임계영역을 빠져나감(당장 기다리는 프로세스가 없더라도 추후에 언젠가 도착할 프로세스는 락 권한을 바로 획득 가능).

 

대표 예제

1. bounded Buffer

유한한 크기의 circular buffer와 buffer를 채우는 producer, 소비하는 consumer가 존재

출처 : http://www.kocw.net/home/search/kemView.do?kemId=1046323

핵심 내용 두 개의 세마포어

1) P와 C의 공유 버퍼 접근 자체에 lock을 걸기 위한 이진 세마포어 mutex

2) P와 C가 조작을 가한 버퍼의 값을 카운팅하는 카운팅 세마포어 full, empty

 

로직  1), 5)는 카운팅 세마포어를, 2),3)은 이진 세마포어를 사용

1) P와 C는 각각 자신이 조작을 가할 버퍼의 값을 살핌

2) P는 empty 자원이 있을 때, C는 full 자원이 있을 때 버퍼에 접근하기 위한 lock권한을 획득

3) lock 권한을 획득하면 버퍼에 접근,조작 (P는 empty를 감소, C는 full을 감소)

4) lock 권한을 해제하고 

5) 상대 버퍼의 값을 추가로 조작 (P는 C가 참조할 full의 값을 증가, C는 P가 참조할 empty의 값을 증가)

 

2. Reader&Writer 

공유 DB에 쓰기를 수행하는 Writer와 읽기를 수행하는 Reader가 존재. Reader끼리는 동시에 DB 접근 가능

핵심내용 두 개의 세마포어, W/R가 서로 다른 권한

1) Writer는 DB 접근 권한을 얻기 위한 이진 세마포어 db가 필요함

2) Reader는 readcount값을 증가시키거나 감소시킬 권한을 얻기 위한 이진 세마포어 mutex가 필요함.

추가로 radcount값이 1또는 0일 때(내가 최초 혹은 최후의 reader일 때) Writer의 접근 권한을 제한/해제 하기 위한 db 세마포어도 함께 조작함 

 

로직 (W는 R가 끊이지 않고 들어올 경우 starvation이 발생할 수 있음)

1) W는 DB접근 권한을 살핌. 권한을 얻으면 DB를 조작하고 락을 해제함

2) R는 readcount에 대한 권한을 살핌.

3) 권한을 얻으면 readcount값을 증가시키고 내가 최초 리더일 경우에는 db락을 획득해 W의 접근을 막음.

(db락을 획들하려 할 때, 이미 도착한 W가 DB를 수정중이었다면 W가 db락을 해제하고 나갈 때 까지 P(db)를 획득하지 못하므로 대기)

4) readcount에 대한 권한을 해제함

5) DB를 읽음. 이 액션은 상호배제적이지 않으므로 아무런 lock를 필요로 하지 않음

6) 읽기가 끝난 후 또다시 readcount에 대한 권한을 살핌.

7) 권한을 얻으면 readcount값을 감소시키고, 내가 최후의 리더일 경우 db락을 해제해 W의 접근을 허용함. 

8) readcount에 대한 권한을 해제함

 

3. Dining Philosopher 

서로 동등한 조건과 액션을 하는 다중 사용자

핵심내용 두 개의 세마포어와 한 개의 상태값 타인의 값을 변경시키는 사용자

1) 식사를 위한 식기정보(self)를 각각 철학자의 수 n만큼 카운팅 세마포어 사용

2) 상태값(state)이라는 추가정보 사용 

2) state와 self에 접근하고 조작할 전체 권한을 획득하기 위한 이진 세마포어 mutex 

 

로직 (나중에 다시 보자;)

1) 철학자는 eat()을 수행하기전 pickup()을, 식사 후 putdown()을 수행

2) pickup()시 전체 권한 mutex를 확인

3) 권한을 얻으면 자신의 state를 변경하고, self 세마포어 값을 변경하기 위해 test()수행

4) 좌우의 철학자의 state가 식사중이 아니고, 내 state가 hungry일 경우, state를 eating으로 변경하고 내 식기에 대한 권한을 얻음 * V연산이 self 세마포어를 증가시키지만 권한을 획득하는 연산임

5) 

 

Monitor

동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct.

세마포어는 여전히 복잡한 과정을 직접 코딩해야 하고, 정확성 입증이 어려우며, 치명적인 실수의 가능성이 있음.

모니터는 language-level에서 지원하는 방법. 프로그램 언어가 사용을 지원하므로 프로그래머는 동기화 제약조건을 명시적으로 코딩할 필요가 없음.(lock을 걸지 않음)

물론 남아있는 자원의 수는 고려해야 함 이를 위해 condition variable 사용. 

condition variable은 wait와 signal 연산에 의해서만 접근 가능.

*condition variable은 카운팅 세마포어처럼 특정 값을 가지거나 조작하기 위한 것이 아님! 자신의 ready queue에 프로세스를 담아서 재우거나 깨워주는 역할을 하기 위해서만 수행함. (세마포어와 목적 자체가 다름!!!!!)

 

데드락이란? 데드락의 발생조건과 해결방안

프로세스가 발생 가능성이 없는 특정 이벤트 또는 자원을 기다리는 경우.(waiting state에서)

발생 요건 : Non-preemptible, exclusive, hold and wait, circular wait 

*deadlock과 starvation의 차이? 데드락은 waiting state에서 자원을 기다림. starvation은 ready state에서 CPU를 기다림. 또한 deadlock은 영원히 발생 가능성이 없은 애를 기다리지만 starvation은 언젠가 해결 가능성은 있음.

해결방안

예방 : 네 조건 중 하나라도 없애버리자. 대체로 비현실적이고 복잡함

회피 : 모든 시스템을 항상 safe states로 유지. 즉 데드락이 발생 가능한 상황을 끊임없이 체크하며 그런 경우 스케쥴링을 바꾸는 방식으로. 하지만 현실적으로 모든 프로세스의 상태와 앞으로 일어날 일을 다 파악하는 건 불가능하거니와 어마어마한 비용이 들기 때문에 비현실적임.

감지 및 복원 : 일어나게 두고, 데드락이 발생했는지 판단 후 복원시킨다. 프로세스를 아예 강제로 terminate 시키거나 리소스를 강제로 내려놓게 함.

 

IPC(Inter Process Communication)란?

ㅇㅇ

 

[메모리 관련]

 

메모리란?

* 계층 구조 : 레지스터 - 캐시 (HW관리)  / 주기억장치 - 보조기억장치 (SW 관리)

Block : 보조기억장치와 주기억장치 사이의 데이터 전송단위

Word : 주기억장치와 레지스터사이의 데이터 전송단위

Address Binding : 프로그램의 논리 주소를 실제 메모리의 물리 주소와 매핑하는 것

바인딩 시점에 따라 Complie time, Load time, Run time 바인딩으로 구분. 오늘날엔 Runtime 씀

Dynamic Loading : 프로그램의 루틴을 디스크에 저장해놓고 실제 호출 시점에만 메모리에 적재함

MMU Memory Management Unit : 

메모리 관련 고려사항

1) 프로세스에 할당되는 메모리 공간 크기

2) 메모리 분할 방법 (연속 할당 or 비연속 가상 메모리)

3) 메모리에 동시에 올라갈 수 있는 프로세스의 수(uni or multi programming)

 

연속 할당 Continuous Memory allocation

프로세스를 하나의 연속된 메모리 공간에 할당.

 

1. Uni-programming

메모리에 하나의 프로그램만 올라감

1) 프로세스 크기 > 메모리 크기?

 Overlay structure를 사용. 메모리에 현재 필요한 영역만 올림

 사용자가 프로그램의 흐름과 구조를 모두 파악하고 이를 나눠줘야 하는 어려움아 있음

2) 커널보호

 경계 레지스터(boundary register)를 사용해 커널 영역을 보호해야 함

3) 공간 낭비

 시스템과 자원의 활용도가 낮음 > 시스템의 성능이 낮음

 

2. FPM Fixed partition Multi-promramming

메모리 공간을 고정된 크기로 미리 분할. 각 프로세스는 하나의 파티션에 적재

(멀티 프로그램의 수 = 파티션의 수)

커널과 각 파티션 영역을 보호하는 boundary register가 필요함

 

3. VPM Variable Partition Multi-promramming

프로세스가 메모리 공간을 요청할 때 파티션을 동적으로 분할함

 

Fragmentation 단편화

 - internal 내부 단편화 : 파티션의 크기 > 프로세스의 크기 일 때 메모리가 낭비됨

 - external 외부 단편화 : 남은 메모리 크기 > 프로세스 크기 이지만 남아있는 메모리 공간이 연속된 공간이 아니라 메모리가 낭비됨

메모리 관리가 간편하지만, 단편화로 인해 자원이 낭비됨

1) internal fragmentation 관련 이슈

placement strategy : 프로세스가 메모리 공간을 반납하고 나간 뒤 남아있는 공간에 대한 배치 전략

- first-fit 최초적합 : 충분한 크기를 가진 첫번째 파티션을 선택. 간단하고 오버헤드가 적지만 공간 활용률이 떨어짐

- best-fit 최적 적합 : 프로세스가 들어가 수 있는 파티션 중 가장 작은 것을 선택, 큰 파티션을 아낄 수 있지만 모든 파티션을 탐색해야 하므로 오버헤드가 크며 자투리 파티션이 많이 낭비됨

- worst-fit 최악 적합: 프로세스가 들어갈 수 있는 파티션 중 가장 큰 것을 선택. 큰 파티션 확보가 어려움. 탐색 오버헤드가 큼. 작은 파티션의 발생을 줄일 수 있음 

- next-fit 순차 최초 적합 : 최초 적합 전략을 사용하되 이전 탐색 이후 위치부터 탐색. 메모리 영역의 사용빈도 균등. 오버헤드가 적음. 

2) External fragmentation 관련 이슈

- coalescing holes 공간 통합 : 프로세스가 메모리를 반납하고 종료되면 인접한 빈 파티션을 하나의 파티션으로 통합. 인접한 빈 메모리만 붙이므로 오버헤드가 작음

- storage compaction 메모리 압축 : 모든 빈 공간을 하나로 통합. 모든 수행중인 프로세스의 메모리 공간도 재배치를 하므로 오버헤드가 큼

 

 

가상 메모리 Virtual Memory 

메인 메모리 영역을 보조기억장치인 디스크까지 확장해 사용하면서 마치 무한한 여유 공간이 있는 것처럼 가상의 메모리 공간을 사용하는 것.

* 가상주소 virtual address = 상대주소 relative address = 논리주소 logical address 

* 실제 주소 real address = 물리 주소 physical address

* MMU Memory Management Unit : 가상주소-물리주소 매핑,

 

ex) 프로세스 A 메모리 2GB 필요 + 커널 메모리 2GB 필요 (총 4GB 메모리 필요) but, 메인 메모리 물리적 크기 256MB!하지만 메모리는 마치 4GB가 있는 것 처럼 0~4GB까지 가상의 메모리 영역을 프로세스에 할당해 줌.추가로 새로운 프로세스 B,C,D 등이 메모리를 요청해도 다~ 할당해줌.

 

어떻게? 프로그램의 크기를 잘게 쪼개서 디스크의 swap device(가상 메모리 영역)에 적재하고 있음. 그리고 CPU가 당장 요청하는 영역만 실제 메모리 영역에 올렸다가 내렸다가 하면서 메모리를 사용! (메모리에는 당연히 잘게 쪼개진 프로그램 덩어리가 부분별로 할당되었다가 내려갔다가 하므로 비연속 할당)따라서 CPU도 가상 메모리를 바라보고 가상 주소를 사용하며, MMU라는 별도의 메모리 관리 유닛이 가상 메모리와 실제 메인 메모리 사이를 왔다갔다 하면서 필요한 영역은 가상 메모리로부터 실제 메모리로 올려주고, 가상 주소를 물리 주소로 매핑해서 실제 메모리 영역에서 자원을 가져다주는 일을 수행함. 

유저나 프로세스는 실제 메모리 영역과 관리에 대한 복잡한 고민을 할 필요 없이 충분한 크기의 연속된 메모리를 할당받았다고 가정하고 프로그램 실행 가능. 메모리 영역에 대한 보호가 가능.

 

Block Mapping

사용자 프로그램을 block 단위로 분할하고 관리. 가상 메모리 시스템의 가장 기본적인 매핑 로직. 

V = (b,d) : 가상 주소 = (블록 번호, block 내 offset)

BMT Block Mapping Table  

address mapping 정보를 관리하는 테이블. 각 프로세스는 커널 공간에 하나의 BMT를 가짐.

block number, residence bit (블록이 메모리에 적재되었는지 아직 swap devicde에 있는지 판별 이진 비트), real address(실제 메모리 주소)로 구성됨

과정

1) 가상 주소 V의 b를 통해 블록 아이디를 추출.

2) BMT로 가서 해당 아이디의 블록의 residence bit를 보고 메모리에 적재되었는지 확인

3-1) residence bit=0이면 swap device에서 해당 블록을 메모리에 가져옴. BMT를 업데이트 하고 3-2) 과정 수행

3-2) residence bit=1이면 해당 블록의 real address 를 추출 (a)후 4) 과정 수행

4) real address 시작점인 a에 V의 offset 값인 d를 더해 (a+d) 실제 메모리 상의 주소를 찾아냄

 

 

프로그램의 크기를 쪼개는 방법에 따른 분류

1) paging

2) segmentation

3) hybrid 

* CPU가 가상 주소(Virtual Address)를 사용하다는 것 = CPU에서 프로세스가 사용하는 모든 주소, 우리가 *p(포인터)를 통해 확인하는 모든 주소는 죄다 Virtual Address라는 것

 

1. Paging system

프로그램을 같은 크기의 덩어리(page)로 분할

page : (가상 메모리 상에 있는) 프로그램을 특정 크기 K로 분할했을 때 분할된 덩어리를 지칭함.

page frame : 실제 메모리 영역을 page와 같은 크기로(K) 여러 덩어리를 분할했을 때 분할된 메모리 영역 덩어리

특징

- page를 논리적 단위가 아닌 크기에 따라 분할하기 때문에 페이지 공유 및 보호 과정이 복잡함

- 간단하고 효율적임

- 외부 단편화는 발생하지 않지만(page와 frame을 모두 같은 크기로 나눴기 때문에) 내부 단편화 발생 가능

V=(p,d) : 가상주소 = (페이지 번호, offset)

PMT Page Map Table

page number, residence bit, page frame number(메모리), swap device address(보조기억장치 주소)

PMT는 커널에 저장되며 PMT를 찾아갈 수 있는 base 주소가 주어짐.

 

Frame Table page frame의 각 frame 하나의 엔트리가 되는 page frame 관리 Table

page frame 번호, 프레임 영역이 할당(allocated)/사용가능(available) 여부 판별 항목, frame영역에 올라온 페이지 판별 PID 항목, 사용 가능한 빈 프레임 영역들을 연결한 free list header(AV)와 linked field (linked list 구조)

* page frame의 빈 공간을 찾아서 page를 할당하는 방법
Frame Table에서 AV가 가르키는 entry를 찾음. 엔트리의 allocated와 PID 값을 변경해주고 해당 엔트리의 page frame number를 통해 해당 frame 영역을 찾아가 page를 할당함. AV 포인터는 해당 entry의 linked field가 가르키는 다음 entry를 다시 가르키게 함.

 

page fault

찾고자 하는 page의 residence bit 가 0인 경우. 즉 해당 페이지를 swap device로부터 memeory로 가져오기 위한 I/O 요청이 필요. 실행중이던 프로세스가 waiting 상태로 전환되며 오버헤드가 발생. 즉 page fault 오버헤드를 줄이는 것이 중요하다.

 

address mapping 기법에 따른 분류

1) direct mapping

2) associative mapping

3) hybrid 

 

page sharing

여러 프로세스가 특정 page를 공유 가능.

보안을 위해 protection bit 사용 : Valid(메인 메모리 적재 여부), Read, Write, Execute 판별 이진 비트 사용

프로시져 page (code) 공유 유의사항 : function 등을 수행 중에 반복문이나 조건문 같은 분기점을 만나게되면 CPU는 가상 메모리 주소를 바탕으로 메모리 이동을 명령하기 때문에 프로그램들은 각각의 가상 메모리 주소 값으로 메모리를 점프하게 됨. 그러나 실제 메모리 영역은 같은 공간을 공유하고 있으므로, 서로 다른 값으로 요청해도 같은 공간을 가르켜 줘야하는 문제가 발생. 따라서 shared page 에 대한 정보는 PMT 상에서 같은 entry(page number가 동일하게)에 저장하게 함

data page 공유 유의사항 : R/W data는 concurrency 제어로 관리되어야 함

 

paging system - direct mapping

b= PMT의 base 주소, entrySize = PMT의 한 줄의 크기, pageSize = 페이지의 크기, V=(p,d) 를 가정

1) PMT에서 원하는 page 정보를 읽어오는 방법 = b + p * (entrySize)

2) page 정보를 읽어와 residence bit 판별 

3-1) 0일 경우(page fault) 해당 엔트리의 swap device address를 읽어와 메모리에 페이지 적재, PMT 갱신 후 3-2)수행

3-2) 1일 경우 해당 엔트리의 page frame number를 읽어와(pf) 4)수행

4) 메모리에 원하는 위치를 읽어오는 방법 = pf * pageSize + d 

단점

1) page를 찾기 위해 메모리 접근이 2번씩 필요함 (PMT 탐색 + 실제 메모리 탐색)

2) PMT를 위한 메모리 공간이 필요함

 

paging system - Associative mapping

TLB(Translation Look-aside Buffer)에 PMT를 적재

PMT를 병렬로 탐색하며 속도를 향상시켰고 PMT 탐색을 위한 메모리 접근을 없애 오버헤드를 줄임.

단점) TLB의 size에 제한이 있어 큰 PMT 관리가 어려움

 

paging system - hybrid (Direct/Associative) mapping

PMT는 메모리에 적재하고, 일부 entery만 TLB에 적재

적재할 entry 선택은 locality(지역성)를 활용함.  최근에 사용된 page와 인접한 영역을 함께 올린다.

 

2. segmentation
프로그램을 paging과 달리 동일한 크기가 아니라 논리적 block으로 분할함. (segment)

block의 크기가 서로 다를 수 있음.

ex) stack, heap, function 당 등등

특징

- 실제 메모리 영역을 미리 분할하지 않음. (segment에 따라 그때그때 알맞은 크기로 메모리 동적 분할)

- address mapping 및 메모리 관리의 overhead가 큼

- 논리적으로 분할되어있어 segment 공유 및 보호가 용이함

- 내부 단편화는 없지만 외부 단편화 발생

V=(s,d) : 가상주소 = (세그먼트 번호, offset)

SMT Segment Map Table

segment number, residence bit, segment address in memory(실제 메모리 주소), secondary storage address(보조기억장치 = 디스크 = swap device 상의 세그먼트 주소), segment length(segment 크기는 각기 다르므로), protection bit(논리적으로 분할했기 때문에 세그먼트 접근 권한을 애초에 세그먼트 테이블에 명시 가능)

 

Partition Table or State Table

세그먼트의 크기에 맞게 메모리 영역을 분할하고 적재시 사용하는 테이블(VPM과 유사)

partition number, start address, size, current process ID, segment number 등

 

segmentation system - direct mapping

b= SMT의 base 주소, entrySize = SMT의 한 줄의 크기, segSize = 페이지의 크기, V=(s,d) 를 가정

1) SMT에서 원하는 segment 정보를 읽어오는 방법 = b + s * (entrySize)

2) segment 정보를 읽어와 residence bit, segment overflow exception, segment protection exception 판별 

3-1) residence bit가 0일 경우(segment fault)

 해당 엔트리의 swap device address를 읽어와 메모리에 세그먼트 적재, SMT 갱신 후 3-2)부터 순차적 수행

3-2) offset d가 segment의 크기보다 큰 경우 (d>segSize) segment overflow exception 처리 모듈 호출

3-3) 허가되지 않은 연산일 경우 (protection bit 항목 검사) segment protection exception 처리 모듈 호출

4) 실제 메모리 주소를 계산해 원하는 위치를 읽어옴

 

3. hybrid paging/segmentation system

각 프로그램을 논리 단위로 자르고(segment), segment를 동일한 크기의 page로 자름(paging)

특징

 - 외부 단편화는 없지만 내부 단편화 발생 가능.

 - 페이징과 세그멘테이션의 장점만 취합(실제 메모리 할당/관리 overhead적음, 공유 및 보호 용이)

 - 전체 테이블 수 증가, address mapping 과정 복잡, direct mapping의 경우 메모리에 3번 접근 필요

   (SMT->PMT->메모리)

 

V = (s,p,d) : 가상주소 = (세그먼트 번호, 페이지 번호, offset)

SMT, PMT 모두 사용 - 프로세스 당 하나의 SMT, 세그먼트 당 하나의 PMT

*SMT에는 resisdence bit가 없음(실제 메모리에는 page가 올라가기 때문)

*SMT에는 segment address in memory 항목 대신 PMT address 항목이 들어감

메모리 관리는 paging 시스템과 유사함 (실제 메모리에는 최말단 단위로 나뉜 page가 적재)

 

virtual memory 성능 최적화

1. H/W 서포트

1) TLB(Translation Look-aside Buffer) 주소 변환 장치를 통한 연관 메모리 관리

2) Bit Vector : page 사용 정보를 기록하는 비트

 - reference bit (used bit) : 페이지 참조 기록, 최근 참조를 표현하기 위해 주기적으로 초기화 

 - update bit(modified/write/dirty bit) : page가 메모리에 적재된 후 프로세스에 의해 값이 수정되었는지 기록

 최종적으로 디스크 상의 페이지에 변경된 값을 반영(write-back) 해주기 위해 사용.

 

2. S/W 서포트 알고리즘

1) Allocation : 메모리를 얼마나(page frame의 개수) 할당할 것인가 (크기 고민)

 - Fixed : 고정된 할당. 프로세스 생성 시점에 정해짐

 - Variable : 가변 할당. 프로세스 실행동안 유동적으로 할당

2) Fetch : 메모리에 언제 적재할 것인가 (시점 고민)

 - Demand : 프로세스가 요구할 때 요구하는 페이지 적재. page fault 오버헤드가 높음 (현실적으로 사용)

 - Pre-fetch : 참조될 가능성이 높은 페이지를 미리 적재. page fault 오버헤드는 적지만 예측을 위한 오버헤드 발생. hit-ratio에 민감하고 현실성이 낮음.

3) Placement : 메모리의 어디에 적재할 것인가 (위치 고민)

paging기법에서는 page와 page frame이 동일하게 정해져있기 때문에 고민이 불필요. segment에서 중요함.

First-fit, Best-fit, Worst-fit, Next-fit 등의 기법

4) Replacement : 메모리 영역이 다 사용중인데 새로운 영역을 요구할 때 어떤 page와 교체 할 것인가 (교체 고민)

5) Cleaning : 디스크에 언제 Wirte-back 할 것인가 (반영 고민)

 - Demand : page가 메모리에서 내려갈 때(page swap 발생 또는 해당 프로세스 종료시) 

 - Pre : 더이상 변경 가능성이 없다고 판단되었을 때 미리 (페이지 교체시 오버헤드를 줄일 수 있음)

6) Load Control : multi-programming degree를 어느정도로 할 것인가(부하 조절 고민)

 - 저부하 : 시스템 자원 낭비

 - 고부하 : 자원 경재 심화, Thrasing 발생 가능(page fault 증가)

 

Replacement 기법 심화

page swapping 에 대한 알고리즘, Locality를 고려하는 게 좋다

1) Min(OPT) : reference string을 이미 알고 있으며 앞으로 가장 오래 참조되지 않을 페이지를 교체. 사실상 미래 예측이 불가능하기 때문에 실제 사용은 불가능하지만, 다른 알고리즘의 성능 평가 기준으로 사용.   

2) Random : 무작위 교체. 교체 대상을 선택할 때의 오버헤드가 없다. 실 사용보단 성능 평가 기준으로 사용.

3) FIFO : 메모리에 가장 처음에 적재된 페이지부터 내보냄.

 - page 적재 시점을 기록해야 함.

 - locality에 대한 고려가 없어서 page fault 오버헤드가 높음

 - FIFO Anomaly가 발생 할 수 있다. (page frame 수를 늘려줬는데 오히려 page fault가 더 많이 발생함)

4) LRU(Least Recently Used) : 가장 오랫동안 참조되지 않은 페이지 교체

 - locality 중 시간 지역성을 고려했으며 최적 알고리즘과 가장 근접한 성능

 - page 참조 시점을 기록해야 함.

 - 특정 반복 조건에서 Loop의 크기보다 적은 수의 page frame할당 시 page fault가 급증하기도 함

5) LFU(Least Frequently Used) : LRU의 변화 버전. 가장 참조 횟수가 적은 페이지 교체

 - locality 고려.

 - 참조 횟수를 누적해 기록해야 하지만, 참조 시간을 기록하는 것 보다는 오버헤드가 적다

6) NUR (Not Used Recently) : 사용된지 가장 오래된 페이지 교체

 - LRU보다 적은 오버헤드로 비슷한 성능을 달성하기 위함

 - 참조시점을 기록하지 않고 bit Vector의 reference bit와 update bit를 살핌

 - (refer bit, update bit) 교체 우선순위 (0,0), (0,1), (1,0) (1,1)

7) Clock : NUR기법 기반, reference bit만 체크

 - 마치 시계 바늘처럼 기준점이 돌아가면서 페이지를 가르키고 해당 페이지의 reference bit 값을 변경해주며 교체할 페이지를 찾아냄

8) Second Chance : Clock 알고리즘에 update bit도 함께 고려한 버전

 - (0,0) 교체할 페이지 / (0,1) : write-back 리스트에 해당 페이지를 추가하고 (0,0)으로 변경한 뒤 다음으로 넘어감

 (1,0) : (0,0)으로 변경한 뒤 다음으로 넘어감 / (1,1) : (0,1)으로 변경한 뒤 다음으로 넘어감 

 

3. 그 외 고려사항

1) page size : 페이지의 사이즈를 어떻게 할 것인가

- 작은 경우 : page frame수가 많아지며 page table의 크기 증가. 내부 단편화 감소.

 잘게 나뉜 여러 페이지를 가져와야 하므로 I/O시간 증가, page fault 증가

- 큰 경우 : page frame 수가 적어지므로 page table의 크기 감소. 내부 단편화 증가.

 page fault가 상대적으로 적게 일어남.

* page 크기는 증가하는 추세! 이유는?

 H/W발전 경향을 보면 CPU성능이 디스크에 비해 가파르게 향상됨. 즉, I/O 병목현상이 커지면서 page fault 발생 시 성능저하가 커짐. 따라서 page fault 를 최소하는 것이 성능 향상에 도움이 됨 + TLB reach 향상 가능 

 2) TLB Reach  : TLB를 통해 접근 가능한 메모리의 양 = TLB 엔트리 개수 * page 사이즈

 - TLB의 엔트리 수를 늘리거나(TLB크기 증가, 비용이 큼), 페이지 사이즈를 증가시켜서 향상 가능

 

 

[파일 시스템 관련]