• 입출력 시스템이란 무엇인가?
• 입출력 하드웨어
  • 입출력 하드웨어의 구성
  • 입출력 하드웨어의 동작
    • 폴링
    • 인터럽트
  • 직접 메모리 접근(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 에서 처리된다.

오늘은 노벨상, 퓰리처 상 수상자인 미국의 극작가 유진 오닐 이 남긴 “꿈”에 관한 이야기를 하고자 합니다.

꿈을 실현시키지 못하고 실패하는 것이
우리에게 주어진 어쩔수 없는 운명이지만
그래도 희망이 없는 곳에는 생명도 없다
그러므로 우리들은 마지막 순간까지
꿈을 계속 찾는 것이다.

우리들은 항상 꿈을 이루기 위해 노력하며 하루를 살아갑니다.
누군가는 꿈을 이루지만, 다른 누군가는 삶이 끝나는 그 날까지 꿈을 이루지 못하기도 합니다.

당신은 어떤 사람인가요?
혹시 지금, 꿈을 이루셨나요?

아마도 대부분의 사람들은 그렇지 않을겁니다.
만약 가지고 있던 꿈을 몇개 쯤 이루었을 수 있지만 수천 수만개의 새로움 꿈들을 우리는 매일 좇으며 평생을 살아갑니다.
이렇게 우리가 꿈을 말할때는 언제나 현재 진행형이지요.

극작가 유진 오닐은 이런 우리들의 모습을 정말 잘 표현해 줍니다.
바로, 꿈의 실현에 대해 꿈을 실현시키지 못하고 실패하는 것이 우리에게 주어진 운명이라고요.

꿈을 실현시키지 못하고 실패하는 것이 운명이라니, 어차피 이루지도 못할 꿈을 더 이상 좇을 의미가 있는 것일까요?

많은 사람들이 이런 생각을 합니다.

“내가 가진 꿈을 이루기는 너무 힘들어요.”
“꿈은 어렸을 때나 가지는 거죠”
“저는 현실적인 사람이에요.”

그리고 더 이상 꿈을 꾸는 의미가 없다고 말을 합니다.

이룰수 없는 꿈을 꾸는 것은 정말 헛된 일일까요?

그래도 희망이 없는 곳에는 생명도 없다
그러므로 우리들은 마지막 순간까지
꿈을 계속 찾는 것이다.

유진 오닐의 한마디는 우리에게 깊은 인상을 줍니다.
꿈은 이루기 위해 꾸는 것이지만, 꿈을 좇는 것은 그 결과가 아닌 과정에 참된 의미가 있다고 우리에게 말해주는 것이지요.

우리는 살아있기 때문에 또, 앞으로 살아갈 용기를 얻기 위해 꿈을 꿉니다.
설사 꿈을 이루는 것을 결국 실패했다고 하더라도 낙담하거나 좌절할 필요는 없는 것이지요. 매일 매일 꿈을 좇는 과정 그 자체 만으로 우리는 살아있음을 느끼고 또 앞으로 살아갈 용기를 얻을 수 있습니다.

이 글을 읽는 많은 독자분들도 오늘 하루 자신이 가진 원대한 꿈을 의심하고 걱정하지 말고 있는 그 자체로 추구하며 살아있음을 느낄 수 있는 하루가 되셨으면 합니다.

감사합니다.

• 왜 메모리 계층구조가 필요한가?
• 메모리의 종류에는 어떤 것들이 있나요?

왜 메모리 계층구조가 필요한가?

컴퓨터 내에서 프로그램이 동작하기 위해서는 프로그램이 메모리 위에 적재되어야 하고, 이상적으로 모든 프로그램이 메모리 위해 적재 될 수 있는것을 많은 프로그래머들은 바래왔습니다.
즉, 무제한의 크기를 가지는 빠른 메모리는 모든 프로그래머들을 꿈 이라고 볼 수 있습니다. 하지만, 메인 메모리는 메우 비싸기 때문에 이러한 무제한의 크기를 가지는 메인 메모리는 사실상 구현 불가능 하기에 메모리 계층 구조를 통해 한정된 메모리를 가지고 최대한 큰 크기의 메모리를 사용하는 것 처럼 컴퓨터가 행동하도록 노력했고, 그 결과 메모리 계층 구조가 도입되게 되었습니다.

메모리 계층 구조를 이해할 때에 흔히 도서관에서 공부를 하는 상황에 대입하여 생각해 볼 수 있습니다. 도서관에는 수많은 책들이 꽂혀 있고 언제든지 가져와서 책을 볼 수 있지만, 한번 책을 가져올 때 마다 상당히 귀찮고 오랜 시간이 소요되게 됩니다. 컴퓨터의 경우도 마찬가지 입니다. 여기서 도서관에 해당하는 것이 컴퓨터의 자기 디스크 입니다. 자기 디스크는 아주 크기가 크고 막대한 양의 자료가 들어갈 수 있지만 한번 접근하려면 오랜 시간이 걸리게 됩니다.

이 문제를 어떻게 해결해야 할까요?
보통 도서관에서 공부를 할 때 우리는 필요한 책들을 쭉 뽑아서 책상위에 쌓아두고 공부를 시작합니다. 이렇게 하면 우리가 필요한 대부분의 정보들은 책상 위에서 빠르게 얻을 수 있고, 사실 도서관 전체에는 나와 관련이 없는 많은 자료들이 있는 것에 반해 책상 위에 뽑아 놓은 책에는 내게 필요한 정보들이 존재하게 됩니다. 이렇게 필요한 책을 뽑아 우리가 필요할 만한 정보들을 주변에 배치해 놓는 것처럼 컴퓨터 에서도 우리가 자주 사용할 만한 정보들을 가까운 곳에 복사해 놓게 되고 이것을 우리는 캐시 라고 합니다.

캐시에 들어갈 정보들은 어떤 식으로 선별이 될까요?
이는 마치 도서관에서 책을 뽑아오는 것과 같은 논리이며 지역성의 원칙 에 따라 선별됩니다. 도서관에는 필요한 책들이 종류별로 분류되어 있고, 아마 내게 필요한 정보는 주변에 붙어 있을 확률이 높습니다. 내가 A라는 책을 가져오면서 혹시 몰라서 A 책 주변의 다양한 책들을 가져오는 것이 이러한 지역성의 원칙 을 따른 캐싱이라고 볼 수 있습니다. 또는, 내가 예전에 한번 봤던 책들에 내가 필요한 정보가 담겨있을 확률도 높습니다.
위처럼 내가 필요한 정보 주변의 책에 필요한 정보가 있을 확률이 높은 것을 공간적 지역성 이라 하고, 또 예전에 내가 사용했던 책에 필요한 정보가 있을 확률이 높은 것을 시간적 지역성 이라고 합니다. 이러한 두가지 지역성을 원칙에 따라 우리는 책을 가져오고 컴퓨터 에서는 캐싱 을 통해 이러한 작업을 수행합니다.

도서관에서 책 무더기를 가져오듯이 한번에 가져오는 정보의 최소 단위를 블록 이라고 합니다. 컴퓨터가 어떤 정보가 필요하다면 그 정보가 담긴 블록을 통으로 가져와서 작업을 수행하게 됩니다. 만약 필요한 정보가 이렇게 한번 가져온 블럭 중에 있는 경우를 적중(hit) 했다고 하고, 그 확률을 적중률 이라고 하며, 그 시간을 적중 시간 이라고 합니다.

만약 가져온 블록 중에 필요한 정보가 없는 경우는 어떨까요?
이 경우를 컴퓨터에서는 실패 라고 하며, 그 확률을 실패율 이라고 합니다. 이렇게 실패에 따른 손실은 실패 손실 이라고 하며 이는 하위 계층에서 블록을 가져와서 상위 계층 블록과 교체하는 시간에 그 블록을 프로세서에 보내는 데 걸리는 시간을 더한 값입니다.

이처럼 컴퓨터는 사용할 확률이 높은 정보들을 CPU에 가까지 적재하고 다른 정보들을 메모리 계층의 아래쪽에 위치시킴으로써 보다 빠르게 정보를 탐색할 수 있도록 하며, 때문에 메모리는 계층 구조 로 이루어져 있습니다.

메모리의 종류에는 어떤 것들이 있나요?

메모리 계층 구조에서 프로세서와 가장 가까운 캐시 는 SRAM이 사용되며, 메인 메모리 에는 DRAM 이 사용됩니다. SRAM은 어떤 데이터든지 접근 시간이 같고 리프레시가 필요없어 DRAM에 비해 아주 빠릅니다. DRAM 은 SRAM에 비해 아주 느립니다.

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

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

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

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

시스템의 관점에서 운영체제는 하드웨어와 가장 밀접한 프로그램이라고 볼 수 있다. 컴퓨터 시스템은 특정 문제를 해결하기 위해 필요한 여러가지 자원들을 사용하는데(가령 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. 메모리 공간을 할당하고 회수

저장 장치 관리

보호와 보안

분산 시스템

진정한 아름다움이란 무엇인가?

요즘 시대에 ‘아름다움’이란 너무도 상업적인 목적 또 하나의 유희이자 쾌락으로써 소비되고 있습니다.
하지만, 예로부터 ‘아름다움’ 이란 많은 철학자들이 하나의 ‘이상’ 으로 추구해 왔던 개념이었고 인간이 추구해야 할 숭고한 가치로 고려되어 왔습니다.
오늘 글에서는 ‘아름다움’이란 의미가 점차 가벼워 지고 퇴색되어 가는 요즘 시대에 진정한 ‘아름다움’ 이란 무엇이며 올바른 아름다움의 추구란 무엇인가에 대해 생각해 보도록 하겠습니다.

‘아름다움’이란 무엇일까요?
고대의 피타고라스 학파는 아름다움이란 비례와 조화, 균형이며, 수적으로 표현이 가능한 대상으로 보았습니다. 완벽한 굴곡을 자랑하는 도자기 혹은 이상적인 신체 비율의 가진 사람의 신체처럼 사물 혹은 사람이 가지는 그 고유의 비례와 조화의 미 그 자체를 ‘아름다움’이라 이야기 했습니다. 요즘 말하는 ‘8등신 황금비율’과 같은 말들도 어느정도는 고대 시대의 아름다움의 척도에 부합한다고 볼 수 있습니다. 이처럼 옛날 사람들은 오늘날 우리가 생각하는 것 보다는 훨씬 객관적인 하나의 성질로써 ‘아름다움’을 보았습니다. 중세에 들어서도 사물 혹은 사람의 성질 로서의 ‘아름다움’의 개념은 연장되어 왔습니다. 참된 아름다움 이란 감각기관이나 상상에 의한 것이 아니라 이성에 의해 파악되는 정신적인 것으로 규정하고, ‘아름다움’ 이란 철저히 객관적인 성질로써 이해되었습니다.

하지만, 근대에 들어서면서 이러한 ‘객관적인 성질’로서의 아름다움에 대한 인식에 큰 변화가 생기게 됩니다. ‘아름다움’ 이란 대상의 성질일 수 있지만, 이것은 대상을 인식하는 우리의 주관이 느끼는 것이라는 생각이 널리 퍼지게 되었습니다. 고대의 미가 단순히 균형, 조화를 추구했다면, 근대의 아름다움 에서는 이를 특정짓는 것이 없이 오로지 우리가 주관적으로 느끼는 것 이라는 것이지요. 가령 아무리 완벽한 자태를 뽐내는 도자기가 있더라도 우리가 이 도자기를 보고 감동을 느끼고 아름답다고 느끼지 않는다면 그 도자기는 더 이상 우리에게 아름다운 것이 아닙니다. 수천년이 지나 칠이 벗겨지고 부수어진 도자기가 우리에게 옛 선조들의 아름다움을 알 수 있게 해주고 우리 마음 속에 아름답다는 감정을 불러 일으킨다면 그 도자기는 그 외관에 상관없이 우리에게 아름다울 수 있는 것이지요.

철학자 칸트는 이러한 근대의 아름다움에 대한 개념을 다음과 같이 얘기합니다.

“미란 결코 객관적인 것이 아니며, 인식적 의미를 지니지 않는다. 우리의 마음 속에 미적 즐거움을 일으키는 대상들의 형식은 객관적이나, 그것은 개념적으로 파악될 수 없다. 그것이 객관적 성질을 지니는 것이 아니라 우리의 마음 속에 미적 즐거움을 환기시킬 수 있도록 구성된 것을 뿐이다. 하지만 미를 일으키는 과정에서 일련의 공통점을 가진다.”

이러한 근대의 아름다움의 개념의 현재 우리 삶의 많은 부분에 녹아 있습니다. 오랜 기간 훈련을 통해 짓 무르고 갈라진 ‘김연아’ 선수의 발을 보면서 많은 사람들이 아름다움을 느끼는 것도 이러한 주관적 의미에서의 아름다움이라고 볼 수 있습니다.

아름다움이란 가질 수 있는 것일까?

현대의 많은 사람들은 ‘아름다움’을 가지기 위해 많은 활동을 합니다. 외적인 아름다움을 가꾸기 위해 성형수술을 하기도 하고 헬스장을 다니고 운동을 하며 다이어트를 하기도 하면서 ‘아름다움’을 소유하기 위해 많은 노력을 기울입니다.

하지만, 이런 많은 활동이 궁극적으로 우리 모두에게 ‘아름다움’을 가지게 해 줄까요?
근대 이후의 많은 철학자들이 말하는 결론은 ‘아니오’입니다.

왜 우리는 아무리 노력해도 아름다움을 소유할 수 없을까요?
위에서 말했듯이 ‘아름다움’이란 객관적인 성질이 아닌 우리 마음 속에 미적 즐거움을 환기시킬 수 있어야 합니다. 즉, 진정한 아름다움이란 모든 사람들이 많은 다양한 의미로 나에게 아름다운 감정을 느껴야 이루어 지는 것이지요. 그것이 외적인 아름다움이던 혹은 내적인 아름다움일 수 있고, 몇몇 사람들이 나의 외적 혹은 내적 아름다움에 공감할 수 있을 지 모르지만 궁극적인 ‘아름다움’을 소유하는 것에는 한계가 있을 수 밖에 없습니다.

아름다움은 소유하는 것이 아니라 추구하는 것

그렇다면 우리는 아름다워 질 수 없는 것일까요? 아름다움을 소유하지 못한다면 우리에게 무슨 낙이 있을까요?

위의 질문에 현대의 많은 철학자들은 이렇게 말합니다.
“아름다움을 얻을 수 있는 최고의 지름길은 미를 소유하는 것이 아닌 추구하는 것에 목적을 두는 것이다.”

아름 다움 자체를 소유하기 위해 노력한다면 돌아오는 것은 실패 뿐을 것입니다. 모든 형태의 아름다움 모든 사람들이 공감할 수 있는 궁극적 아름다움을 가지는 것은 사실상 불가능 하기 때문이지요. 이런 노력은 모두 실패로 귀결될 수 밖에 없습니다.

아름다움이 주는 즐거움을 누릴 수 있는 최고의 방법은 ‘아름다움을 추구’하는 것입니다.
오늘 보다 나은 나를 만들기 위해 노력하고, 누군가를 가슴속 깊이 사랑하고, 나의 주권 또 내 주변 사람들의 자유와 주권에 대한 관심, 즉 나와 이 세계를 아름답게 하고자 하는 노력과 그런 아름다움에 대한 추구를 통해 아름다움이 주는 진정한 즐거움을 알 수 있을 것이라 믿습니다.

이 글을 읽는 독자님도 오늘 하루 ‘아름다움’을 가지지 못한 나를 채찍질 하기 보다 하루 하루 나와 내 주변 사람들의 아름다움을 추구하는 멋진 인생을 살아가 아름다움이 주는 진정한 즐거움을 향유할 수 있기를 기원합니다.

Blockchain technology for enterprise service

건강 보험 등 이력에 대한 불변의 상태기록을 원하는 비즈니스에서는 상당히 유용하게 사용될 수 있다.

인센티브의 경우 네트워크 망을 유지하고 서비스에서 인센티브를 제공하는 기능을 어떻게 활용 가능한가?

Case1 분산 원장으로써의 블록체인

롯데카드 -> 블록체인 기반 생체 인증

삼성페이에서 로그인 정보를 다른 쪽에도 유지하기 위해 사용 =>

Case2 스마트 컨트랙트로써의 블록체인

현대카드 포인트 페이먼트를 스마트 컨트랙트로 구성

제일 큰 문제는 성능문제. => 추가로 컨센서스를 만드는 작업 등

신한금융 => 인증서 발급 로직을 스마트 컨트랙트로 구성

금융보안원, 금융 결제원 => 폰뱅킹 및 은행 송금 시스템

은행 송금 시스템을 블록체인화, 기존에는 중앙 시스템이 모든 은행의 거래 내역을 다 처리하고 매일 한번씩 정산하여 데이터베이스를 맞추는 식으로 햇었음

이 경우 스마트 컨트랙을 통해 했는데 역시 성능문제가 생겼음

여기서 가장 중요한 점은 고객 데이터는 데이터베이스에 올라갈 수 없음

때문에 블록체인과 외부 디비가 어떤 식으로 연동하는 것이 매우 중요한 포인트임

고객의 주요 쟁점

1. 퍼포먼스 컨트랙트 내부 병렬화에 대한 요구가 나온다. 보통 컨트랙트 내에서 락을 걸어서 처리를 하는데 이 경우 처리가 빠르게 일어나지 못함
2. privacy개인정보를 올리려면 어떻게? => 난스 만들어라
3. Multi chain
4. 익명 기술
5. 파이널리티 가령 블록이 생성되어 트랜잭션이 만들어 지더라도 블럭이 폐기되면 다시 뒤로 돌아가기 때문에 고객의 지갑이 변동되는 문제가 생기며 이는 매우 큰 이슈이다,

블록체인 비즈니스 활용 Tip

사이드 체인을 유지하고 퍼블릭 네트워크와 연동하는 형태로 많이 서비스를 하게 된다.

이렇게 하면 기존 서비스의 품질을 해치지 않으면서도 블록체인을 적용할 수 있다.

가령 포인트를 적립시킨다고 하면 별도 사이드 체인을 만들어서 포인트를 등록하고 해당 체인을 다른 퍼블릭체인과 연동하여 포인트를 유통시킬 수 있다.

즉 이더 송금 수수료를 한번만 이용하지만 여러 거래를 별도 사이드체인에서 동작시키고 퍼블릭체인과 연동함으로써 해결이 가능하다.

Ex) aergo => 블록체인 sass 서비스

업그레이드 가능한 스마트 컨트랙트

투명성, 위변조 불가성

왜 업그레이드 가능한 스마트 컨트랙트가 필요한가?

1. 배포 후 취약점이 발견되면 수정이 가능하다.
2. 비즈니스 로직이 수정 불가하기 때문에 겪게 되는 불편함이 있다.

Delegate call 특정 컨트랙트를 통해 다른 컨트랙트를 실행시킴

조건

업그레이드로 스마트 컨트랙트 주소 안변함데이터 마이그레이션 없이 데이터보존여러 스마트 컨트랙을 한번에 배포

Proxy contract 를 만들어 버전관리를 하고 유저는 proxy contract 로 전달하고 proxy contract는 최신버전의 contract로 명령을 전달한다.

Registry contract upgrade Earl => 업그레이드하고자 하는 proxy contract의 주소를 받아온다. registry contract 모두를 업그레이드 하기 위해 registry contract를 실행시킨다.

스마트 컨트랙트 버전관리 툴

1. deploy
2. Registry contract 가 없으면 registry contract 배포

업그레이 가능한 스마트 컨트랙트의 이점

유저 입장에서는 스마트 컨트랙트 주소가 고정됨, 버전 정볼르 생각하지 않고 특정 호출만 계속 함개발자 입장에서는 모든 데이터가 그대로 유지되고 재사용 되게 됨업그레이드가 매우 편리함.

Token Model Design Process

토큰 모델이랑 탈중앙화 네트워크의 보이지 않는 손이다.

토큰이라는 인센티브를 가지고 경제가 어떻게 굴러가는지를 설계한다.

게임 이론

주어진 게임의 규칙에서 최선의 전략을 찾는 이론

메커니즘 디자인

모든 플레이어가 게임에 충실하게 참여를 했을 때 이를 원하는 방향으로 굴러가게 하기 위한 메커니즘에 대한 디자인

어떻게 기존의 경제 시장에서 토큰 모델을 적용시킬 것인가?

메커니즘 디자인의 기초

Agent 행동 주체

Type agent의 사적인 정보

Decision 가능한 사회적 결과의 집합

Utility function 에이전트가 특정 결과에 대해 얻는 효용

Decision function agent의 각 행동을 종합한 결정 규칙

Transfer function agent의 행동에 따라서 받거나 내야하는 돈

Social choice function

가령 마을에 쓰레기 처리장을 짓는 문제를 생각해 보자.

제일 쉬운 방법은 누군가가 모든 사람들에게 의견을 물어보는 것이다.

여기서 transfer function 은 agent의 type 에따라서 받거나 내야하는 돈의 규칙이다.

메커니즘의 특성

Efficiency

최대 다수의 최대 행복

trustfulness

모든 에이전트의 균형 전략이 자신의 type을 솔직하게 보고하는 것일때

Budget balanced

agent의 type이 바뀌더라도 메커니즘이 transfer function으로 얻는 수입이 일정할 때

메커니즘을 최적화 문제로 정의할 수 있다!!

메커니즘 최적화 적용

가령 서울의 평균 기온을 블록체인에 기록하는 메커니즘을 만든다고 해보자

1. 오라클 선출 => 신뢰할 수 있는 외부 데이터를 선정한다.
2. Shelling coin 많은 사람들이 준 값들의 중간값을 실제값으로 정한다.

계속해서 decision function 과 transfer function 을 바꾸어 보면서 실 데이터를 분석하여 효율적인 메커니즘을 도출해 내야 한다.

토큰 모델 디자인 프로세스

agents와 목표 행동 정의최적화 문제 설정반복메커니즘 규칙 설정규칙 변경결과 추론제약조건 변경

예시 - steemit

Object => 좋은 글의 공급을 극대화

Constraint => 초보 작가들이 글을 쓰기가 쉬워야 함, 독자들은 글을 쓸 때 돈을 내지 않아야 함 등

Decision => 추천수에 스팀 파워 가중치를 계산해 퀄리티로 인정함

Transfer =>

더 나은 설계를 위해 필요한 것들

좋은 규칙의 집합, 패턴실제 돌아가는 프로젝트에서 나오는 실증 데이터복잡한 메커니즘의 정량적 추론을 위한 시뮬레이션 툴

토큰 디자인 패턴

Incentive, curation , judgement, governance

메커니즘 디자인의 한계

닫힌 시스템을 가정한 설계이기 때문에 경쟁 프로토콜, 암호화폐 시장 등 외부 요소는 고려하지 못하기에

블록체인과 같은 완벽하게 공개된 플랫폼 내에서 어떤 사이드 이펙트가 나올지 알 수 없다.

토큰 디자이너를 위한 팁

1. 플레이어가 아니라 디자이너처럼 생각하라.
2. 목적과 제약조건 정의만 잘해도 반은 먹고 들어간다. => 토큰 가치 상승이 목적인가 이중 지불 방지가 목적인가, 목적과 제약조건만 확실하다면 솔루션은 얼마든지 바꿀 수 있음
3. 솔루션을 decision function 과 transfer function 으로 바꾼다.
4. 알고 있는 패턴이 풍부해야 문제를 잘 풀어나갈 수 있다.

화폐가치와 메커니즘 디자인은 어떻게 결합될 것인가

IOT에서의 블록체인

오프라인 데이터의 위변조를 막기 위해 가량 씨씨티비의 경우 해당 영상의 해시값을 저장하여 블록체인에 저장하고 추후 검증이 필요한 경우 해당 해시와 비교를 통해 할 수 있따.

Digital forensic => 영상 데이터의 법정에서 신뢰를 얻을 수 있음

가령 자율주행차의 경우 수동으로 운전을 했는가 혹은 자동으로 운동을 했는가가 과실에 매우 중요하다. 이를 블록체인에 실시간으로 저장하면 이를 막을 수 있다.

DAICO 모델 - 블록체인 위에서 ico 플랫폼

메커니즘

하스켈

Flux 란?

flux 는 하나의 개발 철학이며 기존의 MVC 모델이나 양방향 데이터 바인딩에 대한 대안으로 제안된 개념이다.

flux에는 다음과 같은 3가지 개념이 있다.

1. action
2. dispatcher
3. stores

action은 시스템 전체의 상태변화를 묘사하는 다양한 형태의 행위이다. 가령 마우스 클릭이나 axios 요청 등의 행위들이 여기에 포함될 수 있다.

이러한 일련의 action들의 모음으로 시스템이 흘러가며 이를 통해 일관된 행동 양상을 유지하고 시스템의 다음 행보를 예측이 가능하게 된다.

일반적인 flux의 플로우는 다음과 같다.

1. store는 action의 변화를 인지하도록 준비한다.
2. action이 dispatcher를 통해 dispatch 된다.
3. dispatcher는 store의 subscriber에게 변화를 알린다.
4. store는 해당하는 action에 따라 상태를 업데이트한다.
5. 어플리케이션의 view는 해당 상태의 변화에 따라 업데이트 된다.
6. 다음 액션이 실행될 수 있다.

이렇게 시스템 전체가 일련의 action의 나열로 이루어짐에 따라 개발자들은 다음 시스템의 상태를 예상가능하게 되고 개발자의 통제 내에서 모든 시스템 변화가 이루어 질 수 있게 된다. 여기서 중요한 점은 모든 action이 순차적으로 이루어진다는 것이다.

이는 기존의 양방향 데이터바인딩 시스템과 매우 대조적인데 양방향 시스템에서는 모든 데이터가 실시간으로 변화하고 있기에 일관된 데이터의 변화 방향을 인지할 수 없지만 시스템의 순간순간의 상태는 각 액션 사이의 상태값의 변화이기에 모든 순간의 상태값에 대해 인지할 수 있다.

Redux

리덕스란 이러한 flux 패턴의 하나의 구현체이며 단 하나의 스토어를 가진다는 점에서 플럭스와 차이가 있다.

가령 요리책을 다루는 app의 경우 redux 스토어는 모든 요리방법들의 리스트와 상세 내역을 가지게 된다.

여기서 액션이란 요리방법을 추가하고 특정 레시피에 재료를 추가하는 행위라 할 수 있겠다.

실제 비즈니스 로직에서는 이런 다양한 액션들을 묶어서 사용자가 사용하는 수준으로 만들어줄 필요가 생기고 그것이

action

액션은 애플리케이션에서 스토어로 보내는 데이터 묶음이며, 스토어의 유일한 정보원이다.

store.dispatch()

액션의 종류

{

type: COMPLETE_TODO,

index: 5

}

리듀서

이전 상태와 액션을 받아 다음 상태를 반환하는 순수 함수이다.

(prevState, action)

스토어

액션과 리듀서를 함께 가져오는 객체이다.

createStore(_action) => store

store.dispatch(_action)

프로세스

1. Create actionDescribe what happens
2. store.dispatch(action)
3. Redux store executes reducer function
4. Root reducer makes one state tree by merging reducer outputs
5. Store.subscribe(listener) => call all listener

개요

컴퓨터 안에는 수십 수만가지의 데이터 들이 있으며, 이러한 수많은 데이터들을 잘 정리하고 보관하는 것은 빠른 데이터 찾기와 데이터 추가 및 삭제 등의 작업의 효율에 매우 큰 영향을 미친다. 때문에 컴퓨터의 많은 자료들을 효율적으로 분류하고 원하는 자료를 찾고 추가 하기 위해서는 ‘정렬’에 대해 알아야 할 필요가 있다.

본 강의에서 리스트 란 하나 이상의 필드로 된 레코드의 집합이라는 의미로 사용하며, 이때 코드를 서로 구별하기 위해 사용되는 필드를 키 라고 한다.

일반적인 자료의 탐색 방법

흔히 리스트를 탐색하는 가장 직관적인 방법은 앞에서 부터 차례대로 비교하면서 자료를 분류하는 것이다.
프로그래밍에서 for 문을 사용하여 리스트의 제일 앞에서 부터 뒤까지 훑어 가면서 equal 문을 통해 데이터를 찾는 작업은 매우 흔한 프로그래밍의 구현이다.

이렇게 어떤 리스트의 왼편에서 오른편으로 차례대로 데이터를 찾는 것을 순차 탐색 이라고 한다.

다음 C 언어로 순차탐색 프로그램을 구현한 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
using namespace std;

struct Element
{
  public:
    string key;
};

int seqSearch(Element elements[], string key)
{
    int i;
    int count = sizeof(*elements) / sizeof(elements[0]);
    cout << "address of the elements: " << elements << endl;
    cout << "count is: " << count << endl;
    for (i = 0; i < count; i++)
    {
        if (elements[i].key == key)
        {
            return i;
        };
    };
    return 0;
};

int main(void)
{
    Element element1 = {"123"};
    Element element2 = {"namhoon"};
    Element elements[] = {element1, element2};
    int result = seqSearch(elements, "namhoon");
    cout << result;
}

위 프로그램을 살펴보면 for 문을 돌면서 n 개의 레코드를 탐색하는 평균은 (n+1)/2 이므로, O(n)의 시간복잡도를 가진다.

만약 어떤 리스트가 정렬된 순차 리스트라면 이런 순차 탐색 말고 이원 탐색 을 사용하여 자료를 찾을 수 있으며 이 경우 시간 복잡도는 O(logn) 이다.

정렬의 종류

삽입 정렬

i 개의 정렬된 레코드에 새로운 레코드를 끼워넣어 i+1 개의 정렬된 레코드 리스트를 만드는 정렬 방법이다.

아래 프로그램은 C로 구현한 insert 함수이다.

정렬된 리스트 a[1:i] 에 e 원소를 집어넣어 a[1:i+1]의 리스트를 만들어 내는 함수이다.

index 역할을 하는 i가 점차 작아지면서 a[i].key가 e.key 보다 큰 경우 한칸씩 우측으로 밀어내고, a[i].key가 e.key 보다 작아지는 i 값에서 a[i+1]에 e를 넣어준다.

1
2
3
4
5
6
7
8
9

void insert(element e, element a[], int i){
  a[0]=e;
  while(e.key<a[i].key){
    a[i+1] = a[i];
    i--;
  }

  a[i+1] = e;
}

아래 함수는 insert 함수를 활용하여 삽입정렬을 하는 프로그램이다.

1
2
3
4
5
6
7

void insertionSort(element a[], int n){
  int j;
  for(j=2;j<=n;j++){
    element temp = a[j];
    insert(temp, a, j-1);
  }
}

병합정렬(Merge Sort)

병합정렬은 입력 리스트를 길이가 1인 n 개의 정렬될 서브트리로 간주하는 것으로 시작합니다.

아래 merge 함수는 두개의 서로 다른 리스트를 병합하는 것을 보여줍니다.

merge sort 의 각 단계는 O(n) 의 시간이 걸리고 logn 번의 단계가 적용되므로 O(nlogn) 의 복잡도를 가집니다.

Time Complexity: O(nlogn)

또한 각 병합과정에서 새로운 배열이 필요하므로 inplace sort가 아니다.

퀵 정렬(Quick Sort)

퀵 정렬은 앞서 살펴본 정렬법 중에서 가장 좋은 평균 성능을 가지고 있다.
퀵 정렬의 순서는 먼저 피벗 레코드를 선택하여 피벗의 왼쪽에는 레코드 키들이 피벗의 키보다 작거나 같고 피벗의 오른쪽에는 레코드 키들이 피벗의 키보다 크거나 같도록 하는 방법을 사용한다. 최종적으로는 피벗의 왼쪽에 있는 레코드들과 피벗의 오른쪽에 있는 레코드들이 서로 독립적으로 정렬이 된다.

다음은 퀵 정렬을 수행하는 프로그램이다.
i와 j가 각각 왼쪽과 오른쪽에서 가운데 방향으로 진행하며, a[i].key는 pivot 보다 커질 때까지 a[j].key는 pivot 보다 작아질 때 까지

1
2
3
4
5
6
7
8

void quickSort(element a[], int left, int right){
  int pivot,i,j;
  pivot = a[left].key;
  do{
    do j++;while(a[i].key<pivot);
    do j--;while(a[j].key>pivot);
  }
}

히프정렬

히프 정렬에서는 최대 길이 [log_2(n+1)] 을 가지고 adjust를 n-1번 호출한다.

즉, O(nlogn) 이다.

버블 정렬

선택 정렬

히프(heap)란?

히프는 우선순위 큐를 구현하는 데 자주 사용된다. 우선순위 큐에서는 우선순위가 가장 높은(또는 낮은) 원소를 먼저 삭제한다.
히프에 대한 설명을 하기 전에 최대 트리와 최소 트리에 대한 설명을 먼저 진행한다.

최대 트리 란 각 노드의 키 값이 그 자식의 키 값보다 작지 않은 트리이며,
최소 트리 란 각 노드의 키 값이 그 자식의 키 값보다 크지 않은 트리를 말한다.

여기서 최대 히프 란 최대 트리이면서 완전 이진트리이며, 최소 히프 란 최소 트리이면서 완전 이진트리를 의미한다.

이러한 최대 히프 및 최소 히프에서는 부모를 쉽게 찾아 삽입이 가능하다.

히프의 생성은 C를 통하여 다음과 같이 구현한다.

1
2
3
4
5
6
7
8
9

#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)
typedef struct{
  int key;
  } element;

element heap[MAX_ELEMENTS];
int n=0;

최대 히프에서의 삽입

최대 히프에서 원소를 삽입하는 경우 추가되는 원소가 가장 아래부터 루트 쪽으로 올라가는 bubbling up 기법이 사용된다.
다음은 최대 히프에서의 원소의 삽입을 구현한 C 프로그램이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENTS 200 /*최대 히프 크기 +1*/
#define HEAP_FULL(n) (n == MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)

typedef struct element{
  int key;
}element;

element heap[MAX_ELEMENTS];
int n=0;

void push(element item, int *n)
{
  int i;
  if(HEAP_FULL(*n)){
    fprintf(stderr, "The heap is full. \n");
    exit(EXIT_FAILURE);
  }
  i = ++(*n);
  while ((i != 1) && (item.key > heap[i/2].key)){
    heap[i] = heap[i/2];
    i /= 2;
  }
  heap[i] = item;
}
int main()
{
    struct element node1 = {7};
    struct element node2 = {16};
    struct element node3 = {49};
    struct element node4 = {82};
    struct element node5 = {5};
    struct element node6 = {31};
    struct element node7 = {6};
    struct element node8 = {2};
    struct element node9 = {44};
    push(node1, &n);
    push(node2, &n);
    push(node3, &n);
    push(node4, &n);
    push(node5, &n);
    push(node6, &n);
    push(node7, &n);
    push(node8, &n);
    push(node9, &n);
    for(int k=1;k<10;k++){
        printf("%d ",heap[k].key);
    }
    return 0;
}

최대 히프에서의 삭제

최대 히프에서 원소의 삭제는 제일 위에서 이루어 진다.
먼저, 키값이 가장 큰 원소를 삭제하고 마지막 원소를 제거하고 두 자식 노드중 큰 값이 위로 올라가고 아래를 메꾸는 방식으로 진행된다.
최대 히프의 삭제를 구현한 프로그램은 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

element pop(int *n)
{
  int parent, child;
  element item, temp;
  if(HEAP_EMPTY(*n)){
    fprintf(stderr, "The heap is empty\n");
    exit(EXIT_FAILURE);
  }

  item=heap[1];
  temp = heap[(*n)--];
  parent = 1;
  child = 2;
  while(child <= *n){
    if((child < *n) && (heap[child].key < heap[child+1].key))
      child++;
    if(temp.key > heap[child].key) break;
    heap[parent] = heap[child];
    parent = child;
    child *= 2;
  }
  heap[parent] = temp;
  return item;
}

B - 히프

B - 히프란 최소 트리의 집합이다.