[태그:] scheduling

목차

0. analysis
0.1. thread
0.1.1. struct thread
0.1.2. thread functions
– [thread 시작 관련 function]
– [thread 관리 function]
– [thread 동작 관련 function]
– [scheduling function]
– [timer 관련 function]
0.1.3. list
– [list function]
0.1.4. how to switch thread
0.2. synchronization
0.2.1. meaning of synchronization
0.2.2. disabling interrupts
0.2.2.1. meaning of disabling interrupts
0.2.2.2. caution
0.2.2.3. implement
0.2.3. semaphore
0.2.3.1. meaning of semaphore
0.2.3.2. implementation
0.2.4. lock
0.2.4.1. meaning of lock
0.2.4.2. implementation
0.2.5. condition
0.2.5.1. meaning of condition
0.2.5.2. implementation
0.2.6. interrupt handling
0.2.6.1. external interrupt handling

1. alarm clock
1.1. current implementation
1.1.1. timer.c functions
1.1.2. busy-waiting
1.2. new implementation

2. priority scheduling
2.1. current implementation
2.2. new implementation
2.2.1. priority scheduling modification
2.2.2. synchronization modification
2.2.3. priority donation modification

3.advanced scheduling
3.1. MLFQS
3.2. Priority scheduling
3.2.1. ready queue 관리
3.2.2. priority 관리
3.2.3. priority 계산
3.3. fixed-point arithmetic
3.4. implementation

본문내용

0.1. thread
pintos에서는 thread creation과 thread completion, Round-Robin 방식의 thread switching(simple scheduler)을 이미 구현해 두었다.
0.1.1. struct thread
kernel thread의 struct는 “threads/thread.h”에 선언되어 있다.
thread structure은 4kB page를 차지한다. struct thread는 page of memory의 시작부터 공간을 차지한다. page의 나머지 부분은 thread의 stack을 위해 이용되는데, 이는 end of the page로부터 아래쪽 방향으로 내려가며 진행된다.

따라서 kernel stack을 위한 공간을 위해 struct thread는 너무 크기가 크면 안 된다. base struct thread는 1kB 미만이어야 한다. 그리고 kernel stack도 너무 크면 안 된다. stack에서 overflow가 발생하면 thread state를 침범할 것이므로 kernel function은 struct와 array에 non-static local variable 같이 너무 많은 공간을 할당하지 않고, malloc()이나 palloc_get_page() 같은 동적 할당 function을 써야 한다.
[Member of struct thread]
tid_t tid
thread identifier를 뜻한다. 각 thread를 분간한다. 현재는 int 자료형에 1부터 numbering되게끔 짜여져 있다.

출처 : 해피캠퍼스

목차

1. alarm clock
1.1. implementation
1.1.1.data structure
1.1.2. algorithm
1.2. discussion

2. priority scheduling
2.1. implementation
2.1.1. data sturcture
2.1.2. algorithm
2.2. discussion

3. advanced scheduling
3.1. implement
3.1.1. how to compute priority in advanced scheduling
3.1.2. data structure
3.1.3. algorithm
3.2. discussion

4. result

본문내용

1. alarm clock
1.1. implementation
기존의 busy-waiting 방식을 sleep/wake-up 방식으로 변경하는 것은 시스템 자원을 효율적으로 사용하는 데 매우 중요하다. busy-waiting 방식은 프로세서가 일정한 시간동안 아무 작업도 하지 않고 반복적으로 상태를 확인하는 방법으로, 타이머나 조건이 충족될 때까지 CPU가 루프를 반복하며 기다린다. (예를 들어, 알람시계의 경우 지정된 시간이 도달할 때까지 현재 시간을 계속 확인하는 방법이다.) 이로 인해 CPU 사이클을 낭비하게 됨으로써 CPU 자원이 불필요하게 낭비되고, 전력 소비를 증가시킬 수 있다. 반면, sleep/wake-up 방식은 프로세서가 작업을 기다리는 동안 유휴 상태로 전환되어 다른 작업을 수행할 수 있게 한다. 따라서 시스템 효율성을 증가시킬 수 있으며, 특히 임베디드 시스템이나 배터리로 구동되는 장치에서 매우 유용하다. 이를 통해 불필요한 자원 낭비를 줄이고, 시스템의 응답성을 높일 수 있다.

1.1.1.data structure
struct thread에 wakeup 변수 추가
busy-waiting 방식과 sleep/wake-up 방식의 가장 큰 차이점은 thread가 깨어야 할 시간에만 깨는지, 아니면 깨지 않아도 될 시간에도 깨워서 시간을 확인하는 지다. 그러므로 sleep/wakeup 방식을 구현하기 위해 각 thread가 깨어야 할 시간을 저장하는 변수를 thread struct 안에 추가해 주는 것이 좋다. wakeup 변수는 현재 thread가 깨어나야 하는 ticks 값을 저장한다.

출처 : 해피캠퍼스