IT/모바일
리눅스 커널의 이해(6): Uni-Processor 상에서의 동기화 문제와 그에 대한 해결책
본 한빛 네트워크 기사를 블로그 등에 기재할 경우에는 URL을 포함한 출처를 명기해 주시길 부탁드립니다.
특히 아래 본문 서두에 기재된 저자(역자) 및 원출처는 필히 명기해 주시기 바랍니다.
저자: 서민우
출처: Embedded World
[ 관련 기사 ]
♠ 리눅스 커널의 이해(1) : 커널의 일반적인 역할과 동작
♠ 리눅스 커널의 이해(2): 리눅스 커널의 동작
♠ 리눅스 커널의 이해(3): 리눅스 디바이스 작성시 동기화 문제
♠ 리눅스 커널의 이해(4): Uni-Processor & Multi-Processor 환경에서의 동기화 문제
♠ 리눅스 커널의 이해(5): 디바이스에 쓰기 동작에 대한 구체적인 작성 예
이번 기사에서는 mmlt;동기적으로 디바이스로부터 읽기 동작mmgt;과 관련해서 Uni-Processor 상에서 발생할 수 있는 동기화 문제와 그에 대한 해결책을 알아보자. 또한 이를 바탕으로 실제 구현은 어떻게 이루어지는지 구체적인 예를 통해서 알아 보기로 하자.
mmlt;동기적으로 디바이스로부터 읽기 동작mmgt;에 대한 Uni-Processor 상에서의 동기화 문제와 그에 대한 해결책
지난 기사에서 우리는 mmlt;동기적으로 디바이스로부터 읽기 동작mmgt;과 관련한 커널의 흐름을 보았다. 그 흐름을 좀 더 구체적으로 나타내면 다음과 같다.
시스템 콜 루틴 내부
i) 디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고
디바이스에 데이터 읽기를 요청하고
디바이스로부터 데이터 큐에 데이터가 도착하기를 기다린다
데이터 큐에서 데이터를 꺼낸다
디바이스를 다 사용했다고 표시하고 나간다
ii) 디바이스를 사용하고 있으면
디바이스의 사용이 끝나기를 기다린다
하드웨어
디바이스에 데이터가 도착했다 → hardware interrupt 발생
top half 루틴 내부
메모리 버퍼를 하나 할당해
디바이스 버퍼로부터 데이터를 읽어 들인 후
메모리 버퍼를 데이터 큐에 넣는다
bottom half 요청
bottom half 루틴 내부
디바이스로부터 데이터 큐에 데이터가 도착했다고 표시하고 나간다
mmlt;동기적으로 디바이스로부터 읽기 동작mmgt;의 경우 시스템 콜 루틴 내부에서 디바이스에 데이터 읽기를 요청함으로써 디바이스가 동작하기 시작하고, 적당한 시간이 흐른 후, 데이터가 디바이스 버퍼에 도착한다. 그러면 디바이스는 인터럽트를 통해 데이터의 도착을 CPU에게 알리며, CPU는 인터럽트 핸들러를 통하여 이 데이터를 읽어간다. 하드 디스크나 CDROM에 도착한 데이터를 읽어가는 동작 등이 이에 해당한다. 참고로 동기적이란 디바이스에 데이터 읽기를 요청함으로써 디바이스가 동작하기 시작하고, 적당한 시간이 흐른 후, 데이터가 디바이스에 도착함을 의미한다.
위의 흐름은 프로세스를 기준으로 볼 때 논리적으로 두 가지 흐름으로 나눌 수 있으며 각각 다음과 같다.
1) 다른 프로세스가 디바이스를 사용하고 있지 않을 경우
2) 다른 프로세스가 디바이스를 사용하고 있을 경우
각각의 경우를 구체적으로 보자.
1) 다른 프로세스가 디바이스를 사용하고 있지 않을 경우
시스템 콜 루틴 내부 1
i) 디바이스를 사용하고 있지 않으면 ------ ⓐ
디바이스를 사용한다고 표시하고 ------ ⓐ
디바이스에 데이터 읽기를 요청하고 ------ ⓐ
디바이스로부터 데이터 큐에 데이터가 도착하기를 기다린다 ------ ⓑ
하드웨어
디바이스에 데이터가 도착했다 → hardware interrupt 발생
top half 루틴 내부
메모리 버퍼를 하나 할당해
디바이스 버퍼로부터 데이터를 읽어 들인 후
메모리 버퍼를 데이터 큐에 넣는다
bottom half 요청
bottom half 루틴 내부
디바이스로부터 데이터 큐에 데이터가 도착했다고 표시하고 나간다 ------ ⓒ
시스템 콜 루틴 내부 2
i) 데이터 큐에서 데이터를 꺼낸다
디바이스를 다 사용했다고 표시하고 나간다
1)의 경우는 어떤 프로세스 P1이 system call을 통해 커널 영역에서 어떤 디바이스를 사용하고자 할 때 임의의 다른 프로세스가 그 디바이스를 사용하고 있지 않으면 디바이스를 사용한다고 표시하고, 디바이스에 데이터 읽기를 요청하고, 디바이스로부터 데이터 큐에 데이터가 도착하기를 기다린다. 그러면 디바이스는 읽기 동작을 수행하기 시작한다. 어느 정도의 시간이 지나면 그 디바이스는 읽기 동작을 완료하고 hardware interrupt를 발생시킨다.
여기서 hardware interrupt는 임의의 프로세스 Pn을 수행하는 중에 발생한다. hardware interrupt가 발생하면 top half 루틴과 bottom half 루틴을 차례로 수행한다. top half 루틴에서는 메모리 버퍼를 하나 할당해, 디바이스 버퍼로부터 데이터를 읽어 들인 후, 메모리 버퍼를 데이터 큐에 넣는다.
그리고 bottom half 루틴을 수행하기를 요청한다. bottom half 루틴에서는 디바이스로부터 데이터 큐에 데이터가 도착했다고 표시하고 나간다. 그러면 기다리던 프로세스 P1은 데이터 큐에서 데이터를 꺼내고, 디바이스를 다 사용했다고 표시하고 나간다.
2) 다른 프로세스가 디바이스를 사용하고 있을 경우
시스템 콜 루틴 내부(프로세스 Pk)
ii) 디바이스를 사용하고 있으면 ------ ⓓ
디바이스의 사용이 끝나기를 기다린다 ------ ⓓ
시스템 콜 루틴 내부(프로세스 P1)
디바이스를 다 사용했다고 표시하고 나간다 ------ⓔ
이후에는 1)의 동작이 온다.
2)의 경우는 어떤 프로세스 Pk가 system call을 통해 커널 영역에서 어떤 디바이스를 사용하고자 할 때, 임의의 프로세스 P1이 그 디바이스를 이미 사용하고 있으면, 디바이스의 사용이 끝나기를 기다린다. 그 디바이스를 사용하고 있던 프로세스 P1은 후에 디바이스를 다 사용했다고 표시하고 나간다. 그러면 프로세스 Pk는 1)의 동작을 수행할 수 있다.
동기화 문제와 해결책
그러면 지금부터 mmlt;동기적으로 디바이스로부터 읽기 동작mmgt;과 관련한 두 가지 논리적인 흐름에서 생길 수 있는 동기화 문제와 이에 대한 해결책을 생각해 보자.
먼저 1)의 ⓐ 부분에서는 mmlt;시스템 콜 루틴간의 경쟁 상태mmgt;가 발생할 수 있다. mmlt;시스템 콜 루틴간의 경쟁 상태mmgt;와 그에 대한 해결책에 대해서는 본지 11월 호에서 충분히 설명하였으며 이를 참조하기 바란다. 본지 11월 호에서 설명한 내용에 따라 1)의 ⓐ 부분은 다음과 같이 처리한다.
cli
디바이스를 사용하고 있지 않으면
디바이스를 사용한다고 표시하고
디바이스에 데이터 읽기를 요청하고
sti
다음은 1)의 ⓑ 부분을 보자. 이 부분을 실제 소스 코드로 나타내면 다음과 같다.
while(1) {
if(dev_working_done mmgt; 0) {
dev_working_done --;
break;
}
}
이 부분은 1)의 ⓒ 부분에 의해 루프문을 빠져나간다. 1)의 ⓒ 부분을 실제 소스 코드로 나타내면 다음과 같다.
dev_working_done ++;
위의 두 소스 코드는 그대로 사용하여도 논리적으로 문제가 없다.
[그림 1]은 1) 동작의 한 예다.
[그림 1] 동기적으로 디바이스로부터 읽기 예 1
[그림 1]의 A 지점에서 프로세스 P1은 dev_working_done 변수 값이 양의 수가 될 때까지 while 문 안에서 기다린다. 즉, busy waiting을 수행한다. [그림 1]의 ①부터 ② 구간까지는 디바이스의 동작 구간이며 디바이스의 특성에 따라 일반적으로 이 시간을 예측할 수 없다. 일반적으로 디바이스의 동작이 끝나기까지는 CPU를 기준으로 볼 때 상당한 시간이 걸리며, 이 시간동안 busy waiting을 수행할 경우 너무 많은 CPU 시간을 낭비하게 된다. 따라서 이에 대한 적절한 처리를 해 주어야 한다.
일반적으로 시스템 콜 루틴에서 예측할 수 없는 시간동안 논리적으로 busy waiting을 수행해야 할 경우 현재 프로세스를 blocking 시킨다. 즉, 현재 프로세스를 특정한 wait queue에 넣고 schedule을 수행한다. 리눅스 커널에서는 sleep_on 류의 함수가 이러한 역할을 한다.
이상에서 1)의 ⓑ 부분은 다음과 같이 고친다.
while(1) {
if(dev_working_done mmgt; 0) {
dev_working_done --;
break;
}
interruptible_sleep_on(&wait_queue_in);
}
또한 1)의 ⓒ 부분은 다음과 같이 고친다.
dev_working_done ++;
wake_up_interruptible(&wait_queue_in);
앞에서 interruptible_sleep_on 함수는 현재 프로세스를 wait_queue_in에 넣고 schedule 함수를 호출한다. wake_up_interruptible 매크로는 wait_queue_in에 있는 프로세스를 runqueue로 옮기는 역할을 한다. interruptible_sleep_on 함수를 통해 wait_queue_in으로 들어간 프로세스는 mmlt;Ctrl+Cmmgt;등에 의해 발생하는 시그널에 의해서도 wait_queue_in에서 빠져 나올 수 있다. 논리적으로 비슷한 역할을 하는 sleep_on 함수의 경우는 wake_up 매크로와 대응하며, 시그널에는 반응하지 않는다.
그러나 위의 두 소스 코드는 논리적으로 문제가 있다. 본래 의도로는 소스 코드의 배치가 다음과 같이 이루어져야 한다.
while(1) {
if(dev_working_done mmgt; 0) {
dev_working_done --;
break;
}
interruptible_sleep_on(&wait_queue);
}
dev_working_done ++;
wake_up_interruptible(&wait_queue);
그러나 소스 코드의 배치가 다음과 같이 이루어질 수도 있으며, 이 경우 논리적으로 문제가 발생한다.
while(1) {
if(dev_working_done mmgt; 0) {
dev_working_done --;
break;
}
dev_working_done ++;
wake_up_interruptible(&wait_queue);
interruptible_sleep_on(&wait_queue);
}
이와 같이 소스 코드가 배치될 경우 상황에 따라 dead lock 내지는 starvation이 발생할 수 있다. interruptible_sleep_on 함수의 이러한 문제점을 보완하기 위하여 wait_event_interruptible 매크로가 있다. 이 매크로를 이용하여 1)의 ⓑ 부분을 다음과 같이 고치면 문제를 해결할 수 있다.
while(1) {
if(dev_working_done mmgt; 0) {
dev_working_done --;
break;
}
wait_event_interruptible(wait_queue_in, (dev_working_done mmgt; 0));
}
wait_event_interruptible(wq, condition) 매크로는 condition의 조건이 될 때까지 wq에서 기다림을 의미한다. 이렇게 처리할 경우, 1)의 ⓒ 부분은 문제가 없으며, 그대로 사용한다.
[그림 2]는 1)의 완성된 동작을 나타낸다.
[그림 2] 동기적으로 디바이스로부터 읽기 예 2
[그림 2]의 A 부분에서 프로세스 P1은 busy waiting을 수행하지 않고 wait_queue에서 기다린다. 이상에서 1)의 경우에서 발생할 수 있는 동기화 문제와 이에 대한 해결책을 생각해 보았다.
다음은 2)의 ⓓ 부분을 보자. 이 부분에서는 mmlt;시스템 콜 루틴간의 경쟁 상태mmgt;가 발생할 수 있다. 따라서 이 부분은 다음과 같이 처리한다.
cli
디바이스를 사용하고 있으면
디바이스의 사용이 끝나기를 기다린다
sti
2)의 ⓓ 부분은 1)의 ⓐ 부분과 같이 생각해야 하며, 실제 소스 코드로 나타내면 다음과 같다.
while(1) {
local_irq_save(flags);
if(dev_key mmgt; 0) { ------ ①
dev_key --;
break;
}
local_irq_restore(flags);
}
DEV_READ_COMMAND;
local_irq_restore(flags);
이 소스 코드에서 ① 부분이 조건에 맞지 않을 때, 논리적으로 2)의 ⓓ 부분을 나타내게 된다. 이 부분은 2)의 ⓔ 부분에 의해 루프문을 빠져나간다. 2)의 ⓔ 부분을 실제 소스 코드로 나타내면 다음과 같다.
local_irq_save(flags);
dev_key ++;
local_irq_restore(flags);
위의 두 소스 코드는 그대로 사용하여도 논리적으로 문제가 없다. 그러나 여기서도 busy waiting이 발생할 수 있으며, 따라서 각각의 소스 코드를 다음과 같이 수정한다.
먼저 2)의 ⓓ 부분을 다음과 같이 고친다.
while(1) {
local_irq_save(flags);
if(dev_key mmgt; 0) {
dev_key --;
break;
}
local_irq_restore(flags);
wait_event_interruptible(wait_queue_out, (dev_key mmgt; 0));
}
DEV_READ_COMMAND;
local_irq_restore(flags);
다음은 2)의 ⓔ 부분을 다음과 같이 고친다.
local_irq_save(flags);
dev_key ++;
local_irq_restore(flags);
wake_up_interruptible(&wait_queue_out);
이상에서 mmlt;동기적으로 디바이스로부터 읽기 동작mmgt;과 관련한 두 가지 논리적인 흐름에서 생길 수 있는 동기화 문제와 이에 대한 해결책을 생각해 보았다. 다음은 실제 예를 들여다보기로 하자.
디바이스 드라이버 작성 예
다음 예는 지난 기사에서 작성해 본 예제와 유사하며 예제에 대한 자세한 설명은 지난 기사를 참조하기 바란다.
# vi devread-sync.c
#include mmlt;linux/kernel.hmmgt;
#include mmlt;linux/module.hmmgt;
#include mmlt;linux/fs.hmmgt;
#include mmlt;linux/kdev_t.hmmgt;
#include mmlt;asm/uaccess.hmmgt;
ssize_t dev_read(struct file * filp, char * buffer,
size_t length, loff_t * offset);
struct file_operations dev_fops = {
read: dev_read,
};
static int major = 0;
int init_module()
{
printk("Loading devread-sync module\n");
major = register_chrdev(0, "devread-sync", &dev_fops);
if(major mmlt; 0) return major;
return 0;
}
void cleanup_module()
{
unregister_chrdev(major, "devread-sync");
printk("Unloading devread-sync module\n");
}
#define SLOT_NUM 8
char dev_buffer = 0;
int dev_key = 1;
char data_slot[SLOT_NUM];
int full_slot_num = 0;
int empty_slot_num = SLOT_NUM;
int full_slot_pos = 0;
int empty_slot_pos = 0;
void dev_working();
int dev_working_done = 0;
#define DEV_READ_COMMAND
ssize_t dev_read(struct file * filp, char * buffer,
size_t length, loff_t * offset)
{
char user_buffer;
unsigned long flags;
if(length != 1) return -1;
while(1) {
local_irq_save(flags);
if(dev_key mmgt; 0) {
dev_key --;
break;
}
local_irq_restore(flags);
}
DEV_READ_COMMAND;
local_irq_restore(flags);
dev_working();
while(1) {
if(dev_working_done mmgt; 0) {
dev_working_done --;
break;
}
}
full_slot_num --;
user_buffer = data_slot[full_slot_pos];
full_slot_pos ++;
if(full_slot_pos == SLOT_NUM) full_slot_pos = 0;
empty_slot_num ++;
local_irq_save(flags);
dev_key ++;
local_irq_restore(flags);
copy_to_user(buffer, &user_buffer, 1);
return 1;
}
static struct timer_list dev_interrupt;
void dev_interrupt_handler(unsigned long dataptr);
void dev_working()
{
init_timer(&dev_interrupt);
dev_interrupt.function = dev_interrupt_handler;
dev_interrupt.data = (unsigned long)NULL;
dev_interrupt.expires = jiffies + 1;
add_timer(&dev_interrupt);
}
void dev_interrupt_handler(unsigned long dataptr)
{
printk("%d\n", dev_buffer);
dev_buffer ++;
top_half:
empty_slot_num --;
data_slot[empty_slot_pos] = dev_buffer;
empty_slot_pos ++;
if(empty_slot_pos == SLOT_NUM) empty_slot_pos = 0;
full_slot_num ++;
bottom_half:
dev_working_done ++;
return;
}
# gcc devread-sync.c -c -D__KERNEL__ -DMODULE -I/usr/src/linux-2.4/include
# lsmod
# insmod devread-sync.o -f
# lsmod
Module Size Used by Tainted: PF
devread-sync 3004 0 (unused)
...
# cat /proc/devices
Character devices:
...
254 devread-sync
Block devices:
...
# mknod /dev/devread-sync c 254 0
# ls -l /dev/devread-sync
crw-r--r-- 1 root root 254, 0 12월 6 07:46 /dev/devread-sync
# vi devread-sync-app.c
#include mmlt;sys/types.hmmgt;
#include mmlt;sys/stat.hmmgt;
#include mmlt;fcntl.hmmgt;
int main()
{
int fd;
char buffer;
int i;
fd = open("/dev/devread-sync", O_RDWR);
for(i=0;immlt;100;i++) {
read(fd, &buffer, 1);
printf("pid %d: %d\n", getpid(), buffer);
}
close(fd);
}
# gcc devread-sync-app.c -o devread-sync-app
# ./devread-sync-app
pid 1435: 1
pid 1435: 2
pid 1435: 3
pid 1435: 4
pid 1435: 5
...
# rmmod devread-sync
이 예제는 논리적으로 문제가 없다. 그러나 시스템 콜 루틴에서 예측할 수 없는 시간동안 busy waiting을 수행함으로써 CPU 시간을 낭비한다. 일단 dev_read 함수와 dev_interrupt_handler 함수의 dev_working_done 변수 접근 부분을 각각 다음과 같이 고친 후 시험해 본다
DECLARE_WAIT_QUEUE_HEAD(wait_queue_in);
ssize_t dev_read(struct file * filp, char * buffer,
size_t length, loff_t * offset)
{
…
while(1) {
if(dev_working_done mmgt; 0) { // ②
dev_working_done --;
break;
}
printk("sleep on wait queue in start\n");
interruptible_sleep_on(&wait_queue_in); // ③
printk("sleep on wait queue in end\n");
}
…
}
void dev_interrupt_handler(unsigned long dataptr)
{
…
bottom_half:
dev_working_done ++;
printk("wake up wait queue in\n");
wake_up_interruptible(&wait_queue_in); // ④
return;
}
# gcc devread-sync.c -c -D__KERNEL__ -DMODULE -I/usr/src/linux-2.4/include
# insmod devread-sync.o -f
# ./devread-sync-app
pid 6547: 1
pid 6547: 2
pid 6547: 3
응용 프로그램을 수행하는 중에 멈춘다. 이는 dev_read 함수의 ②와 ③ 사이에 dev_interrupt_handler 함수의 ④ 부분이 끼어 들어 발생하는 문제이다. 이 경우, dev_read 함수를 수행 중이던 프로세스가 dev_key를 가진 상태에서 wait_queue_in에서 기다리는 dead lock 상황이다. 즉, wait_queue_in에서 기다리는 프로세스가 깨어나기 위해서는 dev_interrupt_handler 함수를 수행해야 하고, 이 함수는 디바이스의 읽기 동작를 수행하여야 수행할 수 있고, 디바이스의 읽기 동작을 수행하기 위해서는 dev_key가 필요하다.
그런데 dev_key는 wait_queue_in에서 기다리는 프로세스가 가지고 있는 상태이다. 즉, wait_queue_in에서 기다리는 프로세스는 깨어날 수 없고, 새로이 디바이스를 접근하고자 하는 프로세스는 디바이스에 접근할 수 없는 deadlock 상황이다.
mmlt;Ctrl+Cmmgt;를 눌러 프로그램을 종료한다.
# rmmod devread-sync
dev_read 함수를 다음과 같이 고친 후 시험해 본다.
ssize_t dev_read(struct file * filp, char * buffer,
size_t length, loff_t * offset)
{
…
while(1) {
if(dev_working_done mmgt; 0) {
dev_working_done --;
break;
}
printk("sleep on wait queue in start\n");
wait_event_interruptible(wait_queue_in, (dev_working_donemmgt;0));
printk("sleep on wait queue in end\n");
}
…
}
# gcc devread-sync.c -c -D__KERNEL__ -DMODULE -I/usr/src/linux-2.4/include
# insmod devread-sync.o -f
# ./devread-sync-app
pid 1580: 1
pid 1580: 2
pid 1580: 3
pid 1580: 4
pid 1580: 5
...
응용 프로그램이 정상적으로 수행되는걸 볼 수 있다.
# rmmod devread-sync
마지막으로 dev_read 함수의 dev_key 변수 접근 부분을 다음과 같이 수정한다.
DECLARE_WAIT_QUEUE_HEAD(wait_queue_in);
DECLARE_WAIT_QUEUE_HEAD(wait_queue_out);
ssize_t dev_read(struct file * filp, char * buffer,
size_t length, loff_t * offset)
{
…
while(1) {
local_irq_save(flags);
if(dev_key mmgt; 0) {
dev_key --;
break;
}
local_irq_restore(flags);
printk("sleep on wait queue out start\n");
wait_event_interruptible(wait_queue_out, (dev_keymmgt;0));
printk("sleep on wait queue out start\n");
}
DEV_READ_COMMAND;
local_irq_restore(flags);
…
local_irq_save(flags);
dev_key ++;
local_irq_restore(flags);
printk("wake up wait queue out\n");
wake_up_interruptible(&wait_queue_out);
…
}
# gcc devread-sync.c -c -D__KERNEL__ -DMODULE -I/usr/src/linux-2.4/include
# insmod devread-sync.o -f
# vi devread-sync-app-sh
#!/bin/sh
./devread-sync-app &
./devread-sync-app &
./devread-sync-app &
./devread-sync-app &
./devread-sync-app &
./devread-sync-app &
# chmod u+x devread-sync-app-sh
# ./devread-sync-app-sh
...
pid 6601: 55
pid 6602: 57
pid 6601: 56
pid 6602: 58
...
정상적으로 수행되는걸 볼 수 있다.
# rmmod devread-sync
이상에서 mmlt;동기적으로 디바이스로부터 읽기 동작mmgt;에 대한 Uni-Processor 상에서의 동기화 문제와 그에 대한 해결책, 그리고 실제 구현은 어떻게 이루어지는지 알아보았다.
다음 기사에서는 mmlt;비동기적으로 디바이스로부터 읽기 동작mmgt;에 대한 Uni-Processor 상에서의 동기화 문제와 그에 대한 해결책, 그리고 실제 구현은 어떻게 이루어지는지 보기로 하자.
서민우 / minucy@hanmail.net
과학기술정보연구소 및 여러 대학교에서 임베디드 리눅스 실무과정을 강의하면서 리눅스 커널 초기버전을 분석하는 작업을 통해 초보자들도 OS 의 설계 및 구현에 대해 체계적으로 접근할 수 있는 방법에 대한 자료를 제작하는 데에 힘을 쏟고 있다. 50개 정도의 명령어, pipeline 등을 포함한 32 bit RISC CPU 를 설계 및 구현한 경험이 있고 uCOS/II 정도 수준의 OS 설계 및 구현에 대한 체계적인 접근 방법에 대한 자료까지 완성한 상태이며 지속적인 작업을 통해 커널과 OS에 관한 유용한 정보를 널리 공유하고자 노력하고 있다.
TAG :
최신 콘텐츠