단편적으로 정리 - 운영체제

- 프로세스 스케쥴링 : 다중 프로그래밍(multi programming)을 가능케 한다. cpu작업과 입출력 작업을 병행함으로써 이루어진다.

- preemptive : 선점이라는 번역때문에 헷갈리는데, 방해의 의미가 더 크다.

- 비선점형 스케줄링 : 할당받은 자원은 작업이 종료/중단될 때 까지 빼앗기지 않는다.

문맥 교환에 의한 오버헤드가 적은 대신 긴 대기시간으로 처리율은 떨어질 수 있다.

- 문맥 교환 = context switch : cpu가 다른 프로세스를 작업하기 위해 이전 프로세스의 상태를 저장하고 새로운 프로세스의 상태를 적재하는 과정

- 프로세스 제어 블록 = process control block = PCB = task control block = TCB : 프로세스를 표현하는 자료구조

1) pid 2) 프로세스 상태 3) pc 4) 레지스터들 5) 스케줄링 정보 6) 메모리 정보 7) 입출력 정보 8) 기타

일반 사용자가 접근하지 못하는 커널 메모리 영역에 저장된다. 일부 운영체제는 커널 스택에 저장.

- FCFS = first come, first served : 대기 상태 큐에 도착한 순으로 자원 할당. 기아 상태(starvation)를 유발할 수 있다.

- SJF = shortest job first : burst time이 가장 짧은 순으로 자원 할당. 평균 대기 시간을 최소화하는게 목표. 기아 상태를 유발할 수 있다.

- HRN = highest response-ratio next : 우선순위 함수값((대기시간 + burst) / burst)이 가장 높은 순으로 자원 할당. 대기시간이 반영된다.

- 선점형 스케줄링 : 다른 프로세스가 실행중의 프로세스의 자원을 뺏을 수 있다. 시분할 시스템에 적합하다. 즉 응답시간이 빠르다.

- RR = round robin : 시간단위(time quantum)마다 자원을 할당한다. 문맥교환이 잦아지는 대신 응답시간이 짧다.

- SRTF = shortst remaining time first : 최단 잔류 시간 우선. SJF를 선점형으로 바꾼 것.

- 다단계 큐 = multilevel queue : 대기 상태 큐를 우선순위가 부여된 큐들로 나눠서 처리

- 다단계 피드백 큐 : 다단계 큐에선 영구적으로 할당되지만, 프로세스마다 timeout을 추가해 큐들을 옮겨다닐 수 있게 했다.

- 임계 구역 문제 = critical section problem : 프로세스들이 동시에 수행될 수 있기에 발생하는 문제.

- 공유 하는 데이터에 동시적으로 접근하면( = race condition ) 데이터의 일관성을 망칠 수 있기 때문에 임계 구역으로 관리해야 한다.

- 이를 해결하기 위해 = 동기화

1. 특정 프로세스가 공유 자원을 사용하고 있으면 다른 프로세스가 접근하지 못하는 상호배제가 이뤄져야 한다.

2. 임계 구역을 아무도 수행하지 않고 있고, 여러 프로세스가 대기 중이라면, 이들 중의 선택은 무한히 연기될 수 없다.

3. 대기시간에 경계가 존재해야 한다.

1. 피터슨의 해결책 - 두 개의 프로세스에 대해

- flag는 진입할 준비에 대해, turn은 순번을 의미한다. 먼저 준비하고 양보하고 busy waiting한다.

- 탈출하려면 j가 임계구역을 다 끝내고 flag를 내리던지, 다시 돌아와서 turn을 넘기던지 둘 중 하나는 이뤄져야 한다. 

2. 데커 알고리즘 = Dekker : 비슷함 ㅎㅎ;

3. 세마포어 : P연산(try)과 V연산(증가)의 원자성이 확보되었으면, 진입전에 p연산을 수행하고, 나오면서 v연산을 수행해 동기화 할 수 있다.

4. 뮤텍스

- acquire()로 키를 얻고 진입한뒤, release()로 키를 반납한다.

4. 모니터

- 세마포어 문법실수를 막기 위해 세마포어 기능을 제공하는 추상화가 이루어진 객체.

- 한 프로세스만 모니터에 진입할 수 있고, 진입부를 반드시 호출해야 하며, 내부에서만 작업이 이루어진다.

- 운영체제 운용 기법

1. 일괄처리 시스템 = batch processing

- 일정기간동안 데이터를 모아서 한꺼번에 처리.

- 효율적인 사용이 가능한데, 사용자가 느끼기엔 응답 시간이 늦지만, cpu 입장에서 진득하니 모든 자원을 독점하기 때문이다.

- 초창기 모델로, 급여 계산, 연말 결산 등의 업무에 사용했다캄.

2. 다중 프로그래밍 시스템 = multi-programming

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

3. 시분할 시스템 = time sharing system

- 컴퓨터 자원을 사용자들이 시간적으로 분할하여 사용할 수 있다. 즉 대화식 인터페이스가 제공될 수 있다.

4. 다중 처리 시스템 = multi-processing

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

- 하나의 cpu가 고장나도 다른 cpu로 처리할 수 있으므로 신뢰성과 안정성이 높다.

- 종류

1. 주/종 처리기 : 주프로세서가 입출력과 운영체제를 운영하고, 종프로세서가 연산만 담당.

2. 분리 실행 : 주/종 처리기의 비대칭성을 해결하기 위해, 프로세서마다 운영체제를 각각 돌린다.

3. 대칭 처리기 : 여러 프로세서가 하나의 운영체제를 공유함

5. 실시간 처리 시스템 = real-time processing

- 자원이 한정된 상황에서 응답을 제한시간 내에 리턴해줘야 함

5-1) 경성 실시간 시스템 = hard : 조건을 만족시키지 못하면 치명적인 시스템, 철도체어, 원전제어

5-2) 연성 실시간 시스템 = soft : 만족시키지 못해도 치명상은 없는 시스템, 동영상 플레이어

6. 다중 모드 처리 시스템 = multi-mode processing

- 여러 모드를 지원한대

7. 분산 / 병렬 처리 시스템

- 네트워크로 연결 / 슈퍼컴퓨터 

- 분산 시스템의 위상구조

1) 성형 연결 = star connected : 각 노드들이 중앙컴퓨터를 경유해야 함

2) 환형 연결 = ring connected : 각 노드들은 서로 이웃을 두개 가짐

3) 완전 연결 = fully connected : 모든 노드 쌍들을 다이렉트로 연결

4) 계층 연결 = hierarchy connected : 구조가 트리. 루트 노드 + 자식 노드

- 프로세스 모델에 따른 분류

1) 서버/클라이언트 모델

2) 프로세서 풀 모델

3) 혼합모델

- 시스템 소프트웨어

1. 매크로 프로세서 : 원시 프로그램에 정의된 매크로를 인식 -> 정의 기억(저장) -> 매크로 호출 인식 -> 확장 및 치환 -> 어셈블러에 전달

- 매크로 = 개방 서브루틴 = opened sub-routine

2. 링커

- 목적 프로그램과 라이브러리를 연결하여 실행 가능한 모듈로 만들어 줌

- 목적 프로그램은 언어 번역 프로그램이 만든다.

- 언어 번역 프로그램 = 어셈플러, 컴파일러, 인터프리터 : 고급 언어로 작성된 원시 프로그램을 목적 프로그램으로 번역

3. 로더 : 프로그램을 주기억장치에 적재함

- 기능

1. 할당 = allocating : 실행 프로그램을 위한 공간을 확보한다.

2. 연결 = linking : 프로그램이 부프로그램을 호출할 경우, 부프로그램의 시작주소를 연결해준다.

- 링커의 기능과 똑같다. 즉 링커는 연결 기능만 수행하는 로더다.

3. 재배치 = relocating : 목적 프로그램을 실제 주기억 장치에 맞게 재배치한다. 상대주소를 절대주소로 바꿔준다.

4. 적재 = loading : 실제로 프로그램을 할당된 기억공간으로 옮김.

- 종류

1. 컴파일 즉시 로더 = comile and go : 번역기가 로더질까지 한다. 따라서 실행할 때 마다 번역도 다시해야한다.

2. 절대 로더 = absolute : 상대주소질을 할 줄 모르는 아주 간단한 로더.

3. 상대 로더 = relative = direct linking : 4가지 기능을 다 수행하는 일반적인 로더

- 자원 보호 기법 : 권한 부여의 방법

1) 접근 제어 행렬 = access control matrix : 행이 유저, 열이 파일

2) 접근 제어 리스트 = access control list : 파일마다 <영역(유저, 프로세스), 권한내용>의 리스트를 갖게 됨

3) 권한(자격) 리스트 = capability list : 반대로 영역(유저, 프로세스) 마다 <파일, 권한내용>의 리스트를 갖게 됨 

- 프로세서 연결 방법

1) 시분할 공유 버스 : 각종 장치들을 단일 경로(버스) 로 연결함, 경제적이며 나중에 추가가 쉽지만 한 시점에 한 가지 전송만 가능

2) 크로스바 교환 행렬 : 공유 버스 방법에서 버스를 장치 수만 큼 늘렸다. 각 장치마다 다른 버스를 쓸 수 있지만, 확장과 연결이 복잡해졌다.

3) 하이퍼 큐브 : 1차원(선분, 2개, 서로 이웃) 2차원(사각형, 4개, 서로 2개가 이웃) 3차원(육면쳬, 8개, 서로 3개가 이웃), ...

4) 다중포트 메모리 : 1과 2를 혼합한 형태, 프로세서와 장치 쌍으로 각각 버스를 가짐

- 순차 파일 = sequential file : 입력되는 레코드들을 논리적 순서에따라 연속된 물리적 공간에 저장

 -> 메모리의 효율적인 사용, 기록은 빠르지만, 데이터 추가, 삭제, 검색은 느리다. (링크드 리스트를 생각하면 될 듯)

- 색인 순차 파일 = indexed sequential file : 레코드들의 키 값들을 정렬하여 논리적 순서대로 기록하고, 키 항목을 모은 색인을 구성하는 방법

= ISAM = indexed sequential access method -> 색인에서 검색한 이후 포인터로 참조할 수 있다., 랜덤 처리와 순차 처리가 모두 가능함.

1) 기본 구역 = prime area : 실제 레코드를 저장하는 구역

2) 색인 구역 = index area : 색인을 저장하는 구역

3) 오버플로 구역 = overflow area : 기본 구역이 모자랄 상황을 대비한 예비 구역

- 직접 파일 = 랜덤 파일 = directed access method = DAM : 레코드를 임의의 저장공간에 기록하는 방법

- 레코드엔 키가 할당되고, 해시(키)로 주소를 알 수 있다. 기록순서에 대한 제약같은건 없어졌지만, 해시의 단점(충돌을 고려해야함, 변환시간)이 존재

- 디렉토리 : 파일에 대한 여러 정보를 가지고 있는 파일, 캐비넷

1. 1단계 디렉토리 : 모든 파일이 한 폴더내에서 관리된다. 따라서 다른 유저라도 같은 이름의 파일 사용 불가.

2. 2단계 디렉토리 : 사용자별로 1단계 디렉토리를 가진다. 다른 유저라면 같은 이름의 파일 사용 가능. MFD(master file dir) - UFD(user file dir)

3. 트리 디렉토리 : 윈도우즈와 유닉스에서 쓰는 트리형 구조, 루트와 서브

4. 비순환 그래프 디렉토리 : 트리와 비스무리. 다만 디렉토리들이 한 파일을 공유할 수 있게 되었다. 공동 사용이 가능해짐.

5. 일반 그래프 디렉토리 : 비순환은 비순환 보장이 문제다. 그래서 파일에 대한 링크를 허용했다.

- 다중 링 파일 : 레코드들을 그룹화하고 포인터로 연결해 표현

- 커널 : 하드웨어 할당, 프로세스 제어(=태스크 매니징), 메모리 제어, 시스템 콜 응답, 파일 시스템 관리

- 시스템 콜 : 사용자가 커널에 접근하기 위한 인터페이스, 보통 api로 제공된다.

- 유닉스

- 파일 시스템

1) 부트 블록 : bootstrap시 사용함. 부트로더 등

2) 슈퍼 블록 : 파일 시스템의 정보

3) inode 블록 : 파일(디렉토리 포함)의 정보

- 메타 데이터

- 파일 모드, 링크 갯수, 소유자 id, 그룹 id, 파일 크기, 마지막 접근 시간, 마지막 수정 시간, 생성일

- 데이터 블록 포인터들

4) 데이터 블록 : 실제 파일 내용

- 교착 상태 = deadlock : 한 자원에 대해 두 프로세스가 싸우느라 둘 다 대기 상태에서 헤어나오지 못하는 상황

- ( safe ) / ( unsafe ( deadlock ) )

- 조건

1) 상호 배제 조건 = mutual exclusive : 한 자원은 동시에 한 프로세스만 쓸 수 있다.

2) 점유와 대기 = hold and wait : 싸우는 프로세스중 한 놈은 갖고 있으면서 추가로 원하는 파렴치한 놈이어야 한다.

3) 비선점 = no preemption : 중간에 강탈은 없다.

4) 순환 대기 = circular wait : p0은 p1껄 대기하고, p1은 p2껄 대기하고, ... , 화살표로 그렸을때 사이클이 생김

- 해결 방법

1) 예방 : 조건들을 다 반대로 -> 공유 자원, 실행 전에 모두 할당해버리기, 선점 허용, 자원의 번호를 메기고 번호 순대로 요구하게 하기

- 따라서 자원 소비가 크다.

2) 회피 : 은행원 알고리즘 : 할당한 이후에도 안정상태인지 미리 검사해서 회피한다. 맞으면 할당해주고, 아니면 자원이 돌아올 때 까지 대기한다.

3) 탐지 : 현재 교착상태에 빠졌는지 그래프적으로다가 탐지하여 해결할 수 있다.

4) 회복 : 교착 상태의 프로세스들을 중단시키거나, 자원들을 선점하는 방법(빼앗어서 다른애 한테 줘버리기)

- 기억장치 관리 전략

- 반입에 대해 = fetch : 보조기억장치에 저장중인 데이터 / 프로그램을 언제 주기억장치로 반입할 것인지를 결정해야 한다.

1. 요구 반입 : 요구당할 때만 보조기억장치에서 반입한다.

2. 예상 반입 : 언제 요구당할 지 예측하여 미리 반입한다.

- 배치에 대해 = placement : 반입되는 데이터 / 프로그램을 주기억장치의 어디에 반입할 것인지를 결정해야 한다.

1. 최초 적합 = first fit : 맞는 영역중에 가장 첫번째 영역에 배치

2. 최적 적합 = best fit : 맞는 영역중에 가장 단편화가 적게 이뤄지는 영역에 배치

3. 최악 적합 = worst fit : 맞는 영역중에 가장 단편화가 크게 이뤄지는 영역에 배치

- 단편화  = fragmentation: 프로그램에 주기억장치를 할당하고 반납받는 과정에서, 낭비되는 빈 공간이 생기는 현상

1. 내부 단편화 : 프로그램이 쓸 영역보다 더 큰 영역이 할당되어서 낭비되는 공간

2. 외부 단편화 : 메모리 공간이 영역으로 나눠지다보면 내부 단편화가 생기고, 이를 다합친 공간 크기가 충분한데도 할당못하는 상황

- 단편화 해결 방법

1. 통합하기 : 인접한 단편화된 공간들을 통합해준다.

2. 압축하기 : 재배치를 통해 공간들을 압축해서 연속된 빈공간을 만들어낸다.

3. 페이징

4. 세그멘테이션

5. 메모리 풀 : 미리 저수지를 만들어 대비하고, 할당 요청이 들어올때마다 제공해준다.

- 필요한 만큼만 제공해주기 때문에 내부단편화 X, 제공이 풀 내에서만 이뤄지기 때문에 외부단편화 X

- 가상 기억 장치 = virtual memory : 주기억장치와 보조기억장치의 효율저인 사용을 위해 논리적으로 통합해 가상의 기억장치로 운용한다.

- 이제 프로그램에는 가상의 주소 = 논리주소 가 할당된다.

- 논리주소를 물리주소에 매핑할 전략이 필요하고, 이를 memory management unit = MMU가 수행한다.

1. 페이징 기법 : 가상주소공간과 물리주소공간을 같은 크기로 나누고(페이지 / 프레임), 프로그램에겐 페이지를 할당해준다.

- 이제 페이지별로 관리되므로 외부단편화는 없지만, 페이지 전체를 쓰지 않는 경우 꼴랑 mod 페이지크기의 내부 단편화가 발생.

- 쓰레싱 = Thrashing : 다중 프로그래밍의 정도가 너무 높아져서 페이지 교체가 빈번해지고, cpu 사용율이 저하되는 현상

- 페이지 교체 알고리즘

1. OPT : 앞으로 가장 오래 사용되지 않을 놈

2. FIFO

3. LRU : 사용된지 가장 오래된 놈

4. LFU : 사용빈도가 가장 낮은 놈

5. NUR = not used reccently : 참조비트와 변형비트로 우선순위를 나눴다.

참조0 변형0 >> 참조0 변형1 >> 참조1 변형0 >> 참조1 변형1

6. SCR = second chance replacement : FIFO에 참조 비트 추가 -> 참조비트가 1이면 살려준다. 두번의 기회.

- 워킹 셋 = working set : 프로세스가 일정 기간 동안 자주 참조하는 페이지들 집합. 지역성을 이용한 것이다.

2. 세그멘테이션 기법 : 가상 메모리를 여러 다른 타입의 세그먼트들로 나누고 할당해주기

- 커널 영역 / 스택 영역(지역변수, 매개변수) / 힙 영역(동적할당) / 데이터영역(전역, static 변수) / 등등

- 영역내에서 딱 원한 크기만큼 할당해주기 때문에 내부단편화는 없다.

- 하지만 영역의 타입이 다르면 아무리 공간이 있어도 못주기 때문에 외부단편화는 발생함.

- 디스크 스케쥴링 : 디스크상에 데이터가 여러 곳에 나뉘어 저장되어 있을 때, 디스크 헤더가 움직이는 경로를 결정하는 기법

1. FCFS : 디스크 대기 큐에 들어온 수대로 이동하기. 공평성은 보장된다.

2. SSTF = shortest seek-time first : 현재 헤드의 위치에서 가장 가까운 거리의 트랙으로 이동

- 한 쪽에 편중되어 기아 현상이 발생할 수 있다. 일괄처리 시스템에 적합.

3. SCAN : 한 쪽으로 쭈욱 처리, 역방향으로 쭈욱 처리

4. C-SCAN : 바깥쪽에서 안쪽으로만 움직이면서 처리. 안쪽을 다 처리했으면 바깥으로 이동해서 재개. 기아발생 가능성.

5. N-step : 이동하기 시작했을 때 대기였던 애들만 처리하고, 나중에 도착한 애들은 나중에 반대 방향 처리과정에서 처리한다.

6. 에션바흐 기법 : C-SCAN과 같으나, 모든 실린더는 실린더에 요청이 없더라도 한바퀴 돌려야 한다. 대신 한바퀴로 모두 처리되게 재배열한다.

7. SLTF = shortest latency time first

- 회전을 줄이기 위해(회전시간의 최적화) 요청들을 섹터 위치에 따라 재정렬한다. 고정헤드장치용

- 섹터 큐잉이라고도 한다.

8. LOOK : SCAN과 같으나 요청이 없어도 끝까지 가는 SCAN과 다르게, LOOK은 없으면 바로 역방향으로 진행한다.