justgo_developer

레드블랙트리(Red-Black Tree)- 이진탐색트리의 일종- 균형잡힌 트리 : 높이가 O(logn)- SEARCH,INSERT,DELETE를 수정함으로써 균형을 잡히도록 만듬 -각 노드는 하나의키(key),왼쪽자식(left),오른쪽자식(right),그리고 부모노드(p)의 주소를 저장- 자식노드가 존재하지 않을 경우 NIL 노드라고 부르는 특수한 노드가 있다고 가정- 따라서 모든 리프노드는 NIL노드- 루트의 부모도 NIL노드라고 가정- 노드들은 내부노드와 NIL노드로 분류 다음 조건을 만족하는 이진탐색트리 :1. 각 노드는 red 혹은 black이고,2. 루트노드는 black이고 3. 모든 리프노드(즉 NIL노드)는 black이다.4. red노드의 자식노드들은 전부 black이고(즉, red노듣 연속..

Process Switching 일어나는 경우- Interrupt- Trap- Supervisor call ■ Interrupt- Clock interrupt: 일정시간 간격으로 걸리는 인터럽트- I/O interrupt: I/O 반응때 일어나는 인터럽트- Memory fault: 메모리주소가 가상메모리에 있어서 메인메모리로 옮겨야 할때 ■ Trap- 에러 또는 예외발생 할때 ■ Supervisor call(System call)- 명백한 요청일때ex)파일 오픈 mode switching- 사용자 모드에서 커널모드로 변경할때 발생- 완전 문맥 전환이 필요하지 않아 시스템 스택 사용 process switching- 현재 실행중인 프로세스를 중단하고 새 프로세스를 실행할때 발생- 완전 문잭 전환

Process 정의- 수행중인 프로그램- 컴퓨터상에서 수행중인 프로그램의 인스턴스- processor에 할당되고 수행되는 객체 PCB(Process Control Block): 운영체제가 다중 프로세스들을 지원하고 멀티프로세싱을 위해 제공하도록 하는 주요한 도구이다.- process 요소들을 포함- 운영체제에 의해 생성되고 관리- 다중프로세스 지원 ■ Process States - Dispatcher : 한 프로세스에서 다른 프로세스로 processor를 바꾼다.■ Swappingprocessor는 입출력장치보다 빠르다. 그래서 모든 프로세스들은 기다려야한다 해결책 -> Swapping: 모든 또는 일부분의 프로세스를 메인메모리에서 디스크로 이동한다.: 좀더 메모리를 이용하기 위해스왑 했을때 blocke..

운영체제의 목적 1. 편의(Convenience)2. 효율(Efficiency)3. 진화능력(Ability to evolve) ■ Convenience 운영체제가 제공하는 서비스1. 프로그램 개발(program development)2. 프로그램 실행(program execution)3. 입출력장치 접근(Access to I/O devices)4. 파일처리(Controlled access to files)5. 시스템 접근(System access)6. 에러검출 및 응답(Error detection and response)7. 관리(accounting) ■ Efficiency- Resource Manager- 운영체제도 일반 컴퓨터 소프트웨어처럼 작동한다. ■ Ability to evolve- 하드웨어 업..

대부분 입출력장치는 processor보다 느리다.그래서 processor는 장치를 기달리기 위해 정지해야한다 . processor 이용 효율을 향상시키기 위해 Interrupt는 제공된다. Interrupt 종류- Program- Timer- I/O- Hardware failure Interrupt Handler - 입출력장치를 처리하기 위한 특정 프로그램- 운영체제의 일부분 program 수행중 interrupt가 발행하면 interrupt handler로 이동한 후 처리 한후 다시 interrupt가 발생된 지점으로 돌아와 프로그램을 다시 수행한다. Multiple Interrupt: 인터럽트 수행중 다른 인터럽트가 발생하면 무시하는방법하고 우선순위에 따라 처리하는 방법이 있다.

Instruction Execution 2가지 단계를 가진다. 1. fetches: processor는 메모리로부터 명령어를 가지고온다. 2. executes(실행하다): processor는 각 각의 명령어를 실행한다. ■ Instruction Fetch and Execute- processor는 메모리로부터 명령어를 가지고 온다.(fetch)- Program counter(PC)는 다음 fetch될 명령어 주소를 가진다.- PC는 fetch후 1 증가한다. ■ Instruction Register- fetch된 명령어는 명령어 레지스터안에 위치한다. ■ 가상머신의 특징 - opcode는 processor가 수행할 operation(연산)을 정의한다.

1. 운영체제(Operationg System) - 하나 또는 하나 이상 processor의 hardware resources 이용한다. - 일련의 서비스를 시스템 유저들에게 제공한다. - 보조기억장치와 입출력 장치를 관리한다.ex) windows, LINUX, mac OS ,android ,ios 등 2. 기본 요소- Processor :처리장치,연산처리장치,처리프로그램,데이터에 연산 조작등 몇개의 처리를 일으키는 기능을 갖는 장치나 프로그램 - Main Memory: 휘발성/ real memory or primary memory라고도 불린다.- I/O modules: secondary memory devices(hard disk) / communications equipment / terminals-..

이진검색트리(Binary Search Tree)-Dynamic set을 트리의 형태로 구현 정의-이진트리이면서 각 노드에 하나의 키를 저장- 각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.**Binary Search Tree하고 heap은 다르다. 최소값 찾기: 왼쪽 자식이 없어야 하고 어떤 노드의 오른쪽 서브트리이면 안된다. TREE-MINIMUM(x)while left[x]≠NILdo x

검색트리(Search Tree) 트리(Tree)란?-계층적인 구조를 표현(조직도,디렉토리와 서브디렉토리 구조, 가계도) 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨. 부모(parent)-자식(child) 관계 형제관계 :부 모가 동일한 노드들 리프(leaf) 노드 : 자식이 없는 노드들 내부(internal)노드 : 리프노드가 아닌것 조상-자손관계 : 부모-자식 관계를 확장한 것 부트리(subtree)레벨(level)트리의 높이는 : 서로다른 노드의 갯수 트리의 기본적인 성질-노드의 n개일때 링크의 갯수는 n-1이다.-트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두노드간의 경로도 유일하다. 이진트리(binary tree)-이진트리에서 각 노드는 최대 2개의..