📝 배운 것들
🏷️ UNUSED의 사용 목적
void thread_set_nice(int nice UNUSED)컴파일러는 함수에 정의된 인자들이 함수 내에서 사용되지 않으면 경고를 생성할 수 있습니다. 이러한 경고는 때때로 불필요하거나 의도적으로 인자를 사용하지 않으려는 경우에 불편할 수 있습니다. UNUSED는 이러한 경우에 다음과 같은 목적으로 사용됩니다:
컴파일러 경고 억제: 함수에 전달된 인자가 사용되지 않을 것임을 명시적으로 표시하여, 컴파일러가 해당 인자에 대해 경고를 생성하지 않도록 합니다.
코드의 의도 명확화: 함수 인자가 의도적으로 사용되지 않음을 코드상에서 명확히 드러냅니다.
그냥 구현 전에 경고 안 뜨게 하려고 한듯?
🖥️ PintOS
🔷 Advanced Scheduler
1. 기초 공부
https://www.youtube.com/watch?v=4-OjMqyygss
recent_cpu reset이 언제되는지에 대한 설명이 부족해서 gitbook 봤음
TIMER_FREQ의 배수일 때 reset한다
저 자료형을 위한 연산 함수를 직접 만들라는데
해야할 것들
수정해야 할 함수들
init_thread
- nice, recent_cpu 초기화
thread_set_priority - advanced scheduler를 이용할 땐 우선순위 지정 끄기
timer_interrupt - 모든 쓰레드의 load_avg, recent_cpu와 우선순위를 1초마다 재계산
- 모든 쓰레드의 우선순위를 4번째 tick마다 재계산
lock_acquire - advanced scheduler를 이용할 땐 우선순위 기부 끄기
lock_release - advanced scheduler를 이용할 땐 우선순위 기부 끄기
thread_set_nice - 현재 thread의 nice value를 지정한다
thread_get_nice - 현재 thread의 nice value를 return한다
thread_get_load_avg - load_avg에 100 곱한 값을 return한다
- timer_ticks() % TIMER_FREQ == 0
thread_get_recent_cpu - recent_cpu에 100 곱한 값을 return한다
✅ init_thread
- nice, recent_cpu 초기화
✅ thread_set_priority - advanced scheduler를 이용할 땐 우선순위 지정 끄기
✅ lock_acquire - advanced scheduler를 이용할 땐 우선순위 기부 끄기
✅ lock_release - advanced scheduler를 이용할 땐 우선순위 기부 끄기
✅thread_get_nice - nice를 return한다
✅thread_get_recent_cpu - recent_cpu에 100 곱한 값을 return한다
✅ thread_set_nice - 현재 thread의 nice value를 지정한다
- 현재 쓰레드의 nice value를 새로운 nice value로 수정하고, 다시 쓰레드의 우선순위를 새로 결정된 nice value를 기반으로 계산한다(바로 아래의 Calculating Priority를 참고할 것). 만약 현재 작동중인 쓰레드가 가장 높은 우선순위가 아니라면, CPU의 점유를 포기한다.
✅ thread_get_load_avg
- load_avg에 100 곱한 값을 return한다
- timer_ticks() % TIMER_FREQ == 0
timer_interrupt
- ✅ 모든 clock tick마다, 현재 돌고있는 쓰레드의 recent_cpu를 1씩 증가
- ✅ 1초마다, 모든 쓰레드의 load_avg, recent_cpu를 갱신
- load_avg = (59/60) load_avg + (1/60) ready_threads
- recent_cpu = (2 load_avg)/(2 load_avg + 1) * recent_cpu + nice - ✅ 4번째 tick마다, 모든 쓰레드의 priority를 재계산
- priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
recent_cpu와 load_avg는 실수
테케 하나만 디버깅 하는 방법
pintos -v -k -T 480 -m 20 -- -q -mlfqs run mlfqs-load-1
pintos -v -k -T 480 -m 20 --gdb -- -q -mlfqs run mlfqs-load-1
대충 만들고 디버깅 해봤는데 시간이 지나도 load_avg가 올라가질 않음.
소수점 표현 때문에 연산을 바꿔줘야 함.
너무 귀찮아서 사진 주고 gpt.
#define F (1 << 14) // 17.14 형식의 고정 소수점에서의 f 값
// n을 고정 소수점으로 변환
#define N_TO_FIXED(n) ((n) * F)
// 고정 소수점을 정수로 변환 (소수점 버림)
#define FIXED_TO_INT_ZERO(x) ((x) / F)
// 고정 소수점을 정수로 변환 (가까운 값으로 반올림)
#define FIXED_TO_INT_NEAREST(x) (((x) >= 0) ? ((x) + (F / 2)) / F : ((x) - (F / 2)) / F)
// x와 y 더하기
#define ADD_FIXED(x, y) ((x) + (y))
// y를 x에서 빼기
#define SUB_FIXED(x, y) ((x) - (y))
// x에 n을 더하기
#define ADD_INT_TO_FIXED(x, n) ((x) + (n) * F)
// n을 x에서 빼기
#define SUB_INT_FROM_FIXED(x, n) ((x) - (n) * F)
// x와 y 곱하기
#define MUL_FIXED(x, y) ((((int64_t) (x)) * (y)) / F)
// x와 n 곱하기
#define MUL_INT_TO_FIXED(x, n) ((x) * (n))
// x를 y로 나누기
#define DIV_FIXED(x, y) ((((int64_t) (x)) * F) / (y))
// x를 n으로 나누기
#define DIV_FIXED_BY_INT(x, n) ((x) / (n))
int ready_threads = (thread_current() == idle_thread) ? list_size(&ready_list) : list_size(&ready_list) + 1;
load_avg = ADD_FIXED(MUL_FIXED(load_avg, DIV_FIXED(N_TO_FIXED(59), N_TO_FIXED(60))),
MUL_FIXED(N_TO_FIXED(ready_threads), DIV_FIXED(N_TO_FIXED(1), N_TO_FIXED(60))));ready_threads의 개념을 잘 모르고 이상하게 했었는데, 이게 맞음.
현재 쓰레드도 고려, idle thread면 무시.
문제를 꼼꼼히 잘 읽어야 함.
// recent_cpu = decay * recent_cpu + nice
// decay = (2*load_average)/(2*load_average+1)
// load_avg = (59/60) * load_avg + (1/60) * ready_threads
// load_avg 계산
int ready_threads = list_size(&ready_list);
if (thread_current() != idle_thread)
ready_threads = ready_threads + 1;
load_avg = ADD_FIXED(MUL_FIXED(load_avg, DIV_FIXED(N_TO_FIXED(59), N_TO_FIXED(60))), DIV_FIXED(N_TO_FIXED(ready_threads), N_TO_FIXED(60)));
// printf("ready_list size : %d", list_size(&ready_list));
// printf("Updated load_avg: %d\n", FIXED_TO_INT_NEAREST(load_avg));
// recent_cpu = decay * recent_cpu + nice
t->recent_cpu = ADD_FIXED(
MUL_FIXED(
DIV_FIXED(
MUL_INT_TO_FIXED(load_avg, 2),
ADD_FIXED(MUL_INT_TO_FIXED(load_avg, 2), N_TO_FIXED(1))),
t->recent_cpu),
N_TO_FIXED(t->nice));리팩토링 하다가 되던것도 안됨. 그냥 망함.
git 저장도 안 해놨었는데 다행히 ctrl+z로 되돌림.
1초마다 갱신하는거 이상하게 함
/* 1초마다 모든 쓰레드의 recent_cpu 갱신 */
if (timer_ticks() % TIMER_FREQ == 0)
{
update_recent_cpu(thread_current());
for (e = list_begin(&ready_list); e != list_end(&ready_list); e = list_next(e))
{
ready_thread = list_entry(e, struct thread, elem);
update_recent_cpu(ready_thread);
}
}update_recent_cpu(ready_thread); 대기 중인 리스트들을 왜 update 해줌? 0으로 초기화 해야지
/* 1초마다 모든 쓰레드의 recent_cpu 갱신 */
if (timer_ticks() % TIMER_FREQ == 0)
{
// 현재 쓰레드는 recent_cpu 재계산
update_recent_cpu(thread_current());
// 나머지 쓰레드는 0으로 초기화
for (e = list_begin(&ready_list); e != list_end(&ready_list); e = list_next(e))
{
ready_thread = list_entry(e, struct thread, elem);
ready_thread->recent_cpu = 0;
}
}고쳤다
원래 함수 써버림
/* 4틱마다 모든 쓰레드 pirority 재계산 */
if (timer_ticks() % 4 == 0)
{
for (e = list_begin(&ready_list); e != list_end(&ready_list); e = list_next(e))
{
ready_thread = list_entry(e, struct thread, elem);
ready_thread->priority = thread_calculate_priority(ready_thread);
}
thread_set_priority(thread_calculate_priority(thread_current()));
}thread_set_priority 쓰면 안됐음
슬립 타이머?
bool for_ascending_sleep_time(const struct list_elem *a, const struct list_elem *b, void *aux)
{
int ap = list_entry(a, struct thread, elem)->sleep_ticks;
int bp = list_entry(b, struct thread, elem)->sleep_ticks;
return ap < bp;
}
/* Suspends execution for approximately TICKS timer ticks. */
void timer_sleep(int64_t ticks)
{
extern struct list sleeping_list;
struct thread *sleeping_thread = thread_current();
sleeping_thread->sleep_ticks = timer_ticks() + ticks;
list_insert_ordered(&sleeping_list, &(sleeping_thread->elem), for_ascending_sleep_time, NULL); // 명부에 정보 전달
enum intr_level old_level = intr_disable();
thread_block(); // 드르렁. 명부에서 자기 이름 나오면 딱 1번 깨서 마저 실행.
intr_set_level(old_level);
} while (!list_empty(&sleeping_list))
{
// struct list_elem *front = list_front(&sleeping_list);
struct thread *th = list_entry(list_front(&sleeping_list), struct thread, elem);
// struct thread *sleeping_thread = list_entry(f, struct thread, elem)->sleep_ticks;
if (th->sleep_ticks <= timer_ticks())
{
thread_unblock(list_entry(list_pop_front(&sleeping_list), struct thread, elem));
}
else
{
break;
}
}계산식 바꾸기 전에 이렇게 바꿨었음. 잘 작동하던 버전으로 되돌아갔음.
이것 때문에 오류 생기던 것인지는 불명.
계산식 고치기
요약
우선순위 재계산에 사용되는 수식들에 정수 자료형과 실수 자료형이 같이 사용되는데,
이때 잘못된 결과를 내지 않도록 변환 연산을 빠뜨리지 않고 꼼꼼하게 넣어주어야 함.기존에 잘못된 결과를 내고 있던 수식들을 디버깅하기 위해 칠판에 정리한 과정
연산식에서 틀렸을 가능성 높다고 함
gpt 믿지 말라고 함
// 정수 -> 실수
#define I_T_F(n) ((n) * F)
// 실수 -> 정수
#define F_T_I(x) (((x) >= 0) ? ((x) + (F / 2)) / F : ((x) - (F / 2)) / F)
// 실수 + 실수
#define ADD_I_F(x, n) ((x) + (n) * F)
// 실수 - 정수
#define SUB_F_I(x, n) ((x) - (n) * F)
// 실수 * 실수
#define MUL_F(x, y) ((((int64_t)(x)) * (y)) / F)
// 실수 / 실수
#define DIV_F(x, y) ((((int64_t)(x)) * F) / (y))필요한 매크로만 추리고 이름 바꾸기
priority 계산할 때 실수 부분은 계산 뒤에 정수로 바꾸면 추가 연산 필요 x
load_avg 계산할 때 ready_threads를 앞으로 보내고 실수 변환한 다음 60 나누기 계산으로 바꿔야됨
/* mlfqs를 위해 priority 새로 계산하기 */
int thread_calculate_priority(struct thread *t)
{
int recent_cpu = t->recent_cpu;
int nice = t->nice;
int priority = PRI_MAX - F_T_I(DIV_F(recent_cpu, I_T_F(4))) - (2 * nice);
return priority;
}
/* 현재 쓰레드의 recent_cpu 계산 */
void update_recent_cpu(struct thread *t)
{
// load_avg 계산
int ready_threads = list_size(&ready_list);
if (thread_current() != idle_thread)
ready_threads = ready_threads + 1;
load_avg = MUL_F(DIV_F(I_T_F(59), F_T_I(60)), load_avg) + DIV_F(I_T_F(ready_threads), I_T_F(60));
// recent_cpu 계산
t->recent_cpu = MUL_F(DIV_F(MUL_F(I_T_F(2), load_avg), SUB_F_I(MUL_F(I_T_F(2), load_avg), 1)), ADD_I_F(t->recent_cpu, t->nice));
}수정 버전 (F_T_I(60) 이거 잘못해서 터짐)
테스트 결과
pass tests/threads/mlfqs/mlfqs-load-1
pass tests/threads/mlfqs/mlfqs-load-60
pass tests/threads/mlfqs/mlfqs-load-avg
FAIL tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-10
FAIL tests/threads/mlfqs/mlfqs-block여기까지 통과
FAIL tests/threads/mlfqs/mlfqs-recent-1
FAIL tests/threads/mlfqs/mlfqs-recent-1
Some recent_cpu values were missing or differed from those expected by more than 2.5.
time actual <-> expected explanation
------ -------- --- -------- ----------------------------------------
2 0.00 <<< 6.40 Too small, by 3.90.
4 0.00 <<< 12.60 Too small, by 10.10.
6 0.00 <<< 18.61 Too small, by 16.11.
8 0.00 <<< 24.44 Too small, by 21.94.
10 0.00 <<< 30.08 Too small, by 27.58.
12 0.00 <<< 35.54 Too small, by 33.04.
14 0.00 <<< 40.83 Too small, by 38.33.
16 0.00 <<< 45.96 Too small, by 43.46.
18 0.00 <<< 50.92 Too small, by 48.42.
20 0.00 <<< 55.73 Too small, by 53.23.
22 0.00 <<< 60.39 Too small, by 57.89.
24 0.00 <<< 64.90 Too small, by 62.40.
26 0.00 <<< 69.27 Too small, by 66.77.
28 0.00 <<< 73.50 Too small, by 71.00.
30 0.10 <<< 77.60 Too small, by 75.00.
32 2.14 <<< 81.56 Too small, by 76.92.
34 79.33 <<< 85.40 Too small, by 3.57.
36 698.99 >>> 89.12 Too big, by 607.37.
38 undef 92.72 Missing value.
40 undef 96.20 Missing value.
42 undef 99.57 Missing value.
44 undef 102.84 Missing value.
46 undef 106.00 Missing value.
48 534.54 >>> 109.06 Too big, by 422.98.
50 undef 112.02 Missing value.
52 14.48 <<< 114.89 Too small, by 97.91.
54 undef 117.66 Missing value.
56 undef 120.34 Missing value.
58 undef 122.94 Missing value.
60 1085.41 >>> 125.46 Too big, by 957.45.
62 undef 127.89 Missing value.
64 1216.71 >>> 130.25 Too big, by 1083.96.
66 undef 132.53 Missing value.
68 undef 134.73 Missing value.
70 246.74 >>> 136.86 Too big, by 107.38.
72 undef 138.93 Missing value.
74 374.34 >>> 140.93 Too big, by 230.91.
76 676.52 >>> 142.86 Too big, by 531.16.
78 499.93 >>> 144.73 Too big, by 352.70.
80 306.46 >>> 146.54 Too big, by 157.42.
82 1089.18 >>> 148.29 Too big, by 938.39.
84 undef 149.99 Missing value.
86 1243.06 >>> 151.63 Too big, by 1088.93.
88 732.28 >>> 153.21 Too big, by 576.57.
90 25.25 <<< 154.75 Too small, by 127.00.
92 undef 156.23 Missing value.
94 undef 157.67 Missing value.
96 1119.32 >>> 159.06 Too big, by 957.76.
98 undef 160.40 Missing value.
100 undef 161.70 Missing value.
102 1046.74 >>> 162.96 Too big, by 881.28.
104 1180.95 >>> 164.18 Too big, by 1014.27.
106 undef 165.35 Missing value.
108 185.75 >>> 166.49 Too big, by 16.76.
110 undef 167.59 Missing value.
112 1158.07 >>> 168.66 Too big, by 986.91.
114 undef 169.69 Missing value.
116 undef 170.69 Missing value.
118 1302.13 >>> 171.65 Too big, by 1127.98.
120 undef 172.58 Missing value.
122 undef 173.49 Missing value.
124 1009.21 >>> 174.36 Too big, by 832.35.
126 undef 175.20 Missing value.
128 undef 176.02 Missing value.
130 undef 176.81 Missing value.
132 undef 177.57 Missing value.
134 658.75 >>> 178.31 Too big, by 477.94.
136 undef 179.02 Missing value.
138 970.55 >>> 179.72 Too big, by 788.33.
140 undef 180.38 Missing value.
142 481.55 >>> 181.03 Too big, by 298.02.
144 192.91 >>> 181.65 Too big, by 8.76.
146 undef 182.26 Missing value.
148 841.81 >>> 182.84 Too big, by 656.47.
150 740.87 >>> 183.41 Too big, by 554.96.
152 undef 183.96 Missing value.
154 undef 184.49 Missing value.
156 undef 185.00 Missing value.
158 341.64 >>> 185.49 Too big, by 153.65.
160 38.51 <<< 185.97 Too small, by 144.96.
162 undef 186.43 Missing value.
164 795.01 >>> 186.88 Too big, by 605.63.
166 undef 187.31 Missing value.
168 520.66 >>> 187.73 Too big, by 330.43.
170 undef 188.14 Missing value.
172 913.27 >>> 188.53 Too big, by 722.24.
174 1268.21 >>> 188.91 Too big, by 1076.80.
176 undef 189.27 Missing value.
178 undef 189.63 Missing value.FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-2
Some tick counts were missing or differed from those expected by more than 50.
thread actual <-> expected explanation
------ -------- --- -------- ----------------------------------------
0 2801 >>> 1904 Too big, by 847.
1 200 <<< 1096 Too small, by 846.FAIL tests/threads/mlfqs/mlfqs-nice-10
FAIL tests/threads/mlfqs/mlfqs-nice-10
Some tick counts were missing or differed from those expected by more than 25.
thread actual <-> expected explanation
------ -------- --- -------- ----------------------------------------
0 2948 >>> 672 Too big, by 2251.
1 53 <<< 588 Too small, by 510.
2 0 <<< 492 Too small, by 467.
3 0 <<< 408 Too small, by 383.
4 0 <<< 316 Too small, by 291.
5 0 <<< 232 Too small, by 207.
6 0 <<< 152 Too small, by 127.
7 0 <<< 92 Too small, by 67.
8 0 <<< 40 Too small, by 15.
9 0 = 8 FAIL tests/threads/mlfqs/mlfqs-block
FAIL tests/threads/mlfqs/mlfqs-block
Test output failed to match any acceptable form.
Acceptable output:
(mlfqs-block) begin
(mlfqs-block) Main thread acquiring lock.
(mlfqs-block) Main thread creating block thread, sleeping 25 seconds...
(mlfqs-block) Block thread spinning for 20 seconds...
(mlfqs-block) Block thread acquiring lock...
(mlfqs-block) Main thread spinning for 5 seconds...
(mlfqs-block) Main thread releasing lock.
(mlfqs-block) ...got it.
(mlfqs-block) Block thread should have already acquired lock.
(mlfqs-block) end
Differences in `diff -u' format:
(mlfqs-block) begin
(mlfqs-block) Main thread acquiring lock.
(mlfqs-block) Main thread creating block thread, sleeping 25 seconds...
(mlfqs-block) Block thread spinning for 20 seconds...
(mlfqs-block) Block thread acquiring lock...
(mlfqs-block) Main thread spinning for 5 seconds...
(mlfqs-block) Main thread releasing lock.
- (mlfqs-block) ...got it.
(mlfqs-block) Block thread should have already acquired lock.
(mlfqs-block) end⚔️ 백준
📌 3055 탈출
# import copy
# import sys
# sys.setrecursionlimit(10**4)
# 복습 큐 2개 써서 해보기
R, C = map(int, input().split())
twMap = [list(input()) for _ in range(R)]
# 문자열 뜯어서 받기 힘들다
# Sx, Sy = 0, 0
# for i in range(R):
# temp = input()
# for j in range(C):
# twMap[i][j] = temp[j]
# for i in range(R):
# for j in range(C):
# if twMap[i][j] == 'S':
# Sx, Sy = i,j
# 고슴도치 퍼뜨리고
# 홍수 퍼뜨리기
arrived = False
cnt = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
while(1):
# 고슴도치 움직임
moved = False
for i in range(R):
for j in range(C):
if twMap[i][j] == 'S':
for k in range(4):
if (0<=i+dx[k]<R)and(0<=j+dy[k]<C):
if twMap[i+dx[k]][j+dy[k]] == '.':
twMap[i+dx[k]][j+dy[k]] = -2
moved = True
elif twMap[i+dx[k]][j+dy[k]] == 'D':
arrived = True
# if i+1 < R and twMap[i+1][j] == '.':
# twMap[i+1][j] = -2
# moved = True
# if 0 <= i-1 and twMap[i-1][j] == '.':
# twMap[i-1][j] = -2
# moved = True
# if j+1 < C and twMap[i][j+1] == '.':
# twMap[i][j+1] = -2
# moved = True
# if 0 <= j-1 and twMap[i][j-1] == '.':
# twMap[i][j-1] = -2
# moved = True
# if i+1 < R and twMap[i+1][j] == 'D':
# arrived = True
# if 0 <= i-1 and twMap[i-1][j] == 'D':
# arrived = True
# if j+1 < C and twMap[i][j+1] == 'D':
# arrived = True
# if 0 <= j-1 and twMap[i][j-1] == 'D':
# arrived = True
for i in range(R):
for j in range(C):
if twMap[i][j] == -2:
twMap[i][j] = 'S'
# 티떱숲 홍수 갱신 (중복 계산 조심)
for i in range(R):
for j in range(C):
if twMap[i][j] == '*':
for k in range(4):
if (0<=i+dx[k]<R)and(0<=j+dy[k]<C):
if(twMap[i+dx[k]][j+dy[k]] == '.' or twMap[i+dx[k]][j+dy[k]] == 'S'):
twMap[i+dx[k]][j+dy[k]] = -1
# if i+1 < R and (twMap[i+1][j] == '.' or twMap[i+1][j] == 'S'):
# twMap[i+1][j] = -1
# if 0 <= i-1 and (twMap[i-1][j] == '.' or twMap[i-1][j] == 'S'):
# twMap[i-1][j] = -1
# if j+1 < C and (twMap[i][j+1] == '.' or twMap[i][j+1] == 'S'):
# twMap[i][j+1] = -1
# if 0 <= j-1 and (twMap[i][j-1] == '.' or twMap[i][j-1] == 'S'):
# twMap[i][j-1] = -1
for i in range(R):
for j in range(C):
if twMap[i][j] == -1:
twMap[i][j] = '*'
cnt += 1
if arrived:
break
elif not moved:
arrived = False
break
if arrived:
print(cnt)
else:
print('KAKTUS')
그냥 시뮬레이션이라고 생각하고 풀었는데
https://wookcode.tistory.com/167
시뮬레이션도 큐를 활용하면 필요한 부분만 갱신할 수 있다는 거 가져가기
