오늘의 목표는 다음과 같습니다.
[목표]
삭제 과정 이론 정복하기
삭제과정 코드로 구현하기
그외의 max, min,array 등 코드 구현하기
컴퓨터 시스템 한 번 훝고 8장 보기
내일이 퀴즈 시행일인 관계로 CS와 트리들의 종류들을 알아보겠습니다.
9:45 ~ 12:00
삭제 이론을 정복하기 전에 max, min, find, array, delete(트리 전체 삭제) 코드를 구현해보았습니다. 노션에도 정리하고 있습니다.
12:00 ~ 13:30
맛있는 식사를 했습니다.
13:30 ~ 14:30
array 관련 코드를 작성하고 이해하여 주석을 추가했습니다.
14:30 ~ 15:00
지금작성한 코드들에 대해 (노드 삭제 제외) 노션에 정리를 했습니다.(아직 안함)
20분간 게임랩에 가서 게임들을 체험했습니다.
15:00 ~ 16:00
지금까지 짠 코드들에 대해 검토를 진행하고 틀린 부분을 수정했습니다. 상단 설명에 삽입 case 3가지를 추가했습니다.
16:00 ~ 16:30
노션에 삽입에 4가지 함수에 대한 설명을 추가하고 delete_rbtree(트리 전체 삭제), find, max, min, array 함수들의 설명과 코드들을 추가했습니다.
16:30 ~ 17:00
컴퓨터 시스템 8장 예외처리 부분을 공부하다가 질리면 RB트리 삭제 파트를 이해하고 구현해보겠습니다.
17:00 ~ 18:00
오늘도 하체 운동을 했습니다.
18:00 ~ 19:10
식사 후 샤워를 하고 복귀했습니다.
19:10 ~ 22:00
오늘 코어타임에 발표할 컴퓨터 시스템 8장과 RB 트리 노드 삭제 이론을 공부하겠습니다.
컴퓨터 시스템 8장(CSAPP)
8장은 컴퓨터의 if, while, function call 같은 일반적인 제어 흐름을 벗어난 특수한 예외적 제어 흐름에 대해 서술합니다.
왜? 예외적 제어 흐름 필요할까?
→ 컴퓨터 시스템에서 갑작스러운 사건이 있다. (예상되지 않은 사건)
- 사용자가 키보드를 누름
- 타이머 만료
- 0으로 나누기를 시도
- 새로운 프로그램 실행
- 다른 프로그램에서 나에게 신호를 보냄
위와 같은 ECF(예외적 상황)에서 대응하기 위함이다.
ECF(예외적 제어 흐름)은 시스템의 모든 계층에서 일어나며 동시성을 제공하는 기본 메커니즘입니다.
하드웨어 수준에서 예외는 CPU 내부 또는 외부에서 발생한 이벤트로 인해 제어 흐름이 갑자기 바뀌는 현상입니다. 이때, 제어 흐름은 소프트웨어 핸들러(처리기)로 넘어가고, 이 핸들러는 특정 처리를 한 다음 중단되었던 흐름으로 복귀합니다.
예외 처리 4가지
예외에는 크게 4가지 종류가 있습니다. 이 예외는 운영체제와 하드웨어가 협력해서 처리하는 ‘이벤트’ 이다.
- Interrupt: 외부 I/O 장치가 CPU에 신호를 보내면서 발생하고, 비동기적으로 발생합니다.(예: 타이머, 디스크 등)
- Fault, Abort: 프로그램 명령어의 실행 중에 발생하는 동기적인 예외입니다.
Fault는 보통 복구 가능해서, 예외 처리 후 같은 명령어를 다시 실행하지만, (페이지 폴트)
Abort는 복구 불가능해서 프로그램이 즉시 종료됩니다.(메모리 오류 → 강제 종료) - Trap: 시스템 콜을 처리하기 위해 의도적으로 발생시키는 예외로, 마치 함수 호출처럼 동작해서, 커널 코드로 진입하는 안전한 방법입니다.(printf() → 시스템 호출)
운영체제 수준 예외 처리(프로세스)
운영체제 수준에서는, 커널이 이러한 예외적 제어 흐름을 기반으로 프로세스(process)라는 개념을 만듭니다.
이 프로세스는 사용자에게 두 가지 중요한 환각을 줍니다.
- 자신이 CPU를 독점하는 것처럼 보이도록 하는 논리적 제어 흐름.
- 자신만의 메모리를 갖는 것처럼 보이게 하는 독립적인 주소 공간.
인터페이스단에서
운영체제와 인터페이스(사용자 프로그램이 맞닿는)에서는
- 사용자 프로그램이 자식 프로세스를 생성
- 자식이 종료되기를 기다림
- 다른 프로그램을 실행
- 다른 프로세스로부터 시그널을 받는 것
위와 같은 상황에서 이 ECF 메커니즘으로 이루어진다.
특히 4번째 예시의 시그널(signal) 처리는 시스템에 따라 의미가 미묘하게 다를 수 있지만, POSIX 표준을 따르는 시스템에서는 예상 가능한 방식으로 시그널 처리기를 설정할 수 있는 기능이 제공됩니다.
C언어에서
마지막으로, 응용 프로그램 수준에서는 C 언어에서 제공하는 함수 nonlocal jump (setjmp, longjmp)를 사용합니다.
위 함수는 일반적인 함수 호출 스택 흐름을 무시하고, 한 함수에서 다른 함수로 직접 점프하는 것으로, 예외적 제어 흐름의 일종이야.
시그널이 제일 중요하다는데 정리를 다하지 못해서 나중에 재정리하여 포스팅하겠습니다.
컴퓨터 시스템 코어타임 시작(22:00 ~ 00:10)
팀원분들께 배운 내용을 대강 정리해보았습니다. 추후에 개념을 구체화하여 따로 포스팅하겠습니다.
컴퓨터 시스템 7장(CSAPP)
컴파일러에 대해서…
링킹의 역할
동적 링킹과 정적 링킹을 합니다.
정적 링킹은 보통 파일 하나로만 작업하니까 c에서 잘 안 쓴다. 특정 상황에서 쓴다. 외부 라이브러리를 사용할 때 쓴다.(외부에서 가져온 파일들)
동적 링킹은 대부분 많이 사용, 리눅스와 맥에서 많이 사용.(만들때 인클루드한 파일들)
큰 규모의 파일들은 정적 링킹을 수행한다.
typedef: 타입을 재정의한다.
int, char 등은 예약어이다. 그래서 stdio.h 파일 안에 없다.
stdio.h 입출력 스트림에 관련된 내용이 주이다. (printf, scanf 등 의 함수 기능도 포함)
컴퓨터 시스템 9장(CSAPP)
가상메모리
virtual memory → logical memory
DRAM에서 프로세스 프라이빗 메모리를 단다
실제 프로그램은 VM에서 진행
VM은 DRAM에 부분을 나눠서 페이징을 하여 사용
VM은 캐시처럼 사용한다. DRAM에 있으면 히트, 없으면 가져오고
2^64-1은
2^n개의 주소가 필요하면 (0 ~ (2^n-1))의 주소가 할당
메모리할당은
MMU(메모리 관리 유닛)이 프로세스를 실제 주소에 메핑을 해서 쓴다.(VM)
프로그램으로 캐시된 메모리는 sRAM이라고 하며 프로세서를 가져올때 DRAM에서 히트를 하지 않았을땐, 하드디스크 가상 공간까지 가야한다.
만약에 DRAM에 페이지가 없다면, PTE에 따라 값이 있는지 확인하고 없으면 디스크에서 가져온다.
sRAM에서 하드로부터 페이징을 해서 가져온다.
page는 4k의 크기를 가져온다.
동적메모리 로케이션(malloc과 free)
malloc(sizeof()) → sizeof만큼 힙에다 저장을 할지
캐스팅은 위 sizeof에 넣기 위해?
page = 4(killobyte) 가 이번 단원에 제일 중요하다.
01:30 ~ 4:30
노드 삭제 문(erase)을 구현했다. 예찬님의 도움을 받아 모두 구현 완료 했습니다.
다 했으나 테스트 케이스에서 버그가 발생하여 원인을 찾고 있습니다. 또 저는 맥북에서 그냥 돌렸는데, RB tree를 구현하기 위해 valgrind가 필요합니다. 그러나 맥북에선 지원을 안하기 때문에 도커로 돌려야만 합니다. 내일 도커를 전환하여 버그를 고쳐보겠습니다.
