(Be)전공 개발자

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 List 에서 7 를 찾고 싶다고 생각하면 , 기존의 Linked List 에선 7 개의 노드를 봐야한다 . (1)   1 보고 , 아니네 ? 다음 (2)   2 보고 , 아니네 ? 다음 (3)   3 보고 , 아니네 ? 다음 … (7)   6 보고 , 아니네 ? 다음 (8)   7 보고 , 맞네 ? 찾았다 ! 물론 원하는 게 바로 안 나오면 n 개까지 찾다가 없다고 알아낼 수 있다 . 7 을 7 번만에 찾았다는 건 운이 좋은 경우이고 , 정렬이 되어있더라도 이 사실은 크게 변하지 않는다 ( 일반적인 Linked List 라고 하면 ). 반면 Skip List 에서 8 를 찾고 싶다면 1 -> 4 -> 6 -> 7 을 거쳐 찾을 수 있다 . (1)   1 보고 , 나보다 작네 ? 가장 높은 레벨 (4) 이 가리키는 애를 보자 (2)   Null 을 가리키고 있네 .. 그러면 다음 낮은 레벨 (3) 을 보자 . (3)   4 를 기리키고 있네 ? 내가 찾고자하는 8 보다 작으니 이동하자 (4)   4 에서 같은 레

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, 부를 수 있는지 없는지를 확인하는 것 ) -   이 조건을 충족하지 못하면 부를 수 없는 interrupt 를 부른 것이라 exception 이 발생한다 . 3)        만약 target segment selector 의 PL 이 CPL 보다 작으면 PL 의 변환이 필요하다 (ex PL 이 커널모드인 경우 ). 다음 3 단계를 거쳐서 변환이 일어남 . (1)   현재 유저모드니깐 , 유저모드의 esp, ss register 를 임시로 저장함 ( 임시로 저장하는 이유는 커널 스택에다 푸시하기 위해서 ) (2)   task segment descriptor 에서 esp, ss 를 불러와서 CPU-internal registers 에 저장함 . (3)   이제 아까 임시로 저장한 esp, ss 를 푸시해줌 ( 유저 모드로 돌아가기 위한 esp, ss) 4)        eflags, cs, eip register 를 stack 에 푸시한다 . -   당연히 여기는 Kernal Stack 임 .