[정보처리기사] 4과목 3장. 응용 SW 기초 기술 활용

운영체제란?

컴퓨터 시스템의 자원들을 효율적으로 관리하며, 사용자가 컴퓨터를 편리하게 사용할 수 있도록 환경을 제공하는 여러 프로그램의 모임이다.

프로그램 → 하드디스크(보조기억장치) → 주기억장치(적재/실행) → 프로세스 → 프로세서(CPU, 중앙처리장치)

운영체제가 하는 일

응용 프로그램을 설치하면 하드디스크(보조 기억장치)에 들어간다.
실행을 시키면 하드디스크에서 가져와서 주기억장치(RAM)로 올라간다.  (반입 전략)
반입된 데이터들을 한정적인 공간인 주기억장치의 어딘가에 배치해야 한다. (배치 전략)
한정적이라 금방 차기 때문에 교체해줘야 한다 (교체 전략)
프로그램이 실행되면 프로세스가 되고, 이 프로세스들을 프로세서(CPU)가 처리한다.

CPU (Central Processing Unit) 란?

프로세서(processor) 라고도 불린다.
중앙 처리 장치로 컴퓨터 시스템에서 연산, 제어, 데이터 처리 등을 수행하는 핵심적인 부품이다.

► 주기억장치

RAM (Random Access Memory)

RAM은 컴퓨터의 주 메모리로, 프로그램과 데이터를 일시적으로 저장하는 곳이다. 이 메모리는 전원이 꺼지면 그 안의 정보가 사라지는 휘발성 메모리다. RAM 은 프로그램 실행 중에 필요한 데이터를 빠르게 읽고 쓸 수 있도록 CPU에 제공한다. 즉, 운영체제와 실행 중인 프로그램이 실제로 동작하는 동안 사용된다.

ROM(Read Only Memory)

읽기 전용으로 데이터를 저장하는 메모리로, 전원이 꺼져도 정보를 보존하는 비휘발성 메모리이다.
시스템 초기화와 기기 제어 등에 사용된다.

► 운영체제의 구성

제어 프로그램

• 감시 프로그램 (Supervisor) : 자원 할당과 시스템 전체의 작동 상태를 감시, 감독 (핵심)
• 작업 관리 프로그램 (Job Management) : 작업의 순서와 방법 관리
• 데이터 관리 프로그램 (Data Management) : 데이터와 파일의 표준적인 처리 및 전송을 관리

운영체제 운용 기법 (선점 / 비선점)

• 일괄 처리 시스템 (Batch Processing) : 일정량 또는 일정 기간 동안 데이터를 모아서 한 번에 처리
• 실시간 처리 시스템 : 데이터를 즉시 처리하여 결과 산출
• 다중 프로그래밍 시스템 : 하나의 CPU 와 하나의 주기억장치로 여러 개의 프로그램 동시 처리
• 시분할 시스템 (Time Sharing) 여러 유저가 동시에 컴퓨터를 사용할 수 있도록 CPU 시간을 나누어준다. 독립적인 느낌을 준다. 하나의 CPU 가 빠르게 여러 작업들을 전환하며 각 사용자에게 작은 시간 단위를 할당해 주는 시스템 (라운드 로빈 방식 - 선점형)
  
• 다중 처리 시스템 : 여러 개의 CPU 와 하나의 주기억장치를 이용하여 여러 개의 프로그램 동시 처리
• 다중 모드 시스템 : 일괄 처리, 다중 처리, 시분할, 실시간 처리 시스템을 한 시스템에서 모두 제공
• 분산 처리 시스템 (Distributed Processing) : 여러 컴퓨터를 통신 회선으로 연결하여 하나의 작업을 처리하는 방식

운영체제 발달 과정

일괄 ⇒ 실시간, 다중 프로그래밍, 시분할, 다중 처리 ⇒ 다중 모드 ⇒ 분산

► 기억장치 관리 전략

반입 (Fetch) 전략 - when

언제 주기억장치에 적재할 지 결정

• 요구 반입 (Demand Fetch) : 특정 프로그램이나 데이터 등의 참조를 요청할 때 적재하는 방법
• 예상 반입 (Anticipatory Fetch) : 참조될 프로그램이나 데이터를 미리 예상하여 적재하는 방법

배치 (Placement) 전략 - where

주기억장치의 어디에 위치시킬지 결정

• 메모리 할당 알고리즘
  • 최초 적합(First Fit) : 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 첫 번째 영역에 배치 (들어갈 수 있는 곳으로 먼저 들어간다.)
  • 최적 적합(Best Fit) : 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화를 가장 작게 남기는 영역에 배치 (크기가 가장 적합한 곳에 배치)
  • 최악 적합(Worst Fit) : 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화를 가장 많이 남기는 영역에 배치 (가장 큰 곳에 배치)

교체 (Replacement) 전략 - what

주기억장치의 모든 영역이 사용중인 상태에서 교체할 대상을 결정

• 페이지 교체 알고리즘
  • FIFO : 선입 선출 (Belady’s Anomaly 발생 가능)
  • OPT : 앞으로 가장 오랫동안 사용하지 않을 페이지를 계산해서 교체한다. (Page Fault 가장 적음)
  • LRU : 최근에 사용하지 않은 것들을 교체한다. (Page Fault 적음)
  • LFU : 사용 빈도가 적은 것들을 교체한다. 사용된 페이지는 교체하지 않는다.
  • NUR (Not Used Recently) : LRU 와 비슷 / 참조비트, 변형비트를 이용해서 최근 사용 여부를 계산하여 교체한다.
  • SCR (Second Chance Replacement)  : FIFO 를 개선한 알고리즘이다. 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지한다.

► 주기억장치 할당 기법 - how

주기억장치에 어떻게 할당할 것인지

연속 할당 기법

프로그램을 주기억장치에 연속으로 할당하는 기법

• 단일 분할 할당 기법
  • 오버레이 (Overlay) 기법 : 주기억장치보다 큰 하나의 프로그램을 여러 조각으로 분할한 후(개발자가 직접 분할) 필요한 순서로 주기억장치에 적재하여 실행한다. 공간이 부족하면 불필요한 조각 위에 중첩(overlay)하여 적재한다.
  • 스와핑 (Swapping) 기법 : 하나의 프로그램 전체를 적재하여 사용하다 필요에 따라 다른 프로그램과 교체한다. 교체는 여러 번 수행할 수 있다. 가상기억장치의 페이징 기법으로 발전했다.
• 다중 분할 할당 기법 (지금은 사용하지 않음)

분산 할당 기법 (아래 가상기억장치 부분에서 설명)

프로그램을 특정 단위의 조각으로 나누어 주기억장치 내에 분산하여 할당하는 기법

• 페이징 기법
• 세그먼테이션 기법

► 가상기억장치

주기억장치의 한정적인 공간 때문에 하드디스크의 일부(보조기억장치의 일부)를 주기억장치처럼 사용하는 것

• 프로그램을 여러 개의 블록 단위로 나누어서 가상기억장치에 보관하고, 프로그램 실행 시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리한다.
• 주기억장치로 할당시 주소 변환이 필요하다.
• 연속 할당 기법의 단편화를 해결한다.

가상기억장치 구현 방법

(블록의 종류에 따라 나눈다)

1. 페이징 (Paging) 기법
   페이지를 페이지 프레임에 적재시켜 실행하는 기법

   • 페이지 (Page) : 프로그램을 일정한 크기로 나눈 단위
   • 페이지 프레임(Page Frame) : 주기억장치의 영역을 일정한 크기로 나눈 단위
   • 일정한 크기로 분할한다.
   • 내부 단편화가 발생할 수 있다.
   • 페이지 맵 테이블이 필요하다. (주소 변환)

   ★ 페이지 교체 알고리즘

2. 세그먼테이션 (Segmentation) 기법
   프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행하는 기법

   • 세그먼테이션 (Segmentation) : 프로그램을 배열, 함수와 같은 논리적인 크기로 나눈 단위
   • 가변 길이로 조절한다. 다양한 크기의 논리적인 단위로 나눈다.
   • 외부 단편화가 발생할 수 있다.
   • 세그먼트 맵 테이블이 필요하다. (주소 변환)
     실기억주소 구하는 문제가 나올 수 있음!
     • 가상주소 = [ 세그먼트 번호(s) | 변위값(d) ]
     • 세그먼트 맵 테이블 = [ 세그먼트 번호(s) | 세그먼트 크기(L) | 기준번지(b) ]
     • 변위값이 세그먼트 크기보다 작거나 같을 때 (d ≤ L) ⇒ 실기억주소 = 기준번지 + 변위값
     • 변위값이 세그먼트 크기보다 클 때 (d > L) ⇒ 실행 권한을 운영체제에게 넘기고 트랩 발생

► 단편화 (Fragmentation)

주기억장치에 프로그램을 할당하고 반납하는 과정에서 발생하는 사용되지 않는 작은 조각 공간
주기억장치 상에서 빈번하게 기억장소가 할당되고 반납됨에 따라 기억장소들이 조각들로 나누어지는 현상

내부 단편화

할당된 메모리 공간이 프로세스가 요청한 메모리보다 더 큰 경우

• 10kb 메모리 공간에 5kb 프로그램을 집어 넣으면 내부에 공간이 남는다.

외부 단편화

프로세스가 필요한 크기의 메모리를 할당받을 수 없는 경우

• 10kb 메모리 공간에. 15kb 프로그램을 집어 넣으려고 하면 할당이 안되기 때문에 10kb 메모리 공간이 사용하지 않은 상태가 된다.

단편화를 없애기 위한 기법

1. 통합 기법 (Coalescing)
   인접해 있는 공간을 통합해서 하나의 큰 공간을 만들어준다.
2. 압축 기법 (Compaction)
   멀리 있는 공간을 가져와서 압축해서 큰 공간을 만들어준다.
   Garbage Collection 작업이라고도 한다.
3. 재배치 기법 (Relocation)
   압축시 변경되는 프로그램 주소값을 새롭게 지정해준다.

► 스래싱 (Thrashing)

키워드 : 페이지 교체/부재, CPU 이용률, 워킹셋, Locality

다중 프로그래밍에 의해 페이지 교체가 많이 일어나게 되면 스레싱 현상이 발생한다.

스레싱 현상이란?

• 프로세스 수행(처리)에 보내는 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상
• 다중 프로그래밍 시스템이나 가상기억장치를 이용할 때 페이지 부재가 자주 발생해서 나타나는 현상이다.
• 다중 프로그래밍의 정도가 적정 수준보다 높아지면 스래싱이 나타나고 프로세스를 수행하는 CPU의 이용률이 급격히 감소한다.

해결 방안

• 워킹 셋(Working Set)을 유지한다.
  ★ 워킹 셋이란? 프로세스가 일정 시간동안 자주 참조하는 페이지들의 집합 (Locality 의 특징 이용)
  ★ Locality 란? 프로세스가 집중적으로 사용하는 페이지를 알아내는 방법 중 하나
  • 시간 구역성 (Temporal Locality) : 하나의 페이지를 일정 시간동안 집중적으로 액세스하는 현상 ⇒ Loop, 스택, ++, 집계 변수 등
  • 공간 구역성 (Spatial Locality) : 일정 위치의 페이지를 집중적으로 액세스하는 현상 (근처 페이지 참조) ⇒ 배열, 순차코드 등
• 페이지 부재 빈도를 조절한다.

► 프로세스

프로세스는 실행중인 프로그램으로, 하나의 프로세스는 하나 이상의 스레드로 구성된다.
예를 들어, 카톡이라면, 스레드는 메세지를 보내고, 받고, 다른 친구들이랑도 하는 등등

스레드 (Thread)

스레드는 프로세스(Process)내에서의 하나의 작업의 흐름이다.
스레드들은 코드, 데이터, 힙 영역을 공유하면서 각각의 스레드에 스택이라는 지역 변수를 가지고 있다.

스레드 영역 (Context)

1. 코드 영역
   실행할 프로그램 코드가 저장되는 공간
2. 데이터 영역
   초기화된 전역 변수와 정적(static) 변수가 저장되는 공간
3. 힙 영역
   동적으로 할당된 메모리가 저장되는 공간
   개발자가 직접 직접 메모리를 할당하고 해제한다.
4. 스택 영역
   함수 호출과 관련된 지역 변수, 매개 변수, 함수의 반환 주소 등이 저장되는 공간
   LIFO 구조

► 프로세스 동작 방식 (상태 전이)

준비 → 실행 (Dispatch)

준비 상태(준비 상태 큐)에 많은 프로세스들이 프로세서(CPU)를 할당받기 위해 기다리고 있다.
CPU 스케줄러에 의해 Dispatch 가 수행된다.

실행 → 준비 (Time Run Out)

실행상태에서 수행이 완료되기 전에 다시 준비 상태로 보내는 것은 할당 시간 종료 라고 한다.
Time Run Out 이란 각 프로세스에 할당된 시간이 모두 소진되어 해당 프로세스가 CPU 제어권을 잃는 상황이다.

실행 → 대기

실행상태에서 프로세스에 입출력 (I/O) 또는 interrupt (이벤트) 처리가 필요하면 대기 상태로 간다.

대기 → 준비 (Wake Up)

입출력 작업이 완료되면 대기 상태에 있던 프로세스는 준비 상태로 전이 된다.

정리 : 이런 두 프로세스 간의 전환을 문맥 교환 이라고 하고, 문맥 교환 시 프로세스의 상태를 PCB 에 저장하고 필요한 경우 PCB 에서 로드한다.

문맥 교환 (Context Switching)

이전 프로세스의 상태 레지스터 내용을 보관하고 다른 프로세스의 레지스터를 적재하는 과정이다. 즉, 한 프로세스에서 다른 프로세스로 CPU 제어권을 넘겨주는 과정을 말한다.
현재 실행 중인 프로세스의 상태를 저장하고 다음으로 실행될 프로세스의 상태를 로드하는 작업을 한다.

★ 문맥 교환이 일어나는 경우

1. 다른 프로세스가 CPU 를 요청할 때 CPU 할당을 위함
2. interrupt 가 발생했을 때 처리가 끝나면 원래 실행하던 프로세스로 돌아가기 위해 문맥 교환을 수행
3. 시스템 호출(System Call)이나 예외(Exception) 발생 시
4. Time Run Out - CPU 할당 시간이 끝났을 때

PCB (Process Control Block)
프로세스의 상태 정보를 모아놓은 것이다. PCB 가 있어서 문맥 교환이 가능해진다.
프로세스가 생성될 때마다 고유의 PCB 가 생성되며, 프로세스가 완료되면 PCB 는 제거된다.

정리 : 프로세스의 상태가 반복해서 준비 - 실행 - 대기로 변경되는데, 이것을 PCB 를 이용해서 문맥 교환을 한다고 말한다.

► 스케줄링 (Scheduling)

프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업
CPU 할당을 위한 스케줄링

선점 스케줄링 (Preemptive)

우선순위가 높은 프로세스가 CPU 를 점유하는 스케줄링으로, 운영체제가 강력한 제어권을 가지고 있다.

선점 스케줄링 종류 (알고리즘)

• 라운드 로빈 (Round Robin)
  • 같은 크기의 CPU 시간을 할당한다.
• SRT (Shortest Remaining Time First)
  • 실행 시간이 가장 짧은 프로세스를 먼저 실행한다.
  • 프로세스B 가 준비 큐에 들어왔을 때 원래 실행중인 프로세스A 보다 실행시간이 더 짧으면 강제로 A 를 준비 큐에 넣고 B 를 실행할 수 있다.
• MLQ (Multi Level Queue, 다단계 큐)
  • 배치, 실시간 등의 여러 개의 큐를 만들어서 할당한다. 큐 상위에서 하위 단계 순서로 실행한다.
• MLFQ (Multi Level Feedback Queue, 다단계 피드백 큐)
  • 큐마다 다른 CPU 시간을 할당한 후 첫 번째 큐에서 실행한다. 시간이 초과되면 다음 큐로 넘어간다. (FIFO + 라운드로빈)

비선점 스케줄링 (Non-Preemptive)

한 프로세스가 CPU 를 할당받으면 작업 종료 전까지 다른 프로세스는 CPU 를 점유할 수 없다.
운영체제가 제어권이 없어서 오래 걸려도 빼낼 수가 없다.

비선점 스케줄링 종류 (알고리즘)

• FCFS (First Come First Service)
  • 먼저 들어온 프로세스 먼저 빼낸다. (FIFO)
• SJF (Shortest Job First)
  • 실행 시간이 짧은 것을 먼저 실행한다.
• HRN (Highest Response Ratio Next)
  • 경로 우대 사상 - 실행 시간이 짧거나 대기 시간이 긴 것을 먼저 실행한다.
  • 우선순위를 동적으로 결정한다. 우선순위가 높은 것부터 실행한다.
  • 우선순위 = (대기시간 + 실행시간) / 실행시간
• 우선순위 (Priority) : 우선순위를 정한다. (생성될 때 정적으로 결정됨)
• 기한부 (Deadline) : 기한을 정해놓고 그 시간 안에 끝내야 한다.

기아 현상 (Starvation)
SJF 알고리즘 같은 경우 실행 시간이 짧은 프로세스가 계속 들어오면 실행 시간이 긴 프로세스는 한 번도 처리될 수가 없다. 이걸 기아 현상이라고 한다.

• SRT, MLQ, SJF, 우선순위 에서 기아 현상이 발생할 수 있다.

에이징 기법
기아 현상을 해결하기 위한 기법이다. 대기 시간이 증가할수록 프로세스의 우선순위를 높여주는 것이다.

• MLFQ, HRN 등이 에이징 기법을 적용해서 기아 현상을 해결한 기법이다.

► 병행 프로세스 (Concurrent Process)

키워드 : 병행, 임계구역, 상호배제, 동기화, 교착상태-조건(상호,비선점,점유/환형대기), 해결(예방, 회피-은행원, 발견, 회복)

둘 이상의 프로세스들이 동시에 자원을 공유하며 실행 상태에 있는 것이다.
이렇게 하나의 공유 자원을 여러 프로세스가 공유하면 문제가 생길 수 있다.

해결 방법 3가지

• 임계 구역 (critical section) : 한 영역에 오직 한 프로세스만 들어갈 수 있다.
• 상호 배제 : 임계 구역이 가능하도록 다양한 알고리즘을 사용하여 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 것
• 동기화 기법 : 상호 배제를 구현할 수 있도록 임계 구역에 대한 접근을 제어하고, 병행 프로세스 간의 순서를 조정하는 것이다. (세마포어 알고리즘, 모니터, 뮤텍스) 세마포어(Semaphore) : 공유 자원에 여러 프로세스가 접근하는 것을 막는 것
  

교착 상태 (Dead Lock)

상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유하며 서로 무한히 기다리는 상태

교착 상태가 발생하는 조건

조건	설명
상호 배제 (Mutual Exclusion)	한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야함
점유와 대기 (Hold and Wait)	최소한 하나의 자원을 점유하고 있으면서 다른 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함
비선점 (Non-preemption)	다른 프로세스에 할당된 자원은 끝날때까지 강제로 빼앗을 수 없어야 함
환형 대기 (Circular Wait)	프로세스들이 원형으로 구성되어 할당된 자원을 점유하면서 앞, 뒤에 있는 프로세스의 자원 요구해야 함

해결 방법

• 예방 기법 (Prevention) : 교착상태 발생의 네가지중 하나를 제거해 사전에 발생하지 않도록 함
• 회피 기법 (Avoidance) : 적절히 회피하기 / 은행원 알고리즘(Banker’s Algorithm) 사용
• 발견 기법 (Detection) : 점검하여 교착상태를 발견하는것
• 회복 기법 (Recovery) : 교착상태 프로세스를 종료하거나 선점하여 자원을 회복하는 것

► 디스크 스케줄링 알고리즘

디스크에서 어떻게 빨리 데이터를 가져올 수 있게 하는지!

• FCFS (=FIFO) : 요청한 순서대로 데이터를 가져온다.
• SSTF (Shortest Seek Time First) : 헤드 위치에서 가장 가까이 있는 데이터를 가져온다. (정렬 후 계산)
• SCAN : 엘레베이터 알고리즘, 중간 요청까지 다 처리하면서 끝까지 간다. (정렬 후 계산)
• C-SCAN : 중간 요청은 처리하지 않고 끝까지 간다.
• LOOK : SCAN 방식 보완, 처리할 게 없으면 끝까지 가지 않고 다음 처리할 요청으로 간다.
• C-LOOK : C-SCAN 보완
• N-Step SCAN : 중간 요청을 처리하지 않고 모아서 마지막에 처리한다.