RISC(Reduced Instruction Set Computer) 란?

RISC 란 Reduce Instruction Set Computer 의 약자로 말 그대로 축소 명령어 세트 컴퓨터를 의미합니다.
여기서 명령어 세트가 축소되었다는 말은 말 그대로 명령어의 개수가 적은 것을 말합니다. 핵심적인 명령어를 기반으로 최소한의 명령어 세트를 구성함으로써 파이프라이닝 이라는 획기적인 기술을 도입할 수 있어 빠른 동작 속도와 하드웨어의 단순화와 효율화를 시킬 수 있었고, 가격 경쟁력에서도 우위를 점했습니다.

즉, RISC란 CISC의 길고 복잡한 명령어들을 짧고 처리가 가능한 여러개의 명령어로 체계적으로 바꾼 것입니다.

RISC의 특징

1. 적은 명령어 세트
2. 간단한 명령어로 빠른 실행속도
3. 고정적인 명령어 길이
4. 워드, 데이터 버스 크기가 동일하고 실행 사이클도 모두 동일
5. 회로 구성이 단순함
6. 프로그램을 구성할 때 상대적으로 많은 명령어가 필요
7. 파이프 라이닝을 사용함
8. 명령어 개수가 적어서 컴파일러가 단순하게 구현됨

CISC(Complex Instruction Set Computer) 란?

연산을 처리하는 복잡한 명령어들을 수백개 이상 탑재하고 있는 프로세서입니다. CISC는 명령어 개수 증가에 따라 프로세서 내부구조가 매우 복잡해 지고, 고속으로 적동되는 플세서를 만들기 힘듭니다.

여기서 명령어가 복잡하다는 것의 의미는 하나의 명령어가 할 수 있는 일의 양이 RISC 대비하여 많다는 것을 의미합니다. 명령어 마다 길이가 다르고, 실행에 필요한 사이클 수도 다르기 때문에 pipelining 설계가 어려우며 한 바이트 명령어 부터 100바이트 이상되는 명령어 들도 있습니다.

이렇게 CISC는 RISC에 비해 성능이 많이 떨어지지만 다음과 같은 이유 때문에 아직도 쓰이고 있습니다.

CISC의 특징

1. 명령어의 개수가 많음
2. 명령어 길이가 다양하며, 실행 사이클도 명령어 마다 다름
3. 회로구성이 복잡함
4. 프로그램을 만들 때 적은 명령어로 구현 가능
5. 다양한 명령어를 사용하기 때문에 컴파일러가 복잡함

CISC를 사용하는 이유

1. 아직 너무도 많은 프로세서가 CISC 모델로 구축되어 있고, 이것을 전부 바꾸는 것은 너무 큰 비용이 든다.
2. CISC 성능의 취약점은 RISC와 같은 파이프라인을 일부 사용하고 집적도는 더 높임으로써 부분적으로 보완이 가능하다.
3. RISC에 비해 호환성이 좋다.

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

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

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

임계영역 문제(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. 편의성
   한 사용자가 동시에 여러 태스크를 가지는 경우 필요합니다.

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

공유 메모리 모델

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

메시지 전달 모델

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

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

소켓

• 캐시란 무엇인가요?
  • 캐시에 데이터 쓰기
• 캐시 성능의 측정
• 캐시 성능의 향상
  • 유연한 블록 배치를 통한 캐시 실패 줄이기
    • 완전 연관 방식
    • 집합 연관 방식
  • 다단계 캐시를 이용한 실패 손실 줄이기

캐시란 무엇인가요?

캐시란 메모리와 프로세서 사이에 있는 메모리 계층을 나타내기 위해 선택된 이름이며, 오늘날 대부분의 컴퓨터가 캐시 메모리를 사용하고 있습니다.
위의 도서관에서의 예처럼 캐시는 ‘책상’ 의 역할을 수행합니다. 우리는 도서관에서 책상위의 책들을 뒤적거려 책을 찾는다면 캐시는 어떻게 정보를 찾을 까요? 캐시는 다양한 형태로 구성되지만 이번 강의에서는 가장 대표적인 캐시 내의 정보를 찾는 방법으로 직접 사상 캐시 를 기반으로 하여 설명을 진행합니다. 직접 사상 이란 바로 메모리 주소에 기반하며 메모리 주소 하나당 캐시 내의 정확한 하나의 물리적 위치가 사상되는 방식입니다. 이러한 직접 사상 방식에서 실제 물리 메모리는 주소값 을 가지는데 이 주소값의 마지막 몇자리를 인덱스로 하여 캐시에 저장이 됩니다. 가령 물리 메모리의 주소값이 0101100101 이고, 블록의 수가 8개 라면 끝의 3자리(log2_8)는 인덱스 필드로 캐시 내에서의 주소를 담당합니다.
모든 직접 사상 캐시는 블록을 찾기 위하여 다음의 사상 방식을 사용합니다.

(블록주소) modulo (캐시 내에 존재하는 전체 캐시 블록 수)

위의 사상 방식을 따르면 10101011, 11101011, 00101011 처럼 끝의 인덱스 필드가 같은 메모리의 정보들을 캐시 메모리에서 같은 블록에 사상될 것입니다. 이렇게 되면 가져온 블록이 정말 원하는 정보인지 알 수 있어야 하며 이를 위해 태그 필드가 존재합니다. 이 태그 필드는 주소 중에서 인덱스 필드를 제외하고 남은 숫자들이며 이를 통해 해당 블록이 찾고자 하는 블록인지 알 수 있습니다.

캐시 블록은 항상 유효한 숫자를 가지고 있을까요?
만약 캐시가 비어있고나 혹은 올바르지 못한 값을 가지고 있는 경우가 있을 수 있습니다. 심지어 이 데이터는 물리 주소에 없는 값일 수도 있고요, 그렇다면 이러한 블록을 어떻게 표기해야 할까요?
이를 위해 캐시에는 유효 비트 라는 것이 존재합니다. 이 비트가 1로 설정되어 있지 않으면 유효한 블록이 없는 것으로 간주합니다.

이처럼 캐시는 예측 기법 을 통해 자료의 찾는 속도를 빠르게 해 주는 역할을 하며, 현대 컴퓨터에서 캐시 예측 적중률은 95% 이상입니다.

필요한 캐시의 사이즈는 어떻게 알 수 있나요?
필요한 캐시의 사이즈는 전체 블록의 수와 블록의 크기를 가지고 알 수 있습니다.
여기서 가장 중요한 점은 캐시는 몇개의 블록으로 구성되지만 블록이 정확한 값을 들고 있는지 알기 위해서 태그 필드 와 유효 비트(1비트) 를 별도로 필요하게 되며, 이것은 블록의 사이즈와 별도로 필요한 공간 이라는 점입니다. 또한, 인덱스 필드 의 경우는 캐시 메모리에 영향을 주지 않는데, 그것은 바로 인덱스 필드는 별도로 비트 필드를 가지지 않아도 하드웨어에서 물리적인 주소로 바로 연결이 되는 것이기 때문에, 인덱스를 가르쳐 주기 위한 별도의 비트는 필요하지 않습니다.

예를 들어,
32비트의 직접 사상 캐시가 있고, 2^n개 블록 을 가지고 있다고 하면 당연히 n개의 비트는 인덱스 필드 에 사용됩니다.
또 실제 캐시에서는 블록의 크기가 1워드보다 보통 크기 때문에, 만약 블록의 크기가 2^m개 워드 라고 하면 m개 비트는 블록 내부에서 워드를 구분 하는 데에 사용되며 하나의 워드는 4바이트로 구성되므로 2 개의 비트는 주소 중 바이트 구별용 으로 사용됩니다.

이 경우 태그 필드의 길이는

32-(m+n+2) 가 되며,

직접 사상 캐시의 전체 비트 수는
2^n * (블록 크기+태그 크기+유효 비트 크기) 이므로

2^n _ (2^m _ 32 + 32-n-m-2 + 1) = 2^n(32*2^m+31-n-m) 비트 이다.

캐시 실패의 경우는 어떻게 처리되나요?
만약 캐시에서 원하는 정보를 찾지 못하는 경우에는 임시 레지스터와 프로그래머에게 보이는 레지스터의 내용을 그대로 유지한 채 메모리로부터 데이터가 오기를 기다리면서 전체 시스템이 지연되게 됩니다. 캐시 실패의 처리 단계는 다음과 같습니다.

1. 원래의 PC값(현재 PC 값 -4)을 메모리로 보낸다.
2. 메인 메모리에 읽기 동작을 지시하고 메모리가 접근을 끝낼 때까지 기다린다.
3. 메모리에서 인출된 데이터를 데이터 부분에 쓰고, 태그 필드에 주소의 상위 비트를 쓰고 유효 비트를 1로 만들어서 캐시 엔트리에 쓰기를 수행한다.
4. 명령어 수행을 첫 단계부터 다시 시작하여 캐시에 명령어를 가져온다. 이제는 필요한 명령어를 캐시에서 찾을 수 있다.

캐시에 데이터 쓰기

캐시에 데이터를 수정하고 저장하는 경우 데이터 캐시에만 작성 되고 메인 메모리에는 쓰지 않아지는 불일치 가 나타날 수 있습니다. 이를 해결하는 방법 중 하나는 즉시쓰기(write through) 이며, 통해 데이터를 항상 메모리와 캐시에 동시에 작성하게 됩니다. 하지만 이는 프로세서의 성능을 심하게 저하시키고 보통은 쓰기 버퍼 를 활용하여 일단 캐시에만 작성하고 천천히 메모리에 작성되는 방식으로 처리합니다.

두번째 방법은 나중 쓰기(write-back) 입니다.
이 방식에서는 쓰기가 발생했을 때 새로운 값을 캐시 내의 블록에만 쓰고, 나중에 해당 블록이 캐시에서 쫓겨나는 경우 쓰기에 의해 내용이 바뀐 블록이라면, 메모리 계층 구조의 더 낮은 계층에 씌어집니다.

두 방식 모두 장단점이 있는데 이는 다음과 같습니다.

나중쓰기(write-back) 의 장점

1. 각각의 워드는 프로세서에 의해 메인 메모리가 아닌 캐시가 받아들일 수 있는 속도로 쓰인다.
2. 다수의 쓰기가 행해진 블록을 계층의 하위 계층에 한 번만 쓰면 된다.
3. 블록들이 하위 수준에 쓰일 때, 전체 블록을 한꺼번에 쓰기 때문에 높은 대역폭을 효과적으로 사용할 수 있다.

즉시쓰기(write-through) 의 장점

1. 실패가 발생해도 하위 수준 블록을 쓸 필요가 없으므로 간단하고 비용이 적게 든다.
2. 즉시 쓰기는 나중 쓰기보다 구현이 간단하다, 하지만 실제적으로 즉시 쓰기 캐시는 쓰기 버퍼를 요구한다.

가상 메모리 시스템에서는 계층의 하위 수준에 쓰기를 수행할 때 매우 큰 지연시간이 발생하기 때문에 나중 쓰기 방식이 유일한 실용적인 대안이다.

캐시 성능의 측정

캐시가 무엇인지 알았다면 실제 캐시의 성능을 측정하고 분석하는 방법을 배워 봅시다.

캐시의 성능을 측정할 때의 기준은 필요한 메모리를 인출한 시간이라고 볼 수 있으며, 그에 따른 CPU 시간은 다음과 같습니다.

CPU 시간 = (CPU 클럭 사이클 + 메모리 지연 클럭 사이클) X 클럭 사이클 시간

위의 식에서 메모리 지연 클럭 사이클은 주로 캐시 실패 때문에 생기며 다음과 같이 읽기 지연 사이클과, 쓰기 지연 사이클로 나누어 지며 그 값 또한 다음과 같이 계산 할 수 있습니다.

메모리 지연 클럭 사이클 = 읽기 지연 사이클 + 쓰기 지연 사이클

읽기 지연 사이클 = 읽기 접근 횟수 / 프로그램 X 읽기 실패율 X 읽기 실패 손실

쓰기 지연 사이클 = (쓰기 접근 수 / 프로그램 X 쓰기 실패율 X 쓰기 실패 손실) + 쓰기 버퍼 지연

캐시 성능의 향상

앞에서는 직접 사상 으로 구성된 캐시와 캐시의 성능 측정에 대해 알아보았습니다.

이번에는 캐시의 성능을 향상시키기 위한 방법을 알아봅시다.

유연한 블록 배치를 통한 캐시 실패 줄이기

기존에는 메모리 블록을 캐시에 넣을 때 각 블록이 캐시의 정확한 한 곳에만 들어갈 수 있는 단순한 배치 방법을 사용하였고, 이를 직접 사상 이라고 불렀습니다. 하지만, 실제로는 블록을 배치하는 다양한 방법이 존재하는데, 블록의 배치 방법에 따라 완전 연관 방식 과 집합 연관 방식 이 있습니다.

완전 연관 방식

완전 연관 방식에서는 블록이 캐시 내의 어느 곳에나 위치할 수 있으며, 때문에 블록 하나를 찾기 위해서 캐시 내의 모든 엔트리를 검색해야 합니다. 물론 이러한 방법은 하드웨어 비용을 크게 증가시키기 때문에 블록을 적게 갖는 캐시에서만 유용합니다.

집합 연관 방식

집합 연관 방식 은 직접 사상과 완전 연관 사상의 중간 방식입니다. 집합 연관 사상 캐시에서는 한 블록이 들어갈 수 있는 자리가 고정되어 있습니다. 가령 각 블록당 n개의 배치 가능한 위치를 갖는 집합 연관 캐시가 있다면 이를 n-way 집합 연관 캐시라고 부릅니다.

집합 연관 방식에서 메모리의 각 블록은 인덱스 필드에 의해 캐시 내의 한 집합으로 사상 되며, 때문에 일치하는 블록을 찾기 위해서는 집합 내의 모든 블록들을 검색 하여야 합니다. 직접 사상 캐시는 단순히 1-way 집합 연관 캐시라고도 볼 수 있습니다.

이렇게 연관 정도를 늘리는 것의 장점은 대개 실패율이 줄어든다는 것이며, 단점은 적중 시간의 증가입니다.
그 이유는 간단히 생각해 보면 이해할 수 있습니다. 가령 특정 블록을 찾을 때에 기존의 직접 사상 방식에서는 하나의 인덱스에 오직 하나의 블록만이 들어갈 수 있기 때문에, 다른 블록이 들어왔다면 기존의 블록을 삭제하고 새로운 블록을 저장하기 때문에 실패율이 높을 수 밖에 없습니다. 하지만 연관 방식 사상 을 통해서는 하나의 인덱스가 집합을 이루고 과거에 찾아진 블록이 해당 집합에 들어 있다면 캐시에 저장되어 있어 찾을 수 있으므로 실패율이 줄어들게 됩니다. 단점인 적중 시간의 증가도 같은 원리로 만약 하나의 블록을 특정 집합에서 찾았다면 기존의 직접 사상 방식에서는 각 집합마다 블록이 유일하게 존재하므로 집합 내에서 검색이 필요하지 않았습니다. 하지만 n-way 집합 연관 방식에서는 특정 집합을 찾을 이후에도 집합 내에서 n 개의 엔트리 중에서 일치하는 태그인 블록을 찾는 시간이 추가되기 때문에 적중 시간이 증가 하게 됩니다.

집합 연관 방식에서 집합 내의 블록은 어떻게 교체될까요?
집합 연관 방식 사상을 할 때 집합 내에는 정해진 수의 블록 만이 들어갈 수 있으므로, 집합이 가득 찾다면 기존의 블록이 새로운 블록으로 교체되어야 합니다. 이 경우 가장 많이 쓰이는 방법은 LRU 교체 방식 을 사용합니다. 즉, 가장 오래전에 사용된 블록이 교체 됩니다.

집합 연관 방식에서는 캐시 내에서 블록을 어떻게 찾을까요?
직접 사상 캐시에서와 같이 집합 연관 캐시 내의 블록도 블록 주소를 나타내는 주소 태그 를 가지고 있습니다. 선택된 집합 내 모든 블록의 태그는 프로세서로 부터 나온 태그와 일치하는 지를 검사하게 됩니다. 여기서 빠른 속도가 매우 중요하기 때문에 선정된 집합 내 모든 태그는 병렬로 검색이 수행됩니다.
완전연관 캐시 의 경우에는 실제로 한 개의 집합 만이 존재하며 모든 블록들은 병렬로 검사가 되게 됩니다.

다단계 캐시를 이용한 실패 손실 줄이기

현대의 모든 컴퓨터는 캐시를 사용하고 있으며, 프로세서의 빠른 클럭 속도와 상대적으로 점점 느려지는 메모리 접근 시간 사이의 차이를 줄이기 위해, 고성능 마이크로프로세서들은 캐시를 한 계층 더 사용합니다.

여기서 각 단계의 캐시들을 L1, L2, L3, L4 로 부르고 각각은 1차, 2차, 3차, 4차 캐시를 의미합니다.
다단계 캐시를 이용한 CPU 에서 1차 캐시에서 미스가 발생하면 2차 캐시에서 다시 검색을 하고 2차 캐시에서도 미스가 발생하면 메인 메모리 접근이 필요하게 되고 더 큰 실패 손실이 발생하게 됩니다.

1차 캐시와 2차 캐시의 설계 시에는 각자 다른 것을 우선시 합니다. 가령 1차 캐시의 경우에는 어차피 실패를 해도 2차 캐시에서 데이터를 찾는 작업이 일어나므로 메모리 접근이 필요 없기 때문에 실패율이 그다지 높지 않아도 됩니다. 대신, 제일 많이 접근이 되는 만큼 적중 시간의 최소화 에 초점을 맞추어 설계를 진행합니다. 반대로 2차 캐시 의 경우에는 실패가 일어나면 메인 메모리 접근이 필요하게 되기 때문에 긴 메모리 접근 시간으로 인한 손실을 줄일 수 있도록, 실패율이 중점을 맞춘 설계 를 합니다. 같은 원리로 1차 캐시는 실패 손실을 줄이기 위해 블록 크기가 더 작으며, 2차 캐시는 실패율을 줄이기 위해 크기가 더 크고, 높은 연관정도가 많이 사용된다.

m-원 탐색트리란 무엇인가?

B-트리를 배우기 전에 그 근본 개념이 되는 m-원 탐색트리에 대해 알아봅시다.
기존의 이진 탐색트리 에서 균형 이진 탐색트리인 AVL 트리의 경우 n 개의 노드에 대해서 깊이가 최소 logn에 가깝기 때문에, 실제 시스템에서 AVL 구조로 저장된 데이터에 접근하기 위해서는 만약 모든 노드가 다른 메모리 안에 들어 있다면 최악의 경우 logn번 만큼 메모리 혹은 디스크에 접근을 해야 했습니다.

이렇게 수 차례에 걸쳐 메모리 혹은 디스크에 접근하는 것은 치명적인 탐색 시간 상승을 야기했고, 이에 탐색 트리의 높이를 줄여 탐색시간을 줄이기 위한 많은 노력들이 있었고, 이를 위해서는 필수적으로 트리의 차수가 증가 해야 했습니다. m-원 탐색트리는 m개의 차수를 가지는 노드들로 구성된 트리이며, 실제로는 트리 노드들이 하나의 캐시 블록이나 디스크 블록을 체울 수 있는 가장 큰 차수를 사용하고 있습니다.

m-원 탐색트리의 정의는 다음과 같습니다.

m-원 탐색트리의 정의

m-원 탐색트리의 예시

B-트리란?

B-트리는 이러한 m-원 탐색트리의 일종이며 다음과 같이 정의됩니다.

차수가 m인 B-트리의 정의

B-트리의 예시

B-트리의 삽입

B-트리의 삭제

키가 x인 노드를 삭제하려고 할 때, x가 리프가 아닌 노드 z에서 발견될 경우, z에서 x가 차지하던 자리는 B-트리의 리프 노드로 부터 적당한 키로 채워진다. 가령 x가 그의 i번째 키라고 하면, E_i는 서브트리 A_i 내의 가장 작은 원소 혹은 서브트리 A_(i-1)의 가장 큰 원소로 채워질 수 있습니다. 여기서 삭제되는 리프노드 p에 대해 다음의 4가지 경우가 존재합니다.

CASE1

p 또한 루트노드인 경우
삭제 후 리프에 적어도 키가 하나 남아있다면 삭제 후 저장하고, 없다면 공백트리가 됩니다.

CASE2

삭제 후 p가 적어도 [m/2]-1 개의 원소를 가지고 있는 경우 즉, 최소 원소 개수가 만족되는 경우
그대로 삭제를 진행

CASE3 회전

p가 [m/2]-2개의 원소를 가지며, 인접한 형제노드 q가 적어도 [m/2]개 원소를 가지는 경우. 즉, p가 삭제 후 최소 키보다 적은 키를 가지고 있고 형제 노드는 최소 키 이상의 키를 가지고 있는 경우
다음과 같이 회전 을 진행합니다.

CASE4 병합

p가 [m/2]-2개의 원소를 가지고 있고, 가장 가까운 형제노드 q가 [m/2]-1개의 원소를 가지고 있는 경우. 즉, p가 삭제 후 최소 키보다 적은 키를 가지고 있고 형제 노드도 딱 최소 키만을 가지고 있는 경우
p,q와 p,q 중간 원소 E_i를 하나의 노드로 병합 합니다.

• 파이프라이닝이란
  • 파이프라인 해저드
  • 구조적 해저드
  • 데이터 해저드
  • 제어 해저드(control hazard) / 분기 해저드(branch hazard)

본 강의에서는 컴퓨터 구조에서 파이프라이닝 이 무엇이며 어떤 역할을 수행하는 지를 알아봅니다.

파이프라이닝이란

파이프라이닝 이란 마치 조립 라인처럼 어떤 명령어가 중첩되어 실행되는 구현기술입니다.
보통 파이프라이닝을 설명할 때에는 세탁소에서 세탁을 하는 절차를 비유하여 많이 이용하며 세탁소가 세탁을 하는 절차를 컴퓨터에 빗대어 설명을 해보도록 하겠습니다.
세탁소에서 세탁을 하기 위해서는 먼저 다음과 같은 순서로 세탁물을 처리합니다.

1. 세탁기에 한 아름의 더러운 옷을 넣는다.
2. 세탁기 작동이 끝나면 젖은 옷을 건조기에 넣는다.
3. 건조기 작동이 끝나면 건조된 옷을 탁자 위에 놓고 접는다.
4. 접는 일이 끝나면 같은 방 친구에게 옷을 장롱에 넣어달라고 부탁한다.

하지만, 위 순서대로 차례차례 일을 진행하는 것 만큼 바보같은 짓은 없을 것이다.
세탁기가 다 돌아가기를 기다렸다가 세탁이 다 되면 젖은 옷을 건조기에 넣고 건조기가 다 돌아가면 접어서 장롱에 넣는 일련의 전차들은 사실 각 단계 를 담당하는 별도의 자원(세탁기, 건조기, 나, 친구) 들이 있는 한은 모두 동시에 처리될 수 있다.

이 작업을 파이프라이닝을 한다면 다음과 같을 것이다.

1. 첫번째 빨래가 다 돌아가면 건조기에 빨래를 넣고 나는 다시 세탁기에 옷을 집어 넣는다.
2. 건조기와 세탁기가 다 돌아가면 나는 건조된 옷을 접고, 세탁이 된 빨래를 건조기에 넣고, 새로운 빨래를 세탁기에 넣는다.
3. 옷을 다 접었으면 친구에게 옷을 장롱에 넣어달라고 하고, 다시 빨래를 개고, 건조기에 세탁이 된 옷을 넣고, 새로운 빨래를 세탁기에 넣는다.

위처럼 동시에 처리 가능한 일들을 동시에 처리함으로써 처리량 을 올리는 것이 파이프라이닝의 핵심이다.

이 경우 중요한 점은 각 단계를 수행하는 속도가 빨라지지는 않느다는 점이다. 모든 단계는 원래의 동작속도대로 일을 해 나가지만 병렬적으로 처리를 함으로써 쉬는 시간을 없애어 전체 처리량 을 올려 많은 작업을 빠른 시간 내에 처리 할 수 있도록 하는 것이다.

위 과정에서 알 수 있듯이 할 일이 충분히 많다면 파이프라이닝에 의한 속도 향상은 파이프라인의 단계 수와 같다. 위의 예에서는 세탁, 건조, 빨래 개기, 장롱에 넣기 의 4 단계로 파이프라이닝이 진행되므로 4배 빠른 시간에 작업량을 처리 한 것이 되고 처리량은 4배 증가 한 것이 된다.

여기서 또 유의깊에 보아야 할 부분은 각 단계별 걸린 시간이다.
세탁, 건조, 개기, 넣기 4가지의 작업을 하는 각 단계별로 걸리는 시간은 물론 전부 다를 것이다. 하지만, 파이프라이닝을 한 경우에 우리는 제일 빠른 단계의 작업이 끝나도 전체 작업이 다 끝나는 것을 기다렸다가 다음 단계로 넘어갈 수 밖에 없다. 가령 건조가 빨리 다 끝나더라도 세탁기가 덜 돌아갔다면 세탁기가 다 돌아가기를 기다려야 하는 것이다. 컴퓨터 시스템에서 이러한 한 단계를 처리하는 시간을 컴퓨터의 클럭 사이클 이라고 하며, 파이프라이닝에서 클럭 사이클은 전체 단계 중 가장 시간이 오래걸리는 것을 기준으로 한다.

이처럼 이상적으로 파이프라인 프로세서에서 속도향상은 파이프 단계 수와 거의 같아야 하지만 위와 같은 문제 때문에 향상 률은 단계수보다는 조금 적으며, 파이이프라이닝 되지 않은 컴퓨터와 파이프라인 컴퓨터에서의 실제 프로그램의 전체 실행시간의 비율은 명렁어 사이의 시간 비율에 가깝다.

파이프라인 해저드

각 명령어가 다음 클럭 사이클에 실행되지 못하는 상황을 파이프라인 해저드라고 하며 3가지 종류의 해저드가 있다.

구조적 해저드

첫번째 해저드는 구조적 해저드 라 불리는데, 이는 가은 클럭 사이클에 실행하기를 원하는 명령어의 조합을 하드웨어가 지원할 수 없기 때문에 발생하는 해저드이다.
가령, 세탁소의 예를 들면 세탁기와 건조기가 붙어있다던지, 혹은 장롱에 개어진 세탁물을 넣어줄 친구가 없다던지 하는 경우이다. 이러한 해저드를 없애기 위해서는 설계자가 파이프라인을 설계하는 시점에서 구조적 해저드를 피하는 것이 비교적 용이하다.

데이터 해저드

두번째 해저드인 데이터 해저드 는 어떤 단계가 다른 단계가 끝나기를 기다려야 하기 때문에 파이프라인이 지연되는 경우 생기는 것으로, 컴퓨터 파이프라인에서는 앞선 명령어에 종속성을 가질 때데이터 해저드가 일어난다. 가령, add 명령어를 사용하여 %s0 레지스터에 값을 저장하고, 바로 다음 명령어에서 sub 명령어 혹은 기타 명령어를 통해 &s0에 저장된 값을 사용하는 경우 첫번째 명령어에서 미처 데이터가 레지스터에 저장되기도 전에 해당 레지스터를 참조하게 되어 연산이 이루어 질 수가 없게 된다.

이를 해결하기 위한 방법 중 하나는 바로 전방전달(forwarding) 혹은 우회전달(bypassing) 이다.
이것은 별도의 하드웨어를 추가 하여 정상적으로는 얻을 수 없는 값을 내부 자원으로부터 일찍 받아오는 것을 의미하는데, 레지스터나 메모리에 아직 나타나지 않은 데이터를 기다리지 않고 데이터패스를 추가로 하드웨어에 연결하여 내부 버퍼로 부터 가져오는 것이다.

앞의 add 연산 뒤에 바로 sub 연산을 처리하는 경우를 예로 들면, 하드웨어 자체에 앞에서 계산한 결과가 나오는 부분에서 다음 연산의 뺄셈의 입력 부분으로 새롭게 데이터 패스를 연결하여 데이터가 레지스터에 씌어지기 전에 비트값으로 값을 받아와 연산에 활용하여 데이터 해저드 를 해결 할 수 있다.

하지만, 위의 예인 add와 sub 연산의 연속적 사용이 아닌 데이터 적재 명령어를 사용하는 경우 문제는 더 커진다. 이 경우에는 메모리의 적재까지 4단계 정도의 오랜 시간이 소요되고 이것을 기다리는 것은 너무도 큰 성능 저하를 불러 일으키는데 이러한 적재 명령어 사용에 따른 데이터 해저드를 별도로 적재 사용 데이터 해저드 라고 부른다. 이것은 파이프라인 지연(pipeline stall) 의 대표적인 예이며 거품(bubble) 이라는 별명으로도 지칭된다.

제어 해저드(control hazard) / 분기 해저드(branch hazard)

세번째 해저드인 제어 해저드 는 분기 명령어 처럼 다른 명령어들이 실행 중에 한 명령어의 결과 값에 기반을 둔 결정 을 할 필요가 있을 때 일어납니다.
보다 쉽게 이해하기 위해 다시 세탁소의 예를 들어봅시다. 어떤 세탁소의 점원이 옷들을 세탁할 때 세탁 세제와 물의 온도를 선택함에 있어 옷들이 상하지는 않는 한도 내에서 강한 세제와 높은 온도를 통해 옷을 깨끗하게 세척을 해야 합니다. 하지만, 이 때 세탁소의 점원은 그 옷의 성질을 알지 못하므로 일단 한번 세탁을 한 뒤 말려보아야 올바른 세탁 세제와 물의 온도를 사용했는지를 알 수 있습니다. 이를 해결하기 위해서는 다음과 같은 세가지 해결법 이 있습니다.

지연

첫번째는 지연 으로, 첫번째 묶음의 옷들이 건조될 때까지 그냥 순차적으로 작업하되 올바른 비율이 결정될 때까지 계쏙 순차적 작업을 반복하는 것입니다. 위의 세탁소의 예를 들면 일단 옷을 세탁하고 말리는 작업까지를 했다면 그 결과값이 나올때까지 다음 세탁을 대기한 뒤 결과가 나오면 다시 파이프라이닝을 시켜 세탁을 시작합니다. 하지만, 이렇게 계속 반복적으로 분기 명령어 마다 지연을 시킨다면 훨씬 더 큰 속도 저하를 초래할 것입니다 때문에 다른 방법을 필요로 하게 되었고 만들어 진 것이 예측 기법입니다.

예측

예측을 수행하는 가장 간단한 방법은 분기가 항상 실패한다고 예측하는 것 입니다. 예측이 옳으면 파이프라인은 최고 속도로 진행되고, 실제로 분기가 일어날 때만 파이프라인이 지연이 됩니다. 좀 더 정교한 버전은 동적 하드웨어 예측기 를 이용하는 것으로 각 분기가 일어났지는 지록함으로써 최근의 과거 이력을 사용하여 미래를 예측하는 것입니다.

delayed branch

세번째 방법은 분기 지연 입니다. 이 방법은 분기가 필요한 명령어의 결과값이 나오는 동안 해당 분기와 관련이 없는 다양 명령어를 먼저 실행하여 시간이 지연되지 않도록 하는 방법이며, 이를 위해서는 명령어를 적합한 순서에 따라 배치해야하며 주로 컴파일 최적화 를 통해 이루어 질 수 있습니다.

• 시스템 모델
• 교착 상태의 특징
• 교착 상태 처리 방법
  • 교착 상태의 예방
    • 상호배제
    • 점유하며 대기
    • 비선점
    • 순환 대기
• 교착 상태 회피
  • 안전 상태
  • 자원 할당 그래프 알고리즘
  • 은행원 알고리즘(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 알고리즘이다.