스케쥴링 알고리즘

스케쥴링 알고리즘 기본

• waiting time / turnaround time 줄이는 최적의 방법 찾기
• Preemptive or non-preemptive(선점형과 비선점형)

프로세스(Process) 란?

• 실행 중인 프로그램은 프로세스라고 함
  • 프로세스 : 메모리에 올려져서 실행 중인 프로그램
  • 코드 이미지(바이너리) : 실행파일 ex. ELF format

    프로세스라는 용어는 작업, task, job이라는 용어를 혼용

• 응용 프로그램 =! 프로세스
  • 응용 프로그램은 여러 개의 프로세스로 이루어질 수 있음
• 하나의 응용 프로그램은 여러 개의 프로세스(프로그램)가 상호작용을 하면서 실행될 수도 있다.

  간단한 C/C++ 프로그램을 만든다면 하나의 프로세스 여러 프로그램을 만들어서, 서로 통신하면서 프로그램을 작성할 수도 있음(IPC 기법)

스케쥴러와 프로세스

누가 프로세스 실행을 관리할까요? -> 스케쥴러

스케쥴리 알고리즘

• 어느 순서대로 프로세스를 실행시킬까?
• 어떤 규칙에 의해 어느 시점에서 프로세스를 실행시킬까?
• 목표
  • 시분할 시스템 예 : 프로세스 응답 시간을 가능한 짧게
  • 멀티 프로그래밍 예 : CPU 활용도를 최대한 높혀서, 프로세스를 빨리 실행

FIFO 스케쥴러

프로세스가 저장매체를 읽거나 프린팅을 하는 작업 없이 쭉 CPU를 처음부터 끝까지 사용한다고 가정!(CPU만 계속 쓰는 프로그램으로 가정)

• 가장 간단한 스케쥴러(배치 처리 시스템과 유사)
• FCFS(First Come, First Served) 스케쥴러
• Convoy Effect(똥차 효과) : CPU 점유를 길게하는 놈이 먼저 와버리면 나머지 짧은 놈들이 다 기다려야함 마치 똥차 때문에 스포츠카들이 다 기다려야하는 그런 상황….

최단 작업 우선(SJF) 스케쥴러

• Shortest Job First 스케쥴러
• 가장 프로세스 실행시간이 짧은 프로세스부터 먼저 실행시키는 알고리즘
• 실행시간을 미리 알고있어야 한다는 단점이 있음.
• 다음 CPU burst의 시간이 짧은 놈부터 실행, 만약 두 프로세스가 같다면 FCFS 적용

여기서 잠깐!

• RealTime OS(RTOS): 응용 프로그램 실시간 성능 보장을 목표로 하는 OS
  • 정확하게 프로그램이 언제 시작할지, 언제 완료될지 시간을 보장하는 것
  • Hardware RTOS, Software RTOS
  • 시간에 민감한 프로세스에 사용됨.
• General Purpose OS(GPOS) : 프로세스 실행시간에 민감하지 않고, 일반적인 목적으로 사용하는 OS
  • 예 : Windows, Linux 등

우선순위 기반 알고리즘

• Priority-Based 스케쥴러
  • 정적 우선순위
    • 프로세스마다 우선순위를 미리 지정
  • 동적 우선순위
    • 스케쥴러가 상황에 따라 우선순위를 동적으로 변경
    • 응답시간에 민간한 프로세스라면 먼저,

Round Robin 스케쥴러

• 시분할 시스템을 기본으로 하는 스케쥴러
• 3초와 2초 소요되는 프로그램이 있을 때, 각각 1초씩 진행하고 queue로 들어와 다시 또 각각 1초씩 진행

정리

• 다양한 기본 스케쥴링 알고리즘
  • FIFO(FCFS) 스케쥴링 알고리즘(배치 처리 시스템)
• 최단 작업 우선(SJF) 스케쥴링 알고리즘
• 우선순위 기반 스케쥴링 알고리즘
  • 정적 우선순위, 동적 우선순위
• Round Robin 스케쥴링 알고리즘
  • 시분할 시스템

스케쥴링 알고리즘

프로세스 상태와 스케쥴링

멀티 프로그래밍과 Wait

• 멀티 프로그래밍 : CPU 활용도를 극대화하는 스케쥴링 알고리즘
• Wait : 저장매체로부터 파일 읽기를 기다리는 시간(CPU가 작동하지 않는 시간)

  위와 같은 스케줄링은 어떻게 할까?

프로세스 상태

• 어떤 특정 시점에 어떤 프로세스를 실행시킬지 판단해야 한다.
  • 프로세스 상태 정보를 이용하면 가능함
• ready state : CPU에서 실행 가능 상태(싱행 대기 상태)
  • 바로 싱행 가능
• block state : Wait상태, 특정 이벤트 발생 대기 상태
  • 저장매체에 파일 읽기를 요청했다면, 이 프로세스는 파일을 다 읽을 떄까지 기다린다.
  • 만약 위와 같은 특정 작업이 끝나면(block 상태가 끝나는) 운영체제에서 특정 이벤트를 특정 프로세스에 발생시켜 그래서 프로세스가 읽기가 끝난 것을 알 수 있음
  • 그 후 block에서 ready 로 바꿈
• running state : 현재 CPU에서 실행 상태
  • cpu가 1개라 가정하면 running state인 프로세스는 1개 또는 0개이다.
• 종료(exit) : 종료를 위한 일정 시간이 필요함
  • 파일, 시스템 리소스 등을 풀어줘야하는 시간이 필요함
  • 매우 짧은 시점
• 생성

프로세스 상태간 관계

ready, running, block state가 반복된다.

• running인 상태에서 block인 상태로 바뀜
• cpu는 비었고, ready상태인 프로세스 중 하나를 cpu로 가져옴
• block상태에서 특정 이벤트를 받으면(block상태가 끝나면, 다른 작업이 끝나면) 다시 ready상태로 감
• 위와 같은 사이클이 반복

스케쥴링 알고리즘

프로세스 상태와 스케쥴링

• 특정 시점에 각각 프로세스들의 상태로 어떻게 스케쥴링을 할까?
  • Queue 자료형을 이용해서 알고리즘이 됨
  • ready state queue, running state queue, block state queue 등을 이용해서 각 정책에 맞게 스케쥴링
• 우선순위, 최단시간 등의 목적에 따라 알맞은 자료형을 사용해 각각의 스케쥴러를 만든다.(알고리즘)

CPU 상태

• 아무것도 실행하지 않는 상태 == CPU idle 상태

스케쥴링 알고리즘

선점형과 비선점형 스케쥴러

• 이전까지는 기본적인 알고리즘을 알아보았다.
• 이번에는 다른 측면에서 알고리즘을 2가지로 나눠보았다.
• (요즘은 대부분 선점형 스케쥴러임)
  1. 선점형 스케쥴러(Preemptive Scheduling)
• 하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할 수 있음
• 시분할 시스템을 생각했을 때, 특정 A프로세스가 진행되다가 특정 시기에 강제로 중단시키고 다른 프로세스를 실행시킴(b프로세스)
• 이때 스케쥴러는 A프로세스를 ‘선점’해서 A를 중지시키고 다른 프로세스를 실행시킴
• 이처럼 선점해서 제어한다고 해서 선점형

1. 비선점형 스케쥴러(Non-preemptive Scheduling)
   • A프로세스가 실행을 하다가 다른 리소스를 읽거나 프로그램이 끝났을 때 즉, 자체적으로 끝나거나 block될 때 스케쥴러가 나타나서 다른 프로세스를 넣어주는 스케쥴러
   • 이미 실행되고 있는 프로세스를 제어하지 못함

초반에는 비선점형이 기본이었지만, 시분할을 하려면 선점형이 필요함(강제성이 필요함)

스케쥴링 알고리즘

스케쥴러 구분(정책, Policy)

• FIFO(FCFS), SJF(최단작업먼저), Priority-based는 어떤 프로세스를 먼저 실행시킬지에 대한 알고리즘
  • 비 선점형에 가까움
• ROundRonbin은 시분할 시스템을 위한 기본 알고리즘(선점형 스케줄러)
  • 프로세스 조금 실행하고 다시 뒤로 보내고, 조금 실행하고 다시 뒤로 보내고(Queue 활용)

랙? : 마우스 / 키보드 반응이 느린 경우

• 스케줄링이 다양한 프로세스를 적절하게 분배하지 못 할 경우 발생하는 문제!
• 리눅스 스케쥴러 : O(1), CFS와 같이 다양한 방식으로 변경시도 중
  • 인터렉티브, IO, CPU 중심 프로세스로 미리 구분할 수 있다면 보다 개선된 스케쥴링이 가능함

    스케쥴러가 해결해야하는 이슈! 다양하고 복잡한 스케쥴링 알고리즘 필요

스케쥴링 알고리즘

인터럽트(Interrupt)

CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 또는 예외상황이 발생하여 처리가 필요할 경우에 CPU에 알려서 처리하는 기술

• 프로세스의 상태가 바뀌는 경우 block이 끝나거나 ready에서 running을 하는 등 이러한 과정을 알려주는 게 뭐냐? 어떤 시그널이 보내져서 알게 될텐데, 그게 바로 인터럽트!!(이벤트를 발생시키는 주체)
• 이벤트가 발생
  • 이벤트가 발생했을 때 처리(Kernel code)를 해주는 기술 == 인터럽트
• 어떤 이벤트가 발생하면 인터럽트가 CPU에 걸어준다.라는 표현을 씀
• CPU가 코드를 실행하고 있을 때 외부에서 알려주는 기술

  어느 한순간, CPU가 실행하는 명령은 하나!

인터럽트가 필요한 이유

• 선점형 스케줄러 구현에 필수적
  • 프로세스가 running 중에 스케줄러가 이를 중단시키고, 다른 프로세스를 교체하기 위해, 현태 프로세스 실행을 중단시킴
    • 중단시키는 것을 인터럽트가 함
• IO Device와의 커뮤니케이션
  • 저장매체에서 데이터 처리 완료 시, 프로세스를 깨워야 함(block state -> ready state)
  • block 상태가 끝날 떄, 알려줘야함
• 예외 상황 핸들링
  • CPU가 프로그램을 한 줄 한줄 실행하고 있을 때, 입출력 하드웨어 등의 장치나 또는 예외상황이 발생할 경우
    • CPU가 코드 실행에 집중하고 있을 떄 외부에 문제가 발생했을 때 알려줘야함
    • 예를 들면 0으로 나눌 때 문제가 발생했다는 것을 알려줘야함.
    • CPU가 해당 처리를 할 수 있도록 CPU에 알려줌
• 이벤트(인터럽트)를 정의하고, 처리하는 것 모두 운영체제가 함

인터럽트

CPU는 PC(programming counter)가 가르키고 있는 코드 한 줄에만 집중하고 있음. 외부 이슈를 처리해야할 때 인터럽트가 CPU에게 정보를 알려줌 이러한 기술을 운영체제 안에서 구현해놓았음.

인터럽트 처리 예

• CPU가 프로그램을 실행하고 있을 때
  • 입출력 하드웨어 등의 장치 이슈 발새
    • 파일 처리가 끝났다는 것을 운영체제에 알려주기
    • 운영체제는 해당 프로세스를 block state에서 실행 대기(Ready) 상태로 프로세스 상태 변경하기
  • 또는 예외 상황이 발생
    • 0으로 나누는 계산 발생 등의 예외 상황에 인터럽트를 실행시켜 운영체제에 알려주기
    • 운영체제가 해당 프로세스 실행 중지/에러 표시

이벤트와 인터럽트

• 인터럽트는 일종의 이벤트로 불림
• 이벤트에 맞게 운영체제가 처리

주요 인터럽트(Interrupt)

1. 계산하는 코드에서 0으로 나누는 코드 실행 시(Divide-by-Zero Interrupt)
   • 운영체제에 있는 ‘0으로 나누기’ 인터럽트 처리 루틴이 에러 메세지 발생시킴
2. 타이머 인터럽트
   • 선점형 스케줄러를 위해 필요
   • 하드웨어로부터 일정 시간마다 타이머 인터럽트를 운영체제에 알려줌
   • 일정 시간마다 인터럽트가 발생해서 scheduler가 이 타이밍을 보고 프로세스를 변경함
3. 입출력(IO) 인터럽트(여러가지)
   • 프린터, 키보드, 마우스, 저장매체 등
   • 각 디바이스 인터럽트가 해당 디바이스들이 실행되었다는 것을 알려줘야함.

주요 인터럽트

• 내부 인터럽트
  • 주로 프로그램 내부에서 잘못된 명령 또는 잘못된 데이터 사용 시 발생
  • 프로그램 내부에서 진행되는 것 내부에 있는 특정 코드를 실행하다가 발생하는 인터럽트
    • 0으로 나눴을 때
    • C언어 포인트(데이터의 주소)가 주소를 잘 못 지칭해서 프로그램이 다운됨.
    • 사용자 모드에서 허영되지 않은 명령 또는 공간 접근 시
    • 계싼 결과가 Overflow/Underflow 날 때
      • int(32bit) : unsigned(부호x-32bit), signed(부호-31bit 부호 1bit)
      • 위와 같은 자료형들의 계싼들이 int의 한도를 넘어설 때(32bit) 사용하는 인터럽트
• 외부 인터럽트
  • 주로 하드웨어에서 발생되는 이벤트(프로그램 외부)
    • 전원 이상
    • 기계 문제
    • 키보드 등 IO 관련 이벤트
    • Timer 이벤트

인터럽트 종류

• 내부 인터럽트 : 프로그램 내부에서 발생하므로, 소프트웨어 인터럽트라고 함
• 외부 인터럽트 : 하드웨어에서 발생하므로, 하드웨어 인터럽트라고도 함.

timer 인터럽트는 외부 인터럽트인가? cpu한테 매우 중요한 것 같은데…. 동작 원리가 뭘까

인터럽트

시스템 콜 인터럽트

• 시스템콜 실행을 위해서는 강제로 코드에 인터럽트 명령을 넣어, CPU에게 실행시켜야 한다.
• 시스템 콜 실제 코드
  • eax레지스터에 시스템 콜 번호를 넣고,
    • 여기서 각각의 시스템 콜 함수에는 번호가 있다.
  • ebx 레지스터에는 시스템 콜에 해당하는 인자값을 넣고(open()을 예를 들면 ‘data.tx’, 가티 등등 인자)
  • 소프트웨어 인터럽트 명령을 호출하면서 0x80값을 넘겨줌

    mov eax, 1 // 시스템콜 번호
    mov ebx, 0 // 시스템콜 인자 
    int 0x80 // 소프트웨어 인터럽트 명령
         // 0x80 == 인터럽트 번호(시스템콜 0x80)
    // 위 코드에서 int는 오퍼레이션 코드(op-code)로
    // CPU에서 실행될 때 연산(load, store, load 등)을 지정
    

인터럽트와 시스템 콜(고급, 위와 연결)

• 시스템콜 인터럽트 명령을 호출하면서 0x80값을 넘겨줌
  • CPU는 사용자 모드를 커널 모드로 바꿔줌(int(op code)가 바꿔주는 역할을 함)
  • IDT(Interrupt Descriptor Table)에서 0x80에 해당하는 주소(함수)를 찾아서 실행함
    • IDT는 인터럽트 번호가 있고 각각 매칭되는 주소(코드)가 매칭되어 있음. 여기서 0x80에 해당하는 주소를 찾아서 매칭되는 system_call()을 실행시킴 (부연 설명이기에 밑에줄과 연결되지 않음. 그냥 참고)
  • System_call() 함수에서 eax로부터 시스템 콜 번호를 찾아서, 해당 번호에 맞는 시스템 콜 함수로 이동
  • 해당 시스템콜 함수를 실행시킨 후, 다시 커널 모드에서 사용자 모드로 변경하고, 다시 해당 프로세스 다음 코드 실행(pc가 다음 코드를 실행)

사용자/커널 모드와 프로세스, 인터럽트

• 사용자 모드와 커널 모드를 굉장히 많은 횟수로 왓다갓다 함.
• 심지어 일정 주기마다 실행되는 timer 인터럽트 때문이라도 왔다갔따 함.

인터럽트와 IDT

• 인터럽트는 미리 정의되어 각각 번호와 실행 코드를 가리키는 주소가 기록되어 잇음
  • 모든 이벤트들(키보드 마우스 등등) 다 번호로 가지고 잇음
  • 각 번호에 따라 실행 코드도 다르게 되어있음.
  • 어디에? IDT(Interrupt Descriptor Table)에 기록
    • 이벤트 번호 : 실행코드의 주소(함수가 저장되어 있는 코드의 주소))
  • 언제? 컴퓨터 부팅 시 운영체제가 기록
    • 인터럽트가 걸리면 IDT에 가서 주소에 맞는 코드를 실행
  • 어떤 코드? 운영체제 내부코드
    • 커널모드/커널영역(커널모드에서 실행되는 코드들이 모여있는 특정 메모리 공간)

인터럽트와 IDT(다시 예를 보면)

• 항상 인터럽트 발생 시, IDT를 확인
• 시스템콜 인터럽트 명령은 0x80 번호가 미리 정의
• 인터럽트 0x80에 해당하는 운영체제 코드는 system_call()이라는 함수
• 즉, IDT에는 ox80 -> system_call()와 같은 정보가 기록되어 있음.

인터럽트와 IDT(리눅스 예)

• 0 ~ 31: 예외상황 인터럽트(일부는 정의안된 채로 남겨져 있음)
  • 내부 인터럽트/소프트웨어 인터럽트
• 32 ~ 47 : 하드웨어 인터럽트(주변장치 종류/ 갯수에 따라 변경 가능)
• 128 : 시스템 콜(== 0x80)

이터럽트와 프로세스

1. 프로세스 실행 중 인터럽트 발생
2. 현 프로세스 실행 중단
3. IDT에 가서 해당 함수를 실행(사용자모드 -> 커널모드)
4. 인터럽트 처리 함수 실행(운영체제)
5. 현 프로세스 재실행

선점형 스케쥴러 구현 예

• 수시로 타이머 인터럽트 실행
  • 운영체제가 타이머 인터럽트 발생 횟수를 기억해서 5번 타이머 인터럽트 발생하면, 현태 프로세스를 다른 프로세스로 바꿔준다.

정리

프로세스와 컨텍스트 스위칭

• 컨텍스트 스위칭
  • A프로세스가 스케쥴러에 의해 B프로세스로 바뀔 때 바뀌는 메커니즘음
  • 프로세스 구조를 알아야 이해할 수 있음
  • 프로그램을 작성할 때 실제 실행파일의 구조를 알아야하는 경우, 디버깅을 할 때 깊게 디버깅을 할 때 필요함(프로세스 구조 중요!)

프로세스 구조 deep dive

프로세스와 컨텍스트 스위칭

컴파일이 된다는 것은 컴퓨터가 이해할 수 있는 0과 1의 기계언어로 된다는 뜻(== binary 파일) 변수 선언 :

• 프로세스 구조는 몇 가지 영역으로 나뉨
  • Code 영역 : 컴파일된 소스코드가 저장
  • Data 영역 : 변수를 넣어놓는 공간. 전체 컴파일할 때 어느 변수를 선언해야하는지 data영역에 저장
  • Stack 영역 :
  • Heap 영역 : 동적인 메모리 공간이 필요할 때 생성(C언어에 malloc()함수)

프로세스와 컴텍스트 스위칭

프로세스(process)는 일반적으로 어떻게 구성되어 있을까?

• Text(CODE) : 코드
• data : 변수/초기화된 데이터
• stack : 임시 데이터(함수 호출, 로컬 변수 등)
• heap : 코드에서 동적으로 만들어지는 데이터

PC(Program Counter) + SP(Stack Pointer)

• 레지스터 종류 중 하나

스택(stack) 복습

• 스택 프레임(프로세스 구조 중 하나)
• 이 자료구조는 뭐에 쓰이고 왜 강조해서 배웠나?

실제 동작 원리를 엑셀로 설명했음. 영상을 다시 보는 것을 추천함

프로세스와 스케줄러의 이해 -13. 프로세스 구조와 스택 오버플로우

프로세스 구조 : stack, heap, Data(BSS, DATA), TEXT(CODE)

DATA를 BSS와 DATA로 분리

• DATA는 전역변수를 저장하는 부분
• DATA는 2가지 영역으로 나눠짐
  • BSS : 초기값이 없는 전역변수
    • C언어에서 변수 선언 안 한 변수
  • DATA : 초기값이 있는 전역변수
    • C언어에서 변수 선언을 한 변수
• 지역변수 : STack에 들어감

스택 오버플로우

• 주로 해커들의 공격에 활용되었음

프로세스와 컨텍스트 스위칭

PC와 SP에 주목하자 PC(Programm Counter) + SP(Stack Pointer)

메커니즘을 이해해보자!

• A프로세스가 실행되려면 스케줄러에 넣어지게 되고, 스케줄러는 A프로세스를 runing으로 해주고, CPU에 실행됨.
• 어느 순간 스케줄러가 A프로세스를 중지하고 B프로세스로 바꾸는 것 -> 컨텍스트 스위칭!!

bss : 초기값이 없는 변수 data : 초기값이 있느 변수

스위칭 매커니즘은 PC와 SP가 포인트!

1. A프로세스가 코드를 실행하고 있음
2. PC와 SP에 각각 주소들이 채워지면서 작동을 하는데, 중간에 스케쥴러에 의해 B프로세스로 전환
   • 이 때 PC와 SP값은 PCB에 저장이 되고 B프로세스로 전환됨.
3. B프로세스가 진행될 때도 PC와 SP가 채워지면서 진행됨.
4. 이후에 B프로세스도 스케줄러에 의해 A프로세스로 전환
   • 맨 처음에는 A프로세스에 있는 PCB를 확인하고 PC와 SP를 각각 다시 덮어씌움(PC와 SP는 CPU에 있겠찌? 레지스터니까)
   • 물론 이 때도 B프로세스의 PC와 SP도 PCB에 저장
   • 이후에 기존에 A프로세스에 있는 stack에 의해 진행
5. 또 바뀌게 되면 실행중이던 A프로세스에 있는 PCB에 PC와 ST를 저장함
6. 그리고 바꾸고자 하는 B프로세스에 PCB를 확인하고 CPU에 있는 PC와 ST를 덮어씌움

위 매커니즘 핵심

• PC와 SP값을 자기 상태를 나타내고 있는(각각의 프로세스마다 있는) PCB라는 저장공간에 저장하고, 다시 실행할 때는 CPU에 해당 값을 업데이트(덮어씌움)하고 실행

PCB(Process COntrol Block)

• Process Context Block 이라고도 함
• 안에 구성 요소
  • Process ID
  • Register 값(PC, SP 등)
  • Scheduling Info(Process State)
    • 현재 프로세스의 상태(ready, block, running 등)
  • Memory Info(메모리 사이즈 limit, 전체 프로세스의 사이즈 등)

정리

• 프로세스 구조
  • Stack, Heap, data(BSS, DATA), Text(code)
• PCB » 컨텍스트 스위칭 - 이게 시간이 오래 걸리면 안 되기 때문에 어셈블리어로 작성되어 있음
  • 프로세스 상태 정보 - PC, SP, 메모리, 스케쥴링 정보 등

프로세스와 컨텍스트 스위칭

Context Swithching(문맥 교환)

CPU에 실행할 프로세스를 교체하는 기술

1. 실행 중지할 프로세스 정보(CPU에 있는 PC/SP 값-레지스트값)를 해당 프로세스의 PCB에 업데이트해서, 메인 메모리에 저장
2. 다음 실행할 프로세스 정보를 메인 메모리에 있는 해당 PCB 정보(CPU에 있는 PC/SP 레지스터)를 CPU에 넣고 실행
   • 디스패치(dispatch) : ready 상태의 프로세스를 running 상태로 바꾸는 것

컨텍스트 스위칭 자체도 결국 ‘실행코드’임

프로세스와 컨텍스트 스위칭

• 이것도 실행 코드로임
• 오버헤드를 줄여야함
  • 컨텍스트 스위칭도 결국 코드를 통해 실행하는 것이기 때문에 프로세스 전환 간 그 사이에 실행시간이 오래 걸리면 좋지 않다. 추가적으로 드는 시간을 줄여야함
  • 결과적으로 두 프로세스를 전환하는데 추가 시간이 걸림
  • 하지만 컨텍스트 스위칭은 정말 빈번하게 많이 발생하기 떄문에 매우 빠른 코드를 작성해야함

    리눅스의 경우 어셈블리어로 작성되어 있음 -> 빠르게 하기 위해

컴파일러

• 초기 컴퓨터 프로그램들은 어셈블리어로 작성
  • 서로 다른 CPU 아키텍터가 등잘할 때마다 매번 거기에 맞는 프로그램을 작성해야함(이식성 저하)
  • 어셈블리어로는 프로그램 작성 속도가 매우 떨어짐
  • 대신 실행 속도는 매우 빠름(그래서 리눅스는 이식성은 떨어지지면 속도가 빠름)
• 컴파일러 등장
  • CPU 아키텍처에 따라서는 컴파일러 프로그램만 만들면 됨. 기존 코드 재작성 불필요
  • 그러나, 어셈블리어로 작성한 코드보다는 속도가 떨어질 수 있음

정리

• 프로세스 구조(Stack, Heap, DATA(BSS, DATA), Text(code))
• PCB(프로세스 상태 정보 - PC, ST, 메모리, 스케쥴링 정보 등)
• 컨텍스트 스위칭(프로세스 상태 정보를 PCB로부터 CPU에 로드하고, 실행)

프로세스간 커뮤니케이션(InterProcess Communication)

프로세스간에는 직접적으로 커뮤니케이션을 할 수 잇는 방법이 없음

• 그래서 InterProcess Communication 방법을 사용해라!

커뮤니케이션이 왜 필요한가?

• 프로세스간에 원칙적으로 대화 불가
• 프로세스들이 서로의 공간을 쉽게 접근한다면?
  • 프로세스 데이터/코드가 바뀔 수 있음
• 남의 프로세스 주소에 접근할 수 잇는 방법이 없음

  프로세스는 다른 프로세스의 공간을 접근할 수 없다. 직접적으로!!

프로세스간 통신이 필요한 이유

• 요즘에는 CPU에는 코어가 여러개가 있음.
• 각각의 코어에 프로세스를 실행할 수 있또록 운영체제가 지원한다면 여러 작업을 동시에 작업할 수 있어서 실행속도가 빨라짐
• 동시에 실행된 결과들을 특정 프로세스가 다 모아서 정리해줄 필요가 있다.
• 그래서 서로간의 통신이 필요함

fork() 시스템콜

• fork() 함수로 프로세스 자신을 복사해서 새로운 프로세스를 만들 수 있음
  • 처음 주체가 부모 프로세스, 복제된 놈들이 자식 프로세스
• 프로세스를 fork() 해서 여러 프로세스를 동시에 실행시킬 수 있음
  • CPU 안에 코어가 여러개가 있기 때문에 각 프로세스를 각 코어에 동시 실행 가능(병렬처리)

가볍게 생각하기

여러 프로세스 동시 실행하기 예

• 1~10000까지 더하기
  • fork() 함수로 10개의 프로세스를 만들어서 각각 천 단위로 더함
  • 각각 더한 값을 모두 합하면, 더 빠르게 동작 가능

    이떄 각 프로세스가 더한 값을 수집해야 하기 때문에 프로세스 통신이 필요함

웹서버 예

• 웹서버는 여러개의 컴퓨터가 있는 것
  • 여러 요청에 대해 동시에 처리 가능
  • 각각의 요청을 얼마나 빠르게 요청하냐가 성능의 지표
  • 웹 요청이 올 때마다 프로세스를 만들어서 각각 cpu 코어를 사용하면 빠르게 처리 가능(fork함수)

    CPU 병렬 처리가 가능하면 더 빠르게 대응 가능 단, 각 프로세스 제어 및 상태 정보 교환을 위해 프로세스 간 통신이 필요

파일을 사용한 커뮤니케이션

• 저장매체는 공유가 가능하다는 원리를 이용한 방법
• 간단히 다른 프로세스에 전달할 내용을 파일에 쓰고, 다른 프로세스가 해당 파일을 읽으면 됨
• 천 단위로 계산을 하는 값들을 모두 한 파일에 적고 해당 파일을 읽어 다 합치면 만까지의 계산이 가능한 예시

파일 사용한 커뮤니케이션 단점

• 프로세스A가 data.txt에 업데이트를 해도 프로세스B가 업데이트 사실을 알 수 있는 방법이 없음(실시간 전달 어려움)
  • 물론 반복문을 통해 수시로 확인하면 가능 하지만, 그건 현실적으로 너무 손해
  • 또한 프로세스가 해당 파일을 읽어야하는데, 실시간으로 읽고만 있을 순 없으니..
• 저장매체에 갔따오는 시간이 너무 오래 걸림
• 시스템 콜 써서 어저구 저꺼구 그 과정을 다 거쳐야함.

프로세스간의 통신

실제 프로세스 : 리눅스 예

• 프로세스간 공간은 완전히 분리되어 있다.
• 예시에는 0~4GB를 사용한다고 하는데, 이건 ‘가상주소’를 말한다.
  • 실제 물리 메모리에 있는 공간과는 다른 개념
  • 가상 주소를 물리 주소로 바꾸는 방법이 있음
  • 3~4gb는 운영체제가 들어가는 공간, 0~3gb는 실제 프로그램이 사용하는 공간
• 심지어 한 프로세스 내에 0~4gb 공간 중에 실제 프로그램이 있는 공간은 운영체제 공간에 접근 불가(사용자와 커널 공간 분리)
  • 프로텍트 링과 관련이 있음. 커널을 보호함
• 아주 극히 일부만 물리 메모리에 들어감
• 다만 kernel공간은 공유한다.
  • 실제 물리메모리에 들어갈 때는 공유할 수 있는 시스템으로 되어 있음
  • 매번 os부분을 매 프로세스마다 같이 사용하면 낭비
  • 3~4gb는 OS부분, 프로세스 간 kernel부분을 공유
  • 구체적으로는 가상 공간 단원에서 배움

다양한 IPC 기법

1. file 사용
   • 저장매체에 갔다오기 때문에 시간 오래 걸림 - 이 밑에 나오는 기법들은 결과적으로 kernel공간은 물리 메모리에 있어서 저장매체보다 access시간이 짧고, 프로세스가 공유 가능하다.

     2번부터 모두 Kernel공간을 사용한다는 것이 핵심! 또한 전부 함수임

2. message Queue
3. Shared Memory
4. Pipe
5. Signal
6. Semaphore
7. Socket 등

정리

• 여러 프로세스 동시 실행을 통한 성능 개선, 복잡한 프로그램을 위해 프로세스간 통신 필요
• 프로세스간 공간이 완전 분리
• 프로세스간 통신을 위한 특별한 기법 필요
  • IPC(InterProcess communication)
• 대부분의 IPC 기법은 결국 커널 공간을 활용하는 것임
  • 이유 : 커널 공간은 공유하기 때문에

프로세스간 커뮤니케이션

각 IPC기법 개념 이해하기

커널 공간을 공유하는 개념을 이용한 방법!!(2번~)

pipe(파이프)

• 기본 파이프는 단뱡향 통신
• fork()로 자식 프로세스를 만들었을 때, 부모와 자식 간의 통신

  질문 부모 프로세스에서 fd[1]으로 write를 했고, 자식 프로세스에서 fd[0]로 read를 했는데, 두 fd는 메모리 주소가 다른데 어떻게 통신이 됐다는 거지?

  ---

  내 생각 부모 프로세스에서 fd[1]로 write할 때 결국 fd[0]에도 해당 내용이 쓰인 것이고, 따라서 자식 프로세스에서 fd[0]을 통해 해당 내용을 읽은 것?

메세지 큐(message queue)

• 큐니까 기본은 FIFO 정책으로 데이터 전송
• A프로세스가 메세지 큐에 메세지를 보내면, 차례대로 B프로세스가 읽음.

파이프와 메세지 큐

• 메세지 큐는 fork할 필요 없고 어느 프로세스간에라도 데이터 송수신 가능(부모 자식 관계 필요없음)
  • key값만 알면 됨.
• 메세지 큐는 각 프로세스에 각각 하나씩 만들어서 서로 통신할 수 있도록 만들 수 있음
• 파이프는 단방향만 가능하지만 메세지 큐는 양방향 가능

IPC기법과 커널 모드

• pipe, message queue는 모두 kernel 공간의 메모리를 사용한다.
• 메모리 공간도 kernel/user로 구분된다. 가상메모리에서 이해 가능

공유 메모리(Shared Momery)

• 노골적으로 kernel 공간에 메모리 공간을 만들고, 해당 공간을 변수처럼 쓰는 방식
• 메세지 큐처럼 FIFO방식이 아니라, 해당 메모리 주소를 마치 변수처럼 접근하는 방식
• 공유메모리 key를 가지고 여러 프로세스가 접근 가능

정리

• 주요 IPC 기법
  • pipe : 단방향 통신, 부모 자식
  • message queue : 큐를 만들어서 양방향, key값
  • shared memory : 메모리 공간을 만들어서 주소값을 이용해 어느 프로세스도 공유 가능(변수처럼 사용)
• 모두 커널 공간을 활용해서 프로세스간 데이터 공유

프로세스간 커뮤니케이션

각 IPC기법 개념 이해하기(signal과 socket)

IPC기법이지만, 이외에도 많이 사용되는 두 기술

• 시그널(signal)
• 소켓(sockey)

  다른 목적으로 만들어졌지만, IPC기법으로도 사용할 수 있음

시그널(signal) == 이벤트

• 유닉스에서 30년 이상 사용된 전통적인 기법
• 커널 또는 프로세스에 다른 프로세스에 어떤 이벤트가 발생되었는지를 알려주는 기법
• 미리 정의가 된 이벤트(약 64개? 기본 운영체제 - linux)
  • SIGKILL : 프로세스를 죽여라
  • SIGALARM : 알람을 발생
  • SIGSTP : 프로세스를 멈춰라
  • SIGCONT : 멈춰진 프로세스를 실행해라
  • SIGINT : 프로세스에 인터럽트를 보내서 프로세스를 죽여라
• 프로세스 관련 코드에 관련 시그널 핸들러를 등록해서, 해당 시그널 처리 실행
  • 시그널 무시
  • 시그널 블록(블록을 푸는 순간, 프로세스에 해당 시그널 전달)
  • 등록된 시그널 핸들러로 특정 동작 수행
  • 등록된 시그널 핸들러가 없다면, 커널에서 기본 동작 수행

시그널과 프로세스

• PCB에 해당 프로세스가 블록 또는 처리해야하는 시스널 관련 정보 관리
• PCB에는 시그널을 관리하는 자료구조가 있음
  • 커널이든 어디든 시그널이 오면
    • ‘시그널이 왔다’라고 알리는 자료구조도 있고,
    • 처리를 기다리는 시그널을 표현해주는 자료구조도 있고
    • BLOCK된 시그널이 뭔지 알려주는 자료구조
    • 각각의 시그널에 대해 어떤 동작을 해야할지 정의가 되어 있는 자료구조도 있음
• **커널모드에서 사용자모드로 전환 시 시그널 처리

소켓(Socket)

• 소켓은 네트워크 통신을 위한 기술
• 기본적으로 클라이언트와 서버 등 두개의 다른 컴퓨터간의 네트워크 통신을 위한 기술

프로세스 총정리와 프로그램 성능 개선 방법의 이해

인터럽트

0.01초마다 timer 인터럽트를 실행시키는 경우

1. CPU는 사용자 모드를 커널 모드로 바꿈
2. IDT(Interrupt Descriptor Table)에서 0x80에 해당하는 주소(함수)를 찾아서 실행
   • timer 인터럽트 번호 : 함수 주소 -> 함수 실행
3. system_call() 함수에서 eax로부터 시스템 콜 번호를 찾아서, 해당 번호에 맞는 시세틈콜 할수로 이동
4. 해당 시스템콜 함수 실행 후, 다시 커널 모드에서 사용자 모드로 변경하고, 다시 해당 프로세스 다음 코드 진행

컨텍스트 스위칭

• 프로세스1 PC/ST값을 PCB에 저장, 이후 PCB 정보를 메인메모리에 저장
• 프로세스2 PCB 정보를 메인메모리에서 로드

Thread(스레드)

Thread 개념

• 응용 프로그래머(C언어, python언어 등)
• 시스템 프로그래머(API, 라이브러리, 플랫폼, 쉘, 컴파일러, OS)
• 하드웨어 개발자(HW)

Trhead(스레드)

• Light Weight Process 라고도 함
  • 프로세스처럼 작동을 하지만 프로세스보다 작다
• 프로세스
  • 프로세스 간에는 각 프로세스의 데이터 접근 불가 -> IPC
• 스레드
  • 하나의 프로세스에 여러개의 스레드 생성 가능
  • 스레드들은 동시에 실행 가능
  • 프로세스 안에 있으므로, 프로세스의 데이터를 모두 접근 가능

    한 프로세스 안에서 여러개의 스레드 생성 가능, 변수 접근하듯이 프로세스 데이터를 사용할 수 있음.

동작 원리

• 원래 프로세스에는 stack heap bss data code 등의 영역이 있고 이것을 PC와 SP가 동작을 했었는데,
• 스레드는 stack에 잇는 하나의 함수라고 생각하면 됨.
• stack 안에 여러개의 thread stack이 잇고, 각각 스레드 스택에는 pc와 sp가 있다.
• heap, bss data code 등을 다 공유한다.
  • IPC를 사용하지 않고 데이터 공유 가능
• 단지 stack 영역만 공유함
• 사실은 스택과 힙 사이에 스레드 공간이 별도로 있음. 각각에 대해 sp와 pc를 가지고 있음

스레드는 각기 실행이 가능한 stack 존재

• 한 프로세스 안에 스레드별로 register, stack 각각 따로 잇음
• code 및 데이터 공유되니까 동시에 실행할 수 있다.
• thread stack 영역만 공유를 하고 있음

멀티 프로세싱과 thread

멀티 태스킹 vs 멀티 프로세싱

멀티 태스킹

• 하나의 cpu에 여러가지 프로세스가 있을 때 수시로 몇 초마다다 cpu의 실행을 바꿔가면서 결과적으로 사람이 보기에는 모든 프로세스가 동시에 실행되는 것처럼 하는 것
• 하나의 CPU에 여러 process

멀티 프로세싱

• 하나의 process를 여러개의 cpu로 실행시켜서 실행속도를 높이는 것
  • 여러개의 thread를 만들면 가능
• 여러개의 process를 여러 cpu에 조금씩 나눠서 병렬실행하는 것
  • 근데 이건 왜 하는거지? 그냥 각각 cpu가 하면 되는데…

최근에 나오는 CPU는 멀티 코어(여러개의 계산기)로 나오기 때문에 thread는 싫맹속도를 높이는데 굉장한 역할을 한다. 멀티코어의 활용도를 높임

멀티 프로세스와 멀티 태스킹

지금 우리가 쓰는 윈도우는 여러개의 프로세스를 여러개의 스레드를 사용할 수 있는 기능을 제공한다;

• 하지만 이러한 기능은 굉장히 복잡한다. 근데 요즘은 다 이런 기능을 씀.

스레드 장,단점

장점

1. 사용자에 대한 응답성 향상

• 한 프로세스가 2가지 일을 하는 프로세스라고 생각해보자.
  • 1부터 100만까지 덧셈 / IPC를 이용해 더한 수 전달
• 위의 경우 더한 수를 전달하기 위해서는 100만까지의 덧셈을 기다려야함
• 하지만 100만까지 더하는 for구문 중 중간중간 결과를 알고 싶을 떄 또 다른 스레드를 이용하면 전체다 다 실행되지 않고도 보여줄 수 있음
• 그래서 응답속도가 줄어들기 때문에 ‘사용자에 대한 응답성 향상’
• 또 다른 예시로 웹서버로 클라이언트가 요청을 할 때 여러개의 스레드를 이용해서 각각 요청을 처리하면 응답속도 빠름

2. 자원 공유 효율

• 각 프로세스는 IPC를 통해 서로 공유를 하는데, 한 프로세스 안에서는 여러개의 스레드가 해당 프로세스의 데이터를 고유하고 있기 때문에 효율적임
• IPC기법과 같은 자원굥유 기능을 추가하지 않아도 됨

여러개의 프로세스를 만들 경우 각 프로세스가 차지하면 메모리만큼 자원이 소모되는데, 한 프로세스 안에서 여러개의 스레드를 만들면 한 프로세스에 필요한 메모리만큼만 필요하기 때문에 자원 효율에도 효과가 있음(공유 효과도 있지만!)

3. 작업이 분리되어 코드가 간결

• 물론 코드를 작성하기 나름임
• 실제 스레드를 구현할 때 스레드1 함수, 스레드2 함수 처럼 함수로 만들어서 각각 동작을 함. 마치 여러개의 함수로 나눠서 실행하는 것처럼 보임
• 그래서 작업(코드)가 분리된 것처럼 보이기 때문에 장점

단점

1. 스레드 중 하나만 문제가 생겨도 전체 프로세스 영향

• 멀티 프로세스와 멀티 스레드를 비교하면
• 멀티 프로세스의 경우 하나의 프로세스를 하기 위해 여러개의 프로세스를 사용하는데, 그 중 한 개가 고장나도 나머지 프로세스들이 잘 작동함
  • 모든 프로세스들은 분리가 되어있기 때문에 가능
• 하지만 멀티 스레드의 경우 하나의 스레드에 문제가 생기면 해당 프로세스 전체가 멈춤
  • 다 한 프로세스 안에 붙어있기 때문에..

2. 스레드도 결국 Context Swithching을 한다!

• 스레드를 많이 생성하면 context switching이 많이 일어나 성능이 저하됨.
• 예를 들어 LINUX OS의 경우 thread와 process를 같이 다룸

  스레드를 많이 생성하면, 모든 스레드를 스케쥴링해야 하고, Context Swithcing이 빈번히 일어남

Thread vs Process

• 프로세스는 독립, 스레드는 프로세스의 서브셋
• 프로세스는 각 독립자원, 스레드는 프로세스 자원 공유
• 프로세스는 자신만의 주소영역 있고, 스레드는 주소영역 공유
• 프로세스간에는 IPC기법, 스레드는 필요 없음

  스레드는 자원을 공유해야하는데, 그거를 할 때 부가적인 처리를 해야함. 동기화 문제

PThread

• POSIX 스레드에서 인터페이스(함수, api)를 구현해놓았음
  • Thread 관련 표준 API
• 파이썬은 윗단에서 별도 라이브러리를 이용함
  • 근데 이것도 결국 아래로 내려오면 이러한 함수를 이용함

정리

• Thread는 프로세스와 달리 스레드간 자원 공유
• 스레드 장점
  • CPU 활용도 놈고
  • 성능 개선
  • 응답성 향상
  • 자원 굥유 효율(IPC 필요 없음)
• 스레드 단점
  • 하나의 스레드가 문제가 생기면 프로세스 전체에 악영향
  • 여러 스레드 생성 시 성능 저하

동기화(Synchronization) 이슈 예제

• 여러개의 스레드는 실행순서가 정해져있지 않음
• 스케쥴러가 그때그때 다르게 스레드를 실행시킴
• if나 for문을 쓸 때 프로세스 내에 저장되어 있는 데이터(변수)를 스레드가 가져다 쓰는데, 스레드간의 실행순서가 꼬이게 되면 비정상 동작을 하는 경우가 있는데, 이것이 동기화 문제!!

  데이터를 읽고 쓰는 걸 여러 스레드가 동시에 할 수 있기 때문에 발생함. 따라서 스레드 관리가 필요함 동기화 문제가 생기면 디버깅도 쉽지 않다.

import threading

g_count = 0

def thread_main():
  global g_count    # 이거 없이 밑에 코드를 실행하면
  for i in range(10000):
    g_count += 1 # g_count라는 지역변수 선언 안 햇는데 어떻게 연산이 가능하냐? 라고 경고가 뜸 그래서 전역 변수 g_count를 설정해줌

threads = []

for i in range(50):
  th = threading.Thread(target=thread_main)
  threads.append(th)

for th in threads:
  th.start()

for th in threads:
  th.join()

print('g_count = ', g_count)

위 코드 해석

• 1을 1만 번 더하는 코드를 50개의 스레드를 통해 동시에 진행하면 50만이 동시에 나옴
• 1만 번 더하는 경우 스케쥴러가 context switching을 하기 전에 진행이 완료되기 때문에

동기화 문제

• 하지만 만약 100만 번 더하는 코드를 50개의 스레드로 동시에 진행하면 context switching을 해야하는 시간이 됐는데도 불구하고 아직 특정 스레드의 연산이 끝나지 않아는 문제가 발생
• 그러면 해당 스레드는 연산이 끝나지 않은 상태로 연산 결과가 변수에 저장되지 않고 다른 스레드로 해당 변수가 넘어감
• 근데 그 스레드 마저 중간에 끝내지 못하고 다음 스레드로 넘어가는데, 하필 그 타이밍이 첫 번째 스레드의 결과를 저장하는 코드를 수행하는 순서야.

  말로 설명하니까 힘들다. 그냥 사진 참고

동기화 문제 해결방법

Mutual exclusion

• 스케쥴러에 의해 일정 시간이 지나면 context swithch이 발생한텐데, 해당 동작을 강제로 제어해주는 방법
• 죽, 연산이 끝날때까지 기다렸다가 스위칭 실시

Thread(스레드)

동기화(synchronization)와 세마포어

• Mutual exclusion(상호 배제)
• 쓰레드는 프로세스의 모든 데이터에 접근 가능
  • 여러 스레드가 변경하는 공유 변수에 대해 exclusive access가 필요
  • 어느 한 쓰레드가 공유 변수를 갱신하는 동안 다른 쓰레드가 접근하지 못하도록 막는 방법
  • lock.acquire()와 lock.release()

    어디로 접근을 못 하게하냐? 즉, 쓰레드가 일을 하는 장소를 임계 구역(Sritical Section이라고 함.)

Mutex와 세마포어(Semaphore)

• Mutial Exclusion을 다른 말로 LOCKING 메커니즘이라고도 함
• 해당 메커니즘에는 2가지 방법이 있음
  1. Mutex(Binary Semaphore)
     • 임계구역에 하나의 스레드만 입자 가능
  2. Semaphore
     • 임계구역에 여러 스레드가 들어감
     • Counter 변수를 두어 동시에 리소스에 접근할 수 있는 허용 가능한 쓰레드의 수를 제어

함수를 이용해 세마포어 표현

슈도코드(pseudocode)로 로직만 표현을 함

• p : 검사(임계영역 들어갈 때)
• V : 증가(임계영역에서 나올 때)
• S : 세마포어의 값(임계영역에 입장 가능한 쓰레드의 수)

P(S) : wait(S) {
              while S <= 0 //대기
              ;
    S--;
}

V(S) : signal(S){
  S++;
}

• while구문에서는 해당 임계구역에 자리가 빌 때까지 반복수행
• V()의 경우 해당 임계구역에서 특정 작업이 끝나면 스레드가 나오면서 자리를 비워주는 것

세마포어(Semaphore) - 바쁜 대기

• wait(S)는 S가 0이라면, 임계영역에 들어가기 위해 반복 수행
  • 바쁘대기(Busy waiting)
• 해당 while부분이 계속 돈다는 건 CPU를 계속 실행한다는 건데, 성능이 저하되는데 이 방법밖에 없어서 참 아쉽다.
• 코드를 중간에 멈추게 하는 방법이 없기 떄문에

위 바쁜대기 해결 방법(loop 계속 도는 문제)

대기큐를 이용하는 방법

운영체제 기술로 보안 - 대기 큐

• s가 음수일 경우(임계영역에 빈 자리가 없을 경우), 바쁜 대기 대신 대기큐에 넣는다
• 스케줄러는 ready, running, block상태가 있는데 여기서 block()상태로 넣어줘서 나중에 꺼내다 쓰는 방식
• wakeup()함수를 이용해 대기큐에 있는 프로세스를 재실행 이건 운영체제를 뜯어 고쳐야함. 운영체제에서 제공하는 시스템콜을 사용해야한다.

주요 세마포어 함수(POSIX 세마포어)

• sem_open() : 세마포어를 생성
• sem_wati() : 임계영역 접근 전, 세마포어를 잠그고, 세마포어가 잠겨있다면, 풀릴 때까지 대기
• sem_post() : 공유자원에 대한 접근이 끝났을 때 세마포어 잠금을 해제한다.

Thread(쓰레드)

교착생태(Deadlock)와 기아상태(Starvation)

• 임계영역에 쓰레드가 접근하면 나머지 쓰레드가 기다리고 있는데, 순서를 잘못 정하면 어떤 쓰레드도 작동을 안 하거나 특정 쓰레드는 아예 실행을 못 하는 문제가 발생

교착상태(deadlock)이란?

• 무한대기상태 : 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에, 다음 단계로 진행하지 못함
• 쉽게 둘 다 대기하고 있음….아무것도 실행 못 함

  예시

• A프로세스가 a자원을 사용하고 있따가 b자원을 요청함
• B프로세스는 b자원을 사용하고 있다가 a자원을 요청함
• B프로세스가 요청한 a자원은 이미 A프로세스가 사용하고 있음
• 반대로 A프로세스가 요청한 b자원은 B프로세스가 사용하고 있음
• 동기화에 의해 서로가 상대방이 자원사용을 끝마칠때까지 기다리고 있음.
• 무한 반복….

교착상태 해결방법

• 교착상태에 빠지는 4가지 조건이 있는데, 그 중 조건을 충족하지 않도록 조치를 한다!

기아상태(Starvation)

• 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태
• 예를 들어 1순위인 50개의 쓰레드가 있을 때 49개는 우선순위가 1번이고, 나머지 1개가 우선순위가 2번이다.
• 위 경우에서 10번을 실행하는데, 스케쥴링을 할 때 우선순위로 실행을 한다고 했을 떄 우선순위가 2번인 쓰레드는 절대로 실행하지 못함 ㅠㅠ

교착상태 vs 기아상태

• 교착상태는 여러 프로세스가 동일한 자원 점유를 요청할 때 발생
• 기아상태는 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때, 특정 프로세스는 영원히 자원 할당이 안 되는 경우

기아상태 해결방법

• 우선순위 변경
  • 프로세스 우선순위 수시로 변경
  • 오래 기다린 프로세스의 우선순위를 높여줌
  • 요청 순서에 따라 처리하는 FIFO기반 요청큐 사용

가상 메모리(Virtual Memory System)

실제 각 프로세스마다 충분한 메모리를 할당하기에는 메모리 크기가 한계가 있음

• 예 : 리눅스는 하나의 프로세스가 4GB
• 통상 메모리는 8GB, 16GB
• 폰노이만 구조 기반이라 코드는 메모리에 반드시 있어야 함
• 이것만 보면 멀티 프로세싱은 불가능함..

적은 메모리에서 여러 프로세스를 할 수 있도록 메모리 구조를 가져갈까? 가상 메모리

CPU의 프로세스

• CPU가 모든 공간을 한 번에 참조해서 진행하지는 않는다.
• 한 줄 한 줄 메모리에서 cpu로 코드를 한 줄 한 줄 읽어서 실행한다.
• 특정 시간동안 특정 프로세스에서 참조하는 메모리 공간은 제한적이다.
• 프로세스는 4gb지만 지금 쓰는 공간만 메모리에 넣어주고 또 끝나면 빼주고
• 해당 프로세스가 진행되는 물리적 메모리 안의 공간의 주소만 알고 있으면 된다.

가상 메모리가 필요한 이유

• 여러 프로세스를 동시에 실행하는 시스템의 겨웅
  1. 메모리 용량 부족 이슈
  2. 프로세스 메모리 영역간에 침범 이슈

가상 메모리

• 가상 메모리의 기본 아이디어
  • 프로세스는 가상 주소를 사용, 실제 해당 주소를 읽고/쓸 때만 물리 주소로 변환 후 사용
  • virtual address(가상주소) : 프로세스가 참조하는 주소
  • physical address(물리 주소) : 실제 메모리 주소

가상 주소는 0~4GB지만, 물리 주소는 조금만 할당해서 필요할 때마다 가상 주소에서 참조해서 물리 주소에서 실행. 이 때 가상 -> 물리로 변환이 필요함

MMU(Memoery Management Unit)

• 가상 주소를 물리 주소로 빠르게 변환해주는 하드웨어 장치
• 가상 주소를 물리 주소로 변환할 때 시간이 걸린다.
• 변환이 자주 일어나면 그 만큼 시간이 오래 걸린다.
• 이러한 불필요한 시간을 짧게 하기 위해 MMU 칩을 사용한다.
• 가상 메모리는 하드웨어 지원도 필요하다

전체 프로세스를 한 번에 전부 참조하는 것이 아니라 일부분만 물리 주소에 넣는다. 이러한 동작이 원활하게 하기 위해서는 가상 주소를 물리 주소로 변환하는 메커니즘만 있으면 된다.

가상 메모리와 MMU의 관계

• CPU는 가상 메모리 주소를 참조해달라고 요청하고, 그 가상 메모리 주소가 어느 물리 주소에 있는지 MMU가 변환시켜서 해당 물리 메모리에 접근할 수 있도록 함
• 해당 데이터를 CPU에 전달한다.
• CPU가 가상 메모리 요청 -> MMU가 해당 가상 메모리가 물리 메모리의 어느 주소에 있는지 확인하고 변환

가상 메모리 메커니즘이 여러개인데, 대표적인 페이징 시스템에 대해 알아보자.

페이징 시스템

• 가상 메모리를 만들기 위해서는 여러 메커니짐으 있는데, 여기서는 페이징 시스템에 대해 알아보자.
• 가장 많이 사용됨.

페이징 시스템(Paging System)

• 하나의 프로세스에서 특정 시간동안 쓰는 메모리 영역은 일부임
• 그 일부를 메모리에 올려 놓자 -> 가상 메모리 컨셉
• 근데 어느 정도 사이즈만큼 올려줄까? 그것을 페이지단위로 다루겠다.

• 페이징(paging) 개념
  • 크기가 동일한 페이지가 가상 주소 공간과 이에 매칭하는 물리 주소 공간을 관리
  • 하드웨어 지원 필요
    • Ex. 인텔의 경우 intelx86(32bit) 4KB, 2MB, 1GB 등을 지원
• 리눅스는 4KB로 paging
• 페이지 번호를 기반을 ㅗ가상/물리 주소 매핑 정보를 기록/사용

실제 동작하는 예시

• 프로세스(4GB)의 PCB에 Page Table 구조체를 가리키는 주소가 들어가 있음
• Page Table에는 가상 주소와 물리 주소 매핑 정보

페이징 시스템 구조

• Page 또는 page Frame : 고정된 크기의 black(4KB)
• 각 페이지를 page1, page2 처럼 번호를 매김
• 만약 block단위에서 남는 가상 메모리가 있으면(예를 들어 4KB 짜르다가 마지막에 1KB가 남으면) 남는 메모리 + 공란 메모리까지 1page로 할당한다.
• paging system
  • 가상 주소 v = (p, d)
    • p : 가상 메모리 페이지
    • d : p안에서 참조하는 위치(변위)
• 32bit로 예를 들면 0~11bit까지는 변위가 들어가 있고,
• 12비트 이상은 페이지 변호가 들어가 있따.
• 따라서 page table의 맨 위에 있는 base주소랑 변위(베이스 주소랑 얼마나 떨어져잇는지)값만 알면 두 개를 더해서 원하는 page를 불러올 수 있음

프로세스가 4GB를 이용하는 이유

32bit로 표현할 수 잇끼 때문에 2^32

ddddddddddddd d d d

d d d d d d d d

d d d d d

d d d d d d

d d

d

d d d d d d

d

d d