priority-condvar 테스트가 남았다이번 포스트에서는 Pintos의 우선순위 스케줄링 구현의 마지막 단계인 priority-condvar 및 관련 개념을 다룹니다. 들어가기에 앞서 mutex와 semaphore, condition variable에 대한 포스트를 읽고 와주시기를 권해 드립니다.잠깐, Priority Scheduling에서 Condition Variable은?대략적인 구조는 위와 같으며, 아래가 바로 synch.h에 위치한 컨디션 변수입니다.문제 상황Pintos는 기본적으로 비선점형 FIFO 정책으로 스레드를 처리하도록 되어 있었고, 지금까지 저희는 이를 선점형 우선순위 스케줄링으로 고치고 있었습니다. 다만 synch.c/h의 함수들을 수정하지 않은 채 내버려두고 있었지요. syn..

인트로우선순위 스케줄링에서 중요한 또 다른 개념은 우선순위 역전(inversion)/기부(donation)입니다. 낮은 우선순위 스레드가 높은 우선순위 스레드가 필요로 하는 뮤텍스를 획득하고 오랫동안 놓지 않으면, 높은 우선순위 스레드는 계속 기다려야 하는 우선순위 역전 문제가 발생합니다.이를 해결하기 위해 우선순위 상속 메커니즘이 사용될 수 있습니다. 뮤텍스를 획득한 낮은 우선순위 스레드는 그 뮤텍스를 기다리는 가장 높은 우선순위 스레드의 우선순위를 일시적으로 상속받아 실행됩니다. 뮤텍스를 해제하면 원래의 우선순위로 돌아갑니다.들어가기에 앞서 mutex와 semaphore, condition variable에 대한 포스트를 읽고 와주시기를 권해 드립니다.우선순위 역전아래와 같은 상황을 가정합시다.싱글코..

인트로Pintos 프로젝트 경험을 공유하는 두 번째 글입니다. 이전 글에서 timer_sleep 함수의 Busy Waiting 문제를 해결하고 효율적인 Sleep 메커니즘을 구현하는 '알람 시계' 파트를 다루었습니다. 이번 글에서는 OS의 핵심 기능 중 하나인 스케줄링(Scheduling), 그 중에서도 우선순위 스케줄링(Priority Scheduling)에 대해 이야기하려 합니다.들어가기에 앞서 mutex와 semaphore, condition variable에 대한 포스트를 읽고 와주시기를 권해 드립니다.스케줄링이란?다중 프로그래밍 환경에서 여러 스레드(또는 프로세스)가 동시에 실행될 준비가 되어 있을 때, CPU는 한 번에 하나의 스레드만 실행할 수 있습니다. 이때 어떤 스레드에게 CPU를 할당할..

인트로크래프톤 정글 9주차, Pintos 프로젝트를 진행하며 배우고 느낀 점들을 공유하는 시리즈의 첫 번째 글입니다. Pintos 프로젝트는 이론으로만 배우던 운영체제의 핵심 개념들을 직접 코드로 구현해보면서 깊이 이해할 아주 좋은 기회인데요. 그 첫 번째 파트인 '알람 시계(Alarm Clock)' 구현에 대해 이야기해 보고자 합니다.참고: 저희는 스탠포드대 CS 112/212의 오리지널 Pintos가 아닌, x86-64에 맞춘 Pintos-KAIST로 프로젝트를 수행하고 있으며, 포스트 또한 이를 기준으로 합니다.과제 목표: timer_sleep() 개선저희가 다룰 함수는 devices/timer.c에 정의된 void timer_sleep(int64_t ticks)입니다. 최초로 받았을 당시 기본 구..

아쉽게도 이 Rbt.가 아닙니다.0. 목차더보기1. 개념 정의2. 레드-블랙 트리의 규칙 5개조3. 레드-블랙 트리의 노드 삽입4. 레드-블랙 트리의 노드 삭제5. 레드-블랙 트리의 노드 검색6. 기타 특징7. 참고문헌1. 개념 정의레드-블랙 트리 (Red-Black Tree, RBT)는 이진 탐색 트리(BST)의 일종으로, 노드마다 적(赤)또는 흑(黒)색을 덧입혀 균형을 유지하는 자료구조입니다. 이를 통해 삽입, 삭제, 검색이 최악의 경우에도 O(log n)을 보장합니다.레드-블랙 트리의 독특한 특징 중 하나로 NIL 노드가 있습니다. RBT에서 모든 리프 노드는 NIL 노드로 대체됩니다. 즉, 트리내 모든 리프는 NULL이 아니라 (즉, 그냥 비워놓는 게 아니라) NIL 노드가 되도록 합니다. 실제 ..

Unused의 C언어 포인터 시리즈포스트URLC언어의 포인터 (기초)https://unused.tistory.com/221C언어의 포인터 이해: 선언으로서의 *, 연산자로서의 *https://unused.tistory.com/217C언어의 배열과 포인터https://unused.tistory.com/220C언어의 다중 포인터https://unused.tistory.com/215 인트로프로그래밍을 처음 접하면 “변수(위 그림의 ①)”는 익숙하지만, “포인터(위 그림의 ②)”란 개념은 낯설고 어렵게 느껴집니다.그런데 사실, 포인터 개념 자체는 어려울 게 없습니다. 포인터는 “메모리의 특정 주소를 저장한 변수”에 불과하거든요. 문법적으로 좀 헷갈리게 되어 있을 뿐입니다 (이번 포인터 시리즈 정리하면서 느낀 개..

Unused의 C언어 포인터 시리즈포스트URLC언어의 포인터 (기초)https://unused.tistory.com/221C언어의 포인터 이해: 선언으로서의 *, 연산자로서의 *https://unused.tistory.com/217C언어의 배열과 포인터https://unused.tistory.com/220C언어의 다중 포인터https://unused.tistory.com/215위 이미지의 for문을 한번 보시지요. 평소 짜던 것과는 다르지 않으신가요? C언어에서는 배열이 곧 포인터처럼 동작하기에 가능합니다.int arr[5] = {10, 20, 30, 40, 50};int *p = arr; // p는 arr의 첫 번째 요소를 가리키는 포인터여기서 arr은 배열 전체를 의미하지만, 대부분의 문맥에서..

Unused의 C언어 포인터 시리즈포스트URLC언어의 포인터 (기초)https://unused.tistory.com/221C언어의 포인터 이해: 선언으로서의 *, 연산자로서의 *https://unused.tistory.com/217C언어의 배열과 포인터https://unused.tistory.com/220C언어의 다중 포인터https://unused.tistory.com/215 인트로아래와 같은 C 코드가 있습니다.void main() { int value = 123; int *ptr1 = &value; printf("*ptr1: %d\n", *ptr1); // 출력 결과 123 *ptr1 = 456; printf("*ptr1: %d\n", *ptr1); // 출력 결과 4..