[리눅스 커널] Synchronization - tranditional locking

글의 참고

- https://www.cs.utexas.edu/~pingali/CS378/2015sp/lectures/Spinlocks%20and%20Read-Write%20Locks.htm

- https://kernelnewbies.org/SMPSynchronisation

- http://www.wowotech.net/kernel_synchronization/445.html

- https://community.arm.com/support-forums/f/architectures-and-processors-forum/4273/how-to-understand-armv8-sevl-instruction-in-spin-lock

- https://zenn.dev/junkawa/articles/fuchsia-zircon-spinlock-arm64

---

글의 전제

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

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

---

글의 내용

- Overview

" 이 글은 전통적인 동기화 메커니즘에 대한 `구현 방법` 에 대해 간단하게 알아본다. 디테일한 구현은 별도의 글로 다루도록 한다. 그리고, 주의할 점이 있다. 이 글은 각 동기화 메커니즘의 가장 기본적인 구현 방식에 대해 다룬다. 그렇기 때문에, 리눅스의 구현 방식과는 다룰 수 있다는 점을 알아두자. 이 글에서는 총 4개의 동기화 메커니즘에 대해 알아볼 것이다(참고로, 이 글은 각 동기화 메커니즘에 대한 개념에 대해서는 설명하지 않는다).

1. spinlock
2. semaphore
3. read-write lock
4. mutex

 

 

 

1. spinlock

" spinlock 은 리눅스에서 가장 쉽게 볼 수 있는 locking mechanism 으로 구현 방식이 상당히 단순하다. 예를 들어, process A 가 성공적으로 resource X 에 대한 lock 을 소유할 경우, process B 는 resource X 에 액세스할 수 없다. 그렇다면, lock 을 소유하지 못한 process 는 어떻게 되는걸까? spinlock 같은 경우는 resource X 의 lock 을 얻을 수 있을 때 까지 spin 하게 된다. 즉, process B 는 process A 가 resource X 를 release 할 때 까지, CPU 를 점유해서 무한 루프로 대기한다. 그리고, spinlock 은 sleep & context switch(scheduling) 이 없기 때문에 주로 interrupt context 와 궁합이 잘 맞는다.

 

" 그런데, 기본 spinlock 은 사실 좀 불공평하다. 예를 들어, process A 가 resource X 를 release 하면, 나머지 프로세스들은 resource X 를 점유하기 위해서 경쟁할 것이다. 여기서, process A 다음에 process B 가 대기하고 있다고 가정해보자. 1분 뒤에, process C 가 이 경쟁에 참여했다. 여기서, 순서대로 한다면 B 가 먼저 lock 을 소유하는 것이 맞지만, spinlock 은 그렇지 않다. 즉, 순서를 고려하지 않는다는 것이다. 그래서, 리눅스는 `queue` 개념이 접목된 spinlock 을 사용한다. 말 그대로 `first come, first out` 인 셈이다. 우리도 queue spinlock 을 구현해 볼 것이다. 기존 spinlock 은 이 글을 참고하자.

 

 

(1) implementation

" 리눅스에서 spinlock 은 next, owner 라는 2개의 count 를 가지고 있다. 2개의 count 는 초기값으로 0 으로 동일하고, 만약, process A 가 lock 을 소유할 경우, next count 가 `1` 증가하게 된다. 이 때, next count 와 owner count 가 달라진다. 이럴 경우, critical section 에 진입하지 못하게 된다. 즉, 문을 잠갔다고 보면 된다. 이제 process A 를 제외한 다른 프로세스들은 critical section 에 들어가기 위해서 순서대로 문앞에서 대기하게 된다.

 

" 3분 후, process A 가 unlock 했다. 이 시점에 owner count 가 `1` 증가하고, next == owner 가 된다. 2개의 count 가 같을 경우, 문이 열려있다는 뜻이된다. 즉, 다른 프로세스들이 critical section 에 진입이 가능해진다. 정리하면, 다음과 같다.

1. critical section 에 진입하면, next count 를 `1` 증가시킨다.
2. critical section 에 진입하면, owner count 를 `1` 증가시킨다.
3. next count == owner count 이면, critical section 에 아무도 없다는 뜻. 즉, unlock 상태.
4. next count != owner count 이면, critical section 에 누군가 있다는 뜻. 즉, lock 상태.

 

 

" 먼저, 자료 구조를 한 번 정의해보자. 조금 의아하다. owner 와 next 는 이해할 수 있겠는데, slock 은 뭘까? union 을 사용한 이유는 다음과 같다. 구체적인 사용 예시는 뒤에서 다시 설명한다.

- 대입 연산시, slock 을 대입함으로써, owner 와 next 를 모두 대입하는 효과. 즉, atomic operation 이 가능해짐.

// http://www.wowotech.net/kernel_synchronization/445.html
typedef struct {
	union {
		unsigned int slock;
		struct __raw_tickets {
			unsigned short owner;
			unsigned short next;
		} tickets;
	};
} arch_spinlock_t;

 

 

" spinlock 에서 lock 을 잠그는 함수는 arch_spin_lock() 이다.

// http://www.wowotech.net/kernel_synchronization/445.html
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
	arch_spinlock_t old_lock;
 
	old_lock.slock = lock->slock;                             // --- 1
	lock->tickets.next++;                                     // --- 2
	while (old_lock.tickets.next != old_lock.tickets.owner) { // --- 3
		wfe();                                                // --- 4
		old_lock.tickets.owner = lock->tickets.owner;         // --- 5
	}
}

1. `주소` 를 전달하는 것이 아니다. `값` 을 전달한다. 주소를 전달할 경우, 값을 공유하기 때문에 exclusive region 을 만들 수 가 없다. spinlock 에서 exclusive region 를 만들기 위한 기본 원칙은 값을 다르게 함으로써 spin 에 빠지게 하는 것이다. 아래 그림을 보면 이해가 될 것이다(old_lock.slock 과 lock.slock 은 주소가 서로 다르다). 여기서 `union` 으로 선언한 효과를 본다. 만약, union 이 아니었다면, next 와 owner 를 각각 대입 했을것이다(atomic 하지못하다).

2. 여기서 2 가지 개념을 알아야 한다.

1. next 값을 증가시킴으로써, exclusive region 을 생성. 즉, 다음에 액세스하는 프로세스들은 spin 하게 된다. 2. next 값을 순차적으로 증가시킴으로써 lock 을 FIFO 로 가질 수 있도록 한다.

3. spinlock 의 기본 원칙은 acquire 시에 next 증가, release 시에 owner 증가다. 이 말은 next 와 owner 가 같다면, 현재 lock 을 소유한 프로세스가 없다는 뜻이다. 그렇지 않다면, 다른 프로세스가 lock 을 소유하고 있다는 뜻이다.

4. arm 의 `wfe` 는 wakeup event 가 발생할 때 까지 sleep 하는 명령어다. 이걸 사용하는 이유는 일반적으로 CPU 가 무한 루프에서 대기하는 것은 전력 소비면에서 좋지 못하다. 그래서, 하드웨어 차원에서 SLEEP 을 지원해준다. 그게 바로, wfe 명령어다. wake-up 시그널은 `sev` 명령어를 통해서 받을 수 있다. 더 구체적인 내용은 이 글을 참고하자.

5. waiting process 는 주기적으로 자기 차례가 왔는지를 확인해야 한다.

 

 

" 위에 내용이 어려울 수 있다. 아래의 그림을 참고해서 값이 어떻게 변하는지를 확인해보자.

 

 

 

" release 는 상당히 심플하다. 한 번 생각해보자. queue 개념이 도입된 spinlock 은 lock 을 소유하면, next 가 1씩 증가한다. 그리고, lock 을 소유하기 위해서는 next 와 owner 가 같아야 한다. 그렇다면, release 시에 owner 를 증가시킴으로써, 다른 프로세스에게 lock 을 점유할 수 있도록 하면 된다.

// http://www.wowotech.net/kernel_synchronization/445.html
static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
	lock->tickets.owner++;
	sev();
}

 

 

" 그런데, 지역 변수(old_lock) 와 전역 변수(lock) 를 혼용해서 사용하다보니 약간 헷갈릴 수 있어서, 아래 그림으로 release 상황을 표현해봤다.

 

" 참고로, arm64 의 sev() 함수는 arm64 아키텍처 전용 명령어다. 해당 내용은 이 글을 참고하자.

 

 

 

2. semaphore

" 세마포어는 운영 체제 서적이라면 반드시 등장하는 동기화 메커니즘이다. semaphore 와 spinlock 의 가장 큰 차이점은 다음과 같다.

1. spinlock - lock 을 소유하지 못한 프로세스는 sleep 에 들어가지 못하고, lock 을 소유할 때 까지 CPU 를 점유한다.
2. semaphore - lock 을 소유하지 못한 프로세스는 sleep 에 들어간다.

 

 

(1) implementation

" semaphore 는 critical section 에 들어갈 수 있는 개수를 다수로 설정이 가능하다. 그렇기 때문에, 자료 구조를 만들 때도 전역적으로 critical section 의 상황을 나타내는 count 값이 필요하다. 그리고, FIFO 메커니즘으로 waiting process 를 실행시켜야 하므로, linked list 자료 구조를 사용한다.

 

 

" 아래에서 `struct semphore.count` 는 critical section 에 들어갈 수 있는 process 의 개수를 나타낸다. 예를 들어, ->count 가 2 면, critical section 이 2개의 프로세스가 들어갈 수 있음을 의미하고, 0 이면 어떠한 프로세스도 critical section 이 들어갈 수 없음을 의미한다.

// http://www.wowotech.net/kernel_synchronization/445.html
struct semaphore {
	unsigned int count;
	struct list_head wait_list;
};

 

 

" semaphore 에서 locking 단위는 process 이기 때문에 각 linked list entry 는 process 를 나타낼 수 있어야 한다. 그렇기 때문에 각 엔트리에는 `struct task_struct` 자료 구조를 포함하도록 한다. 그리고, linked list 에 연결되어야 하므로, `struct list_head` 를 추가한다.

// http://www.wowotech.net/kernel_synchronization/445.html
struct semaphore_waiter {
	struct list_head list;
	struct task_struct *task;
};

 

" 자료 구조가 만들어졌으면, 이제 동작을 구현해보자(down 은 lock 과 동일하며, up 은 unlock 과 동일하다고 보면 된다).

 

 

" down() 함수는 lock 을 acquire 하는 함수다. 

// http://www.wowotech.net/kernel_synchronization/445.html
void down(struct semaphore *sem)
{
	struct semaphore_waiter waiter;
 
	if (sem->count > 0) { // --- 1
		sem->count--;                               
		return;
	}
 
	waiter.task = current;                          // --- 2
	list_add_tail(&waiter.list, &sem->wait_list);   // --- 2
	schedule();                                     // --- 3
}

1. semaphore count 가 양수일 경우, critical section 에 들어갈 자리가 있다는 것을 의미한다. semaphore count 가 0 이하라면, 자리가 꽉 찼음을 의미한다.
 
2. semaphore 는 process 단위 locking 메커니즘이다. 그래서 일단은 process 가 필요하다. 그렇다면, 어떤 process 가 필요할까? 결론부터 말하면,  lock 을 구별할 필요가 없기 때문에, 어떤 프로세스이냐는 크게 중요하지 않다. 왜냐면, mutex 와 같이 process 주소를 lock ID 로 사용하는 경우가 아니기 때문이다. 그렇기 때문에, 아무 프로세스나 끌고 가야하는데 제일 접근하기 편한게 `current` 프로세스다(mutex 는 뒤에서 설명한다).  

3. schedule() 함수를 호출함으로써, CPU 점유를 포기한다(갖고 있어도 의미가 없기 때문이다).

 

 

" 2 가지 궁금한 점이 있을 수 있다.

1. down() 함수안에서 `struct semaphore_waiter waiter` 를 선언하고 있다. 그런데, 이 변수는 지역 변수다. 그런데, lock 을 획득하지 못하면, waiter 를 global semaphore list 에 연결시킨다. 즉, 함수가 종료되서 지역 변수가 사라질 위험성은 없을까?

2. lock 을 소유하지 못한 프로세스가 schedule() 함수를 호출한 후에, scheduler 에 의해서 다시 select 되어 실행되면 어떻게 되나?

 

(1) 결론적으로 안전하다. 왜냐면, global semaphore list 에 지역 변수가 들어가더라도, 뒤에 schedule() 함수가 호출되면서, 해당 프로세스는 blocked process 가 된다. 그렇면, down() 함수가 종료될 수 가 없기 때문에 스택 또한 계속 유지된다.

 

(2) 리눅스 커널의 scheduler 는 런큐에 들어가있는 TASK_RUNNING 스레드만 select 한다. 저기서, 런큐에 다시 삽입하는 코드를 넣지 않는 이상, scheduler 에 의해서 다시 실행될 가능성은 없다.

 

 

 

" up() 함수는 lock 을 release 하는 함수다. 이 함수는 2개의 로직으로 나눠볼 수 있다.

1. semaphore list 가 비어있는 경우 - semaphonre count 값을 변경한다. 즉, lock 을 release 한다. 
2. semaphore list 가 비어있지 않은 경우 - semaphonre count 값을 유지하면서, 대기중인 프로세스들을 실행한다.

// http://www.wowotech.net/kernel_synchronization/445.html
void up(struct semaphore *sem)
{
	struct semaphore_waiter waiter;
 
	if (list_empty(&sem->wait_list)) {
		sem->count++;                              // --- 1
		return;
	}
 
	waiter = list_first_entry(&sem->wait_list, struct semaphore_waiter, list);
	list_del(&waiter->list);                       // --- 2
	wake_up_process(waiter->task);                 // --- 2
}

1. semaphore 에서 lock 을 반환하는 함수인 `up` 함수를 호출한 시점에 semaphore list 가 비어있다는 것은 무슨뜻일까? 말 그대로 lock 을 기다리는 process 가 없다는 것을 의미한다. 즉, wake-up 할 프로세스가 없으므로, count 만 늘리고 함수를 종료한다. 그런데, 비어있을때만 count 를 증가시킨다.

2. 만약, semaphore 리스트가 비어있지 않다면, semaphore list 에 대기중인 프로세스가 있다는 것을 의미한다. 결국, semaphore list 중에서 제일 앞에 있는 프로세스를 실행시키면 된다. 그런데, count 는 건들일 필요없을까? semaphore list 가 비어있지 않다는 것은, 결론적으로 critical section 내에 존재하는 프로세스 개수(count)가 변함이 없다는 소리다. 왜냐면, critical section 내에서 2개의 프로세스가 실행중인데, 그 중에 하나가 up() 함수를 호출한다고 치자. 그렇면, 기존 프로세스는 critical section 을 나오고, 새로운 프로세는 들어가게 된다. 그러므로, semaphore list 가 비어있지 않다면, count 를 변경할 필요가 없다.

 

 

" count 의 개념이 약간 헷갈릴 수 있기 때문에, 그림으로 표현해봤다.

 

 

3. mutex

" semaphore 에서 언급하지는 않았지만, 사실 semaphore 는 2가지로 타입으로 나눌 수 있다. 이중에서 mutex 는 binary semaphore 의 `한 종류` 라고 보면 된다.

1. counting semaphore
2. binary semaphore

 

 

" binary semaphore 는 critical section 에 진입하는 개수를 1개로 제한하는 것이다. 그렇다면, mutex 와 binary semaphore 는 완전히 동일할까? 그렇지 않다. mutex 의 가장 큰 특징이면서 binary semaphore 와의 차이는 lock 을 가진 process 만이 unlock 할 수 있다는 것이다. 왜냐면, critical section 에 한 번 들어가면, 나올 때 까지 아무도 들어갈 수 없기 때문이다. binary semaphore 에서는 process A 가 lock 을 얻을 경우, process B 가 unlock 할 수 도 있다. 아래 그림을 참고하자(참고로, binary semaphore 는 이러한 특성 때문에 `priority inversion` 이라는 무서운 보안 문제가 발생할 수 있다. 즉, 우선 순위의 역전이 발생하는 것이다).

 

 

(1) implementation

" mutex 는 semaphore 의 부분 집합이기 때문에 기본적으로 자료 구조가 비슷하다. 그러나, 아래에서 볼 수 있다시피, critical section 에 들어갈 수 있는 개수의 1개로 제한되기 때문에, `count` 가 아닌, `owner` 로 변경한다. 이 owner 는 

// http://www.wowotech.net/kernel_synchronization/445.html
struct mutex_waiter {
	struct list_head   list;
	struct task_struct *task;
};
 
struct mutex {
    long   owner;
    struct list_head wait_list;
};

 

 

" semaphore 를 이해했다면, mutex 는 너무 쉬울것이다. lock 을 획득하는 로직이 count 에서 owner 로 바뀌었다. 즉, 다수의 lock 을 관리하다가, 하나의 lock 만을 관리하게 된 것이다. 그리고, 또 하나의 차이가 있다면 owner 가 ID 로 사용된다는 것이다. 즉, ID 이기 때문에 유일성을 보장되고, 이 말은 lock 을 획득한 프로세스만이 unlock 도 할 수 있다는 것이다. 이 때, ID 는 각 프로세스의 주소가 된다.

// http://www.wowotech.net/kernel_synchronization/445.html
void mutex_take(struct mutex *mutex)
{
	struct mutex_waiter waiter;
 
	if (!mutex->owner) {
		mutex->owner = (long)current;               
		return;
	}
 
	waiter.task = current;
	list_add_tail(&waiter.list, &mutex->wait_list);
	schedule();
}

 

 

" mutex 의 unlock 은 `lock 을 획득한 프로세스만이 unlock 도 할 수 있다` 만 이해하고 있으면 쉽다.

// http://www.wowotech.net/kernel_synchronization/445.html
int mutex_release(struct mutex *mutex)
{
	struct mutex_waiter *waiter;
 
	if (mutex->owner != (long)current)                         /* 1 */
		return -1;
 
	if (list_empty(&mutex->wait_list)) {
		mutex->owner = 0;                                      /* 2 */
		return 0;
	}
 
	waiter = list_first_entry(&mutex->wait_list, struct mutex_waiter, list);
	list_del(&waiter->list);
	mutex->owner = (long)waiter->task;                         /* 3 */
	wake_up_process(waiter->task);                             /* 4 */
 
	return 0;
}

1. 바로 이 조건이 mutex 에서 가장 큰 특징을 표현한 코드다. mutex 는 lock 를 소유한 프로세스만이 unlock 할 수 있다. 즉, 현재 코드를 실행중 인 프로세스가 lock 을 소유한 프로세스가 아니면, unlock 을 허용하지 않는다.

2. mutex_release() 함수가 호출되는 시점에 waiting list 가 비어있다면, shared resource 를 노리는 프로세스가 없다는 뜻임과 동시에 critical section 에 아무나 접근할 수 있다는 의미다(`mutex->owner = 0`).

3. mutex_release() 함수가 호출되는 시점에 waiting list 가 비어있지 않다면, 실행 할 프로세스가 있다는 것을 의미한다. 이 과정은 semephore 와 비슷하기 때문에 구체적인 내용은 semaphore 를 참고하자. 대신 한 가지 차이가 있다. semaphore 에서는 waiting list 가 비어있지 않은 경우에는 count 를 건들지 않았다. 즉, lock 을 획득한 프로세스가 반드시 unlock 을 할 필요는 없다는 것이다. 그러나, mutex 는 mutex->owner 에 새롭게 실행 될 프로세스 주소를 할당한다. 왜냐면, unlock 을 반드시 lock 을 획득한 프로세스가 해야하기 때문이다.

 

 

 

4. read-write lock

" spinlock, binary semephore, mutex 와 같은 메커니즘은 critical section 에 1 개의 프로세스만이 접근이 가능하다. 이건 프로세서의 개수가 늘어나고 있는 현 시대에는 맞지 않은 메커니즘이다. 예를 들어, 시스템에 4개의 프로세서가 존재하고, 공유 자원 A 가 있다고 가정하자. 이 공유 자원 A 에 액세스하는 프로세스들의 통계를 내봤더니, 1 초에 read operation 이 1,000,000 번이 발생하고, write operation 이 10 번 발생한다고 치자. 이 말은 read operation 100,000 번 하면, write operation 이 1 번 발생한다는 뜻이다. 그런데, 여기서 공유 자원 A 에 동기화 메커니즘으로 `spinlock, binary semephore, mutex` 방식으로 동기화를 진행하면 어떤 일이 발생할까? 각 operation 을 처리하는데, 1ns 로 계산해보면 총 1,000,010 ns 가 소요된다.

 

" 이렇게 오래 걸리는 이유는 한 시점에 하나의 프로세스만이 공유 자원에 액세스할 수 있기 때문이다. 즉, 하나의 프로세서가 critical section 에 공유 자원을 선점하면, 나머지 3 개의 프로세서들은 해당 공유 자원에 접근을 하지 못하게 된다. 이러한 문제가 발생한 원인은 동기화를 단순히 `프로세스` 단위로 나누었기 때문이다. 그렇다면, 멀티 프로세서 아키텍처에서는 어떠한 관점으로 동기화를 고려해야 할까? 바로 `동작의 속성` 에 초점을 두어야 한다. read opeartion 같은 경우는 사실 데이터만 읽는 것이기 때문에 동기화 문제를 고려할 필요가 없다. 즉, read operation 만 할 것이라면 lock 을 선점할 필요가 없다는 것이다. 그러나, write 는 데이터 일관성을 파괴할 소지가 많으므로, 상호배제 원칙에 따라 critical section 에 하나만 진입해야 할 것이다. 이러한 동기화 메커니즘을 `read-write lock` 이라고 한다. read-write lock 은 3 가지 특성을 가지고 있다.

1. writing process 가 critical section 에 없을 때만, reading process`s 들이 critical section 에 들어갈 수 있다. 
2. critical section 에는 오직 하나의 writing process 만이 들어갈 수 있다.
3. writing process 와 reading process`s 들은 critical section 에 같이 있을 수 있다.

 

" read-write lock 은 semaphore type 과 spinlock type 이 있는데, 이 글에서는 spinlock 타입에 대해 다룬다.

 

 

(1) implementation

" read-write lock 을 구현할 때, 가장 먼저 생각해볼 부분은 어떤 자료 구조가 가장 효율적인지를 생각해봐야 한다. read-write lock 의 3 가지 조건을 참고해서 생각해보자. reading process`s 들 같은 경우는 read-only 만 하기 때문에, 데이터 일관성을 깨드리지 못한다. 즉, 애들끼리는 동기화 자체가 필요없다(lock 이 필요없음). 그러나, writing process 가 critical section 에 들어가려면, reading process`s 들이 없다는 것을 알아야 하기 때문에, reading process 를 카운트할 수는 있어야 한다. 즉, count 변수가 필요할 것이다.

 

" wrting process 같은 경우는 critical section 에 자기 자신만 들어갈 수 있기 때문에, `있다(1)`, `없다(0)` 로 나눠볼 수 있을 것 같다. 그렇다면, 가장 효율적인 자료 구조는 뭘까? 바로, `unsigned int` 변수다. unsigned int 변수 하나면 된다. 어떻게 이게 가능할까?

// http://www.wowotech.net/kernel_synchronization/445.html
typedef struct {
	volatile unsigned int lock;
} arch_rwlock_t;

 

" write 는 단순히 `있다(1)`, `없다(0)` 로 표현하고, read 는 큰 숫자를 나타낼 수 있기만 하면된다. 즉, int 면 된다. 그렇다면, 이 자료 구조는 space 면에서만 좋은걸까? 아니다. int 형 연산은 기본적인 atomic operation 이기 때문에 원자성까지 보장된다. 거기다가 int 연산은 CPU 한테 가장 빠른 연산이다.

 

" 그리고 생각해볼 부분은 `어떻게 read 와 write 를 나눌 것인가` 이다. 예를 들어, critical section 에 액세스할 때, reader 는 다수가 진입할 수 있고, writer 는 하나만 가능한데 위(spinlock, semaphore, mutex) 방식들처럼 하나의 lock() 함수로 2개의 로직(read, write) 을 모두 처리할 것인지를 고민해봐야 한다. 여기서는 가장 일반적인 방법으로 read 와 write 를 각각 처리한다(예를 들어, read_lock / read_unlock 이 한 쌍으로, write_lock / write_unlock 이 또 한 쌍으로 묶인다).

 

" reading process 에서 사용하는 lock() 함수는 다음과 같다.

// http://www.wowotech.net/kernel_synchronization/445.html
static inline void arch_read_lock(arch_rwlock_t *rw)
{
	unsigned int tmp;
 
	sevl();                                   // --- 1
	do {
		wfe();
		tmp = rw->lock;
		tmp++;                                // --- 2
	} while(tmp & (1 << 31));                 // --- 3
	rw->lock = tmp;
}

1. sevl() 함수는 arm64 의 `SEVL` 명령어를 의미한다. `Send Event Local` 의 약자로 WFE 상태에 있을 경우, wake-up 시킨다. 그런데, wfi 명령어 앞에 sevl 명령어를 실행하는 것이 조금 이상해보인다. 왜 먼저 호출할까? A32 에서 WFE 명령어를 사용해서, SLEEP 에 들어가는데 제약 조건이 있다. 그런데, SEVI 명령어를 먼저 실행하고, WFE 명령어가 실행되면, event signal 을 받으면, 즉각적으로 wake-up 할 수 있어서 sevl 명령어가 wfe 보다 앞에 온다.

It's using the WFE instruction with the NE (Not Equal) condition to go to sleep if it's not unlocked.  In A64 the WFE instruction is not conditional.  Which makes this a little trickier.  SEVL is one way to get round this, it sets the Event register only of the core you are running on.... The SEVL means that the first time we hit the WFE it will "wake" immediately... - 참고 : https://community.arm.com/support-forums/f/architectures-and-processors-forum/4273/how-to-understand-armv8-sevl-instruction-in-spin-lock

 

2. reader 가 critical section 에 들어왔으니 reader`s counter 를 1 증가시킨다.

3. `1 <<31` 은 write count 를 의미한다. 이 값이 1 이라는 것은 critical section 에 writing process 가 이미 들어가 있다는 것을 의미한다. 그러므로, reading process`s 들은 무한 루프를 돌면서 writing process 가 나올 때 까지 대기한다.

 

 

" writing process 가 lock() 함수는 다음과 같다.

// http://www.wowotech.net/kernel_synchronization/445.html
static inline void arch_write_lock(arch_rwlock_t *rw)
{
	unsigned int tmp;
 
	sevl();
	do {
		wfe();
		tmp = rw->lock;
	} while(tmp);                       /* 1 */
	rw->lock = 1 << 31;                 /* 2 */
}

1. writing process 는 reading process`s 들과는 달리, 같은 wrting process 와 함께 critical section 에 들어가지 못한다. 즉, writing, reading 관계없이 자기 자신만 critical section 에 혼자 들어가야 한다. rw->lock 에 양수이면, critical section 에 writing, reading 관계없이 임의의 프로세스가 있다는 뜻이므로, 무한루프를 돌면서 대기한다.

2. critical section 에 아무도 없을 경우(rw->lock == 0), critical section 의 lock 을 선점한다. write count 는 30 번째 비트다.

 

 

" reading process 가 critical section 을 나올 때, 어떻게 lock 을 풀어야 할까? 먼저, 고려해볼 점은 reading process 는 critical section 에서 나올 때, 다른 reading process`s 들이 critical section 에 존재할 수 있다. 그렇기 때문에, 자기 자신의 lock 만 제거하면 된다. 그러나, read-write lock 에서는 mutex 와 같이 각각의 lock 을 구분할 필요는 없기 때문에, 개수를 1개 깍는 것만으로도 충분하다(semaphore 에서와 마찬 가지로 lock ID 보단 lock count 에 초점을 둔다).

// http://www.wowotech.net/kernel_synchronization/445.html
static inline void arch_read_unlock(arch_rwlock_t *rw)
{
	rw->lock--;
	sev();
}

 

 

" reading process 가 critical section 을 빠져 나올때는, 다른 프로세스들이 남아 있을 수 있기 때문에 자기만 빠져나간다는 의미로 `1` 을 차감한다. 그렇다면, writing process 가 critical section 을 나올때는 어떤걸 고려 해야할까? writing process 가 critical section 에 있을때는, 자신 말고 아무도 critical section 에 있을 수 없다. 그렇다면, 작업을 막 마친 시점 또한 critical section 에 자기만 있을 것이다. 그렇기 때문에, rw->lock 을 `0` 으로 초기화해도 된다. 굳이, 쉬프트 연산해서 30 번째 비트만 CELAR 할 필요는 없다.

// http://www.wowotech.net/kernel_synchronization/445.html
static inline void arch_write_unlock(arch_rwlock_t *rw)
{
	rw->lock = 0;                    
	sev();                         
}

 

 

" 사실, 엄밀히 따지면 위의 코드들은 AArch64 의 기능을 제대로 사용하지 못한 코드다. arm 에서 STLR(Store-Release) 명령어를 사용할 경우, 다른 CPU 의 Global Exclusives Monitor 를 CLEAR 한다. Global Exclusives Monitor 를 CLEAR 되면, 각 CPU 에 wake-up event 가 발생해서 WFE 상태에 있는 CPU 들을 wake-up 시킨다. 즉, 위에서 *_unlock 함수들은 실제로 sev 명령어를 사용할 필요가 없다는 것이다(하드웨어 의존도를 낮춰서 작성하려고 했기 때문에, 생략된 내용임. 참고바람).

// ARM Architecture Reference Manual ARMv8, for ARMv8-A architecture profile
AArch32
Px
 ; loads and stores in the critical region
 MOV R0, #0
 STL R0, [R1] ; clear the lock
AArch64
Px
 ; loads and stores in the critical region
 STLR WZR, [X1] ; clear the lock