운영체제

#질문

[운영체제]

• 외부단편화와 내부단편화.
• 멀티 프로그래밍, 멀티 프로세싱, 멀티스레드 차이
• 디스페처란?
• 인터럽트 설명하기, Trap?
• 스케줄링이 뭐고 종류가 무엇이있고 언제사용?
• 동기화란?
• Aging기법이란?
• Race Condition 설명
• 세마포어란? 어떻게 구현?
• 모니터는?
• 뮤텍스?
• 데드락(교착상태) 설명
• 락이란?
• Process와 Process API?
• System Call이란?
• Thread?
• CPU 스케줄링
• 페이징과 세그멘테이션

---

#답

[운영체제]

• *외부단편화와 내부단편화.

내부단편화 - 50mb 공간에 30mb 작업을 올리면 쓰지못하는 20mb공간을 의미

외부단편화 – 프로세스들이 메모리를 적재하고 제거되는 일이 반복되면, 작은 자유공간들이 생기고, 그 공간들이 충분한데도 메모리를 적재못하는 것

---

• *멀티 프로그래밍, 멀티 프로세싱, 멀티스레드 차이

멀티 프로그래밍 – 하나의 프로세서로 다수의 프로세스를 적재하여 번갈아가며처리.

멀티 프로세싱 – 하나의 컴퓨터에 여러 cpu(프로세서) 장착. 하나 이상의 프로세스 동시처리

멀티 스레드 – 하나의 프로세스에서 여러 스레드를 형성하여 명령어 처리.

멀티 테스킹 – 테스크란 작업단위, 하나의 cpu가 수시로 프로세스 변경, 여러 작업이 동시에 처리되는것처럼 보이는 것

---

• *디스페처란?

프로그램실행 -> 프로세스 생성 -> Ready Queue -> CPU에 할당

이를 준비상태(레디큐) -> 실행상태(CPU)로 상태전이

이 과정을 디스패처가 함.

---

• *인터럽트 설명하기, Trap?

Interrupt

프로그램 수행 중 CPU가 강제로 제어를 가져오는 것.

주로 허용되지 않은 작업이 수행될 때 발생(비동기적)

Interrupt가 발생하면 명령어의 위치가 있는 interrupt Vector로 이동하여 수행.

인터럽트 처리는 문맥교환이 이뤄짐(현재 자신의 상태 기억하고 이동)

 

#종류

- Trap : 인터럽트의 한 종류, 명령의 수행 결과로 발생(동기적)

   System call 호출, Segmentation fault(할당되지 않은 메모리 참조)가 발생.

- 내부 인터럽트 : 하드웨어, 실행할 수 없는 명령어, 명령어 오류(나누기 0), 사용권한 위배

- 외부 인터럽트 : 주로 입출력 장치.

 

---

• *문맥교환?

하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)을 보관하고 새로운 프로세스 적재하는 과정.

---

• *스케줄링이 뭐고 종류가 무엇이있고 언제사용?

#목적

CPU자원을 효율적으로 사용하기 위함.

프로세스가 실행되고, 필요한 자원을 시스템에게서 받아오기 위함.

 

#비선점, 선점

1)선점

- SRT : 남은 처리 시간이 짧은 프로세스대로 프로세스를 실행.

- RR : 각 프로세스는 같은 크기의 CPU시간을 할당. 할당시간이 너무 크면 선입선출

- MQ : Ready큐를 여러개 사용하는 기법, 각각의 큐는 자신의 스케줄링 알고리즘 수행.

- MFQ : 다단계 큐와 비슷. 프로세스 들이 큐를 이동.

 

2)비선점

- HRN : 긴 작업과 짧은 작업간의 지차닌 불평등을 보완

  우선순위 = 대기시간 + 서비스시간 / 서비스시간

- FIFO(FCFS) : 프로세스들은 Ready큐에 도착한 순서대로 CPU를 할당.
- SJF : 큐 안에 있는 프로세스 중 수행시간이 짧은 것을 먼저 수행, 평균대기시간을 감소.

---

• *Aging기법이란?

시스템에 많은부하로 낮은등급에 있는 준비큐의 프로세스가 무한정기다림(기아현상)

->오랫동안 기다린 프로세스에게 우선순위를 높여주는 일.

---

• *Race Condition 설명과 동기화

경쟁상황 – 동일한 자료에 접근, 조작하며 순서에만 의존하여 나온 결과.

동기화 – 한 번에 한 프로세스만 자료에대한 접근을 허용하게 하는 것.

->임계영역을 둠(자신이 이영역에서 작업중엔 다른 놈이 못들이게)

->임계영역이란 동신에 자원을 접근할 가능성이 있는 코드.

---

• *세마포어란? 어떻게 구현? 뮤텍스? 모니터?

1)세마포어 – 뮤텍스와 유사. 수행할 수 있는 스레드를 여러개 제한.

2)뮤텍스 – 공유 자원에 접근을 하나의 스레드로 제한. 다른프로세스 스레드제어가능

3)모니터 – 프로세스나 스레드를 동기화하는 구현된 기능 혹은 모듈.

고급언어에서 이기능 제공.

한번에 하나의 프로세스만 모니터에서 활동하도록 보장.

---

• *데드락(교착상태) 설명

#설명

첫 번째 스레드와 두 번째 스레드가 자신이 들고있는 자원을 잡고 서로의 자원을 무한정 기다리는 형태.

서로의 락이 풀리기를 기다림.

 

#교착상태 발생 조건

1)상호배제

2)점유와 대기

3)비선점

4)순환대기

 

#예방과 회피

- 예방 : 4가지 교착상태 발생 조건 중 하나를 빼버리는 것.

  -> 심각한 기능 저하를 초래.

- 회피 : 자원할당그래프 알고리즘, 은행원 알고리즘

   은행원(다이직스트라) - 네비에도 씀. 안전상태만 수락, 불안전상태 불수락

   데드락에 빠지지 않을 경우에만 자원을 할당.

---

• 락이란?

#설명

critical section(임계구역) - 여러 Thread에서 동시에 실행되면 안되는 부분.

임계구역에 하나의 Thread만 접근이 가능하도록 lock을 획득 및 반환.

 

#평가기준

1)상호 배제

정말 1개의 Thread만 임계구역에 접근이 가능한지.

2)공평성(Fairness)

오랫동안 코드를 실행하지 못하는(기아) Thread가 없도록 공평하게 lock을 획득하는지.

3)효율성(Performance)

lock을 사용하는 비용이 합당한지.

 

#방법

1)인터럽트 제한.

timer interrupt 때문에 순서가 바뀜

->임계구역에서는 interrupt가 발생하지 않도록 하지 않을까??

이 방법의 문제점!

- 개발자가 의도적으로 전체 코드를 임계구역을 만들어 CPU 독점 가능성.

- I/O 작업이 끝나서 오는 interrupt등의 필수적 interrupt를 수신 x.

- 멀티프로세서 환경에서는 동작 x.

- 비효율적.

2)Flag를 이용한 lock

flag 변수를 하나두어 lock()호출 시 flag를 1로 만들고 1일 때는 critical section에 접근 하지 못하게함.

구현 방법

- 만약 flag가 0이면, flag를 1로 만들고(임계구역 사용중), 끝나면 flag를 0으로 만듬.

문제점!

- Thread 1가 flag0임을 확인하고, flag1로 만들고 임계구역을 진입 직전 과정에, 인터럽트

Thread 2도 flag0이기 때문에 flag1로 만들고 진입.

->상호배제를 불만족

3)Fetch-and-Add

Thread에 숫자를 하나씩 증가시켜 차례대로 Thread를 진입하게함.

기아현상이 발생하지 않고, 공평한 기회 분배.

---

• Process와 Process API?

프로세스 - 실행중인 프로그램

프로그램 - 명령어의 목록

프로세스 제어 블록(PCB, Process Control Block) - 프로세스 요소들의 자료구조

- 프로세스 식별자

- 상태

- 우선순위

- 메모리 포인터

- 프로그램 카운터

- 프로세스 상태(생성,준비,실행,대기)

- I/O 상태정보

프로그램 실행 - 명령어 목록(코드)를 메모리에 할당하여 수행하는 것.

- 생성(New) : 프로세스가 생성 되었지만, 메모리에 적재되지 않은 상태.

- 준비(Ready) : CPU를 할당받기 위해 기다리는 상태.

- 실행(Running) : CPU를 할당받아 명령어를 실행중인 상태.

- 대기(Block) : 어떤 사건이 발생하기를 기다리고 있는 상태.

프로세스 상태 전이도(5상태 모델)

프로세스 API

OS가 Application에게 제공하는 Interface.

프로세스의 생성,종료,정지,재개의 프로세스 상태를 알려주는 기능.

보편적으로 System Call이라고 함.

---

• System Call이란?

System Call이란 OS가 Application에게 제공하는 Interface.

 

#사용이유?

프로세스의 실행, 종료, IO작업등의 명령을 사용자가 함부로 사용시, 문제가 될 명령들을 Privileged Instruction으로 분류하여 막아놓음 -> OS가 제공하는 System Call을 사용해야함!

 

#System Call 수행과정

1)User Mode : 프로세스의 System Call 호출 > Trap 발생 > Kernel Mode

2)Kernel Mode : System Call 처리 > return-form-trap > User Mode

---

• Thread란?

프로세스 내에서 실행되는 흐름의 단위.

Heap, Data, Bss, Code영역은 하나의 프로세스에서 공유.

각각의 스택 영역을 가짐.

#장점

- 사용자에 대한 응답성 향상

  하나의 프로세스 생성시, 두개의 쓰레드를 이용(계산하는 기능과 사용자와 인터페이스 기능)

  응용 프로그램의 일부분 봉쇄 및 긴 작업 수행에도 사용자에대한 응답이 가능.

- 자원 공유 효율

  스레드는 그들이 속한 프로세의 자원 메모리 공유.

- 경제성

  한 프로세스의 자원을 공유함으로 프로세스를 생성하는 것보다 오버헤드를 줄임.

 

#단점

- 스레드 포함 전체 작업이 대기

  사용자 수준 스레드는 커널 자체가 스레드 하나로 구성.

  시스템 호출 실행 시 해당 스레드가 포함된 전체 작업이 시스템 호출 결과가 돌아올때 까지 대기.

- 한 스레드가 터지면 전체 프로세스가 영향

- 스레드를 많이 생성시 잦은 Context switching(문맥교환)

  성능 저하.

- 프로세스 영영을 공유하기 때문에, 동기화가 필요.

 

---

• CPU 스케줄링

#목표

실행 중인 모든 프로세스에게 골고루 cpu를 할당.

시스템 용도에 따라 효율적인 알고리즘 선택하는게 중요.

 

#비선점 스케줄링

1. FCFS (First Come First Served)
   • 큐에 도착한 순서대로 CPU 할당
   • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
2. SJF (Shortest Job First)
   • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
   • FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리

#선점 스케줄링

1. Priority Scheduling

   • 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
   • 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
   • Aging 방법으로 Starvation 문제 해결 가능

2. Round Robin

   • FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할달 받음
     • Time Quantum or Time Slice : 실행의 최소 단위 시간
   • 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가

3. Multilevel-Queue (다단계 큐)

- 정의

우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용

 

# 기능의 척도

1) 응답시간(resonose Time)

 작업이 처음으로 실행되기까지의 시간

2) 반환 시간(Turnaround Time)

 실행시간과 대기시간을 모두 합한시간으로 작업이 완료될때가지의 시간

 

---

• 페이징과 세그먼테이션

- 사용 이유

 다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리관리 작업 필.

 

- 불연속 메모리 관리

 프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법

 

- 용어

 페이지 : 고정 사이즈의 작은 프로세스 조각(고정크기)

 세그먼트 : 서로 다른 크기를 가진 논리적 블록(가변크기)

 단편화 : 기억장치의 빈공간 or 자료가 여러 조각으로 나뉨