[OS] Schedulers

Process Scheduler Queues

• Job Queue => 시스템에서의 모든 프로세스들의 집합(아마 디스크나 메인메모리에 위치)
• Ready Queue => 메인메모리에 위치하고 실행을 기다리는 모든 프로세스의 집합(관례적으로 Queue라고 표현하지만 실제론 pool에 가까움)
• Device Queue => 입출력장치를 위해 기다리는 프로세스들의 집합

프로세스들은 여러 큐들 사이를 이동한다.

ready Queue에서 cpu로 이동해 running을 하다가도
입출력 요청, time slice expired, 자식 프로세스 생성, 인터럽트 발생 같은
상황들로 waiting하게 되면 다시 ready Queue로 이동한다.

Schedulers

- Long-term scheduler (or job scheduler)

ready Queue에서 무슨 프로세스를 고를지 선택함
+) 간단하게 job queue에서 ready queue로 보내는게 job scheduler다.
매우 빈번치 않게 촉발됨 => 느림

- Short-term scheduler (or CPU scheduler)

다음에 실행되어야 하는 프로세스를 선택하고 CPU를 할당함
+) 매우 빈번하게 촉발됨 (밀리세컨초마다) 그래서 빨라야함

- medium term scheduler

메모리로부터 프로세스를 삭제하여 멀티프로그래밍의 정도는 감소시키는 것이 때때로 장점을 가질 수 있다.
그럼 우린 왜 멀티프로그래밍의 정도를 조절해야 할까?
=> 이유는 Thrashing 때문이다.
그게 뭐냐?
클릭->여기 잘 설명되어 있음

I/O bound process vs CPU bound process

• I/O bound process는 계산보다 IO를 더 많이하는 경우의 프로세스이다. 아무래도 CPU burst가 많이 짧다.
• CPU bound process는 계산을 IO보다 많이 하는 경우의 프로세스이다. 저 많은 CPU burst가 존재한다.
  => 이 둘중에 무엇을 먼저 스케줄에 넣을지는 설계자 마음이다.

in Linux...
IO bound를 먼저한다. 보통 IO bound process가 보통 짧기 때문
그리고 두 타입을 적절히 배합해서 더 나은 이용성을 가지게 한다.

Context Switch

시스템은 cpu가 다른 프로세스로 작업을 전환할때 이전의 프로세스의 상태를 저장하고 새로운 프로세스의 저장된 상태를 불러옴. 이것이 문맥교환(Context Switch)

• System context => 커널에 의해 할당된 자료구조 (PCB, page/segment table ...)
• Hardware context => Program counter나 stack pointer의 레지스터 정보
• Memory context => 메모리 공간, 실행파일 이미지

+)문맥교환 동안에는 일을 할 수가 없기에 잦아지면 오버헤드가 커짐
+)문맥교환 사건보다 time slice를 실행하는게 더 오래걸림

Process Creation

부모 프로세스는 자식 프로세스들을 생성한다. 다른 프로세스를 생성하면 트리구조로 생성한다.

• 프로세스 계층에서의 자원공유
  - 부모와 자식은 거의 모든 자원을 공유함(UNIX)
  • 자식은 부모의 자원의 부분집합을 공유
  • 자원공유 x
• 실행
  - 동시에 실행
  • 부모는 자식이 종료 될때까지 기다림(UNIX)
• 주소 공간
  - 자식 프로세스는 부모의 주소를 복사한다.
  • 자식의 프로그램은 복사된 주소에서 실행된다.
• UNIX 예시들
  - fork는 새로운 프로세스를 생성
  - exec는 fork후에 새 프로그램을 메모리공간에 넣어 사용함
  
  ls-> child
  exec()
  child->parent
  fork()
  라는 필기가 있길래 이해가 안되어서 검색해보니
  뤼튼:
  여기서 언급된 용어들은 주로 운영체제와 프로그래밍에서 사용되는 개념들입니다. 각각의 용어를 설명하겠습니다.

ls: 이는 유닉스 및 유닉스 계열 운영체제에서 파일 목록을 보여주는 명령어입니다. ls -> child라는 표현은 ls 명령어를 실행하는 새로운 자식 프로세스를 생성한다는 의미로 해석될 수 있습니다.

exec(): exec() 함수는 호출하는 프로세스를 새로운 프로그램으로 대체하는 시스템 호출입니다. 즉, 현재 실행 중인 프로세스의 실행 코드를 새로운 프로그램의 코드로 대체하며, 이 새로운 프로그램은 exec()를 호출한 프로세스의 프로세스 ID(PID)를 유지합니다.

child -> parent: 이 표현은 자식 프로세스가 부모 프로세스로 정보를 전달한다는 의미로 해석될 수 있습니다. 프로세스 간 통신(IPC) 메커니즘을 통해 이루어질 수 있습니다.

fork(): fork() 함수는 현재 실행 중인 프로세스의 복사본을 생성하는 시스템 호출입니다. 이 함수를 호출하면 부모 프로세스는 자식 프로세스를 생성하게 되며, 두 프로세스는 코드와 데이터 공간을 공유합니다. fork() 호출 후, 부모 프로세스와 자식 프로세스는 실행을 계속합니다.

요약하자면, 여기서 설명된 내용은 프로세스 생성과 프로그램 실행, 그리고 프로세스 간 통신에 대한 개념을 포함하고 있습니다. ls 명령어를 실행하는 자식 프로세스를 생성하고(ls -> child), exec()를 통해 프로세스 내에서 다른 프로그램을 실행하며, 자식이 부모 프로세스로 정보를 전달(child -> parent)하고, fork()를 통해 새로운 자식 프로세스를 생성하는 과정을 나타냅니다.
이라고 한다.

UNIX Process Creation

kernel system calls(for process management)

• fork()
  프로세스의 수를 늘리는 한가지의 방법
  스스로의 카피를 만들어냄 (이론적으로 부모의 복사본)
  모든 환경은 상속적이다.
  fork로 카피를 하더라도 잠겨있는 것은 카피하지 않음 메모리도 공유치 아니함
  그 외에는 PID 제외하고 전부 같음 (스케줄러를 위한 타이머정보도 자식에선 초기화됨)
  메모리를 공유하지 않음. 고유의 메모리공간을 가짐
  공유는 안하지만 ! 복사는 한다는 점!
  => 복사를 해서 고유의 공간에 할당해놓음
  그러나 파일디스크립터는 같은 파일을 가르킴
  +) 몇몇 시스템에서 vfork를 사용하는데 메모리공간을 카피하는것을 제외하고는 fork랑 같다. 그렇기에 성능적 이득이 있음. 또한 exec()가 실행되는걸 전제로함

• exec()
  파일을 디스크로 부터 가져온다.
  오래된 실행파일 이미지에 덮어씌운다.
  시작 지점으로 점프한다.
  exec가 호출하는 프로세스만 메모리에 남게됨
  

• wait()
  고아프로세스가 생기는 것을 방지하기 위해 자식프로세스가 종료될 때까지 기다렸다가 다음 문장을 실행한다. 자식이 끝나면 부모를 깨움
  커널이 부모를 ready queue에 넣어버림
  부모는 후에 dispatch된다.

fork와 exec 비교

• fork는 같은 프로세서만 만들 수 있지만 exec는 다른 프로세스도 만들 수 있다.
• forking process는 포크를 통해 끝나지 않지만 execing process는 exec로 끝난다.
• UNIX에서 fork와 exec를 결합하여 프로세스 종료 없이 다른 프로세스를 생성할 수 있다.

Process Termination

• 프로세스는 마지막 상태에 도달하고 OS에 삭제해달라는 요청(exit)을 하는 것이 보통 종료이다.

• 부모는 자식프로세스들의 실행을 종료(abort)시킬 수 있다.

• 부모가 종료되면 그의 자식도 모두 종료됨

• 자식은 running인데 부모가 갑자기 종료되면 좀비상태가 된다.

  	+) 좀비 프로세스
  	메모리 문맥은 이미 할당을 반환했고 프로세스는 단지 process table 명단에만 	존재한다.

  wait() 시스템 호출을 통해 종료 상태를 읽고 나면 좀비의 항목이 프로세스 테이 블에서 제거됩니다
  - init process (PID 1)
  좀비 또는 고아 프로세스의 반환 코드를 처리합니다

Cooperating Processes

• Independent process => 다른 프로세스 실행에 간섭 불가
• Cooperating process => 다른 프로세스 실행에 영향을 줌

장점

• 정보 공유
• 연산 속도 증가
• 모듈성의 철학 반영가능
• 편리함

Producer-Consumer Problem

생산자 소비자 문제
=> 생산자 프로세스가 정보를 생산하면 그것을 소비자 프로세스가 소비한다.
- threaded 프로그램의 유명한 예시

=> 버퍼 사이즈에 근거한다.
- 선형 구조일 경우엔 계속 사용하다보면 overflow발생
- Ring 원형 큐 구조로 생상하고 소비하고 생산하고 소비함으로써
소비자가 생산자 뒤를 따라가며 해결

IPC

프로세스들이 상호작용하거나 그들의 동작을 동기화하는 메커니즘
메시지 시스템을 통해서 프로세스들은 서로가 변수를 공유하는 것 없이
상호작용이 가능함
- send
- receive
이름이 지어지는 순간 링크는 자동으로 생기는데 단방향일 수도 있지만 보통 양방향임

Synchronization

Blocking VS Non - Blocking

제어권을 바로 돌려주느냐 마느냐 차이
Blocking은 제어권을 들고가서 원래 프로세스는 기다리고 있다. => sync랑 잘맞음
Non blocking은 바로 돌려주고 자신의 작업이 완료되면 그걸 또 리턴해줌 => async랑 잘맞음

Synchronous / Asynchronous는 호출되는 함수의 작업 완료 여부를 누가 신경 쓰냐 가 관심사
- 호출되는 함수의 작업 완료를 호출한 함수가 확인하면 Synchronous (동기)
- 호출되는 함수의 작업 완료를 호출된 함수가 확인하면 Asynchronous (비동기)
출처:(잘설명되어있음)

• & 버퍼가 존재하면 무조건 blocking에 동기

Buffering

링크에 연결된 메시지 큐 세 가지 방법 중 하나로 구현됨
1. 용량 없음 – 메시지 보관할 곳이 없음
보낸 사람은 수신자를 기다려야 함(랑데부)
2. 제한된 용량 – n개 메시지의 유한한 길이 링크가 가득 찬 경우 보낸 사람이
기다려야 함
3. 무한한 용량 – 보낸 사람이 기다리지 않음