커널의 자료구조

728x90

Reporting Date: March. 19, 2025

OS 커널의 자료구조에 대해 다루고자 한다.

목차
01 커널의 자료구조
02 전통적 컴퓨팅의 변화
03 분산 시스템
04 웹 기반 컴퓨팅
05 클라우드 컴퓨팅
06 클라우드 컴퓨팅 관계도
07 실시간 내장형 시스템

01 커널의 자료구조

커널에서는 일반적인 자료구조를 사용하여
프로세스 관리, 메모리 관리, 파일 시스템, 네트워크 스택 등을 구현한다.

리눅스 커널의 자료구조는
linux/include/linux, linux/lib 디렉터리에서
확인할 수 있으며, 대부분 C로 작성되었다.

리눅스 커널의 코드 라인 수는 최신 버전(6.x 기준)에서 약 3500만 줄 정도이다.

윈도우 커널의 경우 정확한 코드 라인 수는 공개되지 않았지만,
Windows OS 코드베이스가 약 5000만 줄 이상으로 추정된다.

리누스 토르발스가 1991년 최초로 공개한 리눅스 커널(버전 0.01)은
약 1만 줄 정도였으며, 이후 발전하면서 현재 수천만 줄까지 증가했다.

1 . 연결 리스트

(Linked List)

노드(Node)와 포인터(Pointer)를
이용하여 데이터를 저장하는 자료구조로,

동적 메모리 할당을 활용하여 크기를 유동적으로 조정할 수 있다.

2 . 연결 리스트의 종류

다음과 같은 세 가지 주요 형태가 있다.

① 단일 연결 리스트

(Singly Linked List)

각 노드가 다음 노드를 가리키는 포인터(next)를 가진다.
한 방향(앞 → 뒤)으로만 탐색 가능하다.

② 이중 연결 리스트

(Doubly Linked List)

각 노드가 이전(previous)과
다음(next) 노드를 가리키는 포인터를 가진다.

양방향(앞 ↔ 뒤)으로 탐색 가능하다.

③ 원형 연결 리스트

(Circular Linked List)

마지막 노드가 첫 번째 노드를 가리키는 구조로,
단일 및 이중 연결 리스트 모두 원형으로 만들 수 있다.

1 . 일반적인 트리 구조

(Tree)

계층적(Hierarchical) 구조를 가진다.

루트 노드(root)를 최상위로 두고,
그 아래에 자식 노드(child)가 연결되는 부모-자식 관계로 구성된다.

일반적인 트리에서는 삽입, 삭제 연산이
명확하게 정의되어 있지 않거나 비효율적일 수 있다.

또한, 트리 구조에서는 노드의 공간적 위치인
왼쪽 또는 오른쪽이 특별한 의미를 가지지 않는다.

2 . 이진 탐색 트리

(Binary Search Tree, BST)

이러한 연산의 비효율성을 극복하기 위해 도입되었다.

데이터를 정렬된 형태로 유지하면서
이러한 연산을 효율적으로 수행할 수 있는 자료구조이다.

각 노드는 왼쪽 자식 < 부모 < 오른쪽 자식의 값을 가지는 규칙을 따른다.

왼쪽 서브트리에는 부모보다 작은 값들,
오른쪽 서브트리에는 부모보다 큰 값들이 저장된다.

이러한 구조 덕분에 데이터의 서열을 표현하거나
정렬된 형태로 출력하는 데 매우 적합하다.

그러나 편향된 트리가 만들어질 경우,
탐색 성능은 최악의 경우 O(n)까지 떨어질 수 있다.

이러한 상황을 방지하기 위해 AVL 트리, Red-Black 트리 등
균형 이진 탐색 트리(Balanced BST)가 사용된다.

균형이 잘 잡힌 경우, 트리의 최대 깊이는 O(log n)이므로
평균적으로 탐색, 삽입, 삭제 모두 동일한 성능을 기대할 수 있다.

3 . 해시 함수

(Hash Function)

데이터를 입력으로 받아,
산술 연산(주로 모듈러 연산) 등을 통해
고정된 크기의 해시 값(해시 코드)을 반환하는 함수이다.

이 값을 이용하면 데이터에 빠르게 접근할 수 있어,
검색 성능을 크게 향상시킬 수 있다.

특히 해시 테이블이나 해시 맵을 구현할 때 사용된다.

단점

서로 다른 입력값이지만 동일한 해시 값이 나오는 현상인
해시 충돌 (Hash Collision)이 발생한다.

충돌을 해결하기 위해 체이닝(Chaining),
오픈 어드레싱(Open Addressing) 등의 기법이 사용된다.

4 . 비트맵

(Bitmap)

0 또는 1로 구성된 이진 비트 배열.

n개의 항목 상태를 표현하기 위해
n개의 비트를 사용하는 간단하고 효율적인 자료 구조이다.

예를 들어, 특정 리소스가 사용 중인지 아닌지를 추적할 때 사용된다.

리눅스 커널에서도 자주 사용되며,
예를 들어 메모리 관리, 프로세스 상태 추적 등에서 매우 유용하다.

리눅스 커널 소스의 <linux/list.h>는 비트맵 외에도

연결 리스트 관련 자료 구조와 매크로를 정의하며,
커널 전반에서 리스트 연산의 효율성과 안전성을 보장하는 데 활용된다.

02 전통적 컴퓨팅의 변화

(Traditional Computing)

과거에는 데스크톱, 서버, 메인프레임, 임베디드 시스템 등으로
전통적인 컴퓨팅 환경이 명확히 구분되었으나,

최근에는 클라우드 컴퓨팅, 엣지 컴퓨팅, 모바일 환경의 발전으로 인해
이러한 전통적 컴퓨팅 환경 간의 경계가 점점 흐려지고 있는 추세이다.

1 . 전형적인 사무실 환경

(Office Environment)

과거의 전형적인 사무실 환경에서는
직접 회사에 출근해야만 업무 처리가 가능했다.

사무실은 주로 네트워크에 연결된 데스크톱 PC들과
파일 및 프린터 공유를 위한 서버들로 구성되었다.

원격 접근(remote access)은 일반적이지 않았고,
이동성(mobility)을 확보하려면 노트북(랩톱)을 따로 준비해야 했다.

하지만 최근에는, 기업들이 다양한 원격 접근 방식과 이동성 제공에 중점을 두고 있다.

사내 시스템에 접근할 수 있는 웹 기반 포털(Portal)을 구축하고,
직원들이 집이나 외부에서도 보안 인증을 거쳐
업무 시스템에 접속할 수 있도록 하고 있다.

이러한 변화는 하이브리드 근무와
디지털 전환(digital transformation) 흐름과도 맞물려 확산되고 있다.

2 . 홈 네트워크

(Home Networks)

가정 내의 다양한 정보 기기들(컴퓨터, 스마트폰, 스마트 TV 등)이
서로 연결되어 데이터를 주고받을 수 있는 네트워크 환경을 말한다.

초기에는 하나의 컴퓨터가 느린 모뎀을 통해 인터넷에 접속했고,
주로 전화망을 이용한 PC통신이 사용되었다.

이때 모뎀(modem)은 아날로그와 디지털 신호를 상호 변환해주는 장치였다.

3 . 모바일 컴퓨팅 환경

(Mobile Computing Environment)

스마트폰, 태블릿, 노트북 등
이동 중에도 컴퓨팅 작업이 가능한 환경을 말한다.

노트북에는 없는 기능 및 서비스

① 위치 기반 서비스

스마트폰과 태블릿은 GPS 기능이 내장되어 있어,
실시간 위치 추적이 가능하다.

4개 이상의 인공위성에서 신호를 수신하여 위치를 계산하며,
일반적으로 오차 범위는 약 5m 이내다.

고정밀 GPS (L5 신호) 사용 시 약 30cm 오차,
토목/측량용 GPS는 보정 기술과 함께
2cm 수준의 정밀도를 달성할 수 있다.

② 자이로스코프 및 센서들

회전 방향과 각속도를 감지하며,
스마트폰이 기울기나 방향을 감지해
지도 회전, 게임 조작, 카메라 안정화 등에 사용된다.

이 외에도 가속도 센서, 근접 센서, 조도 센서 등 다양한 센서가 탑재되어 있다.

③ 증강 현실 지원

(Augmented Reality, AR)

스마트폰은 카메라, 센서, GPS를 결합하여
현실 위에 정보를 겹쳐 보여주는 AR 애플리케이션을 구현할 수 있다.

④ 연결성

스마트폰과 태블릿은 IEEE 802.11 (Wi-Fi) 무선 네트워크는 물론,
셀룰러 데이터 네트워크(LTE, 5G)를 통해서도 인터넷에 접속할 수 있다.

반면, 노트북은 일반적으로 Wi-Fi
또는 테더링을 통해서만 모바일 연결이 가능하다.

주요 모바일 OS

Apple iOS (아이폰, 아이패드)
Google Android (삼성, LG, 샤오미 등 대부분의 스마트폰과 태블릿)

03 분산 시스템

(Distributed System)

여러 컴퓨터(노드)가 네트워크를 통해
서로 협력하여 하나의 시스템처럼 동작하는 구조.

이 중 Client-Server 구조는
대표적인 분산 시스템 구성 방식 중 하나이며,

2가지 주요 구성 요소로 나뉘다.

1 . 클라이언트-서버 컴퓨팅

(Client-Server Computing)

오늘날 대부분의 네트워크 기반 시스템은
클라이언트의 요청을 서버가 처리하는 방식으로 구성되어 있다.

이 구조는 특별한 형태의 분산 시스템으로 간주되며,
이를 클라이언트-서버 시스템이라 부른다.

서버 시스템의 유형

① 계산 서버

(Computation Server)

클라이언트가 계산 작업이나
데이터 처리 요청을 보낼 수 있는 인터페이스를 제공한다.

예: 데이터베이스 서버, 애플리케이션 서버

클라이언트는 서버에 요청을 보내고,
서버는 계산 결과나 데이터를 반환한다.

② 파일 서버

(File Server)

클라이언트가 파일을 생성, 읽기, 수정, 삭제할 수 있도록
파일 시스템 인터페이스를 제공한다.

파일 공유, 백업, 문서 중앙 저장 등에 사용된다.

③ 프린트 서버

(Print Server)

네트워크 상의 여러 클라이언트가
하나의 프린터 자원을 공유할 수 있도록 중재한다.

클라이언트-서버 시스템의 일반 구조

하나의 서버가 존재하고,
여러 명의 클라이언트가 네트워크를 통해 연결되는 구조이다.
클라이언트는 서비스를 요청하고, 서버는 이를 처리해 응답한다.

        [ Client ]      [ Client ]      [ Client ]
             \              |              /
              \             |             /
               ------->  [ Server ]  <-------

2 . P2P Computing

(Peer-to-Peer)

대등한 관계(Peer = Peer)

모든 노드는 동일한 권한을 가진 피어(Peer)로 간주되며,
클라이언트 또는 서버로 고정되지 않는다.

동적(Dynamic)

각 피어는 상황에 따라 서비스를 요청하면 클라이언트,
서비스를 제공하면 서버의 역할을 수행한다.

3 . 서비스 탐색 방법

중앙 집중식 서버 없이도 피어 간 자원 공유가 가능하다.

하지만 누가 어떤 서비스를 제공하는지 알아야 하므로
다음과 같은 방식이 사용된다.

① 중앙 등록 방식

(Centralized Directory)

피어가 네트워크에 접속할 때,
중앙 검색 서버에 자신의 서비스 정보를 등록한다.

② 브로드캐스트 방식

(Flooding)

클라이언트 역할의 피어가
모든 노드에 요청 메시지를 브로드캐스트하여

특정 서비스를 제공하는 피어를 찾는다.
이 방식은 네트워크 부하가 커 최적화된 검색 프로토콜이 필요하다.

③ 발견 프로토콜

(Discovery Protocol)

피어 간 자원을 효율적으로
검색할 수 있도록 지원하는 통신 규약이다.

예시

서비스	설명
Napster	중앙 서버 기반 음악 파일 공유 시스템 (초기형 P2P).
Gnutella	완전한 분산형 P2P 파일 공유 시스템.
BitTorrent	파일을 여러 피어로부터 동시에 분산 다운로드하는 고속 전송 프로토콜.

P2P 시스템 구조도

    [Peer A] <---> [Peer B] <---> [Peer C]
       ↑                                ↓
    [Peer D] <----------------------> [Peer E]

모든 노드가 서로 자원을 주고받을 수 있음 (클라이언트 ↔ 서버)

요약 비교

항목	클라이언트-서버 구조	P2P 구조
역할	고정 (클라이언트 vs 서버)	동적 (모두 피어)
의존성	서버에 의존	중앙 서버 불필요
확장성	제한적	매우 뛰어남
예시	웹 서버, 프린트 서버	Gnutella, BitTorrent

04 웹 기반 컴퓨팅

(Web-Based Computing)

현대의 웹은 언제 어디서나
접근 가능한(Ubiquitous) 환경을 지향하며,

다양한 장치를 통해 접근이 가능하다.

네이버와 같은 대형 포털 사이트는
수많은 사용자 요청을 처리해야 하므로,

부하를 효율적으로 분산하기 위한 다양한 기술을 사용한다.

1 . 웹 기반 컴퓨팅의 특징

① 과거에는 PC가 주된 접근 장치였지만,
현재는 다음과 같은 장치들도 웹에 접속한다.

예: 워크스테이션, 휴대용 PDA, 스마트폰 및 태블릿, 노트북 등

② 웹은 플랫폼에 구애받지 않는다.

브라우저와 네트워크만 있으면 어느 장치에서든 접근이 가능하므로,
범용적이고 확장성 높은 컴퓨팅 환경을 제공한다.

2 . 부하 분산

(Load Balancing)

웹 기반 시스템의 확산과 함께,
사용자 요청이 특정 서버에 집중되지 않도록 분산하는 기술.

사용자의 요청을 여러 대의 웹 서버에 고르게 분배하며,
서버 간 부하 편중을 막고, 시스템의 응답 속도 및 안정성을 향상시킨다.

대형 서비스에서는 수백 ~ 수천 대의 서버가
서버 풀(server pool)로 구성되어 있다.

OS의 발전과 웹 역할의 확대

초창기 OS인 Windows 95는
웹 클라이언트 역할에 주로 사용되었다.

이후 등장한 Windows ME와 Windows XP는
웹 클라이언트와 서버 역할을 동시에 수행할 수 있도록 발전했다.

예: Windows XP에서는 IIS를 통해 웹 서버 기능 제공 가능하다.

정리 요약

항목	설명
웹 기반 컴퓨팅	웹을 중심으로 하는 컴퓨팅 환경. 다양한 장치에서 접근 가능하다.
부하 분산	여러 서버에 사용자 요청을 나눠 서버 과부하 방지한다.
운영체제 변화	Windows 95 → 클라이언트 전용 Windows XP → 클라이언트 + 서버 가능
주요 장점	범용성, 확장성, 플랫폼 독립성

05 클라우드 컴퓨팅

(Cloud Computing)

클라우드 컴퓨팅은 다음과 같은 비유로 설명된다.
"보이지 않지만, 인터넷이라는 구름 속에 연결된 컴퓨팅"

CPU 성능, 저장장치, 응용프로그램 등에
해당되는 컴퓨팅 자원을 직접 구매하거나 설치하지 않고,
인터넷(네트워크)을 통해 필요할 때마다 빌려 쓰는 방식이다.

과거에는 프로그램 하나를 사용하려 해도 직접 구매 및 설치,
고성능 하드웨어 구입, 유지보수가 필요했고 이는 비용 및 시간 낭비였다.

현재는 필요한 만큼만 사용하는 구독 모델(SaaS, PaaS 등)로 전환되었으며,
초기 비용(하드웨어, 소프트웨어 구매) 없이 이용료만 내고 사용 가능해졌다.

이는 유연성, 확장성, 비용 효율성 확보하는 계기가 되었다.

클라우드 컴퓨팅의 핵심 특징

항목	설명
계산(Processing)	CPU/메모리 같은 연산 자원을 클라우드를 통해 제공
저장(Storage)	내 컴퓨터가 아닌 인터넷 기반 저장소(예: Google Drive, Dropbox 등)
응용(Application)	웹 브라우저를 통해 다양한 앱 사용 (예: Microsoft 365, Google Docs 등)
소유 → 구독	직접 소유하지 않고, 필요한 만큼 구독 형태로 사용 가능

가상화

(Virtualization)

하나의 물리적 서버 위에
여러 개의 가상 서버(VM)를 만들고 운영하는 기술.

사용자 입장에서는 하드웨어를
직접 접하지 않고도 컴퓨터를 쓰는 것처럼 느껴진다.

이러한 가상화 기술의 논리적 확장으로
탄생한 것이 클라우드 컴퓨팅이다.

클라우드 컴퓨팅의 유형

유형	설명
공공 클라우드 (Public Cloud)	누구나 사용할 수 있는 오픈형 서비스 (예: AWS, Azure, Google Cloud)
사설 클라우드 (Private Cloud)	한 조직이나 기업 전용으로 운영되는 클라우드 환경
혼합 클라우드 (Hybrid Cloud)	공공과 사설 클라우드를 혼합 운영, 보안과 유연성 확보 목적

구분	SaaS	PaaS	IaaS
사용 대상	일반 사용자	개발자	인프라 관리자
제공 내용	완성된 응용 프로그램	개발·배포 플랫폼	서버, 저장소 등 하드웨어
관리 범위	모든 것을 제공자가 관리	인프라+운영은 제공자, 앱은 사용자	인프라만 제공, 나머진 사용자 관리
예시	Gmail, MS Office 365	Google App Engine, Heroku	AWS EC2, Azure VM

장점

항목	설명
💰 비용 절감	초기 구입 비용이 낮고, 필요한 만큼만 사용 가능 (구독 방식)
🧳 높은 휴대성	인터넷만 있으면 언제 어디서든 접속 가능
💡 높은 가용성	여러 사용자가 동시에 접속 가능, 시스템 다운 시간 최소화 (그린 IT 전략과 부합)
📱 다양한 기기 호환성	스마트폰, 태블릿, 노트북 등 다양한 기기에서 동일한 환경 사용 가능
🔐 데이터 신뢰성	데이터를 신뢰성 높은 서버에 안전하게 보관 (기업이 관리)
🔧 쉬운 사용	복잡한 하드웨어 지식 없이도 쉽게 사용 가능 (설정 및 유지보수 불필요)

단점

항목	설명
🛡️ 보안 우려	서버가 해킹당하면, 개인정보가 유출될 수 있음
🌩️ 데이터 손상 위험	재해나 장애 시 백업 없으면 데이터 복구 불가
📶 통신 의존성	인터넷 연결이 느리거나 끊기면 서비스 사용 어려움
📍 물리적 위치 불확실성	데이터가 실제로 어디에 저장되어 있는지 알기 어려움
🧾 기업 의존성	모든 것을 서비스 제공 기업에 의존해야 하므로, 스스로 백업을 받아두는 것이 중요

06 클라우드 컴퓨팅 관계도

(Cloud Computing Architecture Diagram)

클라이언트 측 요소

Internet:
사용자가 클라우드에 접속하는 경로

Customer Requests: 사용자의 서비스 요청
(예: 웹페이지 요청, 데이터 처리 요청)

Firewall:
외부와 내부 사이의 보안 필터

Customer Interface:
사용자가 접근하는 웹포털, 앱, API 등

중간 처리 계층

Load Balancer:
요청을 여러 서버에 분산시켜 부하를 고르게 만든다.

Cloud Management Commands / Services:
클라우드 전체 제어 및 모니터링하는 관리 시스템이다.

백엔드 클라우드 인프라

Virtual Machines:
실제로 계산이 이루어지는 가상 컴퓨터들 (IaaS의 핵심)

Storage: 데이터를 저장하는 클라우드 공간
Servers: 실제 물리 서버 (VM이 실행되는 기반)

관계도 예시 흐름

① 고객이 인터넷을 통해
Customer Interface에 접속한다.

② 요청이 Firewall을
지나 Load Balancer에 전달된다.

③ Load Balancer가 적절한
Virtual Machine 또는 Server에 요청 및 전달한다.

④ Cloud Management Services가
전체 인프라 제어 및 모니터링

⑤ Storage는 VM이나 앱이
데이터를 읽고 쓸 수 있도록 지원한다.

클라우드 컴퓨팅의 발전 과정

기술	자원 위치	실행 위치	과금 방식	대표 특징
Grid	분산된 여러 컴퓨터	분산	없음/협업	가상 슈퍼컴퓨터
Utility	사업자 서버	서버	사용량 기반	유틸리티처럼
SBC	중앙 서버	서버	라이선스 기반	입출력만 클라이언트
Network Computing	서버 → 클라이언트	클라이언트	일반 과금	다운로드 실행
SaaS	서버	서버	구독 or 사용량	SW를 서비스로
Cloud	서버 (가상화)	유동적	유연한 과금	모든 IT 자원 서비스화

07 실시간 내장형 시스템

(Real-time Embedded Systems)

오늘날 가장 광범위하게
사용되는 컴퓨터 시스템 유형 중 하나로,

자동차, 항공기, 스마트폰, 산업용 장비, 가전제품 등
매우 다양한 분야에 활용된다.

특정한 작업만 수행하도록 설계되었으며,
시스템은 종종 제한된 기능의 OS 혹은 OS 없이 작동한다.

점차 사용 분야가 확산되고 있으며,
기술 발전에 따라 더욱 정교해지고 있다.

1 . 내장형 시스템

(Embedded System)

대부분 특정 기능 수행을 위해 설계된
하드웨어 및 소프트웨어 시스템이다.

이는 두 가지 유형으로 존재한다.

OS를 수행하며 특수 목적 응용 프로그램을 동작하는 시스템
(예: 스마트폰의 안드로이드 OS 기반 시스템)

OS 없이, 단일 기능 수행을 위한 펌웨어/응용 전용 칩 기반 시스템
(예: 전자레인지, 세탁기 등 가전제품 제어기)

2 . 실시간 시스템

(Real-time System)

정해진 시간 내에 응답해야 하는 시스템.

단순히 결과가 올바른 것만으로는 부족하고,
결과가 '언제' 나오는지가 중요하다.

즉, 정해진 시간 내에 결과가 나와야만
올바르게 동작한다고 간주한다.

예: 차량 제어, 의료 기기, 항공 제어, 산업 로봇

하드 실시간(hard real-time):
데드라인을 반드시 지켜야 하며,
miss할 경우, 시스템의 실패를 의미한다.

소프트 실시간(soft real-time):
데드라인이 중요하지만
miss를 하더라도 일부 허용한다.

3 . 오픈 소스 OS

(Free and Open-Source OS, FOSS)

소스 코드가 공개되어 있으며,
누구나 열람, 수정, 배포 가능하다.

일반적으로는 컴파일된 바이너리가 아닌
소스 코드 형태로 제공된다.

예: Linux, FreeBSD, OpenWrt, RTEMS

오픈소스 운동의 시작

Free Software Foundation (FSF):
1985년 리처드 스톨먼(Richard Stallman)이 설립하였다.

"copyleft" 개념 도입이 되었으며,
이에 GNU General Public License(GPL)이 탄생하였다.
(소프트웨어의 자유 사용, 배포, 수정 권한을 강조)

리눅스(Linux)

1991년,
리누스 토르발스가 커널을 개발한다.

(Linus Torvalds)

이는 GNU 도구와 결합하며,
GNU/Linux 시스템으로 탄생하게 된다.

초기 약 1만 줄 코드에서 출발하여
현재는 3 ~ 4천만 줄 이상으로 성장하였다.
(정확한 수치는 리눅스 커널 버전에 따라 다르다.)

장점

① 전 세계 개발자 커뮤니티의 참여로
버그 수정 및 기능 향상이 빠르게 이루어진다.

② 많은 눈이 코드를 검토하게 되며
이에 보안 취약점이 빨리 발견되고 고쳐진다.

③ 무료이며, 원하는 대로 커스터마이징 가능하다.

[교제] 운영체제 제 10판