[PintOS] 1-1 Alarm Clock

GIT

[thread.c, thread.h, timer.c, timer.h]

 

이론 영상 출처 : https://www.youtube.com/watch?v=myO2bs5LMak

# Todo

 - Pintos uses busy waiting for alarm
 - Modify pintOS to use sleep/wake for alarm

# Files to Modify

- threds/thread
- devices/timer

 

 

pintOS 기본 상태

 

구현해야 하는 상태

 

# todo

1. create sleep_list 
2. create wake_up()
3. create sleep()

4. modify timer_sleep()
5. modify timer_interrupt()
6. modify thread_init()

7. Function : 쓰레드 상태를 blocked로 만들고, sleep queue에 삽입한 뒤 대기하는 동작
8. Function : sleep queue에서 wake up 시킬 쓰레드를 찾는 동작 + wake up 시키는 동작
9. Function : 쓰레드가 가지고 있는 tick 최소값을 저장하는 동작
10. Function : 최소 tick 값을 반환하는 동작

 

---

1. timer_sleep (int64_t ticks)
   현재 실행 중인 쓰레드를 지정된 tick 수만큼 슬립 상태로 만드는 함수
	
   2. int64_t start = timer_ticks ()
      현재 tick 값을 가져옴
	
   3. while (timer_elapsed (start) < ticks)
      지정된 tick 수만큼 시간이 경과할 때까지 쓰레드를 슬립 상태로 유지
		 
      4. thread_yield()
         현재 CPU 사용 중인 쓰레드를 양보하고 다른 쓰레드에게 CPU 양보

thread_yield() :
	실행 중인 쓰레드를 양보하고 ready_list에 삽입하는 함수

timer_ticks() :
	현재까지 발생한 tick 수 반환하는 함수
	타이머 인터럽트가 발생할 때마다 tick 값이 증가
	
timer_elapsed () :
	주어진 시작 tick 값부터 현재까지 경과한 tick 수 반환하는 함수
	현재 tick 값에서 시작 tick 값을 빼서 경과한 tick 수 계산

 

1. thread_yield ()
	 쓰레드의 우선순위를 조정하고 스케줄링을 수행하는 함수
	 
	 2. struct thread *cur = thread_current()
		  현재 실행 중인 쓰레드의 포인터 저장

	 3. enum intr_level old_level
		  인터럽트 상태를 저장할 변수 선언
		  
	 4. old_level = intr_disable()
		  변수에 인터럽트 비활성화 상태 저장
		  
	 5. if (cur != idle_thread)
		  현재 쓰레드가 유휴 쓰레드가 아닌 경우에
		  
		  6. list_push_back(&ready_list, &cur -> elem)
			   현재 쓰레드를 ready_list의 맨 뒤에 추가 (= 현재 쓰레드를 준비 상태로 전환)
	 7. cur -> status = THREAD_READY
		  현재 쓰레드의 상태를 THREAD_READY 상태로 변경
	 8. schedule()
		  다음에 실행할 쓰레드를 선택하고 Context Switching 수행하는 함수
	 9. intr_set_level (old_level)
		  이전 인터럽트 상태를 복원

if (cur != idle_thread)
	 유휴 쓰레드인 경우에는 yield 하지 않음
	 * 유휴 쓰레드 : 시스템에서 다른 쓰레드가 실행 가능한 상태가 아닐 때 실행되는 특별한 쓰레드

intr_disable()
	 인터럽트를 비활성화하고, 이전 인터럽트 상태를 반환
	 => 인터럽트로 인한 race condition 방지

 

 

1. Define Sleep Queue

static struct list sleep_list

	** 초기화 하는 것 잊지 말기
	
	*** 어디서 선언할 것인지, 언제 초기화 할 것인지 고민하기
	

2. Global tick / Local tick

global tick, local tick 두개 만들어야 함
 
1) Global tick
	 시스템 전체에서 공유되는 tick값
	 타이머 인터럽트 발생 시 값이 증가
	 시스템의 절대 시간을 나타냄, 모든 쓰레드에서 공유하고 접근 가능
	 timer_ticks() 함수 호출 시 global tick 값 반환
	 시스템 전체의 시간을 측정하고 관리하는 데 사용
	 
2) Local tick
	 개별 쓰레드에서 사용되는 tick값 (공유 X)
	 각 쓰레드는 자신만의 tick값 가지며, 쓰레드 별로 독립적인 시간 측정 가능
	 쓰레드가 생성된 시점 ~ 쓰레드가 실행된 시간 측정하는 데 사용
	 쓰레드가 실행될 때마다 값이 증가
	 쓰레드가 block, yield 되면 local tick은 그대로 정지
	 쓰레드 구조체 내에 local tick 저장 필드가 존재
	 쓰레드 생성 시 초기화 / 쓰레드 실행 중 업데이트

 

1. timer_sleep()
   현재 실행 중인 쓰레드를 지정된 tick 수만큼 슬립 상태로 만드는 함수
	 
2. start = timer_ticks()
   현재 tick 값을 저장
		  
3. if (timer_elapsed (start) < ticks)
   현재 쓰레드의 경과한 시간이 지정된 tick 값보다 작을 경우
			
4. thread_sleep(start + ticks)
   현재 쓰레드를 슬립 상태로 만들고, 슬립 큐에 삽입
   wakeup을 위해 start + ticks로 시간 정해줌

 

start = timer_ticks() 변수를, thread_sleep(start + kicks)로 사용하지 못한다 ?

→ start는 지역변수여서, timer_sleep() 종료 시 더이상 사용 X ⇒ 다른 함수에 start 변수는 넣지 못함

 

1. sleep_list, ready_list에 쓰레드를 넣고 뺄 때 disable interrupt 중요함

2. sleep_list에서 정렬하는 게 편함
   wake time이 빠른 순서대로 앞에 위치
   첫 번째 쓰레드의 wake up 소요 시간까지의 쓰레드만 검색하면 됨

 

수정해야 하는 함수

1. thread_init()
	 sleep queue data structure 초기화하는 코드 추가해야 함
	 
2. timer_sleep()
	 sleep queue에 쓰레드를 넣는 동작 추가해야 함
	 
3. timer_interrupt()
	 모든 틱마다, sleep queue에 있는 쓰레드가 wake up 하는 걸 체크할 것
	 wake up 동작 추가해야 함
	 
	 
추가해야 하는 함수

1. 쓰레드 상태를 blocked로 만들고, sleep queue에 삽입한 뒤 대기하는 동작
2. sleep queue에서 wake up 시킬 쓰레드를 찾는 동작 + wake up 시키는 동작
3. 쓰레드가 가지고 있는 tick 최소값을 저장하는 동작
4. 쓰레드가 가지고 있는 tick 최소값을 반환하는 동작

---

함수 수정/추가 할때마다 기록을 하면서 해야했는데, 이거 고치고 저거 고치고 하다보니까 before&after 비교가 힘들어졌다.