언제나 휴일

3.5 큐를 이용한 스케쥴러 시뮬레이션 이번에는 큐를 이용하는 스케쥴러를 시뮬레이션 형태로 만들어 보아요. 여기서 작성할 시뮬레이션은 CPU가 하나 있는 컴퓨터 시스템에서 라운드 로빈 방식의 스케쥴러의 동작을 표현합시다. 스케쥴러는 컴퓨터 내에 여러 개의 프로세스(동작 중인 프로그램)중에서 누가 CPU를 사용할 것인지를 결정하는 운영체제의 핵심 모듈이죠. (참고로 Windows 운영 체제는 스케쥴링 대상이 쓰레드입니다.) 그 중에 라운드 로빈 방식의 스케쥴러는 시스템 내에 정해진 시간(타임 퀀텀)동안 CPU를 사용한 후 다시 대기 큐에 가서 대기하고 맨 앞에 대기하는 프로세스가 CPU를 점유하여 사용하게 운용해요. 여기에서는 프로세스의 상태를 Idel(휴먼 상태), Ready(준비 상태), Run(동작 ..

3.4 큐(Queue) 이번에는 큐를 알아보기로 해요. 큐는 자료를 한쪽으로 보관하고 다른쪽에서 꺼내는 FIFO(First In First Out) 방식의 자료구조입니다. 큐에 자료를 보관하는 연산을 PUT 혹은 ENQUEUE라 말하고 꺼내는 연산을 GET 혹은 DEQUEUE라고 말합니다. 그리고 보관할 위치 정보를 REAR, 꺼낼 위치 정보를 FRONT라고 말해요. 먼저 간단하게 보관하는 큐를 만들어 보기로 해요. class Queue { 여기에서는 자료를 저장할 버퍼를 생성할 때 정하기로 할게요. 버퍼의 위치를 기억할 멤버를 선언하세요. int *buffer; 버퍼의 크기를 기억할 멤버도 필요하겠죠. const int size; 자료를 꺼낼 위치 정보도 기억해야 합니다. int front; 자료를 보..

3.3 스택(Stack) 이번에는 스택을 알아보기로 해요. 스택은 자료를 한쪽으로 보관하고 꺼내는 LIFO(Last In First Out) 방식의 자료구조입니다. 스택에 자료를 보관하는 연산을 PUSH라 말하고 꺼내는 연산을 POP이라고 말합니다. 그리고 가장 최근에 보관한 위치 정보를 TOP 혹은 스택 포인터라 말합니다. 먼저 간단하게 정수를 보관하는 스택을 만들어 보기로 해요. class Stack { 스택에는 자료를 보관할 저장소가 필요합니다. int *buffer; 저장소의 크기를 기억하는 멤버를 선언하세요. const int size; 가장 최근에 보관한 자료의 위치를 인덱스로 기억하는 멤버를 선언하세요. int top; public: 생성자는 스택 크기를 입력 인자로 받게 합시다. Stack..

3.2.3 list 사용 STL의 list 사용 방법은 vector를 사용하는 방법과 매우 유사합니다. 차이가 있는 부분은 vector에서는 자료를 보관하는 저장소가 연속적인 메모리에 있어서 인덱스 연산을 제공하지만 list에는 제공하지 않는다는 점 정도입니다. 물론 vector에서 저장소의 크기를 확인할 때 사용하는 capacity 메서드나 저장소의 크기를 설정하는 reserve 메서드도 없습니다. 하지만 이 외에 대부분의 사용방법은 같습니다. 3.1.2 와 3.1.4에서 vector를 사용하는 코드에서 포함할 파일명과 타입 재지정하기 위한 typedef문에 vector만 list로 변경하면 아무런 컴파일 오류도 없으며 실행도 똑같이 동작합니다. //#include #include #include //..

3.2.2 이중 연결리스트 만들기 이번에는 노드에 링크가 두 개 있는 이중 연결리스트를 만듭시다. 그리고 연결리스트의 head와 tail이 가리키는 노드를 초기에 만들기로 할게요. 링크가 두 개 있으면 이전 노드의 위치 정보를 갖고 있으므로 삭제나 추가할 때 이전 노드의 위치를 기억하는 변수를 별도로 선언할 필요가 없습니다. 그리고 연결리스트 초기화 과정에서 head와 tail이 가리키는 각 노드를 초기에 만들면 자료를 보관하는 노드를 맨 앞이나 맨 뒤에 보관하지 않아 연산을 단순하게 표현할 수 있습니다. 이 부분은 실제 구현하면서 설명하기로 할게요. 참고로 자료를 보관할 목적이 아닌 연결리스트를 운영하기 쉽게 생성한 노드를 더미 노드(Dummy Node)라 부릅니다. 여기서 만들 이중 연결리스트는 he..

3.2.1 단순 연결리스트 만들기 이번에는 간단하게 단순(단일) 연결리스트를 만들어 보아요. 여기에서 만드는 단순 연결리스트는 개념을 잡기 위해 만드는 것으로 노드에 보관할 자료 형식을 정수로 한정할게요. 뒤에서 STL을 모델로 list를 만들 때 어떠한 자료 형식도 보관할 수 있게 만들거예요. 제공할 기능은 생성자, 해제화, 맨 뒤에 보관, 맨 앞에 보관, 원하는 위치에 보관, 탐색 가능한 반복자 제공, 데이터 제거, 데이터 보관 유무 확인, 전체 보기 기능입니다. 단순 연결리스트를 정의할 클래스 이름을 SimpleLinkedList라 정합시다. class SimpleLinkedList { 단순 연결리스트의 노드는 데이터와 다음 노드의 위치 정보를 기억하는 링크로 구성합니다. 노드는 연결리스트에서 접근..

3.2 연결리스트와 list 연결리스트는 보관하는 자료마다 별도의 노드에 보관하며 노드에 링크를 이용해 논리적으로 선형을 유지하는 자료구조입니다. 따라서 연결리스트를 노드의 선형 집합이라고 말합니다. 배열은 자료를 보관하는 메모리가 연속적인 형태를 지녀 순차리스트라 부르는 순차 자료구조입니다. 이에 반해 연결리스트는 자료 하나를 보관하는 노드마다 별도의 메모리를 할당하여 실제 메모리는 불연속적인 형태입니다. 따라서 연결리스트는 순차 자료구조가 아닙니다. 하지만 노드는 자료와 링크로 구성하는데 링크를 통해 연결리스트를 구성하는 노드들의 논리적인 구조를 선형의 모습으로 표현할 수 있습니다. 이러한 이유로 연결리스트를 선형 자료구조라 말하는 것입니다. 링크는 노드의 위치 정보를 말하며 노드에 링크가 하나인 연..

3.1.5 vector를 인덱스 연산으로 사용 vector는 확장 가능한 배열로 연속적인 메모리에 자료를 보관하는 자료구조입니다. 연속적인 메모리에 자료를 보관하기 때문에 메모리의 시작 위치에서 상대적 거리를 통해 원하는 요소를 접근하게 프로그래밍하면 접근 비용이 거의 들지 않습니다. 프로그래밍 언어에서 제공하는 배열은 거의 모두 인덱스 연산을 사용하여 배열의 원소에 접근하는 것을 제공하고 있습니다. STL의 vector에서도 인덱스 연산을 제공합니다. 주의할 점은 vector에는 저장소의 크기와 보관한 자료 개수를 기억하는 멤버가 있는데 인덱스 연산으로 사용할 때는 0에서 보관한 자료 개수 -1 까지 사용할 수 있어요. 따라서 보관한 자료에 접근하거나 변경할 때만 사용할 수 있다는 것입니다. 따라서 S..

3.1.4 vector에 특정 키 순으로 보관 이번에는 vector에 특정 키 순으로 보관하는 프로그램을 작성해 봅시다. 작성할 프로그램은 앞에서 작성한 프로그램과 같습니다. 다시 한 번 확인하기로 해요. 작성할 프로그램은 장르 관리 프로그램입니다. 장르에는 장르 번호와 장르명이 있습니다. 장르 번호와 장르명은 사용자에게 입력받습니다. 장르 번호와 장르명으로 삭제할 수 있고 검색할 수 있습니다. 그리고 모든 장르 목록을 확인할 수 있습니다. 제공할 기능을 살펴보면 장르 추가, 장르 번호로 장르 삭제, 장르명으로 장르 삭제, 장르 번호로 검색, 장르명으로 검색, 모든 장르 목록 확인이 있어요. 특정 키 순으로 보관하면 전체 목록을 확인할 때 원하는 키 순서로 보여줄 수 있어서 사용자 편의성이 높아집니다. ..

3.1.2 vector에 순차적으로 보관 작성할 프로그램은 장르 관리 프로그램입니다. 장르에는 장르 번호와 장르명이 있습니다. 장르 번호는 순차적으로 부여하며 장르명은 사용자에게 입력받습니다. 장르 번호와 장르명으로 삭제할 수 있고 검색할 수 있습니다. 그리고 모든 장르 목록을 확인할 수 있습니다. 제공할 기능을 살펴보면 장르 추가, 장르 번호로 장르 삭제, 장르명으로 장르 삭제, 장르 번호로 검색, 장르명으로 검색, 모든 장르 목록 확인이 있어요. vector에 순차적으로 보관할 때는 push_back 메서드를 사용하세요. 원하는 자료를 찾을 때는 반복자를 이용하여 찾거나 find, find_if 알고리즘을 이용하여 찾습니다. 삭제할 때는 자료가 있는 위치를 찾아 erase 메서드를 사용하세요. 모든 ..