잡지식창고

페이징은 작업을 크기가 동일한 페이지로 나누어 처리하는 방법이다.

프로세스를 동일한 크기의 페이지로 나누고, 메인 메모리도 프레임이라는 고정 크기 블록으로 나누어 프레임에 페이지를 적재한다.

페이지의 크기가 작을 수록 내부 단편화로 인한 용량 낭비를 줄일 수 있지만, 페이지 테이블을 유지하는데 부담이 커진다.

페이지 테이블은 논리적 주소를 물리적 주소로 변환한다. 페이지 테이블은 페이지의 논리적 주소인 페이지 번호와 이에 대응하는 물리적 주소인 페이지 프레임 주소를 포함한다.

페이지 테이블에서 연관 레지스터를 이용해 주소를 변환하는 방법은 세가지가 있다.

1. 직접 매핑
2. 연관 매핑
3. 연관-직접 매핑

직접 매핑

연관 매핑

연관-직접 매핑

메모리에 프로세스를 적재할 때 연속적으로 적재하는 방법이 연속 메모리 할당이다.

이는 초기 컴퓨터 시스템에서 많이 사용하던 방법으로, 단일 프로그래밍 환경과 다중 프로그래밍 환경으로 구분할 수 있다.

단일 프로그래밍 환경에서의 연속 메모리 할당

초기 컴퓨터 시스템에서는 한명의 사용자만 컴퓨터를 사용할 수 있었고, 자원도 한명의 사용자만 사용 가능했다.

프로그램은 메모리보다 클 수 없고 직접 배치 과정을 수행하여 항상 같은 메모리 위치에 적재되었다.

단일 프로그래밍 환경에서 연속 메모리 할당은 메모리를 사용자 영역과 운영체제 상주 영역으로 나눈다. 크게 모니터(운영체제의 상주 영역), 사용자 영역, 미사용 영역으로 나눌 수 있다. 메모리를 제어하는 모든 권한이 사용자에게 있기 때문에 사용자가 주소를 잘못 지정하면 운영체제가 손상될 수 있다. 그래서 프로세서에 경계 레지스터를 두어 이를 방지한다.

이런 메모리 할당 시스템의 문제는 사용자 프로그램의 적재이다. 컴퓨터 주소 공간이 0000부터 시작하더라도 사용자 프로그램의 시작 주소는 기준 레지스터 값의 이후가 된다. 그러므로 기준 주소가 변하면 다시 적재해야 한다. 다음 두 가지 방법을 고려하여 이런 운영체제의 동적 변화에 대비할 수 있다.

첫 번째 방법은 사용자 프로그램을 기준 레지스터보다 상위 메모리에 적재하는 것,

두 번째 방법은 주소 바인딩을 연기하는 것이다.

단일 프로그래밍 환경에서 연속 메모리 할당은 메모리의 효율성이 떨어진다. 또한 자원 낭비가 심하고 프로세스 스와핑 비용이 많이 든다.

다중 프로그래밍 환경에서의 연속 메모리 할당

1) 고정 분할 방법

고정 분할 방법에서는 메모리를 여러 개의 고정된 크기로 분할하고 분할된 각 메모리는 프로세스 하나를 실행하는 방식이다.

고정 분할 방법에서는 논리적 주소가 분할된 메모리보다 크면 오류가 발생하고, 작으면 내부 단편화가 발생한다.

내부 단편화란 분할된 메모리 공간보다 용량이 작은 작업이 들어갔을 때, 사용할 수 없게 되는 공간이 생기는것을 말한다.

2) 가변 분할 방법 

가변 분할 방법은 고정된 경계를 없애고 각 프로세스가 필요한 만큼 메모리를 할당하는 방법이다.

프로세스가 할당되고 해제되다보면 사용 가능한 메모리 공간이 흩어져있게 되는데, 새로 들어갈 작업이 어느 공간에 할당되어야 할 지 결정하는 방법으로는 최초 적합, 최적 적합, 최악 적합 방법이 있다.

가변 분할 방법에서는 외부 단편화가 일어난다.

외부 단편화는 사용 가능한 공간의 총량은 100MB인데, 메모리공간이 연속적이지 않고 흩어져 있어 총량보다 용량이 작은 작업도 할당할 수 없게 되는것을 말한다.

외부 단편화를 해결할 방안으로 메모리 통합과 메모리 압축 방법이 있다.

3) 버디 시스템

위 두 가지 방법 모두 단편화 문제가 있었다. 이를 해결하는 방법으로 버디 시스템이 제안되었다.

버디 시스템은 큰 버퍼들을 반복적으로 이등분하여 작은 버퍼들을 만들고, 가능할 때마다 인접한 빈 버퍼들을 합치는 과정을 반복한다. 나뉜 버퍼들 각각을 서로의 버디라고 칭한다.

할당 요청이 들어오면, 메모리를 요청한 메모리보다 크거나 같아질때까지 이등분하기를 반복한다.

예를 들면, 전체 메모리가 64KB고 들어온 요청은 8KB라면, 64KB를 32KB두개로, 32KB를 16KB 두개로, 16KB를 8KB 두개로 쪼개어 알맞은 크기로 생성된 8KB의 버디에 들어온 요청을 할당한다. 

메모리는 주소의 연속으로, 주소는 크게 두 가지 관점에서 해석 가능하다.

프로그래머가 프로그래밍에 사용하는 공간으로 보는 논리적 관점의 논리적 주소

그리고 실제 데이터나 프로그램을 저장하는 공간으로 보는 물리적 관점의 물리적 주소이다.

논리적 주소는 C/C++같은 언어에서 변수의 주소값을 출력해보면 나오는 주소를 생각하면 이해하기 쉽다.

메모리 관리 장치

논리적 주소와 물리적 주소의 변환은 메모리관리장치가 처리한다.

메모리관리장치가 논리적 주소를 물리적 주소로 변환할 때 다음과 같은 방법을 사용한다.

1. 고정 분할
2. 동적 분할
3. 페이징
4. 세그먼테이션
5. 페이지화된 세그먼테이션

프로세스의 논리적 주소에 대응하는 물리적 주소를 알아야 프로세스를 실행할 수 있는데, 두 주소를 매핑 시켜주는 작업을 바인딩이라고 한다.

바인딩은 컴파일 시간, 적재 시간, 실행 시간으로 구분할 수 있다.

메모리 관리

메모리 관리는 프로세스들을 위해 메모리를 할당하고 제거하며 보호하는 활동이다. 이는 저장장치 전반(하드디스크, DB, etc..)에 해당한다.

메모리 관리는 메모리 관리자가 담당한다. 메모리 관리자는 운영체제의 관리 모듈과 메모리 관리장치(Memory Management Unit)가 협업하여 관리한다.

메모리 관리자는 메모리와 관련된 여러 관리 정책을 수립해 이에 따라 메모리를 관리한다.

관리 정책

1) 적재 정책

디스크에서 메모리로 프로세스를 반입할 시기 결정한다.

적재는 다음 두 가지 방법으로 실행된다.

2) 배치 정책

디스크에서 반입한 프로세스를 메모리 어느 위치에 저장할 것인지 결정한다.

3) 대치 정책

메모리가 충분하지 않을 때 현재 메모리에 적재된 프로세스 중 제거할 프로세스를 결정하는 방법이다.

시기 및 사용 빈도에 따라 선입선출(FIFO) 대치 알고리즘, 최근 최소 사용(LRU) 대치 알고리즘 등 다양한 방법이 있다.

스케줄링 알고리즘의 선택 기준

스케줄링 알고리즘을 비교할 때 참조할 수 있는 기준은 다음과 같다.

1) 프로세서 사용률 - CPU가 놀지 않고 얼마나 많이 사용되고 있는가?
2) 처리율 - 단위시간당 처리하는 일의 양
3) 반환시간 - 수행 요청을 한 다음 끝날때까지 걸리는 시간
4) 대기시간 - 작업이 준비 큐에서 기다리는 시간
5) 반응시간 - 대화형으로 동작할 때 작업 요청 후 반응하는데 까지의 간격

라운드 로빈 스케줄링

라운드 로빈 스케줄링은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나이다.

라운드 로빈 스케줄링은 작은 단위의 시간인 규정 시간량(time quantum)또는 시간 할당량(time slice)을 정의한다. 보통 규정 시간량은 10ms ~ 100ms정도이다. 준비 큐를 순환 큐로 설계해서 스케줄러가 준비 큐를 돌아가며 한 번에 한 프로세스에 정의된 규정 시간량만큼 프로세서를 제공한다. 준비 큐는 FIFO(First In First Out) 큐로 되어있어 새로운 프로세스를 추가할 때는 준비 큐의 맨 뒤에 붙인다.

스케줄러는 준비 큐의 가장 앞부분의 프로세스에 프로세서를 할당하는데, 해당 프로세스가 규정 시간 안에 작업을 마친 경우엔 프로세서가 준비 큐의 다음 프로세스에 할당된다. 규정 시간을 초과한 경우에는 운영체제가 인터럽트해 중단된 프로세스의 레지스터들을 PCB에 저장하고 프로세스는 준비 큐의 마지막 위치에 들어간다.

라운드 로빈 스케줄링의 장단점

다단계 큐 스케줄링

각 작업을 여러개의 큐에 분할하여 스케줄링 하는 방식이다.

각 큐는 각자 독자적인 스케줄링을 가지고, 고정된 선점 우선순위를 가진다.

이때 하위 우선순위를 가진 큐는 상위 우선순위를 가진 큐가 다 처리되어야만 처리가 가능하다. 이 때문에 기아 상태가 발생할 수 있다. 

다단계 피드백 큐 스케줄링과 다른 점은 작업이 하나의 큐에 고정된다는점이다.

다단계 피드백 큐 스케줄링

모든 프로세스는 다 같이 가장 우선순위가 높은 큐에 들어온다. 이 때 큐에 지정된 time-quantum을 채운(초과한) 프로세스는 그보다 한단계 아래 우선순위의 큐에 들어가게 된다.

HRN 스케줄링

각 작업의 우선순위에 따라 서비스해주는 스케줄링 방법이다.

이 때, 우선순위는 다음과 같이 정한다.

우선순위 = (서비스를 받을 시간 + 대기한 시간)/서비스를 받을 시간

HRN 스케줄링은 자원을 효율적으로 사용하고, 기아가 발생하지 않는 특징이 있다.

이에 반해 오버헤드가 높은 단점이 있다.

스케줄링은 다중프로그래밍을 가능하게 하는 운영체제의 동작 기법이다.

운영체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.

스케줄링의 목표는 다음과 같다.

• 단위시간당 처리량 최대화
  
• 자원할당의 공정성 보장
• 적절한 반환시간 보장
• 자원 사용의 균형 유지
• 서비스 사용기회 확대
• 예측 가능성 보장
• 실행 대기 방지
• 서비스 수 감소 방지
• 오버헤드 최소화
• 우선순위 배정

단위시간당 처리량을 최대화하는것은 가장 중요한 목표중 하나지만, 이 때문에 자원이 균등하게 할당되지 않아 무한대기에 빠질 수 있다. 그렇기 때문에 자원을 할당하는데에 있어서 공정성이 보장되어야한다.

스케줄링의 기준 요소 - 버스트

프로세서(CPU) 버스트 -> 프로세스를 프로세서에서 실행할 때
입출력(I/O) 버스트 -> 프로세스가 추가로 실행하려고 입출력을 기다리고 있을 때

프로세서 버스트가 길면 CPU 바운드, 입출력 버스트가 길면 I/O 바운드이다.

스케줄링을 할 때, 어떤 버스트가 길게 걸리는지에 따라 우선순위에 영향을 미친다.

스케줄링의 단계

1단계 스케줄링 (장기 스케줄링)
-어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다.

2단계 스케줄링 (중기 스케줄링)
-어느 프로세스부터 CPU를 차지할 수 있게 할지를 결정한다. 프로세스들을 보류시키고 다시 활성화하는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절한다. 이로써 시스템을 적절히 운영한다.

3단계 스케줄링 (단기 스케줄링)
-CPU가 사용 가능한 경우 어느 프로세스에게 배당할지를 결정한다.

스케줄링 큐

준비 큐(ready queue)는 프로세서를 할당받아 실행하려고 기다리는 프로세스들이 대기하는 큐다.
장치 큐(device queue)는 장치를 사용하려는 프로세스들이 대기하는 큐다.

스케줄링에서는 여러개의 큐가 우선순위에 따라 번갈아가며 자원을 사용한다.

큐잉 도표

프로세스에 프로세서가 할당되면 다음 상황이 일어난다.

1. 프로세스가 I/O 요청을 보내고 I/O 큐에 들어간다.
2. 프로세스가 Sub-process를 생성하고(fork) 생성한 프로세스의 종료를 기다린다.
3. 프로세스가 인터럽트되어 다시 준비큐에 들어간다.
4. 프로세스가 시간 할당량을 초과해 준비큐로 들어간다.

장기 스케줄러와 단기 스케줄러

장기 스케줄러는 작업 스케줄러라고도 하며, 스케줄링에 따라 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정한다.

단기 스케줄러는 메모리에 적재된 프로세스 중 프로세서를 할당하여 실행 상태가 되도록 결정하는 프로세스 스케줄링을 한다. 이때는 프로세스가 실행하는 데 필요한 자원의 요청을 만족해야 한다.

장기 스케줄러와 단기 스케줄러의 가장 큰 차이는 실행 빈도이다. 단기 스케줄러는 실행할 프로세스를 수시로 선택한다.
반면에 장기 스케줄러는 시스템에 새로운 작업이 분단위로 들어오므로 단기 스케줄러에 비해 상대적으로 드물게 수행된다.

대부분의 작업이 입출력 중심 작업(I/O bound)과 프로세서 중심 작업(CPU bound)으로 구성되므로 스케줄러가 작업을 선택한 두 종류의 작업을 잘 혼합하여 선택해야 시스템의 성능을 높일 수 있다.

중기 스케줄러

중기 스케줄러는 프로세스들이 프로세서를 서로 차지하려고 할 때 프로세스를 별도의 기억장소에서 빼낼 수 있어 다중프로그래밍의 정도를 줄일 수 있다. 시간이 흐른 후 빼낸 프로세스는 다시 메모리에 들어가 실행을 중단했던 곳부터 다시 실행한다. 이 방법을 스왑이라고 하는데, 스왑 인과 스왑 아웃을 중기 스케줄러가 결정한다. 스왑은 작업의 혼합을 개선하거나 프로세스가 가지고 있던 메모리를 사용할 수 있게 하는 데 필요하다.

선점 스케줄링과 비선점 스케줄링

비선점 스케줄링(Non-Preemptive scheduling)은 이미 할당된 cpu를 다른 프로세스가 강제로 빼앗아 사용할 수 없게 하는 기법이다.

반면에 선점 스케줄링(Preemptive scheduling)은 하나의 프로세스가 cpu를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 cpu를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.

선점 스케줄링은 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지하기 때문에 모든 프로세스에 프로세서를 서비스할 기회를 늘릴 수 있다. 따라서 우선순위가 높은 프로세스들이 긴급 처리를 요청할 때 용이하다.

하지만 선점 스케줄링은 오버헤드가 커질 수 있어 이를 효과적으로 이용하려면 메모리에 프로세스가 많이 적재되어 있어야 한다. 즉, 프로세서를 사용 가능할 때마다 실행할 수 있는 프로세스들이 준비 상태에 있어야 효과적이다. 따라서 선점 스케줄링에서는 우선순위라는 개념을 반드시 고려해야 하는데, 우선순위는 의미 있게 부여하지 않으면 효과가 없다.