공부하는 개발 블로그

5.1 프로세스의 개념

★ 프로세스 : 수행중인 프로그램. 디스크에 실행 파일로 존재하던 프로그램이 메모리에 올라가서 수행되는 것

◆ 문맥(context): 프로세스의 주소공간(코드, 데이터, 스택 상태)를 비롯해 레지스터에 어떤 값을 가지고 있었는지, 시스템 콜 등을 통해 커널에서 수행한 일의 상태, 그 프로세스에 관해 커널이 관리하고 있는 각종 정보(PCB)

1) 하드웨어 문맥 :  CPU의 수행상태. 프로그램 카운터, 레지스터값.

2) 프로세스의 주소 공간코드, 데이터, 스택으로 구성되는 자신만의 주소 공간

3) 커널 상의 문맥 : 운영체제가 프로세스를 관리하기 위한 자료구조 (PCB, 커널 스택)





5.2 프로세스의 상태

1) 실행(running): 프로세스가 CPU를 보유하고 기계어 명령을 실행하는 상태.  CPU는 하나이므로 여러 프로세스가 동시에 실행된다고 해도 실제 실행 상태의 프로세스는 유일

2) 준비(ready): CPU만 보유하면 당장 명령을 실행할 수 있지만 CPU를 할당 받지 못한 상태.

3) 봉쇄(blocked, wait, sleep): CPU를 할당 받아도 명령을 실행할 수 없는 상태.

이외의 일시적 상태

시작(new) : 자료 구조는 생성되었지만 메모리 획득을 승인받지 못한 상태

완료(terminated): 프로세스가 종료되었으나 프로세스와 관련된 자료구조를 완전히 정리하지 못한 상태



◆ 문맥 교환(context switch): 수행중이던 프로세스의 문맥을 저장하고 새로운 프로세스의 문맥을 세팅하는 과정.

CPU  디스패치: 준비 상태의 프로세스들 중에서 CPU를 할당 받을 프로세스를 선택하고 실제로 CPU의 제어권을 넘겨 받는 과정



★

5.3 프로세스 제어 블록(PCB)

운영체제가 시스템 내의 프로세스들을 관리하기 위해 프로세스당 유지하는 정보들을 담는 커널 내의 자료구조

구성 요소:

- 프로세스의 상태

- program counter(CPU 수행 관련 하드웨어 값)

- CPU 레지스터(CPU 수행 관련 하드웨어 값)

- CPU 스케줄링 정보

- 메모리 관리 정보(code, data, stack의 위치 정보)

- 자원 사용 정보

-입출력 상태정보



★

5.4 문맥 교환

하나의 사용자 프로세스로부터 다른 사용자 프로세스로 CPU의 제어권이 이양되는 과정.

원래  CPU를 보유하던 프로세스는 context를 자신의 PCB에 저장. 새롭게 CPU를 할당 받을 프로세스는 자신의 context를 하드웨엉로 복원.

시스템 콜이나 인터럽트로 커널 모드로 넘어가는 것은 해당 X. 이 경우에도 문맥의 일부를 PCB에 저장하긴 하나 다른 사용자 프로세스로 변환되는 것이 아니기 때문.

문맥 교환에 소요되는 시간은 오버헤드로 작용. -> 따라서, 시분할 시스템에서 타이머의 CPU 할당 시간을 적절히 조절하는 것이 중요. 너무 짧으면, 문맥 교환 오버헤드가 큼. 너무 길면, 시분할의 의미가 퇴색



5.5 프로세스 스케줄링을 위한 큐

1) 작업 큐(job queue): 시스템 내의 모든 프로세스를 관리하기 위한 큐. 프로세스의 상태와 무관하게 모든 프로세스가 속함. 작업 큐에 있다고 메모리 할당 받은 것은 아님

2) 준비 큐: CPU를 할당 대기.

3) 장치 큐: 장치마다 서비스를 대기하는 큐. 자원마다 존재. 여기에 속한 프로세스는 봉쇄상태.

큐는 프로세스의 PCB를 연결리스트로 연결한 형태

큐헤더 - 큐의 가장 앞 부분



5.6 스케줄러

어떤 프로세스에게 자원을 할당할지 결정하는 운영체제 커널의 모듈

1) 장기 스케줄러(=작업 스케줄러. job scheduler) : 어떤 프로세스를 준비 큐에 삽입할지 결정 - 프로세스의 메모리 할당하는 문제에 관여. 시작 상태의 프로세스 중 어떤 프로세스를 준비큐에 넣을지 결정. 속도가 느려도 됨. 메모리에 동시에 올라가는 프로세스의 수 조절.(시작 상태의 프로세스에 메모리를 할당할지 결정하므로) 하지만, 현대의 시분할 시스템은 장기 스케줄러 사용 안함. 바로 준비 큐에 넣음.

2) 단기 스케줄러(=CPU 스케줄러) : 준비 상태의 프로세스 중 어떤 프로세스를 다음 번에 실행 상태로 만들 것인가 결정.== 준비 큐의 프로세스 중 어떤 프로세스에게 CPU를 할당할 것인가. 시분할 시스템에서 타이머 이터럽트시 단기 스케줄러 호출,. 빈번하게 호출되므로 빨라야함.

3) 중기 스케줄러: 현대의 시분할 시스템에서 이용. 너무 많은 프로세스가 메모리에 적재되어 CPU 수행에 당장 필요한 프로세스의 주소 공간도 올려두기 어려울 때, 메모리에 있는 프로세스 중 일부를 통째로 디스크에 저장.(스왑 아웃: swap out). 0순위: 봉쇄 상태의 프로렛 -> 준비큐로 이동하는 프로세스

프로세스의 상태 : 중지 상태(suspended) - 외부적인 이유로 프로세스가 정지된 상태(중지 준비 상태. 중지 봉쇄상태)

5.7 프로세스의 생성
자식 프로세스는 부모 프로세스의 주소공간을 복사하여 시작
unix의 fork()
pid 제외하고 모든 것이 똑같음. fork()시 원본은 양수, 복사본은 0 return
프로세스 종료 :
1) 자발적 종료 - exit() 시스템 콜
2) 비자발적 종료 -자식의 프로세스를 부모가 강제 종료 : abort()
자원의 한계치를 넘는 자원 요구/ 더 이상 작업이 필요 없는 경우 / 부모 프로세스의 종료

5.8 프로세스 간의 협력
원칙적으로 다른 프로세스의 메모리 공간 참조 불가.

IPC(Inter-process comunication): 하나의 컴퓨터 안에서 실행 중인 서로 다른 프로세스 간의 통신
1) 메시지 전달(message passing): 공유 변수 X.
commnication link 생성 -> 커널에 시스템 골 방식을 send, receive  요청.
comunication link.는 자동 생성. 하나의 프로세스에게는 - 하나의 링크만 존재.
간접통신: 메일박스/포트로부터 전달받음. 여러 프로세스가 메일박스르 공유하는 경우, 어느 프로세스가 받는가?(P1, P2, P3가 공유할 때 P1이 보냄. 수신자는 P2? p3?)
-> 해결책: 둘만 사용하는 링크 만들기/임의로 수신자 지정 / receive를 각 시점에서 한 프로세스만 가능하도록

2) 공유 메모리
시스템 콜을 통해 본인의 주소 공간 일부 공유
동일한 물리적 메모리에 매핑/

2) 공유 메모리(shared memory) : 공유 변수 O.

1. 완전탐색 방법을 생각한다

2. 전체 답이 아니라 앞으로 남은 부분문제에 대한 답을 반환하도록 수정한다.

3. 이전에 구한 답에서 필요한 정보만 남긴다. 입력을 최대한 줄여서 중복을 늘린다.(메모이제이션을 적용했을 때 효율 증가)

4. 메모이제이션

구조

1) 초기화

2) 기저 사례 처리

3) 이미 처리한 값인지 확인(초깃값인지 확인)

4) 계산

시간 복잡도 : 부분 문제의 수 * 부분 문제를 처리하는데 걸리는 시간

메모이제이션을 위해서는 *참조적 투명성* 필요.

함수의 입력값에만 의해서 값이 결정됨.

전역 변수 등의 영향을 받지 않음

비둘기 집의 원리

- 경로는 무수히 많을 수 있지만, 입력의 수는 경로보다 적은 경우, 메모이제이션이 유용할 수 있음

배열의 크기를 하나 더 키워서

첫번째 인덱스를 -1이나 0을 넣어서 예외상황/초깃값 처리를 쉽게 할 수 있다.

관련 문제 : 가장 긴 부분 증가 수열(구종만 p.234 nlog n 해법 다시 공부하기)

quad tree

p.244 quantization 
배열 A를 s개의 숫자로 양자화 
-> 오차의 합을 최소로할 때, 오차합 구하기 

1) 배열을 s개의 집합으로 나누고 
2) 각 집합에서 적정한 숫자를 찾아, 오차합 구하기 

1) s개의 집합을 구하기 : 부분 문제 
2) 적정한 숫자 : 평균, 오차합: 부분합 이용 


p.256 우물을 기어오르는 달팽이 

문제를 분할 할때: 
1) 모든 경우를 포함한다 
1) 두 경우에 동시에 포함되는 경우는 없다.

완전 탐색

기저 사례 작성 -> 반복 제거

dx, dy를 별도의 변수로 분리하자

중복 제거 : 순서를 강제하기