5장. Process Synchronization(1) << 앞부분 링크

5. Spinlock

semaphore를 살짝 변형한 spinlock을 활용한 기법이다.

Spinlock

• 정의

  • Integer variable
  • P(), V(), initialization operation만 접근할 수 있다.
  • Semaphore과 다르게 sleep Q가 없다. busy waiting을 하는 기법이다.P() : S>0 이면 S 1감소 후 나감, S가 0보다 작거나 같으면 while loop을 돈다.
    V() : S값을 1 증가시킨다.

• Spinlock을 이용한 mutual exclusion
  Pi가 먼저 P(active)를 실행하는 경우 active가 0보다 크니 1을 감소시키고 CS에 진입한다. 프로세스의 P(active)가 0이면 busy waiting을 하는 상태에 있는다.나올 때는 V(active)로 S를 1 증가시킨다.

  이런 방법이 있으면 왜 semaphore를 사용해서 열심히 busy waiting을 하지 않도록 했는지에 대한 의문이 든다. busy waiting의 단점은 하는 일 없이 기다리면서 CPU 자원을 소모하고 있다는 점이다. 그렇다면 busy waiting을 억제했을 때의 단점을 뭘까?
  busy waiting이 발생하려하면 sleep 시키는 semaphore 기법은 자연스럽게 context switching이 발생하게 된다. context switching을 하기 위해서는 kernel의 개입이 필수적이고 context switching하는 과정에서 overhead를 갖는다는 단점이 있는것이다.
  각각 장단점이 있기 때문에 상황에 알맞게 선택하면 되는데, CPU가 한 개인 single processor 환경이라면 busy waiting을 해도 어짜피 CPU가 빌 때까지 기다려야하기 때문에 spinlock을 사용할 이유가 없고, semaphore을 사용해 context switching을 하는 편이 유리하다. 하지만 multicore 환경일 경우 busy waiting loop를 필요이상으로 오래 돌지 않고 다른 core에 할당받을 수 있기 때문에 context switching을 하는 것보다 splinlock이 더 좋을 수도 있다.

• Spinlock의 특징

  • Busy waiting을 하기 때문에 context switching을 하지 않는다.
  • lock을 아주 짧은 시간동안 한다는 전제면 spinlock이 좋다.(Multicore환경)
  • Multiprocessor system에서 활용된다.
  • Linux, Solaris2, Windows 2000

6.Ticket Lock (Eventcount/Sequencer)

semaphore은 wakeup 스케줄링을 하지 않기 때문에 starvation 문제가 발생했다. Ticket lock에서는 wakeup 스케줄링을 하고, sleep Q도 사용한다.
은행에 가서 번호표를 뽑고 창구에 번호가 뜨면 가는것과 비슷한 기법이다. Semaphore은 창구에 번호가 뜨면 랜덤으로 사람을 받는 기법이다.

Definitions for E/S

• Sequencer : 변수1
  • Integer variable
  • 0으로 자동으로 초기화되어있고, 단조증가한다.
  • event order를 기록한다.
  • ticket() operation을 통해서만 접근 가능하다.
    • ticket(S) : S는 sequencer variable
    • ticket() operation이 몇 번 call 됐는지 return한다.
    • Indivisible operation : 중간에 개입 불가능
• Eventcount : 변수2
  • Integer variable
  • 0으로 자동으로 초기화되어있고, 단조증가한다.
  • event가 발생한 횟수를 저장한다.
  • read(), advance(), await() operation으로만 접근 가능하다.

E/S의 Mutual exclusion

프로세스는 일단 ticket(S)를 통해 티켓부터 뽑는다. 자기가 받은 티켓 번호를 local variable v에 저장한다. await()로, eventcount값 (은행 창구에 떠있는 번호)가 받은 티켓번호보다 작으면 wait한다. 지금은 같으므로 CS에 진입한다. 나오면서 advance(E)를 통해 eventcount값을 1 증가시키고 증가된 E의 값을 기다리고 있는 프로세스를 wakeup시킨다.

더 자세하게 살펴보자.
티켓받은 번호대로 FIFO wakeup scheduling을 한다.

• Producer-consumer problem
  Producer의 await(Out, t-N+1)은 Out < t-N+1 이면 sleep하라는 명령이다. 식을 조금 수정하면 t-Out > N-1이 된다. t는 produce한 총 횟수, out은 consume한 총 횟수이기 때문에 좌항은 데이터를 가지고있는 버퍼의 개수가 된다. 우항은 그대로 N-1 이고 t-Out > N-1의 의미는 데이터를 가지고있는 버퍼의 개수가 N이상 즉 full로 차있으면이 된다.
  Consumer의 await(In, u+1) 은 In-u < 1이면 sleep하라는 명령이다. In은 데이터가 들어온 횟수, u는 데이터가 나간 횟수다. 좌항은 데이터가 있는 버퍼의 개수고 그게 1보다 작다는건 버퍼가 비어있다는 상태이다.

E/S의 특징

• prevent busy waiting
• process를 wakeup할 때 FIFO (ticket 받은 순서대로) scheduling한다.
• No starvation
• Inefficiency : 철학자 문제를 비교해보면 된다.

7.Case Studies

Solaris

• Adaptive mutexes (mutex는 binary semaphore로 생각하면 편하다)

  • On multiprocessor systems

    • 다른 CPU에 있는 running 프로세스에 의해 lock이 걸렸을 경우 : busy waiting한다.(다른 CPU의 프로세스가 곧 빠져나갈거라는 기대)
    • 다른 CPU에 있는 running하지않는 프로세스에 의해 lock이 걸렸을 경우 : sleep한다.
    • 다른 CPU의 상태를 보고 결정하기 때문에 adaptive mutex인 것임.

  • On uniprocesor systems

    • lock을 만나면 (진행할 수 없는 상황을 만나면) sleep 한다.

  • critical section의 코드가 짧으면 adaptive mutex를 쓰지만 코드가 길면 semaphore나 condition variable을 사용한다.

• reader-writer locks 별도로 제공

  • 어떤 데이터가 read-only 형태로 더 많이 접근된다면 read는 동시에 진입할 수 있기 때문에read-writer lock을 쓰는게 훨씬 효과적이다.

• Turnstile : Solaris가 사용하는 자료구조/ queue structure.

• kernel이 사용하는 locking mechanism을 user-level에서 사용할 수 있도록 한다.

Windows XP

• Kernel이 사용하는 Mechanism
  • uniprocessor system : interrupt masking 사용 (interrupt를 enable/disable)
  • multiprocessor system : spinlock 사용
• Kernel 바깥쪽 (Application)
  • Dispatcher object : mutexex, semaphore, events, timers

Linux

• Kernel의 locking에 사용되는 mechanism

  • Spinlock, semaphores, ticket locks, reader-writer locks
  • SMP machines ( multi processor )
    • spinlock ( short duration )
    • semaphore ( long period locks )
  • Uniprocessor machines
    enabling/disabling of kernel preemptions (preempt_disable(), preempt_enable() 사용)
    

• 어떤 프로세스가 kernel에 들어가서 lock을 걸면 preemption 할 수 없다.

• Pthreads이 사용하는 표준 mechanism

  • mutex lock
  • conditional variables
  • reader-writer locks
  • semaphores
  • spinlocks