핵심 인사이트 (3줄 요약)
- 본질: 전역 테이블(Global Table)은 접근 제어 행렬에서 권한이 존재하는 칸만을
<도메인, 객체, 권한>3단 튜플로 저장하는 자료구조이다. 빈 칸(Null)을 저장하지 않아 공간 복잡도를 $O(실제 권한 수)$로 절감한다.- 가치: 이 희소성 압축(Sparse Compression) 덕분에, 수천만 개의 파일이 있는 시스템에서도 실제 권한 설정만 메모리에 저장하여 RAM을 절약할 수 있다.
- 한계: 권한 확인 시 리스트 전체를 순차 탐색해야 하므로 $O(N)$ 시간 복잡도가 발생하고, 중앙 테이블에 동시 접근 시 락 경합(Lock Contention) 문제가 발생한다.
Ⅰ. 개요 및 필요성
1.1 희소 행렬의 문제점
| 구분 | 전체 칸 수 | 실제 권한 칸 | 낭비 공간 |
|---|---|---|---|
| 수치 | 도메인 1만 × 파일 1만 = 1억 칸 | 약 1만 칸 | 99.99% |
1억 칸의 메모리를 할당하면 대부분의 칸이 비어있어 극심한 메모리 낭비가 발생한다.
1.2 전역 테이블의 해결책
"권한이 있는 경우만 저장한다"
[ 기존 2차원 행렬 ]
파일1 파일2 파일3
도메인A Read Null Null
도메인B Null Read Null
도메인C Null Read Write
[ 전역 테이블 (Linked List) ]
Head -> < 도메인A, 파일1, {Read} >
-> < 도메인B, 파일2, {Read} >
-> < 도메인C, 파일2, {Read} >
-> < 도메인C, 파일3, {Write} >
- 📢 섹션 요약 비유: 복잡한 창고에서 필요한 물건을 찾기 위해 먼저 구역과 표지판을 세우는 것과 같다.
Ⅱ. 아키텍처 및 핵심 원리
2.1 시간-공간 트레이드오프
| 구분 | 2차원 배열 | 전역 테이블 |
|---|---|---|
| 공간 복잡도 | $O( | D |
| 시간 복잡도 | $O(1)$ (인덱싱) | $O(N)$ (선형 탐색) |
| 적용 | 메모리 풍부한 환경 | 메모리 제약 환경 |
2.2 동시 접근 문제
여러 프로세스가 동시에 전역 테이블에 접근하면:
- 읽기/쓰기 충돌 방지을 위해 뮤텍스 잠금(Mutex Lock) 필요
- 잠금 대기 시간이 증가하면 성능 저하 발생
- 📢 섹션 요약 비유: 공장 컨베이어벨트가 어떤 순서로 부품을 받아 가공하고 내보내는지 설계도를 펼쳐 보는 것과 같다.
Ⅲ. 비교 및 연결
3.1 iptables와 전역 테이블
방화벽(iptables)의 규칙 체인도 전역 테이블과 유사한 구조다:
[Chain: INPUT]
Rule 1: DROP IP 192.168.1.100
Rule 2: ACCEPT TCP 80
Rule 3: DROP ALL
패킷이 들어올 때마다 위에서 아래로 순차적으로 규칙을 매칭한다. 규칙이 10만 개인 경우, 마지막 규칙까지 확인해야 하므로 $O(N)$ 시간이 소요된다.
3.2 eBPF와 해시 기반 최적화
최신 리눅스에서는 **eBPF(extended Berkeley Packet Filter)**를 활용하여:
-
규칙을 해시 테이블에 저장
-
평균 $O(1)$ 시간에 규칙 매칭
-
📢 섹션 요약 비유: 비슷해 보이는 공구를 나란히 놓고 언제 망치를 쓰고 언제 드라이버를 써야 하는지 구분하는 것과 같다.
Ⅳ. 실무 적용 및 기술사 판단
-
공간 절약: 희소 행렬 문제를 해결하여 메모리를 효율적으로 사용
-
시간 비용: 선형 탐색으로 인해 접근 검증 시간이 증가
-
현대적 대안: eBPF, 해시 테이블 등을 활용한 최적화
-
📢 섹션 요약 비유: 운전자가 도로 상황에 따라 기어와 브레이크를 다르게 선택하는 것처럼 조건별 판단이 중요하다.
Ⅴ. 기대효과 및 결론
전역 테이블 (Global Table) 방식 구현 (행렬 희소성 문제)은 운영체제 보호와 보안 메커니즘을 이해하는 연결 고리 역할을 한다. 이 개념을 익히면 시스템 동작을 더 예측 가능하게 설명할 수 있지만, 만능 해법은 아니므로 적용 전제와 한계를 함께 기억해야 한다. 앞으로는 접근 제어 목록 (ACL, Access Control List)처럼 더 세분화된 기술과 결합되며 자동화·최적화 방향으로 발전한다.
- 📢 섹션 요약 비유: 도구의 장점만 외우는 것이 아니라 어디까지 믿고 어디서 보완해야 하는지 기억하는 정리 노트와 같다.
📌 관련 개념 맵
| 개념 | 연결 포인트 |
|---|---|
| 보호 도메인 (Protection Domain) | 현재 개념으로 들어오기 전에 함께 이해하면 경계가 선명해지는 기반 개념이다. |
| 접근 제어 행렬 (Access Matrix) | 현재 개념이 등장하게 만든 직접적인 선행 흐름이다. |
| 접근 제어 목록 (ACL, Access Control List) | 현재 개념이 구현·세분화될 때 바로 연결되는 후속 개념이다. |
| 자격 증명 리스트 (Capability List / Ticket) | 확장 학습이나 심화 비교로 이어지는 다음 단계의 키워드다. |
📈 관련 키워드 및 발전 흐름도
[접근 제어 행렬 (Access Matrix)]
│
▼
[전역 테이블 (Global Table) 방식 구현 (행렬 희소성 문제)]
│
├──▶ [접근 제어 목록 (ACL, Access Control List)]
└──▶ [자격 증명 리스트 (Capability List / Ticket)]
이 흐름도는 선행 개념에서 현재 개념으로 넘어온 뒤, 구현 세분화와 후속 확장으로 이어지는 학습 순서를 압축해 보여준다.
👶 어린이를 위한 3줄 비유 설명
-
전역 테이블은 학교의 **"출입 가능 명단"**과 같다. 모든 학생과 모든 교실의 관계를 적는 게 아니라, "출입 가능한 조합"만을 적어둔다.
-
공간 절약은名簿(명부)에서 빈 칸을 지우고 許可(허용)된 경우만 적는 것과 같다. 공간은 절약되지만, 모든 학생의 출입 가능 교실을 알려면名簿를 모두 읽어야 한다.
-
락 경합은 여러 名簿(명부) 관리자가 동시에名簿를 수정하려고 할 때, 한 명씩만 수정해야 해서 대기 시간이 발생하는 것과 같다.