컴퓨터 구조

📌 - Rehash() 해쉬 테이블의 버킷 용량이 증가하면 모든 항목을 더 큰 크기의 해쉬맵으로 균등하게 분배하는 작업 HashMap의 버킷을 두배로 늘리고 안의 요소들을 전부 재배치 하는 작업 size_t old_bucket_cnt, new_bucket_cnt; struct list *new_buckets, *old_buckets; old_bucket_cnt, new_bucket_cnt와, new_buckets, old_buckets를 초기화 old_buckets = h->buckets; old_bucket_cnt = h->bucket_cnt; old_buckets와 old_bucket_cnt를 이전 값으로 설정 new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCK..

📌 - Hash table 기본적인 해쉬 테이블은 key - value를 저장하는 구조이다 예를들어서 50을 저장할 때 index = hash_function(50) % 16 을 통해서 해쉬 값을 받아와서 해당 테이블에 저장한다. 이렇게 저장하면 key에 대한 데이터를 찾을 때 한번만 수행하면 index 위치를 찾을 수 있기 때문에 저장과 삭제가 O(1)로 매우 빠르다. 하지만 이런 방식으로 해쉬 테이블을 구현하게 되면 해쉬 값이 겹칠 경우 문제가 발생하는데 겹치게 되면 충돌이 발생한다. 해결 방법으로는 📌 - Seperate Chaining Linked List를 이용하는 방식으로 각 index 데이터를 저장하는 linked list에 대한 포인터를 가지는 방식이다. index로 인해서 충돌이 발생하면..

페이지 테이블 가상 메모리에서 사용되는 중요한 데이터구조 운영 체제는 가상 메모리를 사용하여 물리적인 메모리를 관리하고, 프로세스 에게 가상 주소 공간을 제공한다 페이지 테이블은 가상 주소 공간과 물리적인 메모리 주소공간 간의 매핑을 관리하는데 사용된다. 페이지 64비트 가상주소의 마지막 12비트는 페이지 오프셋이고, 상위 비트들은 페이지 테이블의 인덱스를 표시한다. 프레임 물리 메모리상의 연속적인 영역. 페이지와 동일하게, 프레임은 페이지사이즈여야 하고 페이지 크기에 정렬되어 있어야 합니다. 64비트 물리주소는 프레임 넘버 와 프레임 오프셋 으로 나누어질 수 있습니다. 구현해야 할 것 보조 페이지 테이블 핵심 유저 → 페이지 폴트 핸들러, 프로젝트2에서 페이지 폴트는 항상 커널, 유저프로그램의 버그를 ..

파일 디스크립터(file descriptor) : 리눅스 혹은 유닉스 계열의 시스템에서 프로세스가 파일을 다룰 때 사용하는 개념으로, 프로세스에서 특정 파일에 접근할 때 사용하는 추상적인 값이다. 파일 스크립터는 일반적으로 음수가 아닌 0과 양수인 정수 값을 의미한다. 기본적으로 할당되는 파일 디스크립터 0 : 표준 입력(Standard Input) / STDIN_FILENO 1 : 표준 출력(Standard Output) / STDOUT_FILENO 2 : 표준 에러(Standard Error) / STDERR_FILENO 우리가 생성하는 파일 디스크립터들은 3번부터 차례대로 할당받게 된다. void halt(void): power_off()를 호출하여 pintos를 종료합니다. 이 함수는 교착 상태 ..

📌- Pintos VM layout Stack : 프로그램이 자동으로 사용하는 임시 메모리 영역이며, 지역 변수, 매개변수, 리턴 값 등을 잠시 사용되었다가 사라지는 데이터를 저장하는 영역입니다. 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸됩니다. Heap 영역에 생성된 Object 타입의 데이터 참조값이 할당됩니다. 힙 영역과 반대로 메모리 상위 주소에서 하위 주소 방향으로 추가 할당됩니다. 재귀 함수가 너무 깊게 호출되거나 stack영역을 초과하게 되면 stack overflow 발생 Heap 사용자에 의해 메모리 공간이 동적으로 할당되고 해제되는 영역입니다. 스택 영역과는 반대로 메모리의 하위 주소에서 상위 주소 방향으로 추가 할당됩니다. 클래스, 클로저와 같은 참조형의 데이터 값이 ..

1️⃣ - 쓰레드 상태 (무엇이 있는지, 어떤 함수 또는 인터럽트등이 불려지면 어떤 상태로 전환되는지) - thread에는 `Ready, Running, Dying, Blocked` 상태가 있고, ready_list에서 대기를 하다가 스케쥴러에 의해 running상태가 되었다가 running 상태에서는 sleep함수로 인해 blocked되면서 sleep_list로 옮겨지게 되고 대기 상태가 된다. 그리고 sleep_list에서 다시 unblock을 통해 ready_list로 가게되고 이 과정을 반복하다가 다 사용하게 되면 exit으로 종료처리가 된다. 2️⃣ - 스케줄링이 무엇인지? (1의 함수들 호출과 스케줄링 관계 설명) 스레드들이 ready_list에서 실행되기만을 기다리고 있는데, 무작정 실행 시..