운영체제 (Operating System)

Operating System 

 

운영체제

  l  커널

 

  l  부트스트랩 (Bootstrap Loader)

 

  l  프로그램의 주소 공간

 

  l  OS(커널)의 주소 공간

 

  l  링커/로더

 

  l  버퍼링 & 스풀링

 

  l  인터럽트

 

  l  시스템 콜 (모니터 호출)

 

 

---

컴퓨터 시스템 구조, 프로세서

 

프로세스

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

 

  l  컨텍스트 스위치 / 문맥 교환 (Context Switch)

 

스레드

  l  멀티 스레드

 

  l  스레드 제어 블록 (TCB, Thread Control Block)

 

  l  스레드 풀

 

 

프로세스와 스레드 차이

 

스케줄링

 

 

---

동기화 관련 문제들

  l  동기화 기법

 

  l  모니터

 

  l  교착 상태 (DeadLock)

 

 

메모리 관리 전략

  l  스와핑

 

  l  메모리 단편화

 

가상 기억장치

  l  가상메모리 관리 기법

 

  l  페이징 기법

 

  l  가상메모리 관리 기법

 

  l  메모리 풀

 

  l  워킹 셋

 

  l  세그먼테이션 기법

 

  l  페이지 부재

 

  l  페이지 교체 알고리즘

 

  l  국부성, 구역성 (Locality)

 

  l  스레싱 (Thrashing)

 

 

 

---

디스크 스케줄링

 

파일 / 파일 시스템

 

 

  l  파일 할당 방법

 

  l  디렉터리

 

자원 보호 기법

 

파일 보호 기법 / 보안 유지 기법

 

 

RAID

 

 

---

운영체제

 

유용한 컴퓨터 시스템을 만드는 과정에서 발생한 문제를 해결하기 위한 방법들을

목적에 따라 필요한 기능을 통합한 소프트웨어 입니다.

 

관점	역할
사용자 관점	사용자가 응용 프로그램을 실행할 수 있는 기반 환경을 제공 컴퓨터를 쉽게 이용할 수 있도록 돕는다. (사용자가 실행하는 작업을 최대화하는 것) 사용자 관점에서 누가 어디에 쓰냐에 따라 설계 목표가 달라짐   한 사용자가 독점 – pc, 휴대폰, 스마트폰 등 여러 사람           – 대형/미니 컴퓨터, 워크스테이션, 서버 등
시스템 관점	자원할당자(resource allocator)로서 CPU, 메모리, 입출력 장치 등에 효율적이고 공정하게 자원을 할당해줍니다.

 

l  구성

 

제어 프로그램	컴퓨터 안의 정보, 자원을 제어하고 실행을 지시
처리 프로그램	지시,감독을 받아 실제로 데이터 처리하고 결과 보여줌

 

 

l  기능

 

프로세스 관리 (프로세스 생성, 제거, 중단, 재수행)

CPU, 메모리, 입출력장치 등의 자원관리, 자원 스케줄링

시스템과 사용자 간의 인터페이스제공

데이터, 파일, 네트워크, 하드웨어 관리

시스템 오류 검출, 복구

메모리 관리

CPU 이용률과 응답속도를 위해 메모리에 여러 프로그램을 유지해야 하므로 관리가 필요하고

메모리 어느 부분이 사용중이고 누가 사용중인지 추적, 메모리 할당, 회수

 

 

l  목적/성능 검사 항목

 

처리능력 향상, 반응시간 최소화, 사용가능도 향상, 신뢰도 향상

 

 

l  실행 과정

 

운영체제는 메모리에 상주하지 않는다.

컴퓨터 부팅시 부트스트랩 프로그램에 의해 메모리에 적재되어 실행

(커널은 메모리에 상주함)

 

 

l  운용 기법

 

기법	설명	장/단점
일괄 처리  (Batch Processing, 1세대)	일정 기간 또는 일정량의 데이터를 모아서 한꺼번에 처리하는 방식	시스템 자원을 독점하여 CPU 유휴 시간이 줄어든다. 효율이 높다.   사용자 측면에서는 처리량이 많아 반환 시간이 늦다.
다중 프로그래밍  (Multi Programming, 2세대)	하나의 CPU와 주기억장치를 이용하여 여러 개의 프로그램을 동시에 처리하는 방식 하나의 주기억장치에 2개 이상의 프로그램을 기억시켜 놓고, 하나의 CPU와 대화하면서 동시에 처리
시분할  (Time Sharing, 2세대)	CPU의 전체 사용 시간을 작은 작업 시간량(Time Slice)로 나눠 그 동안만 번갈아 가면서 CPU를 할당하여 각 작업을 처리한다.   라운드 로빈(Round Robin) 방식이라고도 한다.   다중 프로그래밍 방식과 결합하여 모든 작업이 동시에 진행되는 것처럼 대화식 처리가 가능하다.
다중처리  (Multi Processing, 2세대)	여러 개의 CPU와 하나의 주기억장치를 이용하여 여러 개의 프로그램을 동시에 처리하는 방식이다.	하나의 CPU가 고장나더라도 다른 CPU를 이용하여 업무를 처리할 수 있으므로 시스템의 신뢰성, 안전성이 높다.
실시간 처리  (Real Time, 2세대)	데이터 발생, 처리 요구가 있는 즉시 처리하여 결과를 산출하는 방식이다.	처리시간이 짧고 처리 비용이 낮다.   우주선, 인공위성, 은행 온라인 업무 등 타임 크리티컬한 작업에 사용됨
다중 모드 (Multi Mode, 3세대)	일괄 처리 시스템, 시분할 시스템, 다중 처리 시스템, 실시간 처리 시스템을 한 시스템에서 모두 제공하는 방식
분산 처리 (Distributed Processing, 4세대)	여러 개의 컴퓨터(프로세서)를 통신 회선으로 연결하여 하나의 작업을 처리하는 방식 각 단말장치나 컴퓨터 시스템은 고유의 운영체제와 CPU, 메모리를 가지고 있다.	각 시스템이 통신망을 통해 연결되어서 유용한 자원 공유 가능   하나의 일을 여러 시스템에 분산처리하여 연산 속도 향상   하나의 시스템 오류나도 계속 일을 처리할 수 있으므로 신뢰도 향상   멀리 떨어져 있어도 정보 교환 가능

 

 

---

커널

운영체제의 핵심을 담당하는 소프트웨어

운영체제의 기능은 엄밀히 말하자면 커널의 기능이다.

 

l   커널/사용자 모드

 

OS도 하나의 프로그램이므로 차지하는 영역이 있다.

OS와 사용자는 HW/SW 자원을 공유하므로 사용자 응용 프로그램이 시스템에 문제를 발생시키지 않도록

보장해야 합니다.그래서 OS와 사용자 코드를 구분할 수 있어야하고

하드웨어에 있는 한 비트(모드 비트)가 이를 구분해 줍니다.

0 : 커널 모드, 1 : 사용자 모드

 

CPU는 그저 PC가 가리키는 메모리 영역의 명령어를 처리해줍니다.

(Program Counter : CPU가 실행해야 할 메모리 주소를 담고있는 레지스터)

OS가 존재하는 커널 영역을 가리키면 CPU가 커널모드에서 실행 중이라고 말한다.

 

 

l  일반/특권 명령

 

명령을 다음과 같이 구분하여 부적절한 사용을 막는다.

일반 명령	메모리에서 자료읽어와 CPU에서 계산하고 결과를 메모리에 씀
특권 명령	프로세스 제어, 파일 조작, 장치 조작, 정보유지 보수, 통신, 보호

 

따라서 사용자 응용 프로그램은 특권 명령을 사용하지 못합니다.

특권 명령을 사용하고 싶을 때 사용하는 것이 바로 ‘시스템 콜’ 이며

OS에게 특권 명령을 대신 실행해달라고 요청하는 것입니다.

 

 

---

부트스트랩 (Bootstrap Loader)

시스템 부팅시 커널을 찾아 주 메모리에 적재하고 실행을 시작해줍니다.

커널이 실행되면 시스템과 사용자에게 서비스를 제공할 수 있게 됩니다.

일부 서비스는 부트시 메모리에 적재되어 수행되는데

이를 시스템 프로세스(디먼)이라고 합니다.

일반적으로 ROM에 저장되어 있습니다.

 

---

프로그램의 주소 공간

Code, Data, BSS, Heap, Stack

 

l  코드 (Code / Text)

작성한 코드가 기계어 명령으로 변환되어 저장되는 영역

이 부분은 컴파일 후에 바뀌지 않으므로

같은 프로그램에서 이 코드 부분을 공유하여 메모리 사용량 줄이기 위해 존재

 

l  데이터 (Data)

초기화 된 전역 변수, 정적 변수와 배열, 구조체가 존재,

프로그램 실행 시 생성, 종료시 반환,

함수 내부 정적 변수는 프로그램 실행 시 공간만 할당하고 함수 실행 시 초기화

 

l  BSS (Block Stated Symbol)

초기화 되지 않은 데이터 저장

 

l  힙 (Heap)

동적 할당 (malloc, new)된 데이터가 저장, 런타임에 크기가 결정,

힙 영역에 할당한 다 쓴 메모리를 반환하지 않으면 메모리가 부족해지는 것을

‘메모리 누수’

 

l  스텍 (Stack)

임시 메모리 영역으로 지역 변수, 매개 변수, 반환 값 등이 잠시 저장, 함수의 호출이 끝나고 돌아갈 반환 주소, 함수 내의 지역 변수 등이 저장되는 정보를 ‘스택 프레임’ 이라고 함

런타임에 크기가 결정되지만, 런타임에 스택의 총 사이즈를 변경 못함

 

 

l  추가 정보

코드,데이터,스텍 영역은 컴파일러가 결정, 힙은 개발자가 결정

스텍은 상위 메모리부터 할당, 나머지는 하위 메모리부터 할당

 

 

l  오버플로우

heap overflow	heap이 주소 값을 채우며 내려오다가 stack 영역을 침범
stack overflow	stack이 밑에서부터 주소 값을 채우며 올라오다가 heap 영역을 침범

 

 

 

---

OS(커널)의 주소 공간

 

l  커널의 코드

하드웨어 자원을 효율적으로 관리하는 일과 응용 프로그램 및 사용자에게 편리한 서비스 제공

CPU, 메모리 등의 자원을 관리하기 위한 부분과 인터페이스 제공하기 위한 부분

시스템 콜 및 인터럽트를 처리하기 위한 부분

 

l  커널의 데이터 영역

각종 자원을 관리하기 위한 자료 구조가 저장됩니다.

하드웨어 자원을 관리하기 위한 자료 구조와 현재 수행 중인 프로그램(프로세스)를

관리하기 위한 자료 구조, 큐, PCB 등

 

l  커널의 스텍 영역

함수 호출 시 복귀 주소를 저장하기 위한 용도로 사용합니다.

프로세스마다 별도의 스택을 두어서 관리합니다. 그 이유는 자기 주소 영역 내에 정의된 함수도 호출될 수 있지만 커널 영역에 정의된 함수도 호출될 수 있기 때문이다.

 

 

 

---

링커/로더

l  링커

번역 프로그램이 생성한 목적 프로그램들과 라이브러리나 모듈을 연결하여 실행 가능한

로드 모듈을 만드는 시스템 소프트웨어

 

l  로더

컴퓨터 내부로 정보를 들여오거나 로드 모듈을 ROM으로부터 RAM에 적재하는

시스템 소프트웨어

할당 – 연결 – 재배치 – 적재의 과정을 거친다.

 

할당	기억장치 내의 공간을 확보
연결	부프로그램 호출 시 부프로그램의 시작 주소를 호출한 부분에 등록
재배치	보조기억 장치에 저장된 프로그램이 사용하는 주소를 할당된 기억 장소의 실제 주소로 배치
적재	실행 프로그램을 할당된 기억 공간에 실제로 옮김

 

적재

RAM에서 CPU 내부 레지스터로 한 바이트, 한 워드를 옮기는 것을 의미합니다.

반대가 저장입니다.

RAM에 모든 것을 저장하기엔 크기가 너무 작기 때문에 보조 메모리인 ROM에 저장하고

필요할 때 적재하게 됩니다.

 

적재 방법	설명	Binding Time	장점	단점
정적 적재	번역기는 아무것도 모르기 때문에 전부 적재하고, CPU가 실행할 때 안다.	Link, Load Time	동적 적재에 비해 CPU가 할 일이 적음	사용하지 않는 것도 모두 적재
동적 적재	실행시 번역기가 필요한 부분만 적재하여 CPU가 실행	Execute Time	사용하지 않는 프로그램은 적재 하지 않고 실행하지도 않는다.	CPU가 그 만큼 할 일이 많다.

 

---

버퍼링 & 스풀링

CPU의 처리속도와 입출력 장치의 속도 차이를 보완하기 위한 방법

 

1.     버퍼링

 

한 개의 입출력과 CPU 작업을 같이 하는것

버퍼는 CPU의 레지스터 부분

주기억 장치에 버퍼를 둠으로써

입력시 CPU는 버퍼의 내용을 가져다 쓰고 입력 장치는 버퍼의 내용을 기록하게 된다.

출력시 CPU는 연산결과를 버퍼에 넣고, 출력 준비가 되면 출력장치는 버퍼의 내용을 꺼내어 출력

버퍼링은 입출력과 작업의 계산을 중복한다.

 

 

2.     스풀링 ( Spooling )

 

한 개 이상의 입출력과 CPU 작업을 같이 하는것

디스크의 일부는 스풀공간이라고 불리는 매우 큰 버퍼처럼 사용하는 방식

메모리의 일부를 버퍼로 인식하도록 하여 그 공간을 버퍼 처럼 사용하는 방식

입출력 데이터를 모아두었다가 한꺼번에 하기 위해 디스크에 저장하는 것

 

---

인터럽트

CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 또는 예외상황이

발생하여 처리가 필요할 경우에 CPU에게 알려 처리할 수 있도록 하는 것을 말한다.

 

상대가 CPU에게 일을 처리해달라고 요청하는 수단이다.

인터럽트는 필요할 때 처리되는 경향이 있어 리얼타임 문제가 적다.

하드웨어(주변장치)는 어느 순간이든 시스템 버스를 통해 CPU에게 신호를 보낼 수 있다.

 

인터럽트를 어떻게 처리할 것인가는 CPU-core의 특수 레지스터에 비트 마스크를 통해 선택적으로 수용한다.

인터럽트 발생하면 CPU는 해당 인터럽트를 처리하기 위한 루틴(인터럽트 서비스 루틴(ISR)으로 넘어가서 

처리코드를 수행합니다.

 

 

l  인터럽트 과정

인터럽트 요청이 들어오면 스택에 되돌아갈 주소를 저장하고

요청에 대해 어떤 서비스를 해주어야 할지 판단하여 해결하고 원래의 주소로 되돌아간다.

1)     Request 요청

2)     Service 장치 확인

3)     Handle 해결

4)     Return 되돌아감

 

 

l  인터럽트 처리절차

1)     현재 진행 중인 기계어 코드를 완료한다.

2)     CPU의 특수레지스터 중, 인터럽트 마스크 비트를 보고 마스크 되면 인터럽트를 무시한다.

3)     인터럽트 벡터를 읽고,

4)     ISR 주소값을 얻는다.

5)     ISR로 점프 한다. 이때 PC(Program Counter, IP) 값은 자동 대피 저장된다.

6)     현재 진행중인 프로그램의 레지스터를 대피한다.

7)     해당 코드를 실행한다.

8)     해당 일을 다 처리하면, 대피시킨 레지스터를 복원한다.

9)     ISR의 끝에 IRET 명령어에 의해 인터럽트가 해제 된다.

10)   IRET 명령어가 실행되면, 대피시킨 PC값을 복원하여 이전 실행 위치로 복원한다

 

 

l  인터럽트 서비스 루틴 (ISR) 점프방식

인터럽트는 주로 하드웨어적으로 접수되어 실행되는 것이 일반적이다.

따라서 인터럽트가 접수되었을 때 어떤 하드웨어에서 보낸것인지를 CPU-core가 알아야함

인터럽트 벡터라는 숫자는 CPU코어에 보내지면 소스를 구별할 수단으로 사용된다.

 

인터럽트 벡터를 얻었으면 ISR 주소값을 찾는 2가지 방식

1) 정해진 주소값으로 무조건 점프, 따라서 정해진 메모리 위치에 ISR코드 존재

2) 인터럽트 벡터 테이블에 주소값을 얻어서 점프한다.

따라서 인터럽트가 걸리기 전에 테이블이 완성되어있어야 한다. 

 

l  차이점

시스템콜 = 사용자 프로그램이 요청

인터럽트 = 주변장치, 예외가 요청/발생

 

풀링(polling) = 대상을 주기적으로 감시하여 상황이 발생하면 처리

인터럽트     = 상대가 CPU에게 요청

 

---

시스템 콜 (모니터 호출)

 

사용자 프로그램이 특권 명령의 수행이 필요하여 OS에게 대행을 요청하는 것

OS는 커널영역에 정의된 시스템 콜 처리 코드를 수행합니다.

 

 

---

컴퓨터 시스템 구조, 프로세서

 

1. 단일 프로세서

하나의 CPU로 실행 + 특수 목적의 전용 처리기 (디스크, 키보드, 그래픽 제어기…)

 

2. 멀티 프로세서 (병렬 시스템, 멀티코어 시스템)

하나 이상의 프로세서가 하나의 메모리, 버스, 클락, 주변 장치를 공유하는 구조

 

한 프로세서 보다는 효율이 좋겠지만 동기화 문제가 발생할 수 있다.

시스템의 신뢰성, 장치 이용의 융통성, 처리능력의 증대를 목적으로 만들어진 시스템

 

l 프로세서 연결 방식

 

1)     시분할 및 공유 버스

각종 장치들을 ‘버스’라는 단일 경로로 연결한 방식

장치 연결 단순, 경제적, 융통성 있으며 장치 추가 용이

한 시점에서는 하나의 전송만 가능

 

2)     크로스바 교환 행렬

1의 방식에서 버스의 수를 기억장치 수만큰 증가시켜 연결한 방식

기억장치마다 다른 경로 사용 가능, 두 개의 서로 다른 기억장치 동시 참조 가능

연결이 복잡해짐

 

3)     하이퍼큐브

다수 프로세서를 연결하는 방식

경제적인 방식, 확장성 좋음

 

4)     다중포트 연결 기억장치

시분할 및 공유 버스 + 크로스바 교환 행렬 한 혼합 형태 방식

많은 수의 프로세서 쉽게 연결 가능

다양한 연결 가능하지만 전송 시간 느림

 

 

 

l  장점

 

1)    증가된 처리량

처리기의 수를 증가시킴으로써 보다 짧은 시간 동안에 보단 많은 일을 실행. N개의 처리기를 사용할 경우 속도 증가율이 N배가 되지 않고 N보다 작다.

 

2)    규모의 경제

여러 개의 단일 시스템에 비해 비용을 절약할 수 있는데,

이는 처리기가 주변장치, 대용량 저장장치, 전원 공급 장치를 공유하고 있기 때문.

 

3)    증가된 신뢰성

기능들이 여러개의 처리기에 적절히 분산된다면 한 처리기가 고장나더라도 시스템이 정지하는 것이 아니라 단지 속도만 느려지게 된다.

 

 

l  형태

 

1)     비대칭적 다중처리 (마스터-슬레이브 프로세서, 주-종속 시스템)

하나의 주처리기(마스터)가 시스템을 제어, 작업 스케줄링, 작업 할당

다른 처리기(슬레이브)들이 명령과 테스트 수행

 

2)     대칭적 다중처리

모든 프로세서가 대등

각 프로세서는 고유의 레지스터 집합과 로컬 캐시를 갖진다.

하나의 메모리 공유

 

3)     분리 실행 처리기

비대칭적 다중처리의 비대칭성 보완하여 각 프로세서가 독자적 운영체제 가짐

각 프로세서에서 발생하는 인터럽트는 각자가 해결

그래서 하나가 고장나도 전체 다운되지 않음

 

 

 

l  최근에는 하나의 칩에 여러 코어를 넣는다.

 

이는 칩 내의 통신이 칩 사이의 통신 보다 빠르다.

전력 소모 작다

멀티 코어는 다중처리 시스템이지만 다중처리 시스템이 멀티 코어는 아님

 

 

l  프로세서의 결합도

 

다중 처리기는 각 프로세서 간의 결합도에 따라 다음과 같이 분류된다.

 

1.     약결합 시스템 (Loseely Coupled) = 분산 처리 시스템

각 프로세서마다 독립된 메모리를 가진 시스템

둘 이상의 독립된 컴퓨터를 통신망으로 연결한 시스템

각 시스템은 독자적 운영체제를 가짐

 

2.     강결합 시스템(Tightly Coupled)  = 다중 처리 시스템

동일 운영체제에서 여러 개의 프로세서가 하나의 메모리 공유

공유 메모리 차지하려는 프로세서 간 경쟁 최소화 해야함

 

3. 분산 처리 시스템

약결합 시스템으로, 독립적인 처리 능력을 가진 컴퓨터 시스템을 통신망으로 연결한 시스템

 

l  투명성

구체적인 시스템 환경을 사용자가 알 수 없도록 하고

이러한 정보가 없이도 원하는 작업 수행할 수 있도록 하는 것

종류로 위치, 이주, 복제, 병행, 접근, 성능, 규모, 고장 투명성이 있다.

 

 

l  클러스터형 시스템

분산 시스템의 특별한 형태로 여러개의 컴퓨터가 고속 네트워크로 강하게 결합되어 있는 시스템이다.

여러 PC를 LAN이나 고속신호 연결망으로 연결, 저장장치를 공유

하나 고장나도 다른 것으로 대체 가능, 병렬 수행 가능

 

 

l  위상에 따른 분류

 

위상	설명	장/단점
완전 연결형	각 사이트가 모든 사이트와 직접 연결된 구조	사이트간 메시지 전달 속도 빠름 기본 비용 많이 들지만 통신 비용 적고 신뢰성 높다.
부분 연결형	일부 사이트들 간에만 직접 연결된 형태 직접 연결되지 않은 사이트는 연결된 다른 사이트를 통해 통신	기본 비용은 완전 연결보다 적게 들지만 통신 비용은 많이들고 신뢰성 낮음
트리/계층형	분산 처리 시스템의 대표적인 형태,  각 사이트들이 트리 형태로 연결	기본 비용은 부분 연결형 보다 적게 들고, 통신 비용은 트리의 깊이에 비례 자식 사이트는 부모 사이트를 통해 통신 부모 사이트 고장나면 자식 통신 불가능
스타/성형	모든 사이트가 하나의 중앙 사이트에만 직접 연결	기본 비용은 사이트 수에 비례,  통신 비용 적게듬 중앙 사이트 고장시 모든 통신 단절
링/환형	각 사이트가 인접한 두 사이트와만 직접 연결된 구조 정보는 단방향/양방향 전달 가능	기본 비용은 사이트 수에 비례,  데이터 전달을 위해 링을 순환하면 통신 비용 증가
다중 접근 버스연결형	모든 사이트가 공유 버스에 연결된 구조	기본 비용은 사이트 수에 비례,  데이터 전달을 위해 링을 순환하면 통신 비용 증가

 

 

---

프로세스

프로세서에 의해 처리되는 사용자/시스템 프로그램을 의미, 필요한 자원을 요구한다.

자원을 할당받은 작업의 단위

 

l  개념

실행중이거나 실행 가능한 프로그램

PCB를 가진 프로그램

실기억장치에 저장된 프로그램

프로세서가 할당되는 실체

프로시저가 활동중인 것

비동기적 행위를 일으키는 주체

지정된 결과를 얻기 위한 일련의 계통적 동작

목적 또는 결과에 따라 발생되는 사건들의 과정

 

l  상태

상태	설명
New	프로세스가 생성되는 상태
Ready	CPU 할당을 기다리는 상태
Run	명령들이 실행되는 중인 상태
Wait	입출력 처리가 필요하여 실행중인 프로세스 중단 하여 대기하는 상태 프로세스가 사건이 일어나기를 기다리는 상태
Terminated	프로세스가 실행을 종료하는 상태

 

l  특징

부모 프로세스와 자원 공유하지 않는다.

자식프로세스 생성시 code(text)영역 제외하고 stack,heap,data영역 모두 복사됨

시스템 콜 : fork(), vfork()

 

프로세스의 자원에 접근하려면 프로세스 간의 통신 IPC를 사용해야 한다.

 

 

l  프로세스 간 통신 방법 IPC (Inter-Process-Communication)

 

1)    종류

-       PIPE (익명 PIPE)

익명의 파이프를 통해 동일 PPID (부모 프로세스 ID)를 가진 프로세스 간 단 방향 통신

파이프 하나로 Read 또는 Write만 가능, 양 방향 하려면 각각 만들어야 함

통신 단위는 Stream

 

 

-       Named PIPE

이름 가진 파이프를 통해 다른 프로세스 간 단 방향 통신

파이프 이름만 알면 통신이 가능함

통신 단위는 Stream

 

 

-       Message Queue

메모리를 사용한 파이프, 구조체 기반으로 단 방향 통신

msgtype에 따라 다른 구조체 가져올 수 있다.

파이프가 아니라 어디서나 물건 꺼낼 수 있는 컨베이너 벨트

데이터에 번호를 붙임으로 써 여러 프로세스가 동시에 데이터 쉽게 다룰 수 있다.

통신 단위는 구조체

 

-       Shared Memory

커널이 관리하는 시스템 상의 공유 메모리 통해 양 방향 통신

위의 방법들이 통신을 이용했다면 이것은 데이터 자체를 공유하는 방식이다.

프로세스 간 메모리 크기 동일해야 한다. 동기화 문제 발생할 수 있다.

통신 단위는 구조체

 

 

-       Memory Mapped File (메모리 사상 파일)

프로세스의 가상 메모리 주소 공간에 파일을 매핑한 뒤

가상 메모리 주소에 직접 접근하는 것으로 파일을 Read/Write 하는 방법

Shared Memory와 차이라면 열린 파일을 메모리에 매핑시켜 공유하는 것이다.

파일의 시스템은 전역 (모두 공유 가능한) 자원이므로 데이터 공유에 문제가 없다.

 

파일로 대용량 데이터 공유할 때 사용

대부분 OS에서 프로세스 실행할 때 실행 파일의 각 세그먼트를 메모리에 사상하기 위해 이것을 사용한다.

통신 단위는 페이지

 

-       Socket

네트워크 소켓통신을 사용한 데이터 공유

Client – Server 구조로 데이터 통신

통신 단위는 Stream

 

 

2)    사용 시기 및 특징

 

사용 시기	IPC 종류
부모 자신 간 단 방향 통신	PIPE
다른 프로세스 간 단 방향 통신	Named PIPE, Message Queue
다른 프로세스 간 양 방향 통신	Shared Memory, Memory Map
다른 시스템 간 양 방향 통신	Socket

 

---

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

프로세스에 대한 중요한 정보를 저장해 놓는 곳

프로세스가 생성될 때마다 고유 PCB가 생겅되고 완료되면 제거됨

프로세스 상태, 포인터, 고유 식별자, CPU 레지스터 정보, 스케줄링 정보 등을 포함

 

 

---

컨텍스트 스위치 / 문맥 교환 (Context Switch)

하나의 프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생하는 것으로

현재 CPU가 할당된 프로세스 정보를 저장, 새로운 프로세스 정보를 설정,

혹은 PCB에 저장된정보를 복원한 후 CPU 할당하여 실행되도록 하는 작업

 

l  왜 필요한가?

인터럽트가 발생하면 시스템은 인터럽트 처리가 끝난 후에 문맥을 복구할 수 있도록

현재 실행 중인 프로세스의 현재 문맥을 저장할 필요가 있습니다.

 

결국 문맥 교환이란 프로세스를 중단했다가 재개하는 작업을 위한 것입니다.

실행 상태인 A -> 현재 상태 저장 -> 준비 상태

준비 상태인 B -> PCB에 저장된 정보 복원 -> 실행 상태

 

문맥 교환시간은 하드웨어의 지원에 크게 좌우되며

오버헤드의 큰 요인중 하나로 적용됩니다.

 

 

---

스레드

프로세스 내부에 있는 작업 단위로서 프로세스가 할당받은 자원을 이용하는 실행의 단위

하나의 프로세스에 하나의 스레드가 존재하면 단일 스레드

하나 이상의 스레드가 존재하면 다중 스레드

 

l  사용자 수준의 스레드

 

사용자 영역에서 스레드 연산을 수행

사용자가 만든 라이브러리를 사용해 스레드 운용

커널이 관여하지 않기 때문에 커널 수준 스레드보다 오버헤드 적고 속도 빠르다.

구현 어려움

스케줄링 우선순위 지원하지 않는다. (무슨 스레드가 먼저 동작할 지 모름)

입출력 작업 등에 의해 스레드 하나라도 블록이 걸리면 전체 스레드 블록됨

 

 

l  커널 수준의 스레드

 

커널 영역에서 스레드 연산을 수행

가장 가벼운 커널 스케줄링 단위이다.

커널이 스레드를 관리하기 때문에 커널에 종속적임

커널이 각 스레드를 개별적으로 관리 가능, 안정성과 다양한 기능 제공

스케줄링, 동기화를 위해 커널을 호출하는데 무겁고 오래걸림

모드 전환이 빈번하게 일어나서 성능 저하 발생

 

 

l  장점

 

병행성 증진으로 성능과 처리율 향상, 응답 시간 단축, 공간 절약, 효율적인 통신

 

 

l  상태

l  스레드 간 통신

스레드는 프로세스와 Code, Data, Heap 영역을 공유함

전역 변수로 접근하면 되는데 동기화 문제가 발생할 수 있다.

 

 

---

프로세스와 스레드 차이

 

부모 프로세스와의 자원 공유 유무

크롬으로 스포츠 영상을 보면 크롬이 프로세스가 되고

크롬안에서 영상을 처리해주는 부분과 네트워크로 영상을 받아오는 부분이 쓰레드가 된다.

 

l  프로세스

운영체제로부터 자원을 할당받은 작업의 단위

부모 프로세스와 자원 공유하지 않는다.

자식프로세스 생성시 code( text ) 영역 제외하고 stack, heap, data 영역 모두 복사됨

시스템 콜 : fork(), vfork()

 

l  스레드

프로세스가 할당받은 자원을 이용하는 실행의 단위.

여러 프로세스들이 병렬 처리될 때 하나의 단위를 의미한다.

부모 프로세스와 자원을 공유, code, data, heap 영역 공유, 자신만의 stack 영역 사용

스레드는 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유한다.

시스템 콜 : clone(), pthread()

 

 

---

멀티 스레드

 

•  개요

여러 스레드를 사용해 하나의 작업을 동시에 처리하자는 개념

 

• 사용 이유

단일 프로세서 시스템의 효율성 증대

자원의 활용, 처리량 극대화

 

 

•  멀티 프로세스 대신 멀티 스레드를 쓰는 이유 ( 프로세스에 비해 무엇이 좋은가? )

 

프로그램을 여러 개 실행하는 것 보다 한 프로그램에서 여러 작업을 실행하는 것이라 생각하면 된다.

프로세스 간 문맥교환은 단순히 CPU 레지스터 교체 뿐만 아니라

RAM과 CPU 사이의 캐시 메모리에 대한 데이터까지 초기화 됨

자원의 효율성 증대	프로세스 생성하여 자원을 할당하는 시스템 콜 줄어든다. ( = 성능 오버헤드 줄어든다. )
처리 비용 감소, 응답 시간 단축	스레드는 프로세스 내의 stack영역 제외한 모든 메모리 공유한다. ( = 데이터 주고 받는 것이 간단. 통신 비용 적다. 문맥 교환으로 일어나는 오버헤드가 적다. 자원 소모 줄어든다. )

 

 

•  단점

디버깅이 어렵다
프로세스 외부에서 스레드 제어 x
자원 공유 문제 ( 동기화 문제 )	스레드간 자원 공유는 전역 변수( 데이터 세그먼트 )를 이용하므로 함께 상용할 때 충돌 가능성 있음
하나의 스레드에 문제 발생하면 프로세스 전체에 영향

 

 

•  동기화

방법	종류	장/단점
커널에서 제공하는 동기화 기능	뮤텍스, 세마포어, 이름있는 뮤텍스, 이벤트 기반 동기화	많은 기능 제공됨
커널의 힘을 빌리지 않는 동기화 방법	크리티컬 섹션, 인터락 함수 기반 동기화	성능상 이점이 있지만 기능상의 제한

 

 

•  멀티 스레드 모델

 

스레드를 위한 자원은 사용자 스레드를 위해서는 사용자 수준에서,

커널 스레드를 위해서는 커널 수준에서 제공된다.

 

사용자 스레드와 커널 스레드는 연관 관계가 있어야 한다.

모델	내용	장/단점
다대일 모델	많은 사용자 수준 스레드를 하나의 커널 스레드로 사상	한 번에 하나의 스레드만이 커널에 접근할 수 있기 때문에 다중 스레드가 다중 처리기에서 돌아도 병렬로 작동 불가, 병목 현상이 생길 수 있다.
일대일 모델	각 사용자가 각각 하나의 커널 스레드로 사상.	이 모델은 다중처리기에서 다중 스레드가 병렬로 실행되는 것을 허용.   단점은 사용자 수준 스레드 생성마다 커널 스레드도 생성해야 하므로 성능저하가 생길 수 있음, 시스템에서 제공되는 스레드 수가 제한적
다대다 모델	많은 사용자 수준의 스레드에 많은 커널 수준 스레드 사상	개발자가 원하는 만큼의 사용자 스레드 추가 가능하다. 다중 처리기에서 병렬로 수행 가능, 하지만 여전히 진정한 의미의 병렬처리는 아니다
두 수준 모델	적은 수의 커널 스레드로 다중화 시키면서 하나의 사용자 쓰레드가 하나의 커널 쓰레드에 종속되도록 한 모델

 

 

---

스레드 풀  ( Thread Pool )

 

•  개요

프로세스를 시작할 때 일정한 수의 스레드들을 미리 풀로 만들어 두는 것

 

스레드 풀 안에 있는 스레드들은 할당된 서비스가 없으면 가만히 있다가

서비스가 요청되면, 그 요청을 처리하고 다시 풀로 돌아간다.

이 때 스레드 풀에 남아있는 스레드가 바닥나면 서버는 가용 스레드가 하나 생길 때까지 기다려야 한다

 

•  장점

새 스레드를 생성하는 일은 성능 오버헤드가 따르는데

스레드 풀을 이용해 기존 스레드를 활용하기 때문에 빠르다.

 

동시에 가동하는 스레드 개수에 제한을 둘 수 있다.

이러한 제한은 많은 수의 스레드를 병렬 처리할 수 없는 시스템에 도움이 된다.

 

 

---

스레드 제어 블록 ( TCB, Thread Control Block )

•  구성

스레드 상태

스택 포인터(프로세스에 스레드의 스택에 대한 포인트)

PC

스레드의 레지스터 값

스레드가 있는 프로세스의 PCB를 가리키는 포인터

 

 

---

스케줄링

프로세스가 생성되어 실행될 때 필요한 자원을 할당하는 작업을 뜻한다.

 

1.     목적

 

공정성, 처리율 증가, CPU 이용률 증가, 오버헤드 최소화, 응답 시간 최소화,

반환 시간 최소화, 대기 시간 최소화, 균형 있는 자원 사용, 무한 연기 대피

 

다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해

항상 실행 중인 프로세스를 가지게 하는 데 있다.

거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄된다.

프로세스 실행은 CPU 실행과 입출력 대기의 사이클로 구성된다.

 

 

l  작업, CPU 스케줄링?

 

여러 작업이 메모리에 동시에 유지되어야 하는데, 공간이 부족하다면

그들 중 몇 개를 선택해야 한다. 이것을 ‘작업 스케줄링’이라고 한다.

 

메모리에 여러 프로그램 동시에 있을 경우 ‘메모리 관리’가 필요하며

 

여러 작업이 동시에 실행 ‘준비’ 되어 있으면 그들 중 하나를 선택해야 한다.

이것을 ‘CPU 스캐줄링’ 이라고 한다.

 

 

l  CPU 스케줄링

 

준비완료 큐(반드시 FIFO방식의 큐가 아님)에 있는

어느 프로세스에게 CPU를 할당할 것인가를 결정하는 문제를 다룬다.

큐에 있는 레코드들은 일반적으로 프로세스들의 PCB들이다.

 

 

CPU 스케줄링이 일어날 네 가지 상황

 

1)     한 프로세스가 실행 상태에서 대기 상태로 전환될 때

2)     프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (ex. 인터럽트 발생시)

3)     프로세스가 대기 상태에서 준비완료 상태로 전환될 때 (ex. 입출력 종료 시)

4)     프로세스가 종료할 때

 

 

l  스케줄링 기준

 

기준	내용
CPU 이용률	우리가 가능한 한 CPU를 최대한 바쁘게 유지, (실제 시스템에선 40~90%)
처리량	단위 시간당 완료된 프로세스의 개수
총 처리 시간	프로세스의 제출 시간과 완료 시간의 간격
대기 시간	프로세스가 실행을 기다리는 시간   스케줄링 알고리즘은 오직 프로세스가 준비완료 큐에서 대기하는 시간의 양에만 영향을 준다.
응답 시간	하나의 요구를 제출한 후 첫 번째 응답이 나올 때 까지의 시간

 

 

 

---

스케줄링 종류

 

l  비선점 스케줄링 ( Nonpreemptive Scheduling )

 

이미 할당된 CPU를 다른 프로세스가 강제로 뺏을 수 없는 정책

프로세스가 자원 할당 받으면, 스스로 반납할 때 까지 사용을 허용한다.

 

◾  특징

일괄 처리 방식의 스케줄링

응답시간 예측이 용이

모든 프로세스에 대해 공정함

 

◾  단점

중요한 작업이 덜 중요한 작업에 밀릴 수 있다.

 

◾  종류

선입 선처리 스케줄링 FCFS ( First Come First Service ) 

최단 작업 우선 스케줄링 SJF ( Shortest Job First )

HRN ( HRRN, Highest Response Ratio Next )

우선순위 ( Priority )

기한부 스케줄링 ( Deadline )

 

대기 시간( Waiting Time )	작업 시작 시간 – 도착 시간
반환 시간( Time Around Time )	작업 완료 시간 – 도착 시간 = 대기 시간 + 실행 시간
평균 반환 시간	( 반환 시간 합 ) / 작업 수
평균 대기 시간	( 대기 시간 합 ) / 작업 수

 

 

---

◾  선입 선처리 스케줄링 FCFS ( First Come First Service ) 

 

큐에 도착한 순서에 따라 CPU를 할당하는 기법

평균 대기 시간은 종종 대단히 길 수 있다. ( 호위 효과 )

 

•  호위 효과(convoy effect)

모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것

 

특정 프로세스의 완료 시간, 대기 시간, 반환 시간

전체 작업의 평균 반환시간을 구하라는 유형의 문제가 있습니다.

 

•  문제 예시

 

도착 시간이 같은 경우

도착 시간이 별도로 없으므로 A, B, C 모두 0초에 도착해 있다고 생각하면 된다.

프로세스	실행 시간( 버스트 시간 )	대기 시간	반환 시간
A	13	0	13
B	35	13	48
C	2	48	50
평균	15.66....7	20.333...	37

 

시간	0 ~ 13	13 ~ 48	48 ~ 50
프로세스	A	B	C

 

도착 시간이 다른 경우

프로세스	도착 시간	실행 시간	대기 시간	반환 시간
A	0	13	0	13
B	2	35	13 - 2 = 11	48 - 2 = 46
C	40	2	48 - 40 = 8	50 - 40 = 10
평균	14	15.67	6.333...	23

 

---

◾  최단 작업 우선 스케줄링 SJF ( Shortest Job First )

 

버스트 시간( 실행 시간 ) 이 짧은 프로세스부터 CPU 할당

버스트 시간이 짧을수록 우선순위가 높다고 볼 수 있음

버스트 시간 같으면 FCFS( 선입 선출 ) 스케줄링

 

최적이긴 하지만 다음 CPU 버스트의 길이를 미리 알 수 없음

따라서 다음 버스트 시간이 이전 버스트 시간과 비슷할 것이라고 예측

선점형 SJF 알고리즘은 최소 잔여시간 우선 스케줄링 ( SRTF, Shortest Remaining Time First Scheduling ) 라고 한다.

 

프로세스	실행 시간	반환 시간	대기 시간
A	6	9	3
B	3	3	0
C	8	24	16
평균	5.66...7	(2 + 8 + 21 ) / 3 = 11.666...	( 0 + 5 + 13 ) / 3 = 6

 

시간	0 ~ 3	3 ~ 9	16 ~ 24
프로세스	B	A	C

 

 

---

◾  HRN ( HRRN, Highest Response Ratio Next )

 

짧은 작업에 유리한 SJF의 단점을 개선하여 우선순위로 서비스한다.

우선순위 계산 결과 값이 높은 것부터 수행한다.

대기 시간이 길수록 우선순위가 점점 높아진다.

 

•  우선순위 : ( 대기시간 + 서비스시간 ) / 서비스시간

프로세스	도착 시간	실행 시간
A	0	6
B	1	3
C	4	2
D	6	1

처음에 A 밖에 없으므로 A 실행 ( 0 ~ 6 )

 

프로세스	도착 시간	대기 시간	실행 시간	우선순위 계산
B	1	5	3	( 5 + 3 ) / 3 = 2.67
C	4	2	2	( 2 + 2 ) / 2 = 2
D	6	0	1	( 0 + 1 ) / 1 = 1

B가 가장 우선순위가 높으므로 B 실행 ( 6 ~ 9 )

 

작업	도착 시간	대기 시간	실행 시간	우선순위 계산
C	4	5	2	( 5 + 2 ) / 2 = 3.5
D	6	3	1	( 3 + 1 ) / 1 = 4

D 실행 ( 9 ~ 10 )

종료

 

시간	0 ~ 6	6 ~ 9	9 ~ 10	10 ~ 12
프로세스	A	B	D	C

 

프로세스	도착 시간	시작 시간	완료 시간	대기 시간	반환 시간
A	0	0	6	0	6
B	1	6	9	5	8
C	4	10	12	6	8
D	6	9	10	3	4
평균				3.5	6.5

 

---

◾  우선순위 ( Priority )

 

우선 순위가 높은 작업이 먼저 CPU를 사용한다.

시간 제한, 메모리 요구량, 열린 파일의 수, 프로세스의 중요성, 자원사용 비용 등 으로 우선순위 정의된다.

우선순위 알고리즘은 선점형, 비선점형 둘다 가능

 

•  문제점

실행 준비는 되어 있으나 CPU를 사용하지 못하는 우선순위가 낮은 프로세스는 

CPU를 기다리면서 봉쇄된 것으로 간주될 수 있다.

 

•  해결법

무기한 봉쇄 = 기아 ( Starvation )를 해결하는 한가지 방안은 노화 ( Aging )이다.

 

기아 ( Starvation )
우선순위가 낮은 프로세스가 계속 뒤로 밀리면서 무기한 대기를 하는 것

노화 ( Aging )
기아(Starvation) 현상을 방지하기 위해 일정시간 마다 우선순위를 높여서 노화 시키는것

 

 

◾  기한부 스케줄링 ( Deadline )

 

작업을 명시된 시간이나 기한 내에 완료하도록 하는 기법

 

정확한 자원 및 수행 시간 등을 미리 예측하기 어려움

---

 

l  선점 ( Preemptive ) 스케줄링

 

우선순위가 높은 다른 프로세스가 실행 중인 프로세스의 CPU 뺏을 수 있다.

빠른 응답을 요구하는 대화식 시분할 시스템에 사용됨

선점한 프로세스에게 일정 시간을 배당하기 위한 인터럽트 타이머가 필요

많은 오버헤드 초래할 수 있음

 

 

◾  SRTF ( Shortest Remaining Time First )

 

선점형 SJF 스케줄링

진행 중인 프로세스가 있어도 Sleep시키고 최단잔여시간 프로세스에 우선권 부여

 

 

◾  선점 우선순위 스케줄링

 

새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점

 

 

◾  라운드 로빈 스케줄링 RR ( Round Robin )

 

시분할 시스템을 위해 설계되었다. 

준비완료 큐는 원형 큐로 동작

대기 큐를 사용하여 먼저 대기한 작업이 먼저 CPU를 사용한다.

CPU를 사용할 수 있는시간( Time Slice or Time Quantum ) 동안

CPU를 사용한 후에 다시 대기 큐에 배치하여 대기한다.

 

할당되는 시간이 작을수록 문맥 교환 및 오버헤드가 자주 발생된다.

 

작업	도착시간	실행시간
A	0	8
B	1	4
C	2	9
D	3	5

 Time Slice = 4

시간	0 ~ 4	4 ~ 8	8 ~ 12	12 ~ 16	16 ~ 20	20 ~24	24 ~ 25	25 ~ 26
작업	A	B	C	D	A	C	D	C

 

작업	작업완료시간	도착시간	반환시간 = (작업완료시간 – 도착시간)
A	20	0	20 - 0 = 20
B	8	1	8 - 1 =  7
C	26	2	26 - 2 = 24
D	25	3	25 - 3 = 22
평균			18.25

 

 

◾  다단계 큐 스케줄링 ( Multilevel Queue Scheduling )

 

프로세스를 서로 다른 그룹으로 분류할 수 있는 경우

그룹에 따라 각기 다른 준비상태 큐를 사용하고 자신만의 스케줄링 알고리즘 사용하는 방식

큐와 큐 사이에 스케줄링도 반드시 있어야한다.

 

•  정적 우선순위를 사용한다. ( 큐 사이를 이동할 수 없다. )

큐 1 - RR 2 ... 3 4 큐 5 - FCFS	이런 식으로 큐 마다 자신만의 스케줄링 알고리즘 사용
큐 사이 스케줄링 : 선점	상위 단계 큐에 프로세스가 들어오면 상위 단계 큐 부터 처리하고 하위 단계 큐 처리
큐 사이 스케줄링 : RR	큐 마다 time quantum을 정해줘서 돌아가면서 처리

 

 

◾  다단계 피드백 큐 스케줄링

 

다단계 큐 기법에 적응 기법( 준비상태 큐 사이를 이동할 수 있도록 개선한 기법 )의 개념을 적용한 기법이다.

짧은 작업에 우선권을 준다.

입출력 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다.

프로세스 사용량에 따라 프로세스 분류한다.

 

노화 ( Aging ) : 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다. 

이를 통해 기아 ( Starvation ) 상태를 예방한다.

 

---

l  동시성 vs 병렬성

 

◾  동시성

논리적으로 2개 이상의 작업이 진행되고 있는 것

( 여러 작업이 번갈아가며 진행되는 것 )

 

◾  병렬성 

물리적으로 2개 이상의 작업이 동시에 진행되고 있는 것

 

 

l  Blocking vs Non-blocking

 

◾  Blocking

호출된 함수가 자신의 작업을 모두 마칠 때까지 호출한 함수를 기다리게 만든다.

 

◾  Non-blocking

호출된 함수가 바로 리턴해서 호출한 함수에게 제어권을 준다.

 

 

l  Synchronous vs Asynchronous

 

◾  Synchronous

함수의 결과를 호출한 쪽에서 처리

 

◾  Asynchronous

함수의 결과를 호출한 쪽에서 처리하지 않는다.

호출되는 함수에게 callback을 전달해서, 호출되는 함수가 전달받은 callback을 실행

 

 

l  Race Condition

 

공유 자원에 대해 여러 프로세스/스레드가 동시에 접근을 시도하는 상황

즉, 하나의 자원을 두고 경쟁 하는 것

 

순서를 잘 조절하지 않으면 비정상적인 상태가 발생한다.

 

 

---

l  임계 구역 ( Critical Section )

 

둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부

한 시점에 하나의 스레드만 접근 가능한 공유 메모리 공간

Race Condition을 유발하는 코드 블록

 

 

l  Lock

 

자원을 사용하는 동안 들어오지 못하도록 잠구는 것

하나의 자원에 여러 스레드가 동시에 접근하는 것을 조율해준다.

 

---

동기화 관련 문제들

 

l  생산자 소비자 문제

 

생성자는 프로세스를 만들어 버퍼에 넣고

소비자는 버퍼에서 프로세스를 꺼내서 소비한다.

버퍼는 공유 메모리 공간에 존재해야 생성자가 한 항목을 생성하는 동안 소비자는 한 항목을 소비할 수 있다.

버퍼가 무한 버퍼인 경우에는 생성자가 계속해서 만들어내면 되는데

유한 버퍼인 경우에는 생성자가 버퍼가 꽉 차면 대기해야하고 소비자는 버퍼가 비어 있으면 대기해야한다.

 

◾  이 문제를 해결하는 것을 생산자 소비자 협동이라고 함, 세마포어를 활용

 

 

l  독자 저자 문제

 

여러 명의 독자와 저자들이 하나의 저장 공간(버퍼)를 공유하며 접근할 때 발생

독자는 공유 공간에서 데이터를 읽어온다.

여러 명의 독자가 동시에 데이터를 읽어오는 것이 가능

저자는 공유 공간에 데이터를 쓴다.

한 저자가 공유 공간에 데이터를 쓰고 있는 동안에는 그 저자만 접근 가능하며

다른 독자들과 저자들은 접근할 수 없다.

 

◾  세마포어로 해결

 

 

l  잠자는 이발사 문제

 

이발소에 이발사 한 명이 있다. 이발용 의자도 하나 있고, 대기실에 많은 사람 있다. 이발사가 손님 한명의 머리를 다 깎고 나면, 다른 기다리는 손님이 있는지 대기실로 간다. 손님이 있으면 데려와 머리를 깎고 없으면 자기 의자에 앉아서 잔다.

모든 손님은 이발사가 자고 있으면 깨우고, 다른 사람을 이발하고 있으면 대기실로 간다. 거실에 빈 의자가 있으면 앉고, 없으면 떠난다.

 

◾  뮤텍스로 해결, 한 번에 한 명만이 동작 상태를 바꿀 수 있게 한다.

이발사는 뮤텍스를 반드시 얻은 후 대기실 손님 확인할 수 있고

잠을 자거나 이발을 할 때 뮤텍스 반납.

손님은 뮤텍스를 얻은 후에 이발소에 들어갈 수 있고, 대기실/이발용 의자에 앉을 때 뮤텍스 반납

복수의 잠자는 이발사 문제는 세마포어가 필요함

 

 

l  식사하는 철학자들 문제

 

다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에 스파게티가 있고 양옆에 포크가 하나씩 있다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 있다.

이때 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다.

이때 각각의 철학자가 왼쪽의 포크를 들고 그 다음 오른쪽 포크를 들어서 스파게트를 먹는 알고리즘이 있으면, 다섯 철학자는 동시에 왼쪽 포크를 들 수 있으나 오른쪽의 포크는 이미 가져가진 상태이기 때문에 다섯 명 모두 무한정 서로를 기다리는 상태에 빠진다.

 

◾  동시성과 교착상태를 설명하는 예시로, 여러 프로세스가 동시에 돌아갈 때 교착상태가 나타나는 원인을

직관적으로 보여줌, 동시성을 제거하여 해결

 

 

---

동기화 기법

 

l  임계 구역 (Critical Section)

 

둘 이상의 프로세스/스레드가 동시에 접근해서는 안되는 공유 자원 코드 영역

동시에 Read/Write하면 동기화 문제가 생기므로

하나의 프로세스/스레드만 수행하도록 Lock을 걸고 작업이 끝나면 Lock을 해제

 

임계 구역은 독점할 수 없으며, 선점 할 수 없음

임계 구역 내에서의 작업은 신속하게 이루어져야 함

 

 

l  임계 구역 문제 해결하기 위한 조건

상호 배제 ( Mutual Exclusion )	한 프로세스가 임계구역에 들어가 있으면 다른 프로세스 들어갈 수 없다.
진행 ( Progress )	임계구역에 들어간 프로세스 없다면 어느 프로세스가 들어갈 지 적절히 선택
한정 대기 ( Bounded Waiting )	기아 방지를 위해 한 번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한을 준다.

 

 

l  스핀락 ( Spin Lock ) : 계속 돌면서 확인

 

◾  개요

다른 스레드가 락을 소유하고 있다면 그 락이 반환될 때 까지 확인하며 기다렸다가

사용가능하면 바로 처리하도록 하는 개념 ( Busy Waiting ) ~ while문 안에서 대기

 

◾  장점

락이 해제될 때 스레드 문맥 교환이 없어서 오버헤드 없이 임계 구역 접근 가능함

따라서 임계 영역이 아주 작거나 빠른 처리가 가능할 때 유용

 

◾  단점

어떤 스레드가 락을 오래 소유한다면 CPU시간 낭비하게 됨

단일 CPU,코어 에서는 어차피 락을 풀기 위해서 문맥 교환 일어나므로 유용하지 않음

 

◾  언제 사용하는 것이 좋은가

다중 스레드에서 임계 구역이 아주 작거나 빠른 처리 가능할 때

 

 

l  상호 배제, 뮤텍스 (Mutually Exclusive) : 화장실이 하나 뿐인 식당, 열쇠 1개

 

◾  개요

여러 프로세스/스레드가 공유된 자원에 접근하는 것을 막는 것

여러 프로세스가 공유 자원 사용하려 할 때 번갈아 가며 사용하도록 함

 

임계 구역 내에서 인터럽트, 교착상태, 무한반복 발생하지 않도록 해야 함

키가 1개인 세마포어라고 볼 수 있다.

커널 모드 동기화 객체이다.

 

◾  소프트웨어적 구현 방법

•  2개 프로세스 기준 : 데커 알고리즘, 피터슨 알고리즘

•  여러 개 프로세스 기준 : Lamport의 빵집 알고리즘

 

 

l  데커 알고리즘

상호 배제를 위한 병행 프로그래밍 알고리즘

검사 및 조정(test-and-set) 명령과 같은 원자적 명령이 없는 경우에도 사용 가능

바쁜 대기(busy waiting) 알고리즘에 속함

두 프로세스가 동시에 임계 영역에 들어가려고 할 때 하나만 들어가게 함

f0과 f1 두 개의 플래그(각각 임계영역에 들어갈 의향, 두 프로세스 사이의 우선권을 나타낸다)를 사용하여 구현할 수 있다.

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%BB%A4%EC%9D%98_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

l  피터슨 해결안

상호 배제를 위한 병행 프로그래밍 알고리즘

동기화 문제를 해결하기 위해서 flag와 turn 두 개의 변수를 사용하는데

turn은 임계 구역에 들어갈 프로세스의 번호

flag는 프로세스가 임계 구역에 들어갈 준비 되었음을 의미

https://ko.wikipedia.org/wiki/%ED%94%BC%ED%84%B0%EC%8A%A8%EC%9D%98_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

l  램포트의 빵집 알고리즘

상호 배제를 통해 여러 스레드 간에 공유 리소스를 사용할 때 안전성을 향상시키기 위한 알고리즘

빵집에서 각 고객에게 고유 번호를 부여, 모든 고객은 현재 고객에게 서비스 제공하고 다음 번호가 표시될 때 까지 대기열에서 대기, 고객이 쇼핑 마치면 직원은 번호를 증가시켜 다음 고객에게 서비스 제공, 재구매를 하기 위해서는 다른 번호표 가져와야 함

https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm

 

 

 

l  세마포어 (Semaphore) : 화장실이 여러 개 있는 레스토랑, 열쇠 = 칸 개수 만큼

 

◾  개요

현재 공유자원에 접근할 수 있는 프로세스/스레드 수를 나타내는 값을 두어 상호배제

 

Lock시 특정 수만큼의 카운트를 더하고

Unlock시 빼주는 형식으로 처리

이런 락을 슬립( Sleep ) 가능한 락이라고 함

동기화 해야 하는 대상이 여러 개일 때 사용

 

◾  종류

 

•  카운팅(계수) 세마포어 ( Counting Semaphore )

 

P, V라는 2개의 연산에 의해서 동기화 유지

S는 P와 V 연산으로만 접근 가능한 세마포어 변수로 공유 자원의 개수를 나타내며

0과 1 혹은 0과 양의 값을 가질 수 있다.

 

P는 try, V는 increment를 뜻 하는 네덜란드어에서 따왔다. S는 Source인듯?

 

P 연산 : 자원의 개수(S = S-1)를 감소시켜 점유되었음을 알림(Wait)

V 연산 : 자원의 개수(S = S+1)를 증가시켜 자원이 반납되었음을 알림(Signal), 0이 되면 모두 사용중임을 나타냄

 

P(s) = wait(s) { while(s<=0) s--; };

V(s) = signal(s){ s++;};

 

 

•  이진 세마포어 ( Binary Semaphore )

 

세마포어 값으로 0 또는 1을 가진다.

계수 세마포어보다 간단히 구현할 수 있으며,

Test and Set 등 하드웨어가 지원하는 기능을 이용하여 구현하기도 한다. 

또한, 이진 세마포어를 이용하여 계수 세마포어를 구현할 수도 있다.

 

 

---

모니터

동기화를 구현하기 위한 특수 프로그램 기법

특정 공유 자원을 프로세스에게 할당하는 데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성

자료 추상화, 정보 은폐 개념을 기초, 병행성 구조

 

모니터 내의 공유 자원을 이용하려면 프로세스는 반드시 모니터의 진입부를 호출

외부의 프로시저는 직접 접근할 수 없으며, 모니터의 경계에서 상호 배제가 시행

한 순간에 하나의 프로세스만 진입하여 자원 사용 가능

 

 

---

교착 상태 ( DeadLock )

데드락

 

◾  개요

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에

결과적으로 아무것도 완료되지 못하는 상태

 

다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제

 

◾  교착 상태의 필요 조건

조건	설명
상호배제 (Mutual Exclusion)	한 번에 한 프로세스만 공유 자원 사용
비선점 (Hold And Wait)	다른 프로세스에 할당된 자원은 그 프로세스가 종료될 때 까지 뺏을 수 없다.
점유하며 대기 (Non-Preemptive)	최소 하나의 자원을 점유한 상태로 다른 프로세스에 할당된 자원을 추가 점유하기 위해 대기
순환 대기 (Circular Wait)	공유 자원을 사용하기 위해 대기하는 프로세스들이 T1(A->B), T2(B->C), T3(C->A) 와 같이 원형으로 물려있는 상태 할당된 자원을 점유하면서 앞 또는 뒤의 프로세스 자원을 서로 요구한다.

 

l  예방 기법 ( Prevention )

 

   다음의 4가지 조건 중 하나라도 만족하지 않으면 교착 상태는 일어나지 않는다.

조건	해결법 ( 조건 부정 )	문제
상호배제 ( Mutual Exclusion )	공유를 하자 혹은 싱글 스레드나 공유 데이터 없도록	동시에 사용하니 엉망이 된다.
비선점 ( Non-Preemptive )	선점 하자, 걸려있는 락을 해제	기아, 무기한 대기 등의 새로운 문제
점유하며 대기 ( Hold And Wait )	대기하지 말고 작업 수행 전에 필요한 자원을 한번에 다 줘 혹은 자원을 전혀 갖고 있지 않을 때만 자원 요청할 수 있도록 허용	자원 낭비가 심하다. 기아, 무기한 대기 등의 새로운 문제
순환 대기 ( Circular Wait )	자원에 순서를 부여하여 한 방향으로만 요청할 수 있도록	사이클 고려하며 짜야해서 프로그램을 옳게 짤 수 없다.

 

◾  결론 : 어떠한 방법도 근본적으로 해결이 안된다.

중간중간 확인하여 교착상태에 걸리면 빠져나오게 해야함

 

 

l  회피 기법 ( Avoidance )

   교착상태가 발생할 가능성을 배제하지 않고, 교착상태가 발생하면 회피하는 방법

 

◾  자원 할당 그래프 알고리즘 ( Resource Allocation Graph Algorithm )

 

◾  은행원 알고리즘 ( Banker's algorithm )

   은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법

   프로세스가 자원을 요구하는 시점에 자원 할당해도 안전한지 검사하여 교착 상태 회피

 

안전 상태 : 모든 프로세스가 완료될 수 있는 상태

불안전 상태 : 교착 상태가 발생할 수 있는 상태

 

 

l  발견 기법 ( Detection )

   시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원 발견

 

l  회복 기법 ( Recovery )

   교착상태를 일으킨 프로세스 종료하거나 할당된 자원을 선점하여 프로세스 자원 회복

 

l  무시 기법

   교착 상태가 거의 무시해도 좋을 확률로 일어난다고 판단될 때 무시하는 기법

   왜냐하면 교착 상태를 해결하기 위해 성능상 손해를 보기 때문에 차라리 무시하는 게 나을 때도 있다.

 

 

---

메모리 관리 전략

여러 프로세스들이 동시에 주 메모리를 공유하는 상황에서 어떻게 관리할 것인가

 

l  논리 대 물리 주소 공간

CPU가 생성하는 주소를  논리주소, 메모리가 취급하는 주소를 물리주소

매번 주소를 더해주면 번거로우니 재배치 레지스터가 위치를 잡아주고

0번부터 넣자 (0+500, 1+500 ... X) -> (500 - 0,1,2,3 ... O)

 

CPU -논리주소-> 재배치 레지스터 -물리주소->메모리

Binding Time = Load Time (적재할 때 바꿔줌)

 

 

 

l  메모리 관리 기법 종류

 

◾  반입 전략 (Fetch Policy) 

When 보조 기억장치에서 주기억장치로 언제 적재할 것인가?

 

•  요구 반입

실행 중인 프로그램이 특정 프로그램, 데이터 등의 참조를 요구할 때 적재

 

•  예상 반입

실행 중인 프로그램에 의해 참조될 프로그램이나 데이터 미리 예상하여 적재

 

 

◾  배치 전략 (Placement Policy) 

Where 새로 반입되는 프로그램, 데이터를 주기억장치의 어디에 위치시킬 것인가?

 

총 60k ( A 10k, B 20k, C 30k )

자기 크기에 맞게 들어가려하니 문제점 발생

1) 큐가 각각 다 있어야함.

2) 우연히 비어있는데 못 들어가는 경우 생김

 

•  최초 적합 (First Fit) : 들어갈 수 있는 빈 영역 중에서 첫 번째 분할 영역에 배치

•  최적 적합 (best Fit) : 단편화를 가장 작게 남기는 분할 영역에 배치

•  최악 적합 (Worst Fit) : 단편화를 가장 많이 남기는 분할 영역에 배치

 

 

◾  교체 전략 (Replacement Policy) 

Who 주기억장치의 모든 영역이 이미 사용중인 상태에서 새로운 프로그램,

데이터를 배치하려 할 때 어느 영역을 교체할 것인가?

FIFO, OPT, LRU, LFU NUR, SCR 등이 있다.

 

 

l  연속 메모리 할당 방식

 

◾ 단일 사용자 연속 메모리 할당

◾  고정분할 다중프로그래밍 (MTF)

◾  가변분할 다중프로그래밍 (MVT)

◾  중첩(Overlay)

 

 

l  분산 메모리 할당 방식

 

◾  페이징

◾  세그먼트

 

---

스와핑

주기억장치에 적재한 하나의 프로세스와 보조기억장치에 적재한 다른 프로세스의 메모리를 교체하는 기법

 

프로세스가 여러 개 실행 되는 경우 메모리가 부족할 수 있다

그래서 실행 중인 프로세스를 예비 저장장치에 보냈다가 실행할 때 다시 메모리로 올리는 기법

이는 가상 메모리 관리 기법인 페이징 기법으로 발전했다.

 

 

---

메모리 단편화

공간의 일부가 사용하지 못하게 되는 부분이다.

분할된 주기억장치에 프로그램을 할당하고 반납하는 과정에서

메모리의 공간이 작은 조각들로 나뉘어져 가용 공간이 줄어들거나, 읽기/쓰기 속도를 느리게 하는 것.

 

 

l  종류

 

•  내부 단편화

메모리를 할당할 때 프로세스가 필요한 양보다 더 큰 메모리가 할당되어서

메모리 공간이 낭비 되는 것

 

•  외부 단편화

분할된 영역이 할당될 프로그램의 크기보다 작아서 할당되지 못하고 빈 공간으로 남아 있는 것으로 총 메모리 공간은 충분하지만 실제로는 할당할 수 없는 상황

 

 

l  해결 방법

 

•  통합(Coalescing) 기법

인접해 있는 단편화된 공간을 하나의 공간으로 통합

 

•  압축(Compaction) 기법, 집약

분산되어 있는 단편화된 빈 공간을 결합하여 하나의 큰 가용 공간 만드는 작업

프로세스들의 재배치가 런타임에 동적으로 이루어지는 경우 가능, 비용많이 든다.

외부 단편화 해결

 

•  세그먼테이션, 페이징 기법

 

 

---

가상 기억장치

용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법

 

보조기억장치의 일부를 주기억장치처럼 사용하는 것으로

1.     주기억장치 용량보다 큰 프로그램 실행하기 위해 사용

2.     가상 기억장치의 주소를 주기억장치의 주소로 바꾸는 주소 변환 작업이 필요

3.     블록 단위로 나누어 사용하므로 단편화 문제 해결 가능

4.     주기억장치의 이용률과 다중 프로그래밍 효율 높일 수 있다.

 

 

l  주소 변환 (주소 사상, 주소 매핑)

   가상 기억장치에 있는 프로그램이 주기억장치에 적재되어 실행될 때

   논리적인 가상주소를 물리적인 실기억주소로 변환하는 것

 

 

 

---

가상메모리 관리 기법

 

페이징 기법

가상기억장치를 같은 크기의 블록인 페이지로 나누어 운용하는 기법

 

물리 메모리를 페이지와 같은 크기로 나눈 페이지 프레임에 페이지를 적재시켜 실행한다.

주소 변환을 위해 페이지 위치 정보를 가진 페이지 맵 테이블 필요

 

◾  외부 단편화 해결

사용하지 않는 프레임을 페이지에 옮기고, 필요한 메모리를 페이지 단위로 프레임에 옮기는 기법으로

연속적이지 않은 공간도 활용할 수 있으므로 외부 단편화 해결

 

◾  내부 단편화는 여전히 발생 가능

 

 

◾  가상/논리 주소 V (p,d)

p는 가상 기억장치 내에서 참조될 항목이 속한 페이지 번호

d는 페이지 p 내에서 참조될 항목이 위치한 변위이다.

 

◾  페이지 사상 테이블 (PMT)

 

페이지 번호

물리 메모리(프레임)의 시작 주소(base)

플래그 비트

페이지 정보를 저장하고 있으며, 하나의 프로세스는 하나의 페이지 테이블 가진다.

주기억 장치(RAM)에 상주한다.

 

•  페이지 테이블 엔트리 (PTE)

페이지 테이블의 개별 매핑 데이터 (레코드)이다. 

 

•  플래그 비트

1) 접근 비트 : 페이지의 접근이 있었는지 나타냄

2) 변경 비트 : 페이지의 변경이 있었는지 나타냄

3) 현재 비트 : 현재 페이지에 할당된 프레임이 있는지 나타냄

4) 읽기/쓰기 비트 : 읽기/쓰기에 대한 권한을 표시

 

 

◾  사상 기법

논리 -> 물리 주소 변환 과정에서 다음의 페이지 사상 기법들이 있다. 

•  직접 사상 (Direct Mapping) 

페이지 테이블을 주 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR)가 가리키도록 하는것 
모든 페이지 항목이 페이지 사상 테이블에 포함 
페이지 사상 테이블을 참조하면 바로 해당 위치로 이동 

물리 주소 a = base[p] + d 

단점
페이지 테이블에 접근하여 페이저 번호를 프레임 번호로 바꾸고, 
변위를 더하여 주소를 알아내서 메모리에 접근해야 되기 때문에 2번의 접근이 일어남 
그래서 메모리 접근시간이 오래걸린다.

 

 

•  연관 사상 (Associate Mapping) 

주소 변환을 주기억장치보다 빠른 TLB(연관 메모리로 구성된 특수한 소형 하드웨어 캐시)에 넣어서 수행 

장점 
찾고자 하는 Key를 동시에 여러 Key의 키와 비교 
병렬처리가 되기 때문에 매우 빨라서 성능에 손해가 없다. 

단점 
대신 가격이 매우 비싸서 페이지 사상 테이블 전체를 TLB에 설치하는 것은 부담된다. 

  
•  직접, 연관 사상 혼용 기법 

자주 사용하는 PMT는 연관 메모리에 넣고 나머지는 주기억장치에서 운용, 관리하는 기법이다. 
처음에는 연관 사상 실행 후 없으면(TLB miss) 직접 사상 실행

◾  TLB miss 
페이지 번호가 TLB를 찾아가지 않은 경우로 일반 메모리에 접근하게 됨. 
이 경우에는 TLB에 새롭게 등록되어 다음 참조에 빠르게 처리할 수 있음 

◾  TLB REACH 
TLB로부터 액세스 할 수 있는 메모리 공간 = TLB에 있는 항목 수 x 페이지 크기 

 

 

◾  효율적인 페이징 방법

요구 페이지(필요할 때만 적재)를 사용하여 시간적 공간적 낭비를 줄인다.

대신에 프로세서가 메모리에 올라와있지도 않은 페이지 접근시 페이지 부재가 발생

이 페이지 부재가 많이 발생하면 성능이 저하되므로 페이지 부재율을 낮게 유지

 

 

 

◾  페이지 크기

 

•  페이지 크기가 작을 경우

페이지의 단편화 감소, 한 개의 페이지를 주기억장치로 이동시키는 시간 줄어듦

필요한 내용만 적재할 수 있고 국부성(Locality)에 더 일치할 수 있어 효율 증가

페이지 맵 테이블 크기가 커지고 매핑 속도 늦어짐

디스크 접근 횟수가 많아져서 전체적인 입출력 시간 늘어남

 

•  페이지 크기가 클 경우

페이지 단편화 증가, 한 개의 페이지를 주기억장치로 이동시키는 시간 늘어남

프로그램 수행에 불필요한 내용까지 적재될 수 있음

페이지 맵 테이블 크기가 작아지고 매핑 속도 빨라짐

디스크 접근 횟수 줄어들어 전체적인 입출력 효율 증가

 

 

◾  페이지 테이블의 구조

 

•  계층적 페이징 (Hierarchical Paging) 2단계 페이징 기법 (tow-level paging scheme)

페이지 테이블 자체가 다시 페이지화 - 필요 메모리양은 줄지만 속도가 느려짐

 

 

•  해시 페이지 테이블

주소 공간이 32bit보다 크면 해시 값이 가상 페이지 번호가 되는 해시형 페이지 테이블을 많이 쓴다.

각 항목은 연결 리스트를 가지고 있다.

해시 원소는 세 개의 필드 (가상 페이지 번호, 매핑 페이지 프레임 번호, 다음 포인터)

 

1)    가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱

2)    해시형 페이지 테이블에서 연결리스트 따라가며 첫 번째 원소와 가상 페이지 번호 비교

3)    일치하면 그에 대응하는 프레임 번호를 가져와 물리적 주소를 얻는다.

4)    일치하지 않으면 연결 리스트의 다음 포인트로 3)을 반복

 

+ 클러스터형 페이지 테이블

해시형 페이지에서 각 항목들이 한 개의 페이지만 가리키는데

64bit에서는 해시 알고리즘을 변형하여 클러스터형 페이지 테이블이라고

여러 개의 페이지를 가리키도록 한다.

메모리 접근이 불연속적이면서 주소 공간으로 넓게 퍼져 나오는 경우 유용

 

+ 해싱 (Hasing)

Key를 Hash Function으로 계산한 값으로 Value를 찾는 방법으로

찾을 때와 넣을 때의 Hash Function은 같아야함

찾을 땐 Linear Search, Binary Search

문제점 : 충돌 가능성이 있다는 것(같은 주소값이 나오는 경우)

해결법 :

1) Liner방식 : 다음 번지의 빈곳으로 한칸씩 밀어냄

2) Linked List 방식 : 다음 공간을 가리키도록

3) Overflow 공간 : 별도의 공간으로

 

 

•  역 페이지 테이블 (Inverted Page Table)

프레임마다 한 항목(Pid : 페이지 소유한 프로세스 ID, P : 페이지 주소)씩 할당한다.

시스템에는 단 하나의 페이지 테이블만 존재, 테이블 내 각 항목은 한 프레임 가리킴

용량이 줄어들지만 변경 사항이 있을 때마다 업데이트 하기 때문에 속도가 줄어든다.

 

구성 순서

1)     가상 주소는 <Pid, Page-number, Offset> 세 항목으로 구성

2)     역 페이지 테이블의 각 항목은 <Pid, Page-number> 쌍으로 이루어져 있으며

Pid는 주소 공간 ID의 역할을 한다.

3)     메모리 참조 발생하면 <Pid, Page_number> 쌍으로 이루어진 가상 주소의

일부 메모리 서브시스템에 전달

4)     역 페이지 테이블에서 일치하는 것이 있늕 검색

5)     일치하는 것이 i번째 항목에서 발견되면 물리 주소는 <i, offset>가 되고

6)     일치하는 것이 없으면 잘못된 메모리로 간주

 

장점

논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만

테이블에 저장하기 때문에 메모리 적게 차지

 

단점

주소 변환 시간이 더 오래 걸릴 수 있으며 프레임에 따라 저장되어 있어

탐색은 비효율적

 

역 페이지 테이블을 사용하는 시스템에서 메모리 공유는 어렵다.

페이지 테이블이 공유된 물리 주소에 대해 하나의 가상 주소를 매핑하기 때문에

매핑 되지 못한 다른 가상 주소가 공유된 영역을 참조하게 되면 페이지 부재 발생

 

페이지 테이블 해싱이 느린경우 최근 사용된 항목을 TLB 연관메모리 레지스터에

저장시켜서 다음 참조 시 레지스터만 검사하면서 시간 단축을 할 수 있다.

 

 

※ 하드웨어 지원 (위의 내용을 요약)

1.     페이지를 레지스터에게 주자 - 가장 빠름 가장 비쌈

2.     페이지를 일반메모리에게 주자 - 가장 느림 가장 쌈

3.     페이지를 고속의 메모리(연관 메모리 = 병렬처리가 되는 메모리)에게 주자 - 비싸지만 나름 빠르다.

자주 쓰이는 것을 연관메모리에, 잘 안쓰는것을 일반 메모리로 !

연관 메모리는 1번, 내 메모리 1번 해서 2번을 찾지만

연관 메모리는 찾는데 0초에 가깝기 때문에 1번이나 마찬가지임.

 

 

 

 

---

메모리 풀

메모리 공간을 미리 할당 받아놓고 필요할 때마다 사용하고 반납하는 기법

내부, 외부 단편화 모두 해결, 자칫 잘못하면 메모리 누수가 생길수도 있음

 

 

---

워킹 셋

프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합

구역성 (Locality) 특징을 이용한다.

자주 참조되는 워킹 셋을 주기억 장치에 상주시킴으로써 페이지 부재, 교체 현상 줄임

시간에 따라 워킹 셋 바뀜

 

 

---

세그먼테이션 기법

 

가상 메모리를 가변 크기의 논리적 단위인 세그먼트로 분할하여 주기억장치에 적재시켜 실행시키는 기법

 

주소 변환을 위해 세그먼트 위치, 크기 정보를 가지고 있는 세그먼트 맵 테이블 필요

페이징 기법보다 공유 시스템이 간단하다. 단순히 공유한다고 선언하기만 하면됨

 

 

l  논리 주소  V (s, d) 

세그먼트 번호, 변위 비트로 이루어진다. 

 

l  세그먼트 테이블

세그먼트 번호

시작 주소(base)

세그먼트 크기(limit)

세그먼트 번호를 토대로 테이블 내용으로 들어가 시작 위치, 한계 값을 파악 

한계 값은 세그먼트 크기가 일정하지 않기 때문에 세그먼트 크기 넘어서는 주소 들어오면 처리하기 위해 존재

 

l  물리 주소  a =  base[s] + d
물리주소 = 시작 위치 + 변위 

 

 

l  보호와 공유

보호 : r,w,x 비트를 테이블에 추가한다. 논리적으로 나누기 때문에 영역이 섞이지 않아 매우 간단하고 안전 
공유 : 정확히 code인 영역만 나누어서 효율적

 

l  장점

보호와 공유가 효율적이다.

메모리를 필요한 만큼 사용하므로 내부 단편화 해결

 

l  단점

외부 단편화 발생 가능

평균 세그먼트 크기 작을수록 외부 단편화 작음

메모리 압축 기법이나 동적 대치 알고리즘 활용하여 외부 단편화 최소화 가능

 

 

3.     페이지화된 세그먼테이션 (Paged Segmentation)

페이징과 세그먼테이션 장점을 취합한 것

세그먼트 안에 별도의 페이지 테이블이 존재

 

l  논리주소

세그먼트 번호/페이지 번호/오프셋

 

l  장점

외부 단편화 문제를 해결한다.

 

l  단점

분할 공간이 많아져 메모리 관리 힘들어짐

주소 변환을 두번 해야한다.

 

 

 

 

 

---

페이지 부재

참조할 페이지가 주기억장치에 없는 현상

 

페이지 부재 빈도 (PFF : Page Fault Frequency)

페이지 부재가 일어나는 횟수를 의미

 

페이지 부재율 (Page Fault Rage)에 따라 페이지 프레임 수 늘리거나 줄여서 부재율을 적정 수준으로 유지

 

 

 

---

페이지 교체 알고리즘

페이지 부재 발생 시 필요한 페이지를 주기억장치에 적재해야 하는데

모든 페이지 프레임이 사용 중이면 어떤 페이지 프레임을 선택하여 교체할지 결정하는 기법

 

1. 희생될 페이지 내보냄

2. 유효비트를 V->I 로 수정

3. 원하는 페이지 가져옴

4. 페이지 테이블 수정

 

1.     최적 교체 OPT (OPTimal Replacement)

앞으로 가장 오랫동안 사용하지 않을 페이지 교체

각 페이지의 호출 순서와 참조 사항을 미리 예측해야 하므로 실현 가능성 낮음

 

2.     FIFO (First In First Out)

먼저 적재된 순서대로 교체하는 기법

벨레이디의 모순 : 페이지 프레임 수가 많으면 페이지 부재가 줄어들어야 하는데

더 많은 페이지 프레임을 할당하더라도 페이지 부재가 더 많이 발생함

 

3.     LRU (Least Recently Used)

최근에 가장 오랫동안 사용되지 않은 페이지를 교체하는 기법

페이지마다 계수기나 스택을 두어 가장 오래 전에 사용된 페이지를 교체

 

l  계수기

각 페이지당 가지는 논리적 시계

페이지가 사용될때마다 0으로 클리어하고 시간이 가장 오래된 페이지 교체

 

페이지를 BCBAD 순서로 참조할 때, 캐시 HIT, MISS를 구하시오.

페이지 프레임 = 3

 

순서	B	C	B	A	D
	B	B	B	B	B
		C	C	C	D
				A	A
HIT			1	1	1
MISS	1	2	2	3	4

꼭 마지막 Hit + Miss 값이 전체 개수와 동일한가 확인해보도록 ( 1 + 4 = 5)

 

 

이것을 다음과 같이 재정렬하며 풀면 이해하기 쉽다.

 

1) MISS된 경우 나머지를 아래로 밀고 1순위로 넣는다.

만약 꽉 찬 상태라면 3순위를 버린다.

 

2) HIT된 경우 빼서 나머지를 아래로 밀고 1순위로 다시 넣는다.

순서	B	C	B	A	D
1위 ( 최근에 추가 )	B	C	B	A	D
2위		B	C	B	A
3위 ( 옛날에 추가 )				C	B
HIT			1	1	1
MISS	1	2	2	3	4

 

 

4.     LRU 근사 페이지 교체 (LRU Approximation Page Replacement)

LRU는 하드웨어 오버헤드가 크기 때문에 개선한 방식

 

5.     부가적 참조비트 알고리즘

일정 주기로 참조 비트를 기록함으로써 추가적인 선후 관계 정보를 얻을 수 있다.

이 정보를 통해 가장 오랫동안 쓰이지 않은 페이지 교체

 

6.     2차 기회 알고리즘 SCR (Second Change Replacement)

FIFO 교체 알고리즘으로 참조비트가 0이면 교체, 1이면 기회를 한번 주는것으로

모든 비트가 1이되면 모두 0으로 리셋시킨다.

가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것

 

7.     개선된 2차 기회 알고리즘

CPU가 페이지를 한 번이라도 쓰게 되면 설정되는 변경비트를 함께 사용

참조비트와 변경비트를 조합하여 사용하는 방법으로

0          0  = 최근에 사용되지도 변경되지도 않은 경우로 (1순위)

0          1  = 교체시 디스크에 내용을 기록해야 하므로 우선순위 밀림 (2순위)

1          0  = 이 페이지는 곧 다시 사용할 가능성이 높다. (2,3순위)

1          1  = 곧 다시 사용될 가능성이 높음, 교체시 디스크에 내용 기록 (4순위)

페이지가 어떤 등급에 속하는지 확인하여

가장 먼저 만나는 가장 등급이 낮은(0,0) 페이지를 교체시킨다.

 

 

계수 기반 페이지 교체

---------------------------------------------------

8.     LFU (Least Frequently Used)

사용 빈도가 가장 적은 페이지를 교체하는 기법

실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않은 경우에도

프레임을 계속 차지할 수 있음

 

9.     MFU (Most Frequently Used)

가장 작은 참조 회수를 가진 페이지가 가장 최근에 적재되었고 앞으로 계속 사용될 것이라는 판단에 근거

---------------------------------------------------

10.  NUR (Not Used Recently)

최근에 사용하지 않은 페이지를 교체하는 기법

최근 사용 여부를 확인하기 위해 각 페이지 마다 2개의 비트 사용

참조 비트, 변형 비트를 사용한다.

비트가 1이면 true

 

 

※ LRU 와 NUR의 차이는?

둘 다 가장 오래 쓰이지 않은 페이지 교체한다.

LRU는 스택과 계수기 같은 하드웨어가 필요하고, 오버헤드 발생

NUR은 최근에 사용되지 않은 페이지는 이후에도 사용되지 않을 가능성이 높다는

전제를 통해 참조, 변형 비트 2개를 사용하여 오버헤드 줄인다.

 

 

 

---

국부성, 구역성 (Locality)

 

프로세스가 실행되는 동안 주기억장치를 참조할 때

일부 페이지만 집중적으로 참조한다는 성질이 있다는 이론

 

스레싱을 방지하기 위한 워킹 셋 이론의 기반

캐시 메모리 시스템의 이론적 근거

가상 기억 장치 관리의 이론적인 근거

 

l  종류

 

1.     시간 구역성

하나의 페이지를 일정 시간 동안 집중적으로 접근하는 현상

한 번 참조한 페이지는 가까운 시간 내에 계속 참조할 가능성이 높음을 의미

반복 순환, 스택, 부프로그램, 카운팅, 집계 등에 사용되는 변수(기억 장소)

 

2.     공간 구역성

일정 위치의 페이지를 집중적으로 접근하는 현상

배열 순회 : 관련된 변수를 서로 근처에 선언하여 할당되는 기억 장소

 

 

 

---

스레싱 (Thrashing)

프로세스 처리 시간 보다 페이지 교체 시간이 더 많아지는 현상

 

다중 프로그래밍 시스템, 가상 기억장치 사용하는 시스템에서 자주 발생

필요한 페이지 수보다 할당된 프레임수가 더 적을 경우나 지역 페이지 교체 방법이 사용될 때 발생한다.

 

l  해결 방법

1)     다중 프로그래밍 정도를 적정 수준으로 유지

2)     페이지 부재율 조절 ~ 페이지 프레임 수 조절

3)     워킹 셋 유지

4)     일부 프로세스 종료

 

 

 

---

디스크 스케줄링

데이터가 디스크의 여러 곳에 저장된 경우, 

데이터에 접근하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법

 

 

l  목적

처리량 극대화, 평균 응답 시간 최소화, 응답 시간 편차의 최소화

 

 

l  종류

 

1.     FCFS (First Come First Servie)

먼저 들어온 트랙에 대해 먼저 서비스

공평성이 보장

 

2.     SSTF (Shortest Seek Time First)

탐색 거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스

가장 가까운 거리에 있는 트랙으로 헤드를 이동

FCFS보다 처리량 많고 평균 탐색 시간 짧음, 일괄 처리에 유용

 

3.     SCAN

SSTF가 갖는 탐색 시간의 편차를 해소하기 위한 기법

헤드의 진행 방향이 결정되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청 서비스하고, 끝까지 이동한 후 역방향의 요청 서비스

 

4.     C-SCAN (Circular SCAN)

항상 바깥쪽에서 안쪽으로 이동하면서 가장 짧은 탐색 거리를 갖는 요청 서비스

헤드는 바깥쪽에서 안쪽으로 한 방향으로만 움직이며 더 이상의 요청 없으면 가장 바깥쪽으로 이동

 

5.     N-Step SCAN

SCAN 기법의 무한 대기 발생 가능성을 제거한 것

방향의 진행이 시작될 당시 대기 중이던 요청 서비스

진행 도중 도착한 요청은 모아서 다음 반대 방향 진행 때 서비스

 

6.     에션바흐 (Eschenbach)

헤드가 진행하는 과정에서 각 실린더에 대해 디스크 팩의 한 회전 시간 동안만

입 출력 요구들을 처리

부하가 매우 큰 항공 예약 서비스를 위해 개발

탐색 시간과 회전 지연 시간을 최적화

 

7.     SLTF (Shortest Latency Time First) = 섹터 큐잉 (Sector Queuing)

회전 시간의 최적화를 위해 구현된 기법

디스크 대기 큐에 있는 요청을 섹터 위치에 따라 재정렬하고,

가장 가까운 섹터를 먼저 서비스

헤더의 이동이 거의 없는 고정 헤더 장치 ‘드럼’ 같은 장치에서 사용

 

8.     LOOK

SCAN 기법을 기초로 사용하되 진행 방향의 마지막 요청을 서비스한 후

그 방향의 끝으로 이동하지 않고 바로 역방향으로 진행

 

 

 

---

파일 / 파일 시스템

l  파일

사용자가 작성한 서로 관련 있는 레코드의 집합체

프로그램 구성의 기본 단위, 보조기억장치에 저장

위치, 크기, 작성 시기 등 여러 속성 가짐

 

l  파일 시스템

파일의 저장, 접근, 공유, 보호 등 보조기억장치에서 파일을 총괄하는 파일 관리 기술

사용자와 보조기억장치 사이 인터페이스 제공

파일을 생성, 수정, 제거, 공유할 수 있게 해줌

예비, 복구 등의 기능 제공

암호화, 해동 기능 제공

 

l  파일 디스크립터 (File Descriptor) = 파일 제어 블록 FCB

  파일 관리하기 위해 시스템이 필요로 하는 파일 정보를 갖는 제어 블록

보통 보조기억장치에 저장되어 있다가 파일이 Open될 때 주기억장치로 옮겨짐

파일마다 독립적으로 존재, 시스템에 따라 다른 구조 가질 수 있다.

사용자가 직접 참조 불가

 

정보 : 파일 위치, 구조, 유형, 권한, 크기, 생성 날짜/시간, 접근 횟수 등

 

 

 

---

파일 할당 방법

1.     연속 파일, 순차 파일 (Sequential File)

레코드를 논리적인 처리 순서에 따라 연속된 물리적 저장공간에 기록

각 파일이 디스크에서 연속적인 공간을 차지

 

l  장점

1)     파일 구성 용이

2)     공간 효율 높음

3)     처리 속도 빠름

4)     어떤 기억 매체에서도 실현 가능

 

l  단점

1)    파일에 새 레코드 삽입/삭제하는 경우 전체를 복사한 후 수행해야 하므로 느림

2)    검색 효율이 낮고, 접근 시간, 응답 시간이 느림

 

 

2.     연결할당

파일이 저장되는 공간이 연결리스트로 되어 있음

 

l  문제점

1) 직접접근은 매우 비효율적이다.

2) 포인터를 위한 공간이 필요

3) 신뢰성의 문제(하나 잃어버리면 다 날아감)

 

 

3.     색인 순차 파일 (Indexed Sequential File = ISAM = Index Sequential Access Method)

색인을 이용한 순차적인 접근 방법을 제공

레코드를 키 값 순으로 논리적으로 저장, 시스템은 각 레코드의 실제 주소가 저장된 색인 관리

레코드를 참조하려면 색인 탐색 후 색인기 가리키는 주소를 통해 직접 참조가능

 

l  구성

기본 영역 (Prime Area)

색인 영역 (Index Area) : 트랙 색인 영역, 실린더 색인 영역, 마스터 색인 영역

오버플로 영역 (Overflow Area)

 

l  장점

순차, 임의처리 모두 가능

효율적인 검색 가능

삽입, 삭제, 갱신이 용이

 

l  단점

색인, 오버플로 처리를 위한 추가 공간 필요

접근시간이 직접 파일보다 느림

 

 

4.     직접 파일, 직접 접근방식 (Direct File)

파일을 구성하는 레코드를 임의의 물리적 공간에 기록

레코드에 키가 할당되며, 해싱 함수를 통하여 물리적 상대 레코드 주소를 계산하고

해당 하는 주소에 레코드를 저장

 

레코드는 해싱 함수에 의해 계산된 물리 주소를 통해 직접 접근 가능

 

l  장점

파일의 각 레코드에 직접 접근하거나 기록 가능

접근 시간 빠름

삽입, 삭제, 갱신이 용이

 

l  단점

레코드의 주소 변환 과정 필요

이 과정으로 인해 시간 소요, 기억공간 효율 저하

 

 

 

---

디렉터리

파일 시스템 내부에 있는 것으로, 디스크에 존재하는 파일에 대한 여러 정보를 가진 특수한 형태의 파일

 

 

l  구조

 

1.     1 단계 디렉터리

가장 간단하고 모든 파일이 하나의 디렉터리 내에 위치하여 관리됨

모든 파일들이 유일한 이름 가짐

파일의 수나 사용자 많아지면 관리 복잡

 

2.     2 단계 디레겉리

중앙에 마스터 파일 디렉터리 (MFD)가 있고

그 아래에 사용자별로 서로 다른 파일 디렉터리 (UFD)가 있는 2 계층 구조

서로 다른 디렉터리에서는 동일 이름 파일 사용 가능

 

3.     트리 디렉터리

하나의 루트 디렉터리와 여러 개의 서브 디렉터리로 구성

DOS, Windows, UNIX 등에서 사용됨

동일 이름의 파일이나 디렉터리 생성 가능

디렉터리 생성 파괴가 비교적 용이

 

4.     비순환 그래프 디렉터리

하위 파일이나 하위 디렉터리를 공동으로 사용가능

사이클이 허용되지 않아 하위 디렉터리가 상위 디렉터리나 파일 공유 못함

하나의 파일이나 디렉터리가 여러 경로 이름 가질 수 있음

공유된 파일 삭제할 경우 고아 포인터 (Dangling Pointer) 발생 가능

디렉터리 구조 복잡, 공유된 하나의 파일 탐색 시 다른 경로로 두 번 이상 찾아갈 수 있으므로

시스템 성능 저하 가능

 

5.     일반적인 그래프 디렉터리

트리 구조에 링크를 첨가시켜 순환을 허용하는 그래프 구조

디렉터리와 파일 공유에 완전한 융통성 있음

불필요한 파일 제거하여 사용 공간 늘리기 위해서 참조 계수기 필요

 

 

 

---

자원 보호 기법

사용자, 프로세스 등과 같은 주체가 자원에 불법적으로 접근하는 것을 제어하고 손상 예방

 

※ 종류

1.     접근 제어 행렬 (Access Control Matrix)

객체(자원)의 접근 권한을 행렬로 표시한 기법

 

2.     전역 테이블 (Global Table)

가장 단순한 구현 방법으로, 3개의 순서쌍인 영역, 객체, 접근 권한의 집합을 목록 형태로 구성한 기법

 

3.     접근 제어 리스트 (Access Control List)

접근 제어 행렬에 있는 각 열, 즉 객체를 중심으로 접근 리스트를 구성한 기법

 

4.     권한(자격) 리스트 (Capability List)

접근 제어 행렬에 있는 각 행, 즉 영역을 중심으로 구성한 것으로

각 사용자에 대한 자격들로 구성, 자격은 그 객체에 허용된 연산 리스트이다.

 

 

 

 

 

 

---

파일 보호 기법 / 보안 유지 기법

l  파일 보호 기법

파일에 대한 일방적인 접근, 손상,, 파괴를 방지하기 위한 기법

 

종류

1.     파일의 명명 (Naming)

접근하고자 하는 파일 이름 모르는 사용자를 접근 대상에서 제외

2.     비밀번호

파일에 판독 암호와 기록 암호를 부여, 암호를 아는 사용자만 접근 허용

3.     접근 제어

사용자에 따라 공유 뎅터에 접근할 수 있는 권한 제한하는 방법

 

 

l  보안 유지 기법

 

종류

1.     외부 보안

시설 보안 - 천재지변, 외부 침입자로부터 보안

운용 보안 – 전산소 관리, 경영자들의 정책과 통제에 의해 이루어지는 보안

2.     사용자 인터페이스 보안

운영체제가 사용자 신원 확인 후 권한 있는 사용자에게만 사용할 수 있게

3.     내부 보안

하드웨어나 운영체제의 내장된 보안 기능을 이용하여 신뢰성 유지, 보안 문제 해결

 

 

 

---

RAID

메모리를 여러 디스크에 저장하는 기술

 

처음의 목적은 값싼 하드 디스크들을 묶어서 고비용 고효율의 디스크 효과를 내는 것이였으나

메모리 안정성과 손실을 막는것이 중요시되어 Inexpensive -> Independent로 의미가바뀜

 

l  RAID 0

블록 레벨의 스트라이핑을 사용하며 공간효율이 100%지만 고장나면 복구할 수 없다.

 

l  RAID 1

미러링을 사용하여 복사본을 두기 때문에 공간효율이 50%지만 고장나면 복구가 가능하다.

 

l  RAID 5

여러 디스크에 패리티를 나누어 저장하여 하나가 고장나더라도 다른 디스크와 패리티를 이용하여 복구가 가능함.