2021 06 19 (토)
1. 학습 날짜 : 20210619(토)
2. 학습 시간 : 14 : 00 ~
3. 학습 주제 : 식사하는 철학자 마무리, 사용가능 함수 정리, 우선순위큐, 힙 자료구조 정리
4. 동료 학습 방법 : 개인
5. 학습 목표 :
- Philosophers : 20210625(금) 까지 해결.
- 식사하는 철학자 자료 조사
- https://pages.mtu.edu/~shene/NSF-3/e-Book/index.html 에 있는 자료 더 읽어보기.
- 운영체제 관련 자료들 더 알아보기
- 철학자 과제 사용가능 함수들 조사
- 사용 가능 함수들 사용해보고, test 해보기
- semaphore, mutex 관련 개념,
- mutex
- semaphore
- Pthread
- 식사하는 철학자 자료 조사
- 자료구조
- 우선순위 큐 개념 이해
- 우선순위 큐 개념 정리
- 우선순위 큐 코드 이해
- 우선순위 큐 직접 짜보기 / 힙정렬 직접 해보기
6. 학습 내용 :
세마포어 추가 정리
세마포어의 용도 3가지( 가장 흔한 것 )
Lock
주로 binary Semaphore에 대한 얘기다.
mutex와는 다르게 semaphore는 초기값을 설정할 수 있다. mutex는 선언하고 초기화하는 순간 unlock상태로 존재하지만, semaphore는 초기화할 때 0으로 설정하면 처음부터 lock된 상태로 만들 수 있다.
조금 더 유연성이 있다.
그러나, semaphore는 mutex보다 자원을 많이 사용한다.
Countdown and Lock
공유자원에 대한 접근을 n개의 프로세스/쓰레드가 하지 못하도록 막으면서, 공유자원에 대한 접근을 프로세스/쓰레드 몇개가 하고있는지 keep track하기 위해 사용.
Notification :
A쓰레드와 B쓰레드의 사용 순서가 중요할 경우
counting semaphore는 race condition을 야기하는가?
질문글
There exists a semaphore, and semaphore can be used as "Binary semaphore" and "Counting semaphore" which is classified by initial value. I understand binary semaphore can prevent race condition by acting similarly as mutex(but two are not the same by various reasons.)
What i am curious about is that when we initialize the semaphore's value of more than or equal to 2, let's say n, then n values can enter the critical session. Then does this use of semaphore cause race condition?
I read articles about counting semaphores and it is considered that they are considered to keep track of the access to resources, and I'm confused about do we not use counting semaphore like this, and is counting semaphore not used to solve concurrency problems?
added below because my questions weren't detailed.
For example, when there are 100 threads, and I initialize
X=10, then initialize semaphore withsem_init(&s, 0, X), and if there is a critical session in threads' code flow, then doesn't it induce race condition because 10 threads are allowed to use resources and do through the threads' flow?답변 :
Because semaphores need not be acquired and released by the same thread, they can be used for asynchronous event notification (such as in signal handlers). And, because semaphores contain state, they can be used asynchronously without acquiring a mutex lock as is required by condition variables. However, semaphores are not as efficient as mutex locks.
By default, there is no defined order of unblocking if multiple threads are waiting for a semaphore.
Semaphores must be initialized before use, but they do not have attributes.
비동기적으로 사용될 수 있다고 하니 ,concurrency를 해결하는 데는 다른 용도로 사용되는듯 싶다.
concurrency보다는 resource 를 control의 용도로 많이 사용하는듯..
(정확히는 모르겠다)
세마포어를 사용한 식사하는 철학자 문제 해결
https://pages.mtu.edu/~shene/NSF-3/e-Book/SEMA/TM-example-philos-4chairs.html
데드락은 5명의 철학자 모두가 왼쪽 젓가락을 들기 때문에 발생한다. 만약 철학자 4명만 젓가락을 들 수 있게 하고, 남은 1명은 4명이 식사를 위해 자리에 앉았다면, 대기 상태로 만든다. 이러면 리소스-젓가락은 5개인데 비해서, 식사하는 사람은 4명이기 때문에, 데드락이 발생하지 않는다.
세마포어를 4로 초기화 시킨뒤, 각 젓가락은 하나의 쓰레드에서만 사용해야하기 떄문에, 5개 젓가락 모두 mutex lock을 걸어둔다.
4개의 프로세스/쓰레드만이 공유자원에 접근할 수 있게 하는 개념.. 을 제외하면 나머지는 이전 뮤텍스를 활용한 식사하는 철학자 문제와 동일하다.
사용 가능한 함수 정리, 함수 사용해보기
과제에서 사용 가능한 함수들 :
memset, printf, malloc, free, write,
usleep
,
gettimeofday
,
pthread_create, pthread_detach, pthread_join
,
pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_unlock
fork, kill, exit, sem_open, sem_close, sem_post, sem_wait, sem_unlink
usleep
int usleep(\useconds_t*useconds)* : 해당 프로세스/쓰레드가 마이크로초동안 대기상태에 있도록 한다. 정확히는, 프로세스/쓰레드를 wait()를 사용해서 wait 상태로 바꾼다. 시그널을 사용해서 쓰레드를 깨울 수 있다.
usleep()is implemented using an interruptiblewait()function, and does not use signals. Hence there are no interactions withSIGALRMhandling
The usleep() function shall cause the calling thread to be suspended from execution until either the number of realtime microseconds specified by the argument useconds has elapsed or a signal is delivered to the calling thread and its action is to invoke a signal-catching function or to terminate the process.
https://pubs.opengroup.org/onlinepubs/009604599/functions/usleep.html
The useconds argument shall be less than one million.
이라고 하는데, 밑의 예제에서 1000 * 1000 * 0을 줘도 잘 돌아간다.
#include <stdio.h>
#include <unistd.h>
int main()
{
unsigned int usec = 1000 * 1000 * 10;
printf("Before waiting %u usec \n", usec);
//fflush()
usleep(usec);
printf("AFTER waiting %u usec \n", usec);
}gettimeofday
소스로직 중 특정구간의 수행시간 차이를 계산하기 위해 마이크로 단위의 시간 함수 gettimeofday 를 지원합니다.
gettimeofday(2)함수는 1970-01-01 00:00:00 +0000 (UTC) 이후의 현재까지의 경과된 초와 micro초(백만분의 1초) 값을 얻는 함수입니다
#include <sys/time.h>
#include <unistd.h>
int gettimeofday(struct timeval *tv, struct timezone *tz);1번째 인자는 timeval 구조체로, 아래와 같이 선언되어있다.
tv_sec : 1970년 1월을 기준으로 지난 시간을 반환한다.
tv_usec : 이하 동일. 단, sec 대신 마이크로초.
struct timeval
{
long tv_sec; // 초
long tv_usec; // 마이크로초
}2번째 인자도 구조체다. 모종의 이유로 timezone 구조체는 사용되지 않으며, gettimeofday(tv, NULL) 과 같이 사용한다.
struct timezone
{
int tz_minuteswest: // 그리니치 서측분차
int tz_dsttime; // DST 보정타입(일광 절약시간)
}
#include <stdio.h>
#include <unistd.h>
#include <sys/time.h>
int main()
{
struct timeval start_time, end_time, interv_time;
gettimeofday(&start_time, NULL);
printf("sec : %ld\tusec : %d\n", start_time.tv_sec, start_time.tv_usec);
usleep(1000 * 1000 * 5);
gettimeofday(&interv_time, NULL);
printf("sec : %ld\tusec : %d\n", interv_time.tv_sec, interv_time.tv_usec);
usleep(1000 * 1000 * 5);
gettimeofday(&end_time, NULL);
printf("sec : %ld\tusec : %d\n", end_time.tv_sec, end_time.tv_usec);
}
sec: 1624091712 usec : 923539
sec : 1624091717 usec : 927250
sec : 1624091722 usec : 928240대략 5초정도 지난것 확인 가능. (정확히 5초는 아님)
쓰레드 생성 함수들 : pthread_create, pthread_detach, pthread_join
printf는 thread-safe 하지 않습니다.
#include <stdio.h>
#include <unistd.h>
#include <sys/time.h>
#include <pthread.h>
void *thread_entry(void *arg)
{
int i;
pthread_t tid;
int thread_number;
tid = pthread_self();
thread_number = (int)arg;
i = 0;
while (i < 7)
{
printf("new_thread_%d's tid : %d\t\t incremented : %d\n", thread_number, tid, i);
i++;
}
return NULL;
}
int main()
{
pthread_t tid[5];
int thread_count;
int i;
i = 0;
thread_count = 0;
while (thread_count < 5)
{
tid[thread_count] = pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)thread_count);
thread_count++;
}
while (i < 10)
{
printf("main_thread's tid : %d\t\t, incremented : %d\n", pthread_self(), i);
i++;
}
thread_count = 0;
while (thread_count < 5)
pthread_join(tid[thread_count], NULL);
i = 0;
while (i < 5)
{
printf("MAIN_THREAD : subthread id : %d\t", tid[i]);
i++;
}
printf("\n");
}위 코드를 컴파일 했을 때 4가지 종류의 오류 발생
func.c:17:76: warning: format specifies type 'int' but the argument has type 'pthread_t' (aka 'struct _opaque_pthread_t *') [-Wformat]
printf("new_thread_%d's tid : %d\t\t incremented : %d\n", thread_number, tid, i);
~~ ^~~
func.c:20:1: warning: non-void function does not return a value [-Wreturn-type]
}
^
func.c:33:86: warning: cast to 'void *' from smaller integer type 'int' [-Wint-to-void-pointer-cast]
tid[thread_count] = pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)thread_count);
^
func.c:33:21: warning: incompatible integer to pointer conversion assigning to 'pthread_t' (aka 'struct _opaque_pthread_t *') from 'int' [-Wint-conversion]
tid[thread_count] = pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)thread_count);
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
func.c:38:60: warning: format specifies type 'int' but the argument has type 'pthread_t _Nonnull' (aka 'struct _opaque_pthread_t *') [-Wformat]
printf("main_thread's tid : %d\t\t, incremented : %d\n", pthread_self(), i);
~~ ^~~~~~~~~~~~~~
func.c:47:47: warning: format specifies type 'int' but the argument has type 'pthread_t' (aka 'struct _opaque_pthread_t *') [-Wformat]
printf("MAIN_THREAD : subthread id : %d\t", tid[i]);
~~ ^~~~~~오류 1 : pthread_t tid를 printf로 뽑으려 했지만, 자료형이 int형이 아니다.
printf("new_thread_%d's tid : %lud\t\t incremented : %d\n", thread_number, tid, i);해결 : 강제형변환으로 해결.
printf("new_thread_%d's tid : %lud\t\t incremented : %d\n", thread_number, (unsigned long)tid, i)오류 2 : pthread_create() 반환값의 오용
tid[thread_count] = pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)thread_count);해결 : 반환값 수정.
pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)thread_count);오류 3 : pthread_create() 의 마지막 인자를 void형 포인터로 캐스팅해줌에 따라 포인터로 줘야하는데, int형인 상태로 주었음.
pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)thread_count);해결 : pthread_create()마지막 인자 수정. -> 그에 따른 thread_entry() 수정.
pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)&thread_count);결과 :
new_thread_4's tid : 70000218f000 incremented : 0new_thread_4's tid : 70000218f000 incremented : 1new_thread_4's tid : 70000218f000 incremented : 2new_thread_4's tid : 70000218f000 incremented : 3new_thread_4's tid : 70000218f000 incremented : 4new_thread_4's tid : 70000218f000 incremented : 5new_thread_4's tid : 70000218f000 incremented : 6main_thread's tid : 1127dfdc0 , incremented : 0 main_thread's tid : 1127dfdc0 , incremented : 1main_thread's tid : 1127dfdc0 , incremented : 2main_thread's tid : 1127dfdc0 , incremented : 3main_thread's tid : 1127dfdc0 , incremented : 4main_thread's tid : 1127dfdc0 , incremented : 5main_thread's tid : 1127dfdc0 , incremented : 6main_thread's tid : 1127dfdc0 , incremented : 7main_thread's tid : 1127dfdc0 , incremented : 8main_thread's tid : 1127dfdc0 , incremented : 9new_thread_5's tid : 700002212000 incremented : 0new_thread_5's tid : 700002212000 incremented : 1new_thread_5's tid : 700002212000 incremented : 2new_thread_5's tid : 700002212000 incremented : 3new_thread_5's tid : 700002212000 incremented : 4 #tid : 700002212000 new_thread_5's tid : 70000239b000 incremented : 0 #tid : 70000239b000 new_thread_5's tid : 70000239b000 incremented : 1 #tid가 다른데 new_thread_5라고 표현됨. ---> context switching이 일어났기 때문이라고 사료됨. new_thread_5's tid : 70000239b000 incremented : 2new_thread_5's tid : 70000239b000 incremented : 3new_thread_5's tid : 70000239b000 incremented : 4new_thread_5's tid : 70000239b000 incremented : 5new_thread_5's tid : 70000239b000 incremented : 6new_thread_5's tid : 700002295000 incremented : 0new_thread_5's tid : 700002295000 incremented : 1new_thread_5's tid : 700002295000 incremented : 2new_thread_5's tid : 700002295000 incremented : 3new_thread_5's tid : 700002295000 incremented : 4new_thread_5's tid : 700002295000 incremented : 5new_thread_5's tid : 700002295000 incremented : 6new_thread_5's tid : 700002212000 incremented : 5new_thread_5's tid : 700002212000 incremented : 6new_thread_5's tid : 700002318000 incremented : 0new_thread_5's tid : 700002318000 incremented : 1new_thread_5's tid : 700002318000 incremented : 2new_thread_5's tid : 700002318000 incremented : 3new_thread_5's tid : 700002318000 incremented : 4new_thread_5's tid : 700002318000 incremented : 5new_thread_5's tid : 700002318000 incremented : 6MAIN_THREAD : subthread id : 70000218f000 MAIN_THREAD : subthread id : 700002212000 MAIN_THREAD : subthread id : 700002295000 MAIN_THREAD : subthread id : 700002318000 MAIN_THREAD : subthread id : 70000239b000그리고, tid가 보기 불편하기 때문에, 이를 고쳐줬다.
결과 : Thread는 잘 만들어진 것을 확인할 수 있었으나, tid : 700002212000 일때나 tid : 70000239b000일 때나, new_thread_5라고 표현되었다. 이는 각각의 thread가 만들어지고 난 뒤, wait상태로 진입하고, main thread에서 인자가 증가된 상태로 running 되었기 때문인 것으로 사료된다. 쓰레드를 만들어주는 과정 + i를 증가시키는 과정 자체가 atomic하지 않기 때문이며, 이를 해결하기 위해서 추후 lock을 걸어준 뒤, 다시 생각해보도록한다.
pthread_join을 사용하지 않은 상황 :
subthread가 flow를 마치고 나면, tid : 56fe000 completed 와 같이 끝냈다고 뽑아주도록 했는데, 4개의 쓸레드만 끝난 상황. 메인쓰레드가 끝났기 떄문에, 남은 하나의 쓰레드는 실행되지 않았다.
쓰레드가 적기 때문에, 5개 쓰레드 모두 마지막 control flow까지 진행하고, 종료 될 때도 있다.
또, join을 했을 때와 달리, 아래 출력이 모든 subthread가 실행을 마친 뒤 출력되지 않고, 중간에 출력된다.
MAIN_THREAD : subthread id : 5575000 MAIN_THREAD : subthread id : 55f8000 MAIN_THREAD : subthread id : 567b000 MAIN_THREAD : subthread id : 56fe000 MAIN_THREAD : subthread id : 5781000
pthread_detach 사용방법
자원 측면에서 main_thread와 독립적으로 운용하라고 명령함. 자원 회수를 자율적으로 하라고 명령.
- pthread_attr_t를 사용해서 thread의 속성을 설정한 뒤, thread를 속성에 따라 만드는 방법
- pthread_deatch 를 활용하는 방법
선호되는 방식은 1번 방식이 선호됨. 쓰레드 진행중에 속성을 바꾸어버리기 때문..
main쓰레드가 먼저 끝난뒤, 자원이 반환되지 못할 여지가 존재한다.
각 쓰레드를 독립적으로 운용하라고 명령했기 때문에, main쓰레드는 subthread가 종료될 때 까지 기다리지 않는다.
공유자원 접근제어 : pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_unlock
공유자원 접근제어가 되지 않을 떄 :
while (i < 10000)를 while (i < 100000000)으로 바꿔줌--> 너무 많아서 대충 1000000으로 하기로함
IN MAIN_THREAD : final shared resource == 4999901.원래라면 5개의 subthread에서 1000000개를 각각 더해주었어야 할 연산결과가 공유자원에 대한 접근제어가 되지 않았기에 (상호배제 - mutual exclusion) 최종 연산결과가 5000000개를 넘지 못했다.
공유자원 접근제어가 되었을 때 :
void *thread_entry(void *arg){ pthread_t tid; int i; tid = pthread_self(); i = 0; while (i < 1000000) { pthread_mutex_lock(&mutex); shared_resource++; pthread_mutex_unlock(&mutex); printf("tid : %lx\t\t shared_resource : %d\n", (unsigned long)tid % 10, shared_resource); i++; } return NULL;}나머지 위 코드와 동일.
결과
IN MAIN_THREAD : final shared resource == 5000000critical session에 대해서 mutual exclusion을 행해줬기 때문에 서로의 연산에 간섭받지 않았다.
pthread_create 사용시, 인자로 index를 넘겨주어 thread에 인덱싱하기
#include <stdio.h>
#include <sys/time.h>
#include <pthread.h>
#include <unistd.h>
#define TOTAL_THREAD 5
static int shared_resource;
pthread_mutex_t mutex;
pthread_mutex_t mutex_1; //new lock/mutex
void *thread_entry(void *arg)
{
pthread_t tid;
int i;
int *a;
a = (int *)arg;
tid = pthread_self();
i = 0;
while (i < 1000000)
{
pthread_mutex_lock(&mutex);
shared_resource++;
pthread_mutex_unlock(&mutex);
printf("tid_%d : %lx\t\t shared_resource : %d\n", *a, (unsigned long)tid % 10, shared_resource);
i++;
}
return NULL;
}
int main()
{
shared_resource = 0;
int thread_count;
int i;
pthread_t tid[TOTAL_THREAD];
thread_count = 0;
i = 0;
pthread_mutex_init(&mutex, NULL);
pthread_mutex_init(&mutex_1, NULL); //new mutex
while (thread_count < TOTAL_THREAD)
{
pthread_mutex_lock(&mutex_1); //lock
pthread_create(tid + thread_count, NULL, (void *)thread_entry, (void *)&thread_count);
thread_count++;
pthread_mutex_unlock(&mutex_1); //unlock
}
thread_count = 0;
while (thread_count < TOTAL_THREAD)
{
pthread_join(tid[thread_count], NULL);
thread_count++;
}
printf("IN MAIN_THREAD : final shared resource == %d\n", shared_resource);
}
tid_0 : 8 shared_resource : 220384
tid_0 : 8 shared_resource : 220385
tid_0 : 6 shared_resource : 220374
tid_0 : 0 shared_resource : 220371
tid_0 : 4 shared_resource : 220360
tid_0 : 2 shared_resource : 220373
tid_0 : 8 shared_resource : 220386
tid_0 : 6 shared_resource : 220387
tid_0 : 6 shared_resource : 220392
tid_0 : 6 shared_resource : 220393
tid_0 : 6 shared_resource : 220394
tid_0 : 6 shared_resource : 220395
tid_0 : 0 shared_resource : 220388
tid_0 : 4 shared_resource : 220389
tid_0 : 4 shared_resource : 220398
tid_0 : 8 shared_resource : 220391
tid_0 : 8 shared_resource : 220400
tid_0 : 8 shared_resource : 220401
tid_0 : 8 shared_resource : 220402
tid_0 : 4 shared_resource : 220399
tid_0 : 6 shared_resource : 220396
tid_0 : 6 shared_resource : 220405모든 tid가 0으로 초기화되는 상황 발생.
같은 포인터를 주고 있는데, 값이 증가가 안되나보다..
값이 왜 증가가 안되는지는 모르겠다.
thread의 argument 오류 : 해결 못함
sem_open, sem_close, sem_post, sem_wait, sem_unlink
Posix, SystemV 로 세마포어를 사용하려면 다른 조작이 필요하다. 두 버전만의 장단점이 있으며, 함수가 다르다.
우리 과제에서 사용할 세마포어 관련 함수들은 Posix를 따르기 때문에, SystemV 세마포어 함수는 사용하지 않는다.
오늘은 여기까지...
학습에 도움된 사이트 :
| 주제 | 사이트 | 비고 |
|---|---|---|
| 세마포어를 활용한 식사하는 철학자 문제 해결방법 | https://pages.mtu.edu/~shene/NSF-3/e-Book/SEMA/TM-example-philos-4chairs.html | |
| usleep | https://www.mkssoftware.com/docs/man3/usleep.3.asp | |
| get_time_of_day | https://www.it-note.kr/130 | |
| Pthread_* 함수들 | https://reakwon.tistory.com/56 | |
| 쓰레드 소개 글 | https://www.joinc.co.kr/w/Site/system_programing/Book_LSP/ch07_Thread | |
| mutex 소개 글 | https://www.joinc.co.kr/w/Site/Thread/Beginning/Mutex | |
오늘 발견한 문제와 해결방안:
- 의외로 진도를 뺴지 못함.
7. 학습 총평 :
- 세마포어, mutex, pthread, concurrency 관련 문제들은 예전에 본적이 있었지만 가물가물함.
- 운영체제에 대한 전반적인 이해가 다시 필요할 것으로 보인다.
- 운영체제 다시 보자...
8. 다음 학습 계획 :
- 세마포어 관련 함수들 정리, 세마포어 활용해서 deadlock막고, concurrency 문제 해결.
- 세마포어 관련 함수 정리와 예제를 만들고 나면, Philosophers 설계..
- Philosophers가 끝나면 운영체제 다시 정리하기.
- 우선순위큐와 힙 정리가 끝나는대로 분리집합 ADT 공부.
- 일요일에는 트리구조에 대한 공부 필요.
- Exam02 공부하기.