운영체제 이론과 실제 책을 읽고 정리한 내용입니다.

제1장 운영체제의 개념 및 발전과정

필요성

  • 운영체제의 가장 기본적인 역할 중 하나는 사용자로 하여금 하드웨어인 입/출력 장치를 편리하게 사용할 수 있게 하는 것이다.

주요 기능

  • 컴퓨터의 사용자와 하드웨어 사이의 중개 역할을 담당(사용의 편리성)
  • 컴퓨터의 자원 관리자 역할을 담당(자원 효율성)
  • 컴퓨터의 자원과 사용자 정보를 보호(컴퓨터 보안성)

운영체제의 유형 (사용자 프로그램들이 실행되는 방식 기준)

  • 단일 프로그래밍 일괄 처리 시스템(Single-stream Batch Processing Systems)
    • 사용자는 컴퓨터에 접근할 수 없었으므로 프로그램을 천공카드에 작성하여 관리자에게 제출하였고, 운영체제는 오직 하나의 프로그램만을 적재하여 차례차례 실행시켰다.
    • 사용자 프로그램이 입/출력을 요구 했을 때 상대적으로 매우 빠른 처리 속도를 가진 프로세서(CPU)를 대기시켜야 했으므로 허비하는 시간(Idle Time)이 많았다.
  • 다중 프로그래밍 일괄 처리 시스템(Multiprogramming Batch Processing Systems)
    • 사용자 프로그램을 동시에 여러 개 적재시켜 실행중인 프로그램이 입/출력을 요구하면 그 입/출력 작업이 진행되는 동안에 다른 프로그램을 실행시켜줌으로써 프로세서의 유휴 시간을 줄였다.
  • 시분할 시스템(Time-Sharing System)
    • 여러 개의 프로그램들을 짧게 분할된 시간(Time Quantum 또는 Time Slice) 동안 조금씩 번갈아 가면서 처리함으로써 사용자에게 시스템을 독착지하고 있다는 느낌을 준다.
  • 병렬 처리 시스템(Parallel Processing Systems)
    • 여러 개의 프로세서(CPU)를 이용하여 여러 개의 프로그램을 병렬로 처리한다.
    • 성능향상과 결함허용(Fault Tolerance)에 목적이 있다.
    • 병렬 처리(Parallel Processing)는 어느 시점을 기준으로 보았을 때, 2개 이상의 프로그램을 처리하는 것을 말한다.
    • 동시 처리(Concurrent Processing)는 어느 시점을 기준으로 보았을 때는 오직 하나의 프로그램을 처리하지만, 이들을 번갈아 처리함으로써 일정 기간 동안 결국 여러 개의 프로그램을 처리하는 것을 말한다.
  • 실시간 시스템(Real-Time Systems)
    • Hard Real-Time System: 프로그램들의 처리 마감 시한을 엄격하게 보장한다.
    • Soft Real-Time System: 실시간 처리를 위한 최소한의 서비스만을 제공한다. (유닉스, 리눅스, 윈도우와 같은 상용 운영체제)

제2장 운영체제를위한 배경지식

컴퓨터 시스템 구조

컴퓨터는 크게 중앙처리장치(처리기, CPU), 주기억장치(Main Memory) 그리고 주변장치(Peripheral Device)들로 구성된다.

  • Bus
    • System Bus: 컴퓨터를 구성하는 주요 부위(모듈)를 연결하여 정보를 주고 받는 통신 선로
    • Address Bus: CPU가 메모리의 정보를 읽거나 쓰고자 할 때, 메모리 주소를 전달하기 위한 버스
    • Data Bus: 메모리에 기록할 데이터나 메모리에서 읽힌 데이터를 전달하는 용도로 사용
    • Control Bus
  • 주기억 장치(Main mermory): Bit 8개의 묶음으로 이루어진 Byte 단위로 주소가 배정된다.
  • 기계 명령어(Machine Instruction): 연산코드(Operation code)와 피연산자(Operand)로 구성되고, 연산코드 부분의 크기는 연산종류의 개수를 결정한다. 피연산자 부분의 크기는 최대 메모리 용량을 결정한다. 피연산자는 연산코드에 따라 주소, 상수, 레지스터 번호 등 다양하게 해석된다.
  • 기계 사이클(Machine Code)
    • CPU가 반복적으로 처리하는 동작 패턴으로 명령어 인출(Fetch), 명령어 해석(Decoding), 피연산자 호출(Operand), 연산 처리(Execution) 주기로 크게 4개의 스텝으로 구성된다.
    • 명령어 처리를 위한 기계 사이클이 끝나면, CPU는 자동적으로 다음 명령어에 대한 기계 사이클을 개시한다. 이 때, 처리할 명령어가 저장된 메모리 주소는 CPU내의 PC(Program Counter) 레지스터에 의해 관리된다.
  • 레지스터(Register): 값을 저장할 수 있는 곳
    • 소량의 데이터를 특별한 용도로 저장하는 곳으로 크게 CPU 레지스터와 특수기능 레지스터(Special Function register) 그리고 입/출력 레지스터로 분류된다.
    • CPU 레지스터: 주로 연산을 위한 피연산자의 임시 저장 용도
    • 특수기능 레지스터: 컴퓨터의 상태 설정 등 특수 용도
    • 입/출력 레지스터: 주변 장치와의 입/출력 창구 용도

인터럽트

CPU에 전달되는 사건 신호(Event Signal)로서, 주로 전용 회선으로 전달된다.

  • Interrupt Servcie Routine(ISR): 인터럽트가 발생하면 CPU는 처리 중이던 명령어 순서를 보관한 후, 사전에 설정된 주소로 점프하여 새로운 처리를 시작하게 된는데 이 부분을 ISR 혹은 Interrupt Handler라 부른다.
  • Interrupt Vector: 인터럽트들은 고유의 번호에 의해 식별되고, 이들 인터럽트들에 대응되는 인터럽트 핸들러들의 주소가 표 형태로 기록된 부분
  • 인터럽트 우선순위(Interrupt Priority): 여러 개의 인터럽트가 동시에 발생하거나, 인터럽트 핸들러 처리 도중 다른 인터럽트가 발생하면 CPU는 우선순위에 따라 처리 순서를 결정
  • 인터럽트 사이클(Interrupt Cycle): CPU 기계 사이클의 맨 마지막 단계에 추가되며, 인터럽트 발생을 조사한다.
  • 인터럽트 유형: Device Interrupt, Error Interrupt, Software Interrupt

이중 연산 모드

사용자 모드(User Mode 혹은 프로그램 모드(Program Mode))와 시스템 모드(System Mode 혹은 수퍼바이저 모드(Supervisor Mode))가 식별되는 경우를 이중 연산 모드(Dual Operation Mode)라 하고, 시스템 모드에서만 실행 가능한 기계 명령어를 특권 명령어(Privileged Instruction)라 한다.

입/출력

입력은 CPU 등 처리기가 주변장치 레지스트로부터 주기억장치로 데이터를 복사하는 작업이고, 출력은 입력과 반대로 주기억장치의 데이터를 주변장치 레지스터로 복사하는 작업이다.

  • 입/출력 장치의 식별
    • 메모리 대응 입/출력(Memory Mapped IO): 입/출력 레지스터를 주기억장치의 일부에 대응시켜 메모리 접근 방법과 동일한 방법을 이용하여 입/출력 처리
    • 격리된 입/출력(Isolated IO): 입/출력 레지스터가 주기억장치 영역과 완전히 분리되어 메모리 접근 방법과 상이한 고유의 입/출력 기계 명령어를 이용하여 입/출력 처리
  • 입/출력 처리 알고리즘
    • 한 번에 이루어질 수 있는 입/출력량은 주변장치에 따라 다르나, 일반적으로 단말기와 같이 1바이트 단위로 이루어지는 경우를 문자 입/출력 장치, 하드 디스크와 같이 수십~수백 바이트 단위로 이루어지는 경우를 블록 입/출력 장치라고 함
    • 바쁜 대기 입/출력(Busy Waiting IO): 운영체제(CPU)가 입/출력 상태 레지스터 값을 지속적으로 읽어 입/출력의 진행, 완료, 유휴 등의 상태를 확인하여 완료나 유휴 상태가 되면 다음 입/출력을 진행
    • 인터럽트 기반 입/출력(Interrupt-driven IO): 운영체제는 입/출력 명령 레지스터에 입/출력 명령을 기록한 후 다른 사용자 프로그램으로 점프함으로써 입/출력이 진행되는 동안 CPU는 다른 일을 수행한다. 입/출력이 완료되어 CPU에게 인터럽트가 전달되면, CPU는 해당 인터럽트 핸들러에서 다음 입/출력을 진행한 다음 수행 중이던 원래 사용자 프로그램으로 복귀한다.
    • DMA 입/출력(Direct Memory Access IO): 운영체제는 메모리 주소, 입/출력 데이터의 크기, 입/출력 명령 등 세 가지를 DMA 처리기에 설정하고 다른 사용자 프로그램으로 점프한다. DMA는 CPU대신 인터럽트 기반으로 입/출력을 진행하고, 전체 입/출력이 완료되면 CPU에 완료 인터럽트를 전달한다.

저장장치 계층(Storage Hierarchy)

저장장치 들은 접근속도 용량 가격 관점에서 살펴보면 일련의 계층을 이룬다.

  • 레지스터(Register)
  • 캐시(Cache): 상대적으로 저속/대량/저가인 저장장치의 데이터를 임시로 복사/보관함으로써 컴퓨터 성능을 크게 향상시키는 고속/소량/고가의 기억장치이다. 일반적으로 캐시는 CPU와 주기억장치 사이에서 주기억장치를 돕는 저장장치를 말한다.
  • 주기억장치(Main Memory): CPU보다 접근 속도가 느리고, 용량이 제한적이며, 휘발성이어서 데이터의 영구 저장이 불가능하기 때문에 이를 보완하기 위해 컴퓨터에는 하드디스크 등 다양한 기억장치가 보조적으로 사용
  • 전자 디스크(Electronic Disk)
  • 자기 디스크(Magnetic Disk)
  • 광 디스크(Optical Disk)
  • 자기 테이프(Magnetic Tape)

제3장 프로세스 및 스레드 관리

프로세스 정의

하드디스크에 저장된 프로그램이 처리 혹은 실행되기 위해서는 주기억장치로 적재되어 운영체제하의 관리 객체로 등록되어야 하는데, 이 상태를 프로세스라 부른다. 즉, 프로세스는 처리중인 프로그램이라고 정의할 수 있다.

  • 속성
    • 프로세스 고유번호(PID: Process Identification Number)
    • 프로세스 메모리 정보
    • 프로세스 상태(Process Status): 운영체제가 CPU를 어느 프로세스에게로 점프시켜 줄 것인가(배정이라고도 함)를 탐색하기 위해서는 프로세스들이 입/출력이 완료되기를 기다리고 있는지 아니면 CPU 할당을 기다리고 있는지 등의 프로세스 현재 상태가 필요
    • 프로세스 진행지점(Process Counter): 선택된 프로세스를 처리 중이던 CPU는 운영체제가 설정해 둔 타이머 인터럽트에 의해 언젠가는 그 프로세스를 떠나게 되는데, 이 때 다음 실행할 기계 명령어에 대한 주소를 기록해두어야만 다음 기회에 연속된 처리가 가능
    • 프로세스 문맥(Process Context): 모든 연산은 CPU 안에서 이루어진다. 어느 연산이 끝난 시점에서 인터럽트에 의해 CPU가 운영체제로 되돌아가면 조금 전 프로세스에서 생상된 CPU 레지스터 값들이 파괴된다. 이렇게 되면 해당 프로세스를 나중에 다시 연속해서 실행할 때 이전의 연산 결과 값들을 잃어 올바른 진행이 불가능하다. 이와 같이 현재 진행중인 프로세스의 연산 명령어들에 의해 CPU 안에서 생산되어 보관 중인 값들을 프로세스 문맥이라 하는데, 이런한 문맥은 CPU가 진행 중이던 프로세스를 떠날 때 보관되었다가 나중에 처리를 재개하기 직전에 복원되어야 한다.
    • 프로세스 우선순위(Process Priority)
    • 프로세스 자원목록(Process Resource): 메모리, 디스크 파일, 사운드, 그래픽 등 물리적인 자원들과 세마포, 네트워크 포트, 시그널 등 논리적인 자원들을 사용할 수 있는데, 프로세스별 할당 자원들이 관리되어야만 사후 자원의 회수 및 재활용이 가능하다.
    • 회계 정보(Accounting Information)
  • 프로세스 관리 블록(Process Control Block, PCB): 운영체제가 프로세스 관리를 위해 필요한 모든 정보를 기록하는 표를 PCB라 하는데, 그 수는 곧 생성 가능한 최대 프로세스 수를 의미한다. PCB에 주로 위에 언급한 프로세스 속성들이 저장된다.

프로세스 상태(Process Status)

  • 준비(Ready) 상태: CPU 배정 차례를 기다리고 있는 상태
  • 실행(Running) 상태: CUP 배정, CPU의 제어 흐름이 해당 프로세스로 점프함을 의미하는데 이 과정을 Dispatch라고도 한다.
  • 대기(Blocked) 상태: 프로세스가 입/출력을 하기 위해 대기상태로 오게 된다. 이와 같이 어떤 사건을 기다려 대기 상태로 전환되는 경우는 입/출력 외에도 시간, 동기화 신호, 외부 센서 신호등 다양한데 이들은 모두 운영체제의 도움으로 이루어진다.
  • 보류(Suspended) 상태: 외부 프로세스의 보류 요청 혹은 메모리 부족 등 심각한 상황이 발생하면 운영체제에 의해 자체적으로 발생하기도 한다.
  • 종료(Terminated) 상태: 프로세스를 종료 상태로 전환하고 제거 준비를 한다. 이 상태의 프로세스를 좀비(Zombie)라고 한다.

스레드(Thread)란?

프로세스 구성 요소 중 하나이다. 프로세스의 다른 구성 요소인 메모리(기계 명령어 및 데이터)를 따라 흐르는 개념적인 개체이다. 스레드가 한 개인 경우, 프로세스라 부른다.

다중 스레드 프로세스(Multi-thread Process)

메모리에 적재된 프로그램의 시작 점(Entry point)이 여러 곳이다. 예를 들어 CPU1은 main1 함수부터 시작하고, CPU2는 main2 함수부터 시작해 각자의 제어 흐름에 따라 독립적으로 진행되는데 이들 각각이 스레드이다. 스레드들이 동일한 기계 명령어를 실행하더라도 연산 과정이 고유하게 유지된다. 피연산자를 위한 최종 목적 주소가 분리되기 때문이다. 이렇게 스레드들의 연산 고유성을 유지하기 위한 저장공간을 Stack 영역이라고 부르고, 스레드가 시작할 때 할당된다. 그러나 다중 스레드가 반드시 CPU가 여러개 있어야 하는 것은 아니다. 운영체제가 CPU 배정 단위를 프로세스가 아닌 스레드로 세분화 시키기 때문이다. 이 때 프로세스 개념을 스레드를 위한 자원그릇(Resource Container)으로 제정의 된다. 다중 스레드 프로그래밍의 유의사항은 전역 변수를 동시에 참조하는 경우, 올바른 계산을 위한 동기화 장치가 필요하다. 전역 변수는 상대 주소가 아니라 절대 주소로 참조되기 때문이다.

프로세스 및 스레드를 위한 운영체제 서비스(기능)

  • 프로세스 생성 및 제거
  • 스레드 생성 및 제거
  • 프로세스간 통신(Inter-Process Communication: IPC)
    • 프로세스들은 완전 분리/독립되어 있어서 서로 간에 간섭하거나 정보를 주고 받을 수 없다.
    • 거대한 프로그램을 여러 개의 작은 프로그램으로 분리할 경우, 이들 사이에는 통신할 수 있는 수단이 필요하게 되는데 이를 프로세스 간 통신이라 부른다.
    • IPC의 대표적인 예: 파이프, 메시지 큐, 공유 메모리, 세마포, 소켓 등
  • 프레세스 통제(Process Control)
    • 운영체제는 사용자에게 실행 중인 프로그램을 통제할 수 있는 수단을 제공한다.
    • 프로세스 통제의 전형적인 유형으로 강제종료, 일시중지, 실행재개, 약속처리, 우선순위 변경 등을 들 수 있다.
    • 유니스/리눅스에서는 프로세스 통제를 위해 kill() 시스템 콜과 kill 명령어를 제공한다.

WEB> 멀티 프로세스보다 멀티스레드를 사용하는 이유: 시스템 자원의 효율(Stack 영역을 제외하면 스레드끼리 같은 영역 메모리 사용), 통신 부담(IPC 어려움) but, 멀티 스레드는 전역변수 동기화 문제 주의

WEB, Python> 파이썬에서 멀티 스레드: GIL로 인해 사실상 한 개의 스레드만이 파이썬 코드 실행 가능(파이썬에서 멀티 스레드를 이용한 병렬처리는 무의미)

제4장 프로세서(CPU) 관리

프로세서(CPU) 관리의 개념

  • 프로세서: 주기억장치에 저장된 프로그램(기계 명령어)을 읽어가면서 처리하는 CPU
  • 프로세서 관리: 다수의 프로세스들이 준비 상태에 있을 때, 운영체제가 CPU로 하여금 어느 프로세스를 먼저 처리하도록 할 것인가를 결정하기 위한 제반 사항
  • 단계별 처리 스케줄링
    • 장기 스케줄링(Long-term Scheduling): 대기 중인 프로그램들 중, 먼저 시작(적재)시킬 프로세스 선택
    • 중기 스케줄링(Midium-term Scheduling): 적재된프로세스들 중, 처리를 잠시 보류할 프로세스들 선택
    • 단기 스케줄링(Short-term Scheduling): 준비 상태의 프로세스들 중, CPU를 먼저 할당할 프로세스 선택
  • CPU 스케줄링 전략의 목표 및 기준
    • 사용자 관점에서의 CPU 스케줄링 목표 지표
      • 응답시간(Response Time): 사용자 데이터 입력 후, 출력이 이루어질 때까지의 소요 시간
      • 반환시간(Turnaround Time): 프로그램 제출(혹은 시작) 후, 끝날 때까지 소요되는 시간
      • 대기시간(Waiting Time): 프로세스들이 준비 상태로 대기열에서 기다린 시간의 총합
    • 시스템 관점에서의 CPU 스케줄링 목표 지표
      • CPU 사용률(CPU Utilization): 총 경과 시간 대비 CPU가 순수하게 사용자 프로세스를 수행한 시간의 비율
      • 처리율(Throughput): 단위 시간당 처리된 프로세스의 개수
    • 사용자 관점과 시스템 관점의 CPU 스케줄링 목표 지표는 상호 배타적 관계에 있는 경우가 일반적

CPU 스케쥴링이 이루어지는 시기

프로세스가 입/출력을 요구할 때, 프로세스가 종료를 요구할 때, 높은 우선순위의 프로세스가 나타났을 때, 주어진 CPU 실행 시간(Time Quantum)이 초과되었을 때

CPU 스케쥴링의 전략의 분류

  • 용어: 계산 위주(CPU Bounds) 프로세스, 입/출력 위주(IO Bounds) 프로세스
  • 비선점(Non-Preemption)형 CPU 스케줄링: 실행 중인 프로세스가 자율적으로 CPU를 반납할 때까지 CPU를 계속 점유하여 실행하는 운영체제 환경이다. 다시 말하면, 일단 CPU가 할당되면, 해당 프로세스가 입/출력 및 종료를 요구하지 않는 한 중단 없이 실행을 지속한다. 이런 유형의 운영체제에 입/출력이 적은 계산 위주(CPU Bounds) 프로세스가 다수 적재되어 있다면 다른 프로세스들의 응답 시간은 매우 저조할 것이다. 반대로 거의 대부분의 프로세스가 입/출력 위주(IO Bounds)라면 모든 프로세스들이 CPU를 어느 정도 규칙적으로 번갈아 할당받을 수 있기 때문에 응답 시간이 크게 나쁘지 않을 것이다.
  • 선점(Preemption)형 CPU 스케줄링: 자율적 CPU 반납은 물론 더 높은 우선순위의 프로세스나 시간 초과 등에 의한 타율적(강제적) CPU 반납도 시행. 선점형 운영체제 환경에서는 어떤 프로세스도 일정 시간(타임 퀸텀) 이상 동안 연속해서 CPU를 점유할 수 없기 때문에 계산 위주 프로세스가 많이 적재되어 있다 하더라도, 모든 프로세스들의 반응시간 성능을 평균 이상으로 유지할 수 있다.

CPU 스케쥴링 전략들

  • 선입 선처리(FCFS: First-Come First-Served) 스케줄링: 비선점형 CPU 스케줄링으로 호위 효과(Convoy Effect)에 의해 입/출력 장치나 CPU의 이용률이 낮아질 수 있다.
  • 최단 작업 우선(SJF: Shortest Job First) 스케줄링: 비선점형 CPU 스케줄링으로, 평균 대기 시간 및 평균 응답 시간은 매우 우수하지만 CPU 혹은 입/출력 장치의 이용률 저하 현상과 큰 프로세스에 대한 CPU 할당이 지연되는 기아(Starvation) 현상이 나타날 수 있다.
  • 최단 잔여 시간 우선(SRTF: Shortest Remaining Time First) 스케줄링: SJF의 선점형 스케줄링 전략으로 평균 대기 시간 및 응답 시간을 더욱 개선하고 CPU나 입/출력 장치의 이용률 저하 현상을 억제하지만, 큰 프로세스의 기아 현상은 더욱 악하시킬 수 있다.
  • 최고 응답률 우선(HRRF: Highest Response Ratio First) 스케줄링: SJF나 SRTF 스케줄링의 기아 현상을 예방하기 위하여, CPU 버스트 시간 대비 상대적 응답 시간인 응답률이 높은 프로세스를 먼저 처리한다.
  • 라운드 로빈(RR: Round Robin) 스케줄링: 전형적인 선점형 스케줄링 전략으로, 모든 프로세스에게 동일한 최대 CPU 점유 시간(타임 퀸텀)을 설정하고 처리중인 프로세스의 CPU 실행 시간이 타임 퀸텀을 초과하면 CPU를 강제로 회수하여 다음 프로세스에게 할당하는 방식이다. 대화식 시스템에 적합하고, 타임 퀸텀의 크기가 목표 성능 지표에 영향을 미친다.
  • 다단계 큐(MQ: Multi-level Queue) 스케줄링: 프로세스 특성별로 준비 큐를 독립적으로 운영하고, 각 준비 큐에는 서로 다른 우선 순위와 타임 퀸텀을 설정한다. 각 준비 큐내에서는 FCFS, RR 등 다른 스케줄링 전략을 적용한다.
  • 다단계 피드백 큐(MFQ: Multi-level Feedback Queue) 스케줄링: 프로세스들의 성향을 지속적으로 관찰하여 반영함으로써 대화 프로세스들의 응답시간, 전체적인 CPU 및 입/출력 장치 이용률 등의 목표 성능들이 일정 수준 이상으로 유지될 수 있도록 한다. MQ나 MFQ 스케줄링 전략에서 우선 순위가 높은 입/출력 위주 프로세스들이 월등하게 많고 우선 순위가 낮은 계산 위주 프로세스들이 소수라면 이들 소수 프로세스들은 CPU를 할당받을 기회가 극도로 낮아지는 기아 상태가 나타날 수 있는데, 이 문제는 대기 시간을 준비 큐의 우선 순위 산정에 고려하는 노화(Aging) 기법으로 해결될 수 있다.

제5장 프로세스 동기화

동시처리와 병렬처리, 그리고 경쟁상황(Race Condition)

현대 운영체제는 다수의 프로세스를 적재하여 처리하는 다중 프로그래밍 환경이다. 다중 프로그래밍 환경에서 프로세스들은 기본적으로 엄격하게 분리되어 상호관섭이 불가능하며 비동기적으로 진행되지만, 프로세스들이 메모리를 공유 하거나(공유 메모리) 다중 스레드를 지원할 경우, 여러 개의 프로세스(이하 스레드 포함)들이 변수 등 동일한 자원에 대한 접근을 경쟁하는 상황이 일어날 수 있어 동기화가 필요하다. 이와 같은 접근 경쟁 상황은 동시처리와 병렬처리의 두 가지 처리 형태에서 나타난다.

  • 동시처리(Concurrent Processing)와 경쟁상황: 공유 변수가 포함된 수식 계산을 완전히 마치지 못한 상태에서 CPU 스케줄링이 일어날 때 발생
    • 동시처리: 하나의 CPU가 여러 개의 프로세스를 조금씩 빠른 속도로 번갈아 처리하는 형태(즉, 어느 순간에 살펴보면 오직 한 프로세스만 실행)
  • 병렬처리(Parallel Processing)와 경쟁상황: 공유 변수를 참조하는 프로세스들이 처리될 때 발생(동시처리와 동일한 문제 발생)
    • 병렬처리: 두 개 이상의 CPU가 여러 프로세스를 나누어 동시에 처리하는 형태(어느 순간 CPU 개수만큼 프로세스들이 CUP를 할당받아 실행 중)

임계영역(Critical Section)과 상호배제(Mutual Exclution)

  • 임계 영역: 프로그램에서 경쟁상황이 발생할 수 있는 부분
  • 상호 배제: 임계영역에 어떤 경우에도 오직 하나의 프로세스만 실행 가능하도록 제한하는 개념

상호 배제에 기반한 프로세스 진행을 프로세스 동기화(Process Synchronization)라 한다.

  • 상호 배제 목적을 이루기 위해 요구되는 조건
    • 계속진행: 임계 영역을 실행중인 프로세스가 없을 때, 계속 진행 가능
    • 상호배제: 이미 임계 영역에 진입해 실행 중인 프로세스가 있을 때, 다른 프로세스 진입 대기
    • 대기한정: 임계 영역 진입을 위해 대기 중인 프로세스들에게 모두 공평한 진입 기회가 주어져야 한다. 현저하게 오래 대기하는 프로세스가 있어서는 안된다.

상호 배제 장치는 소프트웨어와 하드웨어 두 가지 방법으로 구현 할 수 있다.

미완성 소프트웨어 상호배제 시도들

  • 공통 깃발(flag) 체크 방법
  • 자기 깃발 체크 방법
  • 자기 차례(turn) 지키기 방법

성공적 소프트웨어 상호배제 방법

  • Dekker 알고리즘: 자기 깃발 체크 방식 + 자기 차례 지키기 방법을 조합하여 알고리즘 완성. 두 개의 프로세스 사이에서 상호배제를 이룰 수 있는 최초의 소프트웨어 동기화 기법
  • Peterson 알고리즘: Dekker 알고리즘을 이해하기 쉽고 간결하게 재현한 것
  • Lamport 빵집 알고리즘: 손님들은 프로세스들이고, 빵 진열대는 임계 영역에 해당하며, 번호표는 장금장치에 해당한다. 이 때 대기표는 기본적으로 증가한다. n 개의 프로세스들 사이에서 상호배제를 얻는 소프트웨어 기법

상호배제를 위한 하드웨어 지원(TAS, SWAP)

  • TSA 기계 명령어: “읽기-판단-1을 저장”의 과정을 하나의 기계어로 실행하고 JNZ(Jump if Not Zero) 반복 체크
  • SWAP 기계 명령어: 두 변수의 값을 원자적으로 교환

세마포(Semaphores)

앞의 상호배제 기법은 모두 바쁜 대기(Busy Waiting, 계속 사용 가능 여부를 체크하는 것)를 기반으로 임계영역을 보호한다. 이러한 잠금 장치를 스핀록(Spin Lock)이라 부르는데, 임계 영역이 길면 스핀록에 의한 CPU 사용낭비가 심하고, 임계영역에 진입한 프로세스가 CPU 스케줄링에 의해 스위칭되거나 비정상적으로 종료되면 이에 따른 파급효과가 크다는 단점이 있다. 이러한 이유로 스핀록은 매우 조심스럽게 제한적으로 사용되어야 하고, 이를 개선할 수 있는 보다 보편적 개념의 잠금 장치가 필요하다.

  • 세마포의 개념: Dijkstra에 의해 제안된 추상적 잠금 장치로 (깃발을 내리는) 잠금 연산 P()와 (깃발을 올리는) 해제 연산 V()에 의해 접근 가능한 (깃발을 의미하는) 정수 변수 S를 일컫는다. 세마포 S에 대한 연산 P()와 V() 각각의 처리 절차 전체는 하나의 임계영역으로 이루어져 원자적으로 처리된다. 만약 두 프로세스가 거의 동시에 P(S) 연산을 시도했다면, 이들 중 한쪽은 깃발을 내려놓고 진행을 계속하지만, 다른 한 쪽은 내릴 깃발이 없으므로 세마포 큐에서 대기한다. P(S) 연산에 성공하여 임계영역을 마친 프로세스는 깃발을 다시 올려놓기 위해 V(S) 연산을 해주어야 하는데, 이 때 V(S) 연산은 세마포에서 대기하는 프로세스가 있다면 깃발을 그대로 두고 하나의 프로세스를 선택하여 준비상태로 만들어 줌으로써 P(S) 연산을 성공하고 임계영역에 진입하도록 한다. 세마포는 임계영역 진입을 위해 대기하는 동안 바쁜 대기를 하지 않기 때문에 CPU 사용 낭비를 줄일 수 있으나, P(S) 연산에서의 대기 상태 전환으로 인한 CPU 스케줄링이 요구되므로 문맥 교환 부담이 따른다. 따라서 스핀록과 세마포 사이의 선택은 임계영역의 크기와 성격에 따라 결정한다.
  • 이진(Binary) 세마포와 카운팅(Counting) 세마포
    • 이진 세마포: 임계 영역 보호를 위한 상호배제 장치로 사용 + 두 프로세스 간에 진행의 보조를 맞추기 위한 수단
    • 카운팅 세마포: 일정 개수로 한정된 자원의 소진여부를 표시하는 자원 카운팅 용도로 사용(예: 세마포 변수 S를 n으로 초기화하고 버퍼가 필요한 프로세스는 P(S)를 반납할 프로세스는 V(S)를 하도록 하면, 버퍼의 현재 사용 현황을 알 수 있을 뿐 아니라 가용 버퍼가 없을 때에는 자동으로 대기할 수 있어서 편리)

프로세스 동기화 예

  • 생산자-소비자 문제(Producer-Consummer Problem)
  • 식사하는 철하자들 문제(Dining Philosophers Problem)

모니터(Monitors)

프로세스 동기화 문제의 세마포는 P()와 V() 연산을 아주 주의 깊게 사용해야 교착상태 등의 오류가 발생하지 않는다. 모니터는 세마포의 상호배제 용법을 보다 편리하고 안전하게 활용할 수 있도록 프로그래밍 언어 수준에서 제공되는 고수준(High level)의 상호배제 구조다.

모니터는 함수 형태로 구분된 임계영역들의 모임이고, 모니터 내의 임계영역 함수들은 어느 순간에 오직 하나만 수행될 수 있다. 따라서 다수의 프로세스들이 동일 모니터 내의 임계영역 함수를 동시 다발적으로 호출하더라도 모니터에 의해 제공되는 상호배제 기능에 의해 오직 하나의 프로세스만이 모니터에 진입할 수 있고, 다른 프로세스들은 모니터 외부 큐에서 대기한다.

  • 모니터의 내부(조건) 큐: 모니터에 진입한 프로세스가 어떤 조건(자원)을 기다려야 하는 경우, 모니터 내부에 마련된 큐에서 대기하고(wait(q)), 이런 프로세스들은 모니터 진입한 다른 프로세스에 의해(signal(q)) 실행이 재개된다.

제6장 교착 상태

교착 상태(Deadlocks)란?

교착 상태의 주요 원인은 자원이 부족하거나 자원을 질서 없이 사용하는 경우 발생한다. 컴퓨터에서는 프로세스들이 진행하는 과정에서 운영체제를 통하여 메모리나 주변 장치 등 자원에 대한 접근을 요구하게 되는데, 이 때 자원의 점유와 요구 상태에 따라 관련된 프로세스들이 영원히 기다리는 교착상태가 발생할 수 있다.

  • 컴퓨터 자원 관리 모델: 프로세스들은 시스템 콜을 통해 운영체제에게 자원을 요청하거나 반납한다.
  • 교착 상태의 필요조건
    • 자원의 베타적 사용(Mutual Exclusion): 할당된 자원은 해당 프로세스에 의해 독점적으로 사용되어 다른 프로세스는 사용할 수 없다.
    • 자원의 점유 대기(Hold & Wait): 일부 자원을 점유한 채 또 다른 자원을 요구하는 것(부분할당, Partial Allocation이라고도 함)
    • 자원의 비선점(No Preemption): 일단 할당된 자원은 사용이 완료되기 전에 강제로 회수할 수 없다.
    • 자원에 대한 환형 대기(Circular Wait): 환영대기 조건의 만족 여부는 자원 할당 그래프(RAG: Resource Allocation Graph)를 그려서 확인 할 수 있다.
  • 교착 상태 대응 방안
    • 예방(Prevention), 회피(Avoidance), 탐지 및 복구(Detection & Recovery), 방치(Don’t care)

교착 상태 예방(Prevention)

네 가지 필요조건 중 어느 하나라도 만족하지 않는 자원 할당 정책을 고안하면 그 시스템에서는 교착 상태가 아예 발생하지 않는다.

  • 자원의 베타적 사용 제거: 사운드 카드와 같이 공유가 근본적으로 불가능한 자원이 많다. -> 자원 속성상 제거 불가능
  • 자원의 점유 대기 조건 제거: 자원의 일부를 점유한 채 또 다른 자원을 요구하는 상황을 배제하기 위해서 필요한 모든 자원을 한꺼번에 할당받아야 한다. 하지만 기아 상태가 발생할 수 있을 뿐만 아니라 자원의 활용도를 크게 저하시킨다. -> 이론적으로는 제거 가능하나 많은 비용을 동반하여 현실적으로 실현 불가능
  • 자원의 비선점 조건 제거: 프로세스들이 사용 중인 자원을 어느 때라도 강제로 회수할 수 있게 한다. -> 자원 속성상 제거 불가능
  • 자원에 대한 환영 대기 조건 제거: 모든 자원에 할당 순서를 부여하고 프로세스들은 그 할당 순서에 따라 자원을 요청하도록 한다. 하지만 나중에 사용할 자원을 미리 할당 받아 놓아야 하므로 자원 활용도가 낮아지고, 기아상태가 발생할 수 있으며 프로그래머가 자원들의 할당 순서를 인식하고 있어야 하므로 이종시스템간의 소프트웨어에 재사용이 곤란해진다. -> 이론적으로는 제거가 가능하나 많은 비용을 동반하여 현실적으로 실현 불가능

결론적으로 교착 상태 예방은 현실적으로 불가능하다.

교착 상태 회피(Avoidance)

좀 더 적은 비용으로 교착 상태를 피해나가는 방안으로 자원을 할당하기 직전 교착 상태가 발생할 가능성이 있는지 살펴보고 교착 상태 발생 가능성이 없는 안전 상태이면 자원을 할당하고, 발생 가능성이 있는 불완전 상태이면 자원 할당을 하지 않고 대기하도록 한다.

  • 안전(safe) 상태와 불완전(unsafe) 상태: 모든 프로세스들의 자원 사용량에 대한 자세한 정보를 바탕으로 현재의 자원할당 이후에 교착 상태가 발생할 가능성이 있는지를 판단한 결과, 교착 상태를 피해갈 수 있으면 안전(safe) 그렇지 않으면 불완전(unsafe) 상태라 한다.
  • 자원 할당 그래프의 예약 간선을 활용한 안전 상태 판별 및 교착 상태 회피: 모든 프로세스들에 대한 자원 요구 정보가 알려져 있다면, 자원 요청이 있을 때 마다 할당 이후에 환형 대기 상태가 일어나는지 자원 할당 그래프를 그려서 예측할 수 있고, 만약 안전하지 않다면 자원 요청을 보류하여 교착 상태를 피한다.
  • Dijstra의 은행가 알고리즘(Banker’s Algorithm)에 의한 교착 상태 회피: Dijstra 알고리즘은 이미 할당된 자원, 남아있는 자원 그리고 앞으로 추가로 사용될 자원을 분석하여 요구된 자원 할당 이후에도 교착 상태를 피해갈 수 있는 할당 시나리오가 존재하는지 판별함으로써 교착 상태를 피한다.

교착 상태 탐지 및 복구(Detection & Recovery)

교착 상태 회피 방법은 프로세스별로 어떤 자원을 어느 만큼 사용할 것인가에 대한 사전정보가 알려져야 한다. 즉, 프로그래머가 운영체제에 어떤 자원이 있으며 그 중 사용하려는 자원이 어느 것인지를 숙지해야 하는데, 현실적으로 거의 불가능하다. 따라서 자원 할당 과정에서 교착 상태를 전혀 고려하지 않고 교착 상태가 발생했는가를 주기적으로 조사하여 처리하는 방법이다.

  • 교착 상태 탐지: 교착 상태 탐지의 한 방법으로 자원 할당 그래프에서 어떤 자원에 대해서도 대기하지 않는 프로세스를 반복적으로 제거한 결과 모든 프로세스가 제거되면 교착 상태가 아니라고 판정하는 알고리즘을 적용할 수 있다.
  • 교착 상태 복구: 교착 상태에 관계된 자원들을 강제로 회수하는 방법 외에는 없고, 이 경우 해당 프로세스들은 진행을 후퇴(Rollback)하거나 처음부터 다시 시작해야 한다. 회수 자원의 단위는 자원별 혹은 프로세스별로 설정할 수 있다.

교착 상태 방치(Don’t care)

대부분의 상용 운영체제는 교착 상태에 관한 어떠한 서비스도 제공하지 않고, 사용자들에게 그에 대한 처리 및 대비를 맡긴다.

  • 운영 체제는 자원을 요청하는 프로세스를 대기시키지 않고 성공/실패 코드를 반환하여 사용자가 대처하도록 한다.
  • 프로그램 개발자는 자원 할당에 실패한 경우 무한 대기하지 않도록 예외 처리로 대비해야 한다.
  • 메시지 및 패킷 송/수신, 사건 대기 등의 논리적 처리 절차에 따른 교착 상태는 전적으로 프로그램 개발자의 책임 하에 예방, 회피, 탐지 및 복구 등의 방안이 수립되어야 한다.

제7장 메모리(주기억장치)관리

메모리 관리

  • 프로그램 전체 적재
    • 연속 할당 (Contiguous): 메모리의 연속된 공간에 적재하는 방법
      • 고정분할 할당
      • 가변분할 할당
    • 비연속 할당 (Non-contiguous): 메모리의 이곳저곳에 조금씩 나누어 적재하는 방법
      • 페이징
      • 세그먼테이션
      • 페지화된 세그먼테이션
  • 프로그램 일부 적재(가상 메모리, Virtual Memory)
    • 연속 할당
      • 오버레이
    • 비연속 할당
      • 페이징 (요구 페이징)
      • 페이지화된 세그먼테이션 (요구 페이징)

논리 주소와 물리 주소(Logical Address, Physical Address)

단일 프로그래밍 메모리 관리

단일 프로그래밍 환경에서는 기본적으로 하나의 프로그램 전체를 연속적으로 적재하고 운영체제 보호를 위해 경계 레지스터(BR: Boundary Register)를 사용한다. 프로그램의 크기가 메모리 용량을 초과하면 프로그램을 분리하여 필요한 부분을 차례로 중첩 적재하는 오버레이(Overlay) 기법을 사용한다.

고정 분할(Fixed Partition)과 가변 분할(Variable Partition)

  • 고정 분할: 메모리를 미리 고정적으로 분할시켜 놓고, 공간이 비워질 때마다 새로운 프로그램을 적재하는 방법
    • 단점: 사용자 프로그램의 크기에 꼭 맞는 메모리 공간을 제공할 수 없기 때문에 대부분의 경우 메모리 일부를 활용하지 못하는 내부 단편화(Internal Fragmentation)에 의한 메모리 낭비를 피할 수 없고, 실행 가능한 프로그램의 최대 크기가 제한된다.
  • 가변 분할: 고정 분할의 내부 단편화 문제를 극복하기 위해 비어있는 공간을 나누어 정확히 프로그램의 크기 만큼만을 할당하는 방법
    • 할당과 반납이 진행되면서 크기가 아주 작은 빈 분할(Hole)들이 늘어나 이들이 비어 있는데도 불구하고 활용되지 못하는 상황이 발생하는데 이를 외부 단편화(External Fragmentation)라 부른다.
    • 외부 단편화 문제를 완화시키기 위해 최적/최악/최초/순서 적합 등 적합한 할당 정책을 선택하고 인접 빈 분할들에 대한 병합과 분할의 재배치에 의한 통합을 실시한다.

페이징(Paging)과 세그먼테이션(Segmentation)

프로그램을 원래 모양 그대로 메모리에 적재하는 환경에 적합한 고정 분할이나 가변 분할과는 달리, 프로그램을 여러 개의 조각으로 분리하여 메모리에 분산하여 적재하는 방법이 있는데 페이징과 세그먼테이션이 그것 들이다.

  • 페이징: 프로그램 전체를 일정한 크기의 작은 조각으로 분리하여 메모리에 적재한다. 이 때, 각각의 조각을 페이지(Page)라 하고 페이지 시스템에 따라 보통 512~8K 바이트 크기를 갖는다. 페이징에서는 프로그램을 페이지 단위로 분리하여 적재하므로 메모리 할당 단위 또한 당연히 페이지 단위로 이루어져야 한다. 즉, 메모리 페이지 크기와 동일한 조각으로 분할되어야 하는데 그 각각을 페이지 프레임(Page Frame)이라 부른다.
    • 페이지 시스템의 가장 큰 장점은 단편화에 의한 메모리 낭비가 적다는 점이다. 할당 단위가 페이지 크기만큼 일정하므로 외부 단편화에 의한 메모리 낭비가 전혀 없고, 마지막 페이지에서 약간의 내부 단편화 낭비가 발생한다.
    • 페이지가 어느 페이지 프레임에 적재되어 있는지는 페이지 테이블에 기록되어 관리되고 이를 이용하여 논리 주소가 물리 주소로 변환된다. 이 때, 페이지 테이블 접근에 따른 성능 저하를 보완하기 위하여 TLB(Translation Look-aside Buffer)를 사용한다.
    • 페이지 테이블 자체가 너무 클 때는 다단계 페이징 기법으로 페이지 테이블을 여러 개로 분리한다.
    • 페이지 테이블 구조를 이용하면 페이지에 대한 보호와 공유를 쉽게 이룰 수 있다.
  • 세그먼테이션: 사용자 프로그램을 균일한 작은 조각(페이지)으로 분리하는 것이 아니고, 프로그램 이미지를 구성 부위별 특성에 따라 분리한다는 점에서 다른데, 이 때 동일한 특성으로 구별되는 묶음들을 세그먼트라 부른다. 보통 프로그램 이미지는 텍스트(기계 명령어 부분), 데이터(전역 변수), 스택(지역 변수 및 서브 루틴 호출 관리), 공유 라이브러리 등 최대 7~8개의 세그먼트로 구성된다. 세그먼트는 프로그램 이미지를 논리적인 특성을 기준으로 분리한 단위를 의미하므로 하나의 큰 덩어리라고 말할 수 있고, 그들의 크기는 각각 다르고 비교적 크다.
    • CPU 주소로부터 세그먼트 번호가 쉽게 도출될 수 있도록, 세그먼트들의 논리 주소를 연속성에 구에받지 않는 일정한 규칙에 의해 부여한다.
    • 페이징에서와 마찬가지로 세그먼트 테이블 구조에 의한 보호와 공유가 용이하다.

페이지화 된 세그먼테이션(Segmentation with Paging)

세그먼테이션의 가장 큰 문제점 중의 하나는 각각의 세그먼테이션을 가변 분할 정책으로 연속적으로 할당함으로써 피할 수 없는 외부 단편화 문제이다. 반면에 페이징에서는 프로그램 이미지가 너무 작은 조각들로 분리되어 페이지별 보호 등의 관리를 위한 부담이 크다. 이와 같은 두 시스템의 단점을 보완하기 위한 방법으로, 논리적 특성에 따라 분리된 세그먼트를 다시 페이지 단위로 분리하여 적재하는 페이지화된 세그먼테이션 시스템이 도입되었는데, 현대 범용 운영체제는 거의 모두 이 방법을 사용한다.

제8장 가상 메모리 관리

가상 메모리(Virtual Memory)의 개념

가상 메모리는 분리된 프로그램 조각 중 필요한 일부 몇 개만 적재함으로써 얻어질 수 있다. 가상 메모리 관리 기법은 페이징을 기반으로 한다.

요구 페이징(Demand Paging)

요구 페이징은 적재되지 않은 페이지를 참조할 때 페이지 부재 트랩(Page Fault Trap)에 의해 적재한다. 페이지를 디스크에서 읽어 들이는 과정을 스왑 인(Swap in), 적재된 페이지를 디스크로 저장하는 과정을 스왑 아웃(Swap out)이라 하고, 이들 두 과정을 스와핑(Swapping)이라 한다. 스왑 아웃은 메모리가 부족할 때 이루어지고, 스왑 아웃시킬 페이지를 선택하는 일을 페이지 교체라 부른다.

페이지 부재 트랩(Page Fault Trap) 처리

페이지 부재 트랩은 적재되지 않은 페이지에 대한 참조에 의해 발생하고, 트랩 핸들러는 해당 부재 페이지를 전재(스왑 인)하고 참조 기계 명령어를 재개시킨다. 이 때, 프로세스의 처리는 페이지 입/출력 시간만큼 지연된다.

페이지 교체(Page Replacement)

메모리가 부족한 상태에서 새로운 페이지를 적재하고자 할 때에는 이미 적재된 페이지 중 어느 것을 선택하여 스왑 아웃시켜 공간을 확보해야 하는데 이를 페이지 교체라 한다. 이와 같이 페이지 교체가 필요할 때는 프로세스의 처리가 더욱 지연될 수 밖에 없다. 스왑 아웃시킬 페이지로 어떤 것을 선택하느냐의 문제는 시스템의 성능을 좌우하는 중요한 사항이다.

  • 최적(OPT: Optimal) 페이지 교체: 미래에 가장 오랫동안 참조되지 않을 페이지를 교체하는 이상적인 기법이지만, 프로세스의 미래 진행을 예측할 수 없으므로 구현이 불가능하다.
  • FIFO(First-In First-out) 페이지 교체: 가장 먼저 적재된 페이지. 즉, 적재된 지 가장 오래된 페이지를 교체한다. 만약 그것이 현재 참조가 왕성하게 일어나고 있는 페이지라면 최악의 선택이 된다.
  • LRU(Least Recently Used) 페이지 교체: 적재된 모든 페이지를 참조 순서에 따라 스택으로 관리하며, 가장 오래 동안 사용되지 않은 페이지를 교체한다. 모든 페이지들을 일렬로 순서화 시켜야 하므로 관리 부담이 크다.
  • NUR(Not Used Recently) 페이지 교체: 최근에 사용되지 않은 페이지를 교체하는 전략으로 참조 순서 대신 최근 참조 성향을 그룹으로 분류한다. 여기서 참조 성향이란, 전체 참조 비트가 클리어되는 주기 동안 이루어진 참조 형태를 말한다. 참조 비트는 하드웨어에 의해 쉽게 구현될 수 있으므로 현대 운영체제는 대부분 이 기법을 사용한다. 교체 대상 페이지는 교체 우선 순위 등급에 따라 해당 그룹에서 임의로 선택된다.
  • 2차 기회(Second Chance) 페이지 교체: FIFO에서 한창 참조 중인 페이지를 교체해 버리는 최악의 선택을 예방한다. 교체 대상인 페이지에 대한 최근 참조가 있었다면 이 번에는 교체하지 않고 다음번 대상이 될 때까지 메모리에 계속 머무를 수 있는 기회를 준다. 다음번에도 참조가 있었다면 교체가 계속 유보된다. 가급적 참조가 있는 페이지의 교체를 지양한다는 점에서 NUR의 취지와 동일하다.
  • LFU(Least Frequently Used)와 MFU(Most Frequently Used) 페이지 교체: LFU는 참조 횟수가 가장 적은 페이지를 MFU는 참조 횟수가 가장 많은 페이지를 각각 교체한다.

페이지 버퍼링(Page Buffering)

몇 개의 가용 페이지 프레임을 미리 풀로 관리하고 있다가 페이지 교체가 필요할 때 우선 풀에서 빈 페이지 프레임을 즉시 할당하고, 사후에 새로운 교체 페이지를 선택하여 디스크 기록 후 풀에 등록하는 것을 페이지 버퍼링이라 한다. 페이지 버퍼링은 교체될 페이지의 디스크 저장과 새로운 페이지 적재 사이에서 지간적 완충을 제공함으로써 페이지 교체에 따른 프로세스 지연 시간을 줄인다.

페이지 프레임 할당(Allocation of Page Frames)

프로세스별 최대 할당 페이지 프레임 수를 지키기 위해서는 새로운 페이지의 적재와 동시에 하나의 페이지는 반납되어야 하는데 이는 곧 내부 교체를 의미한다. 이런 경우를 고정 할당이면서 내부 할당이라 부른다. 이와 같의 프로세스에게 열마만큼의 페이지 프레임을 어디서 할당할 것인가의 문제를 페이지 프레임 할당 정책이라 한다.

  • 최소 할당 페이지 프레임 수: 프로세스가 원활하게 처리될 수 있도록 할당되어야 할 최소한의 페이지 프레임 수는 기계 명령어의 타입 등 하드웨어 측면과 메모리가 낭비되지 않도록 페이지 프레임 할당을 최소화시키는 방법론 등 소프트웨어 측면에서 결정되어야 한다.
  • 균등 할당(Equal Allocation)과 비례 할당(Proportional Allocation): 균등할당은 모든 프로세스에게 동일한 수의 페이지 프레임을 할당하고, 비례할당은 프로세스의 기준 특성에 비례하여 할당한다.
  • 지역 할당(Local Allocation)과 전역 할당(Global Allocation): 지역할당은 교체 페이지를 프로세스 내에서 선택하고, 전역할당은 모든 프로세스를 대상으로 교체 페이지를 선택한다.

스래싱(Thrashing)

페이지 부재가 너무 자주 일어나 프로세스가 실행에 보내는 시간보다 페이지 교체에 더 많은 시간을 소비하는 현상으로 그 근본 원인은 처리 중인 프로세스에 할당된 페이지 프레임이 충분하지 못하여 페이지 부재 빈도가 매우 높아지기 때문이다. 이는 너무 많은 프로세스가 적재되어 프로세스별 할당 가능한 페이지 프레임 수가 줄어드는 상황에서 연유한다. 스레싱을 예방하기 위해서는 각 프로세스가 필요로 하는 최소한의 페이지 프레임을 할당하면서, 지역 할당 전략을 접목하여야 한다.

작업 집합(Working Set)과 페이지 부재 빈도(PFF: Page Fault Frequency) 모델

  • 프로그램 지역성(Locality of Program) 이론: 시간적 지역성(Temporal Locality)은 최근 참조된 페이지가 다시 참조될 가능성이 높다는 성질이고, 공간적 지역성(Spacial Locality)는 최근 참조된 페이지와 인접한 페이지가 다시 참조될 가능성이 높다는 성질을 말한다.
  • 작업 집합 관리와 페이지 부재 빈도(PFF: Page Fault Frequency): 스레싱 예방과 메모리 낭비 예방의 두 가지 상충되는 목표를 달성하기 위해서는 작업 집합의 크기가 적절하게 유지되어야 한다. 지역성 특성을 가진 프로그램의 진행 상황에 따라 작업 집합을 관리하기 위한 방법으로 페이지 부재 빈도를 들 수 있다.즉, 페이지 부재 빈도가 높아지면 작업 집합을 확장하고, 반대로 페이지 부재 빈도가 낮아지면 작업 집합을 축소한다.

기타 논점들

가상 메모리를 실현하기 위한 요구 페이징 시스템이 원할하게 운영되기 위해서는 기본적으로 효과적인 페이지 교체 및 페이지 프레임 할당 정책의 선택이 중요하지만 그밖에도 고려되어야 할 사항들이 있다.

  • 페이지 크기: 페이지 크기는 논리 주소의 물리 주소 변환 과정의 비트 연산 편의성을 위해 2의 n제곱 형태로 결정하며 n은 9~14의 값을 갖는다. 즉, 페이지 크기는 512~16K 바이트이다.
    • 페이지 크기가 클 때의 대체적인 장/단점 (페이지 크기가 작을 때는 반대로 생각하면 됨)
      • 페이지 테이블의 엔트리 수가 감소하므로 페이지 테이블을 위한 메모리 절약
      • 스와핑을 위한 입/출력 대기 시간을 줄일 수 있다. 이를테면 1K 바이트 페이지 두 개를 따로따로 두 번 입/출력 할 때보다 2K 바이트 페이지를 1개를 한번에 입/출력할 때 대기 시간이 더 짧은데, 그 이유는 디스크의 물리적 구조에 따른 실린더(트랙) 탐색 시간(Seek Time)을 한 번으로 줄일 수 있기 때문이다.
      • 페이지 단위가 크므로 페이지 교체 및 전재의 횟수가 줄어들어 전체적인 성능 향상에 도움을 준다.
      • 정보의 적중률이 낮아진다. 즉, 꼭 필요한 부분 외에 앞/뒤에 불필요한 부분이 포함될 가능성이 높아 결국 메모리 낭비 요인이 될 수 있다.
      • 프로그램의 마지막 페이지에서 나타나는 내부 단편화 부분이 커져, 이 또한 메모리 낭비 요인이 된다.
  • 응용 프로그램의 구조: 요구 페이징에 의한 가상 메모리 기법은 프로그램의 지역성이 없다면 설 땅이 없다. 다시 말하면, 사용자들이 개발하는 응용 프로그램의 구조가 가상 메모리의 성능에 영향을 미칠 수 있다.
    • 다차원 배열 접근: 동일 행에 대한 모든 열을 참조 한 후 다음 행으로 진행하는 구조(row major)가, 그 반대의 경우보다 지역성을 높이기 때문에 가상 메모리 관리 부담 관점에서 우수
    • 함수 배치: 프로그램의 진행 과정상 호출 관계가 긴밀한 함수들을 가까이 배치하는 것이 기계 명령어 인출 과정에서 참조되는 메모리의 지역성을 높일 수 있다. 대부분의 언어들에서 목적 프로그램이 파일 단위로 생성되어 링크되므로 밀접한 관계가 있는 함수들은 가급적 동일 파일에 작성하는 것이 좋다.
    • 테이블 인덱싱(Table Indexing): 해싱 결과를 레코드의 위치로 활용하는 테이블 구성 방식을 해시 테이블이라 한다. 이런 테이블은 레코드의 위치 탐색 자체는 용이하지만, 여러 개의 레코드를 지속적으로 탐색할 경우 참조 레코드의 위치 분포가 넓어 지역성이 낮아지고, 이로 인해 가상 메모리 관리 부담이 늘어난다.
    • 프로그래밍 언어: 프로그램의 구현 과정에서 사용자에게 임의의 주소에 대한 자유로운 참조를 허용하는 언어는 가상 메모리 관리 부담 관점에서 불리하다. 예를 들면, C 언어의 경우 포인터에 의한 메모리 접근 방식이 프로그램의 지역성을 저해할 가능성이 있다. 또한 C++/JAVA 등 객체 지향 언어는 다형성 제공을 위한 실행중 overloading/overiding에 의해 함수의 순차 실행이 어려워 지역성이 절차 지향 언어보다 낮다.
    • 입/출력 버퍼 잠금
    • 실시간 처리