박수's Clapany

OS

by 박수 10 min read

운영체제, 한재엽님의 Part 1-4 OS를 기반으로 여러분들의 블로그를 참조!

운영체제

프로세스와 스레드의 차이

프로세스(Process)

  • 프로세스는 실행중인 프로그램
  • 디스크에서 메모리에 적재되어 CPU의 할당을 받을 수 있음
  • OS로부터 주소 공간, 파일, 메모리 등을 할당 받게 됨
  • 구성요소
    • 프로세스 스택 : 함수의 매개변수 / 복귀 주소 / 로컬 변수
    • 데이터 섹션 : 전역 변수
    • 메모리 힙 : 프로세스 실행 중 동적으로 할당되는 메모리
프로세스 제어 블록(Process Control Block, PCB)
  • 특정 프로세스에 중요한 정보를 저장하고 있는 운영체제의 자료구조
  • 운영체제는 프로세스의 관리를 위해 프로세스의 생성과 동시에 고유한 PCB 생성
  • 프로세스는 CPU를 할당 받아작업을 처리하다가 프로세스의 전환이 발생할 경우 진행하던 작업을 저장하고 CPU의 반환이 필요
    • 작업의 진행 상황을 PCB에 저장
  • PCB에 저장되는 정보
    • 프로세스 식별자(Process ID, PID) : 프로세스 식별번호
    • 프로세스 상태 : new, ready, running, waiting, terminated 등의 상태 저장
    • 프로그램 카운터 : 프로세스가 다음에 실행할 명령어의 주소
    • CPU 레지스터
    • CPU 스케쥴링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등
    • 메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보 포함
    • 입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
    • 어카운팅 정보 : 사용된 CPU 시간, 시간제한, 계정번호 등

스레드(Thread)

  • 프로세스의 실행 단위
  • 한 프로세스 내에서 동작되는 여러 실행 흐름
    • 프로세스 내의 주소 공간이나 자원의 공유 가능
  • 구성
    • 스레드 ID
    • 프로그램 카운터
    • 레지스터 집합
    • 스택
  • 공유자원(다른 스레드와)
    • 코드
    • 데이터 섹션
    • 운영체제 자원(열린 파일, 신호 등)
  • 멀티스레딩
    • 하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유
    • 자원의 생성과 관리의 중복성을 최소화함으로써 수행 능력 향상
스택이 스레드마다 존재하는 이유
  • 스택은 [함수 호출 시 전달되는 인자, 되돌아갈 주소값, 함수 내 선언 변수]에 사용
  • 따라서 스택을 독립적으로 사용하면 독립적인 함수의 사용 가능
  • 스택은 즉 독립적인 실행 흐름을 위한 최소 조건
PC Register를 스레드마다 독립할당하는 이유
  • 프로세서 레지스터는 명령이 어디까지 수행됐는지를 저장
  • 스레드는 CPU를 할당 받았다가 스케줄러에 의해 우선순위를 빼앗길 수 있음
  • 다 수행되지 못한 명령어에 대해서 위치를 표시할 필요 존재


멀티스레드

장점

  • 프로세스를 이용하여 동시에 처리하던 일을 스레드로 구현할 경우 메모리 공간과 시스템 자원 소모를 줄일 수 있음
  • 스레드간 통신은 전역 변수의 공간이나 heap영역을 이용하므로 별도의 자원을 사용하지 않음(프로세스간 통신에 비해 훨씬 간단)
  • 스레드의 context switch는 프로세스 context switch와 다르게 캐시 메모리를 유지

단점

  • 동일한 자원에 접근하는 경우에 대한 처리 필요
    • 동기화 작업 필요
    • 작업 순서 컨트롤, 자원 접근 컨트롤 필요
    • 하지만 위 작업들에 의해 병목현상이 발생할 가능성 존재

멀티스레드 vs 멀티프로세스

  • 멀티스레드가 멀티프로세스보다 적은 메모리 공간 사용 / context swtich 빠름
  • 오류에 의해 하나 스레드 종료가 전체 스레드에 영향을 끼칠 가능성 존재


스케줄러

프로세스의 스케줄링을 위한 Queue

  • Job Queue : 현재 시스템 내의 모든 프로세스 집합
  • Ready Queue : 현재 메모리 내에 있으며, CPU를 점유하여 실행을 대기하는 프로세스 집합
  • Device Queue : Device I/O 작업을 대기하는 프로세스 집합

각 Queue를 프로세스들에 넣고 빼는 스케줄러

장기스케줄러(Long-term scheduler or job scheduler)

  • 한정된 메모리에 많은 프로세스가 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적인 디스크)에 임시 저장
  • 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 Ready Queue로 보낼지 결정
  • 메모리 <-> 디스크 사이의 스케줄링 담당
  • 프로세스에 memory를 할당
  • Degree of Multiprogramming 제어(메모리에 몇 개의 프로그램이 올라갈지)
  • 프로세스 상태 (new / ready) cf) 메모리에 프로그램이 너무 많거나 적게 올라가도 성능이 좋지 않음. time sharing system에서는 장기 스케줄러가 존재하지 않음 곧바로 메모리에 올라가서 ready 상태가 됨

단기스케줄러(Short-term scheduler or CPU scheduler)

  • CPU와 메모리 사이의 스케줄링 담당
  • Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running할지 결정
  • 프로세스에 CPU를 할당(scheduler dispatch)
  • 프로세스의 상태(ready -> running -> waiting -> ready)

중기스케줄러(Medium-term scheduler or Swapper)

  • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄(swapping)
  • 프로세스에게서 memory를 deallocate
  • degree of Multiprogramming 제어
  • 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절
  • 프로세스 상태(ready -> )

#####

  • 외부적 이유로 프로세스 수행이 정지된 상태로 메모리에서 내려간 상태를 의미
  • 프로세스 전부가 디스크로 swap out
  • blocked 상태는 다른 I/O 작업을 기다리는 상태이므로 ready state로 돌아갈 수 있지만 는 불가능


CPU 스케줄러

스케줄링 대상은 Ready Queue에 있는 프로세스들

FCFS(First Come First Served)

특징
  • 비선점형(Non-Preemptive) 스케줄링
    • CPU 점유시 CPU burst가 완료될때까지 CPU를 반환하지 않음
  • 할당되었던 CPU반환시에 스케줄링 이루어짐
문제점
  • convoy effect : 소요시간이 긴 프로세스가 먼저 도달하여 효율성이 낮아지는 현상 발생

SJF(Shortest - Job - First)

특징
  • 프로세스의 진입순서보다 CPU burst time이 짧은 프로세스를 먼저 CPU에 할당
  • 비선점형(Non-Preemptive) 스케줄링
문제점
  • starvation : 지나친 효율성 추구로 프로세스가 차별을 받게 됨 / 상대적으로 사용 시간이 긴 프로세스가 할당을 받지 못하는 상황 발생

SRT(Shortest Remaining time First)

특징
  • 새로운 프로세스 도착시 스케줄링
  • 선점형(Preemptive) 스케줄링
    • 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU Burst time을 가지는 프로세스 도착시 CPU 빼앗김
문제점
  • starvation : 새로운 프로세스 도달시마다 스케줄링을 다시 함 / CPU burst time(CPU 사용시간)측정 불가

Priority Scheduling

특징
  • 우선순위가 가장 높은 프로세스에게 CPU 할당
  • 우선순위는 정수로표현, 작은숫자가 우선
  • 선점형 스케줄링(Preemptive) 방식
    • 더 높은 우선순위의 프로세스 도착시 실행중인 프로세스를 멈추고 CPU 선점
  • 비선점형 스케줄링(Non-Premmptive) 방식
    • 더 높은 우선순위의 프로세스 도착시 Ready Queue의 가장 앞에 넣음
문제점
  • starvation : 무기한 봉쇄(Indefinite blocking) - 실행 준비는 되었으나 CPU를 사용하지 못하는 프로세스들이 CPU를 무기한 대기

Round Robin

특징
  • 현대적 CPU 스케줄링
  • 각 프로세스는 동일한 크기의 할당 시간(time quantum) 가짐
  • 할당 시간이 지나면 프로세스는 ready queue의 뒤에서 다시 대기
  • Round Robin은 CPU사용시간이 랜덤한 프로세스들이 섞여 있으 경우에 효율적임
  • Round Robin이 가능한 이유는 Process의 context를 save할 수 있기 때문
장점
  • Response time이 빨라짐
    • ready queue에 있는 n개의 프로세스에 대해 각각 q의 할당 시간을 준다면 프로세스는 q 단위로 CPU시간의 1/n을 얻음
    • 즉 모든 프로세스는 (n-1)q time unit 이상 기다리지 않음
  • 프로세스가 기다리는 시간이 CPU를 사용하는 만큼 증가
주의점
  • 설정한 time quantum(q)가 너무 커지게되면 FCFS와 동일
  • 너무 작아질경우 잦은 context switch로 overhead 발생


프로세스 동기화

Critical Section(임계영역)

멀티 스레딩의 문제 처럼 동일한 자원을 동시에 접근하는 작업(공유 변수 사용, 동일 파일 사용 등)을 실행하는 코드 영역을 Critical Section이라 함

Critical Section Pro(임계영역 문제)

프로세스들이 Critical Section을 함께 사용할 수 있는 프로토콜을 설계하는 것

Requirements(해결을 위한 기본조건)
  • Mutual Exclusion(상호 배제)
    • 프로세스 P1이 Critical Section에서 실행중인 경우, 다른 프로세스들은 Critical Section내에서는 실행 불가
  • Progress(진행)
    • Critical Section에서 실행중인 프로세스가 없고, 별도 동작이 없는 프로세스만이 Critical Section 진입 후보로 참여 가능
  • Bounded Waiting(한정된 대기)
    • P1이 Critical Section에 진입 신청 후 받아들여질 때까지, 다른 프로세스들이 Critical Section에 진입하는 횟수는 제한이 있어야 함

해결책

Lock
  • 하드웨어 기반 해결책, 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section에 진입하는 프로세스는 Lock을 획득 후 Critical Section을 빠져나올때 Lock반납
  • 다중처리기 환경에서는 시간적인 효율성 측면에서 적용이 불가
Semaphores(세마포)
  • 소프트웨어상에서 Critical Section 문제를 해결하기 위한 동기화 도구
  • 종류
    • OS는 Counting/Binary 세마포를 구분
    • Counting Semaphore
      • 가용한 개수를 가진 자원에 대한 접근 제어용도
      • 가용 자원의 개수로 초기화
      • 자원사용시 semaphore 감소 / 방출시 semaphore 증가
    • Binary Semaphore
      • MUTEX라고도 불리움, 0과 1사이의 값만 가능하며, 다중 프로세스 사이의 Critical Section문제해결을 위해 사용
  • 단점
    • Busy Waiting(바쁜 대기)
      • critical session에 진입해야하는 프로세스가 진입 코드를 반복 실행해야하며, CPU시간을 낭비하게 됨
  • Deadlock(교착상태)
    • 세마포가 Ready Queue를 가지고 있고,
    • 둘 이상의 프로세스가 Critical Session 진입을 무한정 기다리며,
    • Critical Session에서 실행되는 프로세스는 진입 대기중인 프로세스가 실행되어야만 빠져나올 수 있는 상황
    • 결국 서로 기다리는 상황..
모니터
  • 고급 언어의 설계 구조물, 개발자의 코드를 상호배제 하도록 만든 추상화 데이터 형태
  • 공유자원에 접근하기 위한 키 획득 및 해제를 모두 처리(cf. 세마포어의 경우 직접 키해제 및 공유자원 접근 처리가 필요)


메모리 관리 전략

메모리 관리 배경

  • 각 프로세스는 독립된 메모리 공간을 가지며, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근이 불가능
  • 단, 운영체제는 운영체제 메모리 영역과 사용자의 메모리 영역의 접근에 자유로움
Swapping
  • 메모리의 관리를 위하여 사용되는 기법
  • 표준 Swapping 방식 : 다중 프로그래밍 환경에서 CPU할당 시간이 끝난 프로세스의 메모리를 보조 기억 장치로 내보내고, 다른 프로세스의 메모리를 불러옴

    • 위의 과정을 swap이라 함. 주 기억장치(RAM)으로 불러오는 과정을 swap-in, 보조 기억장치로 내보내는 과정을 swap-out이라 칭함. 단, swap에는 전송시간이 필요하므로 메모리 공간이 부족할때에 한하여 swapping 수행

  • 단편화(Fragmentation) : 프로세스들이 메모리에 적재되고 제거되는 일이 반복될 경우, 프로세스가 차지하는 메모리 틈 사이에 사용하지 못하는 작은 자유공간이 늘어남
    • 단편화의 2종류
      • 외부단편화 : 메모리 공간 중 사용하지 못하게 되는 일부분, RAM에서 사이사이 남는 공간을 모두 합치면 충분한 공간이 되지만 사용하지 못하는 공간들
      • 내부단편화 : 프로세스가 사용하는 메모리 공간에 포함되어 있으나 남는 뿌분
  • 압축
    • 외부 단편화를 최소하하기 위하여 프로세스가 사용하는 공간을 한쪽으로 몰아 넣음
    • 자유공간을 확보할 수 있지만 작업효율이 좋지 못함.

Paging(페이징)

  • 하나의 프로세스가 사용하는 메모리 공간이 연속적이여야 한다는 제약을 없애는 메모리 관리 방법
  • 외부 단편화와 압축 작업의 해소를 위해 생긴 방법론
  • 물리 메모리는 Frame이라는 고정 크기로 분리, (프로세스가 점유하는)논리 메모리는 페이지라 불리는 고정 크기의 블록으로 분리.
  • 페이징 기법을 사용하여 논리 메모리는 물리 메모리에 저장될 때, 연속적으로 저장될 필요가 없이 물리 메모리의 남는 프레임에 적절히 배치하여 외부단편화를 해결
  • 하나의 프로세스가 사용하는 공간은 여러개의 페이지로 나눠서 관리되며, 개별 페이지는 순서에 상관없이 물리메모리에 있는 프레임에 mapping되어 저장됨
  • 단점
    • 내부 단편화의 비중이 늘어나게 됨
      • 예) 페이지의 크기가 1,024B이고, 프로세스 A가 3,172B의 메모리를 요구할 경우, 3개의 페이지 프레임(1,024 * 3 = 3,072) + 100B로 구성되므로 총 4개의 페이지(4,096B)의 프레임이 필요. -> 924B의 내부 단편화 문제가 발생

segmentation(세그먼테이션) 참고

  • 페이징기법에서는 동일한 크기의 블록(페이지)를 사용하는 것에 반하여, 서로 크기가 다른 논리적 단위인 세그먼트(segment)로 분할하여 메모리를 할당
  • 메모리를 페이징 기법과 달리 미리 분할할 수 없음
  • 메모리가 적재될 때에 빈 공간을 찾아 할당하는 사용자 관점의 메모리 관리 기법
  • 코드부 혹은 리소스/데이터 파트에서 데이터를 참조할 시, 메모리의 위치가 아닌 오프셋을 기준으로 데이터 탐색
    • 마이크로프로세서에 의해 세그먼트 테이블을 참조하여, 실제 물리 주소로 변환
  • 단점
    • 세그먼트들에 대해 필요시 메모리에 올리고 내리는 작업을 반복하다보면 외부 단편화가 발생


가상 메모리

  • 프로세스 전체가 메모리에 올라오지 않은 경우에도 실행이 가능하도록 하는 기법
    • (다중 프로그래밍을 실현하기 위해서는 프로세스들을 동시에 메모리에 올려야 함)

가상 메모리의 개발 배경

  • 실행되는 코드를 전부 물리 메모리에 올리는데에 제한사항이 따름
  • 메모리 용량보다 더 큰 프로그램을 실행할 수 없음
  • 여러 프로그램을 동시에 메모리에 올리는 데에 한계가 있음(메모리용량, 페이지 교체 등의 성능 이슈)
  • 사용빈도가 낮은 코드의 메모리 점유
프로그램의 일부만을 메모리에 올리는 것
  • 물리 메모리의 크기 제약을 받지 않음
  • 더 많은 프로그램을 동시에 실행
  • swap에 필요한 입출력이 줄어들기 때문에 프로그램이 빠르게 실행

가상 메모리의 역할

  • 가상 메모리는 실제 물리 메모리의 개념 <-> 사용자의 논리 메모리 개념 분리
  • 작은 메모리로 얼마든지 큰 가상 주소 공간을 사용 가능
가상 주소 공간
  • 한 프로세스가 메모리에 저장되는 논리적인 모습을 가상메모리에 구현한 공간
  • 프로세스가 요구하는 메모리 공간을 가상메모리에 제공함으로서 현재 직접적으로 필요치 않은 메모리 공간은 실제 물리 메모리에 올리지 않은 것으로 물리 메모리를 절약
  • 한 프로그램이 실행되었을 때 논리 메모리로 100KB가 요구되었을때, 실행까지 필요한 메모리공간(heap, stack, code, 데이터)의 합이 40KB라면 실제 물리 메모리에는 40KB만 올리고, 나머지 60KB는 필요시에 물리 메모리에 요구
프로세스간 페이지 공유
  • 가상메모리
    • 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 함.
      • 각 프로세스는 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가 있는 물리 메모리 페이지들이 모든 프로세스에 공유
    • 프로세스들이 메모리를 공유하는 것을 가능하게 하며, 프로세스들은 공유 메모리를 통해 통신 가능
    • fork()를 통한 프로세스 생성 과정에서 페이지들의 공유 가능

Demand Paging(요구 페이징)

  • 프로그램 실행 시작 시 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신에 초기 필요한 것만 적재
  • 가상 메모리 시스템에서 많이 사용됨
  • 가상 메모리는 보통 페이지로 관리
  • 요구 페이징을 사용하는 가상 메모리에서는 실행 과정에서 필요해질때 페이지들이 적재
  • 페이저
    • 프로세스 내의 개별 페이지들은 페이저에 의해 관리됨
    • 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어 옮
      • 사용되지 않을 페이지를 가져오는 시간/메모리 낭비 줄임
Page fault trap(페이지 부재 트랩)
  • 우선 pass..

페이지 교체

  • 요구 페이징에서 언급되었듯이, 프로그램 실행시 모든 항목이 물리 메모리에 올라오지 않으므로, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 페이지 부재가 발생할 수 있음
  • 페이지 부재 발생시 원하는 페이지를 보조저장장치에서 가져와야함.
  • 만일 물리 메모리가 모두 사용중인 경우, 페이지 교체 발생(or 운영체제에 의한 프로세스 강제 종료)
기본적 방법

물리 메모리가 모두 사용중인 상황에서의 메모리 교체 흐름

  1. 디스크에서 필요한 페이지의 위치를 찾음
  2. 빈 페이지 프레임을 찾음
  3. 페이지 교체 알고리즘을 통해 희생(victim) 페이지 선택
  4. 희생될 페이지를 디스크에 기록, 페이지 테이블 수정
  5. 새롭게 비워진 페이지 테이블의 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정
  6. 사용자 프로세스 재시작

페이지 교체 알고리즘

FIFO 페이지 교체
  • 가장 간단한 페이지 교체 알고리즘, FIFO(First-in first-out)의 흐름
  • 먼저 물리 메모리에 들어온 페이지 순서대로 교체 시점에 나가게 됨
  • 장점
    • 쉬운 이해, 쉬운 프로그래밍
  • 단점
    • 오래된 페이지가 항상 불필요한 정보를 포함한다는 보장이 없음
    • Belady의 모순 : 페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순 존재
최적 페이지 교체(Optimal Page Replacement)
  • 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아서 교체
  • Belady의 모순 확인 이후, 모든 알고리즘 보다 낮은 페이지 부재율을 보이며, Belady의 모순이 발생하지 않음
  • 장점
    • 알고리즘 중 가장 낮은 페이지 부재율
  • 단점
    • 구현의 어려움, 모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없음
LRU 페이지 교체(LRU Page Replacement)
  • LRU: Least-Recently-Used
  • 최적 알고리즘의 근사 알고리즘
  • 특징
    • 대체로 FIFO알고리즘보다 우수, OPT알고리즘보다 비효율
LFU 페이지 교체(LFU Page Replacement)
  • LFU: Least Frequently Used
  • 참조 횟수가 가장 적은 페이지를 교체
  • 특징
    • 어떤 프로세스가 특정 페이지를 집중적으로 사용하다, 다른 기능을 사용하게되면 더 이상 사용하지 않아도 계속 메모리에 머물게 됨
    • 최적(OPT) 페이지 교체를 제대로 근사하지 못함
MFU 페이지 교체(FU Page Replacement)
  • MFU: Most Frequently Used 참조회수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로도 계속 사용 될 것에 가정
  • 특징
    • 최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않음


캐시의 지역성

캐시의 지역성 원리

  • 캐시 메모리는 속도가 빠른 장치와 늘니 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리
  • CPU가 어떤 데이터를 원할지에 대한 예측 필요
  • 적중률(Hit rate)을 극대화 하기 위하여 지역성(Locality)의 원리를 사용
    • 전제조건 : 프로그램은 모든 코드나 데이터를 균등하게 Access하지 않는다
    • 지역성
      • 시간 지역성: 최근에 참조된 주소의 내용은 곧 다음에 다시 참조
      • 공간 지역성: 대부분의 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

Caching line

  • 캐시는 프로세서 가까이에 위치하여 빈번하게 사용되는 데이터를 놔두는 장소
  • 캐시가 아무리 가까이 있더라도 찾고자 하는 데이터를 순회하여 찾아야 한다면 시간이 오래 걸림
  • 캐시의 목적데이터에 바로 접근(상수시간)이 필요
  • 따라서 캐시에 데이터를 저장할 때 자료구조를 이용, 묶음으로 저장하며 이를 캐싱라인이라 함
    • 캐시에 저장하는 데이터에 데이터의 메모리 주소를 함께 저장하여 태그를 달아 놓음
    • 태그들의 묶음을 캐싱라인이라고 함
    • 3가지 방식 존재*(다음에 자세히 알아보기로..)
      • Full Associative
      • Set Associative
      • Direct Map