Carpe Diem

1. Explain the differences between Preemptive Scheduling and Non-Preemptive Scheduling. What are the pros and cons of those?

A. Preemtive Scheduling(선점형 스케줄링) 

- 어떤 스레드가 CPU를 사용하고 있는 동안 다른 스레드에 의해 선점당하는 스케줄링 방식
- 장점: 우선순위가 높은 프로세스가 먼저 수행되어야 할 때 유용
           대화식 시분할 시스템이나 실시간 시스템에 유용
- 단점: 프로세스간에 문맥 교환이 자주 발생하기때문에 이로 인해 오버헤드가 크다.

B. Non-Preemtive Scheduling(비선점형 스케줄링)

- 어떤 스레드가 CPU 사용권을 다른 스레드에게 이양한 후에 다른 스레드가 그 CPU를 사용할 수 있게 되는 방식
- 프로세스가 일단 실행 상태(Running State)에 진입하게 되면 종료되거나 비자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않는다.
- 장점: 모든 프로세스들에 대한 공정한 요구처리가 가능하다.
           응답시간 예측이 용이하다.
- 단점: 짧은 작업이 긴 작업을 기다리는 경우가 초래한다.

2. Explain the Virtual Memory? What are the benefits of that?

- 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능한 기법으로 애플리케이션이 요구하는 메모리와 하드웨어 메모리 관리 유닛(MMU) 사이에 논리적인 계층을 두어 동작한다.
- 각 프로세스에게 독립적인 주소 공간을 제공하여 메모리 보호, 접근 관리등이 보장된다.
-  장점

○ 여러 프로세스를 동시에 실행 가능
○ 사용할 수 있는 물리메모리보다 많은 메모리를 필요로 하는 애플리케이션을 실행가능하게 함
○ 프로그램 코드 중 일부만 메모리에 로드해도 프로세스 실행가능
○ 라이브러리나 프로그램의 메모리 이미지 하나를 프로세스 사이에서 공유가능
○ 프로그램 재배치 가능
○ 기계 독립적 코드 작성 가능

3. What is Cache Memory? And are the benefits of using that?

- 빠른 접근 시간을 제공하는 기억 장치
- 느린 메모리 때문에 발생되는 프로세서 코어에 가해지는 메모리 엑세스 병목현상 감소
- 프로세서와 메모리 사이의 병목현상을 줄이기 위한 고속 메모리
- 지역성을 적극 활용한 것으로 자주 사용되는 데이터를 캐시에 저장하여 프로세서가 원활히 데이터를 사용할 수 있도록 함
- 장점

○ 가장 빠른 메모리의 속도에 근접한 메모리를 제공한다.

4. Explain the VFS(Virtual File System)?

- 표준 유닉스 파일시스템과 관련한 모든 시스템 콜을 처리하는 커널 소프트웨어 계층
- 실제 파일 시스템의 구현과 사용자 프로세스 사이에 존재하는 추상화 계층
- 여러 종류의 파일시스템에 대해 일반적인 공통 인터페이스를 제공

5. What is PCB(Process Control Block)? And what kinds of information are there?

- 수행 프로세스를 인터럽트 한 후 나중에 그 인터럽트가 발생되지 않은 것처럼 프로세스 수행을 재개할 수 있도록 충분한 정보를 유지하는 것
- 프로세스 식별자, 상태, 우선순위, 프로그램 카운터, 메모리 포인터, 문맥교환, 입출력 상태 정보, 어카운팅 정보

6. Explain the Paging Mechanism in memory management.

- 가상기억장치를 모두 같은 크기의 블록으로 편성하여 운용하는 기법이다. 이때의 일정한 크기를 가진 블록을 페이지라고 한다. 주소공간을 페이지 단위로 나누고 실제 기억공간은 페이지 크기와 같은 프레임으로 나누어 사용한다.
- 프로그램을 페이지 단위로 나누었기 때문에 프로그램 실행 시 모든 페이지가 메모리에 로드될 필요없이 요구된 페이지만을 로드함으로써 여러 프로세스를 실행하는 것이 가능해진다.

7. What is Race Condition among processes? How can we solve the problem?

chapter 7. Memory

· 메모리 관리가 만족시켜야 하는 요구 조건

1. 재배치(Relocation)

2. 보호(Protect)

3. 공유(Sharing)

4. 논리적 구성

5. 물리적 구성

2-pass assembler

지금 수행된 application Memory 초과에도 사용될 수 있는 방법

· Fetch policy : 불러들이는 방법

· Placement policy :

· Replacement policy :

· 단편화(Fragmentation)

- 내부 단편화(Internal Fragmentation) : 파티션 내부 공간의 낭비가 발생하는 현상

- 외부 단편화(External Fragmentation) : Compaction 수행 방법 필요

장점: 메모리 효율성 大, 공간 활용도 大

단점: 메모리 할당 속도↓, 할당 · 해지가 계속적으로 반복

해결책 → Compaction(메모리 집약): 프로세스가 사용하는 파티션을 이동시켜 각 파티션이 연속적이 되도록 인접하게 만들고 메모리의 모든 빈 공간이 하나의 블록이 되도록 한다.

· 메모리 분할 (Memory Partition)

- 고정 분할(Fixed Partitioning)

균등 분할: 각 분할이 모두 같은 크기를 작도록 균등 분할

문제점 1) 프로그램이 파티션보다 클 수 있다.

2) 주기억장치 이용률이 매우 저조 - 내부단편화 발생(Internal Fragmentation)

비균등 분할: 위의 문제점 해결

고정된 partition을 사용할 경우 잉여 공간(내부 단편화)이 다량으로 발생

- 동적 분할(Dynamic Partitioning) :

외부 단편화 → compaction

· Placement algorithm ≒ Fit policy

1. Best Fit : 요청된 크기와 가장 근접한 크기의 메모리 선택

공간 효율성 大, 남아있는 잉여구간이 적지만 사용가능성이 적다.

비어있는 구간을 모두 다 비교해야하므로 시간이 많이 걸린다.

2. First Fit : 메모리의 처음부터 검사해 크기가 충분한 첫 번째 사용가능한 메모리 블록을 선택

메모리 공간 효율성 小, 시간이 적게 걸림(가장 마지막 메모리 위치 효율성 ↓)

3. Worst Fit : 메모리 잉여 공간이 가장 큰 메모리 할당

생각보다 비효율적이지 않다. 분할된 구간이 커짐

→ 큰메모리 구간을 남겨둬서 1차적 사용가능

4. Next Fit : 가장 최근에 배치되었던 메모리 위치에서부터 검사를 시작해 크기가 충분한 다음 위치의 사용가능한 메모리 블록을 선택

5. Last Fit :

· 리눅스/유닉스에서 내부 단편화(Internal Fragmentation)를 해결하기 위해 Slab Allocator

Architecture 마다 다르지만 일반적으로 32Bits System에서 4KB 단위의 page Frame이 고정된 크기로 분할되어있다.

If, 메모리가 400KB를 요청한다면 Page 배수가 된다.

즉 Fixed partition과 Page 묶음으로 할당 해지하는 Dynamic partition으로 사용된다.

· 리눅스는 내부 단편화(Internal Fragmentation)를 해결하기 위해서 슬랩 할당자(Slab Allocator)를 도입하고, 버디 할당자(Buddy Allocator)는 메모리 관리의 부하가 적으며 외부 단편화(External Fragmentation)를 줄일 수 있다는 장점을 제공한다.

명령어 수행

1) 명령어 처리 두 단계

(1) 메모리로 부터 한 번에 하나의 명령어를 읽어 들임(fetch)(2) 읽어 들인 명령어 수행

(a)명령어 형식

(b)정수 형식

명령어와 데이터의 길이가 16비트일 때, 명령어 형식은 연산코드(opcode)를 위해 4비트를 할당할 경우 최대 ( 24 = 16 개 )의 서로 다른 연산코드사용 가능할 수 있으며, 명령어 형식으로 나머지 12비트를 사용할 경우 최대 ( 212 = 4,096(4K) ) 워드 까지 직접 주소 지정 가능하다.

1. 중첩인터럽트 처리 방법

1) 하나의 인터럽트를 처리하는 동안 다른 인터럽트를 금지(disable)시킨다.

· 금지된 인터럽트: 단순히 처리기가 인터럽트 요구 신호를 무시한다는 의미

ex) 인터럽트 금지 기간 동안에 발생한 인터럽트는 처리되지 않은 채 남겨져 있게 되고, 처리기가 인터럽트 발생을 허용한 후에 처리된다.

· 단점: 우선순위나 시간 긴급(time-critical) 요구를 고려하지 않고 있다.

2) 인터럽트 간의 우선순위를 정하고 높은 우선순위 인터럽트가 낮은 우선순위 인터럽트를 인터럽트 할 수 있도록 허용하는 것이다.

* First-Come-First-Served(FCFS)

- 비선점형(Non-preemptive)

- 가장 단순한 형태의 스케줄링 정책이며, FIFO(First-Input-First-Output)라고도 불린다.

- 짧은 프로세스보다는 긴 프로세스에 유리하다.

* Round-Robin(RR)

- 선점형(Preemptive)

- 시간 할당량(Time Slicing 또는 Time Quantum) 기법

- 모든 프로세스는 한 번에 정해진 시간 조각만큼만 실행 한 후 강제적으로 CPU를 빼앗는다.

* Shortest Process Next(SPN)

- 비선점형(Non-preemptive)

- 가장 짧은 프로세스를 먼저 수행

- 구현 불가능(각 프로세스가 요구하는 총 실행시간을 미리 알아야 함)

* Shortest Remaining Time(SRT)

- 선점형(Preemptive)

- 예상되는 남아 있는 실행시간이 가장 짧은 프로세스가 선택

* Highest Response Ratio Next(HRRN)

- 비선점형(Non-preemptive)

- 반환 시간(TAT) : 프로세스가 시스템에 진입한 후 대기한 시간과 실행한 시간을 모두 합쳐 결국 시스템 내에서 머문 총 시간을 의미한다.

실제 서비스 시간 대비 반환시간의 비율을 나타낸다.

- R(응답 비율) = ( time spent waiting(처리기를 기다리며 대기한 시간) + expected service time(예상되는 서비스 시간) ) / expected service time(예상되는 서비스 시간)

- 대기시간이 길어지면 R값이 커지기 때문에 스케줄러에게 보상 받는다.

- 계산시간이 복잡하고 증가면 이 알고지름의 시간 복잡성이 증가하여 오버헤드가 발생할 가능성이 크기 때문에 고려해야한다.

* 스케줄링 정책들의 비교 분석 *

<FCFS>

<RR q=1>

<RR q=4>

<SPN>

<SRT>

<HRRN>

<Feedback>

Chapter 9. Uniprocessor Scheduling

* 스케줄링의 목적

- 처리기가 다음에 실행할 프로세스를 선택하는 것

- 응답시간(Response time)

- 처리량(Throughput)

- 효율성(Processor efficiency)

* 스케줄링의 종류

- 장기 스케줄링(Long-Term Scheduling)

· 프로세스를 시스템으로 집입시킬지 여부를 결정

· 다중프로그래밍의 정도를 제어하는 역할

- 중기 스케줄링(Medium-Term Scheduling)

- 단기 스케줄링(Short-Term Scheduling)

· 디스패처(Dispatcher)

· CPU에 의해 실행될 다음 번 프로세스로 어떤 프로세스를 선택할지를 결정

· 자주 실행됨

* 단기 스케줄링 평가 기준들

· 사용자 중심의 성능 관련 평가 척도

- 반환 시간(Turnaround Time): 프로세스가 시스템으로 진입한 후부터 종료할 때까지 걸린 시간

- 응답시간(Response Time): 프로세스가 시스템에 요구를 한 후 이에 대한 시스템으로부터의 첫 번째 응답이 올 때까지의 시간

- 완료 기한(Deadline): 프로세스가 완료 되어야 하는 시점

· 사용자 중심의 기타 평가 척도

- 예측가능성(Predictability): 같은 작업이라면 실행 될 때마다 동일한 기간 동안 실행되어야 하고, 시스템의 부하 정도에 상관없이 동일한 비용으로 실행되어야 한다. 만일 실행할 때 마다 지나치게 차이가 난다면, 사용자들은 시스템을 신뢰하지 못하게 될 것이다.

· 시스템 중심의 성능 관련 평가 척도

- 처리량(Throughput): 단위시간 내에 실행을 완료 시킬 수 있는 프로세스의 수

- 처리 이용률(Processor utilization): 전체 시간 중에 처리기가 바쁘게 실행을 한 시간의 비율

· 시스템 중심의 기타 평가 척도

- 공정성(Fairness):

- 우선순위 부여(Enforcing Priority):

- 균형있는 자원 활용(Balancing Resources):

*　우선순위(Priorities)

- 스케줄러는 항상 높은 우선순위의 프로세스를 선택

- 문제점: 순수 우선순위 기반 스케줄링 방식에서 높은 우선순위의 프로세스가 계속적으로 생성되고 낮은 우선순위의 프로세스가 계속 CPU를 할당 받지 못해 기아(Starvation) 발생

* 결정 모드

- 비선점(Non-preemptive)

· 프로세스가 일단 실행 상태(Running State)에 진입하면 종료되거나 자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않는다.

- 선점(Preemptive)

· 현재 실행 중인 프로세스라고 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동된다.

· CPU를 빼앗을 수 있다.