Process Concept

Process

• 실행중인 프로그램
• 실체는 프로그램을 실행하기 위해 필요한 모든 정보를 담고있는 자료구조
• 분기나 jump가 없는 이상 sequential하게 수행된다

A process includes

• text section: 프로그램 코드
• stack: function call 할때 파라미터, 끝이 날때 돌아올 return address, 함수내 local variable 등 function call과 관련된 데이터 저장
  • function call이 중첩된 경우 return address를 stack top에서 pop해서 가져오면되서 간편하다
  • local stack top의 offset으로 local 변수를 찾을 수 있다
• data section: static and global 데이터 관리
• heap section: 동적 할당한 데이터 관리
  • point 변수는 stack에 있다. 즉 stack에서 heap section 영역을 가르킨다
• pc and registers value: multiprogramming을 위한 상태 저장

Process in Memory: Address Space

• 0~max까지 logical하게 연속된 공간을 process 주소 공간이라고 한다
  • 사용자는 logical == virtual address만 안다
  • OS만 physical adress를 볼 수 있다
• Virtual memory로 address space의 필요한 부분만 실행한다
• Memory management에서 physical memory 실제 위치를 정한다
• text와 data 영역은 고정 크기
• heap은 동적 할당과 해제가 발생해서 가변적이다
• stack 역시 function call과 return에 따라 늘었다 줄었다해서 가변적이다
• 가변적인 heap과 stack을 양쪽에 배치하여 크기가 변해도 문제가 안된다
  • max가 크기 때문에 만나지 않는다

Process State

process는 실행되는 과정 속에서 state를 바꾼다

• new: 막 만들어져 memory에 탑재됨. 아직 cpu scheduling 대상에 편입되지는 못함
  • 왜 cpu를 받고 실행하지 않을까? 실시간 시스템
    • 실시간 시스템에서는 각 작업의 deadline이 보장 되어야 한다. 새로운 process가 추가 되려면 자원을 할당해야한다. 만약 cpu를 이 process에 할당하게 되면 기존의 나머지 process들이 deadline를 만족시키지 못할 수도 있다. 따라서 새로운 process로 인해 다른 process들이 deadline을 만족시키지 못하는지에 대해 확인하는 과정을 new 상태에서 한다.
    • 일반적인 OS에서는 바로 cpu 할당함
• running: 현재 process가 cpu를 잡고 일을 하고 있는 상태
  • cpu core가 하나라면 running 중인 process는 한개다
• waiting: process가 event를 기다리는중
  • ex) IO가 끝나기를 기다리고 있어 cpu를 잡으면 안되는 상태
  • interrupt가 오면 waiting 상태를 벗어남
• ready: process가 일 할 준비가 됐지만 cpu 할당을 받지 못해 기다리고 있는 상태
• terminate: 마지막 instruction 실행하여 cpu 할당을 받지 않아도 되는 상태

Diagram of Process State

new → admission control admitted → ready → cpu allocated → cpu schedular dispatch → running → 3가지 경우

마지막 명령어 수행

last instruction → exit → terminated

I/O event 발생

I/O or event wait → waiting → interrupt → ready → ,,,

할당된 시간 끝

end of time sharing for multitasking → interrupt → ready

• process에 할당된 시간이 종료됐다는 사실을 timer device가 interrupt를 보낸다
• cpu schedular는 timer interrupt가 왔으니까 process를 ready 상태로 전환한다

Process Control Block (PCB)

• PCB는 OS가 process를 표현한 자료구조다
• 운영체제마다 PCB 가 만들어지는 과정이 다르다
• Linux에서 tast_struct 구조체로 선언한다

PCB 구성

• process state
• program counter
• cpu registers
• cpu scheduling information ex) priority
• memory management information ex) 메모리 영역, stack 정보 등
• accounting information ex) process 경과 시간, 메모리 사용량 등
• IO status information ex) 어떤 IO를 요청한 상태, open한 파일

CPU Switch from Process to Process

• 멀티 프로그래밍에서 cpu를 잡고있는 process의 상태를 저장하고 다른 process를 실행하는 작업을 cpu switch라고 한다
• Interrupt 혹은 system call 호출시 CPU switch가 발생한다
• 현재 process 상태 정보를 PCB에 저장해야 한다

P0가 switch 대상이됨 → PCB0에 현재 상태 정보 저장 → process P1을 실행하기로 결정 → PCB1 상태 정보를 읽어와 register에 탑재 →process P1이 switch 대상이됨 → PCB1에 현재 상태 정보 저장 → process P0를 실행하기로 결정 → PCB0 상태 정보를 읽어와 register에 탑재 → ,,,,

Process Scheduling Queues

• 동시에 여러개의 process들이 돌고있다 ex) cpu를 기다리는 process는 여러개다
• 같은 상태인 process들은 queue에 보관하고 하나씩 뽑아서 작업을 수행한다
• 상태가 변할 때 현재 상태 queue에서 다음 상태 queue로 옮긴다

Job Queue

• 모든 process들이 모여있다
• PCB 포인터를 가지고 있다

Ready Queue

• Cpu를 기다리는 process들이 모여있다
• Cpu를 잡으면 running 상태가 되며 ready queue에서 빠져나온다
• running 상태에서 IO를 발생하면 device queue로 이동한다

Device Queue

• IO interrupt를 기다리고 있는 process들이 모여있다
• wait 상태이며 interrupt가 발생하면 ready queue로 이동한다

Schedulers

Long term scheduler (job scheduler)

• ready queue로 편입시킬 대상을 결정
• new → ready 상태로 만든다
• 빈번하게 일어나지 않는다 seconds, minutes ex) 더블 클릭하여 실행했을 때 기존의 process 하나가 빠지면 집어넣는 형태
• long term scheduler가 새로운 process를 ready queue에 넣는 행위는 현재 process 갯수가 1 증가시킨다 == controls the degree of multiprogramming
  • process가 빠져 나가는 것은 os가 관여하지 않는다 ex) 명령어를 다 실행했기때문
  • 새로운 proccess는 os가 관여한다 (long term scheduler)
  • degree of multiprogramming == 현재 cpu를 통해 일을 하고있는 모든 process 갯수 == cpu scheduler의 대상이 되는 process 갯수

Short term scheduler (cpu scheduler)

• ready 상태인 process들 중 cpu 배정 대상 결정
• 매우 자주 일어남 milliseconds ex) 매우 짧은 time quantum이 지날 때 마다 동작한다

Medium term scheduling

멀티 프로그래밍을 하다보면 메모리를 확보해야하는데 부족할 수 있다. 그렇다면 메모리를 차지하고 있는 여러개의 process중 하나를 골라서 disk로 swap out 시켜서 공간을 마련한다.

process in ready queue swap out → 다시 필요해지면 swap into ready queue

process swap out 대상: ctrl z s suspended process

Scheduling Efficiency

Cpu 사용 시간과 빈도가 scheduling시 고려되어야 한다

IO bound process

• 에디터 ex) ppt, hwp
• 짧은 Cpu 사용이 빈번하게 일어남

Cpu bound process

• 한번 시작하면 입력하지 않아도 계속 계산하는 process
• Cpu를 길게 사용하지만 횟수는 적음

Context Switch == CPU Switch

멀티프로그래밍을 하기위해서 process간 전환이 이뤄진다. 이때 현재 상태 혹은 문맥을 PCB에 저장하고 새로운 문맥을 PCB로 가져와야 한다. 이 전환 과정에서 필수적으로 overhead 시간이 생긴다.

• context switch overhead 동안에는 유의미한 일을 못한다
• overhead를 줄이기 위해서는 hardward 지원에 의존한다

Cache Miss Overhead

• cache에는 현재 수행중인 process에서 최근에 접근한 데이터가 저장된다
• context switching이 발생하면 새로운 process에서 데이터를 접근하기 때문에 cache miss가 발생하며cache가 비워야진다 == cache flushing
• 즉 context switching이 일어나면 초반에 cache miss가 계속 발생하고 overhead가 크다
• Context switch overhead + Cache miss overhead 발생!

hyper threading?

Process Creation

• child process를 create하는 주체는 parent process다
  • terminal 더블 클릭하면 GUI process (parent)가 fork하여 terminal process를 만든다
  • terminal process는 shell process를 만들고 shell process는 입력 command에 대한 process를 만든다
• 하나의 root process에서 시작하여 tree 형태로 만들어진다
• process는 pid로 구분한다

Resource Sharing

• 내용적으로 밀접한 관계를 가진 경우 parent와 child process는 자원을 공유할 수 있다
  • 웹 서버인 경우 실행 위치 == program counter만 다른 경우가 있다
• 내용적으로 완전히 다른 경우 자원을 공유하지 않는다

Execution

• parent와 child process는 동시에 실행된다
• parent는 child process의 return 값을 받는다 == child가 terminate할 때까지 기다린다

Address space

• 먼저 child는 parent process의 address space를 복제한다 (fork)
• parent와 관련없는 child라면 address space를 새롭게 채운다 (exec)

Starting point of child process

• fork가 되면 parent를 copy한다 = = parent의 pc, register, memory info 등과 똑같다

• fork 리턴값으로 parent는 child pid를 받고 child는 0값을 받는다

• pid = fork() : parent와 child 모두 return value를 기다리는 상태로 fork됐다

• 나머지 코드는 똑같지만 pid 값이 달라 parent와 child를 구분할 수 있다

• execlp() : child process의 text, data section에 ls 프로그램으로 갈아끼워 parent와 완전히 분리된다

• wait(NULL) : parent는 child가 끝날때까지 기다린다

Single and Multithreaded Processes

• address space를 따로 가지지않는다

• web server에서 parent와 child는 실행하는 위치만 똑같음 == data와 text section + files 동일

• process는 여러 copy를 만들기 위해 비효율적 == fork X

• register와 stack만 다르게 가진다

• memory 낭비 해결! 하지만 공용 data때문에 동기화 문제 발생!

Kernel Level Thread

• OS가 thread 하나씩 관리