Alchemist

Convoy Effects : CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들이 오래 기다리는 현상으로

＂호위 효과 ” 라고도 하며, 이로 인해 평균 대기시간이 길어지게 된다.

만약, 프로세스가 3개 있고, 각각의 프로세스는 30ms , 7ms , 2ms의 버스트 시간이 있다고 가정하자.

(각각의 프로세스에게 P1, P2, P3 라는 명칭을 부여함)

프로세스가 Queue에 도착하는 순서 과정을 두 가지 Case로 나누어 보도록 하자.

•  Case1 : P1 -> P2 -> P3

•  Case2 : P3 -> P2 -> P1

또 각각의 Case의 평균 대기 시간을 구해보도록 하자

•Case1의 평균 대기 시간 : (0 + 30 + 37 ) / 3 = 22.3ms

•Case2의 평균 대기 시간 : (0 + 2 + 9) / 3 = 3.66ms

두 case의 평균 대기 시간을 비교해 봤을 때 평균 대기 시간 차이가 크다는 것을 알 수 있다.

즉, FCFS에서 먼저 도착한 프로세스의 버스트 타임에 따라서 평균 대기시간의 편차가 커지는 것을 알 수 있다.

*평균 대기 시간이 매우 길어질 수 있다는 문제 야기 – 효율적인 CPU 이용 X

교착상태

- Deadlock : 두개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태

1. 발생원인 : 

제한된 자원에서 프로세스의 이용률을 높이고, 시스템 효율성을 높이려는 과정에서 부작용으로 발생

* 프로세스의 자원이용 순서

1) 요청 : 자원요청 -> 자원할당

2) 사용 : 할당된 자원 사용

3) 해제 : 할당자원을 반납 후 종료

2. 필요충분조건 : 

상호배제 + 점유와 대기 + 비선점 + 순환 대기

=> Deadlock이 왜 발생하고, 어디에서 발생하는지 알아야 할 필요가 있다

3. 자원할당 그래프

: 프로세스 집합과 자원들로 구성된 간선 집합을 통해 자원과 프로세스 간 관계를 그래프로 나타낸 것

- 이 그래프에서 사이클이 생기면 Deadlock이 발생한 것

교착상태 처리

- Deadlock 처리기법 : 예방, 회피, 탐지, 복구

1. Deadlock 예방

: Deadlock의 4가지 필요충분 조건이 발생하지 않도록 하여 Deadlock이 아예 발생하지 않게 한다

1) 상호 배제 : 상호 배제가 필요하지 않을 수 있는 상황에서는 가능하나, 자원에 따라 다르므로 상호배제는 무조건 유지

2) 점유와 대기 : 필요한 자원을 한꺼번에 요청하고 다 처리할 때 까지 다른 프로세스 보류

3) 비선점 방지 : 원래는 프로세스가 점유한 자원을 회수할 수 없지만, 회수를 허용하여 자원을 강제로 뺏어올 수 있게 한다.

4) 순환대기 방지 : 모든 자원에 순서를 부여하여 순서 순으로만 자원을 할당하여 Cycle이 발생하지 않게 한다

=> 4가지 조건중 3가지를 방지하면 Deadlock이 발생하지 않는다

2. Deadlock 회피

: 교착 상태가 일어날 확률이 낮은데도 무조건적으로 예방하는 것은 시스템 처리성능 저하의 문제가 발생함

-> Deadlock 발생 가능성을 인정하고 회피대책을 마련하는 것

1) 프로세스 시작거부 : 현재 프로세스와 새로 시작할 프로세스의 최대요구량 > 최대값 인 경우 시작거부

2) 자원할당 거부 : 자원 할당시 Deadlock 가능성이 높으면 할당을 거부한다.

(Unsafe/Safe Zone으로 나누어 놓고 Deadlock은 Unsafe Zone에서만 일어난다는것을 착안)

3. Deadlock 탐지

: 교착상태가 발생하도록 허용하되, 교착상태 발생시 탐지하고 복구

- Deadlock Detection / Deadlock Recovery 알고리즘 두 가지가 필요

(1) Multiple instances of resource

- 은행가 알고리즘의 변형알고리즘 활용

- 교착상태 회피의 경우 들어가기전에 교착상태 여부를 판단했으나, 탐지 알고리즘은 우선 들어간 뒤

교착상태가 발생하면 이를 감지한다

(2) Single Instance of resource

- wait-for graph 활용 알고리즘

4. Deadlock 복구

1) 프로세스 중단

: 교착상태와 관련된 모든 프로세스를 중단 or 하나씩 선택하여 중단

2) 자원선점(강제회수)

: 자원을 강제로 회수하여 교착상태 해결

  Semaphore (“S”)

개념 : 기존 상호배제 해법 으로는 임계영역 문제를 일반화 시키기 어렵다.

“다익스트라”는 세마포어 개념을 제시하였다.

P(S) = 차단 , V(S) = 풀어준다고 생각하면 편하다.

여러 개의 공유 자원을 사용해야 하는 경우, 세마포어 변수의 초깃값을 다르게 주거나, 여러개의 세마포어를 사용한다.

세마포어의 특성 :

• 원자적 명령 (Atomic) : 세마포어를 실행하는 동안에는 인터럽트나 이벤트에 의해 중단되지 않아야 한다. (꼭 필요한 경우 사용하지 않는다)

• 세마포어를 사용하면 N개의 임계영역 문제를 해결할 수 있다.

• 세마포어를 사용하여 N개의 상호배제를 구현할 수 있다.

Dining Philosophers Problem

-병행 프로세스와 동기화 문제의 예

• 5명의 철학가들이 두개의 포크를 이용해야 먹을 수 있다.

• 먹을 땐 생각을 할 수 없고, 먹지 않을 때 생각을 해야한다.

세마포어 P(S), V(S) 개념에 도입해보자. 최대 두명의 철학가들은 먹을 수 있고, 나머지 셋은 생각을 해야 함.

이를 세마포어를 통해 도입할 수 있다.

Semaphore chopStick[5] = {0};

P(chopStick[I])

P(chopStick[ (I+1) % 5])

    Eating();

V(chopStick[I])

V(chopStick[ (I+1) % 5])

    Thinking();

만일 5명 모두가 동시에 왼쪽 포크를 집어 들었을 경우 -> 다른 쪽 리소스를 확보할 수 없기 때문에 더이상 실행할 수 없다.

*Starvation이 발생한다. = 기아 상태(starvation 스타베이션[*])는 컴퓨터 과학 용어의 하나로, 프로세스가 끊임없이 필요한 컴퓨터 자원을 가져오지 못하는 상황으로, 이러한 자원 없이는 처리를 끝낼 수 없는 병행 컴퓨팅에서 마주치는 문제이다.

모니터… 프로세스의 동기화 기법

• P동작과 V연산이 프로그램 전체에 널리 퍼져있으면, 각 연산이 각자의 세마포어에 미치는 영향을 파악하기 어려워진다. -> 유지보수가 힘들고 가독성이 떨어진다.

• 조직적인 구성체를 두어 공유자원, 임계영역을 체계적으로 관리 -> “객체” , “모니터"

모니터 : 하나 이상의 프로시저와 초기화 코드, 공유 데이터로 구성관 소프트웨어 모듈 객체로, 모니터 경계에서 한번에 한 프로세스만 진입하도록 제어되므로 “상호 배제 원칙”을 지키게 된다.

프로세스 간 통신 (IPC)

• 프로세스 내부 데이터 통신 : 2개 이상의 쓰레드 간 데이터 통신(메모리 변수 이용), 전역변수, 파일 공유를 통한 데이터 전달.(매개체 필요)

• 프로세스 간 데이터 통신 : 동일 컴퓨터 내 프로세스간 데이터 통신 (Shared Memory, Pipe 등 이용)

• 네트워크를 이용한 원격 데이터 통신 : 네트워크 간의 프로세스 간 데이터 전송(Send,Receive), 소켓, RPC와 같은 네트워크 프로토콜을 이용한다.

스레드를 사용하면 자원을 공유하여 한 프로세스에서 동시 작업이 가능하다.

프로세스에 포함된 스레드들은 공통의 목적을 달성하기 위해 병렬로 수행된다.

또한 하나의 프로세스가 서로 다른 프로세서에서 프로그램의 다른 부분을 동시에 수행할 수 있으므로 시스템의 성능과 효율을 향상시킨다.

같은 프로세스의 스레드들은 동일한 주소 공간을 공유하고 있다.

Thread의 병렬 수행

1. 프로세스 하나에 포함된 스레드들은 공동의 목적 달성을 위해 병렬 수행 한다.

2. 프로세스가 하나인 서로 다른 프로세서에서 프로그램의 다른 부분 동시 실행.

Thread 병렬 수행의 잇점

1. 사용자 응답성 증가

2. 프로세스의 자원과 메모리 공유 가능

3. 경제성이 좋음

4. 다중 처리로 성능과 효율 향상

스레드/ 프로세스 모델

1. 단일 프로세스에 단일 스레드

2. 단일 프로세스에 다중 스레드

3. 다중 프로세스에 단일 스레드

4. 다중 프로세스에 다중 스레드

Thread State

1. 준비 : 스레드가 프로세서에 의해 실행될 수 있는 상태로 스레드는 준비 리스트에 삽입된다,

2. 실행 :스레드가 프로세서를 점유하여 실행중인 활성화 상태

3. 대기 : 스레드가 이벤트를 기다릴 때를 의미한다.(입출력 작업 등 완료될 때까지 보류상태)

4. 종료 : 스레드의 작업이 종료되면 자원해제. 레지스터 문맥과 스택 할당 제거.

TCB : thread control block

1. 실행상태

2. 프로세서 레지스트리

3. 프로그램 카운터

4. 스택 포인터

5. ...

6. TCB 포인터 등등이 있다.

Thread의 종류 

1. User level thread : 커널에서 쓰레드 기능을 지원하지 않을 때. 커널에 의존적이지 않은 형태로 쓰레드의 기능을 제공하는 라이브러리를 활용할 수 있는데, 이러한 방식으로 제공되는 쓰레드가 유저 레벨 쓰레드이다.

2. Kernel level thread :운영체제가 제공하는 시스템 함수 호출을 통해서 쓰레드 생성을 요구해야 한다. 그러면 운영체제는 해당 쓰레드를 생성 및 관리하면서 새로운 흐름을 형성하도록 도와준다. 프로그래머 요청에 다라 쓰레드를 생성 및 스케줄링하는 주체가 커널인 경우, 이를 가리켜 커널레벨(Kernel Level) 쓰레드라 한다.

3. Hybrid level thread : 스레드 생성은 사용자 영역에서 시작된다.

Process : 실행중인 프로그램 ( 메모리에 로딩된 형태)

메모리에 최상단은 OS가 탑재되어 있으며, 그 이후에는 프로세스들이 적재된 모습을 볼 수 있다.

PCB :프로세스 제어 블록(Process Control Block, 줄여서 PCB)은 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는 운영 체제 커널의 자료 구조이다. 

PCB가 프로세스의 중요한 정보를 포함하고 있기 때문에, 일반 사용자가 접근하지 못하도록 보호된 메모리 영역 안에 남는다. 일부 운영 체제에서 PCB는 커널 스택의 처음에 위치한다. (이 메모리 영역은 편리하면서도 보호를 받는 위치이기 때문이다.)

OS가 관리하는 프로세서의 명세서를 의미한다.

맨 처음 process state(프로세스 상태)가 들어간다.

프로세스가 실행하고 있는 프로그램을 프로세스 이미지라고 한다.

프로세스 주소공간 구조 : 최상단 : 스택 , 실행 힙, 데이터(정적 변수), 텍스트(코드)

프로세스 분류 : 

1. 시스템(커널) 프로세스

2. 사용자 프로세스

3. 병행 프로세스

            - 독립 프로세스

   - 프로세스 여러 개가 병행하여 수행 시 주어진 초기값에 따라 항상 같은 결과를 보여줌

    - 서로 독립적으로 실행되어 다른 프로세스에 영향을 받지 않고, 데이터를 공유하지않음

            - 협동 프로세스

 - 다른 프로세스에 영향을 주거나 다른 프로세스에 의해 영향을 받음

    - 컴퓨터 시스템의 제한된 자원을 공유하는 프로세스들이 통제되어 상호 작용해야 하는 경우 발생

    - 컴퓨터 시스템의 제한된 자원을 공유하는 프로세스들이 통제되어 상호 작용해야 하는 경우 발생

    - 서로 협동해야 하는 경우, 통신을 위한 수단과 동기화 기능이 필요

디스패처(Dispatcher) : 프로세스 스케쥴러

준비 큐 맨 앞에 있던 프로세스가 프로세서를 선택하는 것.

문맥교환 (context Switch)

1. 프로세스의 교환은 Interrupt

2. Trap

3. System call의 동작으로 시행된다.

절차 

1. 프로세스 P1가 실행되다가 타임 아웃이 되면 P1의 상태를 PCB에 저장하고, PCB2에서 P2의 상태를 가져옴 (디스패치)

2. 프로세스 P2가 실행되다가 타임아웃이 되면 P2의 상태를 PCB2에 저장하고, PCB1에서 P1의 상태를 가져온다(디스패치)

문맥 교환 횟수가 늘어날수록 성능이 낮아진다.

프로세스 구조  (Parent - Child)

프로세스 관리 : 프로세서의 생성과 종료, 제거, 서스펜드, 재시작, 우선순위 변경, 보류, 깨움

프로세서의 생성 

1. Fork() 시스템콜 함수는 PCB를 메모리에 생성해준다.

2. Child 프로세스가 생성되면 parent 프로세스에게 PID값을 넘긴다.

3. Parent 프로세스는 PID값으로 Child 프로세스를 구분한다.

프로세스의 종료 

1. 정상적인 종료 : exit()

2. 비정상적인 종료 : Timeout, 파일 입출력 실패( 파일 조회 최대 횟수 초과), 오류 발생(산술오류, 보호오류, 데이터 오류), 메모리 부족, 메모리 접근 불가 지역의 접근 시도 등

프로세스가 종료되면 프로세스를 제거한다. (PCB 제거 및 관련된 자원을 회수한다.)

VMS는 프로세스가 종료되면 Chile 프로세스는 강제종료되며

UNIX는 부모가 변경된다.

프로세스 우선순위와 관리

디스패처가 CPU에 할당할 프로세스를 선택할 때 우선순위를 보고 결정한다.

운영체제의 역할 

 -컴퓨터 시스템 = 사용자 + 하드웨어 + 소프트웨어

  운영체제는 하드웨어와 사용자(소프트웨어)간의 조정자, 자원관리자, 입출력장치와 사용자 프로그램 제어 역할을 한다.

여기서 사용자란 : 컴퓨터를 사용하는 사람 , 프로그램 , 장치 등등이 해당된다.

운영체제의 목표 

-편리성, 효율성(성능 향상), 안정성 , 확장성

1. 자원관리( 프로세스관리,cpu관리,메모리관리,입출력장치 관리)

2. 하드웨어 인터페이스(cpu,주기억장치 등 특성이 다르더라도 일관성 있는 접근제어)

3. 자원 보호 (타 사용자를 차단함)

4. 사용자 인터페이스 (UI)

자원관리 - 효율성

자원 보호 - 안정성

하드웨어 인터페이스 제공 - 확장성

사용자 인터페이스 제공 - 편리성

운영체제의 발전과정

초기의 일괄 처리 시스템 : 1401 작업 , 7094 작업 , 1401 작업 다 나뉘었다.

Offline System : cpu와 입출력장치간의 속도 차이를 개선하였다.

Buffering : 메모리 버퍼를 이용하여 속도 차이를 개선

Spooling : 디스크의 스풀이라는 거대한 장소를 만듦.

운영체제 유형별 특징 

1. Multi Programming System : 멀티 테스크 = 멀티 프로세스

-여러개의 프로세스들이 각각의 일을 처리함.

1. Time Sharing System (시분할시스템 : TSS)

-cpu 스케쥴링 , 다중 프로그래밍을 이용하여 각 사용자들에게 컴퓨터 자원을 분할하여 사용할 수 있게 해준다.

1. Distributed processing system (분산 시스템)

-인터넷에 연결된 여러 컴퓨터들의 처리 능력을 이용해 문제를 해결. (네트워크 필)

1. Multi processor system

-장점 : 처리율 증가, 비용 절감, 신뢰성 증가

Symmertric Multiprocessing을 요즘 많이 사용한다.

1. Cluster System

-여러개의 컴퓨터를 High Speed Network로 연결함. 각각의 컴퓨터는 하나의 storage를 공유함. 다른 컴퓨터가 죽으면 다른 컴퓨터가 역할을 수행하게 됨. 데이터는 하나의 storage에 저장됨.

1. Real time System

-데이터가 발생할 때 마다 즉시 처리함. 처리시간이 단축되고 처리 비용이 절감함. 데이터 발생 지점에서 직접 인출력을 담당함. 특정 상태를 재현할 수 없음.

1. Client Server System

-서비스를 요청하는 클라이언트, 서비스를 제공하는 서버의 이중 구조 시스템. 웹 기술을 이용한 대부분의 구조.

Web이 나오면서 대중화가 되었고, 사용자가 많을수록 서버의 부하가 증가한다.

1. P2P

-클라이언트 서버 구조의 단점인 서버 과부하를 해결하기 위해 서버를 거치지 않고 사용자와 사용자를 직접 연결해 서버의 부하가 분산되는 효과를 보임.

1. 사물인터넷

• 사물에 센서와 통신 기능을 내장하여 인터넷에 연결하는 기술. 인터넷으로 연결된 사물들이 직접 데이터를 주고받아 스스로 분석하고 학습 정보를 사용자에게 전달하거나 새로운 서비스를 창출함.

1.  클라우드 컴퓨팅

• 하드웨어를 포함한 시스템이 구름에 가려진 것처럼 사용자에게 보이지 않는 컴퓨팅환경. 언제나 어디서나 응용 프로그램과 데이터를 자유롭게 사용할 수 있는 컴퓨팅 환경을 의미한다.

1. Edge Computing

-사물인터넷이 발달할 수록 센서의 수가 많아짐. 문제점은 네트워크의 전송량이 증가하고, 클라우드 서버 부하가 증가한다.

센서들과 클라우드 서버간의 경계에서 처리할 수 있는 데이터는 처리하여 부하를 줄이는 방식

세대별 발전 과정 

일괄 작업 시스템. (버퍼링과 스풀링이 나오는데, 버퍼링이 먼저 나옴)

운영체제의 세부 기능 

메모리 관리, 프로세스 관리, 입출력 장치 관리, 파일 관리

기타 기능 : 보안, 네트워킹 / 분산 , 컴퓨터와 대화하는 쉘

메모리 관리 기능 

사용량 모니터, 주소 매핑, 실행과 해제

프로세스 : 프로세스는 실행주인 프로그램으로 실행을 위해 자원이 할당 된 프로그램을 얘기한다.

자원은 프로세서 점유, 메모리, 파일, 입출력 장치 등을 의미한다.

운영체제의 운영은 ? 프로세스 생성과 제거, 중지와 재수행, 동기화, 상호 통신 등등

입출력 장치 관리 기능 

사용자가 자세한 하드웨어 특성을 알지 못해도 자유롭게 활용 가능 하게 함

프로세서와 입출력 장치 가의 속도의 차이를 해결함(스풀링 버퍼링)

파일 관리 기능 

다양한 저장장치를 사용할 수 있도록 기능을 제공한다. 파일을 생성하고 제거하고 디렉토리의 생성 제거 등을 맡는다.

시스템 호출 서비스 : 커널을 스스로 보호하기 위해 만든 인터페이스

멀티 프로그래밍 환경에서 응용프로그램이 작동하면서 공유 자원들을 사용하며 다른 응용프로그램의 영역을 침해하는 것을 막기 위해 커널모드를 도입함

직접 접근 vs 시스템 호출 접근

함수를 이용하는 방식은 듯 함.

부팅 서비스 

부팅 : 운영체제가 메모리로 로딩되는 과정을 부팅이라고 함.

Booting Strap Loader : 디스크 0트랙에 위치하며 운영체제를 메모리로 로딩하는 프로그램을 의미한다.

부팅 절차 :1. 파워를 킨다.  2. 바이오스 부팅 스트랩 로더가 작동한다.3.  하드웨어를 체크한다. 3. 운영체제를 메모리로 로드한다. 5. 실행 완료

계층적 구조 

유사한 기능끼리 그룹으로 묶은 것.

모듈화, 계층간 독립성 보장, 결합도를 낮춘다. 유지보수가 쉬워야 한다. 검증과 오류 수정이 용이.

계층이 많을수록 성능 저하가 예상된다.

커널 

메모리에 상주하는 운영체제의 핵심 모듈을 의미한다.

마이크로 커널 vs 단일 커널

단일 커널 : 모든 커널의 기능을 내부 시스템 호출로 다 묶어서 해버림

마이크로 커널 : 꼭 필요한 기능만 넣고 사용자 모드에서 다른 기능을 사용할 수 있게 함.

마이크로 커널의 장점 : 커널이 가볍다. 한 부분에서 발생한 문제가 시스템 전체에 영향을 주지 않는다. 서버 개발 용이 + 기능 변경 용이 , 실시간 시스템 활용

단점 : 프로세스 간 통신 발생을 최소화 해야 한다. 속도가 느리다.