공부흔적

교착상태 개념

다중프로세싱 환경에서 두 개 이상의 프로세스가 특정 자원 할당을 무한정 대기하는 상태

교착상태 발생 조건

• 상호배제(뮤텍스) : 프로세스가 자원을 배타적으로 점유하여 다른 프로세스가 그 자원을 사용할 수 없는 상태
• 점유와 대기 : 한 프로세스가 자원을 점유하고 있으면서 또 다른 자원을 요청하여 대기하고 있는 상태
• 비선점 : 한 프로세스가 점유한 자원에 대해 다른 프로세스가 선점할 수 없고, 오직 점유한 프로세스만이 해제 가능한 상태
• 환형 대기 : 두 개 이상의 프로세스 간 자원의 점유와 대기가 하나의 원형을 구성한 상태(식사하는 철학자 문제)

교착상태 해결 방법

• 예방 : 상호배제를 제외한 나머지 교착상태 발생 조건 부정, 점유 자원 해제 후 새 자원 요청
• 회피 : 안전한 상태를 유지할 수 있는 요구만 수락
  • 은행원 알고리즘 : 교착상태에 빠질 가능성을 운영체제가 판단한 후, 교착 상태 발생 가능성이 없는 경우 자원 할당
  • Wait-Die 기법 : 사용중인 자원을 점유하기 위해 특정 프로세스가 대기해야하는 경우 대기하는 프로세스는 항상 자원을 사용중인 프로세스보다 적은 타임스탬프를 보유
  • Wound-Wait 기법 : 사용중인 자원을 점유하기 위해 특정 프로세스가 대기해야하는 경우 대기하는 프로세스는 항상 자원을 사용중인 프로세스보다 큰 타임스탬프를 보유
• 발견 : 시스템의 상태를 감시 알고리즘을 통해 교착 상태 검사
  • 자원할당 그래프 알고리즘
  • Wait for Graph
• 복구 : 교착상태가 없어질 때까지 프로세스를 순차적으로 제거, 희생자를 선택해야하고 기아 상태 발생

프로세스 스케줄링 개념

CPU를 사용하려고 하는 프로세스의 우선순위를 관리하는 작업

처리율과 CPU이용률을 증가시키고 오버헤드, 응답시간, 반환시간, 대기시간을 최소화시키기 위한 기법

프로세스 스케줄링 주요 용어

• 서비스 시간 : 프로세스가 결과를 산출하기 까지 소요되는 시간
• 응답시간 : 프로세스들이 입력되어 서비스를 요청하고 반응하기 시작할 때까지 소요되는 시간
• 대기시간 : 프로세스가 프로세서에 할당되기까지 큐에서 대기하는 시간(반환시간 - 서비스 시간)
• 반환시간 : 대기시간 + 수행시간(종료 시간 - 도착 시간)
• 종료 시간 : 요구되는 Processing time을 모두 수행하고 종료된 시간
• 시간 할당량 : 한 프로세스가 프로세서를 독점하는 것을 방지하기 위해 서비스되는 시간 할당량
• 응답률 : (대기시간 + 서비스 시간) / 서비스 시간

프로세스 스케줄링 유형

• 선점형 스케줄링 : 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식
  • 장점 : 빠른 응답, 시분할 시스템에 적합
  • 단점 : 높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래
  • 알고리즘 : SRT, 다단계 큐, 다단계 피드백 큐, 라운드 로빈
• 비선점형 스케줄링 : 한 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식
  • 장점 : 응답시간 예산이 용이, 모든 프로세스에 대한 요구를 공정하게 처리
  • 단점 : 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기
  • 알고리즘 : 우선순위, 기한부, HRN, FCFS, SJF

프로세스 스케줄링 알고리즘

• 선점형 스케줄링
  • SRT : 남은 처리 시간이 짧은 프로세스를 먼저 수행
  • 다단계 큐(MLQ) : 작업들을 여러 종류 그룹으로 분할, 여러 개의 큐를 이용하여 상위 단계 작업에 의한 하위 단계 작업이 선점
  • 다단계 피드백 큐(MLFQ) : 큐마다 서로 다른 CPU 할당량 부여
  • 라운드 로빈 : 프로세스는 같은 크기의 CPU 시간을 할당, 할당된 시간 내에 처리가 안될 시 준비 큐 리스트 가장 뒤로
• 비선점형 스케줄링
  • 우선순위 : 각 프로세스 별로 우선순위가 주어지고 우선순위에 따라 CPU 할당, 동일 순위는 FIFO
  • 기한부(Deadline) : 작업들이 명시된 시간 내에 완료되도록 계획
  • FCFS : FIFO
  • SJF : 프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 자원 점유, 기아 현상 발생 가능
  • HRN : 응답률이 높을수록 높은 우선순위, 기아 현상 최소화

프로세스 개념

CPU에 의해 처리되는 프로그램, 즉 실행 중인 프로그램

프로세스 상태

• 생성 : 사용자에 의해 프로세스가 생성된 상태
• 준비 : CPU를 할당받을 수 있는 상태
• 실행 : 프로세스가 CPU를 할당받아 동작 중인 상태
• 대기 : 프로세스 실행 중 입출력 처리 등으로 인해 CPU를 양도하고 입출력 처리 완료까지 대기 리스트에서 기다리는 상태
• 완료 : 프로세스가 CPU를 할당받아 주어진 시간 내에 완전히 수행을 종료한 상태

프로세스 상태 전이

• 디스패치 : (준비 -> 실행) 준비 리스트 중 실행될 프로세스를 선정하여 CPU를 할당
• 할당 시간 초과 : (실행 -> 준비) 실행 중인 프로세스의 지정 시간 초과 시 스케줄러에 의해 PCB 저장, CPU 반납 후 준비 상태로 전이
• 입출력 발생 : (실행 -> 대기) 실행 중인 프로세스의 지정 시간 초과 전 Block 발생 시 CPU를 스스로 반납하고 대기
• 깨움 : (대기 -> 준비) 입출력 종료 시 대기 상태의 프로세스에게 입출력 종료 사실을 알려주고 상태 전이

프로세스 구성

• 사용자 작성 코드
• 사용자 사용 데이터 : 사용자 작성 코드 프로그램에서 사용하는 데이터
• 스택 : 함수 호출 및 인자 값 전송에 사용
• 프로세스 제어 블록(PCB) : 운영체제가 프로세스 관리를 위해 필요한 자료를 담고 있는 자료 구조
  • 프로세스 생성 시 만들어지고, 메인 메모리에 유지되며, 운영체제에서 한 프로세스의 전체 정의
  • 구성요소 : PID, 프로세스 상태, 프로그램 카운트, 레지스터 저장 영역, 프로세스 스케줄링 정보, 계정 정보, 입출력 상태 정보, 메모리 관리 정보

스레드

프로세스에서 실행 제어만 분리한 실행 단위

프로세스 vs 스레드

TODO

• PCB 구성요소
• IPC란?
• 문맥 교환이란?

메모리 관리 개념

중앙 처리 장치, 메모리, 스토리지, 주변 기기 등을 적절히 관리하는 기법

메모리 관리 기본 사항

• 가상 메모리 : 실제 메모리 주소가 아닌 가상의 메모리 주소를 부여하는 방식
• 메모리 관리 장치(MMU) : CPU가 메모리에 접근하는 것을 관리하는 하드웨어, 가상 메모리 주소를 실제 메모리 주소로 변환
• 메모리 관리자 : 기억 장치의 어느 부분이 사용 중인지 또는 아닌지를 조사하여 필요할 때마다 할당 후 회수하는 작업 수행

메모리 관리 기법

• 반입 기법 : 메모리 적재 시기 결정
  • 요구 반입 기법 : 다음에 실행될 프로세스가 참조 요구가 있을 경우에 적재
  • 예상 반입 기법 : 시스템의 요구를 예측하여 미리 메모리에 적재
• 배치 기법 : 메모리 적재 위치 결정
  • 최초 적합 : 프로세스가 적제될 수 있는 가용 공간 중 첫 번째 분할에 할당
  • 최적 적합 : 가용 공간 중 가장 크기가 비슷한 공간을 선택하여 할당
  • 최악 적합 : 가용 공간 중 가증 큰 공간에 할당
• 할당 기법 : 메모리 적재 방법 결정
  • 연속 할당 기법 : 각 프로세스를 주기억장치 공간 내에서 인접하게 연속하여 저장
    • 단일 분할 할당 기법 : 오버레이, 스와핑
    • 다중 분할 할당 기법 : 고정 분할 할당 기법, 동적 분할 할당 기법
  • 분산 할당 기법 : 하나의 프로세스를 여러 개의 조각으로 나누어 배치, 주로 가상 기억 장치에서 사용
    • 페이징 기법 : 가상 기억 장치 내의 프로세스를 일정한 크기의 페이지 프레임으로 분할하여 주기억장치의 분산된 공간에 적재
    • 세그멘테이션 기법 : 가상 기억 장치 내의 프로세스를 가변적인 크기의 블록으로 나누고 메모리 할당
    • 페이징/세그멘테이션 혼용기법 : 하나의 세그먼트를 정수 배의 부분 페이지로 다시 분할
• 교체 기법 : 메모리 교체 대상 결정
  • FIFO(First In First Out) : 선입선출
  • LRU(Least Recently Used) : 사용된 시간 확인, 가장 오랫동안 사용되지 않은 페이지 선택(프로그램 지역성 원리 적용)
  • LFU(Least Frequently Used) : 사용된 횟수 확인, 참조 횟수가 가장 적은 페이지 선택
  • OPT(OPTimal Replacement) : 앞으로 가장 오랫동안 사용하지 않을 페이지 교체, Page Fault 횟수가 가장 적게 발생
  • NUR(Not Used Recently) : 최근에 사용하지 않은 페이지 선택, LRU의 시간 오버헤드 감소 가능, 페이지마다 참조 비트와 변형 비트 사용
  • SCR(Second Chance Replacement) : 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지 교체 방지 기법

* Page Fault : 주기억장치에 참조 스트링이 없을 때 발생

페이징 기법과 세그멘테이션 기법

페이지 크기에 따른 페이징 기법의 장단점

메모리 단편화

분할된 주기억장치 프로세스를 할당, 반납 과정에서 사용되지 못하고 낭비되는 기억장치가 발생하는 현상

• 내부 단편화 : 분할된 공간에 프로세스를 적재한 후 남은 공간
  • 해결방안
    • Slap Allocator : 페이지 프레임을 할당받아 공간을 작은 크기로 분할하고, 메모리 요청 시 작은 크기로 메모리를 할당/해제
    • 통합 : 인접한 단편화 영역을 찾아 하나로 통합
    • 압축 : 메모리의 모든 단편화 영역을 하나로 압축
• 외부 단편화 : 할당된 크기가 프로세스 크기보다 작아 사용하지 못하는 공간
  • 해결방안
    • 버디 메모리 할당 : 요청한 프로세스 크기에 가장 알맞은 크기를 할당하기 위해 메모리를 2n의 크기로 분할하여 메모리 할당
    • 통합
    • 압축

페이징 기법의 문제점 및 해결방안

• 페이징 기법의 문제점
  • 스레싱 : 어떤 프로세스의 Page Fault로 인해 실제 처리 시간보다 페이지 교체 시간이 더 많아지는 현상
• 페이징 기법의 문제점 해결방안
  • 워킹 세트 : 각 프로세스가 많이 참조하는 페이지 집합을 주기억장치 공간에 계속 상주
    • 장점 : Page Hit증가, CPU 활용율 최적화
    • 단점 : 복잡한 워킹 세트 추적 관리, 워킹 세트 크기 설정 모호함
  • 페이지 부재 빈도(PFF) : 페이지 부재율의 상한과 하한을 정해서 직접 예측하고 조절
    • 장점 : 부하가 적고, 직접적으로 페이지 부재율 조절 가능
    • 단점 : 프로세스를 중지시키는 과정 발생, 페이지 참조가 새로운 지역성으로 이동 가능

지역성

• 지역성 개념 : 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조
• 지역성 유형
  • 시간 지역성 : 최근에 사용된 기억 장소들이 집중적으로 액세스
  • 공간 지역성 : 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스
  • 순차 지역성 : 데이터가 순차적으로 액세스

TODO

• 오버레이란?
• 스와핑이란?

운영체제 개념

사용자가 컴퓨터의 하드웨어를 보다 쉽게 사용할 수 있도록 인터페이스를 제공해 주는 소프트웨어

운영체제 특징

• 사용자 편리성
• 인터페이스
• 스케줄링
• 자원 관리
• 제어 기능

운영체제 기능

• 제어 프로그램
  • 감시 프로그램
  • 작업 제어 프로그램 : 작업의 연속 처리를 위한 스케줄 및 시스템 자원 할당 담당
  • 데이터 관리 프로그램 : 주기억장치와 보조기억장치 사이의 데이터 전송과 보조기억장치 유지보수
• 처리 프로그램
  • 언어 번역 프로그램 : 어셈블러, 컴파일러, 인터프리터
  • 서비스 프로그램 : 링커, 정렬/합병 프로그램, 라이브러리, 유틸리티 프로그램
  • 문제 프로그램 : 특정 업무 해결을 위해 사용자가 작성한 프로그램

커널의 기능

• 쉘
  • 사용자가 입력시킨 명령어 라인을 읽어 필요한 시스템 기능을 실행시키는 명령어 해석기
  • 시스템과 사용자 간의 인터페이스 제공
• 커널
  • 운영체제의 핵심이 되는 기능들이 모여 있는 프로그램
  • 컴퓨터가 부팅될 때 주기억 장치에 적재된 후 상주하면서 실행
  • 프로그램과 하드웨어 간의 인터페이스 역할
  • 기능
    • 프로세스 관리 : 프로세스 스케줄링 및 동기화 관리, 프로세스 생성과 제거, 시작과 정지, 메시지 전달
    • 기억장치 관리 : 메모리 할당 및 회수
    • 주변장치 관리 : I/O 장치 스케줄링
    • 파일 관리 : 파일 관리 파일 CRUD

운영체제 종류

• 윈도우즈 계열
  • GUI 제공
  • 선점형 멀티태스킹 방식 제공
  • 자동감지 기능 제공 : 하드웨어 설치 시 필요한 시스템 환경을 자동으로 구성
  • OLE(Object Linking and Embedding) 사용 : 개체를 현재 작성 중인 문서에 자유롭게 연결 또는 삽입하여 편집할 수 있는 기능 제공
• 리눅스/유닉스 계열
  • 대화식 운영체제
  • 다중 작업
  • 다중 사용자
  • 이식성
  • 계층적 파일 시스템 제공
• 맥 : 매킨토시용으로 개발한 GUI 운영체제
• 안드로이드 : 휴대용 장치를 위한 운영체제와 미들웨어, UI 그리고 표준 응용 프로그램을 포함하고 있는 운영체제, 리눅스 커널 위에서 동작

TODO

• 링커란?
• OLE란?