🎯 To-do List

---

🔆 Today

1. PintOS GitBook 읽기 ✅
2. 정글 컴퍼스 영상 보기 ❌
3. 키워드 공부하기 ❌

바로 구현에 머리 박아보느라 뭐 못함

✅☑️❌

📚 Journal

---

게임랩

점심 먹고 올라오는 길에 게임랩 사람 만나서 얘기 걸어봄

• 바쁜가? : 개인 과제는 안 바쁘고 팀 과제 할 땐 바쁘다. 그래도 개중에 안 바쁜 사람들 있으니 그 사람들한테 물어보면.
• 뭐 하는가? (자세히 x) : 게임 프로토타입 만들어보고 재밌는지 안 재밌는지, 이유 분석

📝 배운 것들

---

🏷️ assert()

void DoSomething(char* str)
{
   assert(str != nullptr);   //str이 nullpointer 라면 프로그램을 종료시킨다.
   //Do Something...
}

assert 함수는 식이 0 또는 false 가 되면 프로그램을 중단 시키고 에러 로그를 띄워준다.

🏷️ Atomic Operation

• 원자적(atomic) : 연산이 중단되지 않고 한 번에 실행된다. 즉, 중간에 다른 연산이 끼어들어 다른 스레드가 그 중간 상태를 볼 수 없다.
• 여러 스레드가 공유 자원을 동시에 접근할 때, 이 연산이 원자적이 아니라면 데이터 불일치나 경쟁 상태(race condition)가 발생할 수 있다.

🏷️ 구조체 포인터 실수

struct *list_elem start;

list_elem까지가 구조체인데 포인터를 잘못 찍음

struct list_elem *start;

뒤에 찍어야 했다

🖥️ PintOS

---

🔷 Proejct 1 : Threads

최대한 정답 코드나 힌트 안 보고 할 것

깃북 읽고 정글 컴퍼스에 나와있는 영상들 대충 보고 키워드 대충 공부하고 내일부터 슬슬 건드려보면 될듯?

깃북 볼 때 이거 참고했다.

Introduction

이 과제에서 최소의 기능만 하는 thread system을 갖고 시작하게 됩니다. 이 시스템의 기능을 확장하면서 synchronization의 문제들을 잘 이해하게 되는 것이 여러분이 할 일 입니다. 먼저 threads 디렉토리에서 이 과제를 시작합니다. devices 디렉토리에도 몇가지 할 일이 있습니다. 컴파일은 threads 디렉토리에서 이뤄져야 합니다. 이 프로젝트의 설명을 읽기전에 Synchronization ← 먼저 읽어야 합니다.

threads 폴더랑 devices 폴더에 있는 것들 건드려서 과제 해결하면 된다.

Synchronization

적절한 동기화는 이 문제의 풀이 중 중요한 부분 입니다. 동기화 문제들은 인터럽트를 비활성화 시키면 쉽게 해결할 수 있습니다 : 인터럽트가 비활성화 되어 있으면, 동시성이 없어집니다. 즉 경쟁 조건의 가능성이 없어집니다. 이런식으로 모든 동기화 문제들을 해결하는건 매우 유혹적이지만, 그렇게 하지 마십시오. 대신 세마포어, 락, 컨디션 변수를 사용해서 동기화 문제들을 해결하세요. 어떤 동기화 함수가 어떤 상황에 쓰여야하는지 잘 모르겠다면, 동기화 ← 이 섹션을 읽거나 threads/synch.c 의 코멘트를 참고하세요.

인터럽트를 아예 막아버리면 얘 했다가 쟤 했다가 해버리면서 연산 순서도 뒤죽박죽, 결과도 뒤죽박죽이 되어버리는 가능성을 원천 차단해버리는데 그러지 말라는 뜻.

Pintos 프로젝트에서 인터럽트 비활성화가 최선의 해결책이 되는 문제는 딱 하나, 커널 쓰레드와 인터럽트 핸들러사이에 공유된 데이터를 조정해야 할 때 입니다. 인터럽트 핸들러는 잠들지 않기 때문에 lock을 소유할 수 없습니다. 이 말은 커널 쓰레드와 인터럽트 핸들러 사이에 공유되는 데이터는 인터럽트를 비활성화 시켜서만 커널 쓰레드에서 보호 받을 수 있다는 뜻 입니다.

커널 쓰레드 : 커널 내부에서 하는 작업. 필요에 따라 잠들거나 깰 수 있다.
인터럽트 핸들러 : 외부에서 발생한 인터럽트를 처리하는 코드. 잠들지 않고 되게 빠른 시간 안에 처리된다.

경쟁 조건 : 예를 들어, 커널 쓰레드가 뭐 하고 있는데 인터럽트 핸들러가 갑자기 들어와서 똑같은 거 만져버리면 결과가 이상해질 수 있다.

그래서 여러 스레드가 같은 데이터 쓸 땐 lock을 써서 한 놈 쓰면 다른 놈 못 쓰게 하는데, 인터럽트 핸들러는 그런 거 모르고 빨리 처리해야 하므로 lock을 못 씀.

결국 인터럽트 핸들러 << 커널 스레드한테서 이 막가파를 막을 때만 인터럽트 비활성화를 한다.

synch.c 에 있는 동기화 함수들은 인터럽트 비활성화하는 방식으로 구현되었습니다. 아마 인터럽트 비활성화로 돌아가는 코드의 양을 추가하게 될 텐데, 최소한으로 유지해주세요.

threads 폴더에 있는 synch.c에 코드를 추가해야 하는거인듯. 최소한으로.

제출물에는 busy wating (spin) 이 없어야 합니다. thread_yield()를 콜하는 작은 루프도 busy waiting 의 하나입니다. (yield = 양보; lock이 없는 쓰레드가 기다리는동안 cpu를 양보하기위한 함수)

Busy waiting : 바쁘게 기다린다는 뜻. 밥만 많이 먹는 백수 상태. 특정 조건이 참이 될 때까지 계속 조건을 확인하면서 반복 루프를 도는데, 딱히 유용한 일은 안 하고 그것만 확인하면서 CPU 자원을 먹게 되는 상황.

Alarm Clock

이미 잘 작동하는 timer_sleep()이 구현되어있지만 이는 busy wait 방식입니다. 즉 이는 계속해서 반복문을 돌면서 현재 시간을 확인하고 충분한 시간이 경과할 때까지 thread_yield()를 호출합니다. busy waiting 을 피하도록 다시 구현합니다.

일 안하고 있을 땐 cpu 자원 못 낭비하도록 쫓아내야하는듯?

timer가 적어도 x번 tick 할때까지 thread 호출의 실행을 일시 중단합니다. 시스템이 idle(다음 thread가 없는) 상태가 아니라면, thread가 정확히 x번의 tick이 발생한 직후에 wake up 할 필요가 없습니다. thread가 적절한 시간동안 대기 한 후 ready queue에 놓이게 해주세요.

timer가 다 돌아간 다음 바로 실행할 필요는 없고, ready queue에만 넣어도 된다.

(+이외)

TIMER_FREQ, timer_msleep(), timer_usleep(), timer_nsleep() 수정하지 마라.

Priority Scheduling

현재 실행중인 쓰레드보다 높은 우선순위를 가진 쓰레드가 ready list에 추가되면 현재 쓰레드는 즉시 프로세서를 새 쓰레드에게 양보해야합니다.

마찬가지로 쓰레드가 락, 세마포어 또는 조건변수(참고)를 대기할 때, 우선순위가 가장 높은 대기 스레드를 먼저 깨워야합니다. 쓰레드는 언제든지 자신의 우선순위를 올리거나 내릴 수 있지만, 우선순위를 내렸을 때 해당 쓰레드의 우선순위가 가장 높은 우선순위가 아니게 된다면 CPU를 즉시 양보해야 합니다.

우선순위 스케줄링 : 에버랜드 VIP 티켓 산 사람이 줄 설 때 싼 티켓 산 사람보다 앞에 서게 된다는 뜻

쓰레드 우선순위의 범위는 PRIMIN (0) 부터 PRI_MAX (63) 까지입니다. 숫자가 작을수록 우선순위가 낮으므로 우선순위 0이 가장 우선순위가 낮고, 우선순위 63이 가장 우선순위가 높습니다. 초기 쓰레드의 우선순위는 thread_create() 에 대한 인수로 전달됩니다. 이때 다른 우선순위를 선택할 이유가 없으면 PRI_DEFAULT (31) 를 사용하세요. PRI매크로는 threads/thread.h 에 정의되있고, 이 값들을 변경하면 안됩니다.

티켓이 63만원짜리부터 공짜까지 있다는 뜻. 비싼 티켓 갖고 있으면 당연히 먼저 CPU 사용 가능.

우선순위 기부를 구현해봅시다. 우선 우선순위의 기부가 필요한 모든 상황을 고려해야합니다. 하나의 쓰레드에 여러 우선순위가 기부되는 multiple donation 상황을 처리할 수 있어야 합니다. 또한 nested donation 즉 H가 M이 가진 락에서 대기하고있고, M은 L이 가진 락에서 대기하고 있다면 M과 L이 모두 H의 우선순위로 상승해야합니다. 필요하다면 8 단계와 같이 nested priority donation의 깊이에 대해 적당한 제한을 둘 수도 있습니다.

락을 대기한다 : 놀이기구 끝날 때까지 기다린다.

우선순위 기부 : 싼 티켓 산 놈이 놀이기구 타고 있으면 VIP가 놀이기구 멈춘 다음에 서민은 잠깐 쫓아내고 자기가 먼저 탄다는 뜻. 근데 너무 돈으로 사람 줄 세우면 폭동 일어나니까 적당히 8번 까지만 쫓아내면 된다.

우선순위 기부를 구현하기 위해 필요한 함수들

void thread_set_priority(int new_priority)

현재 스레드의 우선순위를 새 우선순위로 설정합니다.
만약 현재 스레드의 우선순위가 더 이상 높지 않으면 우선순위를 양보합니다.

void thread_get_priority(int new_priority)

현재 스레드의 우선순위를 반환합니다. 우선 순위 기부가 있는 경우 더 높은 (기부된) 우선순위를 반환합니다.

스레드가 다른 스레드의 우선순위를 직접 수정하는 인터페이스를 제공할 필요는 없습니다. 우선순위 스케줄러는 이후 프로젝트에 사용되지 않습니다.

우선순위 조작하는 함수를 따로 만들면 되지 스레드가 우선순위 헤집어놓을 필요는 없다는 뜻.

Advanced Scheduler

Implement a multilevel feedback queue scheduler similar to the 4.4BSD scheduler to reduce the average response time for running jobs on your system.

Like the priority scheduler, the advanced scheduler chooses the thread to run based on priorities. However, the advanced scheduler does not do priority donation. Thus, we recommend that you have the priority scheduler working, except possibly for priority donation, before you start work on the advanced scheduler.

4.4BSD scheduler 참고해서 발전된 큐 스케줄러 만들어라. 우선순위 기부는 구현할 필요 없음.

You must write your code to allow us to choose a scheduling algorithm policy at Pintos startup time. By default, the priority scheduler must be active, but we must be able to choose the 4.4BSD scheduler with the -mlfqs kernel option. Passing this option sets thread_mlfqs, declared in threads/thread.h, to true when the options are parsed by parse_options(), which happens early in main().

스케줄링 알고리즘 고를 수 있게 해야한다. -mlfqs 커널 옵션 골라서 4.4BSD 스케줄링 고를 수 있게 해라.

When the 4.4BSD scheduler is enabled, threads no longer directly control their own priorities. The priority argument to thread_create() should be ignored, as well as any calls to thread_set_priority(), and thread_get_priority() should return the thread's current priority as set by the scheduler. The advanced scheduler is not used in any later project.

4.4BSD scheduler 켜면 thread_create() 이거랑 thread_set_priority() 이거 무시 때리고 thread_get_priority() 이게 현재 우선순위 결정함.

4.4BSD Scheduler

The goal of a general-purpose scheduler is to balance threads' different scheduling needs. Threads that perform a lot of I/O require a fast response time to keep input and output devices busy, but need little CPU time. On the other hand, compute-bound threads need to receive a lot of CPU time to finish their work, but have no requirement for fast response time. Other threads lie somewhere in between, with periods of I/O punctuated by periods of computation, and thus have requirements that vary over time. A well-designed scheduler can often accommodate threads with all these requirements simultaneously.

입출력 장치는 응답 시간 빨라야 되고 cpu 연산 시간 적음.
compute-bound threads(계산 많이 하는 쓰레드)는 응답 시간 느려도 되는데 cpu 연산 시간 오래 걸림.
다른 것들은 그 중간.

이런 요구사항들 잘 조율해서 스케줄러 잘 만들어봐라.

For project 1, you must implement the scheduler described in this appendix. Our scheduler resembles the one described in [McKusick], which is one example of a multilevel feedback queue scheduler. This type of scheduler maintains several queues of ready-to-run threads, where each queue holds threads with a different priority. At any given time, the scheduler chooses a thread from the highest-priority non-empty queue. If the highest-priority queue contains multiple threads, then they run in "round robin" order.

스케줄러를 부록에 설명된 대로 만들어라. 쓰레드 넣어놓는 큐마다 우선순위가 다르고, 우선순위가 높은 큐부터 꺼내서 쓰레드 처리한다. 우선순위 높은게 너무 많으면 라운드 로빈 써라.

Multiple facets of the scheduler require data to be updated after a certain number of timer ticks. In every case, these updates should occur before any ordinary kernel thread has a chance to run, so that there is no chance that a kernel thread could see a newly increased timer_ticks() value but old scheduler data values.

타이머 돌아간 다음에 커널 스레드가 작동하게 해야지 안 그러면 우선순위 갱신한거 반영 못 함.

Niceness

Thread priority is dynamically determined by the scheduler using a formula given below. However, each thread also has an integer nice value that determines how "nice" the thread should be to other threads. A nice of zero does not affect thread priority. A positive nice, to the maximum of 20, decreases the priority of a thread and causes it to give up some CPU time it would otherwise receive. On the other hand, a negative nice, to the minimum of -20, tends to take away CPU time from other threads.

nice 값 놓으면 CPU 양보 잘 한다.

Calculating Priority

Our scheduler has 64 priorities and thus 64 ready queues, numbered 0 (PRI_MIN) through 63 (PRI_MAX). Lower numbers correspond to lower priorities, so that priority 0 is the lowest priority and priority 63 is the highest. Thread priority is calculated initially at thread initialization. It is also recalculated once every fourth clock tick, for every thread. In either case, it is determined by the formula:

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2),

테스트 방법

1. /pintos 경로에서 source ./activate (로그인할때마다 해야하므로 .bashrc에 명령어를 추가하는 것이 좋다.)

2. threads 폴더 들어가서 make clean - make check를 수행하면 Test Case들에 대해서 채점을 수행한다.

3. Test Case 한가지만 돌리고 싶다면, pintos/(프로젝트명)/build에 들어가서 아래 명령어를 수행하면 된다.
   pintos -T (Timout이 걸리는 시간) -- -q -run (Test case 이름)
   ex) pintos -T 10 -- -q run alarm-multiple
   → alarm-multiple 이라는 test case를 수행하며, 10초 후에는 무조건 종료하라.(무한루프에 빠지는 경우를 방지할 수 있다.)

4. 수행한 결과는 threads/build/tests/threads 폴더에 들어가면 확인해볼 수 있으며, Test Case에 관한 정보/코드는 pintos/tests/threads에 있다.
   threads/build/tests/threads/ 에 .output파일이 내가 짠 코드의 Test Case 결과이며, 틀렸을 경우 Expected Output과 Actual Output이 비교되어 출력된다.

계획

• 기존 (busy wait)
  쓰레드가 time_sleep을 호출한다
  드르렁
  커널이 야임마 하고 깨움
  나 아직 더 자야되는데? 다시 드르렁

• 수정 (sleep awake)
  쓰레드가 time_sleep을 호출한다
  이때 되면 깨워주세요~ 명부에 기록
  드르렁 (thread_block(), 쓰레드 큐 리스트에서 사라짐)
  커널이 명부 계속 체크하다가 깨울 때 되면 깨워서 큐 리스트에 넣기

시도 1. 드르렁 리스트

list_push_back(&ready_list, &t->elem) 이런 느낌으로 사용함.
elem을 어떻게 원하는 값으로 넣는가???

/* 명부에 적을 tid와 ticks를 위한 구조체 */
static struct wait_block
{
	struct list_elem elem; // 리스트에 넣기 위한 원소
	tid_t tid;			   // 쓰레드 식별자
	int64_t ticks;		   // 시간 틱
};

깨울 명부 구조체 선언하고

/* Suspends execution for approximately TICKS timer ticks. */
void timer_sleep(int64_t ticks)
{
	// int64_t start = timer_ticks(); // OS 시작하고 시간이 얼마나 지났는지

	// ASSERT(intr_get_level() == INTR_ON);
	// while (timer_elapsed(start) < ticks) // 처음 시작부터 지금까지 지난 시간이 ticks 이하이면
	// 	thread_yield();					 // 현재 실행중인 프로세스를 waiting list 끝으로 보낸다

	tid_t tid = thread_tid();
	extern struct list sleeping_list;

	struct wait_block wb = {tid, ticks};
	list_push_back(&sleeping_list, &wb.elem); // 드르렁 하기 전에 '명부'에 '자기 이름' 적어야 함
	thread_block();							 // 드르렁. 명부에서 자기 이름 나오면 딱 1번 깨서 마저 실행.
}

드르렁 시키는 건 가능한 것 같은데 (실행도 안 해보긴 함)
이제 어떻게 깨울지가 문제.

timer_sleep()가 각 쓰레드 별로 호출되는거라고 생각했는데,
맞는지 검증을 안 하고 막 만듦.
그리고 깨우는 방법도 모르겠음.

https://soundness.tistory.com/4

이거 보면 맞는 것 같긴 한데

다른 곳에선 busy wait 해결할 때 뮤텍스랑 세마포어 쓴다고 함
근데 말이 되나? 애초에 타이머랑 연관이 없는 개념 아님?

일단 만들었는데 list 푸는 함수가 내 구조체는 안 받아들이고 지들 쓰레드만 받아들임
쓰레드 자체에 드르렁 시간을 정해줘야할듯

시도 1. 정리

struct thread
{
	/* Owned by thread.c. */
	tid_t tid;				   /* Thread identifier. */
	int64_t sleep_ticks;	   // 드르렁 시간
	enum thread_status status; /* Thread state. */

thread.h에 있는
쓰레드 구조체에 드르렁 시간 추가

/* Suspends execution for approximately TICKS timer ticks. */
void timer_sleep(int64_t ticks)
{
	// int64_t start = timer_ticks(); // OS 시작하고 시간이 얼마나 지났는지

	// ASSERT(intr_get_level() == INTR_ON);
	// while (timer_elapsed(start) < ticks) // 처음 시작부터 지금까지 지난 시간이 ticks 이하이면
	// 	thread_yield();					 // 현재 실행중인 프로세스를 waiting list 끝으로 보낸다

	// tid_t tid = thread_tid();
	extern struct list sleeping_list;
	struct thread *sleeping_thread = thread_current();

	// struct wait_block wb = {tid, timer_ticks() + ticks}; // 드르렁 하기 전에 정보 적어놓기
	sleeping_thread->sleep_ticks = timer_ticks() + ticks;

	list_push_back(&sleeping_list, &(sleeping_thread->elem)); // 명부에 정보 전달
	thread_block();											  // 드르렁. 명부에서 자기 이름 나오면 딱 1번 깨서 마저 실행.
}

timer.c에 있는

timer_sleep()에서는 드르렁 하려는 쓰레드 정보 적고
드르렁 깨워주는 리스트에 등록한 다음
드르렁한다

static void
do_schedule(int status)
{
	ASSERT(intr_get_level() == INTR_OFF);
	ASSERT(thread_current()->status == THREAD_RUNNING);
	while (!list_empty(&destruction_req))
	{
		struct thread *victim =
			list_entry(list_pop_front(&destruction_req), struct thread, elem);
		palloc_free_page(victim);
	}

	// 드르렁 중인 친구들 수면 시간 체크하고 깨어날 시간이면 깨운다
	struct list_elem *listE;
	for (listE = list_head(&sleeping_list); listE == list_tail(&sleeping_list); listE = list_next(listE))
	{
		struct thread *sleeping_thread = list_entry(listE, struct thread, elem);

		if (sleeping_thread->sleep_ticks > timer_ticks())
		{
			list_remove(listE);				 // 드르렁 리스트에서 빼고
			thread_unblock(sleeping_thread); // 프로세스 깨운다
		}
	}
	thread_current()->status = status;
	schedule();
}

thread.c에 있는

do_schedule()에 드르렁 리스트 꼽사리 껴봄.

	// 드르렁 중인 친구들 수면 시간 체크하고 깨어날 시간이면 깨운다
	struct list_elem *listE = list_head(&sleeping_list);
	while (listE != list_tail(&sleeping_list))
	{
		struct thread *sleeping_thread = list_entry(listE, struct thread, elem);

		if (sleeping_thread->sleep_ticks > timer_ticks())
		{
			thread_unblock(sleeping_thread); // 프로세스 깨운다
			listE = listE->next;			 // 드르렁 리스트에서 다음 거 탐색할 준비 하고
			list_remove(listE->prev);		 // 이전 건 지워버린다
			continue;						 // 다음으로 넘어간다
		}

		listE = listE->next;
	}

돌려보니까 테케 다 틀림.
for문으로 돌리면 중간에 삭제될 때 오류날 것 같아서 while문으로 바꿈.

그래도 틀림.