프로그래머(뉴비)

주기억장치 할당 기법

주기억장치 할당 기법은 프로그램이나 데이터를 실행시키기 위해 

주기억장치에 어떻게 할당할 것인지에 대한 내용이다.

연속 할당 기법

프로그램을 주기억장치에 연속으로 할당하는 기법으로,

단일 분할 할당 기법과 다중 분할 할당 기법이 있다.

단일 분할 할당 기법

 - 단일 할당 기법은 주기억장치를 운영체제 영역과 사용자 영역으로 나누어 한 순간에는

오직 한 명의 사용자만이 주기억자치의 사용자 영역을 사용하는 기법이다.

 - 가장 단순한 기법으로 초기의 운영체제에서 많이 사용하던 기법이다.

오버레이 기법

 - 오버레이 기법은 주기억장치보다 큰 사용자 프로그램을 실행하기 위한 기법이다.

 - 보조기억장치에 저장된 하나의 프로그램을 여러 개의 조각으로 분할한 후 필요한

조각을 차례로 주기억장치에 적재하여 프로그램을 실행한다.

스와핑 기법

 - 스와핑 기법은 하나의 프로그램 전체를 주기억장치에 할당하여 사용하다 필요에 따라 

다른 프로그램과 교체하는 기법이다.

다중 분할 할당 기법

고정 분할 할당 기법

 - 고정 분할 할당은 프로그램을 할당하기 전에 운영체제가 주기억장치의 사용자 영역을

여러 개의 고정된 크기로 분할하고 준비상태 큐에서 준비중인 프로그램을 각 영역에 

할당하여 수행하는 기법이다.

가변 분할 할당 기법

 - 고정 분할 할당 기법의 단편화를 줄이기 위한 것으로, 미리 주기억장치를 분할해 놓는 것이 

아니라 프로그램을 주기억장치에 적재하면서 필요한 만큼의 크기로 영역을 분할하는 기법이다.

상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 

서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

교착상태 발생의 필요 충분 조건

상호배제(Mutual Exclusion)

 - 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

점유와 대기(Hold and Wait)

 - 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 

사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

비선점(Non-preemption)

 - 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야한다.

환형 대기(Circular Wait)

 - 공유 자우너과 공유 자원을 상요하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 

자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

교착 상태 해결 방법

예방 기법

 - 교착상태 발생의 4가지 조건 중에서 하나를 제거

 - 상호 배제 부정

 - 점유와 대기 부정

 - 비선점 부정

 - 환형 대기 부정

회피 기법

 - 교착 상태가 발생할 가능성을 배제하지 않고, 교착 상태가 발생하면 적절히 피해나가는 방법

 - 다익스트라가 제안한 은행원 알고리즘을 사용

발견 기법

 - 교착 상태가 발생했는지 점검하여 교착 상태에 있는 프로세스와 자원을 발견하는 것으로, 

자원 할당 그래프 등을 사용함

회복 기법

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

'프로세사나 자원을 회복하는 것

병행 프로세스

 - 두 개 이상의 프로세스들이 동시에 존재하며 실행 상태에 있는 것을 의미

임계영역(Critical Section)

 - 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여

어느 한 시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유 자원(영역)을 의미

상호배제(Mutual Exclusion, Mutex)

 - 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 

해당 공유 자원을 사용하지 못하게 제어하는 기법

동기화 기법

 - 두 개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 

각 프로세스에 대한 처리 순서를 결정하는 것으로, 상호 배제의 한 형태이다.

 - 세마포어, 모니터

상호배제 구현 기법

소프트웨어적 구현 기법

 - 2개의 프로세스 기준 : 데커(Dekker) 알고리즘, 피터슨(Peterson) 알고리즘

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

하드웨어적 구현 방법

 - Test & Set 기법

 - Swap 명령어 기법

세마포어(Semaphore)

- 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법이다.

 - P연산 : 자원을 사용하려는 프로세스들의 진입 여부를 자원의 개수(S)를 통해 결정하는 것으로 자원의 개수를 감소시켜(S--) 자원이 점유 되었음을 알림(Wait 동작)

 - V연산 : 대기중인 프로세스를 깨우는 신호(Wake Up)로서, 자원의 개수를 증가시켜(S++) 자원이 반납되었음을 알림(Siginal 동작)

 P(S) {
     S--;
     if S < 0
         // 이 프로세스를 재움 큐에 추가 (잠 듦)
 }

 V(S) {
     S++;
     if S <= 0
         // 재움 큐로부터 프로세스를 제거 (깨어남)
 }

모니터(Monitor)

 - 동기화를 구형하기 위한 특수 프로그램 기법으로 특정 공유 자원을 프로세스에게 

할당하는 데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성된다.

 - 자료 추상화와 정보 은폐 개념을 기초로 하며 공유 자원을 할당하기 위한 병행성 구조로 이루어져 있다.

 - 모니터 내의 공유 자원을 사용하려면 프로세스는 반드시 모니터의 진입부를 호출해야 한다.

 - 외부의 프로시저는 직접 액세스할 수 없으며, 모니터의 경계에서 상호 배제가 시행된다.

선점과 비선점

비선점 스케줄링

 - 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법

 - CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.

 - 일괄 처리 방식에 적합

// FCFS, SJF, 우선순위, HRN, 기한부 등

선점 스케줄링

 - 하나의 프로레스가 CPU를 할당받아 실행하고 있을 때 우선순위가 

높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

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

 - 많은 오버헤드 초래

 - 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록이 필요

// Round Robin, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등

비선점 스케줄링

FCFS(First Come First Service)

 - 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘

P1 (10초)   P2 (3초)   P3 (7초)

SJF(Shortest Job First)

 - 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법

P1 (10초)   P2 (3초)   P3 (7초)

HRN(Highest Response-ratio Next)

 - 실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로,

대기 시간과 서비스 시간을 이용하는 기법이다.

 - 우선순위 계산식 = (대기시간 + 서비스 시간) / 서비스 시간

기한부

 - 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법

우선순위

 - 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 

그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

 - 가장 낮은 순위를 부여받은 프로세스는 무한연기 또는 기아 상태가 발생할 수도 있다.

선점 스케줄링

SRT(Shortest Remaining Time)

 - 남은 시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법

RR(Round Robin)

 - FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당 받지만

각 프로세스는 시간 할당량 동안만 실행한 후 실행이 완료되지 않으면 

다음 프로세스에게 CPU를 넘겨주고 큐의 가장 뒤로 배치 된다.

P1 (10초)   P2 (3초)   P3 (7초)

선점 우선순위

 - 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

다단계 큐

 - 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법

 - 각 준비상태 큐는 독자적인 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 

서로 다른 스케줄링 기법을 사용할 수 있다.

다단계 피드백 큐

 - 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는

다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법

프로세서에 의해 처리되는 사용자 프로그램, 시스템 프로그램, 즉 실행중인 프로그램을 의미하며, 작업, 태스크라고도 한다.

PCB를 가진 프로그램

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

프로세서가 할당되는 실체로서, 디스패치가 가능한 단위

프로시저(부 프로그램)가 활동중인 것

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

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

운영체제가 관리하는 실행 단위

PCB(Process Control Block)

운영체제가 프로세스에 대한 중요한 정보를 저장해 놓는 곳

프로세스의 현재 상태

포인터

 - 부모/자식 프로세스에 대한 포인터

 - 프로세스가 위치한 메모리에 대한 포인터

 - 할당된 자원에 대한 포인터

프로세스 고유 식별자

스케줄링 및 프로세스의 우선순위

CPU 레지스터 정보

주기억장치 관리 정보

입출력 상태 정보

계정 정보

 프로세스 상태 전이

제출(Submit)

 - 작업을 처리하기 위해 사용자가 작업을 시스템에 제출한 상태

접수(Hold)

 - 제출한 작업이 스풀 공간인 디스크의 할당 위치에 저장된 상태

준비(Ready)

 - 프로세스가 프로세서를 할당받기 위해 기다리고 있는 상태

 - 프로세스는 준비상태 큐(스케줄링 큐)에서 실행을 준비하고 있다.

실행(Run)

 - 할당 시간이 종료되면 준비상태로 전이된다.

 - 입출력 처리가 필요하면 대기상태로 전이된다.

 - 준비 상태에서 실행상태로의 전이는 CPU스케줄러에 의해 수행

대기(Wait), 블록(Block)

종료(Terminated, Exit)

스레드

스레드는 프로세스 내에서의 작업 단위로서 시스템의 여러 자원을 할당받아 실행하는 프로그램의 단위

 - 스레드 기반 시스템에서 스레드는 독립적인 스케줄링의 최소 단위로서 프로세스의 역할을 담당

사용자 수준의 스레드

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

 - 속도는 빠르지만 구현이 어렵다.

커널 수준의 스레드

 - 운영체제의 커널에 의해 스레드를 운용

 - 구현이 쉽지만 속도는 느리다.

장점

 - 병행성 증진

 - 하드웨어, 운영체제의 성능과 응용 프로그램의 처리율을 향상

 - 응용프로그램의 응답시간 단축

 - 실행 환경을 공유시켜 기억장소의 낭비가 줄어듬

 - 프로세스간의 통신 향상

 - 스레드는 공통적으로 접근 가능한 기억장치를 통해 효율적 통신

링커

링커는 언어 번역프로그램이 생성한 목적 프로그램들과 라이브러리, 

또 다른 실행 프로그램(로드 모듈) 등을 연결하여 실행 가능한 로드 모듈을 만드는 시스템 소프트웨어이다

연결 기능만 수행하는 로더의 한 형태로, 링커에 의해 수행 수행되는 작업을 링킹이라고 한다.

로더

로더는 컴퓨터 내부로 정보를 들여오거나 로드 모듈을 디스크 등의 

보조기억장치로부터 주기억장치에 적재하는 시스템 소프트웨어이다.

로더의 기능

할당

 - 실행 프로그램을 실행시키기 위해 기억장치 내에 옮겨놓을 공간을 확보하는 기능

연결

 - 부 프로그램 호출 시 그 프로그램이 할당된 기억장소의 시작주소를 호출한 부분에 등록하여 연결하는 기능

재배치

 - 디스크 등의 보조기억장치에 저장된 프로그램이 사용하는 각 주소들을 할당된 기억장소의 실제 주소로 배치시키는 기능

적재

 - 실행 프로그램을 할당된 기억공간에 실제로 옮기는 기능

로더의 종류

Compile And Go 로더

 - 별도의 로더 없이 언어 번역 프로그램이 로더의 기능까지 수행하는 방식

 - 연결 기능은 수행하지 않고 나머지 기능은 언어 번역 프로그램이 담당한다.

절대 로더

 - 목적 프로그램을 기억장소에 적재시키는 기능만 수행하는 로더로, 로더 중 가장 간단한 프로그램으로 구성

 - 기억장소 할당이나 연결을 프로그래머가 직접 지정하며 한번 지정한 주기억장소의 위치는 변경이 어렵다.

 - 할당/연결(프로그래머), 재배치(언어 번역 프로그램), 적재(로더)

직접 연결 로더

 - 일반적인 기능의 로더로, 로더의 기능 네 가지를 모두 수행하는 로더이다.

동적 적제 로더

 - 프로그램을 한꺼번에 적재하는 것이 아니라 실행 시 필용한 부분만을 적재하고, 

나머지 부분은 보조기억장치에 저장해두는 것으로 호출시 적재라고 한다.

프로그램 작성 시 한 프로그램 내에서 동일한 코드가 반족될 경우 반복되는 코드를 한 번만 작성하여 

특정 이름으로 정의한 후 그 코드가 필요할 때마다 정의된 이름을 호출하여 사용하는 것이다.

매크로 정의 인식 ▶ 매크로 정의 저장 ▶ 매크로 호출 인식 ▶ 매크로 확장과 인수 치환

매크로와 부 프로그램

매크로

 - 개방 서브루틴(Opened Sub-routine)

 - 주 프로그램의 매크로 호출 명령이 있는 위치마다 매크로 내용을 삽입하여

확장된 프로그램을 만들어 놓고 연속으로 실행함

부 프로그램

 - 폐쇄 서브루틴(Closed Sub-routine)

 - 부 프로그램이 호출될 때마다 제어가 부 프로로그램으로 넘어갔다가

다시 주 프로그램으로 복귀됨

둘 모두 중복된 코드를 제거해 더 깔끔한 코드를 만들 수 있다.

부프로그램은 매크로에 비해 프로그램의 크기가 작아지고, 

기억장소가 절약되지만 실행시간은 약간 느려짐

매크로 처리 과정

컴퓨터 시스템의 자원들을 효율적으로 관리하여, 사용자가 컴퓨터를 편리하고

효과적으로 사용할 수 있도록 환경을 제공하는 여러 프로그램의 모임

// Windows, MS-DOS, UNIX, Linux 등

성능 평가 기준

처리능력(Throughput)

 - 일정 시간 내에 시스템이 처리하는 일의 양

반환시간(Turn Around Time)

 - 시스템에 작업을 의뢰한 시간부터 처리가 완료될 때까지 걸린 시간

사용 가능도(Availability)

 - 시스템을 사용할 필요가 있을 때 즉시 사용 가능한 정도

신뢰도(Reliability)

 - 시스템이 주어진 문제를 정확하게 해결하는 

운영체제 운용 기법 및 발달 과정

일괄처리   ▶   다중프로그래밍/다중처리/시분할/실시간처리   ▶   다중 모드   ▶   분산처리

일괄처리

 - 한꺼번에 처리

 - 반환(응답) 시간이 늦지만 하나의 작업이 모든 자원을 독점하므로 CPU 유휴시간이 줄어듦

 - 급여 계산, 지불 계산, 연말 결산 등

다중 프로그래밍

 - 하나의 CPU와 주기억장치를 이용하여 여러개의 프로그램을 동시에 처리하는 방식

 - 싱글코어에서도 여러개의 프로그램을 실행하는 것을 기억하면 될 듯

시분할 시스템

 - 여러 명의 사용자가 사용하는 시스템에서 컴퓨터가 사용자들의 프로그램을 번갈아가며 처리해

줌으로써 각 사용자에게 독립된 컴퓨터를 사용하는 느낌을 주는 것이며 라운드 로빈 방식이라고도 함

다중 처리

 - 여러 개의 CPU와 하나의 주기억장치를 이요하여 여러 개의 프로그램을 동시에 처리

실시간 처리

 - 데이터 발생 즉시, 데이터 처리요구가 있는 즉시 처리하여 결과를 산출하는 방식

 - 은행의 온라인 업무, 좌석 예약 업무, 인공위성 등의 제어 업무 등 

시간에 제한을 두고 수행되어야 하는 작업에서 사용됨

다중 모드 처리

 - 일괄 처리 시스템, 시분할 시스템, 다중 처리 시스템, 실시간 처리 시스템을 한 시스템에서 모두 제공

분산처리

 - 여러 개의 컴퓨터를 통신 회선으로 연결하여 하나의 작업을 처리하는 방식

 - 각 단말장치나 컴퓨터 시스템은 고유의 운영체제와 CPU, 메모리를 가지고 있음

제어프로그램

감시 프로그램

 - 각종 프로그램의 실행과 시스템 전체의 작동 상태를 감시감독하는 프로그램

작업제어 프로그램

 - 어떤 업무를 처리하고 다른 업무로의 이행을 자동으로 수행하기 위한

준비 및 그 처리에 대한 완료를 담당하는 프로그램

자료 관리 프로그램

 - 주기억장치와 보조기억장치 사이에 데이터 전송과

보조기억장치의 자료 갱신 및 유지 보수 기능을 수행하는 프로그램

처리프로그램

언어번역 프로그램

 - 원시 프로그램을 기계어 형태의 목적 프로그램으로 번역하는 프로그램

// 어셈블러, 컴파일러, 인터프리터

컴파일러와 인터프리터

컴파일러

 - 고급언어로 작성된 소스 프로그램 전체를 목적 프로그램으로 번역한 후,

링킹 작업을 통해 컴퓨터에서 실행 가능한 실행 프로그램을 생성함

 - 번역 과정이 번거롭고, 번역 시간이 오래 걸리지만 실행 속도가 빠름

어셈블러

어셈블리어를 기계어 형태의 오브젝트 코드로 해석해주는 컴퓨터 언어 번역프로그램

어셈블러는 기본 컴퓨터 명령어들을, 컴퓨터 프로세서가 기본 연산을 수행하는데

사용할 수 있는 비트 패턴으로 변환시키는 프로그램

선택정렬 Θ(n^2)

버블정렬 Θ(n^2)

삽입정렬 Θ(n^2) Θ(n)

선택정렬 Θ(n^2)

A[1..n]에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다.

8 31 48 73 3 65 20 29   index 0~7중에 가장 큰 수의 위치를 찾아 index 7의 값과 바꾼다.

8 31 48 29 3 65 20 73   index 0~6중에 가장 큰 수의 위치를 찾아 index 6의 값과 바꾼다.

8 31 20 29 3 65 48 73   반복

8 31 20 29 3 65 48 73

8 3 20 29 31 65 48 73

8 3 20 29 31 65 48 73

8 3 20 29 31 65 48 73

3 8 20 29 31 65 48 73

PS)

알고리즘 책에서는 뒤에서부터 정렬해 나가지만

정보처리기사에서는 앞에서부터 정렬하게 나온다.

순서의 차이일뿐 똑같은 방법이기 때문에 상관없으려고 했는데 

문제 풀때 헤깔려서 짜증난다.

버블정렬 Θ(n^2)

선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는 정렬

8 31 48 73 3 65 20 29   index 0과 index 1의 값을 비교해 큰 수를 뒤로 미룬다.

8 31 48 73 3 65 20 29   index 1과 index 2의 값을 비교해 큰 수를 뒤로 미룬다.

8 31 48 73 3 65 20 29   반복

8 31 48 73 3 65 20 29

8 31 48 3 73 65 20 29

8 31 48 3 65 73 20 29

8 31 48 3 65 20 73 29

8 31 48 3 65 20 29 73  index 7에 가장 큰 수가 왔으므로 선택정렬처럼 범위를 줄여서 반복한다.

삽입정렬 Θ(n^2) Θ(n)

이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복하는 정렬

정렬되어 있을수록 더 빠른 수행시간을 가진다.

완전히 정렬되어 있다면 Θ(n)의 시간이 든다.

8 31 48 73 3 65 20 29

8 31 48 73 3 65 20 29   1개짜리 정렬된 배열

8 31 48 73 3 65 20 29   2개짜리 정렬된 배열

8 31 48 73 3 65 20 29   3개짜리 정렬된 배열

8 31 48 73 3 65 20 29   4개짜리 정렬된 배열

3 8 31 48 73 65 20 29   5개짜리 정렬된 배열 (추가된 3을 맞는 위치에 가게 한다.)

3 8 31 48 65 73 20 29   반복

3 8 20 31 48 65 73 29

3 8 20 29 31 48 65 73