가상메모리 요구페이징(demand paging)

지금까지의 메모라 관리 기법 방식은 프로세스 전체가 메모리 내에 올라와야 한다는 것을 전제로 하고 있다.

프로세스 전체가 메모리 내에 올라오지 않더라고 실행히 가능하도록 하는 기법을 가상메모리라고 한다.

가상메모리는 물리 메로리로부터 사용자 관점의 논리 메모리를 분리시켜 주 메모리를 균인한 크기의 저장 공간으로 구성된 엄청나게 큰 배열로 추상화 시켜준다.

따라서 작은 메모리를 가지고도 큰 가상 주소 공간을 제공한다.

 

• 장점

  • 사용자 프로그램이 물리 메모리보다 커져도 된다. 즉, 메모리 크기의 제약으로부터 자유로워진다.
  • 각 사용자 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있다. 이에 따라 응답시간은 늘어나지 않으면서 CPU 이용률과 처리율이 높아진다.
  • 프로그램을 메모리에 올리고 스왑하는데 필요한 입/출력 횟수가 줄어든다. 따라서 프로그램들이 보다 빨리 실행된다.
  • 가상메모리 파일의 공유를 쉽게 해주고 공유 메모리 구현을 가능하게 한다.
  • 프로세스 생성을 효율적으로 처리할 수 있는 메커니즘도 제공한다.

• 단점

  • 구현이 어렵고, 잘못 사용시 성능이 현저히 저하될 수 있다.

요구페이징

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

 

요구페이징은 일부 스와핑 기법과 유사하다. 프로세스를 실행하고 싶으면 메모리로 읽어 들이며 이때 전체 프로세스를 읽어오지 않고 lazy swapper를 사용한다. lazy swapper는 그 페이지가 필요하지 않는 한 메모리에 적재 되지 않는다.

 

스와퍼는 전체 프로세스를 관리하지만 페이저(pager)는 프로세스 내의 개별 페이지들을 관리한다. 요구 페이징과 관련해서는 스와퍼보다 페이저가 더욱 가깝다.

 

swap in 시 페이저는 프로세스가 다시 swap out되기 전에 실제로 사용 될 페이지들이 어떤 것인지 추측한다. 페이저는 프로세스 전체를 스왑인 하는 대신에 실제 피룡한 페이지들만 메모리로 읽어온다. 사용되지 않을 페이지를 메모리로 가져오지 않음으로써 시간 낭비와 메모리 공간 낭비를 줄일 수 있다.

 

페이저는 어느 페이지가 디스크에만 있고 어느 페이지가 메모리에 올라와 있는지 구별할 수 있어야 한다. 이대 유효/무효 비트 기법을 사용하여 비트가 유효하면 메모리에 있는 것을 의미하고 유효하지 않으면 메모리에 없거나(디스크에 있거나) 해당 페이지가 유효하지 않다는 것이다.

 

프로세스가 메모리에 없는 페이지를 접근하려 할 때 페이지 부재 트랩(page-fault-trap)을 발생시킨다. 페이징 하드웨어는 페이지 테이블을 이용한 주소 변환 과정에 무효 비트를 발견하고 운영체제에 트랩을 건다.

 

 

페이지 부재를 처리하는 과정

1. 프로세스에 대한 내부테이블을 검사해서 그 메모리 참조가 유효/무효 인지 알아 낸다.
2. 무효한 페이지에 대한 참조라면 프로세스는 중단된다. 유효한 참조인 경우 메모리에 없으면 디스크로부터 가져와야 한다.
3. 빈 공간, 자유 프레임(free frame)을 찾는다.
4. 디스크에 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청
5. 디스크 읽기가 끝나면 이 페이지가 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며 프로세스가 유지되고 있는 내부테이블을 수정한다.
6. 트랩에 의해 중단되었던 명령을 다시 수행하며 프로세스는 그 페이지가 항상 메모리에 있엇던 것처럼 간주하여 해당 페이지를 접근할 수 있다.

페이지가 적재되고 나면 프로세스는 수행을 계속 하는데 프로세스가 사용하는 모든 페이지가 메모리에 올라올 때 까지 필요할 때마다 페이지 부재가 발생 한다. 일단 필요한 모든 페이지가 적재되고 나면 더 이상 부재 오류가 발생하지 않는데 이것이 순수 요구 페이징(pure deman paging)이다.

 

모든 프로그램은 참조의 지역성(locality of reference)이라는 성질이 있어서 프로그램의 어느 한 특정 작은 부분만 한 동안 집중적으로 참조하는데 이러한 성질 때문에 요구 페이징은 만족할 만한 성능을 보인다.

locality of reference 참조 지역성

동일한 값 또는 해당 값에 관계뗀 스토리지 위치가 자주 액세스 되는 특성.
참조지역성의 3가지 기본형 : 시간, 공간, 순차 지역성

1) 공간(spatial) 지역성 : 특성 클러스터들의 기억 장소들에 대해 참조가 집중적으로 이루어지는 경향으로, 참조된 메모리의 근처의 메모리를 참조.

2) 시간(temporal) 지역성 : 최근 사용되었던 기옥 장소들이 집중적으로 액세스 되는 경향으로, 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높다.

3) 순차(sequential) 지역성 : 데이터가 순차적ㅇ로 액세스 되는 경향. 프로그램 내의 명령어가 순차적으로 구성되어있다는 것이 대표적인 경우.

 

요구 페이징의 필수적인 요구 사항은 페이지 부재 오류 처리 후에 명령 처리를 다시 시작할 수 있어야 한다.

만약 페이지 부재가 명령 인출(instruction fetch)시에 발생 했다면 명령을 메모리로 읽어 온 후 다시 수행을 시도하면 된다.

 

요구 페이징은 컴퓨터 시스템의 성능에 중요한 영향을 미친다. 페이지 부재가 발생하지 않는 한 실질 접근 시간은 메모리 접근 시간과 같다. 그러나 페이지 부재가 발생하면 디스크로부터 관련되는 페이지를 읽어 온 뒤 필요한 워드를 접근해야 한다.

 

요구 페이징의 또 다른 특성은 스왑 공간의 관리이다. 스왑 공간에서의 디스크 입/출력은 일반적으로 파일 시스템에서의 입/출력보다 빠른데 그 이유는 스왑 공간은 파일 시스템보다 더 큰 블록을 사용하기 때문이고 또 스왑 공간과 입/출력을 할 때는 파일 찾기(lookup)나 간접 할당 방법 등은 사용하지 않기 때문이다.

 

Operating System

 

프로세스 동기화

---

동기화(Synchronization)

• 동기화의 필요성

은행의 1000원의 잔고가 남아있다고 가정하자.

내가 500원을 찾는 순간 동시에 어머니가 500원을 송금해 오셨다면? 우리는 1000원의 잔고를 예상한다.

Process A : incoming
Register1 = Balance
Register1 = Register1 + 500
Balance = Register1

Process B : outgoing
Register2 = Balance
Register2 = Register2 - 500
Balance = Register2

T0: Process A  Register1 = Balance										R1 = 1000
T1: Process A  Register1 = Register1 + 500						R1 = 1500
T2: Process B  Register2 = Balance										R2 = 1000
T3: Process B  Register2 = Register2 - 500						R2 = 500
T4: Process A  Balance = Register1										B = 1500
T5: Process B  Balance = Register2										B = 500

어떠한 데이터에 대해 동시 작업이 일어났을 경우 처리순서에 상관없이 원하는 결과값을 얻기 위해 동기화가 필요하다.

동기화의 목적은 Data Consistency(데이터 일관성)을 보장해주는 것이다.

 

유저 동기화는 critical section

커널 동기화는 mutex / semaphore

 

Critical Section

멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역.

임계구역은 시간이 지나면 종료되며, 어떤 프로세스가 임계구역에 접근하기 위해서는 지정된 시간만큼 대기해야 한다.

이때 쓰레드나 프로세스가 배타적인 사용권을 보장받기 위해 세마포어 같은 동기화 메커니즘이 사용된다.

한 프로세스 내의 쓰레드 사이에서만 동기화가 가능. 유저 객체(커널에서 제공하는 객체가 아니다.)

 

임계구역 문제를 해결하기 위한 3가지 조건

1. Mutual Exclusion(상호배제) : 임계구역에는 무조건 하나의 프로세스
2. Progress(진행) : 임계구역이 비었으면 어느 프로세스가 들어갈지 적절히 선택한다
3. Bounded Waiting(한정 대기) : 기아 상태를 방지하기 위해, 한 번 들어갔다 나온 프로세스는 다음에 들어갈때 제한을 준다.

 

동기화 방법

 

상호배제 (MUUual EXclusion)  뮤텍스.

공유데이터가 하나의 프로세스에 의해 독점적으로 사용되는 원칙

entry section
		
		critical section
		
exit section

프로세스는 critical section에 들어가기 전에 entry section 단계에서 출입을 허가받아야한다.

critical section 오직 하나의 프로세스만 존재하도록 한다.

동시프로그래밍 환경(멀티 프로세스 및 멀티 쓰레드 같은)에서 공유 불가능한 자원 처리 (critical section과 구분)

DB의 프로그램에서는 자동적인 부가기능으로 지원되지만, OS의 경우는 사용자의 요구에 따라 지원된다.

장점 혼란이없고 간단하다.

단점 read/write 두 처리 모두 대기한다.

write는 대기하는게 맞지만, read는 데이터를 변화시키지 않으므로 상관없다.

하지만 상호배제는 read도 대기해야한다.

→ 해결법

kernel자체가 하나의 커더란 critical section의 역할을 하는 것.

[Spin lock]

0 : critical section가 비어있다. 사용 가능 .

1 : critical section안에 다른 프로세스가 들어와 있는것.

Spin lock이 1일 경우 다음 수행을 기다리는 프로세스는 lock을 계속 돌게된다.

exit section에 의해 프로세스가 처리되었는지를 인식해 spin lock을 조정한다.

장점 : "조금만 기다리면 바로 쓸 수 있는데 굳치 context switching을 해서 부하를 줄 필요가 있나?"

스핀락을 잘 사용하면 context switching을 줄여 효율을 높일 수 있다.

 

[Sleep lock] — 세마포어

lock이 1일 경우 기다리던 프로세스는 sleep을 하게 되는 것.

critical section내에 프로세스의 작업이 끝나게 되면 sleep중인 프로세스를 깨워 처리하게 된다.

 

—두개의 차이

프로세스가 exit section에 도착했을때.

spin lock은 lock으로 접근해 1로 바꾼다 : waiting process가 항시 대기하며 값이 바뀌기를 기다리고 있으므로 lock만 바꿔주면 된다.

sleep lock은 sleeping process를 깨운다.

 

But, 동시에 2개 이상의 프로세스가 접근하면 상호배제 불가.

A와 B가 동시에 접근해서 lock 이 0인걸 확인했다.

A는 0을 1로 바꿨고, B는 read만 수행하고 context switching이 발생했다.

B는 다음 작업이 수행하게 될때 이미 read 했기때문에, 다시 확인하지 않고(A가 1로 바꿔놨는데 0인줄 알고) 데이터에 접근한다.

해결방법 : read/write를 하나의 명령어로 만들어 놓는다.

 

피터슨의 알고리즘

상호배제를 위한 병렬프로그래밍 알고리즘.

do{
  flag[me] = true; //임계 구역 사용을 원함 
  turn =! me; //me 프로세스의 차례가 아님 
  while(flag[me]&&turn =! me); //me 프로세스가 사용을 원하지만, 턴은 아니면 대기  
  **critical section**
  flag[me]=false; //임계구역 사용이 끝나면 폴스로 바꿔준다. 
  **remainder section**
} while(true);

그러나 프로세스가 많이 몰리면 계속 while문을 대기해야 하는데 이를 busy waiting(바쁜 대기)상태라고 부른다.

 

세마포어(Semaphore)

critical section, mutex는 동기화에 있어서 동시에 하나의 쓰레드만 실행되게 하지만, 세마포어는 지정된 수만큼의 쓰레드가 동시에 실행되도록 동기화하는 것이 가능.

• 임계구역에 들어가기 전 스위치를 사용중으로 놓고 들어간다.

• 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠때까지 기다린다.

• 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.

• 임계구역이 잠겼는지 직접 점검하건, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

• 세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up신호를 받으면 큐에서 나와 임계구여에 진입.

• 함수 P는 임계구역 들어가기전에 수행 / V는 나올때 수행

• 2개의 공유자원을 가지고 3개의 프로세스가 작업할 때 (Rs=2;)

  1. 프로세스 P1은 RS 값을 1 감소시키고 임계구역에 진입한다.
  2. 프로세스 P2도 RS 값을 1 감소시키고 임계구역에 진입한다.
  3. P3은 RS가 0이므로 대기.
  4. P1이 작업을 마치고 V()를 실행하면 RS값은 1이 되고 wake_up신호가 프로세스 P3에게 전달
  5. P3 임계구역 진입

• 문제점

  세마포어를 잘못 사용하면 임계구역을 보호할 수 없다.

  (1) P() - P() : wake_up신호가 발생하지 않아 무한대기에 빠진다.

  (2) V() - P() : 상호배제가 보장되지 않는 경우

   

MUTEX vs Semaphore

세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다. 뮤텍스는 상태가 0,1 뿐인 binary 세마포어

세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 진다.

뮤텍스는 1개만 동기화가 되지만 세마포어는 하나 이상의 동기화를 할 수 있다.

 

ex ) 변기가 3개가 있는 화장실에서

각각의 변기 앞에 3줄로 줄을 선다 —> 뮤텍스

화장실 문 앞에 한줄로 줄을 선다 —> 세마포어

 

데드락(DeadLock: 교착상태)

프로세스들이 서로 작업을 진행하지 못하고 영원히 대기상태로 빠지는 현상.

프로세스 사이에 할당된 자원의 충돌로 인하여 발생하게 된다.

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태.

cf) starvation - OS가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

교착상태 - 자연적으로 일어나는 문제

 

데드락은 한 시스템 내에서 다음의 네가지 조건이 동시에 성립할 때 발생한다.

아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 교착 상태를 해결할 수 있다.

• 상호배제 (Mutual exclusion)

  한 번에 한 프로세스만 사용 가능

• 점유대기(Hold and wait)

  최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

• 비선점(No preemption)

  빼앗을 수 없다.

• 순환대기(Circular wait)

  프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

 

데드락 처리

1. 예방

   교착상태 발생조건 중 하나를 제거하면서 해결 -> 자원 낭비가 심하다

2. 회피

   은행원 알고리즘

   • 프로세스가 자원을 요구할 때 , 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피.
   • 안정상태면 자원 할당, 아니면 다른 프로세스들이 자언을 해지할때까지 대기.

 

식사하는 철학자 문제

철학자가 스테이크를 먹기 위해 양옆의 포크를 동시에 들어야한다.

해결책

• n명이 앉을 수 있는 테이블에서 철학자를 n-1명 앉힌다.
• 한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용
• 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용

 

 

—> Synchronization을 구현하는 것은 사용자의 필요성에 의해 각자에게 맡겨진 것이다.

어떠한 1명이 실수로 잘못 구현하면 심각한 문제 발생. —> 해결방안 : 모니터

 

모니터

• 시스템 호출과 같은 개념. 인터페이스만 제공한다
• 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
• 모니터는 요청받은 작업을 모니터 큐에 저장한후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.
• 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고, 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.