3. Process

[3] OS - Process

정의 = instance of a program in execution

프로세스란?

프로그램은 정적인 코드이다. 프로그램이 실행되면, ram 메모리에 올라가고 운영체제(kernel)가 이 실행 중인 상태를 관리하는데, 그걸 하나의 프로세스라고 부른다. Program이 컴파일되면 -> binary program이 되고, 이는 storage에 저장된다. UNIX 계열에서는 이를 a.out과 같은 형태로 저장한다. -> 이를 ram에 올리면, 내가 짠 프로그램을 CPU가 수행할 수 있는 상태가 되는데 이를 프로세스라고 한다. 그래서 program in execution이다. Program은 passive한 form이고 process는 active한 form이다. 이러한 Process가 엄청나게 많다. 심지어는 system call, interrupt이런 것도 사실은 OS code이기 때문에 OS code도 일종의 프로세스이다. CPU는 process를 번갈아가면서 수행한다. 와중에 프로세스가 어떤 경우는 system call, interrupt, kernel code, dual mode 이런 식으로 계속된 Mode switching이 일어나기도 한다.

프로세스가 포함하는 것

Images: 실체
- Code : machine instructions. 원시코드 형태이다.
- Data : variables. int a, b, c; void foo(int i, int j, int k);있으면 이런 함수내의 수많은 지역변수들 말고/Main, 함수 밖의 global한 것들만 담고 있다. 전역 변수나, static같은 정적 변수들을 담는다.
- Stack(LIFO) : states for function calls: 지역 변수, 매개 변수들
- Heap(FIFO) : dynamic memory : malloc, new 등으로 생성, 수동으로 해제해야 함
Process context: 숨겨짐
- Program context : data registers, program counter(현재 가리키는 index pointer), stack pointer
- Kernel context : pid(process id), gid(group id), sid(session id), environment, vm structures(paging tables), open files, signal handlers, 우선순위, parent, child 등

Process Layout

System_overview Stack:

automatic variables
temporary variables
return address
caller’s environment(registers)
long array[100];
long bufsize = 100;
int main(void) {
int i;
char* buf;
i=10;
buf=f1(i);
return(0);
}
char* f1(int n){
printf(“%d\n”,n);
return malloc(bufsize);
}
위와 같은 프로그램이 있다고 생각해보자. heap이 위로, stack이 아래로 가면 어디에선가 공간이 부족해지지 않을까?
Address 공간의 크기 : 아키텍쳐에 의해 결정된다. 예를 들어서 32bit CPU의 경우 maximum address의 주소는 2^32-1(4GB)이다. 4 GB면 Kernel이 1GB, User가 3GB가져가게 된다. 그런데 global, code는 메모리를 그렇게 많이 사용하지는 않기 때문에 stack, heap이 만나기는 어렵다.
그런데 내가 만약에 malloc을 쓰려고 하면, 표준 C라이브러리에 있는데 libc.a는 pre-compile되어있어서 괜찮았음. 과거에는 정적 라이브러리 형태로 배포되었는데, 컴파일할 때 이 안의 함수 코드중 유저 코드가 참조하는 함수만 libc.a(.o의 묶음)에서 .o파일로 뽑아서 코드 영역에 저장하였기 때문임. 만약에 요즘 libc(libc.so)나 math library를 쓰려고 한다면? 이런 library는 heap, stack 사이 어딘가에 할당됨. shared library이기 때문임.

2. PCB

essential kernel data structure로, PCB(process control block) 또는 PD(process descriptor)라고 부른다. process와 관련된 정보를 포함하고 있으며, 모든 프로세스에 존재한다. <h1 style="font-weight:bold">“Process Context”는 ‘프로세스를 어떻게 실행하고 멈췄다 다시 시작할 수 있게 하느냐’에 필요한 모든 정보</h1> -> 그리고 이걸 실제로 커널이 관리하기 위해 만든 구조체가 PCB
PCB의 요소들

Image
Process context 그래서 fork로 proces만들면 PCB로 process를 생성한다. kill하면 그냥 return 해주면 됨.
Linux Process Descriptor : PCB
Specific resources owned by a process
이는 task_struct로 구현됨. (include/linux/sched.h)
OS는 엄청나게 다양한 자료구조를 control한다.
- Table = 자료구조들의 배열
- Table은 OS가 관리하는 각각의 단위를 위해서 생긴 것이다.
- Table 종류 : Memory, IO, File, Process
  - Memory :
    - main memory를 process로 할당
    - secondary memory를 process로 할당
    - 보안 : shared memory region에 접근할 때
    - virtual memory를 위한 정보
  - IO
    - IO device 사용가능한지/할당되었는지
    - IO operation의 상태
    - IO transfer를 위해 source, destination으로 사용중인 main memory의 위치
  - File
    - 파일의 존재성
    - secondary memory의 위치
    - 현재 상태
    - 속성들
  - PCB
    - 프로세스의 위치
    - 속성들(Pid, Process State, location in memory)

3. Process State

Generic five-state model

new : 프로세스 생성, 즉 storage의 program을 RAM에 들고 와서 수행하겠다는 것. 이게 admit되면, process로 만들어 수행하겠다, 즉 Image가 생성됨. 이후 여러단계를 거치면 ready로 가는 것임.
ready : 프로세스가 processor에 할당되길 기다리는중
running : 명령어 수행중. time slice다 쓰면 timeout되어 ready
blocked(waiting) : 어떤이벤트(IO같은) 기다리는 중
exit(terminated) : 프로세스 종료
밑에는 굉장히 단순화된 구조이다. System_overview OS의 동작 방식: CPU비면 -> ready queue중 가장 우선순위가 높은(남은 시간이 짧다거나.. 우선순위를 정의한다거나) 걸 고름. 이를 Running->close되면 Ready queue중 그 다음거로 감.
1) 이를 통해 특정 프로세스의 독점을 막고, 1초씩 돌게 구현한다거나 하면 Timeout으로 Ready queue에서 고르게 됨.
2) Running하다가 IO call 해버리면(syscall) kernel mode로 진입하므로 커널의 syscall handler가 data읽어서 주는데 프로세스는 스탑하게 됨. Kernel code는 read를 위한 kernel service를 하게 되고, storage controller와 이야기하게됨.
3) 구조는 CPU, Memory bus, Disk controller, 너가 가진 파일 중에서 읽어서 주려고 함. 독립적인 실행을 하게 됨.
4) CPU는 이 프로세스만을 기다릴 수는 없음. 수행해야할 것들이 많게 때문임. 커널은 미션을 주고 ready queue에 들어가서 다른 프로세스를 실행하게 됨. CPU는 2번째 프로세스를 돌게 되고, IO operation도 수행되게 됨. 시간이 흘러서 Disk controller가 끝냈다는 걸 알려주면 이 때 Interrupt를 걸게 됨. 이제 CPU가 하는 것은, 모든 CPU cycle의 끝에 interrupt를 체크하는 것임. 이를 통해 Kernel이 interrupt를 인지하게 됨. 이러면 2번째 프로세스를 스탑하고 mode change-> interrupt handler를 위한 kernel code를 수행한다.
5) copy한 buffer의 내용은 ram으로 가서, P1이 다시 ready로 감. 그래서 다시 이를 정리하고 P2 수행함.
6) Kernel이 이후 이제 Ready queue를 바꾸게 된다. P1이 살아서 수행되어야 하는데, P2가 돌면…? 그냥.. P1, P2중 우선순위가 높은 게 실행됨.
밑에는 20년 전 초창기 UNIX의 process state diagram이다. System_overview OS가 하는 일은 PCB를 관리하는 것이다.
즉 다른 말로 하면 OS의 권한은 PCB를 바꾸는 것이다. control block을 queue형태로 바꾸는 것인데, OS kernel은 ready상태인 프로세스들을 특별관리한다.
block : 다양한 IO장치이다.
disk controller는 여러 writing job을 수행한다. 앞의거를 가지고오든, 뒤의 거를 가지고 오든, 프로세스는 block state에 있다. 요청한 read, write를 하기 위함이다.
CPU interrupt : disk에서 가리키고 있던 PCB를 ready queue의 tail에 다시 push 한다.
즉 커널의 일은 pointer를 변경하는 것이다. System_overview System은 여러개의 프로세스를 관리한다. IO마다 block queue를 유지할 수 있다. 예를 들어 Event 1 Queue는 Network일 수 있는 것이다.
컴퓨터 시스템은 마치 서버와 queue의 집단인 것이다.
1개의 CPU queue와 여러개의 IO queue를 그래프 형태로 나타내는 것과 비슷하다.
(**예를 들어서 생각해보면, server가 포아송 분포고 processor가 exponential 분포와 같은 형식이라고 생각해보자. n개가 들어왔을 때 걸리는 시간을 수학적으로 분석할 수 있다. 이게 바로 queueing theory(대기 이론)이다.)

4. Process Scheduling

1) Job scheduling : long term scheduling 여러 프로세스 중에서 어떤 프로세스가 시스템에 들어올지 잘 일어나지 않는다.
multiprogramming 의 선이고, 요즘은 잘 안일어남. 프로세스는 거의 바로 ready queue에 들어가기 때문
2) CPU scheduling :어떤 process가 CPU를 점유할지. 굉장히 자주 일어나며, 빨라야한다.
3) Medium term scheduling
지금 Job scheduling 상황이 안좋으면, 전반적인 system을 swap space해버림. process가 ready-queue에 있어도 그냥 거기로 보내버림. 이제 한가해지면 다시 들여옴

5. Process switching

정의 : 현재 running process가 interrupt되고, 운영체제가 다른 프로세스를 running state에 넣어버려서 그걸 관리하는 것.
안끝났는데도 다른 process가 CPU에서 수행됨. switching이 간단하지 않고 overhead가 심하다는 문제가 있음.
중요하게 볼 상황:
1) 어떤 게 process switch를 일으키는가? -> IO?
2) process switch와 mode switch의 차이는?
3) process switch를 위해 OS가 해야할 것은?
(1)Mode switch

user programs이 low-level hardware components와 directly interact하는 것, 또는 임의의 memory locations에 접근하는 것을 막음
대부분의 현대 운영체제는 최소 두개의 다른 실행모드를 가진다: user mode(less-privileged) and kernel mode(control of processor)
mode switching은 (1) externel interrupt(time, io interrupt) (2) internal trap(exception 등 : page fault, invalid operation …) (3) syscall(io operation : file open/fork 등)
- 참고로, 1만 유저와 무관하다.
- 타이머 구현 방법 : CPU밖에 PIC라는 주기적으로 interrupt를 주는 하드웨어가 있는데 1초에 1000번 interrupt해라고 하면 1ms에 1번 인터럽트 걸림. 1초 time slice면 1000번 interrupt
각 mode switch 이벤트마다:
- 현재 processor state(registers, flags 등)을 저장
- PC를 적절한 루틴의 주소에 넣음
- kernel mode로 switch할 때는 privilege instruction이 사용될 수 있음
- 이런 지금 내용을 저장할 때 필요한 게 바로 PCB: 다시 스케쥴 될 때 restore함.
process 수행 중에도 굉장히 많이 발생함.
IO, syscall 등에 발생
mode switch 중 특정 경우에 process switch가 될 수도 있긴 함. (2) Process switch
Process switch가 아닌 mode switch : 대부분의 운영체제에서 interrupt, exception, syscall은 process switch를 의미하지는 않음. interrupt handler 실행 후, 심지어 현재 프로세스가 다시 프로세스 running으로 선택될 수도 있음
mode switch는 process switch에 수반된다. 만약 현재 running process가 다른 state로 가면, extra work가 필요한데 이게 process switch. 모든 걸 다 save,scheduler call, restore시 overhead 엄청나게 큼.
단계(선행조건 : mode switch: kernel mode에서만 바꿀 수 있어서..) 1) program context 저장
2) 현재 프로세스의 state 변화(running->blocked/ready/exit)
3) 현재 PCB를 appropriate queue로 이동(blocked 인 경우)
4) 다른 프로세스 선택(process scheduling)
5) 선택된 프로세스의 PCB를 appropriate queue에서 꺼내옴
6) 선택된 process의 상태를 running으로 변경
7) 필수적인 memory-management structure 업데이트
8) 새롭게 선택된 프로그램 context를 restore
overhead엄청 큼 -> hardware support가 필요하다. switch overhead가 엄청나게 커서 multiprocessing OS는 이를 작게 유지하려고 엄청나게 노력한다.
Challenge: 어디에 user mode의 SP, PC, program context를 저장할 것인가? (3) Dual modes in linux/x86
CPU: user mode or kernel mode에서 돌아감
process가 system call 호출함 -> cpu가 exception signal -> interrupt signal to the cpu -> 커널 스레드 돌기 시작함

6. OS 구현

놀라운 건, OS도 프로그램이라는 것이다. 그렇다면, OS가 processor에 의해 실행되는 그냥 다른 프로그램이랑 똑같다면 어떻게 디자인해야할까? 두가지 방법론이 있다.
(1) Execution within User Process : 커널 코드가 user process안에 숨겨짐. 즉 운영체제 코드가 virtually linked to the program images. interrupt시(syscall, trap) CPU가 kernel 모드로 가서 user process의 context안에 있는 os routine을 실행한다.(이는 process switch가 아닌 mode switch이다.) 예시로는 Windows, Linux 와 같은 범용 운영체제의 표준
(2) Process-based Operating System : OS가 하나의 process
운영체제가 software고 프로세스는 이미지, context로 하나의 PCB라이다. 그리고 OS코드는 컴파일된 코드이다. 그렇다면 OS도 프로세스인것인가? Process면 어떻게 제어할 것이며, 아니라면 어디에 존재할 것인가?

Linux의 구현

System_overview 코드의 특정 위치 -> Load, decode stack local 변수같은 걸 저장하는 user, address space. image 부분임. 즉 Linux 운영체제는 Bottom 3GB를 User가 쓸 수 있게 해준다. 코드 도는 공간을 3GB, 나머지 1GB는 커널을 위해서 사용한다.
Process의 주인은 나(fork -> system 할당) : 그런데 kernel이 내 address공간을 사용한다 .밖에는 kernel이 안보이고, 모든 process에서 1GB씩 사용한다.
내가 Syscall을 해보고 싶다고 가정하자. code->shared library-> kernel mode read operation -> 벽을 넘어서 kernel로 진입->해당 syscall-> 다시 돌아옴. 이를 마치 <h1>아파트</h1>처럼 비유할 수 있다. 동일한 구조 여러층 있고, 한 아파트에 방 4개가 있다. 방 1개가 1GB, 나는 301호 주인이라고 하자(Pid = 301) 20층 모두다른 Id. 방 하나는 kernel이 쓰고, 모든 호에는 Kernel의 방이 있다. 그런데 kernel 방은 내용이 동일하다.
301호에서 방 4개중 kernel 방 들어갔다가 나옴 : Mode switch
내집에서 kernel 방 들어갔는데 timer끝나면 다른 층 process로 변경된다. 이는 process switch.
장점 : 빠른 mode switch(time interrupt : 1초 1000번, io interrupt)
단점 : kernel, user가 메모리 활용도가 낮아서 unhappy.

헷갈리는 부분

의문점1. kernel == OS인가?
맞다 - “A more common definition, and the one that we usually follow, is that the operating system is the one program running at all times on the computer—usually called the kernel” (공룡책 11th edition)
의문점 2. interrupt handler가 kernel의 일부인가?
Yes
의문점 3. 커널이 각 address space마다 하나씩 있으면 도대체 process switch는 어떻게 일어나는 것인가?
단계1. 트리거 - process1의 kernel 진입: Process1에서 syscall등으로 인해 kernel로 mode switch
단계2. kernel mode의 scheduler 호출 - time slice가 끝났거나 process1의 blocked 등
단계3. context switch : p1의 kernel address space의 코드 중 schedule() 커널 코드가 다른 프로세스를 다음 프로세스로 지정
linux에서는 context_switch() -> switch_to()에서 발생
- P1의 레지스터를 P1의 커널 스택에 push (여기까지는 P1의 스택 위에서)
- P1의 스택 포인터(rsp)를 P1의 task_struct에 저장 → “P1이 나중에 복귀하면 이 스택 위치부터 다시 시작”
- 메모리 맵 교체 (MMU 업데이트) : switch_to전에 switch_mm을 먼저한다. 주소 공간을 교체(CR3에 P2의 페이지 테이블 루트 쓰기)해도, 커널 영역은 P1과 P2의 주소 공간 모두에서 동일한 물리 메모리로 매핑되어있음
- P2의 커널 스택으로 전환 - 현재 스택 포인터를 P2의 커널 스택 주소로 변경(이순간 switch_to()의 실행 주체가 P2로 바뀜)
- P2의 커널 스택에서 저장된 레지스터를 pop → P2가 과거에 switch_to의 ①에서 저장했던 그 값들
- P2의 저장된 레지스터 상태를 CPU에 복원
의문점 4. 커널 주소 공간이 모두 같다면서 왜 스택은 따로인것인가?
가상 주소 공간 레이아웃은 같고, 그 안에 모든 프로세스의 스택이 다 들어있지만, 지금 이 순간 어떤 스택을 실제로 쓰고 있느냐만 프로세스마다 다르다.
의문점 5. 프로세스를 가리키는 방법은?
CR3 (Memory Pointer): 현재 프로세스의 페이지 디렉토리(지도) 위치를 가리킴. (주소 공간 결정)
PC/IP (Instruction Pointer): 현재 프로세스의 코드 중 어디를 읽고 있는지 가리킴.
SP (Stack Pointer): 현재 프로세스의 스택(데이터/로컬 변수) 위치를 가리킴.
이 레지스터들의 값이 특정 프로세스의 PCB에서 복사되어 들어온 순간, CPU는 그 프로세스를 “가리키며” 실행. 즉 현재 process를 가리키는 방법은 PC, SP, CR3이다.
의문점 6. 같은 커널 주소 공간을 갖는다면 PCB를 왜 따로 관리하는가?
PCB를 따로 관리한다 = 각 프로세스마다 별도의 PCB 인스턴스가 존재한다.
P1의 PCB: 물리 메모리 주소 0x10000000에 위치, 16KB 정도 차지, P1의 상태 정보 담음
P2의 PCB: 물리 메모리 주소 0x10010000에 위치, 별도의 16KB, P2의 상태 정보 담음
┌──────────────────────────────────────────┐ │ 가상 주소 0xFFFF888000000000 ~ │ │ … 커널 코드 … │ │ 0xFFFF888001000000: ┌────────┐ │ │ │ PCB1 │ │← P1의 PCB (여기에 위치) │ 0xFFFF888001002000: └────────┘ │ │ │ │ 0xFFFF888001004000: ┌────────┐ │ │ │ PCB2 │ │← P2의 PCB (여기에 위치) │0xFFFF888001006000: └────────┘ │ │ │ │ 0xFFFF888001008000: ┌────────┐ │ │ │ PCB3 │ │← P3의 PCB │ └────────┘ │ │ … │ └──────────────────────────────────────────┘ “같은 주소 공간 안” = 이 PCB들이 모두 공유된 커널 영역에 들어있다. P1의 주소 공간에서 보든 P2의 주소 공간에서 보든 PCB1은 0xFFFF888001000000에 있고, PCB2는 0xFFFF888001004000에 있다. “서로 다른 주소” = PCB1과 PCB2가 같은 번지에 겹쳐 있지 않다. 각각 다른 번지를 차지

Process-based operating system

대안 : 별개 process라고 가정하면 memory 관점에서는 happy하지만 (예시 : 1301호를 kernel에게 줘버림) 너무 빈번한 Mode switch, process간 switch. 특히 process switch 도중 process를 어디에 저장할 것인가?
특히 기존 거를 멈추고 kernel 거 수행하면 overhead가 너무 많다. efficiency issue.
운영체제는 효율적이어야 하는데 throughput을 극대화하려면?
user가 주가 되고, kernel code, data를 user process 영역 밖에서 도는 편이 낫다.

7. Process 생성

단계

unique pid 할당
메모리 할당(이미지, PCB)
PCB init
appropriate queue에 있게 하는 link 할당
memory, file, accounting등 할당

application level process 생성

process 게층 : parent process가 children process 생성

root process: ancestor of all system/user process
init on boot address space : 자녀가 parent를 복사한다.
실행 : 동시에 실행하며 자녀가 끝날때까지 부모는 기다린다.
자원 공유: 모든 자원을 공유한다.
예시 : init다음으로 만드는 프로세스가 shell임.
cat fileA: 이 명령어를 친 후 엔터 치면 shell이 프로세스를 복제하여 child process를 만든다. 이 실체를 cat 코드로 바꾸는게 shell의 엔터라는 뜻으로, 프로세스를 만든다는 의미이다. 만들어진 cat process가 끝날 때까지 shell은 기다린다. shell이 cat끝나야 다음 프롬프트를 준다. cat fileA & ()이면 parent, shell이 동시에 돈다.

System call 설명

fork()
UNIX에서 유일하게 새로운 프로세스를 만들 수 있는 방식이다.
호출한 프로그램와 동일한 복사본을 형성하고, child process라고 부른다. caller는 Parent이다.
다른것: pid, kernel stack pointer, stackpointer
같은것: 위의 것들을 제외하고 모든 내용은 동일하다(text, data, heap, stack. 그렇지만 address space는 다르다)
return value : 부모는 성공하면 child의 Pid, 실패하면 -1을 받고 child는 0을 받는다.
무한히 많이 생성할 수는 없고, limit이 있다.
fork()는 P1의 PCB를 복제해서 P2의 PCB를 만들지만, 곧바로 P2의 고유 필드들(PID, 부모 포인터, 커널 스택 포인터, mm 포인터 등)을 새 값으로 덮어쓴다. 따라서 P1과 P2의 PCB는 별개의 객체이고, 핵심 필드들의 값도 다름. 내용이 “복제됐다”는 것과 “같다”는 것은 다른 얘기이다.
System_overview

exec()
- 새로운 프로그램의 실행을 시작하게 해준다.
- exec를 호출한 프로세스는 완벽하게 새 프로그램으로 바뀐다. (text, data, heap, stack)
- 종류는 6개: execl, execv, execle, execve, execlp, execvp이지만, execve만 kernel 내의 systemcall이다.
- UNIX에서 프로그램을 만드는 것: fork() + exec()
exit()
- 정상적인 종료일 때 사용된다.
- cleanup processing을 수행하며, 커널로 돌아온다. 그리고 모든 표준 io stream을 닫는다.
- 별로 쓸일이 없다. main bracket 끝나면 자동 수행된다.
- _exit(): exit과 동일하지만, cleanup이 없으며 바로 커널로 돌아온다.
wait()
- child termination까지 parent가 기다리는 것을 뜻한다.
- process가 종료되면, kernel은 Parent에게 SIGCHLD 신호를 보낸다.
- wait()call한 process는 block하거나 child의 termination process를 가지고 return 할 수 있다.
Process간 협업 1개가 아니라 다른 프로세스와 메모리 등을 공유하기를 원하는 중
- Communication : Data exchange
- Synchronization : activity간 ordering
- Proces coordination(communication, synchronization)은 application programming(shared memory)나 os에 의해 제공되는 IPC(inter-process communication)에 의해 제공된다.
- 어쩌면 병렬성 극대화로 더 효율적일 수도 있다.
- application에 의한 process coordination
  - producer-consumer problem

IPC

뜻: 프로세스간에 소통하고 동기화하는 메커니즘
Types:

Basic IPC: pipes, FIFO
Advanced IPC: message passing, semaphore, shared memory, socket
위에는 pipe IPC이고, fork후 parent, child가 데이터를 주고받는다 fifo는 named pipe로, parent, children간에만 생성되고 process 종료 시 삭제되는 영구적이지 않은 Pipe의 단점 두가지를 보완하여 만들었다. 상관이 없는 프로세스도 exchange가능
그렇지만 위의 두 방법을 개선한 System V IPC가 있다.
1. Message passing: send, receive가능하다
2. shared memory: 특정 메모리 segmetn에 있는 데이터 공유
3. semaphore: synchronization, 큰 전송에는 적합하지 않음

Client-Sever IPC

이는 두 프로그램이 어떤 종류의 통신이든 가능하게 하려고 만들었다.
클라이언트:

서버와의 연결을 만들고, 요청을 진행한다.
web에서는 브라우저에 구현된다. 이메일같은 것 상상하면 된다.
서버:
클라이언트가 요청한 것을 제공한다.
webserver가 웹페이지를 제공하는 것, 이메일에서는 메일 서버이다.
이들은 BSD socket interface를 사용한다. 서버, 클라이언트는 socket API로 메세지를 주고받는다. 소켓은 TCP(connection-oriented(IP, portnum알아야함), reliable, in-order, 여러대의 서버. child server가 1-1로 클라이언트와 대응, )와 UDP(connectionless, unreliable, 서버한개가 여러개의 클라이언트와 대응)를 사용한다.