컴퓨터 시스템
1.
하드웨어
•
중앙 처리 장치(CPU) 및 메모리, 입출력 장치로 구성되어, 기본적인 계산용 자원을 제공
2.
운영체제
•
다양한 사용자를 위해 응용 프로그램 간의 하드웨어 사용을 제어하고 조정
3.
응용 프로그램
•
워드 프로세서, 스프레드시트, 컴파일러, 웹 브라우저 등과 같이 사용자를 위해 자원이 어떻게 사용될 지를 정의
4.
사용자
운영체제의 정의
•
컴퓨터 시스템의 기본 목표는 프로그램을 실행하고 사용자 문제를 더욱 쉽게 해결할 수 있도록 돕는 것이다. 이러한 컴퓨터 시스템의 기본 목표를 하드웨어만으로는 사용하기 쉽지 않으므로, 입출력 장치 제어와 같은 자원을 제어하고 할당하는 기능들을 하나의 소프트웨어로 통합한 것이 운영체제이다.
•
일반적으로 운영체제는 컴퓨터에서 항상 실행되는 프로그램이다(커널이라고도 불린다). 운영체제와 관련이 있지만 반드시 커널의 일부일 필요가 없는 프로그램을 시스템 프로그램이라 하고, 시스템 작동과 관련되지 않은 모든 프로그램을 응용 프로그램이라 한다.
•
모바일 기기의 운영체제의 경우에는 핵심 커널뿐 아니라, 응용 프로그램 개발자에게 서비스를 제공해주는 일종의 프레임워크인 미들웨어도 포함한다.
•
즉, 운영체제에는 항상 실행 중인 커널, 개발을 쉽게하고 기능을 제공하는 미들웨어 프레임워크, 시스템을 관리하는데 도움이 되는 시스템 프로그램이 포함된다.
컴퓨터 시스템의 구성
•
현대의 범용 컴퓨터 시스템은 그림과 같은 시스템 버스를 통해 여러 장치 컨트롤러로 구성된다.
•
일반적으로 운영체제에는 각 장치 컨트롤러마다 장치 드라이버가 존재한다.
•
CPU와 장치 컨트롤러는 병렬도 실행되어 메모리 사이클을 놓고 경쟁한다(I/O bust, CPU bust)
시스템 버스
컴퓨터 시스템의 CPU, 메모리, 입출력 장치 등과 같은 시스템 주요 구성 요소들 간에 데이터, 주소 및 제어 신호를 전송하기 위한 통신 경로
데이터의 전송을 담당하는 데이터 버스, 메모리나 입출력 장치와 같은 시스템의 주소 정보를 담당하는 주소 버스, 시스템의 제어 신호를 담당하는 제어 버스가 있다.
인터럽트
•
입출력 작업을 시작할 때 장치 드라이버는 장치 컨트롤러의 레지스터에 작업을 저장한다.
•
장치 컨트롤러는 이렇게 저장된 레지스터의 내용을 검사하여, 입출력 작업을 수행한다.
•
컨트롤러는 장치에서 로컬 버퍼로 데이터를 전송하고, 전송이 완료되면 장치 컨트롤러가 시스템 버스를 통해 인터럽트로 장치 드라이버에게 작업이 완료되었음을 알린다.
•
이런 방식으로 하드웨어는 언제든 시스템 버스를 통해서 CPU에게 인터럽트를 발생 시킬 수 있다.
•
인터럽트는 운영체제와 하드웨어의 상호 작용의 핵심 부분이고, 다른 많은 목적으로도 사용된다.
•
CPU가 인터럽트 되면, CPU는 하던 일을 중단하고 즉시 인터럽트 서비스 루틴이 저장된 위치로 실행을 옮겨 인터럽트 서비스 루틴을 실행한다.
•
인터럽트 서비스 루틴이 완료되면, CPU는 중단되었던 연산을 재개한다.
•
CPU는 인터럽트 요청 라인을 하나의 명령어를 처리할 때마다 확인을 하고, 컨트롤러가 인터럽트 요청 라인에 신호를 보내면 CPU가 이를 감지하고 인터럽트 번호로 인터럽트 벡터 인덱스를 찾아 인터럽트 핸들러 루틴으로 옮겨간다.
•
인터럽트 처리기는 작업 중에 변결될 상태를 저장, 인트럽트 원인 확인, 필요한 작업 수행, 상태 복원 후 CPU를 인터럽트 전 상태로 되돌린다.
•
장치 컨트롤러에서 인터럽트 발생(raise) → CPU 인터럽트 포착(catch) → 인터럽트 핸들러로 디스패치(dispatch) → 핸들러에서 장치 서비스 후 인터럽트 지우기(clear)
•
대부분 CPU에는 2개의 인터럽트 요청 라인이 존재하는데, 복구 불가 메모리 오류와 같은 이벤트를 위한 마스크 불가능 인터럽트와 장치 컨트롤러가 서비스 요청 시 사용하는 마스킹 가능 인터럽트이다.
•
컴퓨터에는 인터럽트 벡터의 주소 개수보다 많은 장치가 있기 때문에, 인터럽트 벡터의 각 원소가 인터럽트 핸들러 리스트의 헤드를 가리키는 방식인 인터럽트 체인을 사용한다.
•
인터럽트 우선순위 레벨을 통해 CPU에서 모든 인터럽트를 마스킹하지 않고 우선순위가 낮은 인터럽트의 처리를 연기할 수 있다.
저장장치
•
범용 컴퓨터는 프로그램 대부분을 메인 메모리(RAM, random-access memory)에 가져와서 사용한다.
•
컴퓨터 전원을 켤 때, 부트스트랩 프로그램이 가장 먼저 실행되어 운영체제를 적재한다.
부트 스트랩
ROM 또는 EEPROM에 저장되어있는 프로그램으로, 입출력 장치나 하드웨어와 같은 시스템을 초기화하고 부트로더를 실행하여 운영체제 커널을 적재하고 메모리에 로드하여 실행시킨다.
•
메인 메모리는 빠르지만 용량이 작고 전원이 공급되지 않으면 내용을 잃어버리는 휘발성이기 때문에, 대부분 컴퓨터 시스템은 하드 디스크 드라이브(HDD)나 비휘발성 메모리(NVM)를 보조저장장치로 제공한다.
•
그 외에도 CD-ROM이나 Blu-ray와 같은 매우 느리지만 용량이 큰 저장 장치를 3차 저장 장치라 한다.
•
HDD나 광 디스크같은 용량이 크고 저렴한 기계적 저장장치와 플래시 메모리나 SSD 같이 비싸고 용량이 작지만 더 빠른 전기적 저장장치가 있다.
•
매우 빠른 RAM을 사용하는 CPU와 상대적으로 느린 NVS 사이에 데이터 전송은 입출력 작업이 길어질수록 성능저하를 유발한다. 이를 해결하기 위해 직접 메모리 접근(DMA, Direct Memory Access) 방식을 사용하여 DMA 컨트롤러(장치 컨트롤러)가 CPU로 부터 명령을 받아와 입출력 장치와 시스템 메모리 간의 직접적인 데이터 전송을 처리한다.
컴퓨터 시스템 구조
1.
단일 처리기 시스템(Single-Processor System)
•
단일 처리 코어의 CPU를 가진 단일 프로세서를 사용하는 컴퓨터 시스템
코어
명령을 실행하고 로컬로 데이터를 저장하기 위한 레지스터를 포함하는 구성요소
2.
다중 처리기 시스템(Multiprocessor System)
•
단일 코어를 가진 CPU가 있는 두 개 이상의 프로세서를 사용하는 컴퓨터 시스템
•
프로세서 수가 늘어날 수록 더 적은 시간에 더 많은 작업을 수행할 수 있기 때문에 처리량이 증가한다.
•
현재는 단일 칩에 여러 코어를 가지는 다중 코어 시스템을 사용한다.
•
칩 내 통신이 칩 간 통신보다 빠르므로 다중 코어 시스템이 단일 코여의 여러 칩보다 효율적일 수 있다.
•
각 코어에는 자체 레지스터 세트와 레벨 1(L1) 캐시라고 불리는 자체 캐시가 존재한다.
•
추가적으로 칩에 레벨 2(L2) 캐시를 통해 두 코어에서 공유하는 공유 캐시가 존재하며, 하위 캐시(L1)는 상위 캐시(L2)보다 작고 빠르다.
3.
클러스터형 시스템(clustered system)
•
클러스터형 시스템은 둘 이상의 독자적 시스템이나 노드들을 연결하여 구성하는 시스템이다.
•
일반적으로 클러스터 컴퓨터는 저장장치를 공유하고 LAN과 같은 고속의 상호 연결망으로 연결된 시스템을 정의한다.
•
클러스터링은 하나 이상의 컴퓨터 시스템이 고장나도 서비스를 계속 제공할 수 있기 때문에 사용된다.
•
다른 컴퓨터들이 응용 프로그램을 실행하는 동안 한 컴퓨터가 활성 서버들을 감시하는 비대칭형 클러스터링과 서버가 둘 이상의 호스트들이 응용 프로그램을 실행하고 서로 감시하는 대칭형 클러스터링이 있다.
•
그 외에도 여러 호스트가 공유 저장장치의 동일한 데이터에 접근할 수 있는 병렬형 클러스터링이 있다. 대부분 운영체제가 이러한 동시 접근을 지원하지 않으므로 특수 소프트웨어가 사용된다.
운영체제의 동작
1.
다중 프로그래밍과 다중 태스킹
•
일반적으로 하나의 프로그램은 항상 CPU나 I/O 장치를 바쁘게 유지할 수 없기 때문에, 여러 프로그램을 실행할 수 있다.
•
다중 프로그래밍(multiprogramming)은 CPU가 항상 한 개 이상의 프로그램을 실행할 수 있도록 구성하여, CPU 이용률을 높이는 것이다. 다중 프로그래밍 시스템에서 실행 중인 프로그램을 프로세스라고 한다.
•
운영체제는 여러 프로세스를 메모리에 유지하는데, 메모리의 프로세스 중 하나를 선택하여 실행한다. 만약 실행 중인 프로세스가 입출력이나 다른 이유로 대기해야한다면 CPU는 다른 프로세스로 전환하여 작업을 수행한다. 이러한 방식으로 CPU에서 여러 프로세스를 실행시키는 것을 다중 프로그래밍이라고 한다.
•
다중 태스킹(multitasking)은 다중 프로그래밍의 논리적 확장으로, CPU에서 여러 프로세스를 전환하면서 실행하지만 전환이 자주 발생하여 사용자에게 빠른 응답 시간을 제공한다.
•
다중 태스킹 시스템에서 운영체제는 적절한 응답 시간을 보장해야하기 때문에, 적절한 CPU 스케줄링 알고리즘을 선택하고 그에 따라 시스템은 다음에 실행할 프로세스를 선택한다.
2.
이중-모드와 다중모드
•
운영체제와 사용자는 컴퓨터 시스템의 하드웨어 및 소프트웨어 자원을 공유하기 때문에, 응용 프로그램으로 인해 운영체제 자체가 잘못 실행되는 상황이 발생하지 않도록 보장해야한다. 모드 비트를 통해 운영체제의 작업과 사용자가 실행시킨 응용 프로그램을 차별화할 수 있다.
•
모드 비트(mode bit)라는 하나의 비트가 컴퓨터의 하드웨어의 현재 모드를 나타낸다. 모드 비트를 통해 커널 모드(0)와 사용자 모드(1)를 나타낸다.
•
운영체제를 위해 실행되는 작업은 커널 모드(수퍼바이저 모드, 시스템 모드)로, 사용자를 위해 응용 프로그램을 실행할 때는 사용자 모드로 구분한다.
•
시스템이나 다른 프로그램에 악영향을 미칠 수 있는 일부 명령을 특권 명령(privileged instruction)이라 부르고, 하드웨어는 특권 명령이 커널 모드에서만 수행되도록 허용한다.
•
커널 모드로 전환하는 명령어나 I/O 제어, 타이머 관리, 인터럽트 관리와 같은 명령어들이 특권 명령이다.
•
인텔 프로세서에는 4개의 분리된 보호 링이 있는데 이를 통해 다중모드를 지원한다.
•
가상화를 지원하는 CPU는 VMM(virtual machine manager)가 시스템을 제어하는 상황을 나타내기 위한 별도의 모드를 가진다. 해당 모드에서 VMM은 사용자 프로세스보다 많은 권한을 가지지만 커널 모드보다는 적은 권한을 가진다.
3.
타이머
•
사용자 프로그램이 무한 루프에 빠지거나 시스템 서비스 호출에 실패해 제어가 운영체제로 복귀하지 않는 경우를 대비하여, 타이머를 사용한다.
•
타이머는 지정된 시간 후 인터럽트를 발생시키고, 운영체제는 이를 치명적 오류로 취급하거나 프로그램에 추가 시간을 제공한다.
•
운영체제는 사용자에게 제어를 양도하기 전에 타이머가 인터럽트할 수 있도록 설정되었는 지 확인 후 제어를 넘긴다.
자원관리
1.
프로세스 관리
•
프로그램은 디스크에 저장된 파일처럼 수동적(passive) 개체지만, 프로세스는 다음 수행할 명령의 주소를 가리키는 프로그램 카운터(program counter)를 가진 능동적(active) 개체다.
•
하나의 프로세스는 하나의 시스템 내의 작업 단위이다. 시스템은 프로세스의 집합으로 구성되는데, 프로세스 중 일부는 운영체제 프로세스(시스템 코드를 수행하는 프로세스)들이고 나머지는 사용자 프로세스(사용자 코드를 수행하는 프로세스)이다.
•
운영체제는 이러한 모든 프로세스를 단일 CPU 코어에서 멀티플렉싱하거나 여러 CPU 코어에서 병렬로 실행한다.
•
사용자 프로세스와 시스템 프로세스의 생성과 제거, CPU 스케줄링, 프로세스 context switching, 프로세스 동기화, 프로세스 통신와 같은 프로세스 관리를 책임진다.
2.
메모리 관리
•
메인 메모리(RAM)는 CPU가 직접 접근할 수 있는 유일한 메모리로, CPU가 디스크의 데이터를 처리하기 위해서는 입출력 호출에 의해 먼저 메인 메모리로 전송되어야한다. 또한, CPU가 명령을 수행하기 위해서는 명령이 메인 메모리 내에 있어야 한다. 이렇게 프로그램이 수행되기 위해서는 절대 주소로 매핑(mapping)되고 메모리에 적재되어야한다.
•
CPU 이용률과 사용자에 대한 컴퓨터 응답 속도를 개선하기 위해, 위와 같이 메모리에 여러 프로그램을 유지해야 하는데 이를 위해 메모리 관리 기법이 필요하다.
•
특정 시스템에서 메모리 관리 기법은 여러 요인에 의해 결정되지만, 적용되는 알고리즘에 대한 하드웨어 지원이 필요하기 때문에 주로 하드웨어 설계에 영향을 많이 받는다.
3.
파일 시스템 관리
•
운영체제는 파일을 물리적 매체로 매핑하여, 저장장치를 통해 파일에 접근한다.
•
각 저장장치는 각자의 특성과 물리적 구성을 가지는데, 대부분 디스크 드라이브와 같은 장치에 의해 제어된다.
•
일반적으로 파일은 프로그램(소스와 목적 프로그램)과 데이터를 나타내는데, 데이터 파일은 숫자와 영문자, 영숫자 등으로 구성되고 텍스트 파일과 같이 자유 형태일수도 mp3 파일처럼 포매팅된 형태일 수도 있다.
•
운영체제는 파일 관리를 위해 파일과 디렉토리의 생성 및 제거, 파일과 디렉토리 조작, 보조저장장치로 매핑, 파일 백업 등의 일을 담당한다.
4.
대용량 저장장치 관리
•
대부분의 프로그램은 메모리에 적재되어 프로세스가 생성되기 전까지 하드 디스크와 같은 보조저장장치에 저장한다.
•
운영체제는 이러한 보조저장장치 관리를 위해 마운팅과 언마운팅, 사용 가능 공간(free-space) 관리, 저장장소 할당, 디스크 스케줄링, 저장장치 분할, 보호 등의 활동을 담당한다.
5.
캐시 관리
•
데이터는 일반적으로 메인 메모리와 같은 저장장치에 보관되는데, 이러한 데이터가 사용될 때 메인 메모리보다 더 빠른 장치인 캐시에 일시적으로 복사된다. 이러한 작업을 캐싱이라하는데, 특정 데이터가 필요할 때 캐시를 뒤져 해당 데이터가 있는지 확인하여 빠르게 처리한다.
•
캐시로부터 CPU 및 레지스터로 데이터를 전송할 때는 운영체제의 간섭 없이 하드웨어적으로만 이루어진다. 하지만 디스크와 메모리 간의 데이터 전송은 대부분 운영체제에 의해 제어된다.
•
캐시는 빠르지만 크기가 제한되어 있기 때문에 운영체제는 제어 캐시의 교체 알고리즘을 통해 캐시를 관리한다.
•
A 데이터를 가져올 때 디스크에서 메인 메모리로 데이터를 복사하고, 해당 데이터를 캐시에도 복사 후 내부 레지스터에도 복사 한다. 이렇게 A 데이터의 복사본이 여러 곳에 존재하게 된다. 여러 CPU가 동시에 실행되는 환경에서라면 한 캐시에 있는 A의 값이 변할 경우 A가 존재하는 모든 캐시에 즉각적으로 반영되어야 하는 것을 캐시 일관성 문제라고 한다. 이는 하드웨어적 문제로 이를 보장하는 다양한 방법들이 있다.
6.
입출력 시스템 관리
•
UNIX의 입출력 장치는 입출력 서브시스템에 의해 운영체제로부터 숨겨져 있는 것 처럼, 운영체제의 목적 중의 하나는 사용자에게 특정 하드웨어 장치의 특성을 숨기는 것이다.
•
입출력 시스템은 버퍼링과 캐싱, 스풀링을 포함한 관리 구성요소, 장치 드라이버 인터페이스, 특정 하드웨어의 장치 드라이버로 구성되어 있다.
•
입출력 서브시스템은 장치 드라이버만이 지정된 장치의 특성을 알고있도록 하는 시스템이다.
보안과 보호
•
운영체제는 데이터에 무분별한 접근을 규제하기 위해, 파일과 메모리 영역, CPU 등의 자원들에 대해 운영체제로부터 허가를 받은 프로세스만 작업을 할 수 있도록 한다.
•
메모리 주소지정 하드웨어는 프로세스에 할당된 주소 영역에서만 실행되도록 하는 것처럼, 여러 주변 장치의 무결성이 보호받도록 장치 제어 레지스터들에 사용자가 접근할 수 없도록 한다.
•
보호(protection)는 이렇게 컴퓨터 시스템이 정의한 자원에 대해 프로그램이나 프로세스, 사용자의 접근을 제한하는 기법이다.
•
컴퓨터 시스템의 보호 기능이 존재하더라도 사용자의 인증 정보가 도난당해 사용자의 데이터가 복사되거나 삭제될 수 있다. 바이러스나 랜섬웨어, 식별자 도용, 서비스 도용 등의 이러한 내외부의 공격을 방어하는 것이 보안 기능이다.
•
운영체제 대부분은 사용자 식별자(user ID)의 리스트를 유지하고, 사용자마다 할당되어 사용자의 모든 프로세스나 스레드에 연관되어 사용된다.
•
추가적으로 파일의 소유자가 아닌 다른 사람에게는 별도의 낮은 권한을 부여하기 위해 그룹 식별자(group ID)의 리스트를 통해 그룹의 권한을 부여한다.
가상화
•
가상화는 단일 컴퓨터의 하드웨어를 여러 실행 환경으로 추상화하여 개별의 독립된 컴퓨팅 환경을 구축할 수 있는 기술이다. 단일 운영체제에서 여러 프로세스를 전환하여 실행하는 것처럼, 가상 머신을 통해 다양한 운영체제 간에 전환할 수 있다.
•
소프트웨어로 하드웨어를 시뮬레이션 하는 것을 에뮬레이션이라 부르는데, 일반적으로 컴퓨터의 CPU와 시뮬레이션 할 CPU가 다른 경우에 사용된다. 에뮬레이션은 비용이 크기 때문에, 비슷한 성능 수준일 경우에 에뮬레이트된 코드는 원래의 코드보다 훨씬 느리게 동작한다.
•
반면 가상화는 컴퓨터의 CPU와 동일한 CPU의 다른 운영체제를 구축할 때 사용된다. 호스트 운영체제 위에 가상 머신 관리자(VMM)을 통해 하드웨어를 추상화하여 게스트의 운영체제 환경을 구축한다.
분산 시스템
•
분산 시스템은 물여러 컴퓨터 또는 서버로 구성된 네트워크 시스템으로, 분산 시스템의 컴퓨터들은 동일한 작업을 수행하고 자원을 공유하여 협력적으로 동작한다.
•
분산 시스템은 개별 컴퓨터가 아닌 네트워크 전체로 동작하는데, 이는 자원을 공유하여 효율성을 높이고 여러 컴퓨터에서 작업을 분산하여 병렬처리하여 성능을 향상시킬 수 있다. 또한 하나의 컴퓨터에 장애가 발생하더라도 다른 컴퓨터가 작업을 처리할 수 있고, 새로운 컴퓨터를 추가하거나 제거하여 쉽게 시스템의 규모를 확장하거나 축소할 수 있다.
•
분산 시스템은 대규모 데이터 처리나 클라우드 컴퓨팅, 실시간 협업 시스템, 분산 데이터베이스 등에서 사용된다.
네트워크
•
네트워크는 두 개 이상의 시스템의 통신 경로로, 사용되는 프로토콜이나 노드간의 거리, 전송 매체에 따라 다르게 구성된다.
•
TCP/IP는 인터넷에서 사용되는 가장 일반적인 네트워크 프로토콜로, 대부분의 운영체제에서는 TCP/IP를 지원한다.
•
노드의 거리에 따라서는 근거리 통신망(LAN), 광역 통신망(WAN), 도시권 통신망(MAN) 등으로 구분된다. 또한, 블루투스와 같은 무선 통신 기술을 사용한 단거리 통신망(PAN, personal-area network)도 있다.
•
네트워크 운영체제는 다른 컴퓨터의 프로세스와 메세지나 데이터를 교환할 수 있도록 기능을 제공하는 운영체제를 말한다.
커널 자료구조
1.
배열
•
배열은 각 원소가 직접 접근가능하도록 메모리의 연속된 주소를 할당한 자료구조를 말한다.
•
메인 메모리는 하나의 큰 배열로 볼 수 있다.
2.
단일 연결 리스트
•
데이터를 포함하는 하나의 노드(항)가 다른 노드를 가리키는 형태의 자료구조로, 각 원소에 직접 접근할 수는 없지만 연속된 순서를 통해서 데이터에 접근할 수 있다.
3.
이중 연결 리스트
•
연결 리스트에서 노드를 양방향으로 가리키도록 연결한 자료구조다.
4.
원형 연결 리스트
•
연결 리스트의 마지막 노드가 첫 노드를 가리키게 만들어 전체를 순환할 수 있는 자료구조다.
5.
스택
•
순차적으로 데이터를 쌓아 올리며 저장하고, 반대로 나중에 저장된 데이터부터 꺼내는 후입선출(LIFO, Last-In-First-Out)의 자료구조이다. 데이터 처리는 가장 나중에 저장된 데이터를 꺼내거나 그 위에 저장하고, 이를 각각 pop과 push가 있다.
•
운영체제에서는 프로세스의 메모리 영역 중 스택 영역이 해당 자료구조와 동일하게 동작하고, 함수를 호출할 때 매개변수나 인자, 로컬 변수, 복귀 주소가 저장되었다가 함수가 종료되면 저장된 역순으로 삭제된다.
6.
큐
•
데이터를 저장된 순서대로 먼저 꺼내는 선입선출(FIFO, First-In-First-Out)의 자료구조이다. 데이터 처리는 가장 처음의 데이터를 꺼내는 pop과 데이터들의 가장 뒤에 저장하는 push가 있다.
•
프린터에서 작업물을 출력하는 순서나 CPU에서 작업을 기다리는 순서는 큐의 자료구조와 동일하게 동작한다.
7.
트리
•
부모-자식 관계를 가진 자료구조로, 데이터의 서열을 표시하는데 사용 가능하다.
•
최대 두 개의 자식을 가지는 트리 구조를 이진 트리라고 부르며, 이진 탐색 트리는 좌측 자식 ≤ 부모 ≤ 우측 자식의 순서를 요구한다. 이진 탐색 트리는 최악의 경우 O(n)의 시간복잡도를 가지며, 이런 상황을 방지하기 위해 최악의 경우에도 O(log n)을 보장하는 균형 이진 탐색 트리나 red-black tree와 같은 변형 트리가 사용된다.
8.
해시 함수와 해시 맵
•
해시 함수는 데이터를 받아 특정한 산술 연산을 수행하여 인덱스를 반환하는 함수로, 배열 형태의 해시 테이블에서 원하는 데이터가 저장된 인덱스를 해시 함수를 통해 찾아 데이터를 꺼낸다.
•
연결 리스트의 경우 O(n)의 시간복잡도를 가지는데, 해시 맵의 경우 평균적으로 O(1)의 시간 복잡도를 가진다. 이러한 이유로 운영체제에서 광범위하게 사용된다.
•
서로 다른 두 입력이 해시 함수에서 같은 출력을 가지는 경우를 해시 충돌(hash collision)이라 하며, 여러 방법이 있지만 대표적으로 해시 테이블의 각 항에 연결 리스트를 두어 충돌을 해결할 수 있다.
•
해시 함수를 통해 얻은 출력을 [키: 값]으로 매핑시키는 것을 해시 맵이라 한다.
9.
비트맵
•
비트맵은 n개의 상태를 나타내기 위해 n개의 이진 비트를 사용하는 방법이다. 4개의 자원이 존재할 때, 1번과 3번 자원만 사용 가능하다면 0101과 같은 형태로 표현하는 방법이다.
•
8비트의 bool을 사용할 때 비트맵을 사용하는 것보다 8배 많은 자원을 사용하는 것으로, 이처럼 비트맵을 사용하면 대량의 자원 상태를 표시할 때 사용된다.
•
디스크 드라이브는 디스크 블록이라 불리는 수천 개의 독립된 단위로 나누어지는데, 각 디스크 블록의 가용 여부를 비트맵을 통해 저장하고 있다.