[CS 정리] 운영체제 (1)

프로그램

어떤 작업을 위해 실행할 수 있는 파일

 

프로세스

컴퓨터에서 연속적으로 실행되고 있는 프로그램

 

• 즉, 동적인 개념으로는 실행된 프로그램을 의미
• 디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 것
• 메모리에 올라와 실행되고 있는 프로그램의 인스턴스(독립적인 개체)
• 운영체제로부터 시스템 자원(주소 공간, 파일, 메모리 등)을 할당받는 작업의 단위
• 함수의 매개변수, 복귀 주소와 로컬 변수와 같은 임시 자료를 갖는 프로세스 스택과 전역 변수들을 수록하는 데이터 섹션을 포함
• 프로세스 실행 중에 동적으로 할당되는 메모리인 메모리 힙을 포함
• 프로그램과 프로세스는 다르다!!
  • 프로그램은 명령어를 내용으로 가진 디스크에 저장된 파일, 수동적인 존재(passive entity)
  • 프로세스는 다음에 실행할 명령어를 지정하는 프로그램 카운터 및 관련된 자원의 집합을 가진 능동적 존재(active entity)
  • 실행 파일이 메모리에 적재될 때 프로그램이 프로세스가 되는 것

할당받는 자원의 예

• CPU 시간
• 운영되기 위해 필요한 주소 공간
• Code, Data, Stack, Heap의 구조로 되어 있는 독립적인 메모리 영역

특징

• 프로세스는 각각의 독립적인 메모리 영역(Code, Data, Stack, Heap의 구조)를 할당
  • Code : 프로그램을 실행시키는 실행 파일 내의 명령어(소스코드)
  • Data : 전역변수, static 변수의 할당
  • Heap : 동적할당을 위한 메모리 영역
  • Stack : 지역변수, 함수 호출 시 전달되는 파라미터를 위한 메모리 영역
• 각 프로세스는 별도의 주소 공간에서 실행, 한 프로세스는 다른 프로세스의 변수나 자료구조에 접근❌
• 한 프로세스가 다른 프로세스의 자원에 접근하려면 프로세스 간의 통신(IPC, Inter-Process Communication)을 사용
  • 파이프, 파일, 소켓 등을 사용

상태(state)

• new : 프로세스가 처음 생성되었을 때
• ready : 프로세서에게 할당되기를 기다리는 상태
• running : 프로세서에 할당되어 실행되는 상태, CPU를 차지하고 있다
• waiting : 작업이 완료되어 입출력을 기다리는 상태
• teminated :  실행이 종료되어 프로세스 모드가 끝난 상태

프로세스 제어 블록(Process Control Block, PCB)   

특정 프로세스에 대한 중요한 정보를 저장하고 있는 운영체제의 자료구조

• 운영체제는 프로세스를 관리하기 위해 프로세스의 생성과 동시에 고유한 PCB를 생성
• 프로세스는 CPU를 할당받아 작업을 처리하다가 프로세스의 전환이 발생하면 진행하던 작업을 저장하고 CPU를 반환, 이때의 모든 작업을 PCB에 저장
• 다시 CPU를 할당받게 되면 PCB에 저장되어 있던 내용을 불러와 이전에 종료됐던 시점부터 다시 작업을 수행

저장되는 정보

• 프로세스 식별자(Process ID, PID) : 프로세스 식별 번호
• 프로세스 상태 : new, ready, running, waiting, terminated 등의 상태를 저장
• 프로그램 카운터(PC) : 프로세스가 다음에 실행할 명령어의 주소
• CPU 레지스터
• CPU 스케줄링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등
• 메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보
• 입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
• 회계(Accounting) 정보 : 사용된 CPU 양과 시간, 시간 제한, 계정 번호 등
• 입출력 상태 정보 : 프로세스에 할당된 입출력장치들과 열린 파일의 목록 등

프로세스간 통신(IPC, Interprocess Communication)

서로 다른 두 개의 프로세스가 정보를 주고 받는 방식

실행중인 다른 프로세스들에게 영향을 주거나 받지 않는 독립적인 프로세스, 다른 프로세스들에게 영향을 주거나 받는 협력적인 프로세스가 존재

IPC기법을 통해 협력적인 프로세스들은 데이터와 정보를 교환

공유 메모리 시스템(Shared Memory)

기본적으로 프로세스는 서로의 영역에 침범할 수 없지만 프로세스가 이 제약조건을 제거하는 것에 동의하고 공유 영역에 글을 써 정보를 교환하는 방식

공유 메모리 세그먼트를 생성하는 프로세스의 주소공간에 위치시켜 통신하고자 하는 다른 프로세스들이 이 세그먼트를 자신의 주소공간에 추가하는 방법으로 사용. 동시에 공유 버퍼를 접근하는 상황때문에 동기화를 고려해야 함

메시지 전달 시스템(Message-Passing Systems)

커널을 통해 메세지를 교환하기 때문에 별도의 코드를 구축할 필요가 없어 구현이 쉽지만 컨택스트 스위칭이 발생하기 때문에 속도가 느리다는 단점이 존재

 

 

스레드(Thread)

한 프로세스 내에서 실행되는 여러 흐름의 단위

• 프로세스의 특정한 수행 경로
• 프로세스가 할당받은 자원을 이용하는 실행의 단위, CPU 이용의 기본 단위
• 프로세스 내의 주소 공간이나 자원을 공유
• 스레드 ID, 프로그램 카운터, 레지스터 집합, 스택으로 구성
• 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 열린 파일이나 신호와 같은 운영체제 자원을 공유
• 하나의 프로세스를 다수의 실행단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상하는 것 ⇒ 멀티 스레딩
  • 각각의 스레드는 독립적인 작업을 수행해야하기 때문에 각자의 스택과 PC 레지스터를 가진다

특징

• 스레드는 프로세스 내에서 각각 Stack과 레지스터를 따로 할당받고 Code, Data, Heap 영역은 공유
• 한 스레드가 프로세스 자원을 변경하면, 다른 이웃 스레드(Sibling Thread)도 그 변경 결과를 즉시 확인이 가능

분류

권한이 없는 스레드가 시스템 호출을 이용할 수 없도록 막기위해 종류를 나눔.

사용자 수준의 스레드(User Threads)

• 사용자가 만든 라이브러리를 사용하여 스레드를 운용
• 속도는 빠르지만 구현의 어려움
• 시스템 호출 권한이 없는 스레드

커널 수준의 스레드(Kernal Threads)

• 운영체제 커널에 의해 스레드를 운용
• 구현은 쉽지만 유저 모드에서 커널 모드로 계속 바꿔줘야 하기 때문에 속도가 느림
• 시스템 호출 권한이 있는 스레드

 

❓ 스택을 스레드마다 독립적으로 할당하는 이유는?

스택은 함수 호출시 전달되는 인자, 되돌아갈 주소 값 및 함수 내에서 선언하는 변수 등을 저장하기 위해 사용되는 메모리 공간
스택 메모리 공간이 독립적이라는 것은 독립적인 함수 호출이 가능하다는 것 ⇒ 독립적인 실행 흐름의 추가

따라서, 스레드의 정의에 따라 독립적인 실행 흐름을 추가하기 위한 최소 조건으로 독립된 스택을 제공하는 것이다

 

❓ PC Register를 스레드마다 독립적으로 할당하는 이유는?

PC 값은 스레드가 명령어의 어디까지 수행했는지를 나타낸다
스레드는 CPU를 할당 받았다가 스케줄러에 의해 다시 선점당하는데, 이 때문에 명령어가 연속적으로 수행되지 못하고 어느 부분까지 수행됐는지 기록을 해야 한다. 

스레드 풀(Thread Pools)

웹 서버는 요청을 받을 때마다 요청을 위해 새로운 스레드를 생성

• 프로세스를 시작할 때, 일정한 수의 스레드를 미리 풀로 만들어 두는 것
• 평소에는 기다리다가 요청이 들어오면 풀의 한 스레드에게 서비스 요청을 할당
• 요청이 끝나면 스레드는 다시 풀로 돌아가 다음 작업을 대기

다중 스레드 서버의 문제점

1. 서비스할 때마다 스레드를 생성하는데 시간이 소요
   • 스레드는 주어진 일만 끝나게 되면 곧장 폐기되기 때문에 더욱 낭비
2. 모든 요청마다 새로운 스레드를 만들어 서비스 한다면 동시에 실행할 수 있는 최대 스레드의 한계를 정해야 한다
   • 무한정 생성시 CPU 시간, 메모리 공간 등 시스템 자원이 고갈

장점

• 새 스레드를 만들어 주는 것보다 기존 스레드로 서비스 하는 것이 더 빠름
• 스레드 풀은 임의 시각에 존재할 수 있는 스레드 개수에 제한. 많은 수의 스레드를 병렬 처리할 수 없는 시스템에 도움

 

자바 스레드(Java Thread)

• 일반 스레드와 거의 차이가 없으며, JVM이 운영체제 역할
• 자바에는 프로세스 단위❌, 스레드만 존재
• 자바 스레드는 JVM에 의해 스케줄되는 실행 단위 코드 블록
• 스레드와 관련된 많은 정보들도 JVM에 의해 관리
  • 스래드의 개수
  • 스레드로 실행되는 프로그램 코드의 메모리 위치
  • 스레드의 상태
  • 우선순위 등
• 개발자는 자바 스레드로 작동할 스레드 코드를 작성하고, 스레드 코드가 생명을 가지고 실행하도록 JVM에 요청

 

💡 왜 멀티 프로세스 대신 멀티 스레드를 사용할까?

쉽게 설명하자면 프로그램을 여러개 켜는 것보다 하나의 프로그램에서 여러 작업을 하는 것!

 

1. 응답성(Responsiveness) 증가
   • 프로그램의 일부분이 봉쇄되거나, 긴 작업을 실행하더라도 프로그램의 실행이 계속되는 것을 허용함으로써 사용자에 대한 응답성을 증가
   • 예) 웹 브라우저는 한 스레드가 이미지 파일을 로드하고 있는 동안 다른 스레드에서 사용자와의 상호작용
2. 자원 공유(Resource Sharing) : 자원의 효율성 증가
   • 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리 가능
     • 프로세스 간의 Context Switching시 단순히 CPU 레지스터만 교체하는 것이 아니라 RAM과 CPU사이의 캐시 메모리에 대한 데이터까지 초기화하기 때문에 오버헤드가 큼
   • 스레드는 프로세스 내의 메모리를 공유하기 때문에 독립적인 프로세스와 달리 스레드 간의 데이터를 주고 받는 것이 간단해지고 시스템 자원 소모가 감소
   • 코드와 데이터를 공유하면 한 응용 프로그램이 같은 주소 공간 내에 여러 개의 다른 작업을 하는 스레드 보유 가능
3. 경제성(Economy) : 처리 비용 감소
   • 프로세스 간의 통신(IPC)보다 스레드 간의 통신 비용이 적어 작업들 간의 통신 부담이 감소
     • 스레드는 Stack 영역을 제외한 모든 메모리 공유
   • 프로세스 생성을 위해 메모리와 자원을 할당하는 것보다 스레드를 생성하고 문맥 교환을 하는 것이 더 경제적
   • 프로세스 간의 전환 속도보다 스레드 간의 전환 속도가 빠름
     • Context Switching 시 스레드는 Stack영역만 처리! 캐시 메모리를 비우지 않아도 됨
   • 스레드가 프로세스보다 경량이기 때문에 생성과 제거가 쉽다
4. 규모 가변성(Scalability)
   • 다중 처리기 구조에서는 각각의 스레드가 다른 처리기에서 병렬로 실행 가능   

💥 멀티 스레드에서 주의할 점  

1. 동기화 문제
   • 스레드 간의 자원 공유는 전역 변수(데이터 세그먼트)를 이용하므로 함께 사용시 충돌 발생 가능
   • 사용 중인 변수나 자료구조에 접근하여 잘못된 값을 읽어오거나 수정할 수 있다
   • 동기화를 통해 작업 처리 순서를 컨트롤하고 공유 자원에 대한 접근을 컨트롤해야 한다
     • BUT, 병목 현상이 발생해 성능 저하 가능성 
2. 멀티 스레드는 적은 메모리 공간을 차지하고 Context Switching이 빠르다는 장점을 가지고 있지만, 오류로 인해 하나의 스레드가 종료 시 전체 스레드가 종료될 수 있다   

 

Context

CPU가 해당 프로세스를 실행하기 위한 해당 프로세스들의 정보

프로세스의 PCB에 저장한다

 

Context Switching

현재 진행하고 있는 Task(Process, Thread)의 상태를 저장하고 다음 진행할 상태의 Task의 저장된 상태 값을 읽어 복구하는 작업

Context Switching이 진행되는 동안 시스템은 아무런 유용한 일도 하지 못하기 때문에 순수한 오버헤드

이유

• 하나의 Task만 처리할 수 있다면?
  • 해당 Task가 끝날 때까지 기다려야 한다
  • 반응 속도가 느리고 사용하기 불편하다
• 동시에 사용하는 것처럼 하기 위해
  • Computer Multitasking
  • 빠른 속도로 Task를 바꿔가며 실행하기 때문에 사람의 눈으로는 실시간처럼 보임
  • CPU가 Task를 바꿔가며 실행하기 위해 Context Switching이 필요

과정

1. Task의 대부분 정보는 Register에 저장되고 PCB(Process Control Block)로 관리
2. 현재 실행하고 있는 Task의 PCB 정보를 저장(Process Stack, Ready Queue)
3. 다음 실행할 Task의 PCB 정보를 읽어 Register에 적재하고 CPU가 이전에 진행했던 과정을 연속적으로 수행

Context Switching Cost

• 많은 Cost가 필요
  • Cache 초기화
  • Memory Mapping 초기화
  • Kernel은 항상 실행되어야 한다(메모리의 접근을 막기 위해)
• Process vs Thread
  • Process Context Switching Cost > Thread Context Switching Cost
  • Thread는 Stack영역을 제외한 모든 메모리를 공유하기 때문에 Context Switching 수행시 Stack영역만 변경하면 되기 때문에 비용이 적다

 

Thread-Safe

멀티스레드 환경에서 여러 스레드가 동시에 하나의 객체 및 변수(공유 자원)에 접근할 때, 의도한 대로 동작하는 것

 

구현하기

• 공유 자원에 접근하는 임계 영역(critical section)을 동기화 기법으로 제어해야 한다 ⇒ 상호 배제
• 동기화 기법으로는 Mutex나 Semaphore가 존재

Reentrant

재진입성, 여러 스레드가 동시에 접근해도 언제나 같은 실행 결과를 보장하는 것

 

이를 만족하기 위해 해당 서브루틴에서 공유 자원을 사용하지 않으면 된다

• 예를 들어 정적(전역) 변수를 사용하거나 반환하면 안 되고 호출 시 제공된 매개 변수만으로 동작해야 함

 

따라서, Reentrant하면 Thread-Safe 하지만 역은 성립되지 않는다!

 

 

동기화 객체의 종류

스레드 동기화 방법

1. 실행 순서의 동기화
   • 스레드의 실행 순서를 정의하고, 이 순서에 반드시 따르도록 하는 것
2. 메모리 접근에 대한 동기화
   • 메모리 접근에 있어서 동시 접근을 막는 것
   • 실행의 순서가 중요한 상황이 아니고, 한 순간에 하나의 스레드만 접근하면 되는 상황을 의미

동기화 기법의 종류

1. 유저 모드 동기화
   • 커널의 힘을 빌리지 않는(커널 코드가 실행되지 않는) 동기화 기법
   • 성능상 이점, 기능상의 제한
   • ex) 크리티컬 섹션 기반의 동기화, 인터락 함수 기반의 동기화
2. 커널 모드 동기화
   • 커널에서 제공하는 동기화 기능을 활용하는 방법
   • 커널 모드로의 변경이 필요 → 성능 저하
   • 다양한 기능 활용 가능
   • ex) 뮤텍스 기반의 동기화, 세마포어 기반의 동기화, 이벤트 기반의 동기화

 

 

프로세스 동기화

경쟁 상황(Race Condition)

동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황

예시)

T0 : A가 register1 = counter (register1 = 5)

T1 : A가 register1 = register1 + 1 (register1 = 6)

T2 : B가 register2 = counter (register2 = 5)

T3 : B가 register2 = register2 - 1 (register2 = 4)

T4 : A가 counter = register1 (counter = 6)

T5 : B가 counter = register2 (counter = 4)

 

동시에 동일한 자료를 접근해 부정확한 상태에 도달. T4와 T5의 순서를 바꾸면 또 다른 상태에 도달한다.

이로부터 보호하기 위해 한 순간에 하나의 프로세스만 조작하도록 보장해야 함

임계 영역(Critical Section)

동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역

Critical Section Problem(임계 영역 문제)

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

Requirements(해결을 위한 기본 조건)

• Mutual Exclusion(상호 배제)
  : 프로세스 1이 임계 영역에서 실행 중이라면, 다른 프로세스들은 그들이 가진 임계 영역에서 실행될 수 없다
• Progress(진행)
  : 임계 영역에서 실행 중인 프로세스가 없고 별도의 동작이 없는 프로세스들만 임계 영역 진입 후보로서 참여 가능
• Bounded Waiting(한정된 대기)
  : 프로세스 1이 임계 영역 진입 신청 후부터 받아들여질 때까지 다른 프로세스들이 임계 영역에 진입하는 횟수는 제한이 있어야 한다

해결책

뮤텍스(Mutex)

• 공유된 자원의 데이터를 여러 프로세스나 스레드가 접근하는 것을 막는 것
• 상호 배제라고도 함
• Critical Section을 가진 스레드의 Running Time이 겹치지 않도록 각각 단독으로 실행하게 하는 기술
• 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 syncronized 또는 lock을 사용
  • 즉, 뮤텍스 객체를 두 스레드가 동시에 사용 불가

세마포어(Semaphore)

• 공유된 자원의 데이터를 여러 프로세스나 스레드가 접근하는 것을 막는 것
• 리소스 상태를 나타내는 간단한 카운터로 생각
  • 운영체제 또는 커널의 한 지정된 저장장치 내의 값
  • 일반적으로 비교적 긴 시간을 확보하려는 리소스에 이용
  • 유닉스 시스템 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에 행동을 조정하거나 동기화시키는 기술
• 공유 리소스에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근하여 사용 가능
• 각 프로세스는 세마포어 값을 확인하고 변경 가능
  • 사용 중이지 않은 자원의 경우 그 프로세스가 즉시 자원을 사용
  • 이미 다른 프로세스에 의해 사용 중이라는 사실을 알게 되면 재시도하기 전에 일정 시간을 대기
  • 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 한다.
• 세마포어는 2진수를 사용하거나 추가적인 값을 가질 수 있다
  • 카운팅 세마포어
    : 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용, 세마포어는 가용한 자원의 개수로 초기화
      자원을 사용하면 감소, 방출하면 증가
  • 이진 세마포어
    : Mutex라고도 부르며 상호 배제(Mutual Exclusion)의 머리글자를 따서 만들어짐
      이름 그대로 0과 1 사이의 값만 가능하며 다중 프로세스들 사이의 임계 영역 문제를 해결하기 위해 사용

세마포어와 뮤텍스의 차이

• 가장 큰 차이는 관리하는 동기화 대상의 개수
  • Mutex는 동기화 대상이 오직 하나일 때, Semaphore는 동기화 대상이 하나 이상일 때 사용
• Semaphore는 Mutex가 될 수 있지만 Mutex는 Semaphore가 될 수 없다
  • Mutex는 상태가 0, 1 두 개뿐인 binary Semaphore
• Semaphore는 소유할 수 없는 반면, Mutex는 소유 가능. 소유주가 이에 대한 책임을 가짐
  • Mutex의 경우 상태가 두 개뿐인 lock이므로 lock을 가질 수 있다
• Mutex의 경우 Mutex를 소유하고 있는 스레드가 Mutex를 해제 가능하지만 Semaphore는 Semaphore를 소유하지 않는 스레드가 해제 가능
• Semaphore는 시스템 범위에 걸쳐 있고 파일 시스템상의 형태로 존재하지만 Mutex는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 Clean up

모니터

• 뮤텍스(이진 세마포어) + 조건변수
• 최대 하나의 작업만이 모니터에 진입 가능
• 선행 작업이 존재하면 후행 작업은 대기상태로 변화
• 선행 작업이 signal() 연산을 실행하면 즉시 모니터를 떠나고, 다음 작업이 활성화

 

교착상태의 개념과 조건

교착상태(데드락, Deadlock)

• 첫 번째 스레드는 두번째 스레드가 들고 있는 객체의 락이 풀리기를 기다리고 있고, 두번째 스레드 역시 첫번째 스레드가 들고 있는 락이 풀리기를 기다리는 상황
• 모든 스레드가 락이 풀리기를 기다리고 있기 때문에 무한 대기 상태 ⇒ 교착상태에 빠졌다!

교착상태의 4가지 조건

1. 상호 배제(mutual exclusion)
   • 한 번에 한 프로세스만 공유 자원을 사용
   • 좀 더 정확하게는 공유 자원에 대한 접근이 제한
   • 자원의 양이 제한되어 있더라도 교착상태는 발생 가능
2. 들고 기다리기(hold and wait) = 점유 대기
   • 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가 그 접근 권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구 가능
3. 선취(preemption) 불가능 = 비선점
   
   • 한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소 불가능
4. 대기 상태의 사이클(circular wait) = 순환 대기
   • 두 개 이상의 프로세스가 자원 접근을 기다리는데, 그 관계에 사이클 존재

교착상태 방지

• 4가지 조건들 중 하나를 제거하면 된다
• 공유 자원 중 많은 경우가 한 번에 한 프로세스만 사용할 수 있기 때문에(ex. 프린터) 1번 조건은 제거하기 어렵다
• 대부분의 교착상태 방지 알고리즘은 4번 조건, 대기 상태의 사이클이 발생하는 일을 막는데 초점을 맞춤

자원 할당 그래프

교착 상태가 있는 경우

P3를 완료하기 위해 R2가 필요하지만 P1, P2가 자원을 점령해 진행이 불가능

마찬가지로 P2, P1도 자원을 할당 받지 못하고 대기하고 있어 진행이 불가능하다

사이클이 있지만 교착상태가 아닌 경우

P4가 먼저 자원을 할당받아 작업이 종료되어 R2가 반환, P3가 이를 받아 작업이 종료되고 P1이 순차적으로 종료된다.

 

따라서, 사이클이 있어도 항상 교착상태가 존재하는 것이 아님을 알 수 있다!

 

 

---

📚 Reference

Abraham Silberschatz, 『Operating System Concepts』, 조유근, 홍릉과학출판사(2013)
https://github.com/JaeYeopHan/Interview_Question_for_Beginner
https://github.com/WeareSoft/tech-interview
https://github.com/gyoogle/tech-interview-for-developer