[xv6] Sleeplock

글의 참고

- https://github.com/mit-pdos/xv6-public/tree/master

---

글의 전제

- 밑줄로 작성된 글은 강조 표시를 의미한다.

- 그림 출처는 항시 그림 아래에 표시했다.

---

글의 내용

: 이 글에서는 `xv6`의 `sleeplock`에 대해 설명하려고 한다. `xv6`에서는 이미 `spinlock`이 존재하는데, `sleeplock`을 추가로 구현한 이유가 뭘까? 파일 시스템 관련 작업들은 디스크에 액세스해야 하기 때문에 시간이 많이 필요하게 된다. 예를 들어, A라는 프로세스가 메모리에 있는 1MB를 디스크에 써야한다고 가정한다. 이럴 경우, 메모리에 있는 내용을 디스크에 쓰는 동안에는 해당 메모리 영역에 다른 WRITE 작업들은 막아야 한다. 즉, A를 제외한 다른 프로세스들이 해당 메모리 영역에 접근하는 것을 막아야 한다. 

 

: 그런데, 이 상황에서 `SPINLOCK`을 사용하게되면, 프로세스들은 CPU를 양보하지 않고, A 프로세스가 `LOCK`을 반납하기만을 그 자리에서 계속 기다릴 것이다. 이럴 경우, 아무일도 하지 않고 계속 기다리기만 하는 상황이니 CPU를 낭비하는 꼴이 된다. 그래서 `SLEEPLOCK`은 `SPINLOCK` 과는 다르게, LOCK을 기다리지 않고, 프로세서의 소유권을 반납한다. 아래의 코드를 보자.

// sleeplock.c // Sleeping locks #include "types.h" #include "defs.h" #include "param.h" #include "x86.h" #include "memlayout.h" #include "mmu.h" #include "proc.h" #include "spinlock.h" #include "sleeplock.h" void initsleeplock(struct sleeplock *lk, char *name) {   initlock(&lk->lk, "sleep lock");   lk->name = name;   lk->locked = 0;   lk->pid = 0; } void acquiresleep(struct sleeplock *lk) {   acquire(&lk->lk);   while (lk->locked) {     sleep(lk, &lk->lk);   }   lk->locked = 1;   lk->pid = myproc()->pid;   release(&lk->lk); } void releasesleep(struct sleeplock *lk) {   acquire(&lk->lk);   lk->locked = 0;   lk->pid = 0;   wakeup(lk);   release(&lk->lk); } int holdingsleep(struct sleeplock *lk) {   int r;      acquire(&lk->lk);   r = lk->locked && (lk->pid == myproc()->pid);   release(&lk->lk);   return r; }

: 먼저, `acquresleep` 함수를 분석해본다. 이 함수에 제일 처음 들어온 프로세스는 `lk->locked = 1`을 통해서 다른 프로세스가 자신에 작업을 방해하지 못하도록 한다. 예를 들어, A와 B 프로세스가 존재한다고 가정하자. A 프로세스가 먼저 `123` 이라는 `SLEEPLOCK`을 들고 `acquresleep` 함수를 호출했다. 그렇면, A 프로세스는 `123` 슬립-락에 `lk->locked = 1`을 설정한다. 이로써, A 프로세스가 `123` 슬립-락의 소유권을 획득하게 됬다. A 프로세스가 열심히 디스크에 뭔가를 쓰고 있던 도중에 B 프로세스가 `123` 슬립-락을 획득하기 `acquresleep` 함수를 호출했다. 그런데, 이미 A 프로세스가 `123` 슬립-락에 대한 소유권을 가지고 있기 때문에, B 프로세스는 `while(lk->locked) { sleep(lk, &lk->lk); }` 에 진입하게 된다. 즉, B 프로세스는 주구장창 `123` 슬립-락을 기다리는 것이 아니라, 다른 프로세스에게 잠깐 CPU를 양보했다가(`sleep`), `123` 슬립-락에 소유권에 풀리면(`releasesleep`), 그 때 다시 깨어나서(`wakeup`) 다른 프로세스들과 소유권 싸움을 하게 된다. 

 

: 그런데, B 프로세스가 `acquresleep`에 진입할 때 슬립-락을 보호하기 위해 `acquire` 함수를 호출한다. 문제는 `acquire` 함수가 인터럽트를 비활성화시킨다는 것이다. 이게 왜 문제일까? `xv6`에서 언급되는 내용으로 정리하면, 디스크 관련 작업들은 대게 디스크 컨트롤러가 CPU의 요청을 완료하면, 인터럽트를 통해 완료 메시지를 보낸다. 그런데, 인터럽트가 비활성화되면 디스크 작업이 완료 되었는지 알 수가 없다. 그러면, A 프로세스는 `123` 슬립-락에 대한 소유권을 계속 가지게 되고, B 프로세스는 영원히 잠만 자게되는 꼴이 된다. 디스크 작업 완료 시, 인터럽트를 받지 말고 폴링으로 확인하면 안되나? 당연히 된다. 그러나, 디스크와 같이 상대적으로 오래 걸리는 작업을 폴링하게 되면 CPU와 같이 속도가 빠르고 중요한 리소스들이 낭비가 되는 꼴이다. 그래서, 속도가 느린 작업들은 거의 무조건 인터럽트로 완료 처리를 받는 것이 현대 OS에서는 정석이다.

 

: 본론으로 돌아와서, B 프로세스가 `123` 슬립-락에 대해 `acquire` 함수에서 인터럽트를 비활성화하는데, 어떻게 해야 할까? 걱정할 필요없다. `sleep` 함수에 해당 문제를 해결해준다.

// proc.c .... .... // Atomically release lock and sleep on chan. // Reacquires lock when awakened. void sleep(void *chan, struct spinlock *lk) {   struct proc *p = myproc();      if(p == 0)     panic("sleep");   if(lk == 0)     panic("sleep without lk");   // Must acquire ptable.lock in order to   // change p->state and then call sched.   // Once we hold ptable.lock, we can be   // guaranteed that we won't miss any wakeup   // (wakeup runs with ptable.lock locked),   // so it's okay to release lk.   if(lk != &ptable.lock){  //DOC: sleeplock0     acquire(&ptable.lock);  //DOC: sleeplock1     release(lk);   }   // Go to sleep.   p->chan = chan;   p->state = SLEEPING;   sched();   // Tidy up.   p->chan = 0;   // Reacquire original lock.   if(lk != &ptable.lock){  //DOC: sleeplock2     release(&ptable.lock);     acquire(lk);   } }

: 이 `sleep` 함수가 `acquiresleep` 함수에서 호출되었다는 전제로 분석한다. `sleep` 함수에 두 번째 전달인자를 보면, 위에서 얘기했던 예시를 연속해서 얘기하면, `123` 슬립-락의 `SPINLOCK`이 `sleep` 함수로 전달된다. 그리고 `xv6`는 lk가 `ptable(process table)`이 아니라면, 전달받은 lk를 해제한다. 즉, `release` 함수를 호출한다. 앞에서 얘기했던 부분을 다시 상기해보자. B 프로세스가 `123` 슬립-락 소유권을 얻기 위해, `acquiresleep` 함수를 호출했다. 그런데, `acquire` 호출하기 때문에 인터럽트가 비활성화 된다고 했다. 이 상태가 지속되면 A 프로세스는 `123` 슬립-락 소유권을 못 놓아주게 된다. 그러나, B 프로세스가 `sleep` 함수로 진입하면서 `release` 함수를 통해 `123` 슬립-락의 인터럽트를 다시 활성화한다. 

 

: A 프로세스는 디스크 작업이 모두 완료되면, `releasesleep` 함수를 호출해서 `123` 슬립-락의 소유권을 반납(`lk->locked = 0`)하게 된다. 그리고, `123` 슬립-락의 소유권을 갖지 못해서 잠자고 있던 모든 프로세스들을 깨운다(`wakeup`).

 

: `holdingsleep` 함수는 락을 검사하는 함수다. 락을 얻거나 푸는 함수가 아니다. 즉, 작업이 모두 마무리 됬는데도, 슬립-락에 대한 소유권을 풀지 않고 계속 가지고 있는 프로세스를 검사하는 함수가 `holdingsleep` 함수다. 예를 들어, 아래의 코드를 보자.

// sleeplock.c .... .... int holdingsleep(struct sleeplock *lk) {   int r;      acquire(&lk->lk);   r = lk->locked && (lk->pid == myproc()->pid);   release(&lk->lk);   return r; } .... .... #################################################################################################### // bio.c .... .... // Write b's contents to disk.  Must be locked. void bwrite(struct buf *b) {   if(!holdingsleep(&b->lock))     panic("bwrite");   b->flags |= B_DIRTY;   iderw(b); }

: 2개의 프로세서가 동작하는 시스템에서 `holdingsleep` 함수는 중복되는 프로세스만 검사할 뿐이다. 위의 예시를 기준으로 보면, A 프로세서와 B 프로세서가 있다고 치자. A 프로세서에서 `1` 이라는 프로세스가 돌고, B 프로세서에서 `2`라는 프로세스가 돌고 있다고 치자. 2개의 프로세서가 동시에 `bwrite` 함수를 호출했다. `holdingsleep` 함수에서 지금 이 동시성 문제를 해결해줄까? 아니다. 그냥 보내준다. 만약, A 프로세서와 B 프로세서에서 동작하는 프로세스 동일한 프로세스라면,  `holdingsleep` 함수에서 이러한 부분을 걸러준다. 그러나, 서로 다른 프로세서에서 동일한 프로세스가 동작을 할 수는 없다.

 

: `holdingsleep` 함수에서 `lk->pid == myproc()->pid` 조건은 깊이 생각해볼 조건이다. 왜냐면, `bwrite` 함수에서도 볼 수 있다시피, 대개 `holdingsleep` 함수는 `if(!holdingsleep(&b->lock)) panic("bwrite")` 함수와 같은 형태로 자주 쓰인다. 즉, `0`을 반환하면, `PANIC`으로 시스템이 무한 루프에서 대기하게 된다. 저 조건은 만약, `holdingsleep` 함수를 호출한 프로세스가 슬립-락을 소유한 프로세스가 아니라면, 시스템 에러라는 뜻이다. 그렇다면, `xv6` 코드는 슬립-락을 잡은 프로세스만이 무조건 `holdingsleep` 함수를 호출하도록 구현되어 있을까?

 

: `acquresleep` 함수가 호출되면, `123` 슬립-락을 소유한 프로세스를 제외한 프로세스가 `123` 슬립-락을 소유하려고 하면, `sleep`에 빠지게 된다. 즉, `123` 슬립-락을 소유한 프로세스만이 해당 범위내에서 자유롭게 활동할 수 가 있다. 그런데, `holdingsleep` 함수가 필요한 이유가 뭘까? `Lock Ordering` 때문이다. 예를 들어, 아래의 코드를 보자.

.... .... // Lock the given inode. // Reads the inode from disk if necessary. void ilock(struct inode *ip) {   struct buf *bp;   struct dinode *dip;   if(ip == 0 || ip->ref < 1)     panic("ilock");   acquiresleep(&ip->lock);   if(ip->valid == 0){     bp = bread(ip->dev, IBLOCK(ip->inum, sb));     dip = (struct dinode*)bp->data + ip->inum%IPB;     ip->type = dip->type;     ip->major = dip->major;     ip->minor = dip->minor;     ip->nlink = dip->nlink;     ip->size = dip->size;     memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));     brelse(bp);     ip->valid = 1;     if(ip->type == 0)       panic("ilock: no type");   } } // Unlock the given inode. void iunlock(struct inode *ip) {   if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)     panic("iunlock");   releasesleep(&ip->lock); } .... ....

: `acquiresleep(&ip->lock)`와 `releasesleep(&ip->lock)`가 한 트랜잭션안에 수행되지 못 할 경우, 필수적으로 그 사이에  `holdingsleep` 함수를 작성해야 한다. 위에서 `iunlock` 함수는 앞에서 `acquiresleep(&ip->lock)` 함수가 호출이 되었다는 것을 전제로 하고 있다. 만약, 앞에서 `acquiresleep(&ip->lock)` 함수가 호출되지 않았다면, `lk->locked && (lk->pid == myproc()->pid)` 조건에서 앞 조건인 `lk->locked` 에서 0을 반환해서 `PANIC`에 빠질 것이다. 이러한 문제는 `Caller`와 `Callee` 사이에 지켜야 하는 룰과 같다. 예를 들어, `나를 호출하려면, LOCK을 걸고 호출해! 나는 락을 사용하지 않을테니!" 와 같은 느낌인 것이다. 이런 규칙이 필요한 이유는 데드락을 피하기 위해서다.

 

: `lk->locked && (lk->pid == myproc()->pid)` 조건에서 두 번째 조건에 걸리는 경우는 없을까? 현재 `xv6`가 구현되어 있는 소스 코드에서는 잘 보이지 않는다. 왜냐면, `lk->pid == myproc()->pid` 조건에 걸리려면, `acquiresleep(&ip->lock)` 함수를 호출하지 않아야 하기 때문이다. 즉, `123` 슬립-락은 이미 A 프로세스가 점유하고 있는데, B 프로세스가 `123` 슬립-락을 얻기 위해 `acquiresleep(&ip->lock)` 함수를 호출하면 당연히 `sleep`에 들어가게 된다. 그러면, `acquiresleep(&ip->lock)` 함수를 호출하지 않고, `holdingsleep` 함수를 호출해야 하는데, 이건 현재 `xv6` 코드상 억지가 될 가능성이 높다.

 

:  `holdingsleep` 함수는 스핀-락의 `holding` 함수와 구조가 비슷하다. 구조적인 차이는 있지만, 큰 차이는 없다고 본다. 

`holdingsleep` :  프로세스 검사
`holding` : 프로세서 검사

 

: 이제부터는 내 개인적인 생각이다. 위의 2개의 함수의 차이는 아래와 같다. 

0" 범용성
1" 프로세서의 양도

: `acquire` 함수와 `acquiresleep` 함수의 용도 차이에서 온다고 볼 수 있다. 범용성 측면에서 보면, 예를 들어, `xv6`에서 스핀-락은 거의 모든 곳에 사용된다. 그러나 슬립-락은 파일 시스템에 한정되어 사용된다. 그래서 스핀-락은 프로세스가 할당되지 않은 곳에서도 사용되야 하기 때문에 프로세스 검사가 아닌, 프로세서를 검사하는 것이다. 프로세서는 컴퓨터가 부팅시점부터 활성화되는 물리적인 객체다. 그러나, 프로세스는 프로세서가 생성되는 논리적인 객체이기 때문에, 프로세서보다는 상대적으로 뒤늦게 나타난다.

 

: 스핀-락은 프로세서를 양보하지 않는다. 즉, 계속 대기하면서 `LOCK`이 풀릴 때 까지, 프로세서를 독점한다. 그러나, 슬립-락은 프로세서를 다른 프로세스에게 양보하고, 자신은 잠이 든다. 즉, 스핀-락은 프로세서와 프로세스의 1:1 매핑이 성립되지만, 슬립-락에서는 프로세서와 프로세스의 1:1 대칭이 성립이 되지 않는다.

 

: 이상 `holdingsleep` 함수와 `holding` 함수는 왜 다른가에 대한 내 개인적인 생각이었다.