[CS/OS] 운영체제 간단 요약

프로세스 vs 스레드 차이

• 프로세스 : 자신만의 고유 공간과 자원을 할당받아 사용하며, 최소 1개의 스레드를 소유함

  • Code, Data, Heap(동적할당 시 사용), Stack(임시 메모리 영역)

• 스레드 : Stack만 따로 할당받고 나머지 영역은 서로 공유하면서 사용

• => 프로세스는 자신만의 고유 공간과 자원을 할당받아 사용하지만, 스레드는 다른 스레드와 공간, 자원을 공유하면서 사용하는 차이 존재

• 멀티프로세스

  • 하나의 프로그램을 여러 개의 프로세스로 구성하여 각 프로세스가 병렬적으로 작업 수행

  • 장점: 안정성 / 단점: 각각 독립된 메모리 영역을 가지고 있어 작업량이 많을수록 오버헤드 발생. Context Switching으로 인한 성능 저하

  • Context Switching : 프로세스의 상태 정보를 저장하고 복원하는 일련의 과정
    -> 캐시메모리 초기화와 같은 무거운 작업이 진행되었을 때, 오버헤드가 발생할 문제 존재

멀티스레딩과 동기화 (뮤텍스, 세마포어)

• 멀티스레드 : 하나의 응용 프로그램이 여러 스레드를 구성해 각 스레드가 하나의 작업을 처리하는 것

• 장점 - 독립적인 프로세스에 비해 공유 메모리만큼의 시간, 자원 손실이 감소, 전역 변수와 정적 변수에 대한 자료 공유 가능

• 단점 - 안정성 문제, 하나의 스레드가 데이터 공간을 망가뜨리면, 모든 스레드가 작동 불능 상태 (공유 메모리를 가지기 때문) → Critical Selection 기법을 통해 대비

• Critical Selection(임계 구역) : 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

• 공유된 자원의 데이터는 한번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 함

• 세마포어 : 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

  • P : 임계 구역 들어가기 전에 수행 (프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

  • V : 임계 구역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

  • 한 프로세스가 P 또는 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다. P와 V를 사용하여 임계 구역에 대한 상호배제 구현이 가능하게 되었다.

• 뮤텍스 : 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술 (이진 세마포어)

  • lock : 현재 임계 구역에 들어갈 권한을 얻어옴 (만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기)

  • unlock : 현재 임계 구역을 모두 사용했음을 알림 (대기 중인 다른 프로세스/스레드가 임계구역에 진입할 수 있음)

  • Dekker 알고리즘 : flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식

    • flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수

    • turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수

  • Peterson 알고리즘 : 데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보함

  • Bakery 알고리즘 : 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입

CPU 스케줄링 알고리즘 (FCFS, SJF, RR, Priority)

• 스케줄링 조건 : 오버헤드 줄이고, 사용률 높이고, 기아 현상 줄여야 함

• 스케줄링 목표

  • Batch System : 가능하면 많은 일을 수행. 시간보다 처리량이 중요

  • Interactive System : 빠른 응답 시간. 적은 대기 시간

  • Real-time System : 기한 맞추기

• 비선점 스케줄링

  • 프로세스 종료 또는 I/O 등의 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이)

  • I/O or Event Wait, Exit

  • FCFS(First Come First Served)

    • 큐에 도착한 순서대로 CPU 할당

    • 실행 시간이 짧은게 뒤로 가면 평균 대기 시간이 길어짐

  • SJF (Shortest Job First)

    • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행

    • FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리

  • HRN (Highest Response-ratio Next)

    • 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF 단점 보완)

    • 우선순위 = (대기시간+실행시간) / (실행시간)

• 선점 스케줄링

  • OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우 (처리시간 예측 어려움)

  • Interrupt, I/O or Event Completion, I/O or Event Wait, Exit

  • Priority 스케줄링

    • 정적/동적으로 우선순위를 부여하여 우선순위가 높은대로 처리

    • 우선순위가 낮은 프로세스가 무한정 기다리는 Starvation이 생길 수 있음

    • Aging 방법으로 Starvation 문제 해결 가능

  • RR (Round Robin)

    • FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum(실행의 최소 단위시간) 만큼 CPU를 할당 받음

    • 할당 시간이 크면 FCFS와 같게 되고, 작으면 문맥교환(Context Switching) 잦아져서 오버헤드 증가

  • Multilevel-Queue (다단계 큐)

    • 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 방법

    • 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 time quantum을 설정해주는 방식 사용

    • 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.

  • Multilevel-Feedback-Queue (다단계 피드백 큐)

    • 다단계 큐에서 자신의 time quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 time quantum을 다 채우지 못한 프로세스는 원래 큐 그대로

    • 짧은 작업에 유리, 입출력 위주 작업에 우선권을 줌

    • 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 turn around 평균 시간을 줄여줌

가상 메모리, 페이지 교체 알고리즘 (FIFO, LRU 등)

• 다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적으로 분할하는 메모리 관리 작업이 필요하기 때문에 이 기법을 도입

  • 연속 메모리 관리 : 프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 함

    • 고정 분할 기법 : 고정된 파티션으로 분할 (내부 단편화 발생)

    • 동적 분할 기법 : 파티션들이 동적 생성되며, 자신의 크기와 같은 파티션에 적재 (외부 단편화 발생)

  • 불연속 메모리 관리 : 프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법

    • 페이지 : 고정 사이즈의 작은 프로세스 조각 -> 고정 크기

    • 프레임 : 페이지 크기와 같은 주기억장치 메모리 조각

    • 단편화 : 기억 장치의 빈 공간 또는 자료가 여러 조각으로 나뉘는 현상

    • 세그먼트 : 서로 다른 크기를 가진 논리적 블록이 연속적 공간에 배치되는 것 -> 가변 크기

• 가상 메모리 페이징

  • 단순 페이징과 비교해 프로세스 페이지를 전부 로드시킬 필요없음

  • 필요한 페이지가 있으면 나중에 자동으로 불러들어짐

  • 외부 단편화 X

  • 복잡한 메모리 관리로 오버헤드 발생

• 가상메모리 세그멘테이션

  • 필요하지 않은 세그먼트들은 로드되지 않음

  • 필요한 세그먼트 있을 때 나중에 자동으로 불러들어짐

  • 내부 단편화 X

  • 복잡한 메모리 관리로 오버헤드 발생

• 페이지 교체 알고리즘

  • 페이지 부재 발생 -> 새로운 페이지를 할당해야 함 -> 현재 할당된 페이지 중 어떤 것을 교체할 지 결정하는 방법

  • 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 쓰지 않는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 한다. 여기서 어던 페이지를 out 시켜야 할지 정해야 한다. (victim page)

  • FIFO 알고리즘 - 메모리에 가장 먼저 올라온 페이지를 먼저 내보내는 알고리즘

    • victim page : out되는 페이지는 가장 먼저 메모리에 올라온 페이지

    • 간단한 방법, 초기화코드에서 적절한 방법

  • OPT 알고리즘 - 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄

    • FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있음

    • 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘

  • LRU 알고리즘 - 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

    • 과고를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘

    • OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 알고리즘에서는 가장 좋은 방법 중 하나

파일 시스템 개념

• 컴퓨터에서 파일이나 자료를 쉽게 발견할 수 있도록, 유지 및 관리하는 방법

• 커널 영역에서 동작

• 파일 CRUD 기능을 원활히 수행하기 위한 목적

• 계층적 디렉토리 구조

• 디스크 파티션 별로 하나씩 둘 수 있음

• 메타 영역과 데이터 영역으로 구분

• 순차 접근 - 가장 간단한 접근 방법 (read, write)

  • 현재 위치를 가리키는 포인터에서 시스템 콜이 발생할 경우 포인터를 앞으로 보내면서 read와 write를 진행. 뒤로 돌아갈 땐 지정한 offset만큼 되감기를 해야 함

• 직접 접근 - 특별한 순서없이, 빠르게 레코드를 read, write

  • 현재 위치를 가리키는 cp 변수만 유지하면 됨

  • 무작위 파일 블록에 대한 임의 접근을 허용하므로, 순서의 제약이 없음

  • 데이터베이스에 활용

• 디렉터리

  • UFD(User file Directory)

  • MFD(Master file directory)

데드락(교착상태)

• 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태

• 무한히 다음 자원을 기다리게 되는 상태

• 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

• 발생 조건 - 4가지가 모두 성립해야 발생

  • 상호 배제 : 자원은 한번에 한 프로세스만 사용할 수 있음

  • 점유 대기 : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함

  • 비선점 : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

  • 순환 대기 : 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

• 데드락 처리

  • 예방 : 교착 상태 발생 조건 중 하나를 제거하면서 해결 (자원 낭비 엄청 심함)

  • 회피

    • 은행원 알고리즘 : 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정상태로 남아있게 되는지 사전에 검사하여 데드락 회피

  • 탐지 : 자원 할당 그래프를 통해 데드락 탐지

  • 회복 : 교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법