[SW 정글] 5/21 PintOS - alarm

할거

 

pintos주차가 왓다

처음은 alarm clock이다

과제 내용은 아래와 같다

Reimplement timer_sleep(), defined in devices/timer.c.
Although a working implementation is provided, it busy waits, that is, it spins in a loop checking the current time and calling thread_yield() until enough time has gone by. Reimplement it to avoid busy waiting.

👇

evices/timer.c에 정의된 timer_sleep()을 다시 구현합니다. 작동하는 구현이 제공되더라도 바쁘게 기다립니다. 즉, 현재 시간을 확인하고 충분한 시간이 지날 때까지 thread_yield()를 호출하는 루프에서 회전합니다. 바쁜 대기를 피하기 위해 다시 구현하십시오.

 

문제는 busy waiting때문에 시간이 느리다. busy waiting을 쓰지말고 alarm clock을 구현하라

 

배운거

 

lock 프로그램적 해결법의 충족 조건

 

Mutual Exclusion

- 프로세스 Pi가 critical section부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다

 

Progress(진행)

- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면 critical section에 들어가게 해줘야 한다

 

Bounded Waiting

- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟숙에 한계가 있어야한다.

 

algorithms 1 

progress를 만족못함

do {
	while (turn != 0) // my turn?
    critical section
    turn = 1;		  // Now it's your turn
    remainder section
} while(1);

// progress를 만족 못하므로 제대로 된 알고리즘이 아님

 

algorithms 2

do{
	flag[i] = tue;	// Pretend I am in
    while(flag[i]); // IS he also in ? then wait
    critical section
    flag[i] = false; // I'am out now
    reminder section
 } while(1);
 
  // problem : 아무도 못들어가는 상황발생

 

 

algorithm 3 (Peterson's Algorithm) - good algorithm But, busy waitng

do{
	flag[i] = true;		// My intention is to enter ...
    trun = j;			// See to his turn
    while(flag[j] && turn == j);	// wait only if
    critical section
    flag[i] = false;
    remainder section
 }while(1);

 

Busy waiting (= spin lock)

계속 CPU와 memory를 쓰면서 wait 

 

Synchronization Hardware

하드웨어적으로 Test & modify를  atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

 

Mutual Exclusion with Test & Set

Synchronization variable :
	boolean lock = false;
    
Process Pi
	do {
    while (Test_and_Set(lock);
    critical section
    lock = false;
    remainder section
  	}

 

Semaphores

lock 걸고 푸는 것을 간단하게 추상화 시킴

공유자원을 공유하고 반납하는 것을 처리함

P연산 -> 공유하는 과정

V연산 -> 반납하는 과정

 

Critical Section of n Processes

Synchronization variable
semaphore mutes;	// initially 1 : 1개가 CS에 들어갈 수 있다

Process Pi
do {
	P(mutex);		// if positive, dec-&-enter, Otherwise, wait
    critical section
    V(mutex);		// Increment semaphore
    remainder section
}while (1);

busy-wait는 효율적이지 못함 (= spin lock)

Block & Wakeup 방식의 구현 (next page) (=sleep lock)

 

Block / WakeUp Implemetation

typedef struct
{
	int value;
    struct process *L; //Process wait queue
}semaphore;

block과 wakeup을 다음과 같이 가정

 

block : 커널은 block을 호출한 프로세스를 suspend시킨다. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다

 

wakeup(P) : block된 프로세스 P를 wakeup시킴. 이 프로세스의 PCB를 ready queue로 옮김

 

// Implementation

// P(S)
S.value--;	//prepare to enter
if(S.value<0)
{
	add this process to S.L;
    block();
}

// V(S)
S.value++;
if(S.value <= 0)
{
	remove a process P from S.L;
    wakeup(P);
}

 

Block/wakeup overhead vs Critical section 길이

critical section의 길이가 긴 경우 block/wakeup이 전달

critical section의 길이가 매우 짧은 경우 block/wakeup 오버헤드가 busy-wait 오버헤드보다 커질 수 있음

일반적으로는 block/wakeup 방식이 더 좋음

 

two types of semaphores

Counting semaphore

- 도메인이 0 이상인 임의의 정수값

- 주로 resource counting에 사용

Binary semaphore(=mutex)

- 0 또는 1 값만 가질 수 잇는 semaphore

- 주로 mutual exclusion ( lock/unlock)에 사용

 

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

 

Starvation

Indefinite blocking : 프로세스가 suspend된 이유는 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

 

 

---

 

느낀거

핀토스 너~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~무 너무 어렵다

 

어제 ~ 오늘 저녁까지 코드를 봤지만 뭘 어디서부터 손댈지, 어떻게 손대야할지 전~~~~~~~~혀 감을 못잡겠었다.

 

그래서 결국 kaist 강의 슬라이드를 구글링해서 구해서 보면서 구현을 하고 있다

 

보니까 조금 낫긴하지만

 

어어어ㅓㅁ~~~~~~~~~~~~~~~~~청어려운게 어려워졌다는 정도의 차이밖에없다

 

1주차 제일 쉬운과제도 헤매고있는데 3,4주차되면 어떻게 될지 두렵다

 

그래도 이렇게 하루하루 열코하다보면 실력이 늘것이라고 기대하고 있다

 

 

 

 

이글을 읽는 모두 오늘 하루도 고생했고 내일도 열코하도록 하자 🔥