[기술면접준비] 운영체제

프로세스 Process

• 실행 중인 프로그램
• 디스크로부터 메모리에 적재되어 cpu의 할당을 받을 수 있는 것
• 운영체제로부터 주소 공간, 파일, 메모리 등을 할당받으며 이것들을 총칭하는 것

  프로세스 제어블록 : PCB

  • 특정 프로세스에 대한 중요한 정보를 저장하고 있는 운영체제의 자료구조
  • 프로세스를 관리하기 위해 프로세스의 생성과 동시에 고유한 PCB를 생성
    저장되는 정보

  1. 프로세스 식별자 : process ID[PID]

2. 프로세스 상태 : new, ready, running, waiting, terminated
3. 프로그램 카운터 : 프로세스가 다음에 실행할 명령어의 주소
4. CPU 레지스터
5. CPU 스케줄링 정보 : 프로세스의 우선순위, 스케줄 큐에 대한 포인터
6. 메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블 등과 같은 정보를 포함
7. 입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
8. 어카운팅 정보 : 사용된 CPU 시간, 시간제항, 계정 번호

스레드 Thread

• 프로세스의 실행 단위
• 한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 주소 공간이나 자원을 공유할 수 있다.
• thread는 thread id, PC[program counter], 레지스터 집합, 스택으로 구성
• 같은 프로세스에 속한 다른 스레드와 코드, 데이터 센션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유
• 멀티 스레딩 : 하나의 프로세스를 단수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행능력을 향상시키는 것, 스택과 PC는 각자 가지고 있다.

  스택을 thread마다 독립적으로 할당하는 이유

  스택은 함수 호출 시 전달되는 인자, 되돌아갈 주소값 함수 내에서 선언하는 변수 등을 저장하기 위해 사용되는 메모리 공간이므로 스택 메모리 공간이 독립적이라는 것은 독립적인 함수 호출이 가능하다는 것이고, 이는 독립적인 실행 흐름이 추가되는 것이다. 따라서 스레드의 정의에 따라 독립적인 실행 흐름을 추가하기 위한 최소 조건으로 독립된 스택을 할당한다.

  PC를 thread 마다 독립적으로 할당하는 이유

  PC 값은 스레드가 명령어의 어디까지 수행하였는지를 나타나게 된다. 스레드는 CPU 할당을 받았다가 스케줄러에 의해 다시 선점당하낟. 그렇기 때문에 명령어가 연속적으로 수행되지 못하고 어느 부분까지 수행햇는지 기억할 필요가 있다. 따라서 PC를 독립적으로 할당한다.

멀티 Thread

장점

• 메모리 공간과 시스템 자원 소모가 줄어들게 된다.
• thread 간의 통신 시, 별도의 자원을 이용하는 것이 아니라, 전역 변수의 공간 또는 동적으로 할당된 공간인 heap 영역을 이용하여 데이터를 통신한다 => 통신방법이 간단한다
• 스레드의 context switch는 프로세스 context swtich와는 달리 캐시 메모리를 비울 필요가 없기 때문에 더 빠르다. => 시스템의 Throughtput이 향상되고 자원 소모가 줄어들며 프로그램 응답시간이 ㅐ단축된다.

문제점

• 멀티 프로세스 기반일때에는 프로세스간 공유하는 자원이 없기 때문에 동일한 자원을 동시에 접근하려는 일은 없지만, 멀티 스레딩일 경우 처리해줘야된다.
• 서로 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 어떤 스레드가 다른 스레드에서 사용중인 변수나 자료구조에 접근하여 엉뚱한 값을 읽어오거나 수정할 수 있다.
  => 동기화 작업 이 필요하다.

  동기화작업

  • 작업 처리 순서를 컨트롤하고 공유자원에 대한 접근을 컨트롤하는 것
  • 병목현상이 발생하여 성능이 저하될 가능성이 높다 [ 과도한 lock ]

Multi Thread vs Multi Process

1. 멀티 스레드는 멀티 프로세스보다 적은 메모리 공간을 차지하고 문맥 전환이 빠르다.
2. 멀티 스레드는 오류로 인해 하나의 스레드가 종료되면 전체 스레드가 종료될 수 있다.
3. 멀티 스레드는 동기화문제를 가지고 있다.
4. 멀티 프로세스는 하나의 프로세스가 죽더라도 다른 프로세스에 영향을 끼치지 않는다. => 정상적으로 수행
5. 멀티 프로세스는 멀티 스레드보다 많은 메모리 공간과 CPU 시간을 차지한다
6. 멀티 스레드/멀티 프로세스 모두 동시에 여러 작업을 수행하는 점에서 같지만, 적용해야 하는 시스템에 따라 적합/부적합이 구분된다.

스케줄러

프로세스를 스케줄링하기 위한 queue

1. Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
2. Ready Queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
3. Device Queue : Device I/O 작업을 대기하고 잇는 프로세스의 집합

스케줄러의 종류

1. 장기스케줄러
메모리가 한정되어 있는 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리에 임시로 저장된다. 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할.

• 메모리와 디스크 사이의 스케줄링을 담당
• 프로세스에 메모리를 할당
• degree of multiprogramming 제어
• 프로세스의 상태 new -> ready

2. 단기스케줄러

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

3. 중기스케줄러

• 여유공간 마련을 위해 프로세스를 ㅌ오째로 메모리에서 디스크로 쫒아냄
• 프로세스에게서 memory를 deallocate
• 현 시스템에서 메모리에 너무 많은 프로그램이 올라가는 것을 조절하는 스케줄러
• 프로세스 상태 read -> suspended

cf. suspended : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다.

CPU 스케줄러

FCFS : First Come First Served

특징

• 먼저 온 고객을 먼저 서비스해주는 방식. 즉, 먼저온 순서대로 처리
• 비선점형스케줄링 [ CPU를 뺏기지 않는다 ]

문제점
convoy effect : 소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생

SJF : Shortest Job First

특징

• 다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 선 할당
• 비선점형 스케줄링

문제점
starvation : 효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안된다.

SRTF : Shortest Remaining Time First

특징

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루워진다.
• 남은 CPU burst time이 짧은 순올 CPU 할당
• 선점형 스케줄링 [ CPU가 뺏긴다 ]

문제점
starvation

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링
• 선점형 스케줄링
• 비선점형스케줄링

문제점
starvation

해결책
aging : 아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높인다.

Round Robin

특징

• 현대적인 CPU 스케줄링
• 각 프로세스는 동일한 크기의 할당시간[time quartum]을 갖게 된다
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우 효율적
• 프로세스의 context를 저장할 수 있어 가능하다.

장점

• response time이 빠르다
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다.

주의점

• 설정한 time quantum이 너무 커지면 FCFS와 동일하고, 너무 작으면 잦은 context swtich로 overhead 발생

동기 / 비동기

동기

• 메소드를 실행시킴과 동시에 반환값이 기대되는 경우 => blocking

비동기

• 백그라운드 스레드에서 해당 작업을 처리할 경우
• 동기의 반대 => non-blocking : 이벤트큐에 넣거나 백그라운드 스레드에게 해당 task 를 위임하고 다음 코드 실행

프로세스 동기화

critical section 임계영역

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

해결책

해결책 조건

1. Mutal Exclusion 상호배제 : 하나의 프로세스가 critial section에서 실행중이라면 다른 프로세스들은 critical section에서 실행될 수 없다.
2.progress 진행 : critical section을 진행 중인 프로세스가 없다면 sritical section의 진입 후ㅜ보로서 참여할 수 있다
3. Bounded Waiting 한정된 대기 : 프로세스가 critical section에 진입 신청 후부터 받아들여질 때까지, 다른 프로ㅔㅅ스들이 critical section에 집입할 수 있는 횟수는 제한되어있다.

1. lock

• 하드웨어 기반의 해결책
• 동시에 공유 자원에 접근하는 것을 막기 위ㅐ critical section에 집입하는 프로세스는 lock을 획득하고 critical section을 빠져나올 때, lock을 방출함으로써 동시에 접근이 되지 않도록 한다.
• 한계 : 다중처리 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.

2. semaphores 세마포

• 소프트웨어상에서 critical section 문제를 해결하기 위한 동기화 도구
• 종류
  카운팅 세마포 : 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용, 세마포의 개수는 가용 개수로 설정되며, 사용할때 세마포가 감소하고 완료시 세마포가 증가한다.
  이진 세마포 : MUTEX라고도 부르면, 0과 1의 값만 가지며, 다중 프로세스들 사이의 critical section 문제를 해결하기 위해 사용
• 단점 : busy waiting 바쁜 대기

cf. deadlock 교착상태
세마포가 ready queue를 가지고 있고, 둘 이상의 프로세스가 critical section 집입을 무한정 기다리고 있고, critical section에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되어야만 빠져나올 수 있는 상황
=> 멈춘 상태라고 생각하면 이해가 쉬운 것이다.

모니터

• 고급 언어의 설계 구조물로서, 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태
• 공유자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다. : 세마포는 직접 키 해제와 공유자원의 접근 처리가 필요

메모리 관리 전략

메모리 관리 배경

• 각각의 프로세스는 독립된 메모리 공간을 갖고, 운여체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. 단지, 운영체제만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않는다.

swapping : 메모리의 관리를 위해 사용되는 기법, 표준 swapping 방식으로는 round-robin고 ㅏ같은 스케줄링의 다중 프로그래밍 환경에서 cpu 할당 시간이 끝난 프로세스의 메모리를 보조기억장치로 내보내고 다른 프로세스의 메모리를 불러 들일 수 있다.

단편화 : 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼 작은 자유공간들이 늘어나게 되는데, 것이 단편화이다.

1. 외부단편화 : 메모리 공간 중 사용하지 못하게 되는 일부분. 모두 합치면 충분한 공간이지만, 분산되어 있을 때 발생
2. 내부단편화 : 프로세스가 사요하는 메모리 공간에 포함된 남는 부분.

압축 : 외부 단편화를 해소하기 우해서 프로세스가 사용하는 공간들을 한쪽으로 몰아, 자유공간을 확보하는 방법론, 작업효율이 좋지 않다.

페이징

• 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야한다는 제약을 없내는 메모리 관리 기법
• 외부 단편화와 압축 작업을 해소하기 위해 생긴 방법론
• 논리메모리, 물리메모리
• 하나의 프로세스가 사용하는 공간은 여러개의 페이짖로 나눠어서 관리되고 개발페이지는 순서에 상관없이 물리 메모리에 있는 프레임에 mapping되어 저장됨.
• 단점 : 내부 단편화 문제의 비중이 늘어나게 된다.

세그멘테이션

• 서로 다른 크기의 논리적 단위인 세그먼트로 분할.
• 사용자가 두개의 주소로 지정 [ 세그먼트 번호 + 변위 ]
• 세그먼트 테이블에는 각 세그먼트의 기준[세그먼트의 시작 물리주소]과 한계[세그먼트의 길이]를 저장
• 단점 : 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 자유 공간들이 많은 수의 작은 조각들로 나누어져 못 쓰게 될 수도 있다 [외부단편화]

가상메모리

• 프로세스 전체가 메모리내에 올라오지 않더라도 실행이 가능하도록 하는 기법
• 프로그램이 물리 메모리보다 커도 된다는 장점
• 많은 프로그램을 동시에 실행할 수 있게 된다 => 응답시간 유지, CPU 이용률/처리율 향상
• swap에 필요한 입출력이 줄어들어 프로그램이 빠르게 실행된다.

하는 일

• 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리하는 것
• 작은 메모리를 가지고도 큰 가상 주소 공간을 프로그래머에게 제공가능

가상주소공간

• 한 프로세스가 메모리에 저장되는 논리적인 모습을 가상메모리에 구현한 공간
• 프로세스가 요구하는 메모리 공간을 가상메모리에서 제공함으로서 현재 직접적으로 필요치 않는 메모리 공간은 실제 물리 메모리에 올리지 않는 것으로 물리 메모리를 절약할 수 있다.

프로세스간의 페이지 공유

• 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다.
• 각 프로세스들은 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 랄이브러리가 올라가있는 물리메모리 페이지들은 모든 프로세스에 공유
• 프로세스들이 메모리를 공유하는 것을 가능하게 하고, 프로세스들은 공유 메모리를 통해 통신할 수 있따. 이 또한, 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있다.
• fork()를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

Demand Paging 요구 페이지

• 초기에 필요한 것들만 적재하는 전략
• 가상 메모리 시스템에서 많이 사용
• 가상 메모리는 대개 페이지로 관리
• 요구 페이징을 사용하는 가상 메모리에서는 실행 과정에서 필요해질 때 페이지들이 적재된다.
  => 한번도 접근되지 않는 페이지는 물리 메모리에 적재되지 않는다
  =>시간 낭비와 메모리 낭비를 줄일 수 있다

페이지 교체

• 요구 페이징에서 언급된대로 프로그램 실행시에 모든 항목이 메로리에 올라오지 않기 때문에 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault가 발생하게 되면, 원하는 페이지를 보조저장장치에서 가져오게 된다. 하지만, 만약 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 이뤄져야한다. [ 또는 운영체제가 프로세스를 강제로 종료하는 방법이 있다]

기본적인 방업

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

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

   페이지 교체 알고리즘

   FIFO 페이지 교체

• 가장 간단한 페이지 교체 알고리즘
• 먼저 물리메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다.
• 장점 : 이해하기 쉽고, 프로그램하기도 쉽다
• 단점 : 오랜된 페이지가 항상 불필요하지 않는 정보를 포함하지 않을 수 있다 / 활발한 페이지를 교체할경우, 페이지 부재율을 높이는 부작용 발생 / Belady의 모순 [ 페이지를 저장할 수 잇는 페이지 프레임의 갯수를 늘려도 되려 페이지의 부재가 더 많이 발생하는 모순이 존재 ]

최적 페이지 교체 : OPT

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체
• 낮은 페이지 부재율, Belady의 모순 발생하지 않음.
• 비교 연구목적을 위해 사요
• 장점 : 알고리즘 중 가장 낮은 페이지 부재율을 보장
• 단점 : 구현이 어렵다. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없다.

LRU 페이지 교체

LRU: Least Recently Used

• 최적 알고리즘의 근사 알고리즘
• 가장 오랫동안 사용되지않은 페이지를 선택하여 교체
• 대체적으로 FIFO알고리즘보다 우수하고 OPT알고리즘보다는 부족하다.

LFU 페이지 교체

LFU: Least Frequently Used

• 참조 횟수가 가장 적은 페이지를 교체하는 방법
• 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘
• 특징 : 어떤 프로세스가 특정 페이지를 집중적으로 사용하다. 다른 기능을 사용하게되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있다. / 최적 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

MFU 페이지 교체

MFU : Most Frequently Used

• 참조 횟수가 가장 작은 페이지를 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.
• 특징 : 최적 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 사용되지 않는다.

캐시의 지역성

캐시의 지역성의 원리

• 속도가 빠른 장치와 느린 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리.
• CPU가 어떤 데이터를 원할 것인가를 어느정도 예측할 수 있어야한다.
• 캐시의 성능은 작은 용량의 캐시 메모리에 CPU가 이후에 참조할 정보가 어느 정도 들어있느냐에 따라 좌우된다.
• 적중율[hit rate]를 극대화시키기 위해서 데이터 지역성의 원리를 사용
• 전체조건으로 프로그램은 모든 코드나 데이터를 균등하게 접근하지 않는다는 특성을 기본으로 한다.
• locality 란, 기억 장치 내의 정보를 균일하게 접근하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성
• 시간지역성 : 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성
• 공간지역성 : 대부분의 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

Caching Line

캐시 : 프로세서 가까이에 위치하면서 빈번하게 사용되는 데이터를 나누는 장소 => 목적 데이터가 저장되어있다면 바로 접근하여 출력할 수 있어야 캐시의 의미가 있다
캐시라인 : 캐시에 데이터를 저장할 때 특정 자료구조를 사용하여 묶음으로 저장 => 데이터의 메모리 주소 등을 기록해 둔 태그를 달아놓을 필요가 있다.

1. Full Associative
2. Set Associative
3. Direct Map