코드 없는 알고리즘과 데이터 구조 (암스트롱 수베로 지음)
목차
Part 1 - 데이터 구조
Part 2 - 알고리즘
Part 3 - 알고리즘과 데이터 구조를 이해하는데 필요한 지식들
10. 무작위성
11. 스케줄링 알고리즘
📍운영체제(OS)
✅역할
- 일반적인 컴퓨터에서 CPU를 보조하는 자원은 유한하다
- 따라서 시스템에서 실행중인 여러 프로그램은 메모리와 데이터 처리 시간을 공유해야 한다
- 운영체제는 여러 프로그램이 동시에 실행될 수 있도록 추상화 메커니즘을 제공한다
✅운영체제는 서버, 랩톱, 휴대폰뿐만 아니라, 복사기, 자동차, 주변기기 속 임베디드 시스템의 마이크로 컨트롤러에서도 실행된다
📍범용 운영체제(general-purpose operating system, GPOS)
✅일반적인 컴퓨팅 작업과 응용 프로그램 실행을 위해 설계된 운영체제
- 메모리가 충분히 많은 표준 컴퓨터 하드웨어에서 실행됨
- 유저는 언제든지 하나 이상의 응용 프로그램을 실행할 수 있다
- 대부분 데스크톱과 랩톱에서 실행하도록 설계됨
예) Windows, MacOS, 리눅스(우분투 등)
- 시스템 실행에 필요한 프로세스 처리 및 메모리 요구사항을 가진 워크스테이션, 메인프레임, 임베디드 장치도 포함한다
- 모바일 디바이스의 컴퓨팅 성능이 향상됨에 따라, 안드로이드나 iOS 같은 모바일 운영체제도 범용 운영체제로 분류할 수 있다
📍실시간 운영체제
✅범용 운영체제의 문제
- 프로그램 충돌, 멈춤, 재시작, 실행속도 저하
- 일시적인 문제이며 대부분은 재시작하면 해결된다
예) 웹브라우저의 일시적인 랙
✅그런데, 프로그램에 절대로 문제가 생기면 안되는 경우도 존재한다
예) 심장 박동 조율기, 비행기의 자동조종 시스템 등
- 시간 경과, 응답 지연 등이 있으면 안된다!
- 이러한 시스템을 실시간 시스템(real-time system)이라고 한다
✅경성(hard) 실시간 시스템
- 엄격한 응답시간 충족이 요구됨
- 응답시간 지연이 발생하면 심각한 피해가 발생
예) 자동차의 ABS, 심폐 소생기
✅연성(soft) 실시간 시스템
- 엄격한 응답시간 충족이 요구되지만 어느 정도 융통성이 있음
예) 전화기, 실시간 화상회의 SW
✅실시간 운영체제(real-time operation system, RTOS)
- 실시간 시스템을 관리하고, 필요한 처리 시간 요구 사항을 충족하는지 확인
✅범용 운영체제와의 비교
- 실시간성 충족을 위해 더 빠른 성능과 적은 메모리를 필요로 함
- 독립적으로 장기간 동작이 가능하도록 안정적이어야 함
예) 행성 탐사선의 경우 수리나 재설정이 매우 힘듬
✅실시간 커널
- 마이크로 프로세서가 실시간으로 이벤트를 처리하도록 관리하는 운영체제의 핵심 소프트웨어
✅모놀리식 커널(monolithic kernel, 단일형 커널)
- 실시간 커널의 하나로, 운영체제의 모든 기능이 커널 자체에 적재된 것
📍인터럽트와 인터럽트 서비스 루틴
✅인터럽트
- CPU가 즉시 처리해야하는 작업을 감지하고 알림
- CPU는 기존 작업을 그대로 두고, 인터럽트를 처리한 후 기존 작업을 재개
- 인터럽트 서비스 루틴(ISR) : 프로세서가 인터럽트에 들어갈 때 실행해야 하는 명령 블록
- 인터럽트 간 먼저 처리해야할 우선순위가 존재
✅인터럽트의 종류
- 하드웨어 기반 인터럽트 : 외부 하드웨어 장치(마우스, 키보드)에 의해 발생
- 소프트웨어 기반 인터럽트 : 프로세서를 인터럽트 서비스 루틴에 들어가게 하는 명령 또는 프로그램 예외에 의해 발생
📍유한 상태 기계(finite-state machine, FSM)
유한 상태 오토마타(finite-state automata)라고도 부름
- 상태가 전이하는(변하는) 전산 시스템을 모델링하는데 사용된다
- 유한 상태 기계 시스템에는 유한한 갯수의 상태가 존재
- 상태 변화는 시스템의 현재 상태와 상태에 대한 입력에 따라 달라
✅동작의 구분
- 상태 진입의 원인이 되는 동작
- 상태에 있는 동안 수행되는 동작
- 상태에서 벗어날 때 수행되는 동작
✅유한 상태 기계 예시 : 동전 인식 모듈
- 동전 인식 모듈이 잠금 상태일 때는 동전을 넣어야만 상태를 변경할 수 있다
- 이미 동전을 넣어 잠금 해제 상태일 때는, 버튼 동작 혹은 레버를 돌려야만 다시 잠금 상태로 변경할 수 있다
✅결정/비결정
- 결정적 유한 오토마타 : 임의의 상태는 주어진 유효 입력에 따라 유일한 1개의 상태로 전이
- 비결정적 유한 오토마타 : 임의의 상태는 입력이 주어졌을 때 0~N개의 상태로 전이된다
📍커널, 프로세스, 스레드, 태스크
✅커널(kernel)
- 운영체제의 핵심
- 메인 메모리에 상주하며 시스템 자원(특히 CPU 점유시간 및 메모리)에 대한 모든 접근을 중개
- 커널 자체가 장치의 운영체제가 되기도 함 (임베디드)
- 커널에 파일 관리, UI, 프로토콜 스택, 보안 메커니즘을 등을 추가하면 운영체제가 된다
✅프로세스
- 프로세스 : 프로그램이 메모리에 적재되어 실행될 때
✅프로세스 상태의 라이프 사이클
1. 생성
2. 준비 : CPU를 점유할 시간이 주어지기까지 대기
3. 실행 : 프로세스에 CPU가 할당되어 명령을 실행할 수 있는 상태
4. 대기 : 실행을 위한 추가적인 자원이 필요한 경우 대기 상태가 되기도 함
5. 종료 : 프로세스의 실행이 종료되고 메인 메모리에서 제거됨
✅프로세스 분류
- 입출력 집중 프로세스
- CPU 집중 프로세스 : CPU 사용에 집중
✅스레드(thread)
- 프로세스의 실행 흐름을 나타내는 단위
- 병렬 스레드가 지원되며 일부 프로세스는 멀티 스레드를 지원
- 경량 프로세스(lightweight process)라고 부르기도 함
✅태스크(task)
- 스레드 또는 프로세스의 일부 (운영체제에 따라 의미가 다를 수 있음)
- 일반적으로 스케줄러가 스케줄링할 수 있는 코드의 일부 또는 프로그램의 일부를 가리킴
📍메모리 관리 장치
✅메모리 관리 장치(memory management unit, MMU)
기능
- 가상 주소와 물리 주소 간의 매핑 제공
- 메모리의 비트를 사용하여 무엇을 할 수 있는지 결정(읽기, 쓰기, 실행 등)
(페이지 테이블과 상호작용하며)
✅모드 구분
커널 모드 : 시스템 하드웨어, 커널 주소 공간 및 사용자 주소 공간에 접근 가능
사용자 모드 : 시스템 하드웨어에 직접 접근할 수 없고 사용자 주소 공간에만 접근 가능
📍작업 제어 블록(task control block, TCB)
- 커널은 프로세스 사이의 통신을 처리하고 프로세스를 동기화하며 프로세스간 문맥 전환(context switching) 처리
- 또한 커널은 태스크에 관한 정보가 담긴 작업 제어 블록을 생성
- 작업 제어 블록은 프로세스 id, 프로세스 우선순위 정보 등을 포함