[WIL] Day 18

~~~프로세스 개요~~~
포그라운드 프로세스(foreground process): 사용자가 볼 수 있는 공간에서 실행되는 프로세스

백그라운 프로세스(background process): 사용자와 직접 상호작용이 가능한 백그라운드 프로세스, 사용자와 상호작용하지 않고 그저 정해진 일만 수행하는 프로세스(데몬, 서비스)

 

프로세스 제어 블록

• 모든 프로세스는 실행을 위해 CPU가 필요
• 그러나 CPU자원은 한정
• 프로세스는 한정된 시간 만큼만 cpu사용. 
• 빠르게 번갈아 수행되는 프로세스들을 관리해야
• 이를 위해 사용하는 자료구조가 프로세스 제어 블록(PCB)

PCB에 담기는 대표적인 정보

• PID
• 레지스터 값: 프로세스는 자신의 실행 차례가 오면 이전까지 사용한 레지스터 중간 값을 모두 복원 -> 실행 재게. 예) 프로그램 카운터,…
• 프로세스 상태: 입출력 장치를 사용하기 위해 기다리는 상태, CPU를 사용하기 위해 기다리는 상태, CPU이용중인 상태
• CPU스케줄링 정보: 프로세스가 언제 어떤 순서로 CPU를 할당받을지의 정보
• 메모리 정보: 프로세스가 어느 주소에 저장되어 있는지에 대한 정보, 페이지 테이블 정보(지금으로서는 ‘메모리 주소를 알 수 있는 정보가 담기는구나’ 정도로)
• 사용한 파일과 입출력장치 정보: 할당된 입출력장치, 사용중인(열린) 파일 정보

 

문맥 교환(context switch)

한 프로세스에서 다른 프로세스로 실행 순서가 넘어가면?

• 기존에 실행되던 프로세스 A는 지금까지의 중간 정보를 백업
• 뒤이어 실행할 프로세스 B의 문맥을 복구

 

그렇다면 사용자 영역에는 어떻게 저장됨?

크게 코드 영역(=텍스트 영역), 데이터 영역, 힙 영역, 스택 영역.

코드 영역(=텍스트 영역)

• 실행할 수 있는 코드, 기계어로 이루어진 명령어 저장
• 데이터가 아닌 CPU가 실행할 명령어가 담기기에 쓰기가 금지된 영역(read-only)

데이터 영역

• 잠깐 썼다가 없앨 데이터가 아닌 프로그램이 실행되는 동안 유지할 데이터 저장, 전역 변수

힙 영역

• 프로그램을 만드는 사용자, 프로그래머가 직접 할당할 수 있는 저장공간

스택 영역:

• 데이터가 일시적으로 저장되는 공간, 매개 변수, 지역 변수

 

 

~~~프로세스 상태와 계층 구조~~~

PCB에 기록되는 프로세스 상태. 

 

프로세스 상태

• 생성 상태: 이제 막 메모리에 적재되어 PCB를 할당 받은 상태, 준비완료되면 준비 상태로 
• 준비 상태: 당장이라도 CPU를 할당 받아 실행할 수 있지만, 자신의 차례가 아니기에 기다리는 상태, 자신의 차례가 된다면 실행 상태로(디스패치) 
• 실행 상태: CPU를 할당 받아 실행 중인 상태, 할당된 시간 모두 사용시 준비 상태로, 실행 도중 입출력장치를 사용하면 입출력 작업이 끝날때까지 대기 상태로.
• 대기 상태: 프로세스가 실행 도중 입출력장치를 사용하는 경우. 입출력 작업은 CPU에 비해 느리기에 이 경우 대기 상태로 접어듬. 입출력 작업이 끝나면 준비 상태로. 
• 종료 상태: 프로세스가 종료된 상태, PCB, 프로세스의 메모리 영역 정리.

 

프로세스 계층 구조

• 프로세스 실행 도중(시스템 호출을 통해) 다른 프로세스 생성 가능
• 새 프로세스를 생성한 프로세스 : 부모 프로세스
• 부모 프로세스에 의해 생성된 프로세스 : 자식 프로세스

부모와 자식은 다른 PID가짐. 일부 운영체제는 PPID명시함. 그리고 자식은 또 자식 낳고해서 계층 구조가 됨.

 

프로세스 생성 기법

부모 프로세스는 자식 프로세스를 만들고, 자식 프로세스는 어떻게 자신만의 코드를 실행하나?

복제와 옷 갈아입기, 

• 부모 프로세스는 fork 시스템 호출을 통해 자신의 복사본을 자식 프로세스로 생성
• 자식 프로세스는 exec 시스템 호출을 통해 자신의 메모리 공간을 다른 프로그램으로 교체

 

Fork 시스템 호출 

• 복사본(=자식 프로세스)생성
• 부모 프로세스의 자원 상속

 

Exec 시스템 호출

• 메모리 공간을 새로운 프로그램으로 덮어쓰기 
• 코드/데이터 영역은 실행할 프로그램 내용으로 바뀌고 나머지 영역은 초기화

 

~~~스레드~~~

스레드는 프로세스를 구성하는 실행 흐름의 단위 

하나의 프로세스는 하나 이상의 스레드를 가질 수 있다. 

 

실행 흐름이 하나인 프로세스(단일 스레드 프로세스)

여러 프로세스(멀티 스레드 프로세스)->프로세스를 이루는 여러 명령어 동시 실행 가능

 

스레드의 구성 요소

스레드 ID, 프로그램 카운터를 비롯한 레지스터 값, 스택 등, 그리고 실행에 필요한 최소한의 정보. 스레드들은 프로세스의 자원들을 공유한다. cpu에 전달하는 단위가 되기도 한다. 모든 프로세스는 자원을 공유한다. 

 

멀티 프로세스와 멀티 스레드 차이점

동일한 작업을 수행하는 단일 스레드 프로세스 여러 개 실행 vs 하나의 프로세스를 여러 스레드로 실행. 

프로세스끼리는 자원을 공유하지 않지만 스레드끼리는 같은 프로세스 내의 자원을 공유한다.

• 프로세스를 fork하면 코드/데이터/힙 영역 모든 자원이 복제
• 저장된 메모리 주소를 제외하면 모든 것이 동일한 프로세스 두개가 통째로 메모리에 적재
• Fork직후 같은 프로세스를 통째로 적재하지 않으면서 자원을 공유하지 않는 방법도 있고 이를 copy on write기법이라 한다. 

 

스레드들은 각기 다른 스레드 ID. PCB하나. 프로그램 카운터 값을 포함한 레지스터 값, 스택을 가질 뿐 자원을 공유. 

 

프로세스간에서 자원을 ㄱ주고받을 수 있다: 프로세스 간 통신(IPC)

파일을 통한 프로세스 간 통신, 공유 메모리를 통한 프로세스 간 통신

 

~~~CPU 스케줄링 개요~~~

CPU스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것. 

 

가장 공정한 CPU스캐줄링? 프로세스마다 우선순위가 다르다.

입출력 작업이 많은 프로세스의 우선순위는 CPU작업이 많은 프로세스의 우선순위보다 높다. 

 

프로세스 우선순위(priority)는 PCB에 저장되어 있음.

스케줄링 큐. 모든 PCB를 뒤적거리는 거는 오래걸리기 때문에 스케줄링 큐를 사용.

해당 큐는 반드시 FIFO일 필요는 없다.

준비큐와 대기 큐, 준비큐는 CPU를 이용하기 위해 기다리는 줄이고 대기큐는 입출력장치를 이용하기 위해 기다리는 줄이다.

대기 큐: 같은 장치를 요구한 프로세스들은 같은 큐에서 대기

 

선점형과 비선점형 스케줄링 

특정 프로세스가 cpu를 사용하고 있는데 어떤 프로세스가 급하게 cpu사용할려는 경우

• 할당해주기 -> 선점형 스케줄링
• 기다리게하기 -> 비선점형 스케줄링

선점형 장점: 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원 배분

단점: 문맥 교환 과정에서 오버헤드 발생

 

비선점형 장점: 문맥교환 오버헤드 적다

단점: 모든 프로세스 자원 골고루 배분할수 없다.

 

~~~CPU 스케줄링 알고리즘~~~

7가지 알고리즘.

 

1. 선입 선처리
2. 최단 작업 우선
3. 라운드 로빈
4. 최소 잔여 시간 우선
5. 우선순위
6. 다단계 큐 
7. 다단계 피드백 큐

 

선입 선처리 스케줄링(FCFS First Come First served)

단순히 준비 큐에 삽입한 순서대로 처리하는, 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용.

 

최단 작업 우선(SJF Shortest Job First): CPU사용이 긴 프로세스 나중에 실행, CPU사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링

라운드 로빈(RR, Round Robin): 선입 선처리 + 타임 슬라이스

타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 사간

정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링, 그래서 타임 슬라이스의 크기가 중요.

 

최소 잔여 시간 우선 스케줄링(SRT, shortest remaining time)

최단 작업 우선 + 라운드 로빈

정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택

 

우선 순위

• 프로세스들에게 우선순위를 부여, 우선순위 높은 프로세스부터 실행
• 우선순위가 같으면 선입 선처리로 스케줄링
• starvation(기아)현상, 
• 우선순위 낮은 프로세스는 한도 끝도 없이 실행 연기
• 이를 방지하기 위해 에이징
• 오랫동안 대기한 프로세스의 우선순위를 높이게 하는 방식.

 

다단계 큐= Multilevel queue스케줄링

• 우선순위 스케줄링의 발전한 형태
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식. 큐 별로 스케줄링 다양하게 
• 큐간의 우선순위 교환이 안됨 -> starvation

 

다단계 피드백 큐: 큐간의 이동이 가능하다. 

 

~~~동기화란~~~

동시다발적으로 실행되는 프로세스들은 서로 협력하며 영향을 주고 받는다 이 과정에서 자원의 일관성을 보장해야 한다.

 

공동의 목적을 위해 동시에 수행되는 프로세스, 워드 프로세서 그래서 동기화 필요

프로세스들의 수행 시기를 맞추는 것. 

• 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기
• 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기

 

실행 순서 제어를 위한 동기화: reader writer problem

Writer : Book.txt파일에 값을 저장하는 프로세스

Reader: Book.txt 파일에 저장된 값을 읽어들이는 프로세스

리더 프로세스는 Book.txt안에 값이 존재한다는 특정 조건이 만족되어야 실행 가능.

 

상호 배제를 위한 동기화 : Bank account problem

공유가 불가능한 자원의 동시 사영을 피하기 위한 동기화

한번에 하나의 프로세스만 접근해야 하는 자원에 동시 접근을 피하기 위한 동기화

잔액 10만원, 프로세스는 A는 2만원 추가, 프로세스 B는 5만원 추가. 

무작정 실행 -> 계좌잔액 무조건 17만원? 실상은 다른 값이 들어가 있을 수도.

 

Product & Consumer problem

물건을 계속해서 생산하는 생산자

물건을 계속해서 소비하는 소비자

“총합” 변수 공유. 동기화없이 각 10000번 실행하면 이상한 값이 생김. 총합에 동시에 접근해서 발생한 문제

 

공유 자원: 여러 프로세스 혹은 스레드가 공유하는 자원. 전역 변수, 파일, 입출력장치, 보조 기억장치.

임계 구역: 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역. 

임계 구역에 진입하고자 하면 대기해야 한다. 레이스 컨디션, 임계 구역에 동시에 접근하는 것을 레이스 컨디션이라고 한다.

 

운영체제가 임계구역 문제를 해결하는 3가지 원칙

1. 상호 배제: 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 들어올 수 없다.
2. 진행: 임계 구역에 어떤 프로세스도 진입하지 않았다면 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
3. 유한 대기: 한 프로세스가 임계 구역에 진입하고 싶다면 언젠가는 임계 구역에 들어올 수 있어야 한다. 

 

~~~동기화 시법~~~

동기화 기법 중 뮤텍스 락, 세마포, 모니터

 

뮤텍스 락

상호 배제를 위한 동기화 도구(자물쇠 역할).

뮤텍스 락의 단순한 형태: 전역 변수 하나, 함수 두개

자물쇠역할: 프로세스들이 공유하는 전역 변수 lock

임계 구역을 잠그는 역할: acquire 함수

임계 구역을 잠금을 해제하는 역할: release 함수

바쁜 대기(busy waiting), 임계구역을 while써서 확인하는것.

 

세마포

• 좀 더 일반화된 방식의 동기화 도구
• 공유 자원이 여러개 있는 경우에도 적용 가능
• 임계 구역 앞에서 멈춤 신호를 받으면 잠시 기다리기
• 임계 구역 앞에서 가도 좋다는 신호를 받으면 임계 구역 진입

 

임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S

임계구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait함수

임계구역 앞에서 기다리는 프로세스에 ‘이제 가도 좋다’고 신호 주는 signal 함수. 

비지 웨이팅 얘도 있음 -> cpu사이클 낭비

해결법: 사용할 수 있는 자원이 없을 경우 대기 상태로 만듬(해당 프로세스의 PCB를 대기 큐에 삽입)

사용할 수 있는 자원이 생겼을 때 대기 큐의 프로세스를 준비 상태로 만듬(PCB에서 꺼내 준비 큐에 ㄱ)

 

세마포의 변수 S를 0으로 두고, 먼저 실행할 프로세스 뒤에 signal 함수, 다음에 실행할 프로세스 앞에 wait 함수를 붙이면 p1->p2순서로 실행

 

모니터

세마포 누락시에 문제가 있을 수 있다. 그래서 모니터. 

상호 배제를 위한 동기화

• 인터페이스를 위한 큐
• 공유자원에 접근하고자 하는 프로세스를 큐에 삽입
• 큐에 삽입된 순서대로 공유 자원 이용

실행 순서 제어를 위한 동기화

• 조건 변수 이용, 조건 변수 큐 사용.
• 조건 변수.wait(): 대기 상태로 변경, 조건 변수에 대한 큐에 삽입
• 조건 변수.signal(). wait()으로 대기 상태로 접어든 조건 변수를 실행 상태로 변경

 

~~~교착 상태란(deadlock)~~~

식사하는 철학자 문제. 

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

해결하기 위해

1. 교착 상태가 발생했을 때의 상황을 정확히 표현
2. 교착 상태가 일어나는 근본적인 이유 이해하기

 

자원 할당 그래프로 교착 상태 발생 조건 파악 가능

• 어떤 프로세스가 어떤 자원을 할당 받았는지
• 어떤 프로세스가 어떤 자원을 기다리는지 확인 가능

교착 상태의 자원 할당 그래프는 원의 형태

 

교착 상태가 발생할 조건

1. 상호 배제: 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기: 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3. 비선점: 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
4. 원형 대기: 프로세스들이 원의 형태로 자원을 대기하는 상태

 

~~~교착 상태 해결 방법~~~

예방, 회피, 검출 후 회복으로 교착 상태 해결.

 

예방:

• 애초에 교착 상태가 발생하지 않도록
• 교착 상태 발생 조건 중 하나를 없애버리기

 

• 점유와 대기를 없애면? 이론은 가능, 자원의 활용률을 낮추게 됨.
• 비선점 조건을 없애면? 모든 자원이 선점 가능한 것은 아니다
• 원형 대기 조건을 없애면? 자원에 번호를 붙이고 오른차순으로 할당하면 원형 대기는 발생하지 않음. 자원에 번호 붙이는 것이 어려운 작업, 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다. 

 

회피:

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
• 교착 상태가 발생하지 않을 만큼 조심조심 할당하기
• 배분할 수 있는 자원의 양을 고려하여 배분

 

• 안전 순서열: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안전 상태: 교착 상태 없이 모든 프로세스가 자원을 하라당 받고 종료될 수 있는 상태
• 불안정 상태: 교착 상태가 발생할 수 있는 상태

 

검출 후 회복:

• 교착 상태의 발생을 인정하고 사후에 조치
• 선점을 통한 회복, 프로세스 강제 종료를 통한 회복
• 교착 상태가 해결될때까지 한 프로세스씩 자원을 몰아주는 방식
• 교착 상태에 놓인 프로세스 모두 강제종료/하나씩 종료

 

타조 알고리즘:

• 교착 상태 무시

 

~~~연속 메모리 할당~~~

연속 메모리 할당 : 프로세스에 연속적인 메모리 공간을 할당

 

스와핑:

현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고 그렇게 생긴 빈 공간에 새 프로세스 적재

프로세스들이 요구하는 메모리 공간 크기 > 실제 메모리 크기. Free, top으로 스왑 영역 크기 확인하기.

 

프로세스는 메모리의 빈공간에 할당되어야 한다. 빈공간이 여러개 있다면?

• 최초 적합, 최적 적합, 최악 적합

 

최초적합(first-fit)

빈공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 바로 할당

 

최적 적합(best-fit)

모든 빈공간 검색하고 적재 가능한 가장 작은 공간에 적재한다.

 

최악 적합(worst-fit)

적재 가능한 가장 큰 공간에 할당.

 

외부 단편화

• 사실 프로세스를 연속적으로 메모리에 할당하는 방식은 메모리를 효율적으로 사용하는 방법이 아니다
• 외부 단편화라는 문제가 발생하기 때문 
• 프로세스들이 실행되고 종료되길 반복하며 메모리 사이 사이에 빈공간 발생, 메모리가 낭비됨.
• 해결1: 메모리 압축, 빈 공간을 하나로 합치고 재배치. 오버헤드가 크다. 
• 해결2: 가상 메모리 기법, 페이징

 

 

~~~페이징을 통한 가상 메모리 관리~~~

가상 메모리

• 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
• 페이징, 세그멘테이션 

 

페이징이란

• 외부 단편화가 발생했던 근본적인 문제, 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문.
• 페이징은 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당
• 프로세스의 논리 주소 공간을 페이지라는 일정 단위로 자르고 
• 메모리의 물리 주소 공간을 프레임이라는 페이지와 동일한 일정한 단위로 자른 뒤
• 페이지를 프레임에 할당하는 가상 메모리 관리 기법  

 

페이징에서의 스와핑

• 프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑인 스왑아웃
• 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑아웃
• 실행에 필요한 페이지들은 메모리로 스왑인
• 달리 말해 물리 메모리보다 큰 프로세스도 실행될 수 있다. 
• 문제는: 프로세스가 메모리에 불련속적으로 있어서 cpu가 순차적으로 실행할 수 없고 다음에 실행할 명령어 위치를 모름

 

페이지 테이블

• 페이지 번호와 프레임 번호를 짝지어주는 일종의 이정표
• 프로세스마다 페이지 테이블이 있다
• CPU는 그저 논리 주소를 순차적으로 실행하면 될뿐
• 내부 단편화(또 다른 문제)

 

PTBR

-프로세스마다 페이지 테이블이 있고, 각 페이지 테이블은 CPU내의 프로세스 테이블 베이스 레지스터(PTBR)가 가리킨다. 

• 문제점, 메모리에 있으면 메모리 접근 시간 2배로. 

 

TLB

• CPU곁에 페이지 테이블의 캐시 메모리, 페이지 테이블의 일부를 가져와 저장
• TLB히트, 미스가 존재.

 

페이징에서의 주소 변환

어떤 페이지/프레임에 접근하고 싶은지

접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지 알아야한다. 

• 페이징 시스템에서의 논리 주소

<페이지 번호, 변위>로 이루어진 논리 주소는 페이지 테이블을 통해 <프레임 번호, 변위>로 변환된다. 

 

페이지 테이블의 각각의 행: 페이지 테이블 엔트리(PTE):

• 유효 비트(현재 해당 페이지에 접근 가능한지 여부)
• 유효 비트가 0인 페이지에 접근하려고 하면? 페이지 폴트(page fault)라는 인터럽트 발생

 

보호비트:

• 페이지 보호 기능을 위해 존재하는 비트

참조 비트: CPU가 이 페이지에 접근한 적이 있는지 여부

수정 비트: CPU가 이 페이지에 데이터를 쓴적이 있는지 여부, 스와핑할때 필요. 

 

쓰기식 복사:

쓰기식 복사는 자식 프로세스도 부모 프로세스와 동일한 프레임을 가리킨다. 둘중 하나라도 쓰기 작업하면 별도의 공간으로 복제.