search

J-dbd / PintOS_lab

Other
0 stars 0 forks source link

12/01 mlfq logic and pseudo code #12

Closed J-dbd closed 9 months ago

J-dbd commented 9 months ago

1. make Priority Donation disable

void lock_acquire(struct lock *lock) {
if(! thread_mlfqs) {
 /* mlfq가 false일 때 : priority donation 사용 */
}

void lock_release(struct lock *lock) {
...
}

void thread_set_priority(int new_priority) {
...
}

2. fixed_point.h 작성

3 struct thread에 필요한 property(?) 추가

4. initialize 하기

5 adding funcs

skeleton func들 작성하기

/* Sets the current thread's nice value to NICE. */
void
thread_set_nice (int nice UNUSED) {
    /* TODO: Your implementation goes here */
    // interrupt off needed 
}

/* Returns the current thread's nice value. */
int
thread_get_nice (void) {
    /* TODO: Your implementation goes here */
    return 0;
}

/* Returns 100 times the system load average. */
int
thread_get_load_avg (void) {
    /* TODO: Your implementation goes here */
    return 0;
}

/* Returns 100 times the current thread's recent_cpu value. */
int
thread_get_recent_cpu (void) {
    /* TODO: Your implementation goes here */
    return 0;
}

timer_interrupt

...
if ( curr ! = idle ) {
curr->recent_cpu ++;
}

if (timer_ticks() % TIME_FREQ ==0) {
update_recent_cpu()
}

if (timer_ticks() % 4 == 0) {
  for (ready_list) {
    // 순회 돌며 모든 스레드의 priority 를 갱신 
  }
 list_sort( ready_list )

 if( curr->priority < = readylist.begin ...->priority ) {
    thread_yield //양보 
}

mlfqs_update_recent_cpu

//ready_list에 있는 스레드
for (read_list ... ) 
  nice, recent_cpu 불러오기 (int)
 실수 변환 
 변환한 값을 /100 
 thread_get_load_avg 를 실수변환
 변환한 값을 /100 

recent_cpu 갱신 

if (curr != idle) {
   thread_current() -> recent_cpu = (연산)
J-dbd commented 9 months ago

trouble shooting & studying

이해에 도움이 되었던 참고 페이지 https://web.stanford.edu/class/cs140/projects/pintos/pintos_7.html#SEC131

멀쩡했던 priority donate lower의 상태가..?

thread_mlfqs로 if문 분기 처리 시 중복하여 priority를 갱신하는 이슈 : 어떤 기능을 추가하여 특정 변수를 트리거로 if문을 추가할 때 중복 처리될 수 있음을 교훈으로 얻음 

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {

    struct thread* curr = thread_current ();
    // [ project1-B : Donation ]
    if(! thread_mlfqs) {
        if (curr->priority == curr->original_priority) {
        curr->priority = new_priority;
        curr->original_priority = new_priority;

        } else {
            curr->original_priority = new_priority;
        }

    }

    ///////////////////////////////////////////////////
    // if(thread_mlfqs){
    //  curr->priority = new_priority;
    // }
    curr->priority = new_priority;  //if문을 나오고 다시 한번 더 갱신하여 오류 발생
    thread_switch();
    ///////////////////////////////////////////////////
}

실수(fixed point)와 정수 연산

#define F (1 << 14)     //fixed point 1 
int int_to_fp(int n) {
    return n * F;
}

int fp_to_int_round(int x) {
    if (x >= 0) return (x + F / 2) / F;
    else return (x - F / 2) / F;
}

int fp_to_int(int x) {
    return x / F;
}
int add_fp(int x, int y) {
    return x + y;
}
int sub_fp(int x, int y) {
    return x - y;
}
int add_mixed(int x, int n) {
    return x + n * F;
}
int sub_mixed(int x, int n) {
    return x - n * F;
}
int mult_fp(int x, int y) {
    return ((int64_t) x) * y / F;
}
int mult_mixed(int x, int n) {
    return x * n;
}
int div_fp(int x, int y) {
    return ((int64_t) x) * F / y;
}
int div_mixed(int x, int n) {
    return x / n;
}

pintOS에서 실수 값을 표현하기 위해 사용한 fixed point는 실수 값을 가정한 정수이고, 따라서 연산에 주의해야 한다. 특히 실수(정수로 표현됨)과 정수의 연산 시 정수를 실수화(fixed point로 변환)를 하지 않는 경우 굉장히 작은 값으로 처리가 된다. 이것을 이해하는 게 중요했다.

//example

int a = (59/60)*load_avg // 0
int b = div_fp(int_to_fp(59), int_to_fp(60))*load_avg // 16110 

// 59*(1<<14) or 60*(1<<14) 의 차이.

여담으로 가끔 꽤 큰 마이너스 값이 나오는데, fp의 최상위 비트가 계산 중 오염되어서 sign bit가 0이어야 되는게 1이 되는 것이 아닌가 하는 추측을 한 친구가 있었다.

fixed pointreal airthmetic

이번 프로젝트에서 pintOS는 recent_cpu와 load_avg의 real number를 표현하기 위해 fixed pointreal airthmetic을 사용한다. 즉, Kernel 에서 floating-point arithmetic을 지원하지 않는다.왜냐하면 부동소수점 연산은 무한에 가까운 실수를 표현하기 위해 많은 메모리와 시간을 소모하여, 커널을 더 복잡하고 느리게 만들기 때문이다. 즉 일정 부분의 정확도를 포기하여 빠른 연산과 오버헤드가 발생하지 않는 안정성을 획득하기 위해서 부동소수점(fixed point) 연산을 사용한다.

여기서 오버헤드가 발생한다는 것이 무슨 뜻일까? 공룡 책(Operationg System concept)에서 찾아보니 스케쥴러가 context switching을 할 때 이전 프로세스의 레지스터의 정보들을 저장한다고 한다. 그런데 부동 소수점 레지스터는 별도로 관리되고 저장되는데 이것이 오버헤드를 발생시킨 것 같다.

OSR community의 한 게시글에서는 부동소수점을 사용한 연산 시 사용하는 FPU라는 프로세서의 상태를 저장하는 것이 엄청난 비용이 드는 작업이라고 한다. 그래서 과거에 이 비용을 포기하고 부동소수점 연산을 하지 않는 방향으로 커널을 설계했고, 지금까지도 그렇게 쓰고 있다는 듯 하다. 심지어 80387/80386(?) 까지는 부동소수점을 계산할 수 있는 산술 보조 프로세서가 따로 분리되어 나왔던 모양이다.

부동소수점 연산 고정소수점 연산
특징 정확함 일정 부분 정확도를 희생
시간과 메모리를 많이 차지함 연산이 빠르고 메모리를 덜 차지함
제한된 정밀도지만 빠르고 간단한 하드웨어로 구현 가능
사용처 커널 수준 프로그래밍, 임베디드...

정확도와 크기 / 시간과 메모리의 오버헤드... 두 연산 방식 간에 tread off가 있다

요약하자면 pintOS에서는 커널 수준에서 recent_cpu와 load_avg가 다루는 실수(real number)연산을 정확도를 어느정도 포기하고 빠른 속도와 안정성을 챙기는 부동소수점 연산을 통해 처리한다.

부동소수점 연산은 이 연산을 처리할 때, 실제 소숫점 자리 등을 표기할 수 없으므로 shift 연산을 통해 거대한 정수(1이 2의 14승이다, 이 경우에서는)로 소수점 자리까지 어느정도 보장하여 표현한다.

이러다 보니 정수 연산을 할 때 이 정수를 부동소수점화(化) 하여 처리하지 않는다면 오류가 발생한다. 가령 59/60을 (정수)59/(정수)60을 한 뒤, int 타입 처리를 한다면(int로 처리해야 계산이 가능하기 때문) 0이 되어 제대료 표현할 수 없고, 이것이 priority에게까지 영향을 끼쳐 제대로 된 스케쥴링이 불가능하다.

so what?

이럴 때 해결책으로는 여러가지 방법이 있을 수 있다.

Operationg System concept

A range of extra hardware support was included in this release. Although still restricted to the Intel PC platform, hardware support had grown to include floppy-disk and CD-ROM devices, as well as sound cards, a range of mice, and international keyboards. Floating-point emulation was provided in the kernel for 80386 users who had no 80387 math coprocessor. System V UNIX-style interprocess communication (IPC), including shared memory, semaphores, and message queues, was implemented. (p777)

이 릴리스에는 추가적인 하드웨어 지원이 포함되었습니다. 여전히 인텔 PC 플랫폼에만 제한되어 있지만 하드웨어 지원은 플로피 디스크와 CD-ROM 디바이스, 사운드 카드, 다양한 마우스, 국제 키보드를 포함하도록 성장했습니다. 80387 수학 보조 프로세서가 없는 80386 사용자를 위해 커널에서 부동 소수점 에뮬레이션이 제공되었습니다. 공유 메모리, 세마포어, 메시지 큐를 포함한 시스템 V 유닉스 스타일 프로세스 간 통신(IPC)이 구현되었습니다. (p777)

Scheduling context: The most important part of the process context is its scheduling context — the information that the scheduler needs to suspend and restart the process. This information includes saved copies of all the process’s registers. Floating-point registers are stored separately and are restored only when needed. Thus, processes that do not use floating-point arithmetic do not incur the overhead of saving that state. The scheduling context also includes information about scheduling priority and about any outstanding signals waiting to be delivered to the process. A key part of the scheduling context is the process’s kernel stack, a separate area of kernel memory reserved for use by kernel-mode code. Both system calls and interrupts that occur while the process is executing will use this stack. (p788)

스케줄링 컨텍스트: 프로세스 컨텍스트에서 가장 중요한 부분은 스케줄러가 프로세스를 일시 중단 및 재시작하기 위해 필요한 정보인 프로세스의 스케줄링 컨텍스트입니다. 이 정보에는 모든 프로세스 레지스터의 저장된 복사본이 포함됩니다. 부동 소수점 레지스터는 별도로 저장되며 필요할 때만 복원됩니다. 따라서 부동 소수점 산술을 사용하지 않는 프로세스는 해당 상태를 저장하는 오버헤드가 발생하지 않습니다. 스케줄링 컨텍스트에는 스케줄링 우선순위에 관한 정보 및 프로세스에 전달되기를 대기 중인 미결 신호에 관한 정보도 포함됩니다. 스케줄링 컨텍스트의 핵심적인 부분은 프로세스의 커널 스택인데, 이는 커널 모드 코드에 의해 사용되도록 예약된 커널 메모리의 별도 영역입니다. 프로세스가 실행되는 동안 발생하는 시스템 호출 및 인터럽트 모두 이 스택을 사용할 것입니다. (p788)

OSR Developer Community

https://community.osr.com/discussion/268074/floating-point-operations-in-kernel

1) Why floating point operations are not permitted at kernel level? Is it because when a kernel-kernel context switch happens the state of FP registers is not saved, while it is saved in a user-kernel transition (feel free to correct if wrong)?

커널 레벨에서 부동 소수점 연산이 허용되지 않는 이유는 커널-커널 컨텍스트 스위치가 발생할 때 FP 레지스터의 상태가 저장되지 않고 사용자-커널 전환(잘못된 경우 자유롭게 수정)되기 때문입니까?

Correct. In the early days of the NT kernel, when we were using 80387 co-processors, saving the FPU state was an extremely expensive operation -- many thousands of CPU cycles. The design decision was made at that point to skip it for kernel transitions. Once made, such a decision cannot be easily rescinded.

맞습니다. NT 커널 초기에 우리가 80387 공동 프로세서를 사용할 때, FPU 상태를 저장하는 것은 CPU 사이클 수천 번을 반복하는 엄청난 비용이 드는 작업이었습니다. 그 시점에서 설계 결정은 커널 전환을 위해 생략하기 위해 내려졌습니다. 한번 결정되면 그러한 결정은 쉽게 취소될 수 없습니다.

int64_t 과 int

https://www.quora.com/What-is-the-difference-between-int-and-int32_t https://stackoverflow.com/questions/14515874/difference-between-int32-int-int32-t-int8-and-int8-t

int, int32_t, int64_t는 왜 구분해야 하는 걸까?

int : size >= 16bits 면 그 어떤 사이즈도 int타입이 될 수 있다.

int32_t, int64_t... 는 <stdint.h>헤더에서 typedef로 선언된 타입이며 각각 특정한 사이즈를(32bits, 64bits) 보장받는다. 즉 보장받은 사이즈만큼의 bits로 연산의 정밀도를 보장받을 수 있다고 볼 수 있다.

pintOS의 경우 원래 32비트로 구현되었던 거라고 하고, 64비트로 구현하려면 세심하게 캐스팅해주어야 한다고 하는 듯 하다. (핀토스 외에도 다른 머신들, 특히 64비트로 처음부터 시작하지 않은 경우라면, 특히 C로 다룰 때 모두 샌경 써야 한다. 자바 같은 언어는 조금 덜 신경 써도 된다고 한다.) int64_t로 캐스팅을 하지 않으면 오버플로우가 일어날 수 있음.

Decaying threads in sleep list : blocked된(sleep중인) thread의 감쇠(decay)

thread의 균형잡힌 스케쥴링을 위해서, pintOS의 advanced schedule 섹션에서는 4.4BSD scheduler를 사용한다.

I/O 을 담당하는 threads는 input과 output을 위해서는 빠른 반응을 요구하지만 cpu를 점유하는 시간 자체는 짧으면 된다. 그러나 compute-bound thread는 많은 CPU시간을 요구하지만 빠른 반응 시간을 요구하지 않는다. 그 사이에 있는 다른 스레드들은 요구하는 시간들이 제각각이다. 이런 thread의 요구조건을 scheduler가 미리 알 순 없으므로 thread의 사용량으로 이것을 예측하는 공식을 세운다. 그 인자로는 system-wide한 load_avg와 각각의 threads마다 가진 recent_cpu, 그리고 얼마나 잘 양보하는 속성을 가졌는지의 지표인 nice를 세팅해 사용한다.

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
//아직 load_avg는 보이지 않는데, load_avg는 recent_cpu 내부에서 계산된다.

recent_cpu

recent_cpu = decay * recent_cpu + nice

nice

얼마나 잘 양보하는 속성을 가졌는지의 지표. 양수와 음수 값을 가지는데, 높을 수록 우선순위를 빠르게 낮춘다.

decay(감쇠) 와 load_avg

load_avg = (59/60)*load_avg + (1/60)*ready_threads
decay = (2 * load_average) / (2 * load_average + 1)

각 요소는 갱신 되는 시간이 다르다.

언제 무엇을? load_avg recent_cpu priority
증가 increase 1 tick (실행중일 때) 4 tick
재계산 recalc 1 sec 1 sec 4 tick

sleep 중인 스레드의 recent_cpu도 계산 해야 하는가?

blocked되거나 sleep하게 되어 sleep list로 따로 관리되고 있는 thread의 recent_cpu와 우선순위도 갱신해 주어야 한다. 개인적으로는 '스레드가 잠들어 있다면 변화가 없을 것이다' 라고 생각 했는데, 오류가 떠서 생각을 해보니...

  1. load_avg가 특정 스레드에만 적용되는 것이 아니고 전역변수로서 선언되는 system-wide한 요소이자 시스템 전체의 부하를 측정하는 변인이며,
  2. 이것이 적용되는 decay는 시간의 흐름에 따라 오래된 과거의 데이터가 미치는 영향을 감소시키는 요소로 사용되었으니

sleep list에 있다 하더라도 잠든 스레드의 우선순위에도 영향을 미칠 것 같다' 는 생각이 들었다.

그 외


// inerrupt off 하는 코드 
if (!a ) {
   // interrupt on 코드 작성 필수 
    return 
    }