treecode

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소 (실제 사용 영역은 제한적)
  • Memory 사용량 감소
  • 빠른 응답 시간 (의미 있는 것을 더 올려놓기 때문)

페이지 테이블에는 valid-invalid bit가 있는데 물리 메모리에 페이지가 올라와 있는지를 체크해주는 역할을 한다. 물리 메모리 오른쪽의 그림은 swap area로 사용되지 않는 페이지를 backing store(Disk)에 두는 것인데 요청한 페이지가 물리 메모리에 없을 경우 Page Fault가 발생하고 swap area에서 페이지를 읽어온다.

page fault가 발생하면 MMU(메모리 주소 변환을 해주는 하드웨어)는 trap을 발생시키는데 이때 CPU가 현재 프로세스에서 운영체제로 넘어가고 page fault handler가 동작한다 .

page fault handler는 먼저 정상적인 메모리 요청인지 확인을 한 뒤 물리 메모리의 비어 있는 페이지 프레임을 찾고 없으면 replace 작업을 한다.

DIsk I/O 작업은 비교적 굉장히 오래 걸리기 때문에 프로세스를 block 상태로 만들고 I/O 작업이 끝나면 Invalid bit를 valid로 바꾸고 프로세스를 Ready Queue에 넣는다.

페이지 교체 알고리즘 (Replace Algorithm)

• Optimal Algorithm
  • 가장 먼 미래에 참조되는 페이지를 쫓아내는데 사실상 미래를 예측하기 어려워서 비현실적
  • 이상적인 케이스를 통해 다른 알고리즘과의 성능 비교를 위해 사용(upper bound)
• FIFO
  • FIFO Anomaly : 메모리 크기를 늘리면 page fault가 오히려 증가할 수 있다
• LRU (Least Recently Used)
  • 가장 오래전에 사용된 것을 교체 (들어온 것 기준 x)
  • 과거에 많이 참조가 되었더라도 가장 오래 전에 사용이 됐으면 교체가 되는 단점
  • 링크드 리스트로 구현을 해서 교체 시간 O(1)
• LFU (Least Frequently Used)
  • 참조 횟수가 가장 적은 페이지를 지움
  • 이제 막 참조가 시작된 페이지가 교체되어버리는 경우가 생기는 단점
  • heap 구조 O(log n)

가상 메모리 페이징 기법에서는 LRU, LFU 같은 알고리즘 적용이 어렵다. 왜냐하면 메모리 주소 변환 작업을 운영체제가 관여하지 않아서 언제 어떤 페이지가 참조되었고 얼마나 참조 되었는지 이런 부분을 체크하기 어렵기 때문이다.

Clock Algorithm

• 최근에 페이지가 참조가 되면 reference bit를 1로 설정 (하드웨어가 함)
• 운영체제는 reference bit가 1이면 0으로 바꾸고 그 다음 페이지 비트 검사
• reference bit가 0인 페이지를 만나면 교체
• 가장 오래 전에 참조된 페이지를 교체하진 않지만 LRU와 어느정도 비슷한 효과
• modified bit : 최근에 페이지가 변경되었는지 확인
• modified bit가 0이면 그냥 메모리에서 지우면 되는데 modified bit가 1이면 변경(write)이 있다는 것이므로 디스크에 수정된 내용을 반영

Thrashing

동시에 실행되는 프로그램이 증가하면 프로세스마다 할당되는 메모리가 부족해지고 최소한의 page frame을 할당받지 못해서 Page Fault가 증가하게 된다. 그러면 Disk I/O 작업으로 인해 CPU 이용률이 떨어지게 되는데 이때 운영체제는 CPU 이용률이 부족한 것을 멀티프로그래밍 개수를 늘려야겠다고 판단하는데 이러한 현상을 Thrashing이라 한다.

멀티 프로그래밍 개수를 조절하기 위해 Working-Set 모델이 있는데 working-set이란 특정 시간에 집중적으로 참조되는 page들의 집합으로 프로세스가 일정 시간동안 원활하게 수행되기 위해서 해당 페이지 집합을 전부 메모리에 올리는 것을 말한다. working-set이 보장이 안 되면 모든 프레임을 반납하고 swap-out(suspend) 시켜서 thrashing 현상을 방지할 수 있다.

페이지 단위가 너무 작으면 내부 단편화를 방지할 수 있지만 페이지 테이블 크기가 증가하고 Page Fault로 인한 Disk I/O가 많이 발생한다. 반면 페이지 단위가 클 경우 내부 단편화와 transfer 시간이 오래 걸리고 필요없는 정보까지 메모리에 올라오는 단점이 있다.

[참고]

프로세스와 스레드

프로세스는 실행 중인 프로그램으로 디스크로부터 메모리에 적재되어 CPU를 할당 받으며 프로그램을 실행한다. 운영체제로부터 주소 공간, 메모리 등을 할당 받으며 운영체제는 프로세스를 관리하기 위해 프로세스마다 PCB(Process Control Block)를 생성하는데 프로세스 전환시 필요한 정보들을 저장해둔다.

스레드는 프로세스의 실행 단위(CPU 수행 단위)로 하나의 프로세스 내에는 여러 개의 스레드를 생성할 수 있다.

스레드는 프로세스의 Code, Data 영역, OS 자원과 같은 공통 자원을 공유하면서 독립적으로는 Stack 영역과 PCB에 현재 코드의 어느 부분을 실행하고 있는지를 가르키는 PC(Program Counter), 레지스터 값들을 가지고 있는다.

프로세스의 공통 자원 공유를 통해 여러 개의 프로세스를 생성하지 않고 자원을 효율적으로 사용할 수 있으며 프로세스 컨텍스트 스위칭에 비해 오버 헤드가 줄어든다. (프로세스 간 컨텍스트 스위칭과 달리 캐시 메모리를 비울 필요가 없다.)

멀티 스레드는 프로세스 내의 공간을 공유하고 Heap 영역을 통해 스레드 간에 데이터도 주고 받을 수 있어 프로세스 간에 통신보다 훨씬 간단하다. 하지만 여러 스레드가 하나의 프로세스 공간을 공유하기 때문에 다른 스레드에서 사용중인 변수나 자료구조에 접근해서 문제를 일으킬 수가 있다. 그래서 동기화 작업을 통해 작업 처리 순서와 공유 자원에 대한 접근을 컨트롤해야 되는데 이 경우에도 과도한 제한으로 인해 병목 현상의 위험이 있다. 그리고 하나의 스레드에 문제가 발생할 경우 위험이 전파되는 등의 단점도 있기 때문에 멀티 프로세스 방식과 상황에 따라 적합한 방식을 사용해야 한다.

 프로세스란 실행중인 프로그램을 말하며, 프로세스의 문맥(Context)을 아는 것이 중요하다. 여러 개의 프로세스들이 번갈아 실행이 되기 때문에 문맥 정보를 기억해두지 않으면 이어서 실행할 수 없기 때문이다.

프로세스의 문맥을 나타내는 정보는 CPU의 PC(Program Counter)와 각종 레지스터, 프로세스의 주소 공간, 그리고 운영체제 커널에 생성되는 해당 프로세스의 PCB(Process Control Block)와 커널 스택이 있다.

CPU의 PC는 해당 프로세스의 code 공간에 다음 실행할 명령어의 주소를 담고 있고커널 주소 공간은 프로세스들이 공유하기 때문에 프로세스별로 data영역에 PCB, 스택 영역에 프로세스별 스택을 생성한다.

프로세스의 상태는 다음과 같이 나뉜다.

NEW(생성 중)

RUNNING(CPU를 잡고 명령 수행 중)

READY(CPU 대기 상태)

BLOCKED(CPU가 있어도 명령을 수행할 수 없는 상태)

TERMINATED(처리가 끝난 상태)

SUSPENDED (외부적인 이유로 프로세스 수행이 정지된 상태)

프로세스 스케줄링 큐

프로세스는 준비 상태가 되면 READY 큐에 들어가서 CPU를 받아 처리를 하고 이때는 RUNNING 상태가 되고 이후 타이머 인터럽트에 의해 다시 READY 상태가 되거나 입출력 요청시 BLOCKED 상태가 되며 Device 큐에 들어간다.

여기서 프로세스 상태와 큐 공간은 운영체제가 프로세스를 스케줄링 하기 위해 Data 영역에 큐를 만들어놓고 프로세스 상태를 바꾸어가며 처리를 한다. (실제 큐는 우선 순위 큐처럼 우선 순위가 있다)

운영체제는 data 영역에 프로세스별로 PCB를 생성해서 보관한다 했는데 위에서 말한 프로세스의 상태, 스케줄링 정보, 우선순위, 프로세스의 문맥 정보, CPU 관련 PC, 레지스터 값 등을 구조체로 보관하고 있는다.

그래서 운영체제는 CPU를 현재 프로세스에서 다른 프로세스로 넘겨줄 때 현재 프로세스의 PCB에 상태를 저장하고 다음 프로세스의 상태를 PCB에서 읽어오는데 이를 문맥 교환(Context Switching)이라 한다.

시스템 콜이나 인터럽트가 발생해도 프로세스가 바뀌지 않으면 컨텍스트 스위칭이 발생하지 않는데 이 경우는 컨텍스트 스위칭은 아니지만 운영체제에게 CPU가 넘어가면서 PCB에 save가 된다. 하지만 컨텍스트 스위칭(캐시 메모리를 flush하는 등)에 비하면 추가 오버헤드가 적은 편이다.

프로세스 스케줄링에는 장기, 단기, 중기가 있는데 먼저 단기 스케줄러(Short term, CPU Scheduler)는 다음 번에 어떤 프로세스를 running시킬지 결정하고 프로세스에 CPU를 주는 문제를 담당한다.

장기 스케줄러(Long term, job scheduler)는 시작 프로세스중 어떤 것을 Ready 큐로 보낼지 결정하며 메모리에 올라가있는 프로세스의 수(degree of Multiprogramming)를 제어하는 방식으로 시분할 시스템에서는 보통 장기 스케줄러를 사용하지 않고 중기 스케줄러를 사용한다. 중기 스케줄러(Medium term, Swapper)는 일단 프로세스가 시작되면 메모리를 할당하고 너무 많은 프로그램이 올라가면 일부를 메모리를 뺏는 방식으로 프로세스의 수를 제어한다. 이때 프로세스 상태를 SUSPENDED라고 하며 프로세스가 통째로 디스크에 swap oup 되는데 이 외에 사용자가 프로그램을 정지시킨 경우도 SUSPENDED에 해당된다.

(BlOCKED는 자신이 요청한 event가 만족되면 READY, SUSPENDED는 외부에서 resume 해주어야 Active)

운영체제를 공부하기에 앞서 컴퓨터 시스템 구조를 보면 이전에 PC 조립을 통해 보았듯 메인 보드 위에 CPU, RAM, SSD, I/O 포트등이 있다. 운영체제는 이러한 컴퓨터 하드웨어 바로 위에 설치되어 하드웨어 소프트웨어 사이에서 컴퓨터의 자원(CPU, 메모리, 입출력 장치 등)을 효율적으로 관리하는 역할을 한다. (CPU 스케줄링, 메모리 관리, 인터럽트 입출력 관리, 프로세스 관리 등)

각각의 디스크, I/O 장치들에는 메인 CPU와 메모리처럼 이를 전담하는 device controller와 작업 공간인 local buffer가 있고 CPU에는 register, Interrupt line, mode bit이 붙어있다. 

먼저 레지스터는 CPU의 내부 메모리중 하나로 내부 메모리는 레지스터와 캐시 메모리인 L1, L2, (L3)으로 구성 되어 있는데 메인 메모리(RAM)가 HDD, SSD에 비해 아무리 빠르다고 해도 CPU와 속도 차이가 심하기 때문에 효율적으로 처리하기 위해 CPU 내부에 임시 메모리 저장소가 있는 것이다. (레지스터는 주로 연산 결과를 기억하는 용도)

CPU는 매우 빠르게 메인 메모리로부터 입력을 처리하는데만 집중을 하는데 입출력 처리 같은 경우는 CPU가 기다리기에 너무 비효율적이라 입출력이 되는 동안 다른 프로그램으로 넘어가 명령을 처리한다. 입출력 요청을 받으면 device controller는 입출력을 처리하는데 이후 interrupt line에 인터럽트가 전달(DMA Controller)되어 처리가 끝났다는 것을 알리는데 인터럽트가 들어오면 CPU 제어권이 운영체제에 넘어오면서 운영체제는 CPU를 넘겨 받고 인터럽트 처리를 한다.

운영체제가 프로그램에 CPU를 넘겨주고 받는 등의 처리를 하지만 다른 프로그램에 CPU를 넘겨주면 다시 강제로 받아올 수가 없기 때문에 CPU가 묶이는 상황(무한 루프 등)이 발생할 수 있다. 그래서 또 다른 하드웨어 요소인 타이머를 사용해 시간 제한을 걸어두고 초과가 되면 타이머 인터럽트에 의해 CPU 제어권이 다시 운영체제에 돌아가도록 한다. 이렇게 타이머 인터럽트에 의해 강제로 반납되는 것 외에도 사용자 프로그램은 직접 입출력을 받아오거나 할 수 없기 때문에 운영체제에 입출력 요청을 하고 CPU를 반납한다. 이를 시스템 콜이라 하며 일반적으로 디바이스 컨트롤러에서 발생하는 하드웨어적 인터럽트와 달리 트랩(소프트웨어적 인터럽트)이라고 한다.

운영체제에는 다양한 인터럽트에 따라 처리하는 인터럽트 처리 루틴이 있고 인터럽트를 처리하는 함수인 인터럽트 처리 루틴의 주소를 가지는 인터럽트 벡터가 있다.

운영체제와 사용자 프로그램은 이렇게 처리할 수 있는 권한에도 차이가 있기 때문에 보호 장치인 mode bit가 존재하는데 사용자 프로그램을 수행하는 사용자 모드(1)과 OS 코드를 수행하는 모니터 모드(0)로 계속 전환하면서 처리를 한다. (인터럽트 발생시 mode bit가 0으로, 사용자 프로그램에 cpu를 넘기기 전 1로 셋팅하는 등)

그리고 CPU에 인터럽트가 너무 걸려도 비효율적이기 때문에 DMA(Direct Memory Access) 컨트롤러가 존재하는데 DMA 컨트롤러는 입출력 처리가 끝나면 로컬 버퍼의 데이터를 메인 메모리에 복사하고 CPU에 인터럽트를 한번만 걸어서 요청한다.