concurrency

thread

• per thread registers
• per thread program counter
• per thread stack

address space(heap, data, code는 공유)

why multi threading?

• 여러 cpu에서 동시에 돌려서 수행 속도 빠르게 할 수 있음
• 한 thread가 I/O를 처리하는 동안에도 다른 스레드는 일을 할 수 있으므로 I/O로 인해 blocked돼서 job을 수행하지 못하는 현상을 해결 가능

race condition

멀티 스레딩할 때 수행 결과가 interrupt가 걸리는 timing에 따라 달라지는 것

thread 리턴값 주의

int *ptr(){
  int *a;
  (*a) = 3;
  return a;
}

이러면 존나 문제 있는 코드임. 왜냐면 a는 ptr 함수가 끝나면서 dealloc되기 때문에...
따라서,

int *ptr(){
  int *a = malloc(sizeof(int));
  (*a) = 3;
  return a;
}

이렇게 a에 관한 메모리는 heap에 할당해야함!!

LOCK

lock 성능 평가

• 진짜로 critical section에 하나의 스레드만 들어가는 지
• 모든 스레드가 공평하게 lock을 쥐게 되는 지
• lock을 더함으로써 time overhead가 얼마나 더 생기는지

그럼 lock을 어떻게 구현할 건데?

1. lock = timer interrupt

모든 race condition 문제는 내가 critical section에 있다가 다른 스레드도 critical section에 들어와서 생긴다.

따라서 내가 critical section에 있을 때 timer interrupt를 끄면 다른 스레드가 들어올 일은 생기지 않는다!!

하지만 이 방법은 문제가 많다.

• 나쁜 스레드가 lock을 잡고 무한 루프 돌면 ? ..
• timer interrupt를 키고 끄는 것 자체가 오버헤드가 큼

2. flag를 둬서 누가 lock을 잡고 있다고 나타낼까?

위의 interrupt를 끄는 방법은 처참히 실패했다,,,

그럼 아예 관점을 바꿔서 flag를 두고 해당 영역의 flag가 1로 설정되면 그 영역에 접근하지 못하게 해볼까?

void lock(lock_t *lock){
  while(lock->flag == 1)
    ;
  lock->flag = 1;
}

꽤 그럴듯 해 보인다. flag가 0이 될때까지 기다렸다가 내가 Lock을 쥐었다는 뜻으로 다시 flag를 1로 설정한다.

하지만 세상은 호락호락하지 않다... 이 방법 역시 문제가 있다.
어떤 스레드가 while loop를 빠져나오고 flag를 1로 설정하기 직전에 interrupt가 걸렸다고 해보자
그럼 다른 스레드가 스케줄링 될 것이고 이 동안 flag 값은 절대 바뀌지 않았기에, 그 스레드는 바로 while loop를 빠져나오고 역시 lock을 잡게 된다.
이제 다시 원래 스레드가 스케줄링 된다. 원래 스레드 역시 lock을 잡게 된다.

lock의 기본인 한번에 한 스레드만 lock을 잡는다가 실패한 것이다... ㅠㅠ

이 문제가 왜 발생했느냐? flag가 0일때 1로 바로 바꿔줘야 하는데, 바꾸기 직전에 다른 스레드가 스케줄링 돼서 그렇다.

이제 슬슬 무슨 말을 하려는 지 알 것이다.

0이면 1로 바로 바꿔주는 작업을 hw support 받아서 atomic하게 하면 된다!

따라서 다음부터 나오는 lock은 전부 atomic instruction을 바탕으로 한다.

3. TestAndSet

int TestAndSet(int ptr, int new)는 ptr 값을 new로 바꿔주고 이전 ptr 값을 리턴한다.

이를 사용한 lock의 구현은 다음과 같다.

void lock(lock_t *lock){
  while(TestAndSet(&(lock->flag), 1)==1)
    ;
}

코드를 보면 lock->flag의 값이 0일 때 flag를 1로 세팅하고 while loop를 빠져 나오게 된다.

이제 한번에 한 스레드만 lock을 잡게 된다. 꽤 합리적인 것 같다.

이제 성능 평가를 해보자

• mutual exclusion : 한번에 한 스레드만 lock을 잡는다
• fairness : 스레드가 공평하게 lock을 잡는다는 보장은 없다
• performance : single processor에선 오버헤드가 크다. 스레드의 개수와 processor의 개수가 같다면 성능은 나쁘지 않다.

5. CompareAndSwap

int CompareAndSwap(int ptr, int expected, int *new)는 ptr이 expected와 같으면 new를 넣는다. 이전 ptr값을 리턴한다.

CompareAndSwap을 사용하여 구현한 lock은 다음과 같다.

void lock(lock_t *lock){
  while(CompareAndSwap(&lock->flag, 0, 1)==1)
    ;
}

마찬가지로 lock->flag==0일 때 1을 넣고 0을 리턴해서 while loop를 빠져나오게 된다.

6. LoadLinked, StoreConditional

int LoadLinked(int ptr) 은 ptr을 리턴한다.
int StoreConditional(int ptr, int *value)는 Storeconditional이 호출된 후 ptr의 값에 변화가 없으면 ptr에 value를 넣고 1을 리턴한다. ptr의 값에 변화가 있으면 0을 리턴한다.

LoadLinked와 StoreConditional을 통해 구현한 lock은 다음과 같다.

void lock(lock_t *lock){
  while(LoadLinked(&lock->flag)==1 || StoreConditional(&lock->flag, 1)==0)
    ;
}

while loop의 조건은 lock->flag==0이고, StoreConditional이 성공해서 1을 리턴할 때이다. 즉, flag가 0이고 해당 스레드만 flag에 접근해서 1로 업데이트하는 데 성공한 것이다.

근데 지금까지 말한 lock들(test and set, compare and swap, store conditional)은 fairness에 대한 어떤 보장도 없다...!! 그래서 다음과 같은 lock을 소개하겠다.

7. FetchAndAdd를 사용한 Ticket Lock

FetchAndAdd(int *ptr)은 ptr에 1을 더하고 이전 ptr값을 리턴한다.
ticket lock의 아이디어는 스레드마다 1, 2, 3, ... 등의 티켓을 주는 것이다. 그리고 티켓에 적힌 숫자와 lock의 차례가 같게 되면, 그 스레드에게 lock을 주는 것이다. 코드를 봐 보자

void lock_init(lock_t *lock){
  lock->turn = 0;
  lock->ticket = 0;
}

void lock(lock_t *lock){
  int myTurn = FetchAndAdd(&lock->ticket);
  while(myTurn != lock->turn)
    ;
}

void unlock(lock_t *lock){
  FetchAndAdd(&lock->turn);
}

코드는 상당히 직관적이다. lock을 잡으려 하면 내 티켓 번호를 부여 받고 내 차례가 올때까지 기다린다.
스레드가 lock을 release하게 되면 차례를 1 증가시킨다.

이렇게 하면 티켓을 부여 받은 스레드는 모두 한번 씩 lock을 잡을 수 있으므로 모든 스레드에게 fairness가 보장된다.

지금까지 살펴본 lock들은 전부 atomic instruction을 기반으로 해서 spinning하면서 lock을 기다린다. 다만 spinning 자체가 cpu 낭비이기에, 누군가 lock을 쥐고 있다면 아예 yield를 해서 ready queue에 들어가는 방법도 있다. 다만 이렇게 하면 context switching 오버헤드가 생기기에, spinning을 얼마나 오래 할 지에 따라 spinning을 할지, ready queue에 들어갈 지가 달라진다.

이렇게 lock 끝!!

condition variable

다른 스레드가 신호를 줄 때 내가 특정 코드 영역을 수행하고 싶음

while (initialized==0)
  ;
  
initialized = 1;

이렇게 코드를 짜면 ?
다른 스레드가 initialized = 1로 바꿀 때 내가 다른 코드를 수행할 수 있다는 충족시키지만, 내 스레드는 계속 while문에서 spinning하게 되므로 cpu 낭비!! initialize=0일 때는 그냥 스레드를 block시켜버리는 게 방법!!

여기서 나온 게 condition variable

conditional variable은 항상 3세트로 돌아가는데 필요한 게

• 1. conditional variable
• 2. state variable
• 3. lock

아니 conditional variable 하나 쓰는데 세개나 필요하다고? 싶을 수 있는데 왜 그런 지 하나 씩 설명해 줌

state variable이 없으면?

state variable이 없으면 부모 스레드가 child 스레드를 생성하고, cond_wait 하기 전에 child 스레드가 cond_signal을 한 후 죽으면 부모 스레드는 cond_wait으로 sleep하게 되고, 이제 더 이상 부모 스레드를 깨워 줄 스레드가 없게 됨

따라서 부모 스레드는 특정 state일때만 cond_wait을 하도록 state variable이 필요

lock이 없으면?

lock이 없을 때도 문제인 게, 아까 state variable과 비슷하게 조건을 만족해서 cond_wait하려는데 wait 하기 직전에 child 스레드가 스케줄링 돼서 cond_signal 후 죽으면, 부모는 cond_wait을 하고 깨워 줄 child 스레드가 없게 됨...

따라서 cond_wait, cond_signal 앞 뒤로 lock을 잡아서 부모 스레드가 cond_wait을 해서 lock을 놓아주어야만 child 스레드가 lock을 잡아서 cond_signal 할 수 있도록 해야 함.

state varaible check를 if문으로 하면?

conditional variable 관련 코드를 보면 전부 state varaible을 while문으로 체크한다. 도대체 왜 ? 그냥 조건 만족 안하면 cond_wait으로 sleep하게 하면 되지 않는가...

이는 producer와 consumer가 하나 씩일 때는 문제가 없다. 다만 producer가 한개인데 consumer가 여러 개일때 문제가 발생한다.

consumer1을 consumer2가 깨우게 된다면 consumer1은 바로 consume하려고 한다. consume할 게 없는 데도 말이다!

따라서 깨어나더라도 state를 한 번 더 체크해서 내가 진짜로 consume할 게 맞는 지 확인해야 한다. 즉, 조건 체크를 while문으로 하는 것이다!

producer와 consumer가 같은 conditional variable을 사용하면?

이제 state variable check까지 while문으로 체크하면 완벽한 producer, consumer가 될 거 같지만 아니다. 둘이 같은 conditional variable을 사용하기 때문에 Producer와 consumer는 같은 sleep queue에 들어가게 된다.

consumer는 consume을 한 후 producer에게 produce를 생산하라고 signal을 보내도, consumer가 producer보다 sleep queue의 앞에 있으면 consumer가 깨나게 된다! consumer는 자기가 consume할 게 없기에 sleep한다. 즉, 모든 스레드가 sleep 상태에 빠지게 된 것이다!!

따라서 producer queue 따로, consumer queue 따로 만들어야 한다. producer가 필요할땐 확실히 producer가 깨날 수 있게, consumer가 필요할 땐 확실히 consumer가 깨날 수 있게 하는 것이다.

즉, 두 개의 conditonal variable을 사용해야 한다.

I/O Device

컴퓨터는 항상 i/o device에 연결해서 사용된다. 그럼 그 i/o deviec들이 어떻게 이루어졌길래 컴퓨터와 소통할 수 있는지 알아보자.

configuration

i/o device는 기본적으로 status, command, data register를 갖고 있는데 이 레지스터 값을 갖고 os와 소통한다.

그 안에는 cpu, ram, chip 등이 있는데 이는 os가 알 바는 아니다. device가 알아서 작동한다. 즉, os 입장에서 i/o device는 status, command, data register로 abstraction 돼 있다.

동작 과정

1. process는 i/o device가 idle할때까지 기다린다
2. data를 data register에 작성한다.
3. command를 command register에 작성한다.
4. device는 할 일을 시작하고, process는 이게 끝날때까지 기다린다.

status check 과정

device의 상태를 체크하는 방법에는 두 가지가 있다.
cpu가 계속 status register를 확인할 수도 있고, busy하면 아예 process를 yield하는 방법이 있다.

spinning

뭐 뻔하지만 당연히 계속 status register를 체크하면 cpu time을 잡아 먹는다.

interrupt

또 뻔하지만 interrupt를 걸면, scheduling 알고리즘을 돌리고 context switching이 일어나기 때문에, 만약에 device가 금방 ready 상태가 될 거였으면 정말 낭비이다.
앞으로의 device는 interrupt 방법을 쓴다고 가정한다.

data register에 data 작성

Programmed I/O(PIO)

이는 cpu가 직접 data register에 data를 작성하는 방법이다. 당연하게도 쓸데 없이 cpu time을 잡아먹는다.

DMA(Direct Memory Access)

이는 cpu가 data의 주소값만 알려주면 DMA라는 hw가 직접 메모리에 가서 data를 가져와서 작성하는 방식이다!
앞으로의 device는 dma 방법을 쓴다고 가정한다.

os가 register에 read, write 하는 법

위에서 계속 status register를 체크한다, 어쩐다 했는데 os가 어떻게 device의 레지스터에 접근할 수 있는 걸까?
이는 두 가지 방법이 있다. : hw instruction, memory mapping

HW instruction

device register에 읽고 쓰는 hw instruction을 따로 두는 것이다! 뭐 제일 간단하게 할 수 있는 생각이다. x86에서는 in, out등의 instruction을 사용해서 이를 구현한다.

memory mapping

이는 device의 레지스터를 메모리의 커널 영역에 매핑해서 마치 메모리처럼 읽고 쓰지만, 사실은 register를 읽고 쓰는 것이다!

device driver

모든 i/o device는 위에서 말한 status check->command write->execute 방법을 따른다.

근데 i/o device가 진짜 진짜 많은데 os가 어떻게 그 device에 전부 일관되게 행동할 수 있는 걸까? 이는 device driver가 중간 매핑을 해주기 때문이다!

IDE device driver

예를 들어 ide device driver를 살펴보자
얘는 control register, command block register, status register, error register 이렇게 네 개의 레지스터를 갖는다. 그리고 기본적인 i/o flow는 다음과 같다.

1. status register를 체크한다.
2. command register에 parameter(block 개수, 위치 등)를 작성한다.
3. command register에게 read/write를 명령한다.
   (write의 경우) 3-1.data register에 작성을 한다.
4. interrupt handling을 한다.
5. error register를 체크해서 발생한 오류를 확인한다.

HDD

file system을 살펴보기에 앞서, 실제로 파일이 저장되는 hard disk에 대해 알아보도록 하자.

하드 디스크의 각 부품의 명칭은 이미 알고 있으니 넘어 가고 특징을 알아보자

seek time

seek time은 원하는 트랙을 찾는 시간으로, acceleration time + coasting time + deceleration time + setting time으로 나타낼 수 있다.

rotation delay

rotation time을 R이라고 하면, rotation delay = R/2이다

track skew

각 트랙의 숫자들이 이어질 때 어긋나 이어진 것을 뜻한다
arm이 이동할 때 disk도 돌아가는 것을 고려하여 이렇게 어긋나게 설계하였다

track buffer

disk block의 일부가 캐시된다

disk scheduling

disk에는 여러 Read/write request가 들어올텐데, 이를 스케줄링하는 알고리즘 역시 존재한다.

• FCFS : First Come First Served, 들어온 순서 대로 한다
• SSTF : Shortest Seek Time First. 현재 헤드에서 가장 가까운 순서대로 처리한다
• SCAN : disk 한 쪽 끝으로 이동하며 쭉 요청을 처리하고, 끝에 도달하면 다른 끝으로 쭉 이동하면서 요청을 처리한다
• C-SCAN : disk 한 쪽 끝으로 이동하며 쭉 요청을 처리하고, 끝에 도달하면 반대 끝으로 이동한 다음에 다시 헤드 쪽으로 이동하면서 요청을 처리한다
• C-LOOK : request 한 쪽 끝으로 이동하며 쭉 요청을 처리하고, request 한 쪽 끝에 도달하면, request 반대쪽 끝으로 이동한 다음, 다시 거기서부터 쭉 요청을 처리한다.

일반적으로는 SSTF를 많이 사용하는데, 당연히 scheduler가 preemptive해야 사용 가능하다. 다만 헤드에서 가까운 애들 먼저 처리하기에, 헤드에서 떨어져 있는 애들은 starvation이 생길 수 있다.

SCAN, C-SCAN은 heavy work load에 적합하다.

보통 SSTF, C-LOOK이 무난하다고 한다.

File and Directory

directory의 file의 일종이어서 disk data block에 기록된다. 이때 directory의 내용은 <file 이름, inode 번호>가 된다.

fsync()

프로그램이 write()시스템콜을 호출한다고 해도 바로 disk에 기록되는 것이 아니다. os는 작성할 것을 어느 정도 모았다가 한번에 disk에 write요청을 넣는다(write buffering)

하지만 disk에 write가 바로 보장돼야하는 경우가 있다. 이때 사용하는 것이 fsync(fd)이다. 이를 호출하면 fd가 가리키는 파일에 대한 disk write operation을 즉시 수행하도록 한다. 말 그대로 싱크를 맞추는 것이다.

hard link

파일을 생성하면 inode 역시 생성된다. file과 inode 사이에는 hard link가 연결된다.

$ echo hello > file1
$ ln file1 file2

위의 명령어를 linux 터미널 상에서 입력했다고 해보자.
먼저 file1을 만듦으로써 file1과 file1의 inode 상에는 하드 링크가 생성된다.
그 다음 ln file1 file2를 하면 file2와 file1의 inode와도 하드 링크가 생성된다.
즉, file1과 file2는 동일한 inode에 대해 hard link를 갖게 되고, file1과 file2는 해당 inode에 대한 다른 이름일 뿐이다.

remove link

link를 없애기 위해선 unlink(filename)을 호출하면 된다/
그럼 file name에 해당하는 inode의 link count를 1 줄이고 해당 hard link를 끊게 된다.
이때 link count==0이 되면, inode와 file이 작성된 disk block까지 해제시키게 된다

symbolic link

symbolic link는 hard link와 다르게 directory를 link시킬 수 있고, 다른 partition에 있는 파일과도 링크시킬 수 있다.

왜냐하면 src 파일의 절대경로와 link 를 시키기 때문이다.

$ echo hello > file1
$ ln -s file1 file2

위와 같이 터미널에 입력하면 ln -s file1 file2에서 file2의 inode를 생성하고, 이 inode는 file1의 절대 경로를 가리키게 된다.
즉, symbolic link는 포인터가 되는 것이다.
포인터이기에 dangling pointer 문제가 발생할 수 있다.
위 상태에서 rm file1을 하면, file2의 inode는 해제된 영역을 가리키게 되기 때문이다.