PintOS에 이미 user program을 load하고 실행할 수 있는 베이스 코드를 제공하고 있지만, I/O나 interactivity는 제공하지 않는다. 이 프로젝트에선 시스템 콜을 통해 프로그램이 OS와 interact(상호작용) 하도록 만드는 것이 목표이다. 이번 과제에서 작업할 주요 디렉토리는 userprog 이지만, 거의 모든 PintOS의 내부 파트마다 상호작용할 것이다.(다른 디렉토리도 참고할 것이란 것) 아래에 관련있는 파트를 설명한다. 프로젝트 1에서 제출한 과제 위에서 프로젝트 2를 빌드해야 한다. 프로젝트 1의 코드는 프로젝트 2의 코드에 영향을 미치진 않지만, 프로젝트 1은 증분 프로젝트이므로 여전히 테스트 사례를 통과해야 합니다. 확장 과제는 옵션이며, 해당 과제는 뼈대를 포함..

Alarm Clock 💡 요구사항 timer_sleep() , defined in devices/timer.c 현재 작동하는 구현 방식은 busy wating 방식, busy waitng 방식을 개선한다. 기존 Busy Waiting 방식 현재 시간을 확인하고, thread_yield() 함수를 호출하며 일정 시간이 지날 때 까지 while 루프를 돈다. /* Suspends execution for approximately TICKS timer ticks. */ void timer_sleep (int64_t ticks) { int64_t start = timer_ticks (); // 현재 시간 구하기 ASSERT (intr_get_level () == INTR_ON); while (timer_elap..

동적 메모리 할당(Dynamic Memory Allocation)이란? 동적 메모리 할당(DYNAMIC MEMORY ALLOCATION) 은 컴퓨터 프로그래밍에서 실행 시간 동안 사용할 메모리 공간을 할당하는 것을 말한다. 즉, 프로그램이 실행되는 동안(runtime) 입력되는 데이터에 맞게 기억 공간을 확보하는 것을 동적 메모리 할당이라고 한다. 이는 프로그램이 실행하는 순간 프로그램이 사용할 메모리 크기를 고려하여 메모리의 할당이 이루어지는 정적 메모리 할당과 대조적이다. 그럼 정적 메모리 할당은 무엇일까? 정적 메모리 할당(STATIC MEMORY ALLOCATION)은 프로그램을 컴파일하는 단계에서 필요한 기억 공간의 크기를 결정하는 것이다. 즉, 프로그램을 작성한 이후 컴파일러는 "이 프로그램이..

이진 탐색 트리(Binary Search Tree, BST) 원소를 특정한 조건에 따라 정렬해 놓은 이진트리를 말한다. 이진 탐색 트리는 탐색을 위해 정렬을 해놓은 트리이다. 이진 탐색 트리는 검색 수행 연산은 O(logN) 이다. 이진 탐색 트리의 속성 모든 원소는 유일한 키 값을 갖는다. 즉, 중복된 내용을 가지는 항목은 없다. 왼쪽 서브트리의 모든 원소들은 루트의 키보다 작은 값을 갖는다. 오른쪽 서브트리의 모든 원소들은 루트의 키보다 큰 값을 갖는다. 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다. 즉, 일반 트리나 이진트리하고 똑같이 이진탐색트리도 재귀적인 정의를 한다.(서브트리에서 볼 때나 루트노드에서 볼 때나 위의 조건은 모두 성립되므로) 트리 안에서 어떤 노드를 루트로 잡던지 위 조건은..

C 언어로 연결 리스트 구현 정글에서 5주차가 진행되고 RB-Tree를 구현하는 과제가 주어졌다. 그것도 C 언어를 이용해서 RB-Tree의 자료구조를 구현해야 하는데, C 언어에 대한 문법도 익숙치 않을 뿐더러 RB-Tree 자료구조 구현 자체가 쉽지 않다기에 비교적 쉬우면서도 선수지식으로 알아야 할 '연결 리스트'와 '이진 검색 트리'를 C 언어를 구현해 봄으로써 C 언어를 익히고, RB-Tree를 구현하고자 한다. Operator 1. 연결리스트 구조체 만들고 사용하기 연결 리스트에서 노드를 추가하는 규칙 노드에 메모리 할당 next 멤버에 다음 노드의 메모리 주소 저장 data 멤버에 데이터 저장 마지막 노드라면 next 멤버에 NULL 저장 아래 이미지는 사용자가 정의한 구조체를 이용해 연결리스..

그리디 알고리즘이란? 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다. 그리디 알고리즘(Greedy Algorithm)란 바로 눈 앞의 이익만을 쫓는 알고리즘이다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 이러한 특성때문에 '욕심쟁이 알고리즘'이라는 별명이 붙은 알고리즘이기도 하다. 아래 이미지를 보면 큰 값을 찾기 위한 '그리디 알고리즘의 동작방식과 실제 큰 값은 다르다.'는 것을 알 수 있다. (진짜 욕심쟁이네....