이진 트리란?이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조다.주요 특성:각 노드는 0, 1, 또는 2개의 자식 노드를 가질 수 있다.자식 노드는 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분된다.루트 노드부터 시작하여 계층적 구조를 형성한다.이진 트리의 종류1. 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진다.2. 포화 이진 트리(Full Binary Tree): 모든 내부 노드가 두 개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있다.3. 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하다.4. 편..

트리란?트리는 계층적 관계를 표현하는 비선형 자료구조다. 노드(node)들과 그 노드들을 연결하는 간선(edge)들로 구성되어 트리 모양의 형태를 가진다.트리의 구조루트(Root): 트리의 최상위에 있는 노드노드(Node): 트리를 구성하는 각 요소간선(Edge): 노드와 노드를 연결하는 선부모 노드(Parent Node): 서브트리를 가지는 노드자식 노드(Child Node): 부모 노드 밑에 연결된 노드형제 노드(Sibling Node): 부모가 같은 자식 노드들리프 노드(Leaf Node): 자식이 없는 노드내부 노드(Internal Node): 적어도 하나의 자식을 가진 노드서브트리(Sub Tree): 큰트리의 속하는 작은 트리트리의 특징계층적 구조트리는 계층적 구조를 가진다. 하나의 루트 노드에..

scanf와 printf scanf (Scan Formatted)scanf는 표준 입력에서 형식화된 데이터를 읽어들이는 입력함수다.int a;double b;scanf("%d %lf", &a, &b);형식 지정자를 통해 입력 데이터의 타입을 지정변수의 주소를 인자로 받아 해당 메모리에 직접 값을 저장 printf (Print Formatted)scanf는 형식화된 데이터를 표준 출력으로 내보는 출력함수다.int a = 10;double b = 3.14;printf("정수: %d, 실수: %.2f\n", a, b);형식 지정자를 통해 출력 형식을 지정변수의 값을 직접 인자로 전달주요 형식 지정자:%d: 정수%f: 부동소수점 수%c: 문자%s: 문자열cin과 cout cin (Console Input)cin..

지연 로딩은 메모리 로딩을 필요한 시점까지 미루는 설계 방식이다. 페이지 구조체는 할당되어 페이지에 해당하지만, 전용 물리 프레임은 없고 페이지의 실제 내용은 아직 로드되지 않는다. 내용은 실제로 필요한 시점에만 로드되며, 페이지 폴트에 의해 로드된다.페이지 타입이 세 가지이므로 초기화 루틴은 각 페이지마다 다르다. 커널이 페이지 할당 요청을 받으면 vm_alloc_page_with_initializer를 호출한다. vm_alloc_page_with_initializer함수는 페이지 구조체를 할당하고 페이지 타입에 따라 적절한 초기화 함수를 설정하여 초기화한 후 supple_ment_page_table에 삽입한다. 프로세스는 실제 메모리에 로드가 되지 않은 가상주소로 접근을 한다. 이때 페이지에 내용이 ..

frame_table프레임 테이블을 만들어야하는 이유는 뭘까? 우리는 페이지 폴트시 프레임을 할당하고 페이지와 매핑해야한다. 이때 그것을 관리하는 페이지가 필요하게된다. 그렇담 이것을 언제 활용하게 될까?프레임 테이블은 현재 물리메모리에 올릴수 있는 프레임이 꽉차 더이상 물리메모리에 올릴수 없을때 어느 프레임을 swap out을 할지 정할때 사용하게 된다. 이때 프레임 테이블을 참조해 교체 알고리즘에 때라 swap out할 프레임을 정하게 된다.struct framevm헤더 파일에 frame_table을 정의한다. list로 frame_table을 만든 이유는 clock 교체 알고리즘을 사용하기 위해서다.그리고 frame 구조체에 프레임 테이블에 삽입할 list_elem을 정의한다.vm/vm.hstruc..

Supplement Page Table보충 페이지 테이블은 각 페이지에 대한 추가 데이터를 가지고 있어 페이지테이블을 보완한다. 보충 페이지 테이블이 필요한 이유는 크게 두가지다페이지 폴트 발생 시, 커널이 보충 페이지 테이블을 참고해 프레임과 매핑이 안되었는지 안되었을때 프레임에 할당해야할 데이터는 어떤 데이터인지를 확인한다.커널은 프로세스가 종료될 때 메모리 누수를 막기위해 해제해야할 페이지를 보충 페이지 테이블을 참조해 결정한다. 페이지 폴트 처리페이지 폴트 발생시 커널은 anonymous page인지 file-backed페이지인지 확인한다. 파일 또는 스왑 슬롯에서 페이지를 가져와야 한다면. userprog/exception.c의 페이지 폴트 핸들러 page_fault()는 vm/vm.c의 페이지..

Virtual Memory가상메모리는 DRAM의 추상화다. 이게 무슨 말일까? CPU가 데이터를 읽고 쓰려면 물리메모리 즉, DRAM에 적재되어야 사용할 수 있다. 이때 우리는 이런 경우를 신경쓸 필요가 있나?파일을 로드하거나 동적으로 메모리를 할당할때 물리메모리의 어느곳에 적재되어야하는지물리메모리의 크기보다 데이터의 크기가 클때 어떻게 해야하는지현재 실행중인 프로세스가 다른 프로세스가 사용중인 메모리 영역을 침범하지는 않는지 우리는 이런 경우를 신경 쓰지 않고 정적 파일을 물리메모리에 로드하거다 동적으로 메모리를 할당 받는다. 이런 궂은 일은 운영체제가 하고 우리에게는 API를 제공해주는 거다. 우리는 DRAM을 추상화한 가상메모리를 사용하는거다.처음 운영체제를 설계할때 디자인 컨셉중에 하나는 하나의 ..

Project2-0 BackgroundProject2-1 Passing the argumentsProject2-2 User Memory Access개요시스템 콜은 소프트웨어 예외의 한 종류로 간주된다. 유저 프로그램은 시스템 콜을 통해 운영 체제에 서비스를 요청할 수 있다. x86-64 아키텍처에서는 syscall 명령어를 사용하여 시스템 콜을 호출핰다. 이는 기존의 x86 아키텍처에서 시스템 콜이 다른 소프트웨어 예외와 동일한 방식으로 처리되던 것과 대조적이다. 시스템 콜을 호출할 때는 시스템 콜 번호와 인수를 레지스터에 설정해야 한다. 시스템 콜 번호는 %rax 레지스터에 저장되며, 인수는 %rdi, %rsi, %rdx, %r10, %r8, %r9 순서로 전달된다. 이는 네 번째 인수는 %rcx로 전..