• 파일 시스템 구현
• 디렉터리 구현
  • 선형 리스트
  • 해시 테이블
• 디스크 할당
  • 연속 할당
  • 연결 할당
  • 색인 할당

파일 시스템 구현

운영체제는 파일 내용에 대한 접근을 요청하는 프로세스를 위해 open()과 close() 시스템 호출을 구현합니다.
본 장에서는 파일 시스템 연산을 구현하는데 사용되는 구조와 연산에 대해 알아봅시다.

다음 그림은 파일 시스템에서 디스크 와 메모리 에 어떤 정보들이 들어있는지를 나타내 줍니다.

디렉터리 구현

선형 리스트

해시 테이블

디스크 할당

연속 할당

연결 할당

색인 할당

• 디렉터리 구조
  • Single Level Directory
  • Two Level Directory
  • Tree Structured Directory

디렉터리 구조

Single Level Directory

Two Level Directory

Tree Structured Directory

컴퓨터의 프로세스 중에서 협력적 프로세스 는 실행 중인 다른 프로세스의 실행에 영향을 주거나 받는 프로세스입니다. 이러한 협력적 프로세스는 논리주소 공간을 직접 공유하거나, 파일 또는 메세지를 통해서만 데이터를 공유할 수 있습니다. 이 경우 두개 이상의 프로세스가 동시에 특정 데이터에 접근하면 데이터가 비일관성을 가지게 될 수 있습니다. 본 강의에서는 이렇한 논리주소 공간을 공유하는 협력적 프로세스의 질서있는 실행을 보장하여 데이터의 일관성을 유지 하는 다양한 메커니즘을 다루어 보겠습니다.

두개의 프로세스가 동일한 공유된 변수에 접근하는 프로그램을 동작시킨다면 어떤 프로세스가 어떤 순서로 동작함에 따라 결과가 달라지게 됩니다. 하지만 두 프로세스가 비동기적으로 실행되는 경우 실제로 변수가 어떻게 변화하게 되는지 부정확해지는 일이 생기게 됩니다. 이런 문제는 두개의 프로세스가 동시에 같은 변수에 접근 하기 때문입니다.

여러 개의 프로세스가 동일한 자료를 접근하여 조작하고 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 조건 이라고 합니다. 이를 해결하기 위해서는 한 순간에 하나의 프로세스만이 공유 변수를 조작하도록 보장해야 합니다.

임계영역 문제(The Critical Section Problem)

여러 개의 프로세스가 동작하는 처리기를 생각해 봅시다. 각 프로세스는 임계영역(Critical Section) 이라고 부르는 코드 부분을 가지고 있으며, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하거나, 테이블을 갱신하거나 파일을 쓰거나 하는 등의 작업을 실행합니다. 각 프로세스는 자신의 임계영역으로 진입하려면 진입허가를 요청해야 한다. 이러한 요청을 구현하는 코드 부분을 진입 영역(entry section) 이라고 부르며 임계영역 뒤를 퇴출영역(exit section) 이 따라올 수 있고, 코드의 나머지 부분을 통틀어 나머지 영역 이라고 부릅니다.

이러한 임계영역 문제를 해결하기 위해 서는 다음의 세 가지 요구 조건 을 충족해야 합니다.

1. 상호 배제(mutual exclusion)
   프로세스 P가 자신의 임계영역에서 실행되고 있다면, 다른 프로세스들은 그들 자신의 임계영역에서 실행될 수 없습니다.
   즉, A라는 프로세스가 자신의 임계영역에서 실행되고 있다면, 프로세스 B는 자신의 임계영역에서 실행될 수 없습니다.
2. 진행(Progress)
   자신의 임계영역에서 실행 중인 프로세스가 없는 상태에서 자신의 임계영역으로 진입하려고 하는 프로세스가 있다면, 나머지 영역에서 실행 중이지 않은 프로세스들만 임계영역으로 진입할 프로레스를 결정하는데 참여할 수 없으며, 이 선택은 무한정 연기될 수 없습니다.
   가령, A, B, C 라는 프로세스가 모두 자신의 임계영역에서 실행되고 있지 않은데 프로세스 A가 자신의 임계영역으로 진입하려고 한다면, 반드시 A는 나머지 영역 에서 실행중이지 않아야 하며, 유한한 시간 내에 임계영역으로 진입하고자 하는 프로세스를 선택해야 합니다.
3. 한정된 대기
   프로세스가 자기의 임계영역에 진입하려는 요청을 한 뒤 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계영역에 진입할 수 있는 횟수에 제한이 있어야 합니다.
   예를 들어, 프로세스 A, B, C 가 있을 때 프로세스 A가 자신의 임계영역으로 진입하려고 진입 영역 에서 요청을 한 뒤 실제로 임계영역에 진입하기 전까지는 프로세스 B, 프로세스 C 가 임계영역에서 무한히 많이 진입하도록 되어서는 안되고 몇번 진입 후에는 반드시 프로세스 A에게 진입 할 순차가 와서, 프로세스 A가 한정된 대기를 해야 합니다.

운영체제에서 임계영역을 다룰 때는 두가지 상황을 고려해야 합니다.
바로, 선점형 커널 인가 혹은 비선점형 커널 인가에 대한 문제입니다.

선점형 커널 은 프로세스가 커널 모드에서 실행되는 동안 선점되는 것을 허용하며, 비선점 커널 은 커널 모드에서 실행되는 프로세스의 선점을 허용하지 않고, 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 실행됩니다.
비선점형 커널 의 경우에는 커널 안에서 실행중인 프로세스가 명백하게 하나 밖에 없기 때문에 경쟁조건을 걱정하지 않아도 되지만, 선점형 커널 의 경우는 그렇지 않기 때문에 경쟁 조건이 발생하지 않는 것을 보장할 수 없습니다.

특히, SMP(Symmetric Multi-Processing) 구조에서는 서로 다른 처리기의 두 프로세스가 동시에 커널 모드에 있을 수 있기 때문에, 선점형 커널을 설계하는 것은 특히 어렵습니다.

피터슨의 해결방안

이러한 임계영역 문제 에 대한 고전적인 소프트웨어 기반 해결책인 피터슨의 해결안 에 대해 알아봅시다.

피터슨의 해결안은 임계영역과 나머지 영역을 번갈아 가며 실행하는 두 개의 프로세스로 한정됩니다.
쉽게 말하면 두 개의 프로세스를 구현할 때 특정 변수를 인덱스 값으로 놓아 해당 변수가 임계영역 에 대한 접근의 승낙여부를 공유하는 것입니다.
이를 위해서 다음과 같이 두개의 데이터 항목을 공유합니다.

1
2

int turn;
boolean flag[2]; //프로세스가 임계영역으로 진입할 준비가 됨을 나타냅니다.

위에서 turn 변수 는 임계영역으로 진입할 순번을 나타냅니다. 가령 turn이 i 이면 프로세스 i가 임계영역에서 실행되는 것을 나타냅니다.
flag 변수 는 프로세스가 임계영역으로 집입할 준비가 되었다는 것을 나타냅니다. 가령 flag[i]가 true 라면 프로세스 i가 임계영역으로 들어갈 준비가 되었다는 것을 나타냅니다.

이렇게 동일한 변수를 공유하면 turn에 동시에 접근이 되더라도 하나의 값만을 나타내기 때문에 바로 다음에 접근한 값에 의해 덮어 씌워지게 되어 둘 중 하나의 값만이 될 것입니다.

위의 공유변수를 이용한 피터슨의 해결방안을 코드로 보이면 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10

while(true){
  flag[i] = TRUE;
  turn = j;
  while(flag[j] && turn ==j){
    임계영역 코드
  }

  flag[i] = FALSE;
  나머지 영역
}

위 코드는 프로세스 i가 임계영역에 접근하고자 하는 코드입니다. 위에서 flag[i]를 true로 지정함으로써 프로세스 i가 임계영역에 진입하고자 하는 것을 나타냅니다. 하지만 프로세스 i는 임계영역에 진입하기에 앞서 프로세스 j에게 먼저 입계영역에 접근하고 싶으면 접근하도록 turn을 돌려 줍니다. 만약 flag[j] 가 true 즉, 프로세스 j가 임계영역에 진입하고자 했다면 먼저 진입할 수 있습니다.

동기화 하드웨어

앞에서는 임계영역 문제에 대한 소프트웨어 기반의 해결책을 살펴보았다. 하지만 일반적으로 임계영역의 문제는 록(lock) 이라는 간단한 도구가 필요하다고 말할 수 있다. 경쟁 조건은 임계영역에서 록에 의해 보호함으로써 예방할 수 있습니다. 즉, 프로세스가 임계영역에 진입하기 전에 반드시 록 을 획득하도록 함으로써 임계영역 문제를 해결할 수 있습니다.

이를 간단히 코드로 표현하면 다음과 같습니다.

1
2
3
4
5
6

while(true){
  록 획득
    //임계영역
  록 방출
    //나머지 영역
}

위처럼 임계영역에 진입하기 전에 록을 획득 하고 임계영역을 나오면서 록을 방출 하는 방식을 잘 보여주고 있습니다.

이러한 임계영역의 문제에 대한 해결은 단일처리기 환경 혹은 다중 처리기 환경이냐에 따라 간단하거나 복잡할 수 있습니다.
만약 단일 처리기 환경 이라면 임계영역 문제는 쉽게 해결될 것입니다. 공유 변수가 변경되는 동안에는 하나의 프로세스가 진행되는 것을 막는 인터럽트 의 발생을 허용하지 않는 것이지요. 이렇게 하면 공유 변수가 변경되는 동안에는 인터럽트가 발생하지 않고 해당 프로세스는 방행 없이 자신의 코드를 실행시킬 것 입니다.
반면, 다중 처리기 환경 에서는 이것이 불가능 합니다. 다중 처리기에서 인터럽트를 막기 위해서는 모든 처리기에 인터럽트를 금지시키도록 해야 하는데 이것은 상당한 시간을 소비하기 때문이지요.

이러한 많은 이유들 때문에 현대의 많은 기계들은 한 워드의 내용을 검사하고 변경하거나 두 워드의 내용을 원자적으로 교환(swap) 할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서 특별한 하드웨어 명령어들을 제공합니다.

즉, swap을 통해 여러 처리기의 공유 변수를 원자적으로 변경시켜 록 을 획득하는 것 입니다.

세마포

위에서 제시한 하드웨어 기반의 해결방법은 응용 프로그래머가 사용하기에는 매우 복잡하기에 이를 극복하기 위해 세마포 라고 하는 동기화 도구를 이용할 수 있습니다. 세마포 S는 정수 변수를 포함하며 초기화를 제외하고는 오직 두개의 표준 연산 acquire(), release() 로만 접근이 가능합니다.

이러한 세마포의 간단한 구현은 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10

acquire(){
  while(value<=0){
    아무런 작업 하지 않음
  }
  value--;
}

release(){
  value++
}

위 코드를 분석해 봅시다.
먼저 세마포는 임계 영역에 진입하기 위해 acquire() 를 호출합니다. 하지만 이 경우 누군가가 먼저 acquire를 호출하여 value의 값이 0보다 작다면 아무런 작업도 하지 않고 대기합니다. 그러다가 다른 세마포가 release()를 호출하여 value값을 증가시켜 주면 while 문에서 벗어나고 또 다른 acquire() 요청을 막기 위해 value를 줄여 줍니다.

하지만, 여기서는 치명적인 문제가 있습니다.
바로 while 문에서 value를 검사하면서 바쁜 대기(busy waiting) 을 하고 있는 것이죠. 한 프로세스가 임계영역에 있으면, 자신의 임계영역에 진입하려는 다른 프로세스는 진입 코드를 계속 반복 실행해야 합니다. 이러한 현상을 프로세스가 록 을 기다리면서 회전한다고 하여 spinlock이라고 부르기도 합니다.

어떻게 하면 이런 바쁜대기(busy waiting) 을 없앨 수 있을까요?
바로 바쁜 대기를 하는 대신에 자기 자신을 봉쇄시키는 방법이 있습니다. 봉쇄 연산은 프로세스를 세마포에 연관된 대기 큐 에 넣고, 프로세스를 대기상태로 전환 합니다. 그 후에 제어가 CPU로 넘어가게 되고 추후 다른 프로세스가 release()연산을 실행하면 wakeup() 연산을 통해 재시작 됩니다. 이런 wakeup() 명령은 프로세스의 상태를 대기상태에서 준비완료 상태로 변경합니다. 그 뒤 wakeup 된 프로세스는 준비완료 큐에 넣어지게 됩니다.

이러한 block, wakeup 을 구현하기 위해 우리는 세마포를 한 개의 정수 value와 프로세스 리스트로 정의합니다. 프로세스를 기다려야 한다면 이 프로세스는 그 세마포의 프로세스 리스트에 추가됩니다. release() 연산은 프로세스 리스트에서 한 프로세스를 제거하여 그 프로세스를 깨워줍니다.

이를 구현한 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13

acquire(){
  value--;
  if(value<0){
    block();
  }
}

release(){
  value++;
  if(value<=0){
    wakeup(P);
  }
}

위 코드에서 block() 연산은 자기를 호출한 프로세스를 보류시키고, wakeup(P) 연산은 봉쇄된 프로세스 P의 실행을 재개시키며, 이들 두 연산은 운영체제의 기본적인 시스템 호출 로 제공됩니다.

• 메모리의 기본 개념
  • 기본적인 하드웨어 구조
  • 논리 주소와 물리 주소
  • 동적 적재
• 스와핑
• 연속 메모리 할당
  • 단편화
• 페이징
• 페이지 테이블의 다양한 구조
  • 계층적 페이징
  • 해시된 페이지 테이블
  • 역 페이지 테이블
• 세그먼테이션

주 메모리에는 여러개의 프로세스가 적재되어 있고, 운영체제는 이러한 프로세스를 효율적으로 처리하기 위해 메모리를 효율적으로 관리해야할 필요가 생겼습니다. 이를 위해 두가지 알고리즘인 페이징과 세그먼트 를 다루겠습니다. 최근 디자인이 하드웨어와 운영체제를 밀접하게 통합하고 있지만 본 장에서 설명하는 알고리즘은 대부분 하드웨어 지원을 필요로 합니다.

메모리의 기본 개념

기본적인 하드웨어 구조

메모리는 각각 주소가 할당된 일련의 워드 또는 바이트들로 구성되며 CPU는 PC(Program Counter)가 지시하는 대로 메모리로부터 다음 실행할 명령어를 가져오고, 필요한 경우 추가적인 데이터를 더 가져오거나 데이터를 메모리로 내보냅니다.

전형적인 명령 실행은 먼저 메모리로부터 한 명령어를 가져오는 데서부터 시작되어, 그 다음 명령어를 해독하고 메모리에서 피연산자를 가져와 피연산자에 대해 명령어를 실행합니다.

CPU가 주 메모리에 접근하기 위해서는 많은 CPU 클록 틱 사이클이 소요되며, 이 때문에 CPU가 명령어를 실행하지 못하고 대기하는 시간이 길어집니다. 이러한 상호아은 주 메모리 접근이 빈번하게 일어나는 경우에는 큰 문제가 되며 이를 해결하기 위해 캐기 라고 부르는 메모리 버퍼를 사용합니다.

메모리에 많은 프로세스들이 적재되어 있는데 각각의 프로세스가 다른 프로세스가 사용하는 메모리 영역을 침범하면 큰 문제가 생길 것 입니다. 즉, 각각의 프로세스는 독립된 메모리 공간을 가지고 특정 프로세스만 접근할 수 있는 메모리 영역을 하드웨어 단에서 정해주어야 할 필요가 있습니다. 이 문제는 기준(base)과 상한(limit)이라고 불리는 두개의 레지스터들을 사용 하여 해결합니다. 기준 레지스터 는 가장 작은 합법적인 물리 메모리 주소의 값을 저장하고, 상한 레지스터 는 주어진 영역을 크기를 저장합니다. 이러한 기준과 상한 레지스터는 여러가지 특권 명령을 사용하는 운영체제에 의해서만 적재됩니다.
하지만, 커널 모드 에서 실행되는 운영체제는 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 어떠한 제한도 받지 않는다.

프로세스는 실행되기 위해 디스크에서 메모리로 이동되고, 디스크에서 메모리로 들어오기를 기다리고 있는 프로세스 들은 입력 큐(input que) 를 형성합니다. 이 큐에서 하나의 프로세스를 선택하여 메모리로 적재한 후 실행합니다.

논리 주소와 물리 주소

CPU는 오로지 논리 주소 만을 사용하여 작동하는 반면 메모리가 취급하는 주소는 물리주소 입니다. 따라서 프로그램이 실행되기 위해서는 CPU가 다루는 논리주소가 물리주소로 변환이 되어야 하며 이것은 메모리 관리기(Memory Management Unit) 에 의해 처리됩니다.

이렇게 모든 논리주소와 물리주소 사이의 변환은 MMU에서 처리하며 CPU는 물리주소에 전혀 관심을 두지 않습니다. 즉, 사용자 프로그램은 실제적인 물리주소를 결코 알 수 없습니다.

동적 적재

일반적으로 CPU가 프로세스를 실행하기 위해서는 프로세스 전체가 메모리에 적재되어야 했다. 하지만 동적 적재 는 프로세스의 부분만이 메모리에 적재해도 프로세스를 실행 할 수 있도록 해 준다. 동적 적재에서 각 루틴은 실제로 호출되기 전까지는 메모리에 적재되지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다. 이러한 동적 적재의 장점은 사용되지 않는 루틴들의 경우 절대로 미리 적재되지 않는다는 것이다.

이러한 동적 적재는 공유 라이브러리 를 사용하는 데에 사용될 수 있으며, 주로 시스템 라이브러리에 사용된다. 만일 이 방식이 없다면 모든 프로그램들은 그들의 이진 프로그램 이미지 내에 시스템 라이브러리의 복사본 또는 적어도 참조되는 루틴의 복사본을 가지고 있어야 할 것이다. 하지만 이러한 동적 연결에서는 라이브러리를 호출하는 곳 마다 스텁(stub) 이 생기게 되고, 이 스텁은 메모리에 적재하는 라이브러리를 찾는 방법 또는 메모리에 없을 경우 라이브러리에 적재하는 방법을 알려주는 작은 코드 조각이다. 스텁 은 필요한 라이브러리 루틴이 이미 메모리에 존재하는 지를 검사하고 없으면 루틴을 메모리로 적재한다.

동적 연결 이 없었다면 새로운 라이브러리를 사용하기 위해 모든 프로그램이 새로 연결되어야 한다.

이러한 시스템을 공유 라이브러리 라 한다.

스와핑

프로세스가 메모리에서 실행되기 위해서는 메모리에 적재되어 있어야 하며 이렇게 디스크에서 메모리에 프로세스를 적재하는 것은 스와핑 이라고 한다. 스와핑 은 반드시 보조 메모리가 필요하며 보통 디스크를 사용한다. CPU는 준비완료 큐 에서 프로세스를 가져와 CPU를 할당해 주며, CPU 스케줄러는 다음 프로세스를 고를 때 디스패처 를 호출한다. 디스패처 는 이 큐에 있는 다음 프로세스가 메모리에 적재되어 있는지를 확인하여 없다면 디스크에서 불러들이도록 하여야 한다.

연속 메모리 할당

주 메모리는 여러 사용자 프로세스를 수용해야 하며, 일반적인 메모리 할당방법 중의 하나인 연속 메모리 할당 에 대해 배워보도록 하겠습니다.
메모리는 일반적으로 두 개로 나누어집니다. 하나는 운영체제를 위한 것 이고 다른 하나는 사용자 프로세스를 위한 것 입니다. 운영체제는 메모리의 어느 쪽 끝에도 위치할 수 있으며, 이 결정에 영향을 미치는 중요한 요인은 인터럽트 벡터입니다.

보통 여러개의 프로세스가 메모리에 적재되어야 하며, 입력 큐 에서 대기 중인 프로세스들에게 메모리를 어떻게 할당하는 것이 좋은가를 생각할 필요가 있습니다.
이번에 배울 연속 메모리 할당 에서는 프로세스는 연속된 메모리 공간을 차지하게 됩니다.

연속 메모리 할당에서는 여기 메모리 저기 산재해 있는 여러 크기의 자유 공간 중에서 적절한 것을 찾아 할당하게 됩니다. 만약 자유공간의 크기가 크면 두 개로 나누어 하나는 프로세스에게 할당하고 나머지 하나는 다시 자유공간으로 되돌려 줍니다. 만약 되돌려 준 자유공간이 주변의 공간과 인접해 있다면, 이 두개의 블록을 합쳐서 한개의 큰 자유 공간 블록으로 만들어 줍니다.

이러한 기법은 동적 메모리 할당 문제 은 특별한 예이며, 자유 공간 리스트로부터 크기 n-바이트 블록 요청을 어떻게 만족시켜 줄 수 있는지를 결정하는 문제입니다. 해결방안에는 크게 3가지 정도가 있는데, 최초 적합 기법은 요청을 만족시키는 충분히 큰 첫 번째 가용공간을 할당해 주는 것이며, 최적 적합 은 요청을 만족시키는 충분히 큰 공간들 중에서 제일 작은 자유 공간을 활도해 줍니다. 최악 적합 은 가장 큰 가용 공간을 선택합니다.

단편화

위의 예처럼 자유 공간을 임의의 조각으로 나누어 할당하는 방법은 두가지 형태의 단편화 를 만들어 냅니다. 단변화의 종류에는 내부 단편화 와 외부 단편화 가 있습니다. 먼저, 외부 단편화 는 다음과 같이 설명할 수 있습니다. 가령 계속해서 자유 공간을 할당해 주다 보면 남은 자유공간들이 너무 작은 조각들로 여러 군대에 산재되어 있는 현상이 있을 수 있습니다. 이 모든 조각을 다 모으면 큰 자유공간이 되지만 너무 잘게 쪼게어져 있기 때문에 사용하지 못하는 공간이 되어 버립니다. 이를 해결하는 방법은 압출 을 하는 것입니다. 압축 이란 이런 작은 자유 공간 조각들을 하나의 큰 조각으로 합치는 것으로 사이 사이의 프로세스가 차지하는 공간을 한쪽으로 몰아 재배치 하는 것입니다. 때문에 이 경우에는 프로세스내의 모든 주소들이 동적으로 재배치 되어야 하기 때문에 실행시간이 길어집니다. 다음으로는 내부 단편화 가 있습니다. 보통 자유 공간을 할당해 줄 때는 메모리가 분할된 크기의 정수 배로만 해주는 것이 보통이며 때문에 할당된 메모리 중 프로세스가 사용하지 않는 공간이 생길 수 있으며 이를 내부 단편화 라고 할 수 있습니다. 이러한 내부 단편화 를 줄이기 위해서는 할당해주는 메모리 조각을 최대한 작게 해 주는 것이 좋습니다.

이러한 다양한 단편화를 줄이기 위한 방법으로는 한 프로세스의 주소 공간을 여러 개의 동떨어진 공간으로 배정하는 것입니다. 그 대표적인 예로는 페이징과 세그먼테이션 이 있습니다.

페이징

페이징의 기본적인 개념은 바로 논리주소 공간이 연속된 하나의 공간에 모두 모여 있어야 한다는 제약을 없애는 것입니다.

물리 메모리는 프레임 이라고 불리는 고정 크기의 블록으로 나누어져 있으며, 논리 메모리는 페이지 라고 불리는 고정 크기의 블록으로 나뉘어져 있습니다.
CPU 는 논리 메모리를 기준으로 프로그램을 처리하며 이러한 논리 주소는 페이징 하드웨어의 페이지 테이블 에 의해 물리 주소로 변환된다. 또, 모든 물리 주소는 핻아 논리 주소로 사상될 수 있다. CPU에서 나오는 모든 주소는 논리 주소로써 페이지 번호와 페이지 변위 두 개의 부분으로 나누어 진다. 페이지 번호 는 페이지 테이블 에 접근할 때 사용되며, 해당 페이지 번호에 해당하는 주 메모리 내의 페이지의 기준 주소를 찾기 위해 사용되며, 페이지 변위 는 해당 프레임 내에서의 변위 를 나타낸다. 페이지 주소 에 페이지 변위 를 더하면 메모리 장치로 전송될 물리 주소가 된다.

프레임의 크기와 마찬가지로 페이지의 크기 도 하드웨어에 의해 결정된다. 만약 논리주소 공간의 크기가 2^n 이고 페이지의 크기가 2^m이면 논리 주소의 상위 m-n 비트는 페이지 번호를 나타내며, 하위 m 비트는 페이지 변위를 나타낸다.

페이징은 기본적으로 메모리를 정해진 페이지 사이즈로 잘라서 사용하기 때문에 외부 단편화가 발생하지 않는 대신 통산 페이지 사이즈의 반 정도의 내부 단편화 가 생기게 된다.

페이징의 가장 중요한 특징은 메모리에 대한 사용자가 생각하는 메모리와 실제 물리 메모리를 명확하게 분리한다는 사실이다. 그러나 실제로 프로그램은 물리 메모리 여러 곳에 프레임 단위로 산재되어 있고, 이 물리 메모리는 다양한 프로그램을 적재하고 있다. 사용자가 생각하는 메모리와 실제 메모리의 차이는 주소 변환 하드웨어에 의해 가려진다.

대부분의 운영체제는 프로세스마다 하나의 페이지 테이블을 할당합니다. 페이지 테이블을 가르키는 포인터는 다른 레지스터 값과 함께 프로세스 제어 블록(Process Control Block) 에 저장된다. 디스패처가 어떤 프로세스를 시작할 때 이 레지스터들을 다시 적재하면 페이지 테이블도 함께 사용할 수 있게 됩니다.

이러한 페이지 테이블 은 대부분의 경우 매우 크기 때문에 레지스터에 저장되지 못하고 주 메모리에 저장된 후 페이지 테이블 기준 레지스터(PTBR: Page Table Base Register) 로 하여금 페이지 테이블을 가르키도록 합니다. 하지만 이 경우에는 특정 정보에 접근하기 위해 두번의 메모리 접근이 필요합니다. 페이지 테이블에 접근하기 위해 한번 주 메모리에 접근하고, 얻은 주소를 통해 주 메모리에서 정보에 접근하기 위해 또 한번 접근하게 됩니다. 그래서 메모리 접근은 두 배로 느려 지며 이를 해결하기 위한 표준 방법으로 TLB(Translation Look-aside Buffers) 라고 불리는 특수한 소형 하드웨어 캐시가 사용됩니다. TLB의 각 항목은 키와 값 의 두 부분으로 구성됩니다. TLB에 페이지를 찾아달라는 요청이 들어오면 찾고자 하는 페이지를 동시에 모든 내부 키(페이지 번호)와 비교하여 해당하는 페이지 번호에 해당하는 프레임 번호를 알려줍니다. 하지만 이러한 TLB 하드웨어는 가격이 매우 비싸므로 페이지 테이블 의 일부분 밖에 들고있을 수가 없습니다. TLB에서 찾아진 페이지 번호와 프레임 번호는 TLB에 추가되어 다음 참조 시 매우 빠르게 처리할 수 있습니다. 이러한 페이지 번호는 수시로 교체되며 LRU 부터 무작위 교체까지 다양한 정책이 사용됩니다.

어떤 TLB는 각 항목에 ASID(Address Space IDentifiers) 를 저장하기도 하며, 이 ASID는 그 TLB 항목이 어느 프로세스에 속한 것인지를 알려주며, 이러한 ASID를 통해 TLB 안에 여러 프로세스들의 정보를 동시에 보관할 수 있게 됩니다. 여기서 페이지 번호가 TLB 에서 발견되는 확률을 적중률(hit ratio) 라고 합니다.

페이지 테이블의 다양한 구조

각 프로세스가 필요한 페이지들은 매우 크므로 해당 프로세스의 페이지 테이블 또한 매우 커지게 됩니다. 이를 막기 위해 다양한 페이지 테이블 구조가 있는데 대표적인 테이블 구조인 계층적 페이징, 해시된 페이지 테이블, 역 페이지 테이블 에 대해 알아보겠습니다.

계층적 페이징

계층적 페이징이란 페이지 테이블이 계층적으로 나타나는 것 입니다.
즉, 페이지 테이블이 두개로 나뉘어 하나의 페이지 테이블은 다음 페이지 테이블에 대한 포인터를 가지고 있게 됩니다. 이러한 계층적 페이지의 구조를 전방 사상 페이지 테이블(forward mapped page table) 이라고 합니다.

해시된 페이지 테이블

페이지 테이블을 사이즈를 줄이기 위해서 해시된 페이지 테이블 이 도입될 수도 있습니다. 주소 공간이 32bit 보다 커지는 경우 가상 주소를 해시 값으로 사용하는 해시 페이지 테이블 을 많이 사용합니다.

역 페이지 테이블

역 페이지 테이블은 일반 테이블 페이지 처럼 메모리 페이지 값에 대한 물리 페이지를 가지는 것이 아니라 특정, 물리 페이지에 대한 논리 페이지 값을 가지는 테이블 입니다. 이렇게 되면 시스템에는 단 하나의 페이지 테이블 만 존재하게 되며, 모든 물리 페이지는 특정 논리 페이지를 가르키게 됩니다. 이 경우에는 물리 프레임에 해당한느 항목만 테이블에 저장하면 되기 때문에 메모리에서 훨씬 작은 공간을 차지하게 되지만, 주소변환 시간은 더 오래 걸릴 수 있습니다.

세그먼테이션

페이지 테이블의 가장 큰 문제는 사용자가 사용하는 메모리 공간과 실제 물리 메모리 공간이 분리되어 헷갈린 다는 점입니다.

세그먼테이션 이란 이와 같이 메모리를 바라보는 사용자 관점을 그대로 반영합니다. 세그먼테이션에서 논리 구조 공간 은 세그먼트 들의 집합이며, 물리 메모리도 같은 원리로 세그먼테이션이 이루어집니다.

초기의 컴퓨터 시스템은 한 번에 하나의 프로그램만을 실행할 수 있었습니다. 즉, 하나의 프로그램이 시스템에 대한 완전한 제어를 가지고, 시스템의 모든 자원에 접근하였습니다. 하지만, 오늘날의 컴퓨터 시스템들은 메모리에 다수의 프로그램을 적재하여 동시에 프로그램들을 병행으로 실행이 가능하게 되었고, 이에 따라 다양한 프로그램들의 동작을 관리할 필요성이 되었습니다. 프로세스 란 실행중인 프로그램을 말하며, 현대 시분할 시스템에서 작업의 단위를 지칭합니다.

하나의 시스템은 프로세스들의 집합체 이며, 운영체제 프로세스들을 시스템 코드를 실행하고, 사용자 프로세스들은 사용자 코드를 실행합니다. 이들 모든 프로세스들은 잠재적으로 병행 실행이 가능하고, CPU가 각 프로세스들을 번갈아 가며 실행하게 함으로써 운영체제는 컴퓨터를 보다 생산적으로 만들어 줍니다.

프로세스란 무엇인가?

프로세스란 간단히 말하면 실행중인 프로그램을 의미합니다. 하지만, 프로세스는 디스크에 저장된 실행 파일 처럼 수동적인 존재가 아니라는 점에서 프로그램 과는 큰 차이가 있습니다. 프로그램이 단지 컴퓨터 안에 있는 수동적인 것인 반면, 프로세스 는 다음에 실행할 명령어를 지정하는 프로그램 카운터 및 관련 자원의 집합을 가진 능동적인 존재입니다. 실행파일이 메모리에 적재될 때 프로그램은 프로세스가 됩니다.

이러한 프로세스들은 능동적으로 동작하고 있는 존재이기에 현재의 프로세스 상태(process status) 라는 개념이 존재합니다. 각 프로세스들은 다음 상태들 중 하나에 있을 수 있습니다.

1. new: 프로세스가 생성 중인 상태
2. running: 명령어들을 실행중인 상태
3. waiting: 프로세스가 어떤 사건이 일어나기를 기다리고 있는 경우
4. ready: 프로세스가 처리기에 할당되기를 기다리는 중
5. terminated: 프로세스가 실행을 종료함

모든 프로세스는 위의 상태 중 하나에 있으며, 어느 한 순간에 처리기에서는 오직 하나의 프로세스만이 실행될 수 있습니다.

그렇다면 프로세스는 운영체제에서 어떻게 표현되나요?
프로세스는 운영체제에서 프로세스 제어 블록(Process Control Block) 이라는 이름으로 표현되며, 특정 프로세스와 연관된 여러 정보를 수록하며 다음과 같은 것들을 포함합니다.

1. 프로세스 상태
2. 프로그램 카운터
3. CPU 레지스터들
4. CPU 스케줄링 정보
5. 메모리 관리 정보
6. 회계 정보
7. 입출력 상태 정보

즉, 프로세스 제어 블록은 단순히 프로세스별로 달라지는 모든 정보에 대한 저장소 역할을 합니다.

프로세스들은 어떤 방식으로 처리되나요?

컴퓨터 시스템 안에는 수많은 프로세스들이 동작하고 있으며, 이러한 프로세스들을 효과적으로 처리하기 위한 컴퓨터의 작업을 프로세스 스케줄링 이라고 합니다. 만약 시스템이 시분할 로 동작하는 경우, 각 프로그램이 실행되는 동안 사용자가 상호작용할 수 있도록 프로세스들 사이에서 CPU를 빈번하게 교체하는 것입니다. 이를 위해 프로세스 스케줄러 는 CPU에서 실행 가능한 여러 프로레스들 중에서 하나의 프로세스를 선택하여 교체하는 역할을 수행합니다.

프로세스가 시스템에 들어오면 이들은 작업 큐 에 들어가게 됩니다. 이 큐에는 시스템 안의 모든 프로세스들이 포함됩니다. 또한 메모리에 적재된 프로세스 중 준비완료 상태로 실행되기만을 기다리는 프로세스들은 별도로 준비완료 큐 에 들어가게 됩니다. 또 시스템에는 다른 큐들도 있습니다. 만약 입출력 장치를 대기하는 프로세스들은 장치 큐 안에서 장치를 대기하게 되며, 각 장치는 자기만의 장치 큐 를 가집니다.

일단 프로세스에게 CPU가 할당되어 CPU가 실행되면, 다음 사건들 중 하나가 발생할 수 있습니다.

1. 프로세스가 입출력 요청을 하여 입출력 큐에 넣어질 수 있다.
2. 프로세스가 새로운 서브프로세스를 생성하고 그 프로세스의 종료를 기다릴 수 있다.
3. 프로세스가 인터럽트 처리 결과에 의해 강제로 CPU로부터 제거되어 준비완료 큐에 다시 놓일 수 있다.

프로세스 스케줄링

이렇게 프로세스는 일생 동안에 다양한 스케줄링 큐 사이를 이주 하며 운영체제는 어떤 방식으로든지 프로세스들을 이 큐에서 반드시 선택해야 하며, 이러한 선택절차 는 적절한 스케줄러 에 의해 실행됩니다.
프로세스 스케줄러에는 장기 스케줄러와 단기 스케줄러가 있습니다.

먼저, 장기 스케줄러(작업 스케줄러) 를 살펴봅시다.
앞에서 말했듯이 컴퓨터에는 수많은 프로세스들이 존재하고 모든 프로세스들은 자원을 할당받기 위해 서로 경쟁구도에 놓여 있습니다. 또 어떤 경우에는 동시에 실행 가능한 수보다 많은 수의 프로세스들이 제출되는 경우가 존재하며, 이 경우에는 특정 프로세스를 보류하고 나중에 실행을 해야 할 필요성이 생기게 됩니다. 이것을 처리하는 것이 바로 장기 스케줄러 입니다. 장기 스케줄러는 실행 할 수 없는 프로세스들을 대량 메모리(디스크 등)에 저장시켜 놓고 나중에 프로세스를 실행 시킬 수 있는 시점에 다시 메모리에 적재 시킵니다. 이렇게 디스크에서 메모리로 프로세스를 교체 시키면서 전체 시스템의 다중 프로그램의 개수를 조절 하는 중요한 역할을 수행합니다.
이러한 장기 스케줄러를 잘 살펴보면, 새로운 프로세스를 생성하는 시점에만 그 기능을 하는 것을 쉽게 알 수 있습니다. 또, 새로운 프로세스의 생성이 필요해 졌다는 말은 기존에 있던 하나의 프로세스가 종료되었음을 뜻하기 때문에 장기 프로세서는 프로세스가 시스템을 떠날 때에만 호출 됩니다.

장기 스케줄러는 다음 프로세스를 매우 신중하게 선택해야합니다. 일반적으로 대부분의 프로세스들은 입출력 중심 프로세스 와 CPU 중심 프로세스 로 나뉘게 되는데, 장기 스케줄러는 이러한 입출력 중심과 CPU 중심 프로세스들이 적절하게 혼합되도록 선택하는 것이 중요합니다.

단기 스케줄러(CPU 스케줄러) 는 이러한 장기 스케줄러 와는 달리 매우 빠른 속도로 준비 완료 큐 에 있는 프로세스들의 상태를 바꾸며 CPU에게 교체로 할당하는 역할을 수행합니다.

장기 스케줄러와, 단기 스케줄러 외로 중기 스케줄러 도 있습니다.
중기 스케줄러 는 메모리에서 프로세스들을 제거 하여 다중 프로그래밍의 정도를 완화하는 역할을 수행합니다. 이 중기 스케줄러는 추후 스와핑 을 통해 메모리로 프로세스를 불러와 중단되었던 지점에서부터 실행을 재개합니다.

중단된 프로세스는 어떻게 다시 실행되나요?

여러 프로세스들은 인터럽트 를통해 작업이 중단되고 특정 프로세스가 끝나면 다시 CPU에 의해 실행되게 됩니다.
이렇게 중단된 프로세스가 추후에 어떻게 다시 실행이 되는 것일까요?

이것은 바로 문맥교환 에 의해 이루어 집니다.

시스템은 인터럽트 처리가 끝난 후에 문맥 을 복구할 수 있도록 실행중이던 프로세스의 문맥을 PCB에 저장 하고, 문맥교환 을 통해 새로운 프로세스의 저장된 문맥을 불러들여 복구 합니다.

프로세스의 생성과 종료

운영체제는 이러한 프로세스를 생성하고 종료하기 위한 기법을 제공해야 하며, 이에 대해 배워봅시다.

프로세스 생성

프로세스들은 프로세스를 실행하면서 여러개의 다른 프로세스들을 새롭게 생성할 수 있습니다. 여기서 새롭게 생성된 프로세스를 자식 프로세스 라고 하며, 생성을 하는 프로세스를 부모 프로세스 라고 합니다. 이렇게 프로세스는 프로세스를 생성할 수 있고 궁극적으로 트리 구조 를 형성하게 됩니다.

프로세스가 버스 프로세스를 생성할 때 운영체제로부터 직접 자원을 얻거나 혹은 부모 프로세스의 자원의 일부분을 사용하도록 제한할 수 있습니다.

프로세스가 프로세스를 생성할 때 실행과 관련하여 두가지 기능이 있습니다.

1. 부모가 계속해서 자식과 병렬로 실행된다.
2. 부모가 모든 자식 또는 일부 자식이 끝날 때까지 기다린다.

프로세스간 통신

운영체제 내에서 실행되는 프로세스들은 서로에게 영향을 주는 경우도 있고, 또는 전혀 영향을 주지 않고 별도로 존재하는 경우도 있습니다. 두 프로세스가 서로간에 영향을 주고 받는다면 이를 협력적 프로세스 라고 하며, 그렇지 않고 서로에게 전혀 영향을 주지 않는 프로세스를 독립적인 프로세스 라고 합니다.

이렇게 프로세스 끼리 서로 통신이 가능한 협력적 프로세스 가 생성될 수 있는 환경을 제공하는 데에는 다음과 같은 이유가 있습니다.

1. 정보 공유가 쉽습니다.
   동리한 정보를 공유해야 할 필요가 있습니다.
2. 계산 가속화
   특정 태스크를 빨리 실행하고자 하려면 그것을 서브태스크로 나누어 각각 다른 서브태스크들과 병렬로 실행되게 하여 더욱 빨리 특정 프로세스를 실행시킬 수 있습니다.
3. 모듈성
   각 시스템의 기능을 별도의 프로세스로 나누어 모듈로 구성하기 쉽습니다. 모듈로 구성하기 위해서는 반드시 상호간의 통신이 필요합니다.
4. 편의성
   한 사용자가 동시에 여러 태스크를 가지는 경우 필요합니다.

협력적 프로세스들은 데이터와 정보를 교환할 수 있는 프로세스간 통신 기법을 필요로 하며, 기본적으로 공유 메모리 모델 과 메시지 전달 모델 을 통해 구현할 수 있습니다.

공유 메모리 모델

공유 메모리를 사용하는 프로세스간 통신에서는 통신하는 프로세스들이 공유 메모리 영역을 구축해야 한다. 일반적으로 운영체제는 한 프로세스가 다른 프로세스 메모리의 접근을 금지하기 때문에, 공유 메모리를 사용하기 위해서는 이 제약 조건을 제거하는 것에 동의가 필요합니다. 그런 뒤에는 프로세스들은 공유 영역에 읽고 씀으로써 정보를 교환할 수 있습니다.

메시지 전달 모델

클라이언트 서버 환경에서 통신

클라이언트와 서버의 관계에서 사용할 수 있는 통신 전략인 소켓, 원격 프로시저 호출 에 대해 알아봅시다.

소켓

• 시스템 모델
• 교착 상태의 특징
• 교착 상태 처리 방법
  • 교착 상태의 예방
    • 상호배제
    • 점유하며 대기
    • 비선점
    • 순환 대기
• 교착 상태 회피
  • 안전 상태
  • 자원 할당 그래프 알고리즘
  • 은행원 알고리즘(Banker’s Algorithm)
• 교착 상태 탐지(deadlock detection)
• 교착 상태로 부터의 회복
  • 프로세스 종료
  • 자원 선점

컴퓨터 시스템의 다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하기 위해 경쟁하고 있으며, 한 프로세스가 자원을 요청했을 때 해당 자원이 사용이 불가능한 상태라면 교착상태가 발생 하게 됩니다. 즉, 요청한 자원을 다른 프로세스가 점유하고 있고, 점유하고 있는 프로세스도 다른 자원에 대해 대기 상태에 있기 때문에 두 프로세스가 대기 상태에서 벗어날 수 없는 상황을 교착상태(deadlock) 라고 합니다.
본 강의에서는 운영체제 수준에서 교착상태를 예방하거나 다룰 수 있는 방법들을 논의 합니다.

시스템 모델

교착 상태에 대해 이야기 하기 전에 시스템에 대한 이야기를 잠깐 하고 넘어갑시다. 시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 자원들로 구성 이되며, 여러 프로세스들을 해당 자원을 점유하기 위해 서로 경쟁 구도에 놓여있습니다. 메모리 공간, CPU 주기, 파일, 입출력 장치 등이 이러한 자원 유형이 예입니다. 프로세스가 자원을 사용하기 위해서는 반드시 사용하기 전에 요청 을 해야 하고 사용 후에는 반드시 방출해야 합니다. 즉, 정상적은 작동 모드에서 프로세스는 다음 순서로만 자원을 사용할 수 있습니다.

1. 요청
프로세스는 자원을 요청하고, 즉시 허용되지 않는 경우 자원을 얻을 때까지 대기상태에 놓이게 됩니다.
2. 사용
프로세스는 자원에 대해 작업을 수행합니다.
3. 방출
프로세스가 자원을 다 사용하였다면 방출합니다.

이렇게 경쟁 구도에 놓인 프로세스들은 자원을 요청하는 시점에 해당 자원이 다른 프로세스에 의해 점유되어 있으면 대기상태에 놓이게 되고 각 프로세스와 자원들이 서로 꼬리를 물며 자원을 대기하게 되는 경우 이를 교착상태 에 놓여있다고 합니다. 즉, 한 프로세스 집합 내 모든 프로세스가 그 집합 내 다른 프로세스에 의해서만 발생될 수 있는 사건을 기다린다면, 그 프로세스 집합은 교착상태 에 있는 것입니다.

다중 스레드 프로그램은 공유 자원을 위해 경쟁하는 다수의 스레드가 있을 수 있기 때문에 교착상태의 좋은 예 가 됩니다.

교착 상태의 특징

시스템 내에서 프로세스와 자원이 어떤 관계를 가지는 지 또, 교착 상태가 어떤 상황에서 발생하는 지를 알아보았으므로 이제 교착 상태 가 가지는 특징에 대해 알아봅시다.
교착 상태에서 프로세스들은 결코 실행을 끝낼 수 없으며, 시스템 자원이 묶여 있어서 다른 작업을 시작하는 것도 불가능 하며, 이런 교착 상태는 다음의 필요 조건 을 만족합니다.

1. 상호배제(mutual exclusion)
   최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 대기하고 있어야만 한다.
2. 점유하며 대기(hold-and-height)
   프로세스는 최소한 하나의 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 디기하고 있어야 한다.
3. 비선점(no-preemption)
   자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 프로세스에 의해 자발적으로만 방출될 수 있다.
4. 순환대기(circular-wait)
   각 프로세스가 꼬리를 물며 자원을 점유하고 있어야 한다.

교착 상태가 발생하려면 위의 4가지 조건이 반드시 성립되어야 합니다.

하지만, 위와 같은 필수 조건들로는 어떤 시스템이 교착상태에 빠질 수 있는지를 간결하게 알 수 없는데, 이를 위해 우리는 자원과 프로세스의 관계를 그래프로 표현을 한 자원 할당 그래프 를 통해 시스템의 교착상태 유무를 파악할 수 있습니다. 자원 할당 그래프란 시스템 내 모든 활성 프로세스의 집합인 P 와 모든 자원의 집합인 R로 정점의 집합 V를 구성합니다. 이 그래프에서 P 로 부터 R 로 뻣어나가는 간선은 특정 프로세스가 해당 자원을 요청하고 기다리는 것을 표시하며 자원 R 에서 P로 뻣어나가는 간선 R->P 는 할당 간선 으로 해당 자원이 해당 프로세스에 할당되어있음을 나타냅니다.

이러한 자원 할당 그래프의 정의로 부터 그래프가 사이클을 포함하지 않은 경우 시스템 내 어느 프로세스도 교착상태가 아니라는 것을 보일 수 있습니다. 역으로, 반대의 경우에는 해당 시스템이 교착 상태 를 가질 가능성이 있다고 판단합니다. 여기서 왜 확실히 교착상태가 존재하는 것이 아닌 교착 상태가 될 가능성이 있다라는 표현을 하는 것일까요? 그것은 바로 자원이 하나의 인스턴스가 아니라 여러개의 인스턴스를 가질 수 도 있기 때문입니다. 만약 자원이 여러개의 인스턴스를 가질 수 있어서 여러 프로세스에게 자원을 제공한다면 교착상태가 일어나지 않게 됩니다.

교착 상태 처리 방법

이제 특정 시스템이 교착 상태에 빠질 우려가 있는지를 판단하는 방법 까지를 알아보았으니, 교착상태를 처리 하는 방법 에 대해 알아봅시다.

먼저, 교착상태 처리에는 3가지의 방법이 존재합니다.
첫째 방법 은 교착상태를 예방하거나 회피 하는 프로토콜을 사용하는 것 이며,
두번째 방법 은 시스템이 교착상태가 되도록 허용한 다음에 이를 회복 시키는 방법입니다.
마지막으로 세번째 방법 은 시스템의 교착상태를 무시하고 발생하지 않는 것처럼 꾸미는 방법입니다.

세번째 방법의 경우 터무니 없이 들리지만, 현대의 운영체제들이 대부분 사용하는 방식이며 이 경우 교착상태를 처리하는 것은 응용 개발자의 몫입니다.

위와 같은 여러가지 방법들을 통해 교착 상태가 발생하지 않게 할 수 있지만, 대부분의 경우는 이러한 해결 방법들은 큰 비용을 필요로 합니다. 가령 일년에 한두번 교착상태가 일어난다던가 혹은 특수한 경우 교착상태가 없으면서도 실행이 동결된 상태가 있을 수 있는데, 이를 피하는 것 보다는 수작업으로 한번 복구하는 것이 훨씬 효과적인 방법인 것과 같은 원리입니다. 때문에, 시스템은 교착상태가 아닌상황을 위해 수작업 복구 방법 을 반드시 가지고 있어야 하며 간단하게 이 방법을 교착상태 회복을 위해 사용 할 수도 있습니다.

교착 상태의 예방

교착 상태 처리방법 가운데 교착상태를 예방하는 법부터 배워봅시다.
시스템이 교착상태에 빠지지 않도록 하기 위해서는 앞에서 얘기한 교착 상태의 필요조건 들 중 적어도 하나가 성립하지 않도록 보장하는 방법입니다.

그렇다면 각 필요조건마다의 조건을 하나씩 따져 보며 해당 필요조건이 발생하지 않는 방안에 대해 고민해 봅시다.

상호배제

교착상태의 첫번째 필요조건인 상호배제 가 일어나는 경우는 공유가 불가능한 자원 에 의해서 입니다. 만약 여러 프로세스가 읽기 전용의 파일을 열면 프로세스들은 그 파일에 대한 동시 접근을 보장받고 이 경우 상호배제 가 깨어지게 되어 교착상태를 예방할 수 있습니다. 하지만, 어떤 자원들은 근본적으로 공유가 불가능 하기 때문에 이러한 상호배제가 반드시 일어나야 하기 때문에 교착 상태를 예방하지 못하는 경우가 발생할 수 있습니다.

점유하며 대기

두번째 필요조건인 점유하며 대기 를 방지할 조건에는 무엇이 있을까요?
점유하며 대기 조건이 발생하지 않도록 하려면 프로세스가 자원을 요청할 때 다른 자원들을 점유하지 않고 있다는 것을 반드시 보장 해야 합니다. 즉, 자기 자신이 아무런 자원도 점유하지 않고 있을 때에만 다른 자원을 요청 할 수 있도록 하면, 대기 상태에 빠지더라도 자신은 아무런 자원도 점유하지 않고 있기 때문에 대기 하더라도 점유하며 대기는 발생하지 않게 됩니다.

이 경우 사용할 수 있는 프로토콜은 프로세스가 실행되기 전에 자신이 필요한 모든 자원을 요청하여 할당받도록 하는 것입니다. 이렇게 되면 프로세스가 정도에 다른 자원을 요청하여 할당받을 때까지 대기하는 일이 없고 모든 자원을 가지고 프로세스를 시작하기 때문에 대기하는 일이 발생하지 않습니다. 하지만 이 경우 큰 단점이 발생하는데 바로 많은 자원들이 할당 된 후 오랫동안 사용되지 않기 때문에 자원의 이용률이 낮아 지는 것 입니다. 가령 어떤 명령이 디스크 접근과 인쇄를 같이 하는 것이라면 프로세스가 디스크 접근을 수행하는 동안에도 이 프로세스는 프린터의 자원을 점유하게 되어 그 시간동안 프린터가 이용되지 못하는 상황이 발생하게 됩니다. 또 기아 상태가 가능하다 는 단점이 있을 수 있습니다. 필요한 자원 중 최소 하나가 계속 다른 프로세스에게 할당되어 있으면 이 프로세스는 무한정 대기해야 할 가능성이 생기게 됩니다.

또 다른 프로토콜은 프로세스가 자원을 전혀 점유하지 않을 때만 자원을 요청할 수 있도록 하는 것 입니다. 이 경우 자원을 대기할 때 절대 자원을 점유하지 않게 되므로 점유하며 대기가 일어나지 않습니다. 하지만, 이 경우에도 치명적인 단점이 존재하는 가령 DVD 드라이브에서 디스크로 자료를 복사한 다음 디스크에서 파일을 정렬하고 이를 인쇄하는 경우를 생각해 봅시다 이 경우 프로세스는 드라이브와 디스크를 점유한 뒤에 인쇄를 하기 위해서 디스크와 드라이브를 모두 방출하고 다시 디스크의 자원을 할당받는 비효율적인 동작이 나타나게 되어 자원의 이용률이 낮아지게 됩니다.

비선점

세 번째 필요조건인 비선점 이 발생하지 않도록 해봅시다. 비선점 이란 이미 할당된 자원이 선점되지 않아야 한다는 것 입니다. 이를 위해서는 자신이 점유하고 있는 자원을 강제로 방출시켜 다른 프로세스가 선점하게 함으로써 교착상태를 끈어버리는 다음과 같은 프로토콜 을 생각해 볼 수 있습니다. 만일 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 그 프로세스가 점유하고 있는 모든 자원이 방출되어 필요로 하는 다른 프로세스에게 선점됩니다. 또 해당 프로세스는 자신이 요청하고 있는 새로운 자원은 물론 현재 강제로 방출한 옛 자원들을 다시 획득할 수 있을 때에만 다시 시작될 것입니다.

순환 대기

교착 상태가 일어나기 위한 마지막 조건인 순환대기 를 없애기 위해서는 모든 자원 유형들에게 전체적인 순서를 부여 하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 강제하는 것입니다. 이를 통해 모든 자원들은 먼저 할당되는 순서가 정해져 있기 때문에 교착상태가 일어날 수 없습니다.

교착 상태 회피

이처럼 교착 상태 예방 알고리즘은 요청 방법을 제약하여 교착 상태를 예방합니다. 그러나 이런 방식으로 교착 상태를 예방할 때 가능한 부작용은 바로 장치의 이용률이 저하 되고 시스템 이용률이 감소 된다는 것입니다.

이처럼 교착 상태를 처리하는 다른 방법 중 하나는 교착상태 회피 입니다. 교착상태 회피는 각 프로세스의 요청과 방출에 대한 순서를 파악하고 있다면 우리는 각 요청에 대해서 가능한 미래의 교착상태를 피하기 위해 프로세스가 대기해야하는 지를 결정할 수 있다는 점에 착안하여 나온 방안입니다. 즉, 어떤 프로세스가 요청을 할 때 미래에 대한 분석을 통해 나의 요청을 늦추는 방법으로 교착상태를 피할 수 있습니다. 이렇게 교착상태를 피하기 위한 알고리즘을 위해서는 각 프로세스가 요청할 각 유형의 자원의 최대 개수를 파악하는 것입니다.

안전 상태

안전 상태란 이러한 교착 상태 알고리즘을 설계함에 있어 각 유효 자원의 최대 개수까지 어떤 순서로 요청을 하더라도 교착상태를 야기하지 않고 모두 할당을 잘 해줄 수 있음 을 뜻합니다. 회피 알고리즘은 시스템이 정해진 최대 자원 내에서 시스템이 항상 안전 상태에 있도록 한합니다. 이를 위해 프로세스들이 자원을 요청하면 그 요청을 받아주던지 혹은 교착상태를 피하기 위해서 대기 시킬지를 결정하며, 오직 시스템이 안정상태로 유지될 수 있는 경우에만 즉시 요청을 들어줍니다.

자원 할당 그래프 알고리즘

앞에서 우리는 교착 상태 회피를 위해 정의한 자원 할당 그래프 를 살펴 보았습니다. 우리는 교착 상태 회피를 위해서 예약 간선 을 도입하겠습니다. 예약 간선이란 현재는 아니지만 추후 자원을 요청하게 될 것을 의미 합니다. 즉, 추후 시스템에서 교착상태가 일어날 가능성이 생기는 것이지요. 이러한 예약 간선 은 요청이 발생되면 요청 간선 으로 전환되고 자원이 할당되면 할당 간선 으로 전환됩니다.

은행원 알고리즘(Banker’s Algorithm)

교착 상태 탐지(deadlock detection)

교착 상태로 부터의 회복

탐지 알고리즘에 의해 시스템에 교착 상태 가 발생이 되면 이를 회복하는 여러가지의 방법이 있지만 크게 두가지로 나누어 집니다. 첫번째는 한 개 이상의 프로세스를 중지 시키는 것이고, 둘째는 하나 이상의 프로세스들로부터 자원을 선점하는 것입니다.

프로세스 종료

먼저 교착 상태를 해결하기 위해 존재하는 프로세스 하나를 임의로 종료하여 교착 상태를 해결하는 방법에 대해 알아봅시다.
프로세스를 종료함에 있어 우리는 두가지의 방법 을 사용할 수 있습니다.

첫째는, 교착 상태 프로세스를 모두 중지 하는 것 입니다. 이 방법은 상당히 큰 비용 이 들어가는데, 이유는 단순합니다. 교착상태에 가기까지 프로세스들이 이제껏 많은 작업을 진행했을 것이며, 이를 통해 결과가 폐기된다면 다시 계산을 시작해야 하기 때문입니다.

둘째는, 교착 상태가 제거될 때까지 한 프로세스씩 중지 하는 방법이 있습니다. 이 방법은 각 프로세스가 중지될 때마다 아직도 교착 상태에 있는지 매번 살펴봐야 하기 때문에 상당한 오버헤드를 유발합니다.

자원 선점

자원 선점을 통해 교착상태를 제거하기 위해서는 교착 상태가 깨어질 때까지 프로세스로부터 자원을 계속적으로 선점해 다른 프로세스에게 주어야 합니다.
이런 자원 선점 에 있어서 다음을 사항들을 꼭 고려하여야 합니다.

1. 희생자 선택(selection of a victim)
자원 선점에 앞서 어떤 자원과 어느 프로세스가 선점될 것인가 를 고민해야 합니다. 이 때 비용을 최소화 하기 위해 교착 상태 프로세스가 점유하고 있는 자원의 수, 그리고 교착상태 프로세스가 지금까지 실행하는 데 소요한 시간 등과 같은 변인들을 고려하여 희생자를 선택해야 합니다.

2. 롤백(rollback)
만약 특정 프로세스을 자원을 강제로 방출하고 선점시켰다면, 그 프로세스를 어떻게 처리 할 것인가에 대한 고민이 필요하다. 보통 가장 안전한 방법은 프로세스를 중지시키고 재시작하는 것 즉, 롤백하는 것이다.

3. 기아 상태(starvation)
자원 선점을 통해 기아상태가 발생하지 않을까를 고려해 보아야 한다. 계속해서 특정 프로세스의 자원을 강제 방출시켜 선점을 시켜주게 되면 그 프로세스는 계속해서 희생자로 선택될 확률이 높고 이경우 그 프로세스는 영원히 실행이 완료되지 못하는 기아상태에 빠질 수 있기 때문에 이를 심사숙고 해야 한다. 즉, 프로세스가 한정된 시간에만 희생자로 선정된다는 것을 반드시 보장 해야 한다.

• 가상 메모리는 무엇이며, 왜 사용하는가?
• 요구 페이징이란?
  • 요구 페이징이란?
  • 요구 페이징의 성능
• 페이지 교체
  • 페이지 교체의 필요성
  • 페이지 교체의 동작 원리
  • 선입선출 페이지 교체(FIFO Page Replacement)
  • 최적 페이지 교체(Optimal Page Replacement)
  • LRU 페이지 교체(LRU Page Replacement)

가상 메모리는 무엇이며, 왜 사용하는가?

가상 메모리란 어떤 프로레스를 실행할 때 프로세스 전체가 메모리에 적재되지 않고도 실행이 가능 하도록 하는 기법입니다. 좀 더 나아가면 어떤 프로세스가 차지하는 메모리가 전체 메모리 용량보다 크더라도 지금 현재 필요한 부분만 메모리에 적재 되면 실행이 가능하기 때문에 물리 메모리 용량을 초과하는 프로그램도 동작 시킬 수 있는 큰 장점이 있습니다.

가상 메모리는 실제의 물리 메모리의 개념과 사용자의 논리 메모리의 개념을 분리 합니다. 좀 더 쉽게 말하자면 원래의 컴퓨터의 메모리란 일반적으로 실제 존재하는 물리적인 메모리 만을 의미합니다. 하지만 이러한 물리적인 메모리를 보다 효율적으로 사용 하기 위해서 프로그래머는 가상 메모리 의 개념을 만들게 되었고, 이런 가상 메모리는 다소 복잡하게 구성되고 접근이 어려운 물리 메모리를 가상으로 재구성 하여 엄청나게 큰 배열로 추상화 시켜줍니다. 따라서 프로그래머는 물리 메모리를 신경쓰지 않고 가상의 메모리만을 신경 쓰면서 프로그래밍 을 하게 되어 보다 편리해 진 측면도 존재합니다. 여기서 말하는 가상 메모리 를 프로세스가 차지하는 공간의 측면에서 가상 주소 공간 이라고 부르며, 보다 정확히는 그 프로세스가 메모리에 저장되는 논리적인 모습을 말합니다. 앞의 내용에서 다루었듯이 실제 물리 메모리는 페이지 프레임 들로 구성되며, 논리적인 페이지를 물리적인 페이지 프레임으로 사상하는 것은 메모리 관리 장치(Memory Management Unit) 에서 담당합니다.

가상 메모리를 사용함에 따른 또 다른 장점은 파일이나 메모리가 둘 또는 그 이상의 프로세스들에 의해 공유되는 것을 가능 하게 하는 것입니다. 어떤 프로세스나 파일이 메모리 주소를 참조할 때 특정 물리주소가 아닌 가상 주소를 참조하고 이 가상 주소는 메모리 관리 장치에 의해 물리 주소로 사상되기 때문에 특정 프로세스에서 논리 메모리 값을 참조하면 자연스럽게 두 프로세스가 같은 물리 주소를 참조하게 됩니다.

요구 페이징이란?

요구 페이징이란?

디스크에서 메모리로 실행 프로그램을 적재할 때를 생각해 봅시다. 이 경우 실행하고자 하는 프로그램 전체를 메모리로 옮기는 것이 일반적인 방법입니다. 하지만 가상 메모리에서는 초기에 필요한 것만 적재하는 전략을 사용할 수 있는데 이것을 요구 페이징 이라고 합니다. 이러한 요구 페이징을 사용하게 되면 한번도 접근되지 않는 페이지는 물리 메모리에 전혀 적재되지 않게 됩니다. 이러한 요구 페이징은 어떤 점에서 스와핑 기법과 비슷하게 동작합니다. 프로세스를 실행하고 싶으면 메모리로 읽어 들이는 swap in 을 할 때 전체 프로세스를 읽어오지 않고 필요한 페이지만 메모리에 적재합니다. 하지만 이 경우 프로세스를 하나의 연속된 주소 공간으로 보기 보다 페이지들의 연속으로 생각하고 있으므로 스와퍼 라는 표현이 아닌 페이저 라는 표현을 사용합니다. 이러한 페이저 는 프로세스 내의 개별 페이지들을 관리합니다.

디스크에서 메모리로 페이지를 적재하는 스왑인(swap in) 을 수행하는 경우 프로세스가 다시 스왑 아웃 되기 전에 실제로 어떤 페이지들이 사용될 것인지 추측하고, 프로세스 전체를 메모리에 적재하는 대신 실제 필요한 페이지들만 메모리로 읽어옵니다.

이렇게 프로세스 전체가 아니라 프로세스의 부분 조각인 페이지 들만 가져오게 되면 무슨 일이 생길까요?
특정 프로세스 내에서 어떤 페이지가 실제 메모리에 적재되었는지, 또 적재되지 않았는지를 구별할 수 없게 됩니다. 이런 문제를 해결하기 위해서 약간의 하드웨어 지원을 받아 페이지 테이블 이라는 것이 존재합니다. 이런 페이지 테이블 에는 유효-무효 비트 가 존재하여 어떤 페이지가 실제 물리 메모리에 적재되어 있는지를 표시해 주고 만약 실제 물리 메모리에 적재되지 않은 페이지는 그 페이지가 저장되어 있는 디스크 주소를 기록 해 두어 나중에 필요할 때 가져올 수 있게 해 줍니다.

이제 CPU가 필요한 페이지를 메모리에서 가져올 때 만약 가상 메모리에 해당 내용이 있다면 해당하는 물리 메모리에서 페이지를 로드하여 모든 페이지가 메모리에 존재할 때와 동일하게 실행이 됩니다. 만약 메모리에 없는 페이지에 접근 을 하려고 하면 어떨까요? 이때는 페이지 테이블 항목이 무효로 설정되어 있으므로 페이지 부재 트랩 을 발생시킵니다.

페이지 부재가 발생하면 사용하는 모든 페이지가 메모리에 올라올 때까지 필요할 때마다 페이지 부재가 발생하게 되는데, 일단 필요한 모든 페이지가 메모리에 적재되고 나면 부재 오류가 발생하지 않게 되고 이것이 순수 요구 페이징 입니다. 즉, 어떤 페이지가 필요해 지기 전에는 그 페이지를 적재하지 않습니다.

여기서, 이렇게 가상 메모리가 최초의 페이지를 적재하고 계속해서 필요한 페이지들을 불러오는 방식으로 계속해서 페이지 부재 오류를 처리하면서 페이지를 적재한다면 시스템 성능이 현저하게 떨어지지 않을까하는 의문 이 생길 수 있습니다. 한 명령어에서도 여러 개의 페이지 부재를 일으킬 수 있는 만큼 충분히 이런 의문이 제기될 수 있습니다. 하지만, 모든 프로그램은 참조 지역성 즉, 프로그램의 어느 한 특정 작은 부분만 집중적으로 참조하기 때문에 특정 페이지를 불러오면 그 안에 대부분의 유효한 정보가 밀집되어 있기 때문에, 현실에서는 문제가 될 만큼 많은 페이지 부재가 일어나지는 않습니다.

이러한 요구 페이징에서 필수적인 요구사항은 페이지 부재 오류 처리 후 명령어를 다시 시작 할 수 있어야 한다는 것 입니다. 언뜻 생각하면 이는 매우 단순한 문제인 것 처럼 보입니다. 페이지 부재 오류가 발생하면 중단된 프로세스 상태(일종의 레지스터 값 등)을 저장해 놓은 뒤에 페이지를 적재하고 다시 명령을 처리하면 문제는 해결될 것으로 보입니다.

하지만, 한 명령어가 많은 기억 장소를 변경하는 경우를 생각해 봅시다. 가령 디스크의 특정 블록을 적재하는 데 해당 블록이 페이지 사이에 걸쳐 있다면 정보가 다 적재되기도 전에 페이지 부재가 발생하여 문제가 발생하게 됩니다. 만약 적재하던 블록은 저장하는 장소가 걸쳐진 다른 블록인 경우는 문제가 더욱 심각해 집니다.

이러한 문제를 해결하기 위한 방법 중 하나는 마이크로 코드로 양 블록의 끝을 계산하여 접근을 시도하는 것 입니다. 가령 블록이 몇 페이지에 걸쳐 존재한다면 양 끝 블록을 계산하여 몇 개의 페이지를 적재해야 하는지 알 수 있고, 만약 페이지 부재가 발생하면 어떤 블록도 수정되기 전의 단계에서 부재가 발생하여 데이터의 손상이 없습니다.

요구 페이징의 성능

요구 페이징은 페이지 부재가 발생하지 않는 한 실질 접근시간은 메모리 접근 시간과 같다. 즉, 유효 접근시간은 페이지 부재율 에 비례하기 때문에 페이지 부재율을 낮게 유지하는 것이 상당히 중요하다.

페이지 교체

페이지 교체의 필요성

페이지 부재율을 논할 때 각 페이지는 처음 그 페이지가 접근될 때 한 번만 페이지 부재가 발생한다고 가정하였으나, 이 설명은 정확한 것이 아닙니다. 가령 40프레임의 메모리 용량을 가진 컴퓨터에서 10페이지 중 실제 5페이지만 사용하는 프로세스를 6개를 실행시킨다고 합시다. 그러면 요구 페이징에 의해 총 30페이지가 메모리에 적재될 것입니다. 하지만 기존의 가정과 달리 특정 데이터 조합에 대해 이 프로세스들이 10 페이지를 모두 사용해야 하는 상황이 있을 수 있고 그런 상황의 경우 총 60페이지가 메모리에 적재되어야 합니다. 이렇게 된다면 총 40프레임만 있는 상황에서 60프레임을 필요로 하게 되고 사용자 프로세스가 실행 중 이 때 과할당(over-allocating) 이 발생하게 됩니다. 즉, 과할당이란 프로세스가 메모리보다 더 큰 용량의 페이지를 적재하려고 할 때 발생 하게 됩니다. 이런 과할당이 발생하는 경우 가장 일반적인 해결책은 바로 페이지 교체 입니다.

페이지 교체의 동작 원리

그렇다면 페이지 교체는 어떻게 이루어 질까요?
페이지의 교체는 다음과 같은 순서로 이루어 집니다.

1. 디스크에서 적재가 필요한 페이지의 위치를 알아냅니다.
2. 메모리공간에서 빈 페이지 프레임을 찾습니다.
   이때 빈 프레임이 있다면 그것을 사용하고 없다면 페이지 교체 알고리즘 을 통해 희생될(victim) 프레임 을 선정하고, 희생될 페이지를 디스크에 기록한 뒤 관련 테이블을 수정합니다.
3. 새롭게 비워진 프레임에 새 페이지를 읽어오고 프레임 테이블을 수정합니다.
4. 사용자 프로세스를 재시작 합니다.

위 순서를 잘 살펴보면 만약 메모리 공간에 빈 페이지 프레임이 있는 경우에는 프레임을 비울 때 한번, 프레임을 읽어들일 때 한번 총 2번에 걸쳐 디스크에 접근 하는 점을 알 수 있습니다. 이 때문에 페이지 부재 처리시간은 총 2베가 소요되게 되는데 이는 이러한 오버헤드는 변경 비트(modify bit or dirty bit) 를 활용해서 해결 할 수 있습니다. 변경 비트란 CPU가 페이지 내 어떤 워드나 바이트라도 쓰게 되면 페이작 변경되었음을 나타내기 위해 설정됩니다. 만약 변경 비트가 설정되어 있지 않다면 페이지가 메모리로 읽혀들어온 후에 바뀌지 않았으므로 메모리에서 그냥 삭제해도 디스크에는 원본이 잘 보존되어 있기 때문에 별도로 저장을 하지 않아도 됩니다. 이 기법은 읽기전용 페이지들에도(디스크 내용을 변경하지 않았으므로) 같은 원리로 적용이 됩니다.

위에서 다룬 페이지 교체 알고리즘 을 비롯하여 현대의 페이징 시스템은 두 가지 중요한 문제를 해결해야 하는데, 그것은 프레임 할당 알고리즘 과 페이지 교체 알고리즘 입니다.
프레임 할당 알고리즘 이란 여러 개의 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 할지 결정하는 알고리즘이며, 페이지 교체 알고리즘 이란 페이지 교체가 필요할 때 어떤 페이지를 교체할지 선정하는 알고리즘 입니다.

현재에는 많은 페이지 교체 알고리즘이 존재하며 일반적으로는 페이지 부재율이 가장 낮은 것을 선정 하는 알고리즘을 사용합니다.

선입선출 페이지 교체(FIFO Page Replacement)

페이지 교체 알고리즘 중에서 가장 간단한 알고리즘인 선입선출 알고리즘 을 살펴봅시다. 선입선출 교체 알고리즘은 각 페이지에 메모리 적재시간을 연관시켜 가장 오래된 페이지를 교체하는 알고리즘 입니다. 하지만 선입선출 알고리즘은 간단한 만큼 많은 문제점을 가지고 있습니다. 쉽게 생각해 봐도 오래된 페이지가 얼마나 자주 사용될지도 모르는데 모래되었다는 것 하나로 교체해 버리는 것은 참 무모해 보입니다. 가령 매우 중요한 변수를 들고있을 수도 있고 수없이 많이 수행되는 중요한 페이지 일수도 있기 때문입니다. 하지만 이렇게 페이지가 교체되어도 치명적인 문제는 일어나지 않습니다. 페이지가 교체되어도 필요한 시점에서 바로 부재처리 가 되어서 다시 메모리에 적재시키면서 프로세스가 동작하기 때문입니다. 하지만, 이 경우에는 페이지 부재율이 많이 높아지게 되고 효율적이지 못한 동작 이 일어난다고 볼 수 있습니다.

최적 페이지 교체(Optimal Page Replacement)

최적 페이지 교체 알고리즘을 알아보기 전에 Belady 의 모순 에 대해 알아봅시다. 보통 프로세스에게 얼마만큼의 프레임을 할당하는가 하는 문제에 있어서 많은 프레임을 할당하면 페이지 부재율이 낮아질 것으로 생각을 합니다. 하지만 위의 선입선출 알고리즘과 마찬가지로 Belady 의 모순이란 많은 프레임을 할당해 주었는데도 불구하고 반대로 페이지 부재율이 더 증가하는 현상을 일컷습니다. 이러한 Belady 의 모순이 없는 알고리즘을 찾던 와중에 최적 교체 알고리즘 이 탄생하게 되었습니다. 최적 교체 알고리즘은 간단히 말하면 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체 하는 알고리즘이며, 프레임 수가 고정된 경우 가장 낮은 페이지 부재율을 보장 합니다. 하지만 불행하게도 이 알고리즘의 구현은 매우 어렵고 따라서 주로 비교 연구 목적을 위해 가장 최선의 경우를 계산할 목적으로 사용됩니다. 가령 특정 알고리즘을 개발하였는데 최적 알고리즘에 비해 12.3% 이상으로 나빠지지 않았다라는 연구결과를 얻는 등 일종의 레퍼런스로 사용됩니다.

LRU 페이지 교체(LRU Page Replacement)

최적 페이지 교체 알고리즘이 미래에 사용되지 않을 페이지를 찾아 교체하는 것이라 할때 최근의 과거를 미래의 근사치로 본다면 가장 오랜 시간 사용되지 않은 페이즈를 교체할 수 있고 이것이 LRU 알고리즘이다.

• 입출력 시스템이란 무엇인가?
• 입출력 하드웨어
  • 입출력 하드웨어의 구성
  • 입출력 하드웨어의 동작
    • 폴링
    • 인터럽트
  • 직접 메모리 접근(Direct Memory Access)

입출력 시스템이란 무엇인가?

컴퓨터의 주요한 두가지 작업은 연산작업 과 입출력 작업 입니다. 많은 경우 연산 작업 보다는 입출력 작업이 중요 한데, 가령 우리가 인터넷 서핑을 하거나 혹은 문서작업을 하는 경우 대부분은 컴퓨터 내의 저장된 파일을 열거나 작성하는 경우가 다반사 이기 때문입니다. 그만큼 컴퓨터는 설치된 입출력 장치들과 원활하게 소통해야 하고 운영체제는 이러한 입출력이 잘 이루어 지도록 할 필요 가 있습니다. 본 강의 에서는 어떻게 컴퓨터에 연결된 다양한 입출력 하드웨어 장치들과 소통이 이루어 지는지 를 공부하고 그 과정에서 하드웨어 인터페이스 및 소프트웨어 인터페이스의 간극을 운영체제가 어떻게 해결하는 지에 대해 알아봅니다.

컴퓨터에 연결될 장치들을 제어하는 일은 운영체제의 주요한 관심사 입니다. 다양한 장치들 은 기능이나 속도면에서 다양한 특성을 보이기 때문에 각각에 맞는 제어가 필요 하고, 이와 같은 다양한 제어 방법들이 커널의 입출력 서브 시스템을 형성 하여 커널의 다른 부분이 입출력장치를 관리하는 복잡한 일에 신경쓰지 않게 해줍니다.

이렇게 입출력을 관리하기 위한 기술들이 지향하는 바는 새로 나오는 장치들이 기존 시스템에 쉽게 결합될 수 있게 하는 것입니다. 가령 무수히 쏟아져 나오는 마우스, 키보드, 모니터 등 다양한 장치들이 내 컴퓨터와 잘 동작하게 하려면 둘 사이에 무언가 공통된 인터페이스 가 존재해야 하며 그 역할을 수행하는 것이 입출력 관리의 핵심이라고 할 수 있습니다. 때문에 이런 인터페이스의 표준화 는 입출력 관리에서 매우 중요합니다. 운영체제 커널 이 이렇게 다양한 입출력 장치들의 차이를 가려주기 위해서 장치 구동기 모듈 을 사용합니다. 장치 구동기는 모든 하드웨어를 일관된 인터페이스로 표현해 주며, 이러한 인터페이스를 그보다 상위층인 커널의 입출력 서브시스템에 제공해 줍니다.

입출력 하드웨어

입출력 하드웨어의 구성

다양한 입출력 장치들이 컴퓨터와 동작을 하는 원리를 알기 위해서 우리는 이런 입출력 장치 들이 어떻게 구성되어 있는지 살펴 볼 필요가 있습니다. 이런 입출력 장치들은 크게 저장 장치, 전송 장치, 사용자 인터페이스 장치 등으로 나뉘어집니다. 하지만, 이러한 다양한 입출력 장치가 어떻게 운영체제와 동작하는지 알기 위해서 우리는 몇가지 표준적인 개념만 이해하면 됩니다.

하드웨어 장치는 케이블을 통하거나 무선으로 신호를 보냄으로써 컴퓨터 시스템과 통신 하며, 포트 라고 불리는 연결점을 통해 컴퓨터에 접속합니다. 만약 하나 이상의 장치들이 공동으로 여러 선들을 사용한다면 이것을 버스 라고 부릅니다. 여기서 버스는 단순히 선만을 의미하는 것이 아니라 각 선에 어떤 전기적 신호를 보내어 통신이 이루어지는 지를 약속하는 프로토콜 까지를 포함하는 개념 입니다. 하드웨어 장치의 또 다른 구성요소는 바로 제어기 입니다. 제어기란 포트나 버스나 입출력 장치를 제어하는 전자회로의 집합체이며 많은 입출력 장치는 제어기를 내장 하고 있습니다.

그렇다면 컴퓨터는 어떻게 장치의 제어기에서 입출력을 하도록 명령할 수 있을까요?
모든 제어기는 레지스터를 가지고 있고 컴퓨터의 프로세서는 제어기의 레지스터에 비트 패턴을 쓰거나 읽음으로써 입출력을 실행 합니다. 다른 방법으로는 장치 제어 레지스터를 프로세서의 주소 공간으로 사상 하는 방법이 있고 이것을 메모리 맵 입출력(Memory Map I/O) 이라고 부릅니다. 이 경우에는 각 주변장치 레지스터들은 메모리 주소와 일대일 대응이 되고, 컴퓨터는 이러한 메모리 주소에 데이터를 읽고 쓰는 것으로 장치 제어기의 레지스터에 직접 데이터를 읽고 쓰는 역할을 수행 하게 할 수 있습니다. 이러한 메모리 맵 입출력의 활용은 다양합니다. 가령 스크린에 내용을 출력하는 작업을 함에 있어서 모든 비트맵을 일일히 제어기에 작성하는 것은 너무도 큰 작업이 될 것입니다. 하지만 메모리맵 입출력을 통해 메모리에 수백만 바이트를 기록하는 방식으로 입출력 명령어를 이용하는 경우보다 훨씬 빠른 성능 을 낼 수 있습니다. 하지만 이러한 메모리 맵 이출력에서는 잘못된 포인터 등의 오류로 현재 선점 중인 메모리 주소에 임의값을 작성하는 경우 입출력 시스템에 문제가 생기게 되는 문제점 이 있습니다.

다음은 장치의 입출력 포트 가 어떻게 구성되어 있는지 알아봅시다. 장치의 입출력 포트 는 보통 4개의 레지스터로 구성 되어 있는데, 상태, 제어, 입력, 출력 레지스터가 그것입니다.

입출력 하드웨어의 동작

입출력 하드웨어가 어떻게 생겼는지 알아보았으니, 이제는 그 동작을 알아보도록 합시다.

폴링

컴퓨터와 입출력 하드웨어 사이의 프로토콜을 복잡하지만 기본적인 핸드셰이킹 개념은 간단합니다. 장치의 제어기의 레지스터 에는 비지 비트 라는 것이 존재 하는데, 이것은 현재 장치가 사용가능한 상태인지 아니면 다른 작업을 처리중이라 사용이 불가능 한지를 나타냅니다. 제어기는 작업이 하느라 바쁠 때에는 비지 비트를 1로 설정하고 준비 중인 경우에는 0으로 설정하여 컴퓨터가 현재 장치가 사용중인지를 알 수 있게 해줍니다.

여기서 컴퓨터는 시시때때로 장치가 사용중인지를 검사하기 위해 비지 비트 를 검사해야 하는데, 이것을 계속 돌면서 반복한다고 하여 폴링 이라고 부릅니다. 이러한 폴링에는 컴퓨터 자원이 많이 소요되지 않지만(3 사이클 정도) 장치가 준비하는 시간이 길어지면 매우 비효율적이며, 이 대신 하드웨어가 제어기가 자신의 상태가 바뀔 때 컴퓨터에 통보를 해 주면 이렇한 비효율을 막을 수 있으며 이를 인터럽트 라고 합니다.

인터럽트

인터럽트의 기반 메커니즘은 다음과 같습니다. CPU는 인터럽트 요청 라인 이라고 불리는 선을 가지는데, CPU는 매 명령어를 끝내고 다음 명령어를 수행하기 전에 이 선을 검사 합니다. 만약 입출력 장치가 준비가 완료되어 인터럽트 요청 라인 에 신호를 보내면 CPU는 하나의 명령을 끝낸 시점에 인터럽트를 확인하고 인터럽트 핸들러 를 실행합니다. 여기서 인터럽트 핸들러 란 입출력 장치를 서비스함으로써 이 인터럽트를 처리해 주는 것입니다. 하지만 현대의 시스템에서는 이러한 인터럽트를 처리함에 있어 보다 세분화된 인터럽트 핸들링이 필요 했고, 다음은 인터럽트 핸들러가 수행해야 하는 기능을 보여줍니다.

1. 임계영역을 실행 중에는 인터럽트 처리를 연기시키는 능력이 필요하다.
2. 어떤 장치가 인터럽트를 일으켰는지 조사하기 위해 모든 장치를 폴링하지 않고 적절한 인터럽트 핸들러로 이동 하는 효율적인 방법이 필요하다. 즉, 인터럽트 요청 라인에 요청이 들어왔을 때 어디서 들어온 요청인지 바로 알아야 한다.
3. 운영체제가 높은 우선순위와 낮은 우선순위를 구분하고 긴급한 정도에 따라 응답하기 위한 다수준 인터럽트 가 필요하다.

위의 세가지 기능을 제공하기 위해 CPU와 인터럽트 제어기 하드웨어를 통하여 구현하고 있습니다.
대부분의 CPU는 두 종류의 인터럽트 요청 라인인 마스크 불가 인터럽트, 마스크 가능 인터럽트 를 가지고 있습니다. 여기서 마스크 불가 인터럽트는 회복 불가능한 메모리 에러와 같은 이벤트를 처리 하며, 마스크 가능 인터럽트는 필요 시 잠시 중단시켜 놓을 수 있는 인터럽트를 처리 합니다.
보통의 인터럽트 기법에서는 인터럽트 요청을 할 때 주소라고 하는 하나의 정수를 받아 들이는 데 이것은 인터럽트 핸들러들의 메모리 주소들을 가지고 있는 인터럽트 벡터 라 불리는 테이블의 인덱스값 으로 사용됩니다. 이러한 벡터형 인터럽트 기법 은 인터럽트 벡터 를 활용하여 모든 가능한 인터럽트의 진원지를 찾아야 할 필요를 줄여 주지만 컴퓨터는 인터럽트 벡터 내에 있는 주소들보다 더 많은 수의 장치를 가지고 있고 이 문제를 해결하기 위해 인터럽트 사슬화 를 사용합니다. 인터럽트 사슬화에서 인터럽트 벡터의 각 원소들은 인터럽트 핸들러 리스트 의 헤더를 가르키고 있고, 만약 인터럽트가 일어나면 해당 핸들러를 찾을 때까지 리스트 상의 핸들러들을 하나씩 검사하게 됩니다.

직접 메모리 접근(Direct Memory Access)

이제까지 컴퓨터와 입출력 장치가 어떻게 구성되어 있고, 어떻게 동작하는 지를 알아보았습니다. 그렇다면 입출력 장치와 컴퓨터 사이의 데이터는 어떤 방식으로 주고 받을까요? 만약 CPU를 사용하여 디스크와 같은 대용량 입출력 장치의 데이터를 읽어들인다면 CPU의 사용량이 매우 높아지고 이는 컴퓨터 성능을 심각하게 저하시킬 것입니다. 즉, CPU가 매번 바이트 전송을 제어하는 것은 심한 낭비인 것이죠. 이렇게 CPU가 1바이트씩 옮기는 입출력 방식을 PIO 라고 부릅니다.

많은 컴퓨터들은 이렇게 CPU의 낭비를 막기 위해 PIO를 DMA 제어기 라고 불리는 특수 프로세서 에게 위임함으로써 CPU의 일을 줄여줍니다. 그 과정은 다음과 같이 진행됩니다

먼저, 컴퓨터(호스트)는 메모리에 DMA 명령 블록을 씁니다. 이 블록에는 전송할 데이터가 있는 곳의 포인터와 전송할 장소에 대한 포인터 그리고 전송될 바이트 수를 기록해 놓습니다. 그러면 CPU는 DMA 명령 블록의 주소를 DMA에게 알려주고 자신은 다른 일을 처리합니다. 그러면 DMA는 CPU의 도움 없이 자신이 직접 버스를 통해 DMA 명령 블록을 액세스하여 입출력을 실행합니다.

그러면 DMA 제어기와 장치 제어기는 어떻게 연결될까요?
이 둘의 핸드셰이킹은 DMA request, 와 DMA acknowledge 라고 불리는 두 개의 선을 통해서 실행됩니다. 장치 제어기는 전송할 자료가 생기면 DMA request를 통해 장치 제어기에서 데이터 전송을 요청 합니다. 그러면 DMA 제어기가 메모리 버스를 얻어 거기에 원하는 주소를 올려 놓고 DMA acknowledge 신호 를 보냅니다. 장치 제어기가 DMA acknowledge 신호를 받으면 제어기는 한 워드를 메모리로 전송하고 DMA request를 제거 합니다. 그리고 전송이 끝나면 DMA 제어기는 CPU에게 인터럽트를 걸어 전송이 완료되었음을 알립니다. 이 과정에서 DMA 제어기가 메모리 버스를 점유 중이면 주 메모리는 주캐시와 보조캐시에 있는 데이터에는 접근할 수 있지만 주 메모리에 있는 데이터는 접근을 할 수 없게 되어 CPU의 속도를 저하시키지만 전체적으로 보았을 때에는 입출력 작업을 DMA로 넘기는 것은 시스템 성능을 향상 시킵니다.

• CPU 스케줄링이란 무엇인가?
  • 프로세스는 어떤 식으로 동작하나요?
  • CPU 스케줄링은 누가 수행하나요?
  • 스케줄링의 방법들
  • 누가 프로세스에게 제어권을 주나요?
• 스케줄링의 기준
• 스케줄링 알고리즘
  • 선입 선처리 스케줄링
  • 최단 작업 우선 스케줄링
  • 우선 순위 스케줄링
  • 라운드 로빈 스케줄링
  • 다단계 큐 스케줄링
  • 다단계 피드백 큐 스케줄링
• 다중 처리기 스케줄링
  • 다중 처리기 시스템에 대한 접근방법
  • 처리기 친화성
  • 부하 균등화
  • 대칭적 다중 스레딩(SMT: Symmetric Multi-Threading)
• 스레드 스케줄링

CPU 스케줄링이란 무엇인가?

단일 처리기 시스템에서는 한 순간에 오직 하나의 프로세스만 실행이 될 수 있었지만 다중 처리기 시스템에서는 어느 한 순간에 다수의 프로세스들이 메모리 내에 위치하게 되고 여러개의 CPU가 수많은 프로세스들을 처리하며 복잡하게 움직입니다. 운영체제는 CPU에게 여러 프로세스들을 계속해서 배분하고 교환해 줍니다. 가령 하나의 프로세스가 대기해야 할 때 다른 프로세스가 CPU 사용을 양도받아 CPU가 쉬지않고 작업을 처리할 수 있게 해 줍니다.

모든 컴퓨터 자원들은 사용되기 전에 스케줄링 되며, 따라서 CPU 스케줄리은 운영체제 설계의 핵심이라고 볼 수 있습니다.

프로세스는 어떤 식으로 동작하나요?

우리는 운영체제가 CPU에게 다수의 프로세스들을 효과적으로 배분해 줌을 배웠습니다.
CPU가 프로세스를 어떻게 스케줄링 해 주는지 배우기 전에 먼저 프로세스가 CPU에서 어떻게 동작하는지를 살펴봅시다.

먼저, 프로세스의 실행은 CPU 실행과 입출력 대기의 사이클로 구성되며, CPU의 실행은 CPU 버스트 로 부터 시작되고, 입출력은 입출력 버스트 로 부터 시작이 됩니다. 이렇게 CPU 버스트와 입출력 버스트가 교대로 발생하면서 프로세스가 진행이 됩니다. 프로그램 마다 이러한 CPU 버스트와 입출력 버스트의 시간 분포가 매우 상이합니다. 가령 입출력이 중심이 되는 상대적으로 짧은 CPU 버스트 시간을 가질 것이며, CPU 중심 프로그램은 상대적으로 긴 CPU 버스트 시간을 가지게 되며, 이러한 버스트의 분포는 CPU 스케줄링 알고리즘을 선택하는 데에 있어 매우 중요한 역할 을 합니다.

CPU 스케줄링은 누가 수행하나요?

CPU 스케줄링은 CPU 스케줄러(단기 스케줄러)에 의해 수행되며, CPU가 유휴 상태가 될 때마다 CPU 스케줄러는 준비완료 큐에 있는 프로세스 중 하나를 선택하여 실행합니다. 여기서 준비완료 큐 는 반드시 선입선출(FIFO) 방식으로 동작하지 않아도 되며 이제까지 배운 다양한 자료구조들을 통해 구현될 수 있습니다. 예를 들어 선입선출 큐, 우선순위 큐, 트리 등 다양한 자료 구조를 통해 구현되어집니다. 개념적으로 볼 때 준비완료 큐에 있는 모든 프로세스들은 CPU에서 실행될 기회를 기다리면 대기하고 있으며, 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB) 입니다.

스케줄링의 방법들

CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.

1. 한 프로세스가 실행 상태에서 대기 상태로 전활될 때
2. 프로세스가 실행 상태에서 준비완료 상태로 전활될 때
3. 프로세스가 대기 상태에서 준비완료 상태로 전환될 때
4. 프로세스가 종료할 때

위의 1, 4의 경우 스케줄링 면에서는 선택의 여지가 없고 반드시 선택되어야 하며, 이러한 상황에서 스케줄링이 발생할 경우 우리는 이러한 스케줄링 방법은 비선점 또는 협조적 스케줄링이라고 말합니다. 그렇지 않으면 선점 스케줄링 이라고 합니다. 현대의 운영체제들은 이러한 선점 스케줄링 을 기반으로 하지만, 선점 스케줄링은 공유 자료에 대한 접근을 조정하는 데 필요한 비용을 발생시킵니다. 가령 프로세스 A가 쓰기 작업을 하는 중에 프로세스 B가 A 가 쓰고 있는 파일을 읽어들이는 경우를 생각해 보면, A 라는 프로세스가 컴퓨팅 자원을 선점 하고 있었으므로 프로세스 B가 이 자료에 접근을 하지 못하도록 막아야 할 필요가 생기게 되는 됩니다.

누가 프로세스에게 제어권을 주나요?

디스패처 는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 넘겨주는 모듈이며 다음과 같은 작업을 수행합니다.

1. 문맥을 교환하는 일
2. 사용자 모드로 전환하는 일
3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

스케줄링의 기준

위에서는 CPU 스케줄링이 무엇이고 어떤 방식으로 수행이 되는지를 알아보았습니다.
이제는 실제로 스케줄링 알고리즘을 설계하려고 할 때, 과연 어떤 기준에 따라 프로세스들을 선택하고 스케줄링을 해야 할까요?
다음에는 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되며, 이러한 특성에 따라 최선의 알고리즘을 결정하는 데 큰 차이가 있습니다.

1. CPU 이용률
2. 처리량
3. 총처리 시간
4. 대기 시간
5. 응답 시간

스케줄링의 기준을 간단히 말하자면 CPU 이용률과 처리량을 최대화 하고, 총처리 시간, 대기시간, 응답시간을 최소화 하는 것에 있습니다.

스케줄링 알고리즘

실제로 프로세스들을 스케줄링 하려고 할때 쓰이는 스케줄링 알고리즘 에는 무엇이 있을까요?
다양한 스케줄링 알고리즘들을 소개합니다.

선입 선처리 스케줄링

가장 간단한 CPU 스케줄링 기법으로, 먼저 들어온 프로세스가 CPU를 할당받는 방식입니다.

최단 작업 우선 스케줄링

SJF(Shortest Job First) 알고리즘의 대표적인 예로, 이 알고리즘은 각 프로세스에 CPU 버스트 길이를 연관시켜, 짧은 CPU 버스트를 가지는 프로세스에게 우선적으로 CPU를 할당해 주는 방식입니다.

우선 순위 스케줄링

각 프로세스 마다 우선순위를 부여하고 우선순위가 높은 프로세스에게 CPU를 먼저 할당하는 알고리즘 입니다.
프로세스가 준비완료 큐에 도착하면, 새로 도착한 프로세스와 현재 실행중인 프로세스의 우선순위를 비교하여 높은 우선순위를 가진 프로세스 에게 CPU를 할당해 줍니다.

하지만, 이 알고리즘은 무한 봉쇄 또는 기아상태(starvation) 에 빠질 수 있는 문제점을 가지고 있습니다.
예를 들어 낮은 우선순위를 가진 프로세스들으 무한정 대기완료 큐에서 대기하는 경우가 발생하게 되는데 이러한 경우에 대한 해결방안으로 노화 알고리즘을 포함시켜 오랫동안 시스템에서 대기한 프로세스들의 우선순위를 점진적으로 올려주는 방식입니다. 따라서 오랫동안 대기완료 큐에서 머문 프로세스들은 자연스레 우선순위가 올라가게 되고 최종에는 CPU를 할당받을 수 있게 됩니다.

라운드 로빈 스케줄링

라운드 로빈 알고리즘은 특별히 시분할 시스템을 위해 설계된 알고리즘 입니다. 시분할 알고리즘에서는 각 프로세스가 일정 구간으로 나눈 시간을 계속해서 배정받으면서 CPU 가 같은 시간동안 프로세스들을 돌면서 작업을 처리하게 됩니다. 즉, CPU 스케줄러는 준비완류 큐를 돌면서 한번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당합니다. 이러한 라운드 로빈 큐를 위해서 우리는 준비완료 규를 선입선출 큐로 유지합니다.

다단계 큐 스케줄링

다단계 피드백 큐 스케줄링

다중 처리기 스케줄링

위의 모든 방법론들은 단일 처리기 시스템을 스케줄 하는 문제에 초점을 두고 배워보았다. 이번 장에서는 여러 개의 CPU가 있는 다중 처리기 시스템에서의 CPU 스케줄리에 대해 배워보도록 합시다.

다중 처리기 시스템에 대한 접근방법

다중처리기 시스템의 CPU 스케줄링의 한가지 방법은 비대칭 다중처리(Asymmetric Multi-processing) 입니다. 비대칭 다중처리란 주 서버라는 하나의 처리기가 나머지 모든 처리기에 대한 통제권을 가지고 모든 스케줄링을 결정하고 입출력 처리 그리고 다른 시스템의 활동을 처리하게 하는 것 입니다. 이 방법은 오직 하나의 처리기 에서만 자료구조에 접근하므로 정보의 공유가 필요 없다는 장점이 있습니다.

다른 해결방안은 대칭 다중처리(SMP: Symmetric Multi-processing) 입니다. 대칭 다중처리 에서는 모든 처리기의 스케줄러가 준비완료 큐를 검사해서 실행할 프로세스를 선택함으로써 진행됩니다. 여러 개의 처리기가 공통의 자료구조를 처리하려고 한다면 문제가 발생합니다. 때문에 각 처리기가 공동 자료구조를 접근하고 갱신하려고 한다면 스케줄러가 신중하게 프로그램 되어야 합니다.

처리기 친화성

위에 설명한 대칭 다중 처리기를 살펴보면 각 처리기가 독자적으로 프로세스를 처리하므로 특정 처리기에서 다른 처리기로 프로세스가 이동 하면 각 처리기의 캐시에 해당 프로세스의 정보가 적재되게 될 것입니다. 그렇게 된다면 전에 있던 처리기의 캐시에 있던 정보가 삭제되고 이동한 처리기의 캐시가 체워져야 하는데 이는 큰 비용을 초래합니다. 때문에 대부분의 SMP 시스템은 한 처리기에서 다른 처리기로의 이주를 피하고 대신 같은 처리기에서 프로세스를 실행시키려고 하는데 이러한 성질을 처리기 친화성 이라고 합니다. 즉, 프로세스가 현재 실행 중인 처리기에 친화성을 가지는 것을 말합니다.

부하 균등화

다중 처리기 스케줄링 에서는 처리기가 여러개 이기 때문에 각각의 처리기가 균등하게 사용되는 것이 매우 중요합니다. 이렇게 각 처리기에 부하가 잘 분산되는 것은 부하 균등화 라고 부릅니다. 공용 실행 큐만 있는 시스템 에서는 한 처리기가 쉬게 되면 바로 공용 큐에서 프로세스를 불러와 실행하므로 문제가 없습니다. 하지만 현대의 대부분의 컴퓨터들은 자신만의 전용 큐 를 가지고 있기 때문에 각 처리기가 별도의 큐에서 프로세스를 가져와서 실행하게 됩니다.

이렇게 자신만의 전용 큐를 가지고 있는 처리기의 경우 push 이주(migration) 과 pulll 이주(migration) 을 통해 부하를 분산합니다. 푸시 이주의 경우는 부하가 높은 처리기가 프로세스를 다른 처리기로 넘기는 것을 말하며, pull 이주의 경우는 한가한 처리기가 바쁜 처리기의 프로세스를 가져오는 것을 의미합니다.

대칭적 다중 스레딩(SMT: Symmetric Multi-Threading)

SMP 시스템은 다수의 물리 처리기를 제공함으로써 다수의 스레드가 동시에 실행되게 합니다. 여기서 SMT의 착상은 동일한 처리기 상에서 여러 개의 논리 처리기 를 생성하는 것입니다. 각 논리 처리기는 구조 상태 를 가지게 되며 이때 인터럽트가 물리처리기가 아닌 논리적 처리기에 전달되고 처리되는 것을 의미합니다.

스레드 스케줄링

스레드는 경량의 프로세스라고 일컬어 지며, CPU 가 처리하는 task의 최소한의 단위가 된다.

이런한 thread 와 process 의 차이는 바로 공유하는 메모리 공간의 차이인데, process 는 stack 과 heap 을 모두 공유하지 않기 때문에 서로 다른 프로세스를 메모리 공간을 공유하지 않으며, 때문에 여러 프로세스 사이의 통신은 매우 어렵다. 반면, thread 는 stack 은 공유하지 않고 따로 존재하며 heap 는 공유하기 때문에 같은 메모리 공간을 공유한다. 즉, 각 thread 는 공통된 변수 및 메모리 공간에 접근이 가능하기 때문에 쉽게 통신할 수 있으나 다른 작업 que 를 가지기 때문에 병렬적으로 처리되어 병렬성을 가질 수 있다.

여러개의 thread 는 CPU 에 할당되는 시점에 CPU affinity 를 가지고 할당되기 때문에, 가급적 하나의 CPU 에서 처리된다.

• 운영체제가 하는 일은 무엇인가?
• 컴퓨터 시스템은 어떻게 구성되어 있는가?
  • 컴퓨터 시스템의 동작
  • 저장 장치의 구조
  • 입출력 구조
• 단일 처리기 시스템에서 다중 처리기 시스템으로
  • 단일 처리기 시스템
• 운영체제의 구조
• 운영체제는 어떤 방식으로 작업을 처리하는가?
• 프로세스 관리
• 메모리 관리
• 저장 장치 관리
• 보호와 보안
• 분산 시스템

운영체제가 하는 일은 무엇인가?

운영체제란 컴퓨터 하드웨어를 관리하는 프로그램입니다.
운영체제는 사용자의 관점에서 혹은 시스템 적인 관점에서 보는가에 따라 그 존재 목적이 달리 설명될 수 있습니다.

사용자의 관점에서의 운영체제는 바로 한낱 고철덩어리에 불과한 컴퓨터를 사람이 사용하기 쉽게 여러가지 일들을 수행해 주는 역할을 한다고 볼 수 있다.
이 경우 운영체제는 주로 사용의 편리와 자원의 이용 간에 적절히 조화를 이루도록 설계된다.

시스템의 관점에서 운영체제는 하드웨어와 가장 밀접한 프로그램이라고 볼 수 있다. 컴퓨터 시스템은 특정 문제를 해결하기 위해 필요한 여러가지 자원들을 사용하는데(가령 CPU 시간, 메모리 공간, 파일 저장 공간, 입출력 장치 등) 운영체제는 이러한 자원의 관리자로써 동작 하여 자원 할당자 역할을 수행한다.

결과적으로, 운영체제를 명확히 정의하는 것은 매우 어렵지만 컴퓨터라는 순수 하드웨어를 보다 쉽게 사용하기 위한 다양한 응용 프로그램들을 원활하게 동작시키기 위해 입출력 장치의 통제와 같은 공통적인 연산과 CPU, 메모리 공간 등의 컴퓨터 자원을 제어하고 할당하는 기능을 하는 하나의 소프트웨어라고 정의할 수 있을 것 같다. 또한, 운영체제는 컴퓨터에서 항상 실행되는 프로그램(일반적으로 커널)으로 운영체제를 제외한 다른 모든 프로그램은 응용 프로그램으로 부른다.

컴퓨터 시스템은 어떻게 구성되어 있는가?

컴퓨터 시스템의 동작을 배우기 전에 컴퓨터 시스템의 구조에 대해 간략하게 알아봅시다.

컴퓨터 시스템의 동작

현대의 컴퓨터 시스템은 공유 메모리에 대한 접근을 제공하는 공통 버스를 통해 연결된 여러 개의 장치 제어기 와 하나 이상의 CPU 로 구성되어 있다. 각 장치 제어기는 특정 장치(가령 디스크 드라이브, 오디오 장치, 비디오 디스플레이 등)를 관리 하며, CPU와 장치 제어기는 메모리 사이클을 얻기 위해 경쟁하면서 병행 실행될 수 있다.

컴퓨터를 구동시킬 때는 가장 먼저 흔히 펌웨어 로 알려져 있는 컴퓨터 내의 읽기 전용 메모리(ROM)에 저장된 부트스트랩 프로그램 을 실행한다.
부트스트랩 프로그램은 CPU 레지스터로 부터 장치 제어기, 메모리 내용 등을 포함한 시스템의 모든 면을 초기화 하고 운영체제의 커널을 찾아 메모리에 적재한다.
적재가 완료되면 운영체제는 init과 같은 초기 프로세스를 동작하고 사건이 발생하기를 기다린다.

기본적으로 운영체제는 이렇게 사건을 기반으로 동작하게 되는데, 이러한 사건의 발생 사실을 인터럽트 에 의해 통보받을 수 있다.
하드웨어는 언제든지 시스템 버스 를 통해 인터럽트를 발생시킬 수 있고, 소프트웨어는 시스템 호출 을 통해 인터럽트를 발생시킬 수 있다.

인터럽트가 발생되면 적절한 서비스 루틴으로 전달하고 이 루틴은 이어 인터럽트 고유의 핸들러를 호출한다.

저장 장치의 구조

컴퓨터가 프로그램을 실행하기 위해서는 프로그램이 반드시 주 메모리(RAM) 에 있어야 한다.
컴퓨터가 명령어를 실행한다는 것은 이 메모리로 부터 레지스터로 워드를 옮기는 적재(load) 과정을 통해 이루어 지며, 적재된 명령어는 명령 레지스터에 저장되고 명령이 해독되어 메모리에서 피연산자를 인출하여 내부 레지스터에 저장되도록 유발할 수 있다. 여기서 메모리 장치는 단지 연속적인 메모리 주소만을 인식하며 메모리는 주소값의 구체적인 생김새 등에는 관계없이 단지 주소값을 저장만 하고 있다.

이상적으로는 프로그램과 데이터가 주 메모리 안에 영구히 존재한다면 좋지만, 메모리는 용량이 너무 작고 전원이 공급되지 않으면 내용을 잃어버리는 휘발성 저장장치이기 때문에 반드시 보조 저장장치에 프로그램과 데이터를 보관해야 한다. 이러한 보조 저장장치로는 주로 자기 디스크 등이 쓰인다.

이러한 저장 장치의 구조는 하나의 계층으로 구성되며 저장 장치 구조의 최상단인 레지스터 부터 캐시, 주 메모리 순으로 내려 가면서 가격은 저렴해 지고 속도는 느려지는 피라미드형 구조를 보인다.

입출력 구조

컴퓨터에 입력을 하고 또 출력 값을 받아오기 위해 다양한 입출력 장치들이 연결될 수 있으며, 범용 컴퓨터 시스템은 공통 버스에 의해 연결된 여러 개의 장치 제어기와 CPU 들로 구성된다.
장치 제어기는 자신이 제어하는 주변장치와 자신의 로컬 버퍼 저장장치 사이의 데이터 전송을 담당하며, 통상적으로 운영체제는 장치 제어기 마다 장치 드라이버 를 가지고 있는데, 이 장치 드라이버는 장치 제어기의 동작을 이해하고 운영체제의 다른 부분에게 장치에 대한 일관된 인터페이스를 제공한다.

장치->장치 제어기->장치 드라이버->운영 체제
로 이어지는 입출력의 흐름은 인터럽트 를 기반으로 이루어진다. 먼저, 장치 제어기는 취할 동작을 결정하고 장치에 연산이 완료되었으면 인터럽트를 이용하여 장치 드라이버에 통보한다. 그러면 장치 드라이버는 제어를 운영체제에게 반환하는 방식이다. 하지만 이러한 인터럽트 구동방식은 대량의 데이터를 전송하는 데에는 높은 오버헤드를 초래하였으며, 이를 해결하기 위해 직접 메모리 접근(DMA) 장치가 사용된다. 이를 통해 장치 제어기는 CPU의 개입 없이 메모리로 부터 자신의 버퍼 장치로 또는 버퍼로부터 메모리로 데이터 블록 전체를 전송한다. 즉, 장치 제어기가 전송 작업을 실행하고 있는 동안 CPU는 다른 작업을 실행할 수 있다.

단일 처리기 시스템에서 다중 처리기 시스템으로

컴퓨터 시스템은 사용된 범용 처리기(CPU)의 개수에 따라 단일 처리기 시스템 과 다중 처리기 시스템 으로 나누어 집니다.
하나의 CPU를 가지는 경우를 단일 처리기 시스템, 1개 이상의 CPU를 가지는 컴퓨터 시스템의 경우를 다중 처리기 시스템이라고 합니다.

하나의 CPU를 가질 때 보다 여러개의 CPU를 가지면 무엇이 좋을까요?

먼저, 시스템의 처리량이 증가 합니다.
여러 개의 CPU를 가지게 되면 컴퓨터가 여러개의 일들을 동시에 처리할 수 있기 때문에 같은 시간동안 많은 양을 처리하게 되어 시스템의 처리량이 증가합니다.

비용이 절감됩니다.
컴퓨터 하나에는 많은 주변 장치, 저장 장치, 전원 장치 등이 필요합니다.
5대의 하나의 CPU를 사용하는 컴퓨터를 제작하는 것 보다 5개의 CPU를 가진 컴퓨터 한대를 제작하는 것이 많은 디바이스와 리소스를 공유해서 이용하기 때문에 규모의 경제 가 나타나고 저렴한 비용으로 시스템을 만들 수 있습니다.

믿을 수 있습니다. 즉, 신뢰도가 올라갑니다.
CPU 하나가 고장나더라고 시스템이 정지하지 않고 살아남은 하드웨어 수준에 비례하여 지속적으로 서비스가 동작하는 것은 우아한 퇴보 라고 합니다.
어떤 시스템은 하나의 구성요소의 고장에도 불구하고 시스템을 동작할 수 있기에 결함 허용 적이라고 불리며, 다중 처리기 시스템은 하나의 CPU가 고장나도 안정적으로 시스템이 동작하므로 단일 처리기 시스템에 비해 신뢰도가 높은 시스템을 구축할 수 있습니다.

이러한 다중 처리 시스템의 경우 각 처리기에 일이 할당되는 방식에 따라 비대칭적 다중 처리 와 대칭적 다중 처리 로 구분되는데, 비대칭적 다중 처리의 경우 하나의 주 처리기가 시스템을 제어하고 다른 처리기들이 복종하는 시스템이며, 대칭적 다중 처리의 경우 모든 처리기가 동등한 업무를 수행하는 방식이며 현대에는 대부분 대칭적 다중 처리가 이용된다.

단일 처리기 시스템

하나의 주 CPU를 사용하는 시스템으로

운영체제의 구조

컴퓨터 시스템의 구성과 구조를 알아 보았으므로 이제는 본격적으로 운영체제에 대해 알아 보겠습니다.
운영체제의 가장 중요한 측면은 다중 프로그램(multi program)을 할 수 있는 능력입니다. 만약, 한명의 사용자가 컴퓨터를 사용한다면 아무리 노력해도 컴퓨터를 효과적으로 사용하여 모든 처리기를 바쁘게 유지시킬 수 없을 겁니다. CPU가 잠시라도 쉬면 서둘러 다른 업무를 시켜서 쉬지않고 일을 하도록 하는 다중 프로그래밍 은 CPU가 항상 하나의 작업을 수행하도록 조정함으로써 CPU의 이용률을 높여줍니다.

이러한 다중 프로그래밍의 기본적인 동작 원리는 다음과 같습니다.
먼저 한 번에 여러 작업을 메모리에 적재하고, 운영체제는 메모리에 있는 작업 중 하나를 선택해서 실행합니다. 만약 이 작업이 어떤 일을 기다려야 한다면 CPU는 다른 작업으로 전환하여 다른 작업을 진행합니다. 이러한 다중 프로그래밍 시스템은 시스템 자원을 효율적으로 이용할 환경을 제공하지만 사용자와 컴퓨터 시스템이 상호작용을 할 수는 없는데, 이를 확장한 시분할(multi tasking) 을 통해 이를 해결할 수 있습니다. 시분할 시스템에서는 CPU가 다수의 작업을 서로 교대로 실행하지만 매우 빈번하게 교대를 일으킴으로써 프로그램이 동작하는 동안 사용자와 상호작용이 가능해 지기에, 시분할 프로그램은 대화식 혹은 hands on(실제 조작 가능한) 컴퓨터 시스템을 필요로 하며, 각 사용자에게 시분할 되는 컴퓨터의 작은 부분을 제공하기 위해 CPU 스케줄링과 다중 프로그래밍을 사용합니다.

시분할과 다중 프로그래밍 운영체제에서는 메모리에 여러 작업이 동시에 유지되어야 하는데, 일반적으로 주 기억장치(RAM)은 사이즈가 너무 작기 때문에 메모리에 들어가지 못한 작업들을 디스크의 작업 풀 에 보관된다. 이런 작업 풀에서 어떤 프로그램을 메모리에 적재할 지 선택하는 것을 CPU 스케줄링 이라고 한다.

또 다른 방법 중 하나는 가상 메모리 를 이용하는 것이다. 이것은 프로그램의 일부만이 메모리에 존재해도 작업을 실행을 허용하는 개념이기에, 프로그램 전체가 주 메모리에 적재되지 않아도 프로그램이 시작되고, 또 주 메모리의 전체 사이즈보다 큰 규모의 프로그램도 실행 할 수 있게 해 주는 중요한 개념이다. 이런 가상 메모리 는 주 메모리를 크고 균등한 저장장치의 배열로 추상화하여 사용자에게 보이는 논리 메모리 를 실제 물리 메모리로부터 분리시켜 주며, 이를 통해 프로그래머를 메모리 저장장치의 한계로부터 자유롭게 해 준다.

운영체제는 어떤 방식으로 작업을 처리하는가?

현대의 운영체제는 인터럽트 구동식 으로 무언가 일이 일어나야만 동작을 한다. 사건은 트랩 혹은 인터럽트에 의해 발생하며 여기서 트랩 이란 오류 혹으 사용자 프로그램의 운영체제 서비스 실행 요청에 의해 유발되는 소프트웨어의 실행에 의해 생성된 인터럽트이다. 때문에 운영체제는 수많은 인터럽트들을 계속해서 처리해야 하며, 이중 하나만 잘못되어도 시스템이 정지한다면 그 시스템은 매우 불완전하다고 볼 수 있다.
올바르게 설계된 운영체제는 잘못된 또는 악의적인 프로그램이 부정확하게 실행되지 않도록 보장해야 한다.

이렇게 안정성 있는 운영체제를 위해 운영체제 내에는 다양한 안정 장치들이 있는데 그중 하나가 이중 동작 모드 이다.
이중 동작 모드란 운영체제의 적절한 동작을 보장하기 위해서 운영체제 코드와 사용자가 작성한 코드의 실행을 구분하는 것이다. 이렇게 구분된 각각의 명령은 독립된 동작모드인 사용자 모드 와 커널 모드 혹은 특권 모드 로 나뉘어 실행되게 된다. 만약 트랩 이나 인터럽트 가 발생할 때마다 하드웨어는 사용자 모드에서 커널 모드로 전환한다.

또다른 안전장치는 타이머 인데, 이는 사용자의 프로그램이 무한루프에 빠져 동작하지 않게 되어 운영체제로 통제권이 돌아오지 않는 경우를 막기 위해 특정 시간이 지나면 제어가 자동으로 운영체제로 넘어가게 하는 기능이다.
타이머가 인터럽트를 발생시키면 제어는 자동적으로 운영체제로 넘어가게 된다.

프로세스 관리

실행중인 프로그램을 프로세스 라 하며, 프로세스가 끝나면 운영체제는 재사용 할 수 있는 자원을 회수하게 된다.
여기서 프로그램 자체는 프로세스 가 아니다. 하나의 프로그램은 디스크에 저장된 파일의 내용과 같이 수동적인 개체인 반면, 프로세스는 다음 실행할 명령을 지정하는 프로그램 카운터 를 가진 능동적인 개체이다.
운영체제는 프로세스 관리와 관련하여 다음과 같은 활동을 수행한다.

1. 사용자 프로세스와 시스템 프로세스의 생성과 제거
2. 프로세스의 일시 중지와 재싱행
3. 프로세스 동기화를 위한 기법 제공
4. 프로세스 통신을 위한 기법 제공

메모리 관리

메모리는 컴퓨터 시스템에서 매우 중요한 부분이며, 운영체제는 이러한 메모리를 관리하며 다음과 같은 일을 담당한다.

1. 현재 메모리의 어느 부분이 사용되고 있으며, 누구에 의해 사용되고 있는지를 추적
2. 어떤 프로세스들을 메모리에 적재할 것이며 제거할 것인가?
3. 메모리 공간을 할당하고 회수

저장 장치 관리

보호와 보안

분산 시스템