To do - 1 지금 PintOS에서는 쓰레드들이 ready_list에 삽입된 순서대로(Round-Robin) 실행되고 있다. Round-Robin 방식은 쓰레드들의 대기 시간의 총합을 늘릴 수 있기 때문에 각 쓰레드마다 우선순위를 부여하고 우선순위가 높은 쓰레드부터 작업될 수 있도록 한다. 위 동작을 편리하게 하기 위해 list에 삽입되는 쓰레드들이 우선순위가 높은 순으로 정렬한다. ready_list와 synchronization primitives(semaphore, condition variable)에 있는 wait list에 대해 정렬을 해야 한다. Priority order insert ready_list /* thread.c */ bool cmp_priority(const struct li..
Alarm clock /* tests/thread/alarm-priority.c */ .... timer_sleep (wake_time - timer_ticks ()); alarm을 테스트하는 c파일에서는 timer_sleep() 함수를 불러온다. 현재 PintOS는 busy waiting 방식으로 알람이 구현되어 있다. void timer_sleep (int64_t ticks) { int64_t start = timer_ticks (); ASSERT (intr_get_level () == INTR_ON); while (timer_elapsed (start) < ticks) thread_yield (); } busy waiting 방식은 아무것도 하지 않는 쓰레드가 CPU를 점유하고 있는 매우 비효율적인..
synch.h /* A counting semaphore. */ struct semaphore { unsigned value; /* Current value. */ struct list waiters; /* List of waiting threads. */ }; /* Lock. */ struct lock { struct thread *holder; /* Thread holding lock (for debugging). */ struct semaphore semaphore; /* Binary semaphore controlling access. */ }; /* Condition variable. */ struct condition { struct list waiters; /* List of waiting ..
thread.h thread_status enum thread_status { THREAD_RUNNING, /* Running thread. */ THREAD_READY, /* Not running but ready to run. */ THREAD_BLOCKED, /* Waiting for an event to trigger. */ THREAD_DYING /* About to be destroyed. */ }; 쓰레드는 총 4개의 상태를 가지게 된다. 1. THREAD_RUNNING : 실행 중인 쓰레드 2. THREAD_READY : 실행 가능한 쓰레드 3. THREAD_BLOCKED : block 된 쓰레드 4. THREAD_DYING : 곧 사라질 쓰레드 struct thread struct thr..
Soket이란? 소켓은 프로세스가 네트워크로 데이터를 주고 받는 창구 역할을 하며 Unix, Window, Max 등 대부분의 현대 시스템에 내제되어있다. 리눅스 커널의 관점에서 본다면 소켓은 통신을 위한 끝점(endpoint)이다. Endpoint는 아이피 주소와 포트 번호의 조합으로 구성되어져 있다. 소켓은 endpoint를 통해 유일하게 식별되어질 수 있다. 두 소켓이 연결되면 서로 다른 프로세스끼리 데이터를 주고 받을 수 있다. Soket Address Structures /* IP socket address structure */ struct sockaddr_in { uint16_t sin_family; /* Protocol family (always AF_INET) */ uint16_t sin..
동적 메모리 할당 동적 메모리 할당기는 heap이라고 하는 프로세스의 가상메모리 영역을 관리한다. 시스템마다 다르지만 일반적으로 stack은 낮은 영역으로, heap은 높은 영역으로 주소를 확장한다. kernel은 변수 brk를 사용하여 heap의 꼭대기를 가리킨다. 프로그램을 실제로 실행시키기 전에 자료 구조의 크기를 알 수 없는 경우가 많다. 따라서 임의의 큰 값 할당하기보다는 런타임 중 필요한 크기를 알게 되었을 때 할당해 주는 동적할당 방식이 매우 효율적이다. 할당기의 요구사항과 목표 요구사항 임의의 요청 순서 처리하기 요청에 즉시 응답하기 힙만 사용하기 블록 정렬하기 할당된 블록을 수정하지 않기 목표 처리량 극대화하기 메모리 이용도를 최대화하기 할당기를 구현하기 전에 알아둬야 할 점 malloc..
1. Cookie Session 인증방식 기존에는 쿠키와 세션을 이용한 인증방식을 사용했다. 사용자가 개인 PC를 통해 서버에 로그인을 요청하면 서버는 아이디와 비밀번호를 확인 후 고유 세션 아이디 값을 생성한다. 서버는 생성된 아이디 값을 저장하고 그 값을 사용자에게 전송한다. 전송된 아이디 값은 브라우저의 쿠키에 입력되어 저장된다. 이후 사용자가 서버에 접근할 때마다 서버는 쿠키에 저장된 세션 아이디를 확인하며 인증이 이루어진다. 서버에 모든 세션 아이디 값이 저장되어 있기 때문에 서버의 보안이 뚫리면 모든 사용자의 정보가 유출될 수 있다는 단점이 있다. 2. JWT 인증방식 쿠키와 세션을 이용한 인증방식을 개선하고자 JWT 인증방식이 도입되었다. JWT란 JSON Web Signature의 약자로 ..
이 글은 Ries 마법의 슈퍼마리오 블로그와 plzrun's algorithm 블로그 내용을 기반으로 작성하였습니다. 1. Suffix Array 1. Suffix Array란? Suffix Array는 접미사 배열로 문자열의 접미사들을 사전순으로 나타낸 것이다. Suffix Array를 활용하면 문자열 탐색을 보다 효율적으로 할 수 있다. banana는 총 6개의 접미사를 가지며 Suffix Array는 다음과 같다. Suffix Array 접미사의 시작 인덱스를 가지고 있기 때문에 [5,3,1,0,4,2]가 된다. Suffix Array를 구하는 데 걸리는 시간복잡도는 어떻게 될까? 네이브 한 방식으로 구현한다면 문자열을 비교하는데 O(n) 그리고 정렬을 하는데 O(n log n)이므로 총 O(n2 ..
해당 포스팅은 Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편을 보고 작성하였습니다. 1. 병합 정렬(Merge Sort) 병합 정렬은 배열을 앞 뒤 두 부분으로 나누어 정렬한 후 병합하는 정렬이다. 위는 크기 8의 병합 정렬되는 과정이다. 크기가 1이 될 때까지 쪼개지고 서로 정렬되면서 병합되는 것을 확인할 수 있다. 쪼개고 합치는데 O(log n) 정렬 할 때마다 O(n)이 걸려 총 O(n log n)이 걸린다. from typing import Sequence, MutableSequence def mergesort(a : MutableSequence)->None: def _mergesort(a:MutableSequence, left:int, right:int)->None: if lef..
