Operating System Ch13: Lock

Layfort·2023년 11월 9일

Operating System lock 락 운영체제

System Programming

목록 보기

4/5

Lock

Prevent global(shared) data corruption

1. Why we need?

기본적으로 thread는 process enviorment를 공유한다.
- Virtual address space
  - 단 stack(local variable)은 여기서 제외된다.(stack pointer는 thread마다 개별적으로 동작하므로...)
  - 즉 global variable(.data/.bss), dynamic allocated objects(heap)이 공유된다...
- File descriptor table
그외에도 mmap으로 shared memory, shmem을 설정하는 경우도 있고... 뭐 일단 그렇다.

1-2. Synchronization Problem

이런 shared resource는 non-deterministic result를 낳는다.
- 이를 race condition이라고 한다.
- 이런 버그를 Heisenbugs라고 부르기도 한다.
결론은 뭐냐, concurrency를 제약해야한다는 것이다.
- shared resource를 조작하는 사람은 단 한명이어야 한다는 것이다...
- scheduling은 너 맘대로 할 수 있는게 아니다 이말이야

1-3. Critical Section

Shared resource에 접근하는 code sectio을 critical section이라고 한다.
Mutual Exclusion
- 위에서 말한 것처럼... 우리는 shared resource에는 한번에 한thread만 접근을 허용해야 한다는 것.
- Shared resource에 다른 thread가 접근하고 있으면... 나머지는 block해야 한다.(접근 거부!)

2. Lock

Mutual exclusion을 제공하기 위한 장치로, 다른 thread의 data access를 막는 역할을 한다.
- acquire() : lock을 잡고싶어요... 잡을 때까지 기다린다.
- release() : 잡았던 lock을 풀어준다.(그리고 기다리는 다른 thread를 깨우기도 한다.(wake))

2-1. Using lock

int 
withdraw(int account, int amount) 
{
	acquire(lock);
#pragma region critical_section
    balance = get_balance(account);
	balance = balance - amount;
    put_balance(account, balance);
#pragma endregion critical_section
	release(lock);
    return balance;
}

acquire와 release로 critical section을 가둔다.

2-2. Requirment for Locks

Mutual exclusion : only one thread access critical section → Essential
Progress(deadlock-free) : critical must executed if waiter is exist → Essential
Bounded waiting(starvation-free) :
Fairness : fair chance
Performance : decreasing a lot of overhead

3. Implementing Lock

3-1. Initial Attempt

struct lock { int held = 0; }

void acquire(struct lock *l) 
{
  while (l->held); 	// loop until when held = 0(busy waiting - not sleep)
  	l->held = 1;	// shutdown held
}

void release(struct lock *l) 
{
  l->held = 0;		// release held to accept another one
}

but, there is big problem in this code...
- lock it self is critical section(use global variablestruct lock for implement lock

3-2. Software-only Algorithm

2개의 thread만이 존재한다고 가정하자...

int interested[2];				// 각 task가 현재 shared resource에 접근하고자 하는가?

void acquire(int process) 
{								
  int other = 1 – process;
  interested[process] = TRUE;	// 일단 내가 shared resource에 관심이 있다는 표시를 한다.
  while (interested[other]);	// 다른 task에서 관심이 없으면 진행한다.(아니면 무한 loop - busy waiting)
}

void release(int process) 
{
  interested[process] = FALSE;	// 끝났으면 다른 쪽에서 진행이 가능하도록 interest를 풀어준다.
}

될거같지만 안된다.
- if) interested[process] = TRUE;에서 기가막힌 이유로 scheduling되서 다른 쪽으로 간다면?
- 다른 task에서도 interested[process] = TRUE가 되고, 아무도 들어가지 않았지만 서로가 서로를 막아버리는 기가막힌 상황(progress violation and maybe dead lock?)

3-3. Patterson's Algorithm

위의 Software-only Algorithm의 개선판

int volatile turn;
int interested[2];

void acquire(int process) 
{
  int other = 1 – process;
  interested[process] = TRUE;
#pragma region added
  turn = other;				// 어떤 역할을 하는가?
#pragma endregion added
  while (interested[other] && turn == other);
}

void release(int process) 
{
  interested[process] = FALSE;
}

저 turn의 목적은 무엇인가?
- 위에서 언급했던 그 상황을 다시 생각해보자
- 우리가 문제로 지적했던 점은 2개의 task가 동시에 interested[process] = TRUE 되는 상황
- 여기에 turn == other을 추가했는데... 이 경우 loop 조건에 turn이 들어갔기 때문에, 2개의 thread가 동시에 loop를 도는 것은 불가능하다.(turn이 어떻게든지 결국 1개의 값으로 확정 될것이기 때문에)
- 자세히 설명하자면, 2개의 interest가 동시에 TRUE라고 하더라도 turn은 1 아니면 0중 하나니까... 현재 turn으로 설정된 task가 loop안으로 들어갈 수 있는 것.
다만 여전히 2개의 thread가 존재하는 경우에만 적용가능

3-4. Bakery Algorithm

Multi process lock algorithm

int number[N];		// 대기열 등록이라고 생각하면됨 현재 N번째 task가 뽑은 번호표 기록
int choosing[N];	// interest의 Multi process 판

#define EARLIER(a,b) \\
  ((number[a] < number[b]) || \\
  (number[a] == number[b] && \\
  (a) < (b))) 				// 먼저 enqueue한 task를 찾는다? 아마

int Findmax () 				// 제일 큰 번호 찾기(즉 새로운 번호표를 뽑는거라고 생각하자)
{
#pragma region CS
  int i;
  int max = number[0];
  
  for (i = 1; i < N; i++)
    if (number[i] > max)
    	max = number[i];
#pragma endregion CS

  return max;
}

void acquire (int me) 
{
  int other;
  choosing[me] = TRUE;			// 현재 번호표 뽑는중
  number[me] = Findmax() + 1;	// 번호표 뽑기 실행
  choosing[me] = FALSE;			// 번호표 뽑았음(등록 완료)
  
  for (other=0; other<N; other++)
  {
    while (choosing[other]); 	// 누가 번호표를 뽑지는 않는지?(왜나면 findmax는 CS를 포함하니까... number를 건드리면 안되거든요
    while (number[other] && EARLIER(other, me)); // 나보다 빠른 번호표가 있으면, 무한 loop
  }
}

void release (int me) 
{
  number[me] = 0;
}

좋아보이지만, Findmax가 CS에 속하는기 때문에, 서로 다른 task에서 findmax를 동시에 실행하면 번호표가 겹치는 경우가 있을 수 있다.

3-5. Test-And-Set

여기서부터는 Hardware support가 들어간다. (Insturction의 atomicity를 보장하기 위해서)

int TestAndSet(int *v, int new) {
  int old = *v;
  *v = new;
  return old;
}

위의 과정이 atomic하게 수행된다. 즉, 새로운 것을 쓰고 기존 것을 반환하는 과정 전체가 하나의 Instruction으로서 수행된다.(atomic exchange operation)
이게 그래서 lock을 구현하는데 어떤 도움을 주는가?

struct lock { int held = 0; }

void acquire(struct lock *l) 
{
  while (TestAndSet(&l->held, 1));
}

void release(struct lock *l) 
{
  l->held = 0;
}

While은 무엇을 하는가?
- 계속 Test-And-Set을 수행하면서(exchange를 atomic하게 수행), 기존에 저장되어 있던 값이 0이었는지 검사한다.
- 0이었다는 이야기는 lock이 잡혀있지 않는다는 이야기이므로...
- Test-And-Set 과정이 atomic하게 수행되기 때문에, CS걱정을 하지 않아도 된다는 장점이 있다.

3-5-1. BoundedWaiting Example

struct lock { int value = 0; }
int waiting[N];

void acquire(struct lock *l, int me)
{
  int key;
  
  waiting[me] = 1;					
  key = 1;							// lock checking용 변수
  while (waiting[me] && key)		// waiting을 합니다. 계속
  	key = TestAndSet(&l->value);
  waiting[me] = 0;
}

void release(struct lock *l, int me)
{
  int next = (me + 1) % N;
  
  while ((next != me) && !waiting[next])
  	next = (next + 1) % N;			// 다음으로 락이 잡혀있는 찬구를 찾는다.
  
  if (next == me)					
  	l->value = 0;					// 나만 사용중이면 그냥 락을 푼다.
  else
  	waiting[next] = 0;				// 락을 푸는게 아니라 다음 task가 락 안으로 들어오도록 한다.(일종의 bypass)
}

3-5-2.

3-6. Compare-And-Swap

Test-And-Set가 유사하긴 한데, 무작정 쓰는게 아니라 내가 target하는 값이 저장되어 있으면 store를 하고 아니면 store하지는 않는다.

int CompareAndSwap(int *v, int expected, int new) 
{
  int old = *v;
  if (old == expected)							// expect 값이 아니면 store는 안한다!
  	*v = new;
    
  return old;
}
void acquire(struct lock *l) 
{
	while (CompareAndSwap(&l->held, 0, 1));		// 0이 들어있으면 1을 쓴다...
}

3-7. LL & SC

나중에...

3-8. Fetch-And-Add

나중에...

3-9. Controlling Interrupts

아주 극단적인 방법이긴 한데... 정말 근원적인 부분을 차단해버리는 방법
race condition이 생기는 원인이 무엇인가? → interrupt에 의한 scheduling!
- 제거한다.

void acquire(struct lock *l) 
{
	cli(); // disable interrupts;
}

void release(struct lock *l) 
{
  sti(); // enable interrupts;
}

장점은...
1. 간단하다.
단점도 많다...
1. 유저 code에서는 못쓴다.(에초에 저건 interrupt disable 자체가 privileged operation이다.)
- 만일 이 operation을 user mode에서 사용할 수 있다면 당연하겠지만, hacking에 최우선 고려사항이 될 것이다.
1. 멀티 프로세스에서도 못쓴다.
2. CS가 길어지면, 진짜 난리난다.(중요한 interrupt이 전부 차단 되버릴 수 있다...)

4. Additional Information from Reading Assignemnt

4.1 Locking Strategies

Coarse-grained : 한개의 lock을 이용하여 여러 개의 critical section에 대해 동시에 제한을 거는 방법
Fine-grained : 각각의 shared data마다 다른 lock을 사용하여 보호하는 방법 → 당연히 이쪽이 효율이 더 좋음

4-2. Evaulation

Mutual Exclusion: 이건 그냥 MUST 당연히 되어야 한다. 이게 안되면 lock의 존재가치가 유명무실해진다...
Fairness: lock을 누가 잡는지를 결정할 수 있다면(구현에 따라서는 scheduler에 의해서 결정되는 경우도 있다. fair 하지는 않지만) 당연하겠지만 공평하게 부여해야한다. starvation이 일어날 수도 있으므로...
Performance: 원래는 multicore로 작동해야할 코드에 Bottle neck같은 것을 집어넣은 것이니 당연히 성능이 좋을 수가 없다. + lock을 얻고 푸는 overhead또한 고려해야 한다.

Layfort

물리와 컴퓨터

이전 포스트

System Programming 16. Interprocess Communication

다음 포스트

Operating System Ch13: Lock

System Programming

Lock

1. Why we need?

1-2. Synchronization Problem

1-3. Critical Section

2. Lock

2-1. Using lock

2-2. Requirment for Locks

3. Implementing Lock

3-1. Initial Attempt

3-2. Software-only Algorithm

3-3. Patterson's Algorithm

3-4. Bakery Algorithm

3-5. Test-And-Set

3-5-1. BoundedWaiting Example

3-5-2.

3-6. Compare-And-Swap

3-7. LL & SC

3-8. Fetch-And-Add

3-9. Controlling Interrupts

4. Additional Information from Reading Assignemnt

4.1 Locking Strategies

4-2. Evaulation

System Programming 16. Interprocess Communication

System Programming Lab 3. Shell Lab - 1

0개의 댓글

Operating System Ch13: Lock

System Programming

Lock

1. Why we need?

1-1. Sharing Resources

1-2. Synchronization Problem

1-3. Critical Section

2. Lock

2-1. Using lock

2-2. Requirment for Locks

3. Implementing Lock

3-1. Initial Attempt

3-2. Software-only Algorithm

3-3. Patterson's Algorithm

3-4. Bakery Algorithm

3-5. Test-And-Set

3-5-1. BoundedWaiting Example

3-5-2.

3-6. Compare-And-Swap

3-7. LL & SC

3-8. Fetch-And-Add

3-9. Controlling Interrupts

4. Additional Information from Reading Assignemnt

4.1 Locking Strategies

4-2. Evaulation

System Programming 16. Interprocess Communication

System Programming Lab 3. Shell Lab - 1

0개의 댓글