CAOS Flashcards
관련법칙
(무마 암프 요수 샤채 길광)
- 무어 (마이크로칩, 성능2배, 가격절반)
- 암달 (프로세서 병렬화 한계)
- 요르돈 (수확체증의 법칙)
- 샤논-하아틀리이 (채널용량, 잡음, C = W log2(1+S/N)
- 길더 (광섬유 대역폭, 12개월 마다 3배 증가)
논리회로
- 조합논리회로: 출력신호가 입력신호의 의해서만 결정 되는것
and, or, not과 같은 기본 논리소자의 조합으로만 만들어 진다.
ex> 가산기, 비교기, 디코더, 인코더, 멀티플렉서, 디멀티플렉서, 코드컨버터 등 - 순차논리회로 : 출력신호가 입력신호뿐 아니라 이전상태의 논리값에 의해 결정되는 회로
플립플롭과 같은 기억소자를 포함한다.
ex> 레지스터, 카운터 등
cf) 동기식 순차논리회로와 비동기식 순차논리회로?
클록펄스의 유무에 따라결정된다. 클록펄스가 있으면 동기식, 비동기식은 클록펄스없이 입력타이밍에 의존한다.
부트로더
- 정의 : 운영체제 가동 프로그램
- 기능 : 시스템 초기화, 커널적재
- 종류 : GRUB(GNU), LILO(Linux), ARMBoot, BLOB(ARM), PMON(MIPS), u-Boot(ARM)
- 절차 : BIOS -> 1차(MBR/PBR) -> 2차(GRLDR, NTLDR) -> 커널
i-node
- 정의 : 유닉스 파일 데이터 블록 포인터
- 구조(모오타싸 다싱더트) : mode, owners, timestamps, size block count, direct blocks, single indirect(4MB), double indirect(4GB), triple indirect(4TB)
마이크로 커널
- 정의 : OS핵심기능만 커널에 구현
- 구성(프쓰메커슈) : Process, Thread, Memory, Communication, Supervisor
모놀리딕 커널
- 정의 : OS 주요기능 모두 제공
- 구성(디파네) : Device/File System/Network Manager
RTOS(RealTime OS)
- 키워드 : 다중프로그램, 실시간OS, 선점형, 우선순위, Hard/Soft/Firm RTOS, GPOS
- 정의 : 정해진 시간 내에 완벽한 처리, 다중 프로그래밍 기반 실시간 운영체제
- 조건 : 신뢰성, 예측가능성, 성능, 최적성, 확장성
- 유형 : Hard RTOS(경성), Soft RTOS(연성), Firm RTOS(준경성)
- 기술(멀프뮤프 스디콘세) : Multi Tasking, Preemptive Kernel(선점형), Mutual Exclusion, Priority Inversion/Inheritance, Scheduler, Dispatcher, Context Switch, Semaphore
Embedded System
- 정의 : 특정목적 수행 SW/System
- 특징 : HW, SW 동시설계, 소형, 실시간, 저전력
- 분류(실특소저) : 실시간 처리(경성, 연성), 특수목적(가정, 정보, 공장, 사무), 소형, 저전력
- 테스트 자동화 이슈 : Event Driven, Time Critical, Platform Diversity, Platform Stability, Development Envronment
- 테스트 자동화 도구 : 기능, 호스트, 타겟, 데이터, 품질, 인증
Embedded OS
- 기능 : 실시간 처리, 프로그램 스케줄링, 멀티 태스킹, 선점형 커널지원, 부팅지원, XIP(eXcute In Place), GUI, 통신
모바일 OS
- 정의 : 기본 OS 기능을 제공하고 서비스와 라이브러리를 포함하는 플랫폼 OS
- 기술 : 기본OS(커널, 미들웨어), 플랫폼OS(App Framework, UI Framework, Apps)
- 종류 : iOS, Android, Web OS, Tizen
Tiny OS
- 정의 : UC버클리 스마트 더스트 프로젝트, 상태머신 구조의 컴포넌트 및 이벤트 기반 센서 네트워크용 운영체제
- 특징(상컴저이 네피확) : 상태머신 구조, 컴포넌트 기반, 저전력, 이벤트 호출, nesC언어, FIFO, 확장성
- 구성(MASAC 힐할팔): Main(Kernel Scheduler), Application(User Components), Actuating, Sensing, Communication, HAA(HIL(Indenpendent), HAL(Abstraction), HPL(Presentation))
- 스케줄러 동작(루스이태) : Loop, Sleep, Event, Task
SQLLite
- 정의 : 어플리케이션 프로세스 영역 내부에 공존하는 임베디드 데이터베이스
- 구성(코코액백)(인커버 토파코 비패오 유테) : Core(Interface, SQL Command Processor, Virtual Machine), Compiler(Tokenizer, Paser, Code Generator), Backend(B-Tree, Pager, OS Interface), Accessories (Utilities, Test Code)
Virtual Memory
- 정의 : 보조기억장치 부분을 주기억장치 처럼 사용
- 관리정책 : 할당(고정, 가변), 호출(요구, 예상), 배치(First, Best, Worst),교환(FIFO, LRU, LFU, NUR)
- 구성 : Paging(고정분할, 내부단편화), Segmentation(가변분할, 외부단편화), Paged Segmentation(page(메모리), Segment(파일))
- 페이징 기법 : Direct(Page Table), Associative(Associative Buffer), Direct/Associative
- 페이지 교체 알고리즘 : 무작위, FIFO, Optimal, LFU(횟수), LRU(시간), NUR, MFU
- 문제점 : Demand Paging, Page Fault Trap, Thrashing
- 해결방안 : Locality Model, Working Set, Page Fault Frequency
FIFO Anomaly
- 개념 : 프레임 개수 추가, page fault 증가
- 현상 : locality 미고려 문제점 -> LRU고안
- 해결 : SCR (FIFO 단점 보완)
- SCR 개념 : 각 페이지마다 참조 비트, 0 인 경우 교체, 1인경우 0으로 지정 후 FIFO 리스트의 맨 마지막으로 피드백
MMU (Memory Management Unit)
- 개념 : 가상 메모리에서 주소 매핑, 논리적 주소를 물리적 주소로 변환하는 하드웨어
- 과정 : CPU에서 MMU에 가상 주소 전달 -> MMU는 TBB부터 Page Table 검색 -> Page Table 에서 물리주소 검출 -> 물리주소의 데이터 CPU에 전달
TLB(Translation Look-aside Buffer)
- 필요성 : 페이지 테이블 반입, 엑세스 데이터 반입 두번 엑세스 시간 단축
- 원리 : 시간 지역성, 연관 사상
- 동작 : TLB 우선검색, TLB Hit, TLB Miss, 메모리 접근
캐시 메모리
- 정의 : CPU와 주기억장치 사이에 위치한 소형 고속 메모리
- 특성 : 공간지역성, 시간지역성, 순차지역성
- 매핑기법 : Direct(블록분할), Full Associative (태그필드), Set Associative(라인분할)
- 쓰기정책 : Write Through(동시), Write Back(제거될 때)
- 캐시 일관성 문제 해결 : 공유 캐시 사용, 공유변수를 캐시에 저장하지 않기, 버스감시 매커니즘 사용, 디렉토리 기반 유지 기법 사용
캐시 플러시
- 개념 : 주메모리에서 데이터를 다시 읽어 들일 필요가 있을 경우 캐시를 비우는 동작
- 구성 : Flush (Cache reset, I-Cache/D-Cache 중 하나만 실행), Clean (Cache Write Back, D-Cache 에서만 동작)
Locality
- 정의 : 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성
- 종류 : 시간적(순환, 서브프로그램, LRU), 공간적(Array, Sequential Processing, Pre-fetch), 순차적
- 관리방법 : 기억장치 계층구조, 캐시 엑세스 시간, 워킹셋
- 사례 : Cache Memory, Virtual Memory, CDN
Thrashing
- 정의 : Multi Processing 기능을 갖춘 가상 시스템에서 페이지부재가 너무 많이 발생하여 프로세스 실행보다 페이지교체에 더 많은 시간을 소모하는 현상
- 원인 : 부적절한 페이지 교체 정책, 과단한 멀티 프로세싱 정책
- 발견방법 : Page Fault 조사, Swapping 조사
- 예방방법 : Working-Set(전이), Page-Fault Frequency(상한할당, 하한회수)
문맥교환(Context Switching)
- 개념 : 멀티 프로세스 환경에서 실행 중인 프로세스의 상태를 보관하고 새로운 프로세스의 상태를 CPU에 적재하는 과정
- 관련용어 : Dispatching, Time Quantum, Preemption
- 절차 : 인터럽트 -> 모드전환(USER->OS) -> 기존 상태 PCB 저장 -> 신규 상태 PCB 로드 -> 다음 프로세스 실행 -> 모드전환(OS->USER)
- 발생시점 : 비자발적(타임 슬라이스 소진시, 인터럽트 발생시), 자발적(sleep, exit, wait)
- 오버헤드 발생 시점 : 인터럽트, 프로세스 스케줄링, 디스패치
- 오버헤드 해결 방안 : 다중 프로그래밍 정도 낮춤, 프로세스간 문맥교환 수행, 쓰레드 이용
CPU 스캐줄링
- 정의 : 언제, 어느 Process에 CPU를 할당할 것인지 결정하는 작업
- 특징 : 처리능력 최대화, 경과시간 최소화, 대기시간 최소화, 응답시간 최소화, CPU 이용율 극대화
- 종류 : Scheduling Queue, Job Scheduler(장기), Process Scheduler(중기), Read Scheduler(단기)
- 기법 : 선점(RR, SRTF, MLQ, MLFQ), 비선점(FCFS, SJF, Priority Queue)
Dispatcher
- 정의 : 프로세스 전환수행을 하는 운영체제내부모듈
- 기능 : 프로세스 공간의 전환 처리(switch_mm), 레지스터의 전환 처리(switch_to), 부동 소수점 연산 레지스터의 지연 전환 가능, 범용 레지스터의 백업, CPU 할당, 스케줄러에 의한 호출(선점)
Deadlock
- 정의 : 다중 프로그램 환경에서 두 개 이상의 프로세스가 아무리 기다려도 자원을 사용할 수 없는 무한 대기 상태
- Deadlock 관리 필요성 : 자원 낭비 방지, 성능 저하 방지, 사용자 불만 해소
- 발생원인 : 상호 배제, 점유와 대기, 비선점, 환영 대기
- 교착상태 예방 : 부정
- 교착상태 회피 : 제거
- 교착상태 발견 : 특정경우 -> 알고리즘 -> 발견 -> 회복
- 교착상태 회복 : 수동처리(process kill), 제거(abort)
- 교착상태 해결 위한 시스템 설계 : PCB/Buffer/Semaphore 자원 순서화, 주 기억 장치 선점(Paging/Segmentation/Swapping), 자원 필요량 산정, 교체 가능 공간 사전 할당
Banker 알고리즘
- 정의 : 감시와 제시, 교착 상태 회피 알고리즘
- 자료구조 : Available(사용가능), Max(최대 자원 요구), Allocation(할당 받음), Need(남은 자원)
- 동작원리
1) 현재 사용 가능한 리소스의 양을 구한다 (Available)
2) 추가 요구량을 구한다 (Request = Max - Available)
3) 추가 요구 자원이 현재 여유 자원보다 적은 프로세스 (i)를 찾는다
4) 수행 가능한 프로세스가 점유한 자원을 여쥬 자원으로 바꿈 (끝내고 반환한 경우로 가정) 한 후에 3번 부터 반복
상호배제 해결을 위한 소프트웨어와 하드웨어적 방안
- 소프트웨어적 방안 : 데커(공유변수, 차례설정), 피터슨(공유변수, 의사표시, 차례양보), 램포트(번호표 부여)
- 하드웨어적 방안 : 인터럽트 금지, Test & Set, Swap
세마포어
- 정의 : P와 V라는 2개의 연산에 의해 동기화를 유지시키며 상호 배제의 원리를 보장하는 기법
- 유형 : 이진, 계수
- 원리 : s가 1이면 접근가능, s가 0이면 접근불가
- 연상 : 초기화(s에 초기값 부여), P연산(Wait, s = s - 1), V연산(Signal, s = s + 1)
- 적용방법 : Busy waiting(while), Sleeping Queue(if)
세마포어(비교)
- 주체 : OS, 개발자 주체의 동시성 지원
- 상호작용 : 모니터에 이론적 기반 제공
- 특징 : s의 타입에 따라 Binary/Counting으로 구분
- 구현사례
Semaphores S;
P (s); // 검사 s–
임계구역()
V (s); //증가 s++ - 언어 : P, V 연산
- 공통점 : 동시성 지원
모니터(비교)
- 주체 : 프로그래밍 언어 수준의 동시성 지원
- 상호작용 : 세마포어의 단점인 타이밍 오류 해결 및 개발편의성 보완
- 특징 : 한 시점에 하나의 프로세스만 모니터 내부에서 수행
- 구현사례
Monitor monitor-name
{
//지역변수 선언
Public entry p1(…) { }
Public entry p2(…) { }
} - 언어 : JAVA의 synchronized Object, .NET의 모니터
Multi Threading
⦿ 정의 : CPU가 한번에 처리할 수 있는 작업 실행 단위가 1개가 아닌 여러개가 될 수 있는 기능 ⦿ 특징 : CPU 이용률 최대화, 대기/응답시간 최소화, 수행의 흐름을 분리, 예측불가, 동기화 ⦿ 종류 - Interleaved(Fine-grain) : Clock cycle - Blocked(Coarse-grain) : cache miss - Simultaneous (SMT) : Super scala - Chip : two-issue ⦿ 모델 - Many to one : 빠름, 간단, 병렬안됨 - One to one : 오버헤드, 병렬됨 - Many to Many : 진정한 동시성 ⦿ 장점 : Idel 시간 감소, 빠른 처리 결과, Cache 효율성 강화 ⦿ 단점 : 상호 방해, 오버헤드, 하드웨어 지원 필요
프로세스
- 정의 : 메모리에 로드 되어 CPU에 의해 실행되고 있는 실행 프로그램
- 특징 : PCB, Dispatch, Context Switching, 순차적 수행
- 상태
1) Ready (dispatch, suspend)
2) Running (timer runout, suspend, I/O wait or event wait)
3) Blocked (I/O completion or event completion, suspend)
4) Suspended Ready (resume)
5) Suspended blocked (I/O Completion or event completion, resume)
PCB (Process Control Block)
⦿ 정의 : 프로세스에 대한 중요 정보를 저장해 놓은 저장소 ⦿ PCB의 자료구조(상고부자 우메할 카레) - 프로세스의 현 상태 - 프로세스의 고유한 식별자 - 프로세스의 부모 프로세스에 대한 포인터 - 프로세스의 자식 프로세스에 대한 포인터 - 프로세스의 우선순위 - 프로세스가 위치한 메모리에 대한 포인터 - 할당된 자원에 대한 포인터 - 프로그램 카운터 - 중앙처리장치 레지스터
메모리 인터리빙
⦿ 키워드 : 상위/하위/혼합, C-Access, S-Access ⦿ 정의 : 메모리 접근시간을 최소화하기 위해 메모리를 복수개의 모듈로 나누고 각 모듈에 연속적인 주소를 부여하여 동시 접근이 가능하게 하는 기법 ⦿ 활용방식 - 상위 인터리빙 : 순차적 - 하위 인터리빙 : 연속적 - 혼합 인터리빙 : 뱅크(상위), 모듈(하위) ⦿ 엑세스 방식 - C-엑세스 : 순차적 도착 - S-엑세스 : 동시읽기, 순차전송