전공/운영체제

28. Locks

nongdamgom 2024. 1. 15. 19:57

 

Building a Lock

  • low cost의 좋은 lock을 위해 hardware와 OS의 도움을 받을 수 있음

 

 

Evaluating locks - Basic criteria

1. Mutual exclusion

  • 여러개의 thread를 사용할 때, critical section을 보호할 수 있는지

2. Fairness(Starvation)

  • flag를 누가 catch 했냐에 따라 lock을 잡고 못잡고가 결정 => 운이 안좋으면 계속 못잡을 수도 있음

3. Performance

  • spin waiting을 하면서, 계속 다른 thread가 기다려야 하는 문제 => cpu 낭비

==> 이러한 문제들을 어떻게 해결할 수 있을까?

 

 

Controlling Interrupts

void lock(){
	DisableInterrupts();
}

void unlock(){
	EnableInterrupts();
}

 

  • Disable Interrupts
  • 예전에 사용하던 방식
  • cpu가 하나일 때, 한 process가 lock을 잡으면 context switching을 막아서 critical section 보호
  • Problem
  • greedy한 program이 cpu를 독점할 수 있음
  • multiprocessors 에서는 작동 x => interrupt를 막는건, 해당 core(cpu)에서만 막는거라서, 다른 core로 가면 막을 수 x
  • cost가 많이 든다 => slowly

 

 

Why hardware support needed?

  • 26.  Concurrency 할 때 봄
  • First attempt : flag 사용 
  • 중간에 interrupt가 오면 둘다 자기가 lock을 잡고 있다고 생각하는 문제 발생
  • spin waiting 문제 

==> test and set instruction 사용

 

 

 

Test And Set (Atomic Exchange)

int TestAndSet(int *ptr, int new){
    int old = *ptr;  // old value에 *ptr(flag)을 저장
    *ptr = new;  // *ptr(flag)에 new 값 저장
    return old; // old value 반환
}
  • 결론적으로 old value 반환 == flag에 담긴 값 반환 (flag가 0이면 0 반환, 1이면 1 반환)
  • 이런 Test and Set이라는 hardware적 명령어가 1개 있는거(위는 c코드지만 진짜 c코드는 아님 그냥 예시)
  • First attempt 때, interrupt가 중간에 오는 문제를, 이러한 hardware 명령어 1개를 사용하게 되면, 이 instruction이 다 끝날 때까지 interrupt를 못받음(만약 온다면 반려 후, 이 instruction이 끝난 후 실행)
  • 즉, 중간에 interrupt가 와도 문제 x ==> performed atomically

 

 

A Simple Spin lock using test-and-set

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *lock){
	lock->flag = 0;
}

void lock(lock_t *lock){
	while(TestAndSet(&lock->flag, 1) == 1)  // 1이면 대기
    	;  // spin - wait
}

void unlock(lock_t *lock){
	lock->flag = 0;  //unlock 후 다시 0으로 만들어서 대기 풀어줌
}
  • core 0번과 core 1번에서 T-A-S를 동시 수행 한다고 해도, hardware에서 동시 실행 안되게 직렬적으로 만들어줌
  • NOTE : single processor 에서 맞게 작동하려면 preemptive scheduler 여야 함
  • => process A가 critical section 수행 중 yield()를 호출하면, process B가 수행 되는데, 이 때 lock에 대한 제어권은 A가 계속 가지고 있기 때문에, B는 수행이 안되고 flag 1 에서 무한 loop가 돌게 됨 
  • => 즉 OS가 다시 제어권을 잡을 수 없기 때문에, preemptive한 scheduler 여야 하는 것

 

 

Evaluating Spin Locks

1. Correctness : yes 

  • critical section을 보호할 수 있음

2. Fairness : no

  • 어떤 fairness도 보장하지 않음

3. Performance : 해결 x

 

 

 

Fetch-And-Add(Hardware 명령어)

int FetchAndAdd(int *ptr){
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

 

 

 

Ticket Lock

  • fetch-and-add를 이용해서 만든 lock
  • 도착한 순서대로 실행되는 것을 fair하다고 했을 때, 이 lock은 fairness 하다고 말 할 수 있음
typedef sturct __lock_t{
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock){
    lock->ticket = 0;
    lock->turn = 0;
}

void lock(lock_t *lock){
    int myturn = FetchAndAdd(&lock->ticket);
    // myturn에 old value, ticket은 + 1 됨
    while(lock->turn != myturn)
    	;  //spin
}

void unlock(lock_t *lock){
	FetchAndAdd(&lock->turn);
}
  • 처음에 ticket이랑 turn 전부 0으로 초기화
  • 처음에 lock 부르면 turn = 0, ticket = 1 => 이 thread가  unlock 할 때 turn + 1 됨
  • 다음 thread가 lock을 부르면 turn = 1, ticket = 2 를 받음
  • 처음 thread unlock을 해서 turn 이 1이 될 때까지 두번째 thread는 대기, 1되면 lock 잡음 
  • 이런 식으로 흘러나간다. ==> 순서대로 실행 될 수밖에 없음

 

 

So Much Spinning

  • Correctness와 fairness는 해결이 됐지만 performance는 여전히 spinning 문제 때문에 안좋다

==> Spinning을 피하려면 OS의 도움을 받아야함

 

** hardware의 도움을 받아서 mutual exclusion 과 fairness 문제 해결, 해결되지 않는 performance 문제를 OS 도움을 받아서 해결하겠다...........

 

 

 

 

A Simple Approach : Just Yield

void lock(lock_t *lock){
	while(TestAndSet(&lock->flag, 1) == 1) 
		yield();  // give up the CPU
}

 

  •  spinning에 들어가면 yield()를 불러서 cpu를 다른 thread에 넘겨줌
  • yield()를 부른 thread는 run queue의 맨 뒤로 들어가서 대기 

==> yield() 하면서 context switch 하는 cost와 starvation 문제가 여전히 존재 

 

 

 

Using Queues : Sleeping Instead of Spinning

  • 위의 문제를 해결하기 위해 도입 
  • park() : sleep 과 비슷함, 스스로 잠에 든다
  • unpark(threadID) : wake up과 비슷, 남이 나를 깨워줌
typedef struct __lock_t{
    int flag;
    int guard;
    queue_t *q;
} lock_t;

void lock_init(lock_t *m){
    m->flag = 0;
    m->guard = 0;
    queue_init(m->q);
}

void lock(lock_t *m){
    while(TestAndSet(&m->guard, 1) == 1)
    	; // queue에 대한 lock을 먼저얻음
        // queue를 조작하는 시간은 짧으므로 spinning 문제 해결 가능
    if(m->flag == 0){ 
    // 위에서 이미 guard로 lock을 잡았기 때문에, 여기선 T-A-S 쓸 필요 x
    	m->flag = 1;  // critical section lock 얻고
        m->guard = 0;  // queue에 대한 lock은 놔줌
    }
    else{  // queue에 대한 lock은 잡았는데, critical section을 다른 thread가 쓰고 있음
    	queue_add(m->q, gettid());  // queue에 내 tid 추가
        m->guard = 0;  // 이미 id 넣었으니 더이상 lock 필요 x => 놔줌
        park(); // 잠든다
    }
}

void unlock(lock_t *m){
    while(TestAndSet(&m->guard, 1) == 1)
    	;  // unlock을 하면 queue에서 다른 thread 같이 깨워줘야 돼서 , queue를 수정할 수 있을 때만 진행
    if(queue_empty(m->q)) // queue에 대기 중인 thread가 없으면
    	m->flag = 0; // lock 바로 놔줌
    else
    	unpark(queue_remove(m->q)); // queue에서 지우고 첫번째 thread 꺼내줌 
        // 여기서 나온 thread는 바로 critical section 수행 가능
        // 왜냐면 flag를 0으로 만들지 않았기 때문에 그냥 계속 flag는 1로 유지
        //(뒤에 대기 중인 애가 없을 때까지)
    m->guard = 0; // queue lock을 놓음 
}
  • flag => critical section의 lock
  • guard => queue의 lock