[정보처리기사] Part04-03-1. 운영체제 기초 활용 (7)

 

Contents

 

 

UNIX, WINDOWS

디스크 공간할당 방법

디스크 공간할당을 효율적으로 사용하기 위한 방법

구분	설명
연속 할당기법	- 파일을 디스크의 연속된 기억공간에 할당 - 생성되는 파일 크기만큼의 공간 필요 - 구조 단순하고 접근시간 빠름 - 단편화 줄이기 위한 압축(Compaction) 필요
불연속 할당기법	- 파일 크기에 맞춰 디스크 일정 단위로 나누어 할당 - 섹터 할당 : 디스크 섹터 단위로 저장하고 섹터들을 Linked-list로 연결 - 블록 할당 : 파일 블록 단위로 저장하고 블록체인 할당기법, 인덱스 블록체인 할당기법, 블록지향 파일 사상 기법 등 존재
인덱스 블록체인 할당기법	- 파일마다 인덱스 두고, 파일이 지정한 블록 포인터를 인덱스에 연결하여 접근
블록지향 파일 사상 기법	- 포인터 대신 파일 할당 테이블(FAT) 블록 번호 사용 - 디렉토리가 파일 할당 테이블 시작 위치 정보 가짐

 

파일 편성기법

파일 형성하고 있는 레코드를 기록 매체 위에 어떻게 배치할 것인지에 대한 파일 구조를 의미.

레코드의 식별, 검색, 저장, 기록 매체 종류에 따라 편성 방법 상이.

편성 방법	설명
순차 편성(SAF)	- 파일 내 레코드가 물리적으로 연속해서 기록되는 방식 - 장점 : 간단하고 버퍼링 용이, 가변길이 레코드, 메모리 효율 높음 - 단점 : 느리고 수정 어려움 - 매체 : 테이프
직접 편성(DF)	- 키를 지정하면 대응하는 레코드 기록 위치 구하는 방식 - 장점 : 수정 용이, 빠른 속도 - 단점 : 주소 계산 필요, 가변 길이 사용 어려움 - 매체 : 디스크, 드럼
색인 순차 편성 (ISAM)	- 키의 순번으로 나열된 레코드 저장하는 주 데이터 영역과 레코드를 키와 포인터로 표시한 색인 영역을 조합하는 방식 - 장점 : 파일 수정 용이, 빠른 속도 - 단점 : 키가 필요하며 사전에 배열 필요, 주기적 재구성, 가변 길이 구성 어려움 - 매체 : 메모리, 드럼
구분 편성 (Partitioned Organization)	- 파일 편성하는 멤버명과 주소가 들어간 등록부와 데이터 영역으로 편성

 

UNIX 파일 보안

UNIX나 Linux는 chmod 명령어로 권한 부여되지 않은 사용자들로부터 시스템 자원 접근 통제.

사용자 식별과 인증, 파일워 권한 관리가 대표 사례.

파일 유형	owner (소유자)			group			other
일반파일	r	w	x	r	w	x	r	w	x
	4	2	1	4	2	1	4	2	1
Read(r)	일반파일		읽기와 복사 가능
	디렉토리		디렉토리 내용 표시 가능
Write(w)	일반파일		수정 가능
	디렉토리		파일 추가 삭제 가능
Execute(x)	일반파일		수행 가능
	디렉토리		디렉토리 변경 가능

• 파일 유형 : 일반 파일 기호는 -, 디렉토리 파일 기호는 d
• 소유자 : 그 파일이나 디렉토리 생성한 주체
• 그룹 : 그 파일이나 디렉토리 생성한 주체가 속한 그룹
• 모든 주체 : 소유자나 그룹 이외에 모든 시스템 주체

병행 처리와 상호배제

구분	병렬처리(Parallel)	병행처리(Concurrency)
의미	계산 과정에 동시성을 강조하는 정보처리형태, 명령어 사이에 상관관계 없음	2개 이상 관련 있는 프로세스가 동시에 실행되는 동시처리 프로세스
수행대상	복수 연산	복수 프로세스
고려사항	병행성 개념 완벽히 수용	프로세스 동기화/통신, 상호배제, Deadlock
구현방법	- 파이프라인 기법 - Array Computer, 다중 처리	- 세마포어 - Dekker's 알고리즘

 

     병렬처리 (Parallel Processing)

• 폰노이먼 구조의 순차처리 방식을 개선하여 프로그램 명령어를 여러 프로세서에 분산, 동시 수행하여 빠른 계산을 수행하는 프로세싱 기술

유형	설명
파이프라인	- RISC 기반 명령어의 Instruction Cycle 중첩 수행 - 단위시간 내 실행되는 명령어 수 증가 - 유효 명령어 수행시간 단축, Throughput 향상
멀티 프로그래밍	- 2개 이상 프로그램을 동시 수행하는 방식 - 각 프로그램이 프로세서를 짧은 시간 동안 점유하여 번갈아 수행 - Bus 이용한 Data I/O 등 시간 소요되는 작업 시, 다른 프로그램 동작하여 전체 프로세스 효율 향상
벡터 프로세싱	- 다수 프로세서로 구성된 벡터 처리기 이용 - SIMD 방식 통한 다수 data 동시 processing 수행
멀티 프로세싱	- Master-Slave 방식 프로세스 운영 - Master : 전체작업 관장 - Slave : 마스터가 할당한 작업 수행 - 성능 확장 용이. 관리 어려움
SMP (Symmetric MultiProcessing)	- 한 개의 공유 메모리 - 2개 이상 프로세서 운영 - 다중 프로세서 아키텍처
MPP (Massive Parallel Processing)	- 다수 프로세서가 네트워크로 연결 - 한 시스템 내 프로그램을 여러 부분으로 분할 - 다수 프로세서 이용하여 효과적으로 수행

 

     병행 처리 동시성 제어, 상호배체 기법

• 상호배제 : 경쟁조건 방지 위해 특정 프로세스가 공유자원 사용하고 있는 경우 다른 모든 프로세스가 해당 공유자원을 사용하지 못하도록 제어. 즉, 둘 이상 프로그 램이 임계영역(Critical Section)을 동시에 진입 못하도록 통제하는 기법
• 상호배제 기법에서 핵심이 되는 임계영역(Critical Section)은 여러 개 프로세스가 공유하는 데이터 및 자원에 대해 어느 한 시점에는 하나의 프로세스만 사용하도록 지정된 공유 영역

요구조건	구분	관련사항
상호배체 조건	오직 한 개 프로세스만 임계영역에 존재 가능	임계 영역
진행 조건	임계영역 밖에 있는 프로세스가 다른 프로세스 임계영역 진입 막을 수 없음	교착상태 기아상태
한계 대기 조건	어떤 프로세스도 임계영역 진입이 무한정 연기될 수 없음
상대 속도 조건	프로세스에 대한 상대적 속도에 대해서는 어떤 가정도 하지 않음

 

상호배제 원리

• 스레드 임계 영역에서 일어나는 일을 캡슐화하는 상호배제 관련 가낭 기본적인 연산 호출 방법

항목	enterMutualExclusion()	exitMutualExclusion()
개념도
역할	- 임계영역 진입 전 검사과정 - 다른 프로세스가 임계영역 내 존재하는지 여부 검사	- 임계영역을 벗어날 경우 처리 과정 - 임계영역을 벗어날 경우 시스템에게 알림

 

상호배제 해결방안

해결방안		설명
SW	데커(Dekker) 알고리즘	- 두 개 프로세스 위한 상호배제에 대한 최초 소프트웨어 기법 - 공유 변수: 두 개 Boolean Flag(사용의사)와 int turn(차례) - 차례(turn) 설정 : 차례를 자신 프로세스에게 설정
	피터슨(Peterson) 알고리즘	- 공유 변수: 두 개 Boolean Flag(사용 의사)와 int turn(차례) - 의사표시 : 임계영역 진입하려면 먼저 Flag(사용 의사)를 True로 설정 후 임계영역 진입 - 차례 양보 : 차례를 다른 프로세스에게 양보
	램포트(Lamport) 베이커리 알고리즘	- 분산처리 환경에서 유용한 상호배제 알고리즘 - 수행 순서 위한 번호표 부여 - 낮은 번호가 먼저 임계영역 사용 요청한 프로세스로 진입
	세마포어 (Semaphore)	- 운영 체제 또는 프로그램 작성 내에서 지원하는 상호배제 알고리즘 - 세마포어의 상태변수(S)와 두 개의 연산(P. V)으로 임계영역에 접근 는 잠금장치에 대한 이론적 기반
HW	인터럽트 사용금지	- 공유 변수가 변경되는 동안 인터럽트 발생 허용 않음 - 단일 프로세서에서 가능하고 멀티 프로세서에서는 적용 불가
	Test and Set	- 하드웨어에서 한 워드(Word) 내용 검사하고 변경하는 명령어 제공 Function Test-and-Set (var target: Boolean): Boolean; Begin Test-and-Set := target;    Target := true; End;
	소프트웨어 ap	- 하드웨어에서 두 워드 간 내용 교환 가능한 명령어 제공 Procedure 소프트웨어ap (var a, b: Boolean); var temp: Boolean; Begin    temp := a;    A := b;    B := temp; End;

 

     세마포어

• 운영 체제 또는 프로그램 작성 내에서 공유 자원에 대한 접속 제어 위해 사용되는 IPC(Inter-Process Communication) 자원

세마포어 적용 방법

• 세마포어에서 S는 정수값을 가지는 변수이며, P연산과 V연산이라는 함수에 의해 접근 가능
• P연산은 임계 구역에 들어가기 전에 수행
• V연산은 임계 구역에서 나올 때 수행
• 변수 값을 수정하는 연산은 모두 원자성을 만족 해야 함. 즉, 한 프로세스(또는 스레드)에서 세마포어 값 변경하는 동안 다른 프로세스가 동시에 이 값 변경 불가

세마포어 유형

유형	목적
Binary Semaphore	- 세마포어 값으로 0 또는 1을 가짐. - 계수 세마포어보다 간단히 구현할 수 있으며 Test and Set 등 하드웨어가 지원하는 기능을 이용하여 구현 - 이진 세마포어를 이용하여 계수 세마포어를 구현
Counting Semaphore	초기값은 가능한 자원수로 정해지며, 세마포어 값의 범위는 정해져 있지 않음

 

     교착상태

• 다중 프로세스 환경에서 서로 다른 프로세스가 각자 자신이 소유한 자원을 포기하지 않고, 상대 프로세스 자원을 무한 대기하고 있는 상태
• 한 시스템 내에서 교착 상태 발생 원인 4가지 조건이 동시 성립되어야 교착 상태 발생

원인	내용	간략도
상호배제 (Mutual Exclusive)	프로세스가 자원을 배타적으로 점유하여 다른 프로세스가 그 자원 사용 불가
점유와 대기 (Hold & Wait)	한 프로세스가 자원을 점유하고 있으면서 또 다른 자원 요청하여 대기하고 있는 상태
비선점 (Non-Preemption)	한 프로세스가 점유한 자원에 대해 다른 프로세스가 선점할 수 없고, 오직 점유한 프로세스만이 해제 가능
환형대기 (Circular wait)	두 개 이상 프로세스 간 자원 점유와 대기가 하나의 원형을 구성한 상태

 

해결방안	내용
예방 (Prevention)	- 상호배제, 점유와 대기, 비선점 및 환형대기 조건 중 하나 이상 부정
회피 (Avoidance)	- 은행가 알고리즘 (Banker's Algorithm) - Wait-die, wound-wait
발견 (Detection)	- 시스템 상태를 감시 알고리즘을 통해 교착상태 검사 - 자원할당 그래프, Wait for Graph
회복 (Recovery)	- Deadlock 없어질 때까지 프로세스 순차적으로 Kill 명령으로 제거 - 프로세스 종료비용 최소화 : 우선순위, 진행비용, 복귀비용 등 자원 우선순위 할당: 희생자 선택, 복귀, 기아상태

 

교착상태 회피 방법과 은행가 알고리즘

• 프로세스가 자원 요구 시 시스템은 자원 할당 후에도 안정 상태인지 사전에 검사하여 교착상태 발생 회피하는 기법
  • 자원 상황과 최대 사용량 미리 파악
  • 프로세스 자원할당 요구
  • 안정 알고리즘에 의한 상황 점검
  • 안정 상태이면 할당
  • 불안정 상태이면 승인 거부

자료구조	설명	수식
Available	사용 가능한 자원 수	- Available[j] = K - 자원종류 Rj 중 K개 사용 가능
Max	프로세스 별 최대 자원 요구	- Max[i, j] = K - Pi는 자원종류 Rj 중 최대 K개 요청
Allocation	현재 프로세스 별 할당된 자원 수	- Allocation[i, j] = K - Pi는 현재 자원종류 Rj를 K개 할당 받음
Need	프로세스 별 남아 있는 자원 수	- Need[i, j] = (Max - Allocation) - Pi는 자원종류 Rj를 K개 더 요구

 

교착상태 회피기법, Wait-die와 Wound-wait

• Wait-die 알고리즘 예제
  • T2가 이미 선점한 자원을 T1이 요청하면 T1은 대기, T3이 요구하면 T3은 복귀(die)
  • T1이 older 프로세스이기에 T2가 점유하고 있는 자원 기다리고, T3의 경우 younger 프로세스이므로 abort 시킴
  • 만약 위 상태에서 T4(Timestamp = 15)가 T2가 점유하고 있는 자원 요청하는 경우 wait 상태였다가, T2가 수행 마치고 T1이 자원 점유 시 기본적으로 T4는 abort 상태가 됨

• Wound-wait 알고리즘 예제
  • T2가 이미 선점한 자원을 T1이 요청 시 T2 복귀시키고 T1 요청 수용하며, T3가 요구 시  T3는 wait 상태
  • T1이 younger 프로세스이기에 T2가 점유하고 있는 자원 기다리고, T3은 older 프로세스이므로 abort 시킴
  • 만약 위 상태에서 T4(Timestamp = 25)가 T2가 점유하고 있는 자원 요청하는 경우 wait 상태였다가, T2가 수행 마치고 T1이 자원 점유 시 기본적으로 T1은 abort 상태가 되고 T4가 자원 점유

구분	Wait-die	Wound-wait
개념	개별 프로세스에 타임스탬프 지정하고, 해당 프로세스가 보유 중인 자원 요구하는 프로세스가 적은 타임스탬프를 가지면 대기(wait)하고 그렇지 않으면 복귀(die)	개별 프로세스에 타임스탬프를 지정하고, 해당 프로세스가 보유 중인 자원 요구하는 프로세스가 적은 타임스탬프를 가지면 자원 선점(wound)하고 그렇지 않으면 대기(wait)
특징	- 오래된 프로세스가 기다림 - 프로세스 P1이 프로세스 P2에 의해 점유된 자원 요청해서 롤백되면 프로세스 P1은 재시작 시 전과 같은 요청 다시 진행 - 재요청 시 자원이 P2에 의해 점유되어 있으면 P1은 다시 롤백	- 오래된 프로세스는 기다리지 않음 - 프로세스 P2는 P1이 점유한 자원 요청하면 P1은 자원 방출하고 롤백 - 이후 P1이 재시작하여 P2에 의해 점유된 자원 요청하면 P1은 자원 기다리는 상태 - 롤백되는 경우 상대적으로 적음

• 두 기법 모두 우선순위가 높은 프로세스가 낮은 우선순위 프로세스를 Abort 시켜 교착상태 발생 회피하면 교착상태가 아닌 경우 불필요한 복귀가 발생
• 두 기법 모두 롤백되는 프로세스에 새로운 타임스탬프를 다시 할당하지 않게 되어 기아 상태를 방지 가능

 

     교착상태 발견 방법, 자원할당 그래프

• 프로세스와 자원 간 관계 나타내는 그래프
• 정점(vertex)들과 정점을 연결하는 간선(edge)들로 이루어진 그래프

 

교착상태 발견 알고리즘

• 시스템 상태 감시하는 알고리즘 통해 교착상태 검사하는 알고리즘

 

자원할당 그래프 통한 교착상태 발견

• 요청선(request edge) : 프로세스 정점에서 자원 정점으로 연결된 선
• 할당선(assignment edge) : 자원 정점에서 프로세스 정점으로 연결된 선

## 교착상태 확인 사례

• 자원할당 그래프 사이클이 존재하는지 확인
• 사이클이 존재 시 자원 유형에 하나의 사례만 있으면 교착상태이고, 자원 유형에 여러 사례가 있으면 교착상태 가능성
• 프로세서 p1이 작업 완료하고 R3 자원 반환하면 p3는 p1이 반환한 자원 할당 가능

 

인터럽트

• 프로그램 실행 중 CPU 현재 처리 순서 중단시키고 다른 동작 수행하도록 요구하는 시스템 동작
• 인터럽트 발생 원인
  • 기계적인 문제 (정전, 데이터 전달 과정에서 HW 오류 발생)
  • 프로그램 문제
  • 컴퓨터 조작자의 의도적인 조작에 의한 중단
  • 입출력 장치들 동작에 CPU 기능 요청되는 경우
  • 산술 연산 overflow, underflow 발생

구분	설명
인터럽트 요청(IRQ)	- Interrupt ReQuest - CPU에 인터럽트를 요청하는 신호 - CPU에게 인터럽트 요청 시 CPU가 각 장치 구분 가능한 공유한 IRQ 존재
인터럽트 처리루틴 (IPR) 또는 인터럽트 벡터	- Interrupt Process Routine - 인터럽트 발생 원인 찾아 ISR 호출
인터럽트 서비스 루틴(ISR)	- Interrupt Service Routine - 인터럽트에 대한 실체 처리 담당
트랩(Trap)	- 오류나 사용자 요청에 의해 소프트웨어가 발생시킨 인터럽트

• 인터럽트가 발생 시 인터럽트 받은 장치는 현재 자신의 상태를 PCB(Process Control Block)라는 자료구조에 기억시켜두고 인터럽트 처리

 

##인터럽트 유형

분류	종류	설명
외부인터럽트 (하드웨어 인터럽트)	전원 이상 인터럽트	- 정전 또는 전원 이상에 의한 인터럽트 발생
	기계 착오 인터럽트	- CPU의 기능적인 오류동작 발생
	외부 신호 인터럽트	- 타이머에 의해 규정된 시간 알리는 경우 - 키보드로 인터럽트 발생시킨 경우 (Ctrl+Alt+Del) - 외부 장치로부터 인터럽트 요청 발생
	입/출력 인터럽트	- 입출력 데이터 오류나 이상 현상 발생한 경우 - 입출력 장치가 데이터 전송 요구 또는 전송 완료 알림
내부인터럽트 (하드웨어 인터럽트)	프로그램 검사 인터럽트	- 0으로 나누기 한 경우 - Overflow, Underflow가 발생 경우 - 당한 기억장소 참조와 같은 프로그램 상 오류
소프트웨어 인터럽트	SVC 인터럽트	- 사용자가 SVC 명령 사용하여 의도적으로 인터럽트 발생 - 기억장치 할당 및 오퍼레이터와 통신 필요한 경우

 

##소프트웨어 하드웨어 인터럽트

소프트웨어 방식 (폴링)

- CPU가 모든 I/O 제어기들에 접속된 선 이용 - 인터럽트 요구한 장치 검사하는 방식 - Test I/O 신호 이용 - 각 I/O 장치 인터럽트 플래그 검사 - 우선순위 변경 쉬움 (SW 변경만으로 가능) - 회로 간단하고 융통성 있으며 별도 HW 필요 없ㅇ므 - 인터럽트 많을 시 조사하는데 처리 시간 다소 소요

 

하드웨어 방식 (직렬 연결)

- Daisy-Chain(데이지체인) - 우선순위 부여 방식으로 인터럽트 발생하는 모든 장치를 한 개의 회선에 직렬로 연결 - 우선순위 높은 장치 선두에 위치시키고 나머지 우선순위에 따라 차례로 연결 - 인터럽트 요구한 I/O 장치는 자신 고유 ID 번호, 즉 인터럽트 벡터를 벡터 버스 통하여 CPU로 전송 - 인터럽트 벡터는 해당 I/O 장치 위한 인터럽트 서비스 루틴 시작주소 결정 - 하드웨어 구조 간단 - 우선순위 낮은 장치들이 서비스 받지 못하는 현상 발생

 

하드웨어 방식 (병렬 연결)

- Multiple Interrupt - 각 I/O 제어기와 CPU 사이에 인터럽트 요청선(INTR) 인터럽트 확인선(INTA) 접속하는 방식 - 인터럽트 발생하는 각 장치를 개별적 회선으로 연결 - 각 장치 회선에 대응하는 Mask Register 사용하고 우선순위는 Mask Register 비트 위치에 의해 결정 - CPU가 인터럽트 요구한 장치 식별 용이 - 입력 핀 수에 의해 제한