해킹왕 양선규

PintOS는 알람을 구현할 때 기본적으로 busy waiting 방식을 사용한다.따라서 sleep/wakeup 방식으로 개선하는 것이 목표이다.  timer_sleep 함수는, running중인 스레드를 지정된 ticks 동안 blocked 시키는 함수이다.기존의 timer_sleep은 위 사진처럼 busy waiting이 일어나도록 설계되어 있다. 지정된 ticks가 지날 때 까지 while문 조건을 끝없이 검사하며 의미없이 CPU를 잡아먹는다.즉, 지정된 시간을 기다리기만 할 뿐인 스레드가 무의미하게 while문을 돌며 CPU자원을 소모한다. 이것이 busy waiting이며, 개선해야 하는 부분이다.  어떻게 개선해야 하는가?- thread 구조체에, 깨어나야 할 시간을 의미하는 Local Tic..

응용 프로그램 구현 시, Multiprocess와 Multithread중 하나를 선택하는 기준1. 안정성 vs 자원 사용 : 시스템 안정성이 매우 중요하면 멀티프로세스가 선호된다. 리소스가 제한적인 경우 멀티스레드가 더 효율적일 수 있다.2. 구현의 복잡성 : 스레드는 공유 메모리로 인해 동기화 문제가 복잡해질 수 있다. 따라서 멀티스레드를 사용하려면 개발자의 동시성 제어에 대한 이해도가 중요하다.3. 응답 시간 : 멀티 스레드는 Context Switching이 빠르게 때문에, 빠른 응답 시간을 요구하는 경유 유리하다.4. 플랫폼 및 언어 지원 : 사용 중인 프로그래밍 언어나 플랫폼이, 멀티스레드 또는 멀티프로세스 중 어느 쪽을 더 잘 지원하는지 고려할 수 있다. 멀티프로세스 : 조금 느리고 쉽지만 안..

프로세스(Process)- 관리하는 최소 단위의 작업, 주기억장치에 등록된 프로그램 즉 실행중인 프로그램- CPU에 의해 실행되는 시스템 및 사용자 프로그램- 하나의 응용 프로그램은 여러 개의 프로세스로 이루어질 수 있음 스레드(Thread)- “하나의 프로세스 내에서 동시에 진행되는” 작업 갈래, 흐름의 단위ex) 하나의 브라우저에서, 파일을 다운받으면서 음악을 듣고 쇼핑을 하고 게임도 하는 것- 멀티(다중) 스레드 : 스레드가 여러 개 있는 것- 스레드는 프로세스의 메모리 영역(Code, Data, Heap, Stack) 중 Stack만 할당받아 복사하며, 나머지 Code, Data, Heap은 다른 스레드들과 “공유” 한다.- 따라서 Stack은 별도이지만 Heap은 공유하기 때문에 서로 다른 스레..

파일 디스크립터(File Descriptor, FD)- 유닉스/리눅스 시스템에서 프로세스가 파일을 다룰 때 사용하는 개념, 프로세스에서 특정 파일에 접근할 때 사용하는 추상적인 값- 이 값은 일반적으로 “0이 아닌 양수 정수값”을 갖는다.- 프로세스 실행 중 파일을 Open하면, 커널은 해당 프로세스의 파일 디스크립터 숫자 중 사용하지 않는 가장 작은 값을 할당해 준다.- 이후 프로세스가 System Call을 이용해서 Open되어있는 파일에 접근할 때, FD값을 이용해서 파일을 지칭한다.- 기본적으로 할당되는 FD는 표준입력(Standard Input), 표준출력(Standard Output), 표준에러(Standard Error) 3가지이며 각각 0, 1, 2가 할당된다.   네트워크- 호스트에게 있..

명시적 가용 리스트(Explicit Free lists)- 묵시적 가용 리스트는 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 범용 할당기로는 적합하지 않음- 명시적 가용 리스트는 가용 블록만을 위한 연결 리스트를 만들어 활용한다.- free 블록 안에 predecessor, successor를 넣어서 앞/뒤 미할당 블록을 가리키게 하여 구현할 수 있다. LIFO(Last In First Out) 정책을 사용하여 구현한다.- 할당 해제되어 새롭게 생긴 free 블록을, 리스트의 앞 부분에 삽입하여 Stack처럼 후입선출이 이루어지도록 한다.- free_listp는 항상 리스트의 가장 앞 부분(삽입되는 부분이자 가장 먼저 탐색되는 부분)을 가리키고 있다. - LIFO + first fit 정책을 사용하..

동적 메모리 할당- heap 영역에서 이루어진다.- heap은 위쪽으로(높은 주소 방향으로) 성장한다.- heap의 top(높은 주소 쪽)을 가리키는 변수는 “brk”이며 break로 발음한다.- 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다.- 각 블록은 할당된 블록과, 가용된 가상메모리의 연속적인 묶음이다. 명시적 할당기 - malloc- malloc을 호출해서 메모리 블록을 할당한다.- free를 호출해서 메모리 블록을 반환한다. 묵시적 할당기 - garbage collector- 할당된 블록이 언제 반환되어야 하는지 할당기가 알고 있다- 사용되지 않는 블록을 자동으로 반환하는 작업을 “garbage collection" 이라고 부른다.- List, ML, Java 같은 언어들은 garba..

페이징과 세그먼테이션세그먼테이션(Segmentation)- 메모리를 “세그먼트”단위로 나누는 방법- 각 세그먼트는 시작 길이와 주소를 가지며, 다른 유형의 데이터(코드, 데이터, 스택 등)을 위해 사용됨- 메모리를 유연하게 관리할 수 있게 하며, 프로그램의 논리적 구조를 반영함 페이징(Paging)- 메모리를 동일한 크기의 블록인 “페이지”로 나누는 방법- 각 페이지는 가상 메모리 주소와 매핑되고, 페이지 테이블을 통해 물리적 메모리 주소로 변환됨- 메모리 관리를 단순화시키고 낭비를 줄이며, 프로그램 간 메모리 충돌을 방지함 세그먼테이션 : 장점- 메모리를 논리적 단위로 나눠, 프로그램 구조를 반영한다.- 세그먼트별 보호/공유가 용이하다.세그먼테이션 : 단점- 외부 단편화 발생 가능성- 메모리 관리가 복..

이진 탐색 트리(Binary Search Tree, BST) - 왼쪽 서브트리는 부모 노드보다 작고 오른쪽 서브트리는 부모 노드보다 큰 이진 트리 - BST의 최소값은 “트리의 가장 왼쪽”에 존재한다 - BST의 최대값은 “트리의 가장 오른쪽”에 존재한다 이진 탐색 트리의 삽입 - 아무것도 없는 트리라면 그냥 삽입한다. - 삽입할 노드를 루트 노드부터 하나씩 비교한다. 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 빈 자리를 찾을 때 까지 반복한다. - 같은 값을 가지는 노드는 없다. 이진 탐색 트리의 삭제/검색 - 삭제를 하려면 검색부터 해야 한다. - 찾을 노드를 기준으로, 루트 노드부터 하나씩 비교한다. 삽입할 때처럼 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 값이 같다면 해당 노..

선언(declaration)과 정의(definition) 선언(declaration) - 컴파일러가 참조할 식별자(identifier)의 이름을 알린다. - 식별자란 변수의 타입, 함수의 인자목록을 뜻하며 이름은 변수, 함수, 클래스의 이름 등을 뜻한다. - 선언은 메모리 영역 상에 올리지 않기 때문에 중복되어도 문제가 되지 않는다. extern int a; // 전역변수 선언 int add(int a, int b); // 함수 선언 class ClassId; // 클래스의 선언 정의(definition) - 식별자와 이름으로부터 코드를 생성한 것 - 정의는 고유해야 한다. 같은 식별자와 이름의 정의가 2개 이상이면 컴파일 에러 발생 int add(int a, int b) { // 함수의 정의 (함수 본..

x86-64에서 프로시저에서 프로시저로의 데이터 전달 - 레지스터를 통해서 일어난다. ( 인자들이 %rdi, %rsi등으로 전달되고 %rax로써 리턴되는 형태들을 의미 ) - 프로시저 P가 프로시저 Q를 호출할 때, P는 자신이 전달할 인자들을 레지스터에 복사해야 한다. - 전달할 인자들이 레지스터에 복사되거나 스택에 할당된 후에!!!!!! Q를 호출하게 된다. - Q가 일을 끝내고 P로 리턴할 때, P는 Q가 리턴한 값을 %rax에서 접근할 수 있다. x86-64에서 프로시저에서 프로시저로의 데이터 전달2 - x86-64에서는 “최대 여섯 개의 정수형 인자(정수와 포인터)”가 레지스터로 전달될 수 있다. - 레지스터는 “전달되는 데이터 형의 길이”에 따라서, 정해진 순서대로 이용된다. - “프로시저의 ..