Microsoft PowerPoint - ch Muti_Thread_보충설명

Size: px
Start display at page:

Download "Microsoft PowerPoint - ch Muti_Thread_보충설명"

Transcription

1 2015 yuantl Ch Multi-Thread 2015 년 6 월 5 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : ; Fax : ytkim@yu.ac.kr)

2 Outline 프로세스와스레드 Task 수행이병렬로처리되어야하는경우 왜다중프로세스 / 다중스레드가필요한가? 다중프로세스와다중스레드의차이점 Windows 환경에서의다중스레드생성, 초기화및종료 다중스레드로의파라메터전달 큐를이용한다중스레드간의데이터전달 Critical Section을사용한다중스레드간의동기화 turn semaphore를사용한실행순서관리 간단한다중스레드의예제 ch

3 프로세스 (Process) Process 프로세스 (process) 란프로그램이수행중인상태 (program in execution) 각프로세스마다개별적으로메모리가할당됨 (text core, initialized data (BSS), noninitialized data, heap (dynamically allocated memory), stack) 일반적인 PC 나대부분의컴퓨터환경에서하나의물리적인 CPU 상에다수의프로세스가실행되는 Multi-tasking 이지원되며, 운영체제가다수의프로세스를일정시간마다실행기회를가지게하는테스크스케쥴링을지원 하나의프로세스가실행을중단하고, 다른프로세스가실행될수있게하는것을컨텍스트스위칭 (Context switching ) 이라하며, 운영체제의 process scheduling & switching가이를담당함 하나의물리적인 CPU가사용되는시스템에서는임의의순간에는하나의프로세스만실행되나, 일정시간 ( 예 : 100ms) 마다프로세스가교체되며실행되기때문에전체적으로다수의프로그램들이동시에실행되는것과같이보이게됨 ch

4 스레드 (Thread) 스레드 (Thread) 스레드는하나의프로세스내부에포함되는함수들이동시에실행될수있게한작은단위프로세서 (lightweight process) 기본적으로 CPU를사용하게하는기본단위 하나의프로세스에포함된다수의스레드들은프로세스의메모리자원들 (code section, data section, Heap 등 ) 과운영체제의자원들 ( 예 : 파일입출력등 ) 을공유함 ch

5 프로세스 (Process) 와스레드 (Thread) 의차이점 스레드 (Thread) 란? 어떠한프로그램내에서, 특히프로세스 (process) 내에서실행되는흐름의단위. 일반적으로한프로그램은하나의 thread를가지고있지만, 프로그램환경에따라둘이상의 thread를동시에실행할수있다. 이를멀티스레드 (multithread) 라한다. 프로세스는각각개별적인 code, data, file을가지나, 스레드는자신들이포함된프로세스의 code, data, file들을공유함 ch

6 Task 수행이병렬로처리되어야하는경우 양방향동시전송이지원되는멀티미디어정보통신응용프로그램 (application) full-duplex 실시간전화서비스 : 상대편의음성정보를수신하면서, 동시에나의음성정보를전송하여야함 음성정보의입력과출력이동시에처리될수있어야함 영상정보의입력과출력이동시에처리될수있어야함 ch

7 실시간화상전화기의기능블럭도 User Input & Output MIC/Camera USER A (Client Mode) Speaker/Monitor Input Output User Input & Output MIC/Camera USER B (Server Mode) Speaker/Monitor Input Output MIC Camera Speaker Monitor MIC Camera Speaker Monitor ReadAudioThread() - ReadStream() - Create RTP Packet -Set RTP Packet ReadVideoThread() -CvCapture() - Create RTP Packet -Set RTP Packet streamapp WriteAudioThread() - WriteStream() - Set Sync Time Shared SyncTime WriteVideoThread() -ShowImage() - Read Sync Time ReadAudioThread() - ReadStream() - Create RTP Packet -Set RTP Packet ReadVideoThread() -CvCapture() - Create RTP Packet -Set RTP Packet streamapp WriteAudioThread() - WriteStream() -Set Sync Time Shared SyncTime WriteVideoThread() -ShowImage() - Read Sync Time Audio Buffer Video Buffer Audio Buffer Video Buffer Audio Buffer Video Buffer Audio Buffer Video Buffer SendThread() - Compare Timestamp video/audio ReceiveThread() - Identify video/audio SendThread() - Compare Timestamp video/audio ReceiveThread() - Identify video/audio - Sendto() - Recvfrom() - Sendto() - Recvfrom() RTP Datagram UDP Socket sendto() recvfrom() Tx Rx RTP Datagram UDP Socket sendto() recvfrom() Tx Rx ch

8 양방향동시전송 (full-duplex) Twitter User A (Client mode: Account User or Follower) Input Message using MFC GUI Simple Twitter Client Display received Message using MFC GUI User B (Server mode) Simple Twitter Server Receive Message, Classify Message, and multi-cast or uni-cast message StreamApp StreamApp SendMsg() - create AppPDU - calculate checksum - enqueue() TxQueue TCB wnd, rwnd,cwnd, accmack,elps_t, SeqNo, ThreadSendPDU() - dequeue() -SendTo() - delete Acked PDUs - retransmit time-out PDUs Thread Timer ACK Flow & Error Control ThreadReassemblePDU() -dequeue() -displaymsg() ThreadRecvPDU() -RecvFrom() - verify checksum - enqueue() RxQueue SendMsg() - create AppPDU - calculate checksum - enqueue() TxQueue TCB wnd, rwnd,cwnd, accmack,elps_t, SeqNo, ThreadSendPDU() - dequeue() -SendTo() - delete Acked PDUs - retransmit time-out PDUs Thread Timer ACK Flow & Error Control ThreadReassemblePDU() - dequeue() - displaymsg() ThreadRecvPDU() -RecvFrom() - verify checksum - enqueue() RxQueue Datagram UDP Socket Datagram UDP Socket SendTo() RecvFrom() SendTo() RecvFrom() Tx Rx Tx Rx ch

9 스레드함수의구현 스레드의생성및초기화 프로그램에포함되는함수중, 병렬로실행되어야하는함수를스레드로지정 파라메터구조체포인터를통하여, 스레드생성및실행에관련된정보를 main() 함수로부터전달받으며, 파라메터구조체는필요에따라정의 스레드는보통지정된회수만큼실행을하거나, 무한루프로실행함 스레드함수의예 DWORD WINAPI Thread_producer(LPVOID pparam) ThreadParam *pthrparam; /*void* 자료형으로스레드에전달된인자를형변환을통해 pthrparam 구조체로변환 */ pthrparam = (ThreadParam *)pparam;.... while (1) ch

10 스레드함수로의파라메터전달 스레드파라메터전달을위한구조체정의 ( 예 ) 필요에따라파라메터항목들을포함하는구조체정의 기본적으로 Critical section에관련된정보, 공유되는큐의정보, 파일입출력에관련된정보를포함 typedef struct ThreadParam Circular_Int_Queue *queue; CRITICAL_SECTION* pcs; int role; ThreadParam; typedef struct ThreadParam CRITICAL_SECTION *pcs; Queue *pq; ROLE role; // unsigned int addr; int max_queue; int duration; FILE *fout; ThreadParam; ch

11 스레드간의정보전달 큐를사용한정보전달 스레드간에정보 / 메시지 / 신호를전달하기위하여 FIFO 동작을수행하는 queue를사용 Queue의 end에정보를추가하는 enqueue() Queue의 front에있는정보를추출하는 dequeue() Queue는다수의스레드가공유하는자원 (shared resource) 이며, 임계구역 (critical section) 으로보호되어야함 PacketGen() 1 Queue (shared resource, critical section) PacketGen() 2 linktx() PacketGen() 3 ch

12 Critical Section (1) Critical section 다중스레드사용을지원하는운영체제는프로그램실행중에스레드또는프로세스간에교체가일어날수있게하여, 다수의스레드 / 프로세스가병렬로처리될수있도록관리 Context switching이일어나면, 현재실행중이던스레드 / 프로세스의중간상태가임시저장되고, 다른스레드 / 프로세스가실행됨 프로그램실행중에특정구역은실행이종료될때까지스레드 / 프로세서교체가일어나지않도록관리하여야하는경우가있음 아래의스레드예에서 critical section으로보호하여야할구역은? Thread_Deposit (int deposit) // account is shared variable cur_account = account; cur_account = cur_account + deposit; account = cur_account; print(account);.... 은행잔고 account Thread_Withdraw (int withdraw) // account is shared variable cur_account = account; cur_account = cur_account - withdraw; account = cur_account; print(account);.... ch

13 Critical Section (2) Critical section 를현재어떤스레드 / 프로세스가실행중에있다는상태를 Critical section 을표시하는변수로표시 semaphore 라고부르기도함 Critical section 을표시하는변수의설정 InitializeCriticalSection(LPCRITICAL_SECTION lpcriticalsection) initialization of critical section must be called before using EnterCriticalSection(), LeaveCriticalSection() Critical section 영역지정 EnterCriticalSection(LPCRITICAL_SECTION lpcriticalsection) LeaveCriticalSection(LPCRITICAL_SECTION lpcriticalsection) the procedures between these two functions are defined as critical section Critical section 을표시하는변수의소멸 DeleteCriticalSection(LPCRITICAL_SECTION lplcriticalsection) delete the critical section flag executed at the process exit ch

14 스레드의종료 (1) MS-Windows 환경에서의스레드소멸및관리를위한함수들 생성된스레드가스스로함수실행을종료할때까지기다리거나, 지정된시간이후에강제종료를시킬수있음 WaitForSingleObject() 와 TerminateThread() 함수를사용 HANDLE m_hthread; m_hthread = CreateThread(NULL, 0, Thread_Function_Name, pthrdparam, 0, NULL);.... // 생성된스레드가별도로실행이됨 DWORD nexitcode = NULL; GetExitCodeThread(m_hThread, &nexitcode); WaitForSingleObject(m_hthread, THRD_EXE_TIME_MS); // wait for terminate thread TerminateThread(m_hThread, nexitcode); CloseHandle(m_hThread); ch

15 스레드의종료 (2) 스레드가스스로종료할때까지기다리는경우 main() 함수에서는무한대시간 (INFINITIVE) 으로기다림 WaitForSingleObject(m_hthread, INFINITIVE); // wait for terminate thread TerminateThread(m_hThread, nexitcode); 스레드를일정시간동안실행하게한후, 강제종료를시키는경우 #define THRD_EXE_TIME_MS 5000 // mili-second 단위의시간 WaitForSingleObject(m_hthread, THRD_EXE_TIME_MS); // wait for terminate thread TerminateThread(m_hThread, nexitcode); ch

16 Two Simple Threads version 1 thread_main() create thread_a() create thread_b() print thread_m :: MMMM thread_a() print thread_a :: AAAA thread_b() print thread_b :: BBBB ch

17 /* SimpleThreadsVer1.cpp (1) */ #include<stdio.h> #include<windows.h> #include<time.h> enum ROLE PRODUCER, CONSUMER ; typedef struct ThreadParam char mark; ThreadParam; DWORD WINAPI Thread_A(LPVOID pparam); DWORD WINAPI Thread_B(LPVOID pparam); void main() /* 변수선언 */ ThreadParam *pthrparam; /* 각스레드로전달될파라미터구조체 */ HANDLE hthread_a, hthread_b; /* 스레드정보를관리하게될핸들러변수 */ DWORD nexitcode = NULL; /* thread_a 에전달될파라미터값초기화 */ pthrparam = (ThreadParam*)malloc(sizeof(ThreadParam)); pthrparam->mark = 'A'; /* CreateThread API 를이용하여 Thread 생성과전달할인자를전달한후반환되어지는해당 Thread 에대한정보를 hthread_a 핸들러에저장 */ hthread_a = CreateThread(NULL, 0, Thread_A, pthrparam, 0, NULL); ch

18 /* SimpleThreadsVer1.cpp (2) */ /* thread_b 에전달될파라미터값초기화 */ pthrparam = (ThreadParam*)malloc(sizeof(ThreadParam)); pthrparam->mark = B'; hthread_b = CreateThread(NULL, 0, Thread_B, pthrparam, 0, NULL); /* main() thread 실행 */ char mark = M ; for (int i = 0; i < 100; i++) printf("thread_main... "); for (int j = 0; j < 50; j++) printf("%c", mark); printf(" n"); /* main 스레드가생성한 thread_a 가스스로종료할때까지대기 */ WaitForSingleObject(hThread_A, INFINITE); GetExitCodeThread(hThread_A, &nexitcode); TerminateThread(hThread_A, nexitcode); /* thread_a 종료 */ CloseHandle(hThread_A); /* 스레드핸들러종료 */ /* main 스레드가생성한 thread_b 가스스로종료할때까지대기 */ WaitForSingleObject(hThread_B, INFINITE); GetExitCodeThread(hThread_B, &nexitcode); TerminateThread(hThread_B, nexitcode); /* thread _B 종료 */ CloseHandle(hThread_B); /* 스레드핸들러종료 */ ch

19 /* SimpleThreadsVer1.cpp (3) */ DWORD WINAPI Thread_A(LPVOID pparam) ThreadParam *pthrparam = (ThreadParam *)pparam; int data = 0; int sleep_time_ms = 0; char mark = pthrparam->mark; for (int i = 0; i < 100; i++) printf("thread_a... "); for (int j = 0; j < 50; j++) printf("%c", mark); printf(" n"); return 0; /* SimpleThreadsVer1.cpp (4) */ DWORD WINAPI Thread_B(LPVOID pparam) ThreadParam *pthrparam = (ThreadParam *)pparam; char mark = pthrparam->mark; for (int i = 0; i < 100; i++) printf("thread_b... "); for (int j = 0; j < 50; j++) printf("%c", mark); printf(" n"); return 0; ch

20 실행결과 thread_a, thread_b, thread_main 이일정시간마다번갈아가며실행 한줄이다출력되기전에 thread간의교체가발생되어, 출력이섞임 만약, 한번에 thread 하나가한줄씩만출력하고, 번갈아가며출력하기위해서는어떻게수정하여야하나? critical section 사용 : 한줄을다출력할때까지, 다른스레드가실행되지못하도록보호 turn semaphore 사용 : 한줄을다출력한후에는반드시다른스레드가실행되도록실행순서 (turn) 제어 ch

21 Two Simple Threads version 2 thread_main() create thread_a() create thread_b() CRITICAL_SECTION crit EnterCriticalSection() print thread_m :: MMMM LeaveCriticalSection() thread_a() EnterCriticalSection() print thread_a :: AAAA LeaveCriticalSection() thread_b() EnterCriticalSection() print thread_b :: BBBB LeaveCriticalSection() ch

22 /* SimpleThreadsVer2.cpp (1) */ #include<stdio.h> #include<windows.h> #include<time.h> enum ROLE PRODUCER, CONSUMER ; typedef struct ThreadParam CRITICAL_SECTION* pcs; char mark; ThreadParam; DWORD WINAPI Thread_A(LPVOID pparam); DWORD WINAPI Thread_B(LPVOID pparam); void main() /* 변수선언 */ CRITICAL_SECTION crit; ThreadParam *pthrparam; HANDLE hthread_a, hthread_b; DWORD nexitcode = NULL; /* 변수초기화 */ InitializeCriticalSection(&crit); /* SimpleThreadsVer2.cpp (2) */ /* Consumer 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*) malloc(sizeof(threadparam)); pthrparam->pcs = &crit; pthrparam->mark = 'A'; hthread_a = CreateThread(NULL, 0, Thread_A, pthrparam, 0, NULL); /* Producer 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*) malloc(sizeof(threadparam)); pthrparam->pcs = &crit; pthrparam->mark = 'B'; hthread_b = CreateThread(NULL, 0, Thread_B, pthrparam, 0, NULL); WaitForSingleObject(hThread_A, INFINITE); GetExitCodeThread(hThread_A, &nexitcode); TerminateThread(hThread_A, nexitcode); CloseHandle(hThread_A); WaitForSingleObject(hThread_B, INFINITE); GetExitCodeThread(hThread_B, &nexitcode); TerminateThread(hThread_B, nexitcode); CloseHandle(hThread_B); DeleteCriticalSection(&crit); ch

23 /* SimpleThreadsVer2.cpp (3) */ DWORD WINAPI Thread_A(LPVOID pparam) ThreadParam *pthrparam; pthrparam = (ThreadParam *)pparam; char turn = ' 0'; char mark = pthrparam->mark; for (int i = 0; i < 20; i++) EnterCriticalSection(pThrParam->pCS); printf("thread_a... "); for (int j = 0; j < 50; j++) printf("%c", mark); printf(" n"); LeaveCriticalSection(pThrParam->pCS); Sleep(100); printf("thread_a finished... n"); return 0; /* SimpleThreadsVer2.cpp (4) */ DWORD WINAPI Thread_B(LPVOID pparam) ThreadParam *pthrparam; pthrparam = (ThreadParam *)pparam; char mark = pthrparam->mark; char turn; for (int i = 0; i < 20; i++) EnterCriticalSection(pThrParam->pCS); printf("thread_b... "); for (int j = 0; j < 50; j++) printf("%c", mark); printf(" n"); LeaveCriticalSection(pThrParam->pCS); Sleep(100); printf("thread_b finished... n"); return 0; ch

24 실행결과 (ver 2) critical section을사용하여, 하나의스레드가한줄의출력을완전히완료할때까지다른스레드가실행되지못하게보호 thread_a 또는 thread_b가두줄씩출력하는경우가있음 각스레드가한번에한줄씩만출력하게하는방법은? ch

25 Two Simple Threads version 3 thread_main() create thread_a(); create thread_b(); CRITICAL_SECTION crit char turn = A ; wait until (turn == M ) EnterCriticalSection() print thread_m :: MMMM turn = A ; LeaveCriticalSection() thread_a() wait until (*pturn == A ) EnterCriticalSection() print thread_a :: AAAA *pturn = B ; LeaveCriticalSection() thread_b() wait until (*pturn == B ) EnterCriticalSection() print thread_b :: BBBB *pturn = M ; LeaveCriticalSection() ch

26 /* SimpleThreadsVer3.cpp (1) */ #include<stdio.h> #include<windows.h> #include<time.h> enum ROLE PRODUCER, CONSUMER ; typedef struct ThreadParam CRITICAL_SECTION* pcs; char mark; char *pturn; ThreadParam; DWORD WINAPI Thread_A(LPVOID pparam); DWORD WINAPI Thread_B(LPVOID pparam); void main() /* 변수선언 */ CRITICAL_SECTION crit; ThreadParam *pthrparam; HANDLE hthread_a, hthread_b; DWORD nexitcode = NULL; char turn = 'A'; /* 변수초기화 */ InitializeCriticalSection(&crit); /* SimpleThreadsVer3.cpp (2) */ /* Consumer 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*) malloc(sizeof(threadparam)); pthrparam->pcs = &crit; pthrparam->mark = 'A'; pthrparam->pturn = &turn; hthread_a = CreateThread(NULL, 0, Thread_A, pthrparam, 0, NULL); /* Producer 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*) malloc(sizeof(threadparam)); pthrparam->pcs = &crit; pthrparam->mark = 'B'; pthrparam->pturn = &turn; hthread_b = CreateThread(NULL, 0, Thread_B, pthrparam, 0, NULL); WaitForSingleObject(hThread_A, INFINITE); GetExitCodeThread(hThread_A, &nexitcode); TerminateThread(hThread_A, nexitcode); CloseHandle(hThread_A); WaitForSingleObject(hThread_B, INFINITE); GetExitCodeThread(hThread_B, &nexitcode); TerminateThread(hThread_B, nexitcode); CloseHandle(hThread_B); DeleteCriticalSection(&crit); ch

27 /* SimpleThreadsVer3.cpp (3) */ DWORD WINAPI Thread_A(LPVOID pparam) ThreadParam *pthrparam; pthrparam = (ThreadParam *)pparam; char mark = pthrparam->mark; char turn = ' 0'; for (int i = 0; i < 20; i++) do EnterCriticalSection(pThrParam->pCS); turn = *pthrparam->pturn; LeaveCriticalSection(pThrParam->pCS); if (turn == 'A') break; else Sleep(100); while (turn!= 'A'); EnterCriticalSection(pThrParam->pCS); printf("thread_a... "); for (int j = 0; j < 50; j++) printf("%c", mark); printf(" n"); *pthrparam->pturn = 'B'; LeaveCriticalSection(pThrParam->pCS); Sleep(10); printf("thread_a finished... n"); return 0; ch /* SimpleThreadsVer3.cpp (4) */ DWORD WINAPI Thread_B(LPVOID pparam) ThreadParam *pthrparam; pthrparam = (ThreadParam *)pparam; char mark = pthrparam->mark; char turn = 0 ; for (int i = 0; i < 20; i++) do EnterCriticalSection(pThrParam->pCS); turn = *pthrparam->pturn; LeaveCriticalSection(pThrParam->pCS); if (turn == 'B') break; else Sleep(10); while (turn!= 'B'); EnterCriticalSection(pThrParam->pCS); printf("thread_b... "); for (int j = 0; j < 50; j++) printf("%c", mark); printf(" n"); *pthrparam->pturn = 'A'; LeaveCriticalSection(pThrParam->pCS); Sleep(100); printf("thread_b finished... n"); return 0;

28 실행결과 (ver 3) critical section과함께turn semaphore를사용 하나의스레드가한줄의출력을완료한후, 다른스레드가출력을완료할때까지계속기다리게함 thread_a 또는 thread_b가한번에한줄씩만출력하며, 번갈아가며출력 ch

29 Two Simple Threads with shared Queue version 4 shared Queue 사용 thread_main() create thread_a() create thread_b() CRITICAL_SECTION crit Queue queue; thread_a() wait until (*pq is not FULL) EnterCriticalSection() Element e = data[i]; enqueue(pq, e); LeaveCriticalSection() Queue thread_b() wait until (fifoq is not EMPTY) EnterCriticalSection() Element e = dequeue(pq); LeaveCriticalSection() ch

30 Shared Queue 의구현방법 (1) Circular Queue array 기반의구현 first_index, last_index 가저장된데이터를가르킴 first_index와 last_index의초기값은 0 index 값은 0 ~ N-1 범위의값을가지며, N-1 이후에는 0으로순환됨 enqueue() pq->data[last_index] = element; pq-> last_index = (pq-> last_index + 1) % N; pq->num_data++; dequeue() element = pq->data[first_index]; pq-> first_index = (pq-> first_index + 1) % N; pq->num_data--; ch

31 Shared Queue 의구현방법 (2) List Queue Doubly Linked List 기반의구현 LinkNode, LinkedList 구조체필요 enqueue() 에서는현재의 *plast 뒤에새로운 list node를추가 dequeue() 에서는현재의 *pfirst 노드를읽고, remove Priority Queue Heap priority queue 기반의구현 complete binary tree로구성 insertheap() 에서는 upheap bubbling이수행되며, 항상기준이되는 key 값이가장작은 ( 또는가장큰 ) element가 root에위치하도록관리됨 removemin() 에서는 downheap bubbling이수행되며, 남아있는항목들중기준이되는 key 값이가장작은 ( 또는가장큰 ) element가 root에위치하도록관리됨 ch

32 간단한 Producer Consumer 스레드구현예 Thread Producer generate and data randomly, and enqueue() into the shared queue if queue is full, it waits sleeps randomly chosen time repeats the data generation for given execution duration Thread Consumer dequeues a data from the shared queue if queue is empty, it waits sleeps randomly chosen time repeats the data processing for given execution duration Functional Block diagram Critical Section Thread_ Producer enqueue() dequeue() Thread_ Consumer Circular_Queue_int ch

33 Queue - Header File /* Queue.h */ #ifndef CIRCULAR_INT_Q_H #define CIRCULAR_INT_Q_H typedef struct Circular_Int_Queue int numdata; int max_q_size; int first_index; int last_index; int *data; Circular_Int_Queue(int maxqsize); // 구조체의초기화생성 Circular_Int_Queue; int enqueue(circular_int_queue* pq, int data); int dequeue(circular_int_queue* pq); int isqueueempty(circular_int_queue* pq); int isqueuefull(circular_int_queue* pq); void printqueue(circular_int_queue* pq); void freequeuebuffer(circular_int_queue* pq); #endif ch

34 Queue 멤버함수 /* Queue.c (1) */ #include <stdio.h> #include <stdlib.h> #include"queue.h" Circular_Int_Queue::Circular_Int_Queue(int maxqsize) max_q_size = maxqsize; data = (int *)malloc(sizeof(int)* max_q_size); first_index = last_index = 0; numdata = 0; for (int i = 0; i < max_q_size; i++) data[i] = -1; void freequeuebuffer(circular_int_queue* pq) free(pq->data); ch

35 Queue 멤버함수 /* Queue.c (2) */ int enqueue(circular_int_queue* pq, int data) int index = -1; if (isqueuefull(pq)) printf("queue is Full!! n"); return -1; else index = pq->last_index; pq->data[index] = data; pq->last_index = (pq->last_index + 1) % pq->max_q_size; pq->numdata++; return 0; /* Queue.c (3) */ int dequeue(circular_int_queue* pq) int data = 0; int index = -1; if (isqueueempty(pq)) printf("queue is Empty!! n"); return -1; else index = pq->first_index; data = pq->data[index]; pq->data[index] = -1; pq->first_index = (pq->first_index + 1) % pq->max_q_size; pq->numdata--; return data; ch

36 /* Queue.c (4) */ int isqueueempty(circular_int_queue* pq) if (pq->numdata == 0) return 1; else return 0; int isqueuefull(circular_int_queue* pq) if (pq->numdata == pq->max_q_size) return 1; else return 0; void printqueue(circular_int_queue* pq) int count = 0; printf(" Current queue (numdata: %2d) [", pq->numdata); for (int i = 0; i<pq->numdata; i++) printf(" %2d", pq->data[(pq->first_index + i) % pq->max_q_size]); if (i < (pq->numdata - 1)) printf(", "); printf("] n"); ch

37 main(), Threads /* Multi-thread.c (1) */ #include<stdio.h> #include<windows.h> #include<time.h> #include"queue.h" #define MAX_QUEUE_SIZE 10 #define THREAD_EXECUTION_TIME // 10 sec enum ROLE PRODUCER, CONSUMER ; typedef struct ThreadParam Circular_Int_Queue *queue; CRITICAL_SECTION* pcs; int role; ThreadParam; DWORD WINAPI Thread_producer(LPVOID pparam); DWORD WINAPI Thread_consumer(LPVOID pparam); ch

38 /* Multi-thread.c (2) */ void main() Circular_Int_Queue circular_intq(max_queue_size); // Queue 생성및초기화 /* 임계구역을나누어스레드간의공유자원사용을관리하게될 CriticalSection 변수 */ CRITICAL_SECTION crit; ThreadParam *pthrparam; /* 각스레드로전달될파라미터구조체 */ /* 스레드정보를관리하게될핸들러변수 */ HANDLE hthreadproducer, hthreadconsumer; DWORD nexitcode = NULL; Circular_Int_Queue *pq = &circular_intq; /* 변수초기화 */ InitializeCriticalSection(&crit); /* 스레드에서사용될 CriticalSection 변수초기화 */ /*Consumer 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*)malloc(sizeof(ThreadParam)); pthrparam->pcs = &crit; pthrparam->queue = pq; pthrparam->role = CONSUMER; /*CreateThread API 를이용하여 Thread 생성과전달할인자를전달한후반환되어지는해당 Thread 에대한정보를 hthreadconsumer 핸들러에저장 */ hthreadconsumer = CreateThread(NULL, 0, Thread_consumer, pthrparam, 0, NULL); printf("thread consumer has been created and instantitated.. n"); ch

39 /* Multi-thread.c (3) */ /*Producer 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*)malloc(sizeof(ThreadParam)); pthrparam->pcs = &crit; pthrparam->queue = pq; pthrparam->role = PRODUCER; /*CreateThread API 를이용하여 Thread 생성과전달할인자를전달한후반환되어지는해당 Thread 에대한정보를 hthreadproducer 핸들러에저장 */ hthreadproducer = CreateThread(NULL, 0, Thread_producer, pthrparam, 0, NULL); printf("thread producer has been created and instantitated.. n"); /*main 스레드가생성한 Producer 스레드가끝날때까지대기 */ printf("waiting for the termination of thread producer... n"); WaitForSingleObject(hThreadProducer, THREAD_EXECUTION_TIME); GetExitCodeThread(hThreadProducer, &nexitcode); TerminateThread(hThreadProducer, nexitcode); /*Producer 스레드종료 */ CloseHandle(hThreadProducer); /* 스레드핸들러종료 */ printf("thread producer is now terminated.. n"); /*main 스레드가생성한 Comsumer 스레드가끝날때까지대기 */ printf("waiting for the termination of thread consumer... n"); WaitForSingleObject(hThreadconsumer, THREAD_EXECUTION_TIME); GetExitCodeThread(hThreadconsumer, &nexitcode); TerminateThread(hThreadconsumer, nexitcode); /*Comsumer 스레드종료 */ CloseHandle(hThreadconsumer); /* 스레드핸들러종료 */ printf("thread consumer is now terminated.. n"); ch

40 /* Multi-thread.c (4) */ /* 스레드에서사용된 CriticalSection 변수 Delete*/ DeleteCriticalSection(&crit); freequeuebuffer(pq); DWORD WINAPI Thread_producer(LPVOID pparam) ThreadParam *pthrparam; /*void* 자료형으로스레드에전달된인자를형변환을통해 pthrparam 구조체로변환 */ pthrparam = (ThreadParam *)pparam; Circular_Int_Queue *pq = pthrparam->queue; int data = 0; int sleep_time_ms = 0; int enq_res; srand(time(null)); while (1) data = rand() % 100; /* 공유자원에접근하는임계구역에진입하기전 cs 변수를이용하여, Lock 을잡고임계구역에진입한번에하나의스레드만이공유자원에접근하도록제한함 */ EnterCriticalSection(pThrParam->pCS); printf("thread_producer::enqueue(data = %2d) => ", data); ch

41 /* Multi-thread.c (4) */ enq_res = enqueue(pq, data); LeaveCriticalSection(pThrParam->pCS); if (enq_res!= -1) EnterCriticalSection(pThrParam->pCS); printqueue(pq); LeaveCriticalSection(pThrParam->pCS); else // 만약 Queue 가 FULL 상태이면, 여유공간이생길때까지반복하여 enqueue() 시도 do Sleep(200); EnterCriticalSection(pThrParam->pCS); enq_res = enqueue(pq, data); LeaveCriticalSection(pThrParam->pCS); while (enq_res == -1); EnterCriticalSection(pThrParam->pCS); printqueue(pq); LeaveCriticalSection(pThrParam->pCS); sleep_time_ms = rand() % 500; Sleep(sleep_time_ms); return 0; ch

42 /* Multi-thread.c (4) */ DWORD WINAPI Thread_consumer(LPVOID pparam) ThreadParam *pthrparam; /*void* 자료형으로스레드에전달된인자를형변환을통해 pthrparam 구조체로변환 */ pthrparam = (ThreadParam *)pparam; Circular_Int_Queue *pq = pthrparam->queue; int sleep_time_ms = 0; int dequeue_data = -1; srand(time(null)); while (1) /* 공유자원에접근하는임계구역에진입하기전 cs 변수를이용하여, Lock 을잡고임계구역에진입한번에하나의스레드만이공유자원에접근하도록제한함 */ EnterCriticalSection(pThrParam->pCS); printf("thread_consumer::dequeue() => "); dequeue_data = dequeue(pq); if (dequeue_data > -1) printf("dequeue data (%2d)", dequeue_data); printqueue(pq); /* 공유자원에대한처리를종료한후 critical section Lock 을놓아주어해당임계구역에대한권리를다른스레드가가질수있도록허락함 */ LeaveCriticalSection(pThrParam->pCS); sleep_time_ms = rand() % 1000; Sleep(sleep_time_ms); return 0; ch

43 실행결과 ch

44 ch

45 Task Generator Task Processor Functional Block diagram 2 개의 threads: Task_Gen, Task_Proc 1 개의 Linked List 기반 Queue Critical Section Thread_ Task_Gen enqueue() dequeue() Thread_ Task_Proc ListQueue (for task) ch

46 Thread Task_Gen Thread_Task_Gen() 는차례대로 0 ~ 19 값의 task_id 와임의로생성되는 task_name 를가지는 Task 구조체변수를생성하며, 이생성된 task 를공유되는 queue 에저장 (enqueue) 시킨다. 항상 isfull() 함수를사용하여, queue가 FULL 상태인가를먼저확인하고, 만약 queue가 FULL 상태이면, 0.1초를 sleep한후다시queue 상태를점검한후, 여유공간이생기면저장한다. Queue에데이터를저장한후에는, printqueue() 함수를사용하여현재의 queue 상태를출력시키며, 0.1 ~ 1초사이의값을임의로선정하여그기간동안 sleep한후, 데이터생성및 enqueue 동작을반복한다. Thread Task_Proc Thread_Task_Proc() 는 isempty() 함수를사용하여 queue 의상태를확인하여, 만약 EMPTY 상태가아니면 queue 에저장되어있는데이터를추출 (dequeue) 하여 Task 정보 (task_id, task_name) 을출력하고, printqueue() 함수를사용하여 queue 상태를출력한후, 0.1 ~ 1초사이의값을임의로선정한후, 그기간동안sleep하고, queue로부터의데이터추출을반복한다. 만약 queue가 EMPTY 상태이면, 0.1 초동안sleep한후, queue를상태를다시점검하고, EMPTY 상태가아니면데이터를추출한다. ch

47 main() 함수 main() 함수는 MAX_CAPACITY 10인 queue를구조체변수의초기화기능을사용하여설정하며, 두개의스레드 (Thread_Task_Proc(), Thread_Task_Gen()) 를생성하고, 이들스레드들이 queue와 CRITICAL_SECTION criticalsection를공유하도록하며, 각각의 role을 TASK_PROC와 TASK_GEN으로지정한다. 생성된 Thread_Task_Gen() 는지정된개수 ( 예 : 20) 의Task를생성하여, enqueue 시킨후, 종료를한다. Thread_Task_Proc() 는지정된개수의 task를차례로 dequeue한후, 이를처리 ( 화면에출력 ) 한후, 스스로종료한다. main() 함수에서는 WaitForSingleObject() 함수를사용하여, Thread_Task_Gen() 이스스로종료할때까지기다린다. Thread_Task_Gen() 이종료되면, main() 함수에서는 WaitForSingleObject() 함수를사용하여, Thread_Task_Proc() 이스스로종료할때까지기다린다. ch

48 Task_Gen, Task_Proc, ListQueue 의구현 /* ListQueue.h (1) */ #ifndef LIST_QUEUE_H #define LIST_QUEUE_H /* Queue based on Linked List */ #include <stdio.h> #include <stdlib.h> typedef struct Task int task_id; char task_name[16]; Task; typedef struct ListNode Task *ptask; ListNode *prev; ListNode *next; /* ListQueue.h (2) */ typedef struct ListQueue ListNode *pfront; ListNode *pend; int size; int max_capacity; ListQueue(int max_cap); ListQueue; bool isempty(listqueue *pq); bool isfull(listqueue *pq); void initqueue(listqueue *pq); int enqueue(listqueue *pq, Task *ptsk); Task *dequeue(listqueue *pq); void printqueue(listqueue *pq); #endif ListNode; ch

49 /* ListQueue.c (1) */ #include "ListQueue.h" ListQueue::ListQueue(int max_cap) max_capacity = max_cap; size = 0; pfront = pend = NULL; bool isempty(listqueue *pq) if (pq->size == 0) return true; else return false; bool isfull(listqueue *pq) if (pq->size >= pq->max_capacity) return true; else return false; /* ListQueue.c (2) */ void printqueue(listqueue *pq) Task *ptsk; if (isempty(pq)) printf(" Exception::Queue is Empty!! n"); return; printf(" Queue status (size:%2d) : ", pq->size); ListNode *pln = pq->pfront; for (int i = 0; i < pq->size; i++) ptsk = pln->ptask; printf(" task (%2d, %8s)", ptsk->task_id, ptsk->task_name); pln = pln->next; printf(" n"); ch

50 /* ListQueue.c (2) */ int enqueue(listqueue *pq, Task *ptsk) ListNode *pnewln; pnewln = (ListNode *) malloc(sizeof(listnode)); pnewln->ptask = ptsk; pnewln->next = NULL; if (isfull(pq)) return -1; // queue is full else if (isempty(pq)) // queue is empty pnewln->prev = NULL; pq->pfront = pq->pend = pnewln; else pnewln->prev = pq->pend; pq->pend->next = pnewln; pq->pend = pnewln; pq->size++; return pq->size; /* ListQueue.c (3) */ Task *dequeue(listqueue *pq) Task *ptsk; if (isempty(pq)) printf(" Exception::Queue is Empty!! n"); return NULL; ptsk = pq->pfront->ptask; pq->size--; ListNode *pln = pq->pfront; pq->pfront = pq->pfront->next; free(pln); return ptsk; ch

51 /* main.c (1) */ #include<stdio.h> #include<windows.h> #include<time.h> #include"listqueue.h" #define MAX_CAPACITY 4 #define TASK_NAME_LEN 8 #define TASK_NAME_LEN_MIN 4 #define NUM_TASK_GEN 20 #define THRD_TASK_GEN_INTERVAL 500 // 500ms #define THRD_TASK_PROC_INTERVAL 1000 // 1000ms #define THREAD_EXECUTION_TIME 5000 // 5 sec enum ROLE TASK_GEN, TASK_PROC ; typedef struct ThreadParam ListQueue *pq; CRITICAL_SECTION* pcs; int role; ThreadParam; DWORD WINAPI Thread_TaskGen(LPVOID pparam); DWORD WINAPI Thread_TaskProc(LPVOID pparam); ch

52 /* main.c (2) */ void main() /* 변수선언 */ ListQueue queue(max_capacity); Elm_t data; ListQueue *pq = &queue; /* 임계구역을나누어스레드간의공유자원사용을관리하게될 CriticalSection 변수 */ CRITICAL_SECTION crit; /* 각스레드로전달될파라미터구조체 */ ThreadParam *pthrparam; /* 스레드정보를관리하게될핸들러변수 */ HANDLE hthreadtaskgen, hthreadtaskproc; DWORD nexitcode = NULL; /* 스레드에서사용될 CriticalSection 변수초기화 */ InitializeCriticalSection(&crit); /*Task_Processor 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*)malloc(sizeof(ThreadParam)); pthrparam->pcs = &crit; pthrparam->pq = pq; pthrparam->role = TASK_PROC; /*CreateThread API를이용하여 Thread 생성과전달할인자를전달한후반환되어지는해당 Thread에대한정보를 hthreadtask_processor 핸들러에저장 */ hthreadtaskproc = CreateThread(NULL, 0, Thread_TaskProc, pthrparam, 0, NULL); printf("thread Task_Proc has been created and instantitated.. n"); ch

53 /* main.c (3) */ /*Task_Generator 스레드에전달될파라미터값초기화 */ pthrparam = (ThreadParam*)malloc(sizeof(ThreadParam)); pthrparam->pcs = &crit; pthrparam->pq = pq; pthrparam->role = TASK_GEN; /*CreateThread API 를이용하여 Thread 생성과전달할인자를전달한후반환되어지는해당 Thread 에대한정보를 hthreadtask_generator 핸들러에저장 */ hthreadtaskgen = CreateThread(NULL, 0, Thread_TaskGen, pthrparam, 0, NULL); printf("thread Task_Gen has been created and instantitated.. n"); /*main 스레드가생성한 Task_Generator 스레드가끝날때까지대기 */ printf("waiting for the termination of thread Task_Gen... n"); WaitForSingleObject(hThreadTaskGen, INFINITE); GetExitCodeThread(hThreadTaskGen, &nexitcode); TerminateThread(hThreadTaskGen, nexitcode); /*Task_Generator 스레드종료 */ CloseHandle(hThreadTaskGen); /* 스레드핸들러종료 */ printf("thread Task_Gen is now terminated.. n"); /*main 스레드가생성한 Task_Gen 스레드가끝날때까지대기 */ printf("waiting for the termination of thread Task_Proc... n"); WaitForSingleObject(hThreadTaskProc, INFINITE); GetExitCodeThread(hThreadTaskProc, &nexitcode); TerminateThread(hThreadTaskProc, nexitcode); /* Task_Proc 스레드종료 */ CloseHandle(hThreadTaskProc); /* 스레드핸들러종료 */ printf("thread Task_Proc is now terminated.. n"); DeleteCriticalSection(&crit); /* 스레드에서사용된 CriticalSection 변수 Delete*/ ch

54 /* main.c (4) */ DWORD WINAPI Thread_TaskGen(LPVOID pparam) ThreadParam *pthrparam; Task *ptask; char t_name[task_name_len]; int t_name_len; int i, j; /* void * 자료형으로스레드에전달된인자를형변환을통해 pthrparam 구조체로변환 */ pthrparam = (ThreadParam *)pparam; ListQueue *pq = pthrparam->pq; int data = 0; int sleep_time_ms = 0; int enq_res; srand(time(null)); for (i = 0; i < NUM_TASK_GEN; i++) ptask = (Task *)malloc(sizeof(task)); ptask->task_id = i; for (int j = 0; j < TASK_NAME_LEN; j++) t_name[j] = ' 0'; t_name_len = rand() % (TASK_NAME_LEN - TASK_NAME_LEN_MIN) + TASK_NAME_LEN_MIN; t_name[0] = rand() % 26 + 'A'; for (j = 1; j < t_name_len; j++) t_name[j] = rand() % 26 + 'a'; t_name[j] = ' 0'; strcpy(ptask->task_name, t_name); ch

55 /* main.c (5) */ EnterCriticalSection(pThrParam->pCS); printf("taskgen::enqueue(%2d, %8s) => ", ptask->task_id, ptask->task_name); enq_res = enqueue(pq, ptask); LeaveCriticalSection(pThrParam->pCS); if (enq_res!= -1) EnterCriticalSection(pThrParam->pCS); printqueue(pq); LeaveCriticalSection(pThrParam->pCS); else // queue is full EnterCriticalSection(pThrParam->pCS); printf("queue is Full!! n"); LeaveCriticalSection(pThrParam->pCS); do Sleep(200); EnterCriticalSection(pThrParam->pCS); enq_res = enqueue(pq, ptask); LeaveCriticalSection(pThrParam->pCS); while (enq_res == -1); EnterCriticalSection(pThrParam->pCS); printf(" enqueue() after queue has been Full =>"); printqueue(pq); LeaveCriticalSection(pThrParam->pCS); sleep_time_ms = rand() % THRD_TASK_GEN_INTERVAL; Sleep(sleep_time_ms); // for printf("taskgen:: Total %d tasks have been generated!! n", NUM_TASK_GEN); return 0; ch

56 /* main.c (6) */ DWORD WINAPI Thread_TaskProc(LPVOID pparam) ThreadParam *pthrparam; /*void* 자료형으로스레드에전달된인자를형변환을통해 pthrparam 구조체로변환 */ pthrparam = (ThreadParam *)pparam; ListQueue *pq = pthrparam->pq; int sleep_time_ms = 0; int dequeue_data = -1; int count = 0; Task *ptsk; srand(time(null)); while (1) /* 공유자원에접근하는임계구역에진입하기전, cs 변수를이용하여, Lock 을잡고임계구역에진입한번에하나의스레드만이공유자원에접근하도록제한함 */ EnterCriticalSection(pThrParam->pCS); printf("taskproc::dequeue() => "); ptsk = dequeue(pq); if (ptsk!= NULL) printf("task(%2d, %8s)", ptsk->task_id, ptsk->task_name); printqueue(pq); count++; ch

57 /* main.c (7) */ /* 공유자원에대한처리를종료한후 Lock 을놓아주어해당임계구역에대한권리를다른스레드가가질수있도록허락함 */ LeaveCriticalSection(pThrParam->pCS); if (count >= NUM_TASK_GEN) printf("taskproc:: Total %d tasks have been processed!! n", count); break; sleep_time_ms = rand() % THRD_TASK_PROC_INTERVAL; Sleep(sleep_time_ms); return 0; ch

58 ch

59 Homework Critical section 이필요한이유에대하여설명하라 Queuing System and Multi-Threads (1) 다음과같은 typedef 을정의하라 : typedef unsigned int UINT_32; typedef unsigned short UINT_16; typedef unsigned char UINT_8; (2) 구조체 struct Packet 은다음과같은멤버를가진다 : UINT_32 srcaddr; // source address UINT_32 dstaddr; // destination address UINT_8 priority; // priority of protocol data unit ( 사용자 / 프로토콜정보의우선순위 ) UINT_32 seqno; // sequence number UINT_32 payloadlength; // length of payload UINT_8 *ppayload; // payload (3) 다음함수들이구조체 struct Packet 를위하여사용된다 : void initpacket(packet *ppkt, unsigned int saddr, unsigned int sn); FILE * fprintpacket(file *fout, Packet* ppkt); ch

60 11.2 Queuing System and Multi-Threads (2) (4) 구조체 struct ListNode 는다음과같은데이터멤버를가진다 : Packet *ppkt; ListNode *pnext; ListNode *pprev; (5) 구조체 struct Queue 는다음과같은데이터멤버를가진다 : int numpkts; ListNode* pfirst; ListNode* plast; (6) 다음함수들은구조체 struct Queue 와관련되어사용된다 : int enqueue(queue *pq, Packet* ppkt); // enqueue a packet into the queue. // The list node is pointing a packet. Packet* dequeue(queue *pq); // remove a list node from the queue, and return a Packet. void printqueue(file *fout, Queue *pq); // print all list node in the queue ch

61 11.2 Queuing System and Multi-Threads (3) (7) 다중스레드의초기화를위하여다음과같은구조체 (ThreadParam) 가스레드로파라메터를전달하기위하여사용된다 : typedef struct ThreadParam CRITICAL_SECTION *pcs; // pointer to the shared critical section Queue *pq; // pointer to the shared queue int role; // packetgen or linktx UINT_32 addr; int max_queue; int duration; // duration of the thread execution (1 minute). FILE *fout; // pointer to the output file stream ThreadParam; (8) Thread packetgen() 는주기적으로패킷들을생성하며, 생성된패킷들을 queue에삽입 (enqueue) 한다. 각스레드 packetgen() 은지정된송신주소 (srcaddr) 를사용한다. 패킷생성시간간격은 1 ~ 5 초사이의값이임의로설정된다. (9) Thread linktx() 는 queue를지속적으로점검하며, 만약 queue가 empty 상태이면 1 초를 sleep 한다. Queue가 empty가아니면, queue로부터패킷1개를추출 (dequeue) 하여그패킷의정보를지정된파일로출력한다. ch

62 11.2 Queuing System and Multi-Threads (4) (10) main() 함수는다음과같은내용을실행한다 : 3 의 critical section 이생성되어다수의 packetgen() 스레드와 linktx() 스레드간의공유자원 (3 개의 queue) 에대한사용을제어한다. 5 개의패킷생성스레드를생성하고, 초기화한다. 1 개의 link transmission 스레드를생성하고, 초기화한다. main() 함수는 3 의구조체 struct Queue 변수를생성하고, 3 의 critical section 을생성하여, 5 개의 packet generation 스레드와 1 개의 link transmission 스레드가공유하게한다. 각패킷생성스레드는각각 30 개의패킷 ( 목적지주소는 random 하게설정하며, 우선순위 (priority) 는 0 ~ 2 의값을 random 하게설정 ) 을생성하여, 우선순위에따라지정된 queue 에넣는다. linktx() 스레드는항상우선순위가높은 queue 를먼저점검하며, 만약패킷이존재하는경우, 이를우선처리한다. 패킷생성스레드에서생성되어 enqueue 된패킷들은 linktx() 스레드에의하여 dequeue 된후, 송신측주소에따라분류되어개수가점검된다. 각송신주소로부터의우선순위별총패킷개수는프로그램의종료단계에서출력되어, 정확하게전달되었는지를확인한다. 프로그램의수행내용은출력파일 output.txt 에출력된다. PacketGen () 1 PacketGen () 2 PacketGen () 3 PacketGen () 4 PacketGen () 5 High-priority (2) Queue Mid-priority (1) Queue Low-priority (0) Queue linktx() ch

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100 2015-1 프로그래밍언어 9. 연결형리스트, Stack, Queue 2015 년 5 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 연결리스트 (Linked List) 연결리스트연산 Stack

More information

6주차.key

6주차.key 6, Process concept A program in execution Program code PCB (process control block) Program counter, registers, etc. Stack Heap Data section => global variable Process in memory Process state New Running

More information

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경

More information

10주차.key

10주차.key 10, Process synchronization (concurrently) ( ) => critical section ( ) / =>, A, B / Race condition int counter; Process A { counter++; } Process B { counter ;.. } counter++ register1 = counter register1

More information

03_queue

03_queue Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,

More information

Lab 3. 실습문제 (Single linked list)_해답.hwp

Lab 3. 실습문제 (Single linked list)_해답.hwp Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.

More information

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures 단일연결리스트 (Singly Linked List) 신찬수 연결리스트 (linked list)? tail 서울부산수원용인 null item next 구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct

More information

untitled

untitled - -, (insert) (delete) - - (insert) (delete) (top ) - - (insert) (rear) (delete) (front) A A B top A B C top push(a) push(b) push(c) A B top pop() top A B D push(d) top #define MAX_STACK_SIZE 100 int

More information

untitled

untitled Embedded System Lab. II Embedded System Lab. II 2 RTOS Hard Real-Time vs Soft Real-Time RTOS Real-Time, Real-Time RTOS General purpose system OS H/W RTOS H/W task Hard Real-Time Real-Time System, Hard

More information

Microsoft PowerPoint - ch20-설계문서작성, Pseudo Code, Sequence Diagram, Class Diagram - 김영탁140609v2

Microsoft PowerPoint - ch20-설계문서작성, Pseudo Code, Sequence Diagram, Class Diagram - 김영탁140609v2 요구사항분석 시스템개발자는사용자들의요구사항을만족시키기위하여하드웨어및소프트웨어시스템설계및구현 ( 예 ) 1 Km 거리에 200Kbps 급데이터를전송할수있는양방향무선데이터통신모듈을개발 어떤무선통신채널 ( 예 : 2.4GHz 또는 900MHz) 을사용할것인가? 관련하드웨어모듈 /Chipset 은? 사용가능한임베디드프로세서는? 무선통신채널을제어하고관리하기위한운영체제

More information

Chapter #01 Subject

Chapter #01  Subject Device Driver March 24, 2004 Kim, ki-hyeon 목차 1. 인터럽트처리복습 1. 인터럽트복습 입력검출방법 인터럽트방식, 폴링 (polling) 방식 인터럽트서비스등록함수 ( 커널에등록 ) int request_irq(unsigned int irq, void(*handler)(int,void*,struct pt_regs*), unsigned

More information

K&R2 Reference Manual 번역본

K&R2 Reference Manual 번역본 typewriter structunion struct union if-else if if else if if else if if if if else else ; auto register static extern typedef void char short int long float double signed unsigned const volatile { } struct

More information

Chapter 4. LISTS

Chapter 4. LISTS C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or

More information

1217 WebTrafMon II

1217 WebTrafMon II (1/28) (2/28) (10 Mbps ) Video, Audio. (3/28) 10 ~ 15 ( : telnet, ftp ),, (4/28) UDP/TCP (5/28) centralized environment packet header information analysis network traffic data, capture presentation network

More information

chap01_time_complexity.key

chap01_time_complexity.key 1 : (resource),,, 2 (time complexity),,, (worst-case analysis) (average-case analysis) 3 (Asymptotic) n growth rate Θ-, Ο- ( ) 4 : n data, n/2. int sample( int data[], int n ) { int k = n/2 ; return data[k]

More information

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular

More information

03장.스택.key

03장.스택.key ---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1 ? (stack): (LIFO:Last-In First-Out) 2 : top : ( index -1 ),,, 3 : ( ) ( ) -> ->. ->.... 4 Stack ADT : (LIFO) : init():. is_empty():

More information

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600 균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at

More information

11장 포인터

11장 포인터 Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함

More information

Chapter 4. LISTS

Chapter 4. LISTS 6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립

More information

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint - ch07 - 포인터 pm0415 2015-1 프로그래밍언어 7. 포인터 (Pointer), 동적메모리할당 2015 년 4 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline 포인터 (pointer) 란? 간접참조연산자

More information

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7> 제14장 동적 메모리 할당 Dynamic Allocation void * malloc(sizeof(char)*256) void * calloc(sizeof(char), 256) void * realloc(void *, size_t); Self-Referece NODE struct selfref { int n; struct selfref *next; }; Linked

More information

(Asynchronous Mode) ( 1, 5~8, 1~2) & (Parity) 1 ; * S erial Port (BIOS INT 14H) - 1 -

(Asynchronous Mode) ( 1, 5~8, 1~2) & (Parity) 1 ; * S erial Port (BIOS INT 14H) - 1 - (Asynchronous Mode) - - - ( 1, 5~8, 1~2) & (Parity) 1 ; * S erial Port (BIOS INT 14H) - 1 - UART (Univ ers al As y nchronous Receiver / T rans mitter) 8250A 8250A { COM1(3F8H). - Line Control Register

More information

5.스택(강의자료).key

5.스택(강의자료).key CHP 5: https://www.youtube.com/watch?v=ns-r91557ds ? (stack): (LIFO:Last-In First-Out):. D C B C B C B C B (element) C (top) B (bottom) (DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=.

More information

61 62 63 64 234 235 p r i n t f ( % 5 d :, i+1); g e t s ( s t u d e n t _ n a m e [ i ] ) ; if (student_name[i][0] == \ 0 ) i = MAX; p r i n t f (\ n :\ n ); 6 1 for (i = 0; student_name[i][0]!= \ 0&&

More information

슬라이드 1

슬라이드 1 -Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역

More information

1장. 유닉스 시스템 프로그래밍 개요

1장.  유닉스 시스템 프로그래밍 개요 Unix 프로그래밍및실습 7 장. 시그널 - 과제보충 응용과제 1 부모프로세스는반복해서메뉴를출력하고사용자로부터주문을받아자식프로세스에게주문내용을알린다. (SIGUSR1) ( 일단주문을받으면음식이완료되기전까지 SIGUSR1 을제외한다른시그널은모두무시 ) timer 자식프로세스는주문을받으면조리를시작한다. ( 일단조리를시작하면음식이완성되기전까지 SIGALARM 을제외한다른시그널은모두무시

More information

06장.리스트

06장.리스트 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :

More information

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Lab 5. 실습문제 (Double linked list)-1_해답.hwp Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.

More information

제11장 프로세스와 쓰레드

제11장 프로세스와 쓰레드 제9장자바쓰레드 9.1 Thread 기초 (1/5) 프로그램 명령어들의연속 (a sequence of instruction) 프로세스 / Thread 실행중인프로그램 (program in execution) 프로세스생성과실행을위한함수들 자바 Thread 2 9.1 Thread 기초 (2/5) 프로세스단위작업의문제점 프로세스생성시오버헤드 컨텍스트스위치오버헤드

More information

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를 리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은

More information

Figure 5.01

Figure 5.01 Chapter 4: Threads Yoon-Joong Kim Hanbat National University, Computer Engineering Department Chapter 4: Multithreaded Programming Overview Multithreading Models Thread Libraries Threading Issues Operating

More information

구조체정의 자료형 (data types) 기본자료형 (primitive data types) : char, int, float 등과같이 C 언어에서제공하는자료형. 사용자정의자료형 (user-defined data types) : 다양한자료형을묶어서목적에따라새로운자료형을

구조체정의 자료형 (data types) 기본자료형 (primitive data types) : char, int, float 등과같이 C 언어에서제공하는자료형. 사용자정의자료형 (user-defined data types) : 다양한자료형을묶어서목적에따라새로운자료형을 (structures) 구조체정의 구조체선언및초기화 구조체배열 구조체포인터 구조체배열과포인터 구조체와함수 중첩된구조체 구조체동적할당 공용체 (union) 1 구조체정의 자료형 (data types) 기본자료형 (primitive data types) : char, int, float 등과같이 C 언어에서제공하는자료형. 사용자정의자료형 (user-defined

More information

Microsoft Word - FunctionCall

Microsoft Word - FunctionCall Function all Mechanism /* Simple Program */ #define get_int() IN KEYOARD #define put_int(val) LD A val \ OUT MONITOR int add_two(int a, int b) { int tmp; tmp = a+b; return tmp; } local auto variable stack

More information

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2 제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.

More information

Chap06(Interprocess Communication).PDF

Chap06(Interprocess Communication).PDF Interprocess Communication 2002 2 Hyun-Ju Park Introduction (interprocess communication; IPC) IPC data transfer sharing data event notification resource sharing process control Interprocess Communication

More information

untitled

untitled int i = 10; char c = 69; float f = 12.3; int i = 10; char c = 69; float f = 12.3; printf("i : %u\n", &i); // i printf("c : %u\n", &c); // c printf("f : %u\n", &f); // f return 0; i : 1245024 c : 1245015

More information

윤성우의 열혈 TCP/IP 소켓 프로그래밍

윤성우의 열혈 TCP/IP 소켓 프로그래밍 C 프로그래밍프로젝트 Chap 22. 구조체와사용자정의자료형 1 2013.10.10. 오병우 컴퓨터공학과 구조체의정의 (Structure) 구조체 하나이상의기본자료형을기반으로사용자정의자료형 (User Defined Data Type) 을만들수있는문법요소 배열 vs. 구조체 배열 : 한가지자료형의집합 구조체 : 여러가지자료형의집합 사용자정의자료형 struct

More information

chap7.key

chap7.key 1 7 C 2 7.1 C (System Calls) Unix UNIX man Section 2 C. C (Library Functions) C 1975 Dennis Ritchie ANSI C Standard Library 3 (system call). 4 C?... 5 C (text file), C. (binary file). 6 C 1. : fopen( )

More information

Chapter 4. LISTS

Chapter 4. LISTS 연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는

More information

강의10

강의10 Computer Programming gdb and awk 12 th Lecture 김현철컴퓨터공학부서울대학교 순서 C Compiler and Linker 보충 Static vs Shared Libraries ( 계속 ) gdb awk Q&A Shared vs Static Libraries ( 계속 ) Advantage of Using Libraries Reduced

More information

<4D F736F F F696E74202D E20B3D7C6AEBFF6C5A920C7C1B7CEB1D7B7A1B9D62E >

<4D F736F F F696E74202D E20B3D7C6AEBFF6C5A920C7C1B7CEB1D7B7A1B9D62E > 웹프로그래밍및실습 ( g & Practice) 문양세강원대학교 IT 대학컴퓨터과학전공 소켓 (Socket) (1/2) Socket 이란? 서버와클라이언트가서로특정한규약을사용하여데이터를전송하기위한방식 서버와클라이언트는소켓연결을기다렸다가소켓이연결되면서로데이터를전송 현재네트워크상에서의모든통신의근간은 Socket 이라할수있음 Page 2 1 소켓 (Socket) (2/2)

More information

BMP 파일 처리

BMP 파일 처리 BMP 파일처리 김성영교수 금오공과대학교 컴퓨터공학과 학습내용 영상반전프로그램제작 2 Inverting images out = 255 - in 3 /* 이프로그램은 8bit gray-scale 영상을입력으로사용하여반전한후동일포맷의영상으로저장한다. */ #include #include #define WIDTHBYTES(bytes)

More information

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx #include int main(void) { int num; printf( Please enter an integer "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; } 1 학습목표 을 작성하면서 C 프로그램의

More information

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning C Programming Practice (II) Contents 배열 문자와문자열 구조체 포인터와메모리관리 구조체 2/17 배열 (Array) (1/2) 배열 동일한자료형을가지고있으며같은이름으로참조되는변수들의집합 배열의크기는반드시상수이어야한다. type var_name[size]; 예 ) int myarray[5] 배열의원소는원소의번호를 0 부터시작하는색인을사용

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070> #include "stdafx.h" #include "Huffman.h" 1 /* 비트의부분을뽑아내는함수 */ unsigned HF::bits(unsigned x, int k, int j) return (x >> k) & ~(~0

More information

Microsoft PowerPoint - 3ÀÏ°_º¯¼ö¿Í »ó¼ö.ppt

Microsoft PowerPoint - 3ÀÏ°_º¯¼ö¿Í »ó¼ö.ppt 변수와상수 1 변수란무엇인가? 변수 : 정보 (data) 를저장하는컴퓨터내의특정위치 ( 임시저장공간 ) 메모리, register 메모리주소 101 번지 102 번지 변수의크기에따라 주로 byte 단위 메모리 2 기본적인변수형및변수의크기 변수의크기 해당컴퓨터에서는항상일정 컴퓨터마다다를수있음 short

More information

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE> 쉽게풀어쓴 C 언어 Express 제 17 장동적메모리와연결리스트 이번장에서학습할내용 동적메모리할당의이해 동적메모리할당관련함수 연결리스트 동적메모리할당에대한개념을이해하고응용으로연결리스트를학습합니다. 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것

More information

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Function) 1. 함수의개념 입력에대해적절한출력을발생시켜주는것 내가 ( 프로그래머 ) 작성한명령문을연산, 처리, 실행해주는부분 ( 모듈 ) 자체적으로실행되지않으며,

More information

슬라이드 1

슬라이드 1 마이크로컨트롤러 2 (MicroController2) 2 강 ATmega128 의 external interrupt 이귀형교수님 학습목표 interrupt 란무엇인가? 기본개념을알아본다. interrupt 중에서가장사용하기쉬운 external interrupt 의사용방법을학습한다. 1. Interrupt 는왜필요할까? 함수동작을추가하여실행시키려면? //***

More information

歯9장.PDF

歯9장.PDF 9 Hello!! C printf() scanf() getchar() putchar() gets() puts() fopen() fclose() fprintf() fscant() fgetc() fputs() fgets() gputs() fread() fwrite() fseek() ftell() I/O 2 (stream) C (text stream) : `/n'

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 System Software Experiment 1 Lecture 5 - Array Spring 2019 Hwansoo Han (hhan@skku.edu) Advanced Research on Compilers and Systems, ARCS LAB Sungkyunkwan University http://arcs.skku.edu/ 1 배열 (Array) 동일한타입의데이터가여러개저장되어있는저장장소

More information

13주-14주proc.PDF

13주-14주proc.PDF 12 : Pro*C/C++ 1 2 Embeded SQL 3 PRO *C 31 C/C++ PRO *C NOT! NOT AND && AND OR OR EQUAL == = SQL,,, Embeded SQL SQL 32 Pro*C C SQL Pro*C C, C Pro*C, C C 321, C char : char[n] : n int, short, long : float

More information

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 비트연산자 1 1 비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 진수법! 2, 10, 16, 8! 2 : 0~1 ( )! 10 : 0~9 ( )! 16 : 0~9, 9 a, b,

More information

중간고사

중간고사 중간고사 예제 1 사용자로부터받은두개의숫자 x, y 중에서큰수를찾는알고리즘을의사코드로작성하시오. Step 1: Input x, y Step 2: if (x > y) then MAX

More information

Microsoft PowerPoint - chap06-2pointer.ppt

Microsoft PowerPoint - chap06-2pointer.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-2 참고자료 포인터 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 포인터의정의와사용 변수를선언하는것은메모리에기억공간을할당하는것이며할당된이후에는변수명으로그기억공간을사용한다. 할당된기억공간을사용하는방법에는변수명외에메모리의실제주소값을사용하는것이다.

More information

untitled

untitled Step Motor Device Driver Embedded System Lab. II Step Motor Step Motor Step Motor source Embedded System Lab. II 2 open loop, : : Pulse, 1 Pulse,, -, 1 +5%, step Step Motor (2),, Embedded System Lab. II

More information

슬라이드 1

슬라이드 1 6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,

More information

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770> 연습문제해답 5 4 3 2 1 0 함수의반환값 =15 5 4 3 2 1 0 함수의반환값 =95 10 7 4 1-2 함수의반환값 =3 1 2 3 4 5 연습문제해답 1. C 언어에서의배열에대하여다음중맞는것은? (1) 3차원이상의배열은불가능하다. (2) 배열의이름은포인터와같은역할을한다. (3) 배열의인덱스는 1에서부터시작한다. (4) 선언한다음, 실행도중에배열의크기를변경하는것이가능하다.

More information

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1

More information

The Self-Managing Database : Automatic Health Monitoring and Alerting

The Self-Managing Database : Automatic Health Monitoring and Alerting The Self-Managing Database : Automatic Health Monitoring and Alerting Agenda Oracle 10g Enterpirse Manager Oracle 10g 3 rd Party PL/SQL API Summary (Self-Managing Database) ? 6% 6% 12% 55% 6% Source: IOUG

More information

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 #define _CRT_SECURE_NO_WARNINGS #include #include main() { char ch; printf(" 문자 1개를입력하시오 : "); scanf("%c", &ch); if (isalpha(ch))

More information

<4D F736F F F696E74202D20BBB7BBB7C7D15F FBEDFB0A3B1B3C0B05FC1A638C0CFC2F72E BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D20BBB7BBB7C7D15F FBEDFB0A3B1B3C0B05FC1A638C0CFC2F72E BC8A3C8AF20B8F0B5E55D> 뻔뻔한 AVR 프로그래밍 The Last(8 th ) Lecture 유명환 ( yoo@netplug.co.kr) INDEX 1 I 2 C 통신이야기 2 ATmega128 TWI(I 2 C) 구조분석 4 ATmega128 TWI(I 2 C) 실습 : AT24C16 1 I 2 C 통신이야기 I 2 C Inter IC Bus 어떤 IC들간에도공통적으로통할수있는 ex)

More information

Deok9_Exploit Technique

Deok9_Exploit Technique Exploit Technique CodeEngn Co-Administrator!!! and Team Sur3x5F Member Nick : Deok9 E-mail : DDeok9@gmail.com HomePage : http://deok9.sur3x5f.org Twitter :@DDeok9 > 1. Shell Code 2. Security

More information

SMB_ICMP_UDP(huichang).PDF

SMB_ICMP_UDP(huichang).PDF SMB(Server Message Block) UDP(User Datagram Protocol) ICMP(Internet Control Message Protocol) SMB (Server Message Block) SMB? : Microsoft IBM, Intel,. Unix NFS. SMB client/server. Client server request

More information

OPCTalk for Hitachi Ethernet 1 2. Path. DCOMwindow NT/2000 network server. Winsock update win95. . . 3 Excel CSV. Update Background Thread Client Command Queue Size Client Dynamic Scan Block Block

More information

본 강의에 들어가기 전

본 강의에 들어가기 전 C 기초특강 종합과제 과제내용 구조체를이용하여교과목이름과코드를파일로부터입력받아관리 구조체를이용하여학생들의이름, 학번과이수한교과목의코드와점수를파일로부터입력 학생개인별총점, 평균계산 교과목별이수학생수, 총점및평균을계산 결과를파일에저장하는프로그램을작성 2 Makefile OBJS = score_main.o score_input.o score_calc.o score_print.o

More information

Microsoft PowerPoint - chap13-입출력라이브러리.pptx

Microsoft PowerPoint - chap13-입출력라이브러리.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 스트림의 기본 개념을 알아보고,

More information

UI TASK & KEY EVENT

UI TASK & KEY EVENT KEY EVENT & STATE 구현 2007. 1. 25 PLATFORM TEAM 정용학 차례 Key Event HS TASK UI TASK LONG KEY STATE 구현 소스코드및실행화면 질의응답및토의 2 KEY EVENT - HS TASK hs_task keypad_scan_keypad hs_init keypad_pass_key_code keypad_init

More information

T100MD+

T100MD+ User s Manual 100% ) ( x b a a + 1 RX+ TX+ DTR GND TX+ RX+ DTR GND RX+ TX+ DTR GND DSR RX+ TX+ DTR GND DSR [ DCE TYPE ] [ DCE TYPE ] RS232 Format Baud 1 T100MD+

More information

Microsoft PowerPoint - Lecture_Note_5.ppt [Compatibility Mode]

Microsoft PowerPoint - Lecture_Note_5.ppt [Compatibility Mode] TCP Server/Client Department of Computer Engineering Kyung Hee University. Choong Seon Hong 1 TCP Server Program Procedure TCP Server socket() bind() 소켓생성 소켓번호와소켓주소의결합 listen() accept() read() 서비스처리, write()

More information

슬라이드 1

슬라이드 1 / 유닉스시스템개요 / 파일 / 프로세스 01 File Descriptor file file descriptor file type unix 에서의파일은단지바이트들의나열임 operating system 은파일에어떤포맷도부과하지않음 파일의내용은바이트단위로주소를줄수있음 file descriptor 는 0 이나양수임 file 은 open 이나 creat 로 file

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070> 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include "QuickSort.h" 7 using namespace std; 8 9 10 Node* Queue[100]; // 추가입력된데이터를저장하기위한 Queue

More information

0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x = (12 + 6) / 2 * 3; x = 27 x = 3 * (8 / 4

0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x = (12 + 6) / 2 * 3; x = 27 x = 3 * (8 / 4 Introduction to software design 2012-1 Final 2012.06.13 16:00-18:00 Student ID: Name: - 1 - 0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x

More information

SRC PLUS 제어기 MANUAL

SRC PLUS 제어기 MANUAL ,,,, DE FIN E I N T R E A L L O C E N D SU B E N D S U B M O TIO

More information

Frama-C/JESSIS 사용법 소개

Frama-C/JESSIS 사용법 소개 Frama-C 프로그램검증시스템소개 박종현 @ POSTECH PL Frama-C? C 프로그램대상정적분석도구 플러그인구조 JESSIE Wp Aorai Frama-C 커널 2 ROSAEC 2011 동계워크샵 @ 통영 JESSIE? Frama-C 연역검증플러그인 프로그램분석 검증조건추출 증명 Hoare 논리에기초한프로그램검증도구 사용법 $ frama-c jessie

More information

Microsoft PowerPoint - Chapter_09.pptx

Microsoft PowerPoint - Chapter_09.pptx 프로그래밍 1 1 Chapter 9. Structures May, 2016 Dept. of software Dankook University http://embedded.dankook.ac.kr/~baeksj 구조체의개념 (1/4) 2 (0,0) 구조체 : 다양한종류의데이터로구성된사용자정의데이터타입 복잡한자료를다루는것을편하게해줌 예 #1: 정수로이루어진 x,

More information

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조

More information

Microsoft PowerPoint - 08-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In

More information

The Pocket Guide to TCP/IP Sockets: C Version

The Pocket Guide to  TCP/IP Sockets: C Version 1 목포해양대해양컴퓨터공학과 UDP 소켓 네트워크프로그램설계 4 장 2 목포해양대해양컴퓨터공학과 목차 제 4장 UDP 소켓 4.1 UDP 클라이언트 4.2 UDP 서버 4.3 UDP 소켓을이용한데이터송신및수신 4.4 UDP 소켓의연결 3 목포해양대해양컴퓨터공학과 UDP 소켓의특징 UDP 소켓의특성 신뢰할수없는데이터전송방식 목적지에정확하게전송된다는보장이없음.

More information

Microsoft Word - KPMC-400,401 SW 사용 설명서

Microsoft Word - KPMC-400,401 SW 사용 설명서 LKP Ethernet Card SW 사용설명서 Version Information Tornado 2.0, 2.2 알 림 여기에실린내용은제품의성능향상과신뢰도의증대를위하여예고없이변경될수도있습니다. 여기에실린내용의일부라도엘케이일레븐의사전허락없이어떠한유형의매체에복사되거나저장될수없으며전기적, 기계적, 광학적, 화학적인어떤방법으로도전송될수없습니다. 엘케이일레븐경기도성남시중원구상대원동

More information

C 언어 프로그래밊 과제 풀이

C 언어 프로그래밊 과제 풀이 과제풀이 (1) 홀수 / 짝수판정 (1) /* 20094123 홍길동 20100324 */ /* even_or_odd.c */ /* 정수를입력받아홀수인지짝수인지판정하는프로그램 */ int number; printf(" 정수를입력하시오 => "); scanf("%d", &number); 확인 주석문 가필요한이유 printf 와 scanf 쌍

More information

chap x: G입력

chap x: G입력 원형큐 (Circular Queue) [2] [3] [2] [3] [1] [4] [1] [4] [0] [5] front = 0, rear = 0 [2] [3] [0] [5] front = 0, rear = 3 [1] [4] [0] [5] front = 0, rear = 0 최대큐이용률 = MAX_Q_SIZE 1 3 장. 스택과큐 (Page 13) 원형큐의구현

More information

PowerPoint Template

PowerPoint Template 18 동적할당과고급처리 인터넷정보과 1 2/19 동적할당 목적 다음과같은일반변수의선언과사용은변수를정적 (static) 으로사용 int a = 10; 메모리사용예측이부정확한경우는충분한메모리를미리확보해야하는것은비효율 동적 (dynamic) 메모리할당 (Memory Allocation) 동적인메모리할당을위해서는함수 malloc() 을이용, 메모리공간을확보 함수 malloc()

More information

CompareAndSet(CAS) 함수는 address 주소의값이 oldvalue 인지비교해서같으면 newvalue 로 바꾼다. 소프트웨어 lock 을사용하는것이아니고, 하드웨어에서제공하는기능이므로더빠르고 간편하다. X86 에서는 _InterlockedCompareEx

CompareAndSet(CAS) 함수는 address 주소의값이 oldvalue 인지비교해서같으면 newvalue 로 바꾼다. 소프트웨어 lock 을사용하는것이아니고, 하드웨어에서제공하는기능이므로더빠르고 간편하다. X86 에서는 _InterlockedCompareEx NON-BLOCKING ALGORITHM Homepage: https://sites.google.com/site/doc4code/ Email: goldpotion@outlook.com 2011/10/23 멀티쓰레드환경에서알아두면유용한자료구조에대해소개해본다. HARDWARE PRIMITIVE 효율적인구현을위해, Hardware 에서제공하는기능을이용해야한다. 자주쓰는기능에대해

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Reasons for Poor Performance Programs 60% Design 20% System 2.5% Database 17.5% Source: ORACLE Performance Tuning 1 SMS TOOL DBA Monitoring TOOL Administration TOOL Performance Insight Backup SQL TUNING

More information

ABC 10장

ABC 10장 10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;

More information

2. QUEUE OPERATIONS Initialize the queue Insert to the rear of the queue (also called as Enqueue) Remove (Delete) from the front of the queue (also ca

2. QUEUE OPERATIONS Initialize the queue Insert to the rear of the queue (also called as Enqueue) Remove (Delete) from the front of the queue (also ca Queues The name "queue" likely comes from the everyday use of the term. Consider: queue of people waiting at a bus stop, as pictured in fig. below. Each new person who comes and takes his or her place

More information

TCP.IP.ppt

TCP.IP.ppt TCP/IP TCP/IP TCP/IP TCP/IP TCP/IP Internet Protocol _ IP Address Internet Protocol _ Subnet Mask Internet Protocol _ ARP(Address Resolution Protocol) Internet Protocol _ RARP(Reverse Address Resolution

More information

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 제 8 장. 포인터 목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 포인터의개요 포인터란? 주소를변수로다루기위한주소변수 메모리의기억공간을변수로써사용하는것 포인터변수란데이터변수가저장되는주소의값을 변수로취급하기위한변수 C 3 포인터의개요 포인터변수및초기화 * 변수데이터의데이터형과같은데이터형을포인터 변수의데이터형으로선언 일반변수와포인터변수를구별하기위해

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임

More information

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms 2015-1 12. 그래프와관련알고리즘 2015 년 5 월 28 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 그래프 (Graph) 그래프의응용예 Outline 미로찾기 인터넷라우터에서의패킷 forwarding

More information

Chap 6: Graphs

Chap 6: Graphs AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node

More information

chap8.PDF

chap8.PDF 8 Hello!! C 2 3 4 struct - {...... }; struct jum{ int x_axis; int y_axis; }; struct - {...... } - ; struct jum{ int x_axis; int y_axis; }point1, *point2; 5 struct {....... } - ; struct{ int x_axis; int

More information

The Pocket Guide to TCP/IP Sockets: C Version

The Pocket Guide to  TCP/IP Sockets: C Version 얇지만얇지않은 TCP/IP 소켓프로그래밍 C 2 판 4 장 UDP 소켓 제 4 장 UDP 소켓 4.1 UDP 클라이언트 4.2 UDP 서버 4.3 UDP 소켓을이용한데이터송싞및수싞 4.4 UDP 소켓의연결 UDP 소켓의특징 UDP 소켓의특성 싞뢰할수없는데이터젂송방식 목적지에정확하게젂송된다는보장이없음. 별도의처리필요 비연결지향적, 순서바뀌는것이가능 흐름제어 (flow

More information

슬라이드 1

슬라이드 1 CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문 1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문 1. 표준입출력 표준입출력 입력 : 키보드, scanf 함수 출력 : 모니터, printf 함수문제 : 정수값 2개를입력받고두값사이의값들을더하여출력하라. #include int main(void) int Num1, Num2; int

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070> /* */ /* LZWIN.C : Lempel-Ziv compression using Sliding Window */ /* */ #include "stdafx.h" #include "Lempel-Ziv.h" 1 /* 큐를초기화 */ void LZ::init_queue(void) front = rear = 0; /* 큐가꽉찼으면 1 을되돌림 */ int LZ::queue_full(void)

More information

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-chap06-Queue.ppt / 큐 (QUEUE) Chapter 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 큐 Ticket ox Dongwon Jeong djeong@kunsan.ac.kr Department of Kunsan National University 전단 () 후단 () 학습목표 큐 DT 큐의개념및추상데이터타입에대한이해

More information