beMajor

File System 파일 시스템은 2차 저장장치의 느린 속도를 극복하기 위해 온갖 기법이 들어가서 매우 복잡하다. 여기서 하는 정리는 수박 겉핥기 정도이다. 구체적으로 더 공부하고 싶다면 대학원에 진학하면 된다 File 기본 개념 File 이란 파일이란 데이터와 프로그램을 위한 '그릇'이다. 프로세스처럼 데이터와 프로그램이 logical address space에 연속적으로 존재한다. File Structure 종류 OS와 프로그램이 구조를 결정한다. None: words, bytes의 연속 Simple record structure: 레코드 단위, 한 줄이 한 의미를 가짐 - Lines: Fiexd(라인 길이 고정), Variable(라인 길이 가변) Complex Structures - Format..

Skip List 일반 Linked List는 정렬이 되어있더라도 그 이점을 살리지 못하고, 원하는 노드를 찾기 위해 헤드부터 끝까지 쭉 돌아야 한다. == O(n). Skip List는 일반 Linked List에 level의 개념을 추가해서 마치 binary search tree처럼 탐색 속도를 줄이는 자료구조라고 할 수 있다 우선 생긴 것은 아래와 같다. 출처: https://en.wikipedia.org/wiki/Skip_list#/media/File:Skip_list.svg 각 노드마다 위쪽으로 길게 포인터가 붙어있는데, 이것을 레벨이라고 한다. (위에서부터 0이라 하는지, 밑에서부터 0이라 하는지 등의 구체적인 것은 구현에 따라 달라질 수 있음) 먼저 find를 생각해보자. 위의 Skip Li..

x86 운영체제에서는 다음과 같은 과정을 거쳐 interrupt를 호출한다 1. interrupt n instruction 수행. 2. IDT에 등록되어있는 ISR(interrupt Service Routine) 수행. xv6는 위의 두 과정을 아래와 같이 진행한다. 1. interrupt n instruction - “int n” instruction workflow. 1) IDT(interrupt descriptor table)에서 n’th descriptor를 읽어온다. - 시스템 부팅시 tvinit() 함수로 vertors.S의 번호, DPL을 다 초기화 해줌. - system call은 DPL이 유저 레벨로 세팅됨 2) CPL이 DPL보다 작거나 같은지를 확인함(커널 모드: 0, 유저 모드: 3..

수업 중 selection sort를 C로 구현하는 게 있어 업로드 합니다? 한다? 매번 C++ 을 쓰다가 C를 쓰니 문법이 기억날랑말랑 했다. 하지만 멀록은 내가 가장 좋아하는 명령어라서 기억이 났다. Selection sort 과정 Selection sort은 정렬 기법 중에 하나로 구현은 쉽지만 시간복잡도가 크다. 오래 걸린다는 뜻이다. Selection sort의 구현방법은 다음과 같다. (오름차순 기준) 1. N개의 숫자가 무작위로 있다고 가정할 때, 각각 1번, 2번 ... N-1번, N번 이라고 생각해보자. 2. index를 1로 초기화한다 3. index번 ~ N번까지 중 가장 작은 수를 찾는다. 4. 젤 작은 것을 찾아 index 위치의 수와 자리를 바꾼다. 5. index++을 해준 뒤..