게임 프로그래머

요구 페이징

가져오기 정책 중 프로세스가 요청할 때 메모리로 가져오는 방법

프로세스의 일부만 메모리로 가져오는 이유

• 적은 메모리를 유지하여 메모리를 관리하기 쉬워짐
• 메모리 적재하는 시간 감소, 캐시 지역성 활용, 스왑 감소 등으로 응답 속도를 향상

페이지 테이블 엔트리(PTE) 구조

• 페이지 번호 : 직접 매핑에는 필요없지만 연관 매핑에는 필요
• 프레임 번호 : 가상 주소의 페이지가 어느 프레임에 있는지 알려줌
• 접근(참조) 비트 : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트
• 유효 비트 : 페이지가 메모리에 있는지 나타내는 비트
  페이지가 스왑 영역에 있는 경우는 요구 페이징으로 처음부터 메모리에 적재되지 않는 경우와 메모리가 꽉 차서 스왑 아웃된 경우
• 읽기, 쓰기, 실행 비트 : 페이지에 대한 읽기, 쓰기, 실행 권한을 나타내는 비트
  세그먼테이션-페이징 혼용 기법에서 테이블의 크기를 줄이기 위해 접근 권한 비트를 세그먼테이션 테이블로 옮김

페이지 폴트

프로세스가 페이지를 요청했을 때 페이지가 메모리에 없는 상황

페이지 폴트가 발생하면 스왑 영역에서 물리 메모리로 옮기고 페이지 테이블을 업데이트

메모리에 빈 프레임이 없을 때는 페이지 교체 알고리즘을 통해 메모리에 있는 프레임 중 하나를 스왑 아웃해야 함

페이지 폴트 이후 처리 과정

1. MMU가 페이지 폴트 인터럽트를 발생시켜 현재 실행 중인 명령어의 상태가 저장됨
2. 페이지 폴트 처리 루틴 실행
3. 페이지 테이블을 검사하고 페이지 찾기
4. 메모리가 꽉 찼다면 페이지 교체 알고리즘을 사용하여 페이지를 스왑 아웃하고 페이지 테이블 업데이트
5. 필요한 페이지를 스왑 인하고 페이지 테이블 업데이트
6. 페이지 폴트 발생 시킨 명령어부터 프로세스 실행 재개

세그먼테이션 오류는 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생하고, 해당 프로세스를 강제 종료하여 해결

페이지 교체 알고리즘

페이지 교체 알고리즘에 의해 스왑 아웃하는 페이지를 대상(victim) 페이지라고 함

지역성

메모리가 꽉 차서 페이지를 스왑 아웃할 때는 되도록 앞으로 사용하지 않을 페이지를 스왑 아웃하는 것이 좋음

• 자주 사용될 페이지를 스왑 아웃하면 다시 스왑 인해야 하기 때문에 시스템의 성능이 떨어짐

지역성은 기억장치에 접근하는 패턴이 특정 영역에 집중되는 성질

• 공간의 지역성 : 현재 위치에서 가까운 페이지에 접근할 확률이 먼 페이지에 접근할 확률보다 높음
• 시간의 지역성 : 현재를 기준으로 가까운 시간에 접근한 데이터가 먼 시간에 접근한 데이터보다 사용할 확률이 높음
• 순차적 지역성 : 작업이 순서대로 진행되는 경향, 공간의 지역성의 특별한 경우로도 보기도 함

무작위 페이지 알고리즘

가장 간단한 알고리즘

대상 페이지를 무작위로 선정

지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정

알고리즘의 성능이 좋지 않아 거의 사용되지 않음

FIFO(First In First Out) 페이지 교체 알고리즘

시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정

큐로 구현하여, 가장 오래된 페이지인 메모리의 맨 위에 있는 페이지를 스왑 아웃하고, 새로운 페이지는 항상 맨 아래에 삽입되어 스왑 인

큐로 간단하게 구현 가능

시간의 지역성을 고려하면 가장 오래된 페이지를 선정하는 것이 맞지만, 오래되었더라도 자주 사용되는 페이지일 수 있기 때문에 성능이 떨어짐
Belady의 역설 : 페이지의 프레임 수가 커질수록(사용 가능한 메모리의 크기가 클수록) Page Fault가 늘어나는 역설

최적 페이지 교체 알고리즘

앞으로 사용하지 않을 페이지를 선정

미래의 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋음

미래의 접근 패턴을 안다는 것이 불가능하여 실제로 구현할 수 없음

LRU(Least Recently Used) 페이지 교체 알고리즘

가장 오랫동안 사용되지 않은 페이지를 선정

시간, 카운터, 참조 비트 등을 사용하기 때문에 추가적인 메모리 사용

• 접근 시간에 기반한 구현은 접근한 시간을 기록하여 접근한 지 가장 오래된 페이지를 선정
  LRU 방법 중 가장 간단
• 카운터에 기반한 구현은 시간 대신 카운터를 사용
• 참조 비트 시프트 방식은 일정 크기의 참조 비트를 만들어 참조 비트가 가장 작은 값인 페이지를 선정
  참조 비트의 초기값은 0이고, 접근할 때마다 모든 참조 비트가 오른쪽으로 이동한 뒤 1로 변경됨

LFU(Least Frequently Used) 페이지 교체 알고리즘

사용된 횟수가 가장 적은 페이지를 선정

횟수를 표시하는데 필요한 메모리 낭비

NUR(Not Used Recently) 페이지 교체 알고리즘

LRU, LFU와 성능이 가장 비슷하고 메모리 낭비 문제를 해결

95번 접근한 페이지와 91번 접근한 페이지가 있다면 미래를 추정할 때 두 페이지의 접근 확률은 비슷

따라서 정확한 값을 유지하는 것은 메모리만 차지하기 때문에 추가 비트 2개만 사용

• PTE의 접근 비트와 PTE의 변경 비트

우선 고려 대상은 접근 비트이므로 (0, 0) (0, 1) (1, 0) (1, 1) 순서대로 페이지를 선정

모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 (0, 0)으로 초기화

FIFO 변형 알고리즘

FIFO 페이지 교체 알고리즘을 기본으로 하되 페이지에 접근할 때마다 순서의 변화를 주어 성능을 향상

• 2차 기회 페이지 교체 알고리즘 : 특정 페이지에 접근하여 페이지 폴트 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동
  성능은 LRU, LFU, NUR보다 낮고 FIFO보다 높음
  큐를 유지하는 비용이 높고, 큐의 중간 값을 뒤로 이동하는 작업이 추가되는 단점
• 시계 알고리즘 : 원형 큐를 사용
  대상 페이지를 가리키는 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부름
  참조 비트를 사용하여 페이지 참조에 성공하면 참조 비트가 1이 됨
  참조 비트가 1인 페이지는 건너뛰고 참조 비트를 0으로 초기화
  NUR보다 메모리 공간이 적게 들지만 알고리즘이 복잡하고 계산량이 많다는 단점
  

  

스레싱과 프레임 할당

스레싱

잦은 페이지 폴트로 CPU 작업 시간보다 스왑 인/스왑 아웃 작업 시간이 더 많은 상태

동시에 실행할 수 있는 프로그램의 수를 멀티프로그래밍 정도라고 하는데, 멀티프로그래밍 정도가 높으면 스레싱 발생 확률이 높아짐

스레싱은 프로세스에 프레임을 할당하는 정책과 연관이 있는데, 적은 프레임을 할당하면 스레싱이 발생할 확률이 높아지고, 많은 프레임을 할당하면 메모리 낭비

정적 할당

프로세스 실행 초기에 프레임을 할당한 후 크기를 고정

• 균등 할당 : 프로세스의 크기와 상관없이 모든 프로세스에 균등하게 할당
  크기가 큰 프로세스는 페이지 폴트가 빈번하게 발생하고, 크기가 작은 프로세스는 메모리 낭비
• 비례 할당 : 프로세스의 크기에 비례하여 할당
  프로세스가 런타임에 필요한 프레임을 유동적으로 반영하지 못함
  사용하지 않을 프레임을 미리 할당하여 낭비

동적 할당

런타임에 필요한 프레임만 할당

• 작업집합 모델 : 지역성 이론을 바탕으로, 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고 집합에 있는 페이지들을 물리 메모리에 유지
  작업집합 크기는 작업집합에 들어갈 최대 페이지 수를 의미하고, 작업집합을 갱신하는 주기를 의미
  작업집합 크기를 크게 잡으면 필요 없는 페이지가 메모리에 남아 메모리 낭비하고, 작게 잡으면 필요한 페이지가 스왑 아웃되어 페이지 폴트 증가
• 페이지 폴트 빈도 : 페이지 폴트 횟수를 기록하여 비율을 계산하고, 상한을 초과하면 프레임을 추가로 할당하고, 하한 아래로 내려가면 프레임을 회수
  실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절

프레임 관련 이슈

전역 교체 : 전체 프레임을 대상으로 페이지 교체 알고리즘을 적용

지역 교체 : 현재 실행 중인 프로세스의 프레임를 대상으로 교체 알고리즘을 적용
프로세스의 할당된 프레임의 전체 개수에 변화가 없기 때문에 다른 프로세스의 스레싱에 영향을 미치지 않음

자주 사용하는 페이지가 스왑 아웃되어 현재 프로세스의 스레싱이 발생할 수 있음

페이지 테이블의 크기를 줄이기 위해 페이지의 크기를 높일 수 있음

그러나 페이지의 크기를 무작정 늘리면 내부 단편화로 인한 메모리 낭비 증가

여러 프로세스가 동시에 같은 프레임을 메모리에 올리면 메모리가 낭비되므로 메모리에 프레임을 하나만 올리고 페이지가 공유하여 해결

가상 메모리

가상 메모리는 물리 메모리의 크기와 상관없이 프로세스에 커다란 메모리 공간을 제공하는 기술

가상 메모리 시스템의 모든 프로세스는 물리 메모리와 별개로 0번지 부터 시작하는 연속된 메모리 공간을 가짐

가상 메모리 시스템에서는 물리 메모리가 꽉 찼을 때 물리 메모리의 내용 중 일부를 스왑 영역으로 보내고(스왑 아웃), 프로세스가 작업을 마치면 스왑 영역에 있는 프로세스를 메모리로 가져옴(스왑 인)

따라서 가상 메모리에서 메모리 관리자가 사용할 수 있는 메모리의 전체 크기는 물리 메모리 크기 + 스왑 영역 크기

메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주소를 실제 메모리의 물리 주소로 변환함(동적 주소 변환, DAT, Dynamic Address Translation)

• 가상 주소 공간 : 가상 메모리 기법으로 생성된 논리 주소 공간

가상 메모리 분할 방식

운영체제를 제외한 나머지 메모리 영역을 일정한 크기로 나누어 프로세스에 할당

가변 분할 방식을 이용한 메모리 관리 기법을 세그먼테이션, 고정 분할 방식을 이용한 메모리 관리 기법은 페이징이라고 함

세그먼테이션 기법은 가변 분할 방식의 단점인 외부 단편화 등의 문제 때문에 잘 사용되지 않고, 페이징 기법은 페이지 관리에 어려움이 있기 때문에 두 기법의 단점을 보완한 세그먼테이션-페이징 혼용 기법을 주로 사용

매핑 테이블

메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리

페이징 기법에서 사용하는 매핑 테이블을 페이지 매핑 테이블 또는 페이지 테이블이라고 부르며 세그먼테이션 기법에서는 세그먼테이션 매핑 테이블 또는 세그먼테이션 테이블이라고 부름

페이징 기법

페이징 기법은 고정 분할 방식을 이용한 가상 메모리 관리 기법

가상 주소의 분할된 각 영역은 페이지라고 부르며 물리 메모리의 각 영역은 프레임이라고 부름

페이지와 동일한 크기의 프레임 단위로 나눈 뒤 페이지를 프레임에 할당

페이지와 프레임의 크기는 같기 때문에 페이지는 어떤 프레임에도 배치될 수 있음

페이지와 프레임 크기를 같게 하는 이유는 페이지에 대응되는 프레임을 쉽게 찾기 위함

어떤 페이지가 어떤 프레임에 있는지에 대한 연결 정보는 페이지 테이블에 담겨 있음

여러 프로세스가 동일한 프로그램을 실행할 때 코드는 동일하므로 각 프로세스가 코드를 담은 페이지를 공유하여 메모리 낭비 방지

프로세스마다 각자의 페이지 테이블 정보를 보유

주소 변환

1. 가상 주소가 어느 페이지에 있는지 찾음
2. 페이지 테이블에서 페이지에 대응되는 프레임을 찾음
3. 물리 메모리 프레임에 접근

페이지 테이블의 크기는 물리 메모리가 아닌 프로세스의 크기에 비례

페이지 테이블은 물리 메모리의 운영체제 영역에 존재하고, 실행하는 프로세스마다 존재하여 실행하는 프로세스의 수에 비례

물리 메모리의 크기가 작을 때는 프로세스 뿐만 아니라 페이지 테이블의 일부도 스왑 인/아웃 됨

페이지 테이블에 빨리 접근하기 위해 페이지 테이블의 시작 주소를 저장한 PTBR(Page Table Base Register)을 사용

• PTBR은 PCB에 저장되는 데이터

페이지 테이블 매핑 방식

• 직접 매핑 : 페이지 테이블 전체가 물리 메모리의 운영체제 영역에 존재하는 방식
  페이지 테이블 전체가 메모리에 적재되므로 사용되는 메모리가 증가
  모든 페이지를 물리 메모리에 가지고 있기 때문에 주소 변환 속도가 빠름
• 연관(associative) 매핑 : 페이지 테이블 전체를 스왑 영역에서 관리하여 메모리 절약, 물리 메모리의 여유 공간이 작을 때 사용, 페이지 테이블의 일부만 무작위로 가져오기 때문에 페이지 번호와 프레임 번호 둘 다 표시
  원하는 프레임 번호를 가져올 때 페이지 테이블을 다 검색해야 하므로 주소 변환이 느림
  
  프로세스의 페이지 테이블을 메모리에 둘 경우 메모리를 차지하고, 물리 메모리에 있는 페이지 테이블에 접근해야 하므로 접근 속도 저하
  위 문제를 해결하기 위해  TLB와 계층적 페이징을 사용
  
  메모리에 적재된 일부 페이지 테이블을 TLB(Translation Look-aside Buffer) 또는 연관 레지스터라고 부름
  TLB에 원하는 페이지 번호가 있는 경우 TLB 히트, 없는 경우 TLB 미스라고 하며 스왑 영역에 저장된 직접 매핑 테이블을 사용하여 프레임 번호로 변환
  TLB 미스가 빈번할 경우 시스템의 성능이 떨어짐
  
  계층적 페이징(Hierachical Paging)
  페이지 테이블을 계층적으로 구성하여 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없고 Outer 페이지 테이블만 메모리에 유지하여 메모리 용량 줄임
  

  

  
  
  
  
• 페이지 테이블을 페이징하는 방식
• 집합-연관 매핑 : 모든 페이지 테이블을 스왑 영역에서 관리하고 일부만 메모리로 스왑 인 하는 것은 연관 매핑과 동일하고, 관련 있는 페이지 테이블을 일정한 집합으로 자르고 집합 단위로 스왑 인
  물리 메모리의 모든 페이지 테이블을 검사할 필요가 없어 주소 변환 시간이 단축
  
  집합 테이블이 메모리에 있는지 스왑 영역에 있는지를 표시하는 디렉터리 테이블을 새로 만듦
  디렉터리 테이블을 확인하여 집합 테이블이 어디있는지 확인할 수 있으므로 바로 TLB 미스를 알 수 있음
  PTBR이 디렉터리 테이블 시작 주소를 갖고 있음
• 역매핑 : 위 세 매핑 방식과 달리 프레임 번호를 기준으로 테이블을 구성
  PID와 페이지로 구성됨
  프로세스의 수와 상관없이 테이블이 하나만 존재하므로 테이블의 크기가 매우 작음
  가상 메모리에 접근할 때 프로세스 아이디와 페이지 번호를 모두 찾아야 하므로 속도가 느림

세그먼테이션 기법

가변 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 메모리를 프로세스의 크기에 따라 가변적으로 사용

세그먼테이션 (매핑) 테이블은 세그먼테이션 기법에서 사용하는 매핑 테이블

• 세그먼트의 크기를 나타내는 limit과 물리 메모리의 시작 주소를 나타내는 address가 있음
• 프로세스의 크기에 따라 메모리를 분할하기 때문에 세그먼트의 크기를 저장
• 각 세그먼트가 주어진 메모리 영역을 넘어가면 안되기 때문에 size 대신 limit을 사용
  만약 Distance가 limit보다 크면 메모리 오류(트랩)를 출력하고 해당 프로세스를 강제 종료
  • 트랩 : 프로세스 영역을 벗어나는 주소에 접근하거나 숫자를 0으로 나누는 것과 같이 사용자가 의도치 않게 일으키는 인터럽트

물리 메모리가 부족할 때 스왑 영역을 사용

가변 분할 방식이 기본이기 때문에 가변 분할 방식의 장단점을 모두 갖고 있음

• 메모리를 프로세스 단위로 관리하기 때문에 페이지 테이블이 작고 단순
• 물리 메모리의 외부 단편화로 인해 물리 메모리 관리가 복잡

세그먼테이션-페이징 혼용 기법

메모리 접근 권한은 메모리의 특정 번지에 저장된 데이터를 사용할 수 있는 권한으로 읽기, 쓰기, 실행, 추가 권한이 있음

코드 영역은 읽기 및 실행 권한을 갖고, 데이터 영역은 일반적으로 읽기 및 쓰기 권한을 가지고 상수로 선언한 변수는 읽기 권한만 가짐

• 만약 읽기만 가능한 메모리에 쓰기를 하려고 하면 트랩 발생

페이지마다 접근 권한이 다르기 때문에 페이지 테이블의 모든 행에는 메모리 접근 권한과 관련된 권한 비트가 추가됨

인접한 페이지의 메모리 접근 권한이 같은 경우가 많으므로 페이지마다 권한 비트를 설정하는 것은 메모리 낭비가 됨

권한 비트 추가에 따른 페이지 테이블의 크기가 커지는 문제는 세그먼테이션 테이블을 이용

서로 관련 있는 영역을 하나의 세그먼트로 묶어 세그먼테이션 테이블로 관리하고, 각 세그먼트를 구성하는 페이지를 페이지 테이블로 관리하는 방식

• 권한 비트와 같이 중복되는 데이터를 세그먼테이션 테이블로 옮겨 페이지 테이블의 크기를 줄임

캐시 매핑 기법

캐시의 크기는 메모리의 크기보다 작기 때문에 항상 메모리의 일부 페이지만 가지고 있음

직접 매핑

블록은 메모리 프레임 수 N을 캐시의 페이지 수 M으로 나눈 개념

메모리의 블록이 항상 같은 위치에 올라오기 때문에 메모리의 어떤 블록에서 올라온 페이지인지만 확인하면 됨

따라서 캐시에 블록 번호를 명시하는데 이를 태그라고 함

또한, 태그만 확인하면 되기 때문에 캐시 히트나 캐시 미스를 빠르게 확인할 수 있음

그러나 페이지가 같은 위치에만 올라오기 때문에 같은 태그의 메모리를 연달아 필요한다면 캐시에 여유가 있어도 캐시 적중률이 떨어짐

연관 매핑

메모리 워드가 캐시의 어느 위치에도 자유롭게 올라갈 수 있으므로 캐시가 메모리 워드의 주소를 전부 가지고 있음

CPU에서 특정 주소를 필요로 할 때 캐시에서 검색하여 찾는 경우 캐시 히트, 못 찾는 경우 캐시 미스가 발생하여 메모리에서 원하는 데이터를 가져옴

캐시 메모리를 자유롭게 사용할 수 있다는 장점이 있지만 캐시 히트/미스인지 확인하기 위해 캐시의 모든 주소를 검색해야 하므로 연관 매핑보다 느림

집합-연관 매핑

캐시를 K개의 집합으로 나누고 각 집합에 직접 매핑을 사용

• 직접 매핑하는 캐시 메모리를 K개로 나눠 같은 끝자리를 가진 캐시 메모리가 K개가 되기 때문에 직접 매핑의 자리다툼 문제 완화

집합 내에서 직접 매핑을 사용하기 때문에 바로 캐시 히트 여부를 알 수 있음

메모리의 구조는 1B 크기로 나뉨

CPU는 메모리에 있는 내용을 가져오거나 작업 결과를 메모리에 저장하기 위해 메모리 주소 레지스터(MAR)를 사용

메모리는 유일한 작업 공간이며 운영체제를 포함한 모든 프로그램은 메모리에 올라와야 실행이 가능하기 때문에 메모리 관리가 복잡

메모리 관리 이중성 : 프로세스는 메모리를 독차지하려 하고, 메모리 관리자 입장에서는 메모리 관리를 효율적으로 하고 싶어 하는 것

소스코드의 번역과 실행

언어 번역 프로그램은 고급 언어(C, 자바 등)으로 작성한 소스코드를 컴퓨터가 실행할 수 있는 기계어로 번역하는 프로그램

• 컴파일러 : 소스코드를 컴퓨터가 실행할 수 있는 기계어로 번역한 후 한꺼번에 실행, C/자바 등
• 인터프리터 : 소스코드를 한 행씩 번역하여 실행, 자바스크립트/베이직 등

컴파일 과정

1. 컴파일 : 컴파일러가 소스 코드를 오류 점검, 최적화 등을 수행하여 object 코드(기계어)로 번역됨
2. 링크 : object 코드에 라이브러리 코드를 삽입하여 최종 실행 파일을 만듦
   
   • 라이브러리의 내부 구현을 동적 라이브러리에서 가져와 실행하여 라이브러리가 변경돼도 컴파일하지 않고 라이브러리를 공유하여 메모리 절약

메모리 관리자(MMU, Memory Manage Unit)의 역할

프로세스와 데이터를 메모리로 가져오는 작업(fetch)

가져온 프로세스와 데이터를 메모리의 어떤 부분에 올려놓을지 결정하는 작업(placement)

꽉 차 있는 메모리에 새로운 프로세스를 가져오기 위해 오래된 프로세스를 내보내는 작업(replacement)

CPU의 비트는 한 번에 다룰 수 있는 데이터의 최대 크기를 의미하여, 내부 부품이 모두 이 비트를 기준으로 제작됨

메모리의 주소를 지정하는 메모리 주소 레지스터(MAR)의 크기가 CPU의 비트와 같으므로 32비트 CPU의 경우 2^32개(4GB), 64비트 CPU의 경우 2^64개(1천 6백만TB)

설치된 메모리의 주소 공간을 물리 주소 공간(절대 주소)이라고 하며, 프로세스마다 부여되는 0번지부터 시작하는 주소 공간은 논리 주소 공간(상대 주소)
CPU와 프로세스가 사용하는 주소 체계는 논리 주소이므로 중복 물리 주소는 없지만 중복 논리 주소는 가능

운영체제는 시스템을 관리하는 중요한 역할을 하기 때문에 사용자가 운영체제를 침범하지 못하도록 메모리 관리자는 분리하여 관리

상위 메모리부터 운영체제 메모리 방향으로 사용자 영역을 할당하는 방법은 운영체제의 크기에 상관없이 사용자 영역의 시작점을 결정할 수 있으나 메모리를 거꾸로 사용하기 위해 주소를 변경하는 것이 복잡하여 잘 쓰이지 않음

경계 레지스터는 운영체제 영역과 사용자 영역 경계 지점의 주소를 가진 레지스터로, 사용자 영역이 운영체제 영역으로 침범하는 것을 막을 때 사용

상대 주소는 사용자 영역이 시작되는 번지를 0번지로 변경하여 사용하는 주소 지정 방식으로, 운영체제가 업그레이드되거나 운영체제 영역의 주소가 사용자에게 노출될 가능성을 방지

MMU가 상대 주소를 절대 주소로 매우 빠르게 변환하여 메모리에 접근

상대 주소를 절대 주소로 변환하는 과정

1. 사용자 프로세스가 상대 주소 40번지에 있는 데이터 요청
2. CPU는 메모리 관리자에게 40번지에 있는 내용을 가져오라고 명령
3. 메모리 관리자는 재배치 레지스터를 사용하여 상대 주소 40번지를 절대 주소 400번지로 변환하고 메모리 400번지에 저장된 데이터를 가져옴

재배치 레지스터는 메모리에서 사용자 영역의 시작 주소값을 저장

메모리 오버레이

메모리 오버레이는 프로그램의 크기가 메모리보다 클 때 전체 프로그램을 적당한 크기로 잘라서 가져오는 기법

프로그램을 몇 개의 모듈로 나누고 중요한 모듈만 메모리에 적재하고, 나머지는 필요할 때마다 모듈을 메모리에 가져와 사용

어떤 모듈을 가져오거나 내보낼지는 프로그램 카운터가 결정

메모리보다 큰 프로그램의 실행이 가능

프로그램 전체가 아니라 일부만 메모리에 올라와도 실행이 가능

스왑

모듈을 메모리에서 제거할 때 다시 사용할 지도 모르고 작업이 끝나지 않았기 때문에 저장장치의 특별한 공간인 스왑 영역에 저장
메모리에 적재된 프로세스 중 실행되고 있지 않는 프로세스를 스왑 영역으로 보내고 다른 프로세스를 적재하여 실행하는 메모리 관리 방식

스왑 영역에서 메모리로 데이터를 가져오는 작업인 swap in, 메모리에서 스왑 영억으로 데이터를 내보내는 swap out

스왑 영역은 메모리 관리자가 관리

다시 swap in될 때는 swap-out되기 전의 물리 주소와 다를 수 있음

사용자는 메모리의 크기와 스왑 영역의 크기를 합쳐서 전체 메모리로 인식하고 사용할 수 있음

메모리 분할 방식

메모리에 여러 개의 프로세스를 배치하는 방법은 가변 분할 방식과 고정 분할 방식으로 나뉨

• 가변 분할 방식(세그멘테이션 기법)  : 프로세스의 크기에 따라 메모리를 나눔
  프로세스의 크기에 따라 메모리를 나누므로 메모리의 영역이 각각 다름
  한 프로세스가 연속된 공간에 배치되기 때문에 연속 메모리 할당이라고 함
  
  프로세스를 한 덩어리로 처리하여 하나의 프로세스가 연속된 공간에 배치됨
  프로세스 작업을 마쳤을 때 빈 공간이 떨어져 있기 때문에 통합하는 작업 등이 필요하므로 메모리 관리가 복잡
  
  외부 단편화(fragmentation) 발생 가능 : 빈 영역이 있어도 서로 떨어져 있으면 연속된 크기의 메모리가 없어 프로세스를 할당하지 못하는 상태
  외부 단편화를 해결하기 위해 작은 조각이 발생하지 않도록 프로세스를 배치하거나, 단편화가 발생했을 때 작은 메모리를 합쳐 큰 메모리로 만드는 조각 모음을 하는 방법이 있음
  
  • 최초 배치(first fit) : 단편화를 고려하지 않는 것으로, 프로세스를 메모리에 적재 가능한 공간을 순서대로 찾다가 첫 번째로 발견한 공간에 프로세스를 배치하는 방법
    빈 공간을 찾을 필요가 없음
  • 최적 배치(best fit) : 메모리의 빈 공간을 모두 확인한 후 가장 작은 공간에 프로세스를 배치하는 방법
    딱 맞는 공간이 있을 때는 단편화가 일어나지 않지만 딱 맞는 공간이 없을 때는 아주 작은 조각을 만드는 단점이 있음
  • 최악 배치(worst fit) : 메모리의 빈 공간을 모두 확인한 후 가장 큰 공간에 프로세스를 배치하는 방법
    빈 공간의 크기가 클 때는 효과적이지만 빈 공간의 크기가 점점 줄어들면 최적 배치처럼 작은 조각을 만드는 단점이 있음
    
    
  • 조각 모음 : 조각 모음을 하기 위해 프로세스의 동작을 멈추고 프로세스를 이동한 후 프로세스의 상대 주소값을 변경하고 프로세스를 다시 시작
    위와 같은 작업을 하기 때문에 많은 시간이 걸리고, 부가적인 작업이 필요하므로 메모리 관리가 복잡
    
    
  • 버디 시스템 : 외부 단편화를 완화하는 방법
    프로세스의 크기에 맞게 메모리를 반으로 자르면서 프로세스를 메모리에 배치
    나뉜 메모리의 각 구역에는 프로세스가 1개만 들어감
    프로세스가 종료되면 주변의 빈 조각과 합쳐서 하나의 큰 메모리를 만듦
    가변 분할 방식처럼 메모리가 프로세스 크기대로 나뉘며, 고정 분할 방식처럼 내부 단편화가 발생
    가변 분할 방식보다 효과적으로 공간을 관리할 수 있는 이유는 비슷한 크기의 메모리가 서로 모여 있어 통합하기가 쉽기 때문
    공간 관리 측면에서는 고정 분할 방식과 비슷하지만 공간을 반으로 나누고 통합하는 과정보다 똑같은 크기로 나누는 고정 분할 방식이 더 단순
  • 메모리 풀 : 사전에 큰 메모리 블록을 할당하고 이를 필요한 크기로 나누어 사용하는 방법
• 고정 분할 방식(페이징) : 프로세스의 크기와 상관없이 메모리를 같은 크기로 나누는 것
  한 프로세스가 분산되어 배치되기 때문에 비연속 메모리 할당이라고 함
  
  일정한 크기로 나누어 관리하기 때문에 부가적인 작업을 할 필요가 없어 메모리 관리가 수월
  일정하게 나누어진 공간보다 작은 프로세스가 올라올 경우 메모리 낭비 발생
  프로세스가 메모리의 여러 조각에 저장되는 것이 문제
  
  가변 분할 방식보다 공간을 효율적으로 관리
  조각 모음을 할 필요가 없어 관리가 수월하므로 기본으로 사용되고 있음
  
  내부 단편화 발생 가능 : 각 메모리 조각에 프로세스를 배치하고 공간이 남는 현상
  분할되는 공간의 크기를 조절하여 내부 단편화를 최소화할 수 있음
  분할되는 공간의 크기를 줄이면 내부 단편화가 줄어들지만 프로세스가 여러 개로 분할되어 관리하기 어려움
  분할되는 공간의 크기를 늘리면 내부 단편화가 늘어나 메모리가 낭비됨

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

Starvation은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제이고, 교착 상태는 여러 프로세스가 작업을 진행하다 자연적으로 일어나는 문제

다중 자원 : 여러 프로세스가 하나의 자원을 동시에 사용할 수 있는 자원

교착 상태 필요 조건

상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야 발생, 하나라도 충족하지 않으면 교착 상태가 발생하지 않음

상호 배제(Mutual Exclusion) : 한 프로세스가 사용되는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함

(배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없음)

비선점(Nonpreemptive) : 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함

점유와 대기(Hold And Wait) : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함

원형 대기(Circular Wait) : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어 프로세스들이 서로 양보하지 않아야 함

상호 배제와 비선점 조건은 자원의 특징을 나타내고, 점유와 대기, 원형 대기 조건은 프로세스의 행위를 나타냄

교착 상태 해결 방법

예방

교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식

실효성이 적어 잘 사용되지 않음

• 상호 배제 예방 : 상호 배타적인 모든 자원을 없애는 방법, 현실적으로 모든 자원을 공유할 수 없으며 보호해야 하는 자원이 있으므로 어려움
• 비선점 예방 : 모든 자원을 빼앗을 수 있도록 만드는 방법, 상호 배제를 보장할 수 없고 임계구역 보호가 불가능하고 Starvation을 초래하므로 어려움
• 점유와 대기 예방 : 필요한 자원을 전부 할당하거나 아예 할당하지 않는 방법
  프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
  앞으로 사용할 자원까지 미리 선점해버리기 때문에 자원 낭비가 심함
  많은 자원을 사용하는 프로세스의 작업이 지연되는 Starvation 현상 발생
  실제로 구현하면 일괄 작업 방식으로 처리되므로 시스템의 효율이 떨어짐
• 원형 대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
  모든 자원에 번호를 부여하고 번호가 큰 방향으로 자원을 할당
  프로세스 작업 진행에 유연성이 떨어짐
  자원의 번호를 어떻게 부여할지의 문제가 있음

회피

자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 대기하는 방법

자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정(safe) 상태와 불안정(unsafe) 상태로 나누고 안정 상태를 유지하도록 자원을 할당

불안정 상태에서 항상 교착 상태가 발생하는 것이 아닌 교착 상태 발생 가능성이 높아짐

• 은행원 알고리즘(Banker's Algorithm)
  스레드(프로세스)가 요청하는 최대 자원 개수를 신고
  스레드가 자원을 요청했을 때 안정 상태이면 자원을 할당하고, 불안정 상태이면 다른 스레드가 끝날 때까지 대기

자원을 얼마나 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적음

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 하는데 어려움
• 시스템의 전체 자원 수가 고정적이어야 하는데, 시스템의 자원 수는 유동적임
• 모든 불안정 상태가 교착 상태가 되는 것은 아니므로 최대 자원을 사용할 수 없어 자원이 낭비됨

검출

어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식

• 타임아웃을 이용한 교착 상태 검출 : 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리
  • 타임아웃 시간 동안 작업이 진행되지 않은 모든 프로세스가 교착 상태 때문에 작업이 이루어지지 않은 것은 아니므로 엉뚱한 프로세스가 강제 종료될 수 있음
  • 윈도우의 '프로그램이 응답이 없어 종료합니다' 메시지
• 자원 할당 그래프를 이용하여 교착 상태 검출
  • 운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신하는데, 사이클이 발생하면 교착 상태가 검출된 것으로 판단 
  • 작업이 너무 많아 구현하기 어려워 자주 발생하지 않는 교착 상태를 찾기 위해 자원 할당 그래프를 유지하면서 모든 자원을 감시하기에 어려움

회복

교착 상태를 검출한 후 교착 상태를 유발한 프로세스를 강제 종료하여 교착 상태를 푸는 후속 작업

• 교착 상태를 일으킨 모든 프로세스를 종료 : 종료된 프로세스가 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크기 때문에 다시 실행할 때는 순차적으로 실행해야 함
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

프로세스를 강제 종료하는 일뿐 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 함

명령어가 실행될 때마다 체크포인트를 만드는 일은 작업량이 상당하여 시스템에 부하를 주므로 선택적으로 사용해야 함

프로세스 간 통신(IPC)

동시에 실행되는 프로세스끼리 데이터를 주고받는 작업

프로세스 간 통신에는 같은 컴퓨터에 있는 프로세스 뿐만 아니라 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와의 통신도 포함됨

프로세스 내부 데이터 통신 : 하나의 프로세스 내에 2개 이상의 스레드가 존재하는 경우의 통신, 전역 변수나 파일을 이용하여 데이터를 주고 받음

프로세스 간 데이터 통신 : 같은 컴퓨터에 있는 여러 프로세스끼리 통신하는 경우로, 공용 파일이나 메모리 또는 운영체제가 제공하는 파이프를 사용하여 통신

네트워크를 이용한 데이터 통신 : 여러 컴퓨터가 네트워크로 연결되어 있을 때 프로세스가 소켓을 이용하여 데이터를 주고 받음

양방향 통신 : 데이터를 동시에 양쪽 방향으로 전송할 수 있는 구조, 소켓 통신

반양방향 통신 : 데이터를 양쪽 방향으로 전송할 수 있지만 동시 전송은 불가능하고 특정 시점에 한쪽 방향으로만 전송할 수 있는 구조, 무전기

단방향 통신 : 한쪽 방향으로만 데이터를 전송할 수 있는 구조, 전역 변수와 파이프

전역 변수를 사용하는 통신 방식의 가장 큰 문제는 언제 데이터를 보내는지를 데이터를 받는 쪽에서는 모른다는 것

따라서 상태 변화를 살펴보기 위해 반복문을 무한 실행하며 기다리는 바쁜 대기(busy waiting)는 좋지 않음

busy waiting을 해결하기 위해서는 데이터가 도착했음을 알려주는 동기화(synchronization)을 사용

대기가 있는 통신 : 동기화를 지원하는 통신 방식, 데이터를 받는 쪽은 데이터가 도착할 때까지 자동으로 대기 상태, 파이프, 소켓

대기가 없는 통신 : 동기화를 지원하지 않는 통신 방식, 데이터를 받는 쪽은 바쁜 대기를 사용, 전역 변수, 파일

공유 메모리

데이터를 공유하는 프로세스가 공통적으로 사용할 메모리 영역을 두는 방식

프로세스가 공유 메모리 영역을 확보하는 시스템 콜을 기반으로 수행하거나 변수/파일을 활용하는 방법

데이터를 공유할 때 커널 영역을 거의 사용하지 않아 속도가 빠름

각각의 프로세스가 공유 메모리 영역을 동시에 읽고 쓸 경우 race condition, 동기화 문제 가능

메시지 전달(메시지 큐)

프로세스 간에 공유하는 데이터를 메시지의 형태로 커널을 거쳐 송수신되는 방식

메시지를 보내는 send() 시스템 콜과 메시지를 받는 recv() 시스템 콜을 사용하여 송수신

커널의 도움을 받아 race condition, 동기화 문제는 적지만 통신 속도는 느림

공유 자원과 임계 구역

동기화

실행 순서 제어와 상호 배제 조건을 충족하여 실행하는 것을 의미

• 실행 순서 제어 : 프로세스 및 스레드를 올바른 순서로 실행
• 상호 배제 : 동시에 접근해서는 안되는 자원에 하나의 프로세스 및 스레드만 접근

공유 자원

공유 자원은 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말함

누가 언제 데이터를 읽거나 쓰냐에 따라 결과가 달라질 수 있으므로 프로세스들의 공유 자원 접근 순서를 정하여 문제가 발생하지 않도록 해야 함

두 프로세스가 예금 10만 원을 동시에 읽은 후 다른 프로세스의 작업을 무시하고 덮어쓰는 바람에 총액이 맞지 않는 문제가 발생

이처럼 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 경쟁 조건(race condition)이 발생했다고 함

임계 구역(critical section)

공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역

임계 구역에서는 프로세스들이 동시에 작업하면 안됨

생산자-소비자 문제

produce()
{
    input(buf);
    sum += 1;
}

consumer()
{
    output(buf);
    sum -= 1;
}

sum += 1;과 sum -= 1;이 거의 동시에 실행되면 sum 값은 2 또는 4가 될 수 있음

임계 구역 해결 조건

상호 배제 : 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없음

한정 대기 : 특정 프로세스가 임계구역에 진입하지 못하면 안됨

진행의 융통성 : 한 프로세스가 다른 프로세스의 진행을 방해해서는 안됨

임계 구역 해결 방법

진행의 융통성 문제

// process A
while(lock == 2);

{
    // 임계 구역
}

lock = 2;

// process B
while(lock == 1);

{
    // 임계 구역
}

lock = 1;

한 프로세스가 다른 프로세스로 인해 방해받아 두 번 연달아 임계 구역에 진입할 수 없는 현상을 경직된 동기화(lookstep synchronization)이라고 함

하드웨어적 해결방법

while(testandset(&lock) == true);

{ 
    // 임계 구역
}

lock = false;

testandset은 while(lock == true); 문과 lock = true; 문을 한 번에 실행

바쁜 대기를 사용하여 검사하기 때문에 자원 낭비

피터슨 알고리즘

// process A
lock1 = true;
turn = 2;

while(lock2 && turn == 2);

{
    // 임계 구역
}

lock1 = false;

// process B
lock2 = true;
turn = 1;

while(lock1 && turn == 1);

{
    // 임계 구역
}

lock2 = false;

turn은 두 프로세스가 동시에 락을 설정하여 임계 구역에 못 들어가는 상황을 대비하기 위한 장치

프로세스를 추가하려면 변수가 늘어나고 알고리즘이 복잡해지는 단점이 있음

데커 알고리즘

// process A
lock1 = true;

while(lock2)
{
    if(turn == 2)
    {
        lock1 = false;
        while(turn == 2);
        lock1 = true;
    }
}

{
    // 임계 구역
}

turn = 2;
lock1 = false;

// process B
lock2 = true;

while(lock1)
{
    if(turn == 1)
    {
        lock2 = false;
        while(turn == 1);
        lock2 = true;
    }
}

{
    // 임계 구역
}

turn = 1;
lock2 = false;

프로세스를 추가하려면 변수가 늘어나고 알고리즘이 복잡해지는 단점이 있음

Mutex Lock

동시 접근이 불가능하도록 상호 배제를 보장하는 동기화 도구

임계 구역에 접근하려면 반드시 락을 획득(Acquire)하고, 임계 구역을 벗어나면 락을 해제(Release)해야 함

RAII 기법을 사용하여 객체의 생성자와 소멸자에서 락을 획득 및 소멸하는 방법으로도 구현 가능

락을 획득한 상태에서 다른 프로세스 및 스레드가 락을 획득하려고 하면 락을 해제할 때까지 대기

mutex threadMutex;

void increment()
{
	for (int i = 0; i < threadCount; ++i)
	{
		std::lock_guard<std::mutex> lock(threadMutex);
		++value;
	}
}

void decrement()
{
	for (int i = 0; i < threadCount; ++i)
	{
		std::lock_guard<std::mutex> lock(threadMutex);
		--value;
	}
}

세마포어

// 주석은 해당 함수의 내부 코드
Semaphore(n); // Rs = n; // n은 공유 자원의 개수를 의미
P(); // if(RS > 0) RS -= 1;
     // else block();

{
    // 임계 구역
}

V(); // RS += 1;
     // wake_up();

세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up 신호를 받으면 큐에서 나와 임계구역에 진입하기 때문에 바쁜 대기를 하지 않음

P와 V의 내부 코드가 실행되는 도중에 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못하므로 내부 코드는 검사와 지정(testandset)을 사용하여 완전히 실행되게 해야 함

피터슨 알고리즘이나 데커 알고리즘보다 단순하고 사용하기 편리

임계구역 전후로 P와 S를 정확히 호출하지 않으면 임계구역이 보호받지 못할 수 있다는 문제가 있음

모니터

공유 자원을 내부로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킴

사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋음

임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 모니터에 작업을 요청

모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 결과만 해당 프로세스에 전달

class BankAccount {
public:
    void deposit(double amount) {
        std::unique_lock<std::mutex> lock(mtx);

        cv.wait(lock, [this]() { return !isProcessing; });
        
        isProcessing = true;

        // 입금 처리
        if (amount > 0) {
            balance += amount;
        }

        isProcessing = false;
        
        cv.notify_one();
    }
    
private:
    double balance;
    std::mutex mtx;
    std::condition_variable cv;
    bool isProcessing;
};

wait : 모니터 큐에서 자신의 차례가 올 때 까지 기다림, 세마포어의 P()에 해당

notify_one : 모니터 큐에서 기다리는 다음 프로세스에 순서를 넘겨줌, 세마포어의 V에 해당

CPU 스케줄링은 어떤 작업에 CPU를 배정할 지 결정하는 것

컴퓨터 시스템의 효율은 어떤 프로세스를 CPU에 먼저 배정하느냐에 따라 달라지므로 CPU 스케줄링은 작업의 형평성과 효율성을 결정하는 중요한 일

CPU 스케줄링 단계

CPU 스케줄링은 규모에 따라 고수준, 중간, 저수준 스케줄링으로 구분

대부분의 CPU 스케줄러는 중간과 저수준 스케줄링으로 구성됨

고수준 스케줄링

시스템 내의 전체 작업 수를 조절하는 CPU 스케줄링으로, 장기(long-term), 작업(job), 승인(admission) 스케줄링으로도 불림

작업은 운영체제에서 다루는 일의 가장 큰 단위로, 1개 또는 여러 개의 프로세스로 이루어짐

시스템의 상황을 고려하여 어떤 작업을 시스템이 받아들일지 거부할지를 결정하여 실행 가능한 프로세스의 총 개수가 결정되는데 이를 멀티프로그래밍 정도(degree of multiprogramming)라고 함

메인프레임과 같은 큰 시스템에서 규모가 큰 일괄 작업을 처리할 때 사용

중간수준 스케줄링

중지와 활성화로 일부 프로세스를 중지 상태(보류 상태에 해당)로 전환하여 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막음

보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화됨

저수준 스케줄링

가장 작은 단위의 스케줄링으로, 아주 짧은 시간에 일어나기 때문에 단기 스케줄링이라고도 부름

준비 상태의 프로세스 중 하나를 골라 실행 상태로 전환

실행 상태의 프로세스를 대기 상태로 전환

대기 상태의 프로세스를 준비 상태로 전환

전환하는 기준에 따라 시스템의 성능에 많은 영향을 끼침

스케줄링의 목적

공평성 : 모든 프로세스가 자원을 공평하게 할당받아야 함

효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 함

안정성 : 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 할당하여 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호

확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 함, 시스템 자원이 늘어나는 경우 시스템에 반영해야 함

반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구 안에 반응해야 함

무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안됨

스케줄링 시 고려 사항

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

선점형 스케줄링

프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식

대표적인 예로 인터럽트 처리

컨텍스트 스위칭 같은 부가적인 작업으로 인해 오버헤드가 발생하는 것이 단점

프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합

대부분의 저수준 스케줄러는 선점형 스케줄링 방식을 사용

비선점형 스케줄링

프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

프로세스가 종료되거나 자발적으로 대기 상태로 전환하기 전까지 계속 실행됨

선점형 스케줄링보다 작업량이 적고 컨텍스트 스위칭 오버헤드도 적음

CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어짐

과거 일괄 작업 시스템에서 사용하던 방식

선점형 스케줄링 방식의 스케줄러에도 비선점형 프로세스(예를 들면, 시스템을 백업하는 프로세스)가 있을 수 있는데 비선점형 프로세스의 우선순위를 낮게 설정하여 선점형 프로세스에 영향을 덜 미치도록 함

프로세스 우선순위

일반적으로 CPU 스케줄러는 우선순위가 높은 프로세스부터 처리

일반적으로 커널 프로세스가 일반 프로세스보다 우선순위가 높음

CPU 집중 프로세스와 입출력 집중 프로세스

CPU 버스트 : CPU를 할당받아 실행하는 작업

입출력 버스트 : 입출력 작업

CPU 집중 프로세스

CPU 버스트가 많은 프로세스

입출력 집중 프로세스

입출력 버스트가 많은 프로세스

CPU 집중 프로세스보다 입출력 집중 프로세스의 우선 순위를 높이면 시스템의 효율이 향상됨

입출력 집중 프로세스는 잠깐 CPU를 사용한 후 대기 상태로 전환하기 때문에 다른 프로세스가 CPU를 사용할 수 있어 CPU의 사용률이 올라감

사이클 훔치기 : 입출력 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우

전면 프로세스와 후면 프로세스

전면 프로세스

GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스

현재의 입력과 출력을 사용하는 프로세스

사용자의 요구에 즉각 반영해야 하므로 우선순위가 높음

후면 프로세스

사용자와 상호작용이 없는 프로세스

사용자와 상호작용이 없으므로 우선순위가 낮음

다중 큐

준비 상태의 다중 큐

프로세스마다 중요도가 다르며 PCB에 표시됨

CPU 스케줄러는 매번 모든 PCB를 탐색하는 것은 비효율이므로 우선순위에 따라 여러 개의 큐를 관리

준비 큐의 개수와, 여러 개의 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 일은 스케줄링 알고리즘에 따라 달라짐

고정 우선순위 방식

운영체제가 프로세스에 우선순위를 부여하면 끝날 때까지 변경되지 않는 방식

구현하기 쉽지만 우선순위를 고정하면 시스템의 변화에 대응하기 어려워 작업 효율이 떨어짐

변동 우선순위 방식

프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식

구현하기 어렵지만 시스템의 효율을 높일 수 있음

반전 우선순위

프로세스의 낮은 우선순위를 높은 우선순위로 변경하는 것

변동 우선순위 방식의 한 예

우선순위가 낮은 프로세스 P1이 중요한 자원을 사용하고 있다면 자원을 독점하여 사용하기 때문에 이 자원을 사용하려는 다른 프로세스는 P1이 작업을 마칠 때까지 기다려야 함

이때 P1의 우선순위를 높이면 다른 프로세스보다 작업을 빨리 끝낼 수 있으며, 자원을 기다리던 다른 프로세스의 작업도 원활하게 진행됨

대기 상태의 다중 큐

해당 입출력장치의 완료 인터럽트가 발생한 경우 모든 PCB를 탐색하는 것은 비효율이므로, 요구한 입출력장치에 따라 여러 개의 큐를 관리

일반적으로 큐에 삽입된 순서대로 처리되지만, 입출력장치가 CPU나 메모리보다 느리기 때문에 작업 속도를 높이기 위해 작업 순서를 바꿔 나중에 요청된 작업이 먼저 처리되기도 함

준비 큐는 한 번에 하나의 PCB를 꺼내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 PCB를 동시에 꺼내어 준비 상태로 전환

시스템에는 많은 입출력장치가 있기 때문에 입출력이 동시에 끝날 경우 여러 개의 인터럽트가 한 번에 처리되는데, 인터럽트 벡터라는 자료구조를 사용

인터럽트 벡터에는 동시에 완료된 입출력 정보와 처리 방법이 담겨 있는데, 이 정보에 따라 완료된 PCB는 모두 준비 상태로 이동

스케줄링 알고리즘

비선점형 알고리즘 : FCFS, SJF, HRN

선점형 알고리즘 : 라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐

둘 다 가능 : 우선순위 스케줄링

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

CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법

처리량 : 단위 시간당 작업 시간을 마친 프로세스의 수로, 수치가 클수록 좋음

대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간으로, 짧을 수록 좋음

응답 시간 : 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간으로, 짧을 수록 좋음

반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간, 대기 시간 + 실행 시간

알고리즘의 효율성을 평가할 때 CPU 사용률과 처리량은 계산하기 어렵기 때문에 주로 대기 시간, 응답 시간, 반환 시간을 계산

FCFS(First Come First Served)

준비 큐에 도착한 순서(선입선출)대로 CPU를 할당하는 비선점형 방식

초기 일괄 작업 시스템에서 사용

큐가 하나이기 때문에 모든 프로세스의 우선순위가 동일

단순하고 공평

호위(Convoy) 효과 : 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들이 기다리므로 시스템의 효율성이 떨어짐

• 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져서 작업 효율이 떨어짐

SJF(Shortest Job First)

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식

FCFS보다 평균 대기 시간이 줄어들어 호위 효과를 완화하고 시스템의 효율성을 높임

운영체제가 프로세스의 종료 시간을 정확히 예측하기 어려움

작업 시간이 길어 계속 연기되는 Starvation 현상이 발생 가능

• Aging으로 프로세스가 연기되는 상한선을 정하는 방식으로 해결 가능

HRN(Highest Response Ratio Next)

SJF 스케줄링에서 Starvation 현상을 완화하기 위해 만들어진 비선점형 알고리즘

우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간

Starvation 현상을 완화했지만 여전히 발생하기 때문에 많이 사용되지 않음

라운드 로빈(Round Robin)

프로세스가 할당 받은 타임 슬라이스 동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤에서 다시 기다리는 방식

선점형 알고리즘 중 우선순위가 적용되지 않은 가장 단순하고 대표적인 방식

타임 슬라이스 동안 사용한 후 다른 프로세스에게 CPU를 양보하기 때문에 Convoy 효과가 줄어듦

라운드 로빈 같은 선점형 스케줄링 방식에는 컨텍스트 스위칭 비용이 추가되기 때문에 비선점형 알고리즘과 시간이 비슷하면 비효율적인 알고리즘

효과적으로 작동하기 위해 컨텍스트 스위칭에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함

• 타임 슬라이스가 클 경우 FCFS와 유사
• 타임 슬라이스가 작을 경우 컨텍스트 스위칭 비용 증가

SRT(Shortest Remaing Time)

기본적으로 라운드 로빈 스케줄링을 사용하고 CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택하는 선점형 알고리즘

SJF보다 평균 대기 시간이 짧음

현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산해야 함

Starvation 현상 발생 가능

우선순위 스케줄링

프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘

어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있음

고정 우선순위 알고리즘 : 우선순위가 고정되어 단순하게 구현할 수 있지만 시스템의 상황을 반영하지 못해 효율성이 떨어짐

변동 우선순위 알고리즘 : 우선순위를 계속 계산하고 변경되어 시스템이 복잡하지만 시스템의 상황을 반영하여 효율적임

준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스를 실행하기 때문에 Starvation 현상 발생 가능

프로세스의 우선순위를 매번 변경해야 하는 비용 발생

이러한 단점에도 불구하고 우선순위는 시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정됨

다단계 큐(Multilevel Queue)

우선순위에 따라 여러 개의 준비큐를 사용하고 각 단계의 큐에 라운드 로빈을 사용하는 알고리즘

고정형 우선순위를 사용하며 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨

우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식

• 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있음

우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는 Starvation 현상 발생 가능

다단계 피드백 큐(Multilevel Feedback Queue)

우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식

일반적으로 사용하고, 변동 우선순위 알고리즘의 전형적인 예

CPU를 사용한 프로세스는 우선순위가 낮아져 원래의 큐가 아닌 우선순위가 하나 낮은 큐의 끝으로 삽입

• 우선순위가 낮아지더라도 커널 프로세스가 일반 프로세스의 큐로 삽입되지는 않음

우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화

인터럽트 처리

과거에는 입출력장치가 거의 없었기 때문에 입출력을 요청하면 운영체제가 주기적으로 입출력장치를 직접 확인해서 처리했는데 이를 폴링이라고 함

다양한 입출력 장치가 개발되어 운영체제가 모든 입출력을 관리하기 어려워지자 입출력을 요청하고 입출력이 완료되면 이벤트를 발생시켜 이 사실을 알리게 되었는데 이를 인터럽트라고 함

인터럽트는 입출력뿐만 아니라 광범위하게 사용됨

동기적 인터럽트와 비동기적 인터럽트

동기적(사용자) 인터럽트는 프로세스가 실행 중인 명령어로 인해 발생

비동기적 인터럽트는 실행 중인 명령어와 무관하게 발생, 하드디스크 읽기 오류, 메모리 불량과 같은 하드웨어적인 오류

동기적 인터럽트 예

프로그램상의 문제 때문에 발생하는 인터럽트(다른 사용자의 메모리 영역에 접근하는 경우, 오버플로우나 언더플로우에 의해 발생하는 경우 등)

컴퓨터 작업자가 의도적으로 프로세스를 중단하기 위해 발생시킨 인터럽트

입출력장치 같은 주변 장치의 조작에 의한 인터럽트

산술 연산 중 발생하는 인터럽트(어떤 수를 0으로 나눔)

인터럽트 처리 과정

시스템에는 많은 인터럽트가 존재하고, 각각의 인터럽트에는 인터럽트 번호(IRQ)로 식별

인터럽트는 여러 개가 동시에 발생할 수 있으며, 동시에 발생하는 인터럽트를 인터럽트 벡터에 저장

인터럽트가 발생하면 인터럽트 벡터 내에 번호가 0에서 1로 변경됨

인터럽트 벡터에는 각 인터럽트를 처리하는 함수(인터럽트 핸들러)가 연결되어 있음

1. 인터럽트가 발생하면 현재 실행 중인 프로세스는 대기 상태가 되며, 재시작하기 위해 현재 프로세스 관련 정보를 임시로 저장

2. 인터럽트 컨트롤러가 실행되어 인터럽트의 처리 순서를 결정
    여러 개의 인터럽트가 동시에 발생했다면 인터럽트의 우선순위를 고려하여 중요한 인터럽트부터 처리하도록 순서 결정

3. 벡터에 등록된 인터럽트 핸들러를 실행

4. 인터럽트 핸들러가 끝나면 프로세스가 다시 실행되거나 종료됨

인터럽트와 이중 모드

커널 모드는 운영체제와 관련된 커널 프로세스가 실행되는 상태

사용자 모드는 사용자 프로세스가 실행되는 상태

커널 모드로 전환되는 경우

• 사용자 프로세스가 커널의 기능을 사용하기 위해 시스템 호출을 요청한 후 대기 상태로 전환되고 커널 프로세스는 요청받은 작업을 처리(자발적)
• 인터럽트가 발생했을 때(비자발적)

이중 모드

운영체제가 두 모드를 전환하며 일 처리 하는 것

사용자 프로세스가 커널 모드에서 실행되지 못하도록 하여 운영체제가 자원을 보호하기 위해 사용하는 기법