운영체제 어떻게 공부했나?

• 운영체제
  • 폰 노이만 구조부터 라운드 로빈 스케쥴링까지 수업
  • 리눅스 시스템 구조 수업

내가 공부한 것

멀티 스레딩과 멀티 프로세싱의 차이

사용자 수준 스레드와 커널 수준 스레드

말 그대로 스레드의 구현 수준이 어디에 있느냐가 핵심으로 가장 큰 차이는
커널에서는 사용자 수준에서 구현 된 스레드의 존재를 알지 못한다는 것

• 커널 수준 스레드
  커널에서 프로세스 : 스레드의 1:1 관계를 가지고, 커널에서 관리되지만 사용자 수준으로 변환의 비용이 필요

• 사용자 수준 스레드
  커널에서 스레드의 존재를 모르기 때문에 I/O 사용 시에 문제가 있음.
  스레드의 스케쥴링을 사용자가 하기 때문에 I/O 프로세스 블록이 걸린다면 프로세스의 스레드는 모두 블로킹 됨

리눅스 프로세스 구조

프로세스들은 커널로부터 메모리 영역을 할당
stack은 동적 할당이 없는 로컬 데이터에 할당, stack overflow 발생가능
heap은 동적 할당 데이터에 할당, heap overflow 발생 가능
프로세스는 각각 PID를 가짐, 각 프로세스가 메모리 영역을 할당 받음, 각 프로세스는 서로 영향을 주지 않음
스레드는 하나의 PID 내 존재, 각 스레드가 메모리 영역을 공유하여 영향
프로세스 간 복사 시 COW(Copy-on-Write)이용, 실제 쓰기 연산 시 데이터 복사

동기와 비동기

프로그램 진행 시 함수의 완료 시점이 누구에게 있는가? 목적이 함수의 완료인가?

• 동기
  진행 중 함수 호출 -> 함수가 완료될 때까지 진행 멈춤 -> 완료 시점은 호출한 함수 동기
• 비동기
  진행 중 함수 호출 -> 프로그램이 진행 -> 이벤트 발생 -> 완료 시점은 진행 중이던 함수

블로킹과 논블로킹

프로그램 진행 시 함수의 처리 결과는 누구에게 있는가? 목적이 함수의 결과인가?

• 블로킹
  진행 중 함수 호출 -> 시스템 콜 -> 함수 진행 멈춤 -> 처리 결과 리턴 -> 함수 진행
• 논블로킹
  진행 중 함수 호출 -> 시스템 콜 -> 함수 진행 -> 시스템 콜 -> 처리 결과 리턴 -> 함수 진행

결합

• Sync - Blocking
  시스템 I/O를 통한 Read 작업이라고 가정 시
  Read() -> Process stop -> System call() -> Task stop -> return -> task run -> return -> process run
  I/O 작업 도중 프로그램이 종료되지 않기 위해 Sync
  I/O 작업 결과에 따라 함수를 처리하기 위해 Blocking

• Sync - nonBlocking
  시스템 I/O를 통한 Read 작업이라고 가정 시
  Read() -> Process stop -> System call() -> System call() return -> Task run -> System call() -> System call() return -> Process run
  I/O 작업 도중 프로그램이 종료되지 않도록 Sync
  I/O 작업 결과가 나오지 않더라도 진행 되도록 nonBlocking

• Async - nonBlocking Event Driven
  시스템 I/O를 통한 Read 작업이라고 가정 시
  Read() -> System call() -> return -> register callback handler -> Prcoess run -> system call handler -> complete callback -> Process run
  I/O 작업을 요청, 완료되지 않더라도 결과를 반환, 완료 시점을 알기위해 콜백 등록
  프로그램 진행 Async
  I/O 작업 결과가 나오지 않더라도 반환, 결과가 나오면 핸들러 호출

Concurrency

DeadLock

대표적으로 멀티 스레딩에 따른 메모리 공유로 발생하는 문제로 교착상태라고 함.
Dead Lock은 4가지의 조건을 만족해야함

Mutex(상호배제)

• 하나의 스레드가 작업을 수행하는 Critical Section(임계구역)에 다른 스레드 가 접근 할 수 없음

  Circular Wait(순환대기)

• 각 스레드가 작업 중인 스레드의 작업이 종료되기를 꼬리를 물며 기다리는 상태

  Hold and Wait(점유대기)

• 이미 작업 중인 스레드가 다른 스레드의 작업이 끝나기를 기다림

  Non-Preemption(비선점 상태)

• OS가 작업을 컨트롤 할 수 없음
  작업 스레드가 스스로 자원을 반납하길 기다림

  Dead Lock의 해결

• 은행가 알고리즘 (회피)
  구현이 어려움

• 우선순위 lock(semaphore) (회피)
  기아상태(우선 순위에 밀려 대기)와 우선순위 역전(하위 우선순위가 세마포어를 소유 하고 블로킹 되어 상위 우선순위가 밀리 상태)이 발생 가능

  Queue를 이용한 데이터 확인(데이터가 없으면 작업 안함)
  우선순위 계승, 라운드로빈 선점 스케쥴링, 스레드 풀을 통한 우선순위 해결

• Timeout (탈출)
  일정 시간 내 교착상태가 종료되지 않으면 강제로 할당 해제
  LiveLock 발생 가능

• RollBack (탈출)
  되돌리기, 교착상태 다시 발생 가능

event driven

이벤트 이용 방식, 비동기, 작업에서 어떤 이벤트가 발생했을 때 처리

thread pool

Queue이용, 먼저 작업할 스레드가 먼저 끝냄, 스레드 개수를 유지 가능
만약 db connect task가 1000번 일어나면 1000개 스레드 생성할건가?
스레드의 상한선을 정하고 스레드를 돌려막기

IPC(Inter Process Communication)

• message queue
  스레드 간 Context-Switching, 버퍼 형태의 큐가 존재
  스레드 간 메세지를 송수신, 큐에 대한 입출력 시스템 콜 빈번(커널 동기화)
  사용자가 따로 동기화를 신경 쓸 필요가 없음
  soket, message queue, signal, pipeline 등이 해당
  JDK8부터 Parallel Stream(stream pipeline) 구현
• share memory
  스레드 간 Context-Switching, 동일 메모리 객체(버퍼) 공유
  프로세스 내 공유 메모리에 접근 하므로 시스템 콜 필요 없음
  동일 메모리 객체를 공유하므로 연산에 대한 동기화가 필요
  레코드 lock, mutex/semaphore(복수 뮤텍스)로 제어

프로세스 스케쥴링

비선점형

• FCFS(First come First Served)
  먼저 온 프로세스가 먼저 작업한다
  프로세서가 건들 수 없기에 시분할 시스템(동시처리)에서는 좋지 못하다

선점형

• R-R(Round Robin)
  Time slice, 일정 시간 단위로 프로세스 작업을 재할당
  Time slice를 무한에 가깝게 설정 시 FCFS로 동작(할당이 안이루어지므로)
• Priority
  준비 큐와 작업 큐를 분리 우선 순위에 따라 프로세스를 선택, 기아 상태 발생 가능
  기아 상태를 해결해주기 위해 준비 큐에서 오래 있는 애들은 우선 순위를 변경
• 다단계 큐
  준비 큐를 포그라운드(우선순위 높음), 백그라운드(우선순위 낮음) 프로세스로 분리
  각 큐별 스케줄링에 따라 처리, 우선순위는 절대적
• 다단계 피드백 큐
  다단계 큐의 개선으로 기존 프로세스의 큐가 작업시간이 길어진다면 낮은 우선순위 큐로, 대기시간이 길어진다면 높은 우선순위 큐로 이동

캐시 메모리

메모리와 지역성

프로세서는 메모리를 효율적으로 사용하기 위해 동일한 공간에 빠른 시간 내에 재접근 하려는 경향이 있음

• 시간 지역성
• 공간 지역성
  이러한 특성에 따라 프로세서는 디스크와 물리적인 거리가 있음에도 요구 페이징 기법을 이용하여 필요한 프로세스만 페이징하여 실제 디스크로 가기까지 소요되는 시간을 줄여 지역성을 만족 시킬 수 있음

  맨 처음에 페이지를 메인 메모리에 적재한 후에는 다시 적재할 필요가 없기 때문에 페이지 결함의 확률이 매우 낮다. 공간적인 지역성은 코드를 읽을 때 현재 코드의 주변에 있는 코드를 읽을 확률이 높다는 것을 의미한다. 페이지 결함이 일어나 하드디스크에서 페이지를 가져올 때 주변 코드들을 block 단위로 가져오게 되면 주변 코드를 읽을 확률이 높으니 다음의 페이지 결함의 확률이 낮아지는 것이다. 따라서 지역성의 원리에 의해 페이지 결함으로 인한 컴퓨터의 효율이 떨어지는 확률이 많이 낮아진다.

또한 L1, L2와 같은 캐시를 이용하여 임시적인 지역성을 확보하여 최근의 데이터에는 빠르게 접근 가능
이는 시간 지역성에 따른 접근이지만 실제로 캐시는 캐싱을 위해 캐시 라인을 사용하기때문에 공간 지역성에 따른 영향도 받음

물리 메모리와 가상 메모리

지역성의 원리를 만족하기 위해선 자주 참조하는 데이터가 밀집되어 있어야 함
이를 위해 디스크의 물리적 메모리를 분할하여 RAM에 논리적 메모리로 적재하는 가상
메모리 기법이 사용
가상 메모리 분할 기법을 통해 적재되는 논리적 메모리는 분할 기법에 따라 랜덤하나
각 배치 테이블을 통해 변환 되므로 프로세서 입장에서는 순차적 메모리로 보임
또한 메모리의 효율성을 위해 적재된 프로세스 중 쓰이지 않는 프로세스를 교체하는 Swapping을 사용

물리 메모리 분할 기법 페이징과 세그먼테이션

• 세그멘테이션 - 논리 프로세스 크기 단위 분할
  세그멘테이션 테이블을 이용해 가변 크기로 프로세스를 분할
  실제 메모리에 따른 고정크기로 분할하는 페이징과 달리 세그먼트 테이블을 작성하여 매핑
  실제 메모리 적재 시 할당됨
  가변 크기에 따라 메모리는 논리적 분할되므로 세그먼트의 크기는 랜덤하고 이를 통해 남아있음에도 사용하지 못하는 메모리 hole들이 발생, 최적의 fit으로 적재할 수 있는 방법이 없음에 따른 외부 단편화 발생
  이를 해결하기 위해 세그멘테이션 페이징 기법을 이용
  세그멘테이션 분할 후 페이징 단위로 재분할

• 페이징 - 물리적 크기 단위 분할
  페이징 테이블을 이용해 고정 크기로 프로세스를 분할
  실제 메모리가 프레임 단위로 분할 되어 페이지와 매핑되어 있기에 연속적 메모리가 아니라도 할당 가능
  고정 크기에 따라 메모리는 분할되므로 논리적 단위가 맞지 않을 수 있어 프로세스보다
  메모리 크기가 큰 내부 단편화 발생 가능
  15byte 프로세스에 4byte단위 페이징 테이블이 할당 된다면 1byte가 남음

가상 메모리 적재 기법 요구 페이징

물리 메모리를 가변 크기로 분할하는 건 외부 단편화의 문제가 발생할 수 있어 대부분의 현대 운영체제는 페이징 분할 기법을 통해 물리적 크기로 분할한다.
그렇다면 가변 크기로 메모리를 사용하기 위해선 어떻게 하는걸까?

요구 페이징

논리적 프로세스 크기로 분할하되 미리 알자는 방식
각 프로세스가 필요로 하는 메모리 크기는 다르지만 필요한 만큼만 페이지를 이용하여 적재하자는 기법이다.
하지만 이 기법에도 문제가 있는데 적재된 페이지 중 필요로 하는 페이지가 없다면?

• Page fault
  요구 페이지가 없을 시 기존의 저장장치로 돌아가 페이지를 재적재하는 방식
  공간 지역성의 원리에 따라 기존 접근 메모리 주변의 메모리도 함께 적재하므로 다음 page fault의 확률은 매우 낮아진다.
• Page Replacement
  메모리 크기는 한정되어 있고 페이지는 늘어난다.
  그럼 페이지를 교체하자
  • FIFO
  • LRU(Least Recently Used)

JVM 메모리 구조

GC와 GC 알고리즘