process / thread / cpu scheduling / 동기화 원리 (여기까지 중간) / 동기화 예제 / deadlock (프로그램이 서로 기다림)

Process Concept

Process Concept

• An operating system executes a variety of programs that run as a process.
• Process – a program in execution; process execution must progress in sequential fashion
• Multiple parts
  • The program code, also called text section
  • Current activity including program counter, processor registers
  • Stack containing temporary data
    • Function parameters, return addresses, local variables
  • Data section containing global variables
  • Heap containing memory dynamically allocated during run time

• 운영 체제는 프로세스로 실행되는 다양한 프로그램을 실행한다.
• Process – 실행 중인 프로그램. 프로세스 실행은 순차적 방식으로 진행되어야 한다.
• 다중 부품
  • Text Section이라고 하는 프로그램 코드
  • Program Counter, 프로세서 레지스터를 포함한 현재 작업
  • 임시 데이터가 포함된 Stack
    • 함수 매개 변수, 반환 주소, 로컬 변수
  • 전역 변수를 포함하는 Data section
  • 실행 시간 동안 동적으로 할당된 메모리가 포함된 Heap

프로세스는 프로그램을 수행하는 것이다. 사용 설명서가 프로그램, 사용 설명서대로 따라하는 동작이 프로세스이다.
프로세스는 메모리 상에 로딩이 되어야 한다. 프로세스는 text(명령어), program counter(cpu 안 register 값, 다음 어느 instruction을 수행할지 가리킴. cpu에 있지만 프로세스마다 cpu를 사용할 때 다음 수행할 instruction 번지수가 어디일지 알아야 한다. cpu는 여러 프로세스가 공유하기 때문에.), stack(주로 일시적인 데이터를 보관한다. function을 부르고 저장할 때), data(데이터 저장), heap(데이터 저장)이 있다.

• Program is passive entity stored on disk (executable file); process is active
  • Program becomes process when executable file loaded into memory
• Execution of program started via GUI mouse clicks, command line entry of its name, etc
• One program can be several processes
• Consider multiple users executing the same program

• 프로그램은 디스크에 저장된 passive 엔티티(실행 파일)이며, 프로세스는 active이다.
  • 실행 파일이 메모리에 로드되면 프로그램이 처리된다.
• GUI 마우스 클릭, 이름 명령줄 입력 등을 통해 시작된 프로그램 실행
• 하나의 프로그램은 여러 프로세스가 될 수 있다.
• 동일한 프로그램을 실행하는 여러 사용자를 고려한다.

프로그램은 passive (멈춰 있음), process는 active(살아서 움직인다.)
program은 excutable file 일종으로써 storage에 저장되어서 가만히 있는다.
프로그램을 수행함으로써 해당 프로세스가 동작하는 것이다.
프로그램은 UI를 통해서 수행된다.
한 프로그램에 여러 프로세스가 존재할 수 있다. (하나의 프로그램은 여러 프로세스로 수행될 수 있다. concurency. 동시성. 소프트웨어 소스 코드를 function으로 분리한다.)

Process in Memory

프로세스는 프로그램이 메모리에 로딩돼서 실제로 동작하는 과정이다. 프로세스가 메모리에 있을 때 text(instruction), data(프로그램할 때 미리 설정한 데이터),heap(프로그램 도중에 확장된 메모리 데이터), stack(함수의 local variable, argument, return value등 일시적인 것을 저장)이 있다.
stack과 heap은 메모리 영역이 늘었다 줄었다 하기 때문에 가운데 공간은 비어있어야 한다.

Memory Layout of a C Program

어느 프로그램의 어느 부분이 compile해서 excutable 파일을 만들고 메모리에 로딩됐을 때 어느 것이 어디에 저장되는지를 알아보기.

global variable: data 영역. 초기화했는지 안했는지에 따라 이름이 다름. 프로그램 수행 도중에 변하지 않는다.
argument: stack 영역.
local variable: stack 영역. 또다른 함수 call을 했을 때 stack에 쌓인다. return 할 때 stack이 줄어든다.
malloc: heap 영역.

+ thread는 프로세스이다. 같은 프로세스 두 개가 동시에 수행되면 메모리가 낭비된다. InterProcessCommunication을 해야 한다. 그래서 thread를 만들어서 공유할 수 있는 것은 공유하고 공유 안되는 것은 각자 가진다. thread는 죽는 것도 생성하는 것도 빠르다. 공유하는 데이터 간의 통신을 하면 된다. global memory. thread는 text, global data 공유가 된다. stack은 공유가 되지 않는다.

Process Scheduling

Process State

• As a process executes, it changes state
  • New: The process is being created
  • Running: Instructions are being executed
  • Waiting: The process is waiting for some event to occur
  • Ready: The process is waiting to be assigned to a processor
  • Terminated: The process has finished execution

프로세스는 살아서 움직이기 때문에 상태가 시시각각 변한다. new는 새로 생성하는 상태, running은 실제로 동작하는 상태, waiting은 이벤트를 기다리는 상태, ready는 이벤트가 발생하면 cpu 할당을 기다리는 상태, terminated는 종료하는 상태이다.

new, terminated 사이 running, waiting, ready 상태가 반복되면서 프로세스가 수행된다.

Diagram of Process State

state transition diagram. state는 상태, transition은 변화이다. 프로세스가 변하는 상태를 표시한다.
cpu 할당 받는 상태가 running, 이벤트를 기다리는 상태가 waiting, 이벤트가 발생했다면 ready 상태.
(time sharing 상태에서는 timer interrupt가 걸릴 수 있다.running->ready)

Process Control Block (PCB)

Information associated with each process
(also called task control block)

• Process state – running, waiting, etc
• Program counter – location of instruction to next execute
• CPU registers – contents of all process-centric registers
• CPU scheduling information- priorities, scheduling queue pointers
• Memory-management information – memory allocated to the process
• Accounting information – CPU used, clock time elapsed since start, time limits
• I/O status information – I/O devices allocated to process, list of open files

운영체제에서는 프로세스 관리, 메모리 관리, 파일 관리, I/O 관리를 한다.
프로세스 관리를 위해서는 프로세스 테이블이 필요하다.
(메모리는 page 테이블, segment 테이블로 관리한다.)

프로세스 관리하는 테이블은 Process Contrl Block(PCB)이다.
프로세스 상태, 프로세스 번호, program counter+registers(cpu를 할당 받은 프로세스가 cpu를 이용한다. cpu는 하나고 프로세스는 여러 개 있다. 어디까지 수행했는지 pc에 보관해야 한다. pc 이외에도 다른 값도 저장해야 한다. 각 프로세스마다 보관해야 한다.), memory limits, list of open files, ...

(16p)

register
cache
memory (process)
process가 올려놓고 사용을 했다. program counter. cpu register를 사용하는데 register에 있던 것이 다른 프로그램이 수행된다. 자신이 쓰던 register 값을 overwrite했다. 엉망이 되어 있으면 다시 실행해야 하므로 register 값도 잘 저장해두어야 한다.
save state into PCB
reload state from PCB
momory -> register : save
register -> memory : reload
이런 것을 context라고 한다. 자신이 동작하던 상황.

파일을 오픈할 때마다 id를 할당 받는다.
일반적인 운영체제에서 pcb에는 이러한 정보를 담아둔다.

Threads

• So far, process has a single thread of execution
• Consider having multiple program counters per process
  • Multiple locations can execute at once
    • Multiple threads of control -> threads
• Must then have storage for thread details, multiple program counters in PCB
• Explore in detail in Chapter 4

process는 프로그램을 수행하는 것이고 thread는 프로세스 자원을 공유하는 것이다. 한 프로세스가 있는데 그 안에 program을 수행하는 action이 여러 개 있을 수 있다.
한 프로그램을 세 개의 프로세스로 수행한다고 하자. 그럼 프로세스가 3개이고, 프로세스끼리 통신하는 데 IPC를 해야 해서, overhead가 많다. 그래서 프로세스는 하나 만들고 스레드를 여러 개 만들어서 하나의 프로세스에 여러 개의 action이 존재하게 하는 것이 multi thread이다.
multi thread를 수행하면 자원을 적게 차지하고, shard-memory처럼 global data로 통신해서 속도가 더 빨라진다.

Process Representation in Linux

Represented by the C structure task_struct

리눅스에서 사용하는 PCB이다. tast_struct라고 불린다.
PID(프로세스 번호), state(상태), time_slice(cpu 할당받은 시간), parent_process, child_process(누가 parent인지 가리킨다.), head_child(첫번째 child), access file 정보, 메모리 공간을 저장한다.

자신의 parent가 누구고 child가 누구인지. parent가 fork 여러 번 했다면..

Process Scheduling

• Maximize CPU use, quickly switch processes onto CPU core
• Process scheduler selects among available processes for next execution on CPU core
• Maintains scheduling queues of processes
  • Ready queue – set of all processes residing in main memory, ready and waiting to execute
  • Wait queues – set of processes waiting for an event (i.e. I/O)
  • Processes migrate among the various queues

프로세스는 여러 개 있는데 cpu는 하나이다. 언제 어떤 프로세스를 cpu를 수행할 것인지.
cpu가 여러 개 있는 multi processer 시스템과 cpu 안에 cpu 역할을 하는 multi core가 있다. 그러나 cpu나 core수보다 process 수가 훨씬 많다.

어느 cpu가 어느 프로세스를 언제 수행할 것인가를 정하는 것이 process scheduling이다. ready queue는 cpu를 기다리는 queue, wait queue는 이벤트를 기다리는 queue이다.

리소스를 여러 프로세스에 스케쥴링하고 어떤 리소스가 부족할 때 프로세스는 기다리게 되는데 그것이 queue이다. 어떤 자원이 있다면 자원을 기다리는 것이 queue이다.

ready queue는 cpu를 기다린다.
wait queue는 I/O나 이벤트를 기다린다.

cpu scheduling. cpu를 하나로 가정했다. core나 cpu가 많으면 그만큼 running 상태에 있는 것이 많이 있다. 그래서 wait 상태에 있는 것도 많다.
core든 cpu든 컴퓨터는 queue를 공유하지 않는다.
multi-computer는 큐가 틀리다.
ready queue는 하나, wait queue는 여러 개.

Ready and Wait Queues

큐를 연결 리스트로 표현할 수 있다. ready queue는 cpu를 기다리는 queue이다. process 테이블을 head는 가장 앞에 있는 것, 여러 pcb를 연결해서 자료구조로 가지고 있다. head는 가장 앞에 있는 것, tail은 가장 뒤에 있는 것이다.

ready queue는 cpu를 기다리는 process를 보관하는 자료구조이다. cpu scheduler가 동작할 때 하나를 골라서 cpu를 할당한다.
waiting queue는 목적에 따라 여러 개가 존재한다. i/o나 event마다 기다리는 프로세스들이 있다면 head를 통해 가장 앞에 있는 것을 연결해서 queue를 관리한다.

Representation of Process Scheduling

여러 가지 queue를 종합적으로 그린 그림이다. cpu 서비스를 기다리기 위해 process들이 cpu 할당을 기다리고 있다. cpu는 어떤 process 수행을 끝내면 ready queue 프로세스 중 하나를 골라서 cpu 서비스를 해주게 된다.

I/O request, time slice expired, create child process, wait for an interrupt에서도 마찬가지이다.

I/O를 기다리는 건지, I/O가 끝나기를 기다리는 건지 구분해야 한다.
parent가 child를 fork(copy)했다. 프로그램 수행은 parent가 child를 끝나기를 기다린다. cpu를 놓는다.

이렇게 기다리는 상태를 queuing diagram이라고 한다. 동그라미는 서비스이고, queue는 서비스를 기다리는 대기열이다.

CPU Switch From Process to Process

A context switch occurs when the CPU switches from one process to another.

스케쥴링은 cpu가 언제 어느 프로세스를 수행할 것인지 순서를 결정한다. 시간의 계획을 잡는다.
스위칭은 스케쥴에 의해 A가 수행됐다가 B가 수행될 시간이 되면 B로 cpu 사용권을 넘기는 동작이다.

context는 프로세스가 동작하던 상태를 말한다.

process 0번, 1번이 있다고 가정한다. 프로세스 수행 순서는 스케쥴링에서 결정된다. 상태가 바뀔 때가 되면 context save해서 pcb(pc, register 값도 저장)에 잘 보관한다. 그리고 프로세스를 불러올 때는 pcb에서 잘 reload(resume) state한다.

cpu 사용권이 넘어갈 때 잘 저장하고 로딩하는 것이 중요하다.

Context Switch

• When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch
• Context of a process represented in the PCB
• Context-switch time is overhead; the system does no useful work while switching
  • The more complex the OS and the PCB -> the longer the context switch
• Time dependent on hardware support
  • Some hardware provides multiple sets of registers per CPU -> multiple contexts loaded at once

context switch는 돌던 프로세스의 상태를 잘 저장하는 것이다. 돌던 것을 잘 보관하고 돌려고 하는 프로세스를 reload, resume하는 상태를 context switching이라고 표현한다.

cpu 놓는 것은 save, cpu 사용하는 것은 reload

Multitasking in Mobile Systems

• Some mobile systems (e.g., early version of iOS) allow only one process to run, others suspended
• Due to screen real estate, user interface limits iOS provides for a
  • Single foreground process- controlled via user interface
  • Multiple background processes– in memory, running, but not on the display, and with limits
  • Limits include single, short task, receiving notification of events, specific long-running tasks like audio playback
• Android runs foreground and background, with fewer limits
  • Background process uses a service to perform tasks
  • Service can keep running even if background process is suspended
  • Service has no user interface, small memory use

multi programming은 메모리에 여러 프로그램을 로딩하는 것이다. 빠른 cpu가 A를 수행했다 B를 수행했다 time sharing에 의해 짧은 시간동안 cpu 사용권이 넘어간다. cpu 시간을 쪼개 쓰는 것이 multi tasking이다.

foreground는 User Interaction가 있는 프로세스이다.
background는 User Interaction가 없는 프로세스이다.

안도로이드에서는 중간 단계인 서비스라는 프로세스를 두었다. 서비스는 원래는 background이지만 사용자가 그 프로그램을 수행하는 것을 느낄 수 있는 것이다.
음악 파일을 듣는 것이 background이지만 소리가 들린다. 제한적이지먄 UI가 일부 있을 수 있는 것이다.

memory에서 virtual memory로 swap in swap out.
모바일에서는 Memory와 SSD(비휘발성 메모리)를 쓴다. SSD는 쓰기 횟수의 제약이 있다. 그리고 쓰는 속도가 느리다. 그래서 swapping을 안쓴다. memory가 모자르면 프로그램을 종료해야 한다. 프로그램이 종료될 때 기본적인 사항만 ssd에 저장될 수 있다.

Operations on Processes

Operations on Processes

• System must provide mechanisms for:
  • process creation
  • process termination

프로세스가 생성되고 종료하는 것이 시작과 끝이다. 프로세스의 동작에 대해서 알아볼 것이다.

Process Creation

• Parent process create children processes, which, in turn create other processes, forming a tree of processes
• Generally, process identified and managed via a process identifier (pid)
• Resource sharing options
  • Parent and children share all resources
  • Children share subset of parent’s resources
  • Parent and child share no resources
• Execution options
  • Parent and children execute concurrently
  • Parent waits until children terminate

process의 생성. parent-child relationship이 있다. parent에서 child에게 복제한다. process id는 프로세스마다 달라서 fork를 할 때 process id는 달라진다.
parent는 child에 그대로 copy한다.

parent는 child를 fork해서 일을 시키려고 한다. 필요한만큼 만들어서 여러 개의 프로세스를 동시에 수행함으로써 concurrency라는 동시성을 통해 성능의 이득을 보려 한다.

클라이언트의 사용자 요구가 서버 머신으로 간다. 이때 parent 혼자서 여러 사용자의 요청을 받으려면 수많은 client가 오래 기다린다. 이럴 때 child를 만들어서 한 client 요청이 올 때마다 fork한다면 여러 client에게 동시에 서비스를 제공할 수 있다.

• Address space
  • Child duplicate of parent
  • Child has a program loaded into it
• UNIX examples
  • fork() system call creates new process
  • exec() system call used after a fork() to replace the process’ memory space with a new program
  • Parent process calls wait() for the child to terminate

process creation은 프로세스를 생성하는 것이다. unix는 프로세스를 생성할 때 fork system을 쓴다. 동일한 copy를 만들어서 일을 시킬 수가 있고, 다른 프로그램을 수행시키고자 할 때는 child가 execute한다.

fork를 하고 return 되는 값으로 parent와 child를 구분한다. parent는 pid>0이 return되어 child process number를 알려주고, child는 pid=0이 return된다.

이때 parent program은 child를 기다리게 하고, child는 수행이후 exit으로 종료하고 parent 프로그램이 계속 수행한다.

A Tree of Processes in Linux

리눅스에는 system daemon이 있는데 가장 먼저 실행된다.
가장 최초의 process는 create로 의해 만들어진다.
즉 최초의 하나(system daemon)만 create한 것이고, 나머지는 fork한 것이다.

fork한 다음에 execute해서 다른 프로그램으로 바뀐다.
execute는 수행하는 프로그램을 바꾸는 것이다.

C Program Forking Separate Process

parent program이 main을 수행한다. fork하면 똑같은 process가 copy되어 있다.
return되는 값으로 child, parent를 구분한다.
pid가 0보다 작으면 error이다.
pid가 0이면 child로 child가 해야할 일을 프로그래밍한다. exec()로 다른 프로그램을 수행할 수 있도록 했다. path name과 executable file name을 넘겨준다.
pid가 0보다 크면 parent로 parent가 해야할 일을 프로그래밍한다. child가 하는 일이 끝나기를 기다린다.

Creating a Separate Process via Windows API

window api도 parent와 child를 fork하는 것이 제공된다.
window에서는 create_process, wait를 사용한다.

Process Termination

• Process executes last statement and then asks the operating system to delete it using the exit() system call.
  • Returns status data from child to parent (via wait())
  • Process’ resources are deallocated by operating system
• Parent may terminate the execution of children processes using the abort() system call. Some reasons for doing so:
  • Child has exceeded allocated resources
  • Task assigned to child is no longer required
  • The parent is exiting and the operating systems does not allow a child to continue if its parent terminates

프로세스 종료를 의미한다. exit()으로 프로세스를 종료할 수 있다. child가 exit()하면 wait()하던 parent에게 status data를 return한다.
child에 여러 문제가 있을 때, abort() system call을 통해서 종료시킬 수도 있다.

• Some operating systems do not allow child to exists if its parent has terminated. If a process terminates, then all its children must also be terminated.
  • cascading termination. All children, grandchildren, etc. are terminated.
  • The termination is initiated by the operating system.
• The parent process may wait for termination of a child process by using the wait() system call. The call returns status information and the pid of the terminated process
  • pid = wait(&status);
• If no parent waiting (did not invoke wait()) process is a zombie
• If parent terminated without invoking wait , process is an orphan

parent는 wait() system call을 통해서 child 종료를 기다릴 수 있다.
cascading termination은 parent가 종료될 때 child도 함께 종료되는 상태를 말한다.
만약 parent가 wait()하지 않는다면 child는 정상 종료가 되지 않고 zombie 상태가 된다.
만약 parent가 먼저 종료되면 orphan 상태가 된다.

Android Process Importance Hierarchy

• Mobile operating systems often have to terminate processes to reclaim system resources such as memory. From most to least important:
  • Foreground process
  • Visible process
  • Service process
  • Background process
  • Empty process
• Android will begin terminating processes that are least important.

안드로이드에서는 세분해서 process 계층 구조가 존재한다.
visible은 프로세스 동작 상태를 foreground process를 통해서 보는 것이다.
service는 background process이지만 간접적으로 동작 상태를 볼 수 있는 것이다.

Multiprocess Architecture - Chrome Browser

• Many web browsers ran as single process (some still do)
  • If one web site causes trouble, entire browser can hang or crash
• Google Chrome Browser is multiprocess with 3 different types of processes:
  • Browser process manages user interface, disk and network I/O
  • Renderer process renders web pages, deals with HTML, Javascript. A new renderer created for each website opened
    • Runs in sandbox restricting disk and network I/O, minimizing effect of security exploits
  • Plug-in process for each type of plug-in

multiprocess가 다양한 용도로 사용된다. 다양한 프로세스로 분리된다.
browser는 사용자 인터페이스, network I/O.
renderer는 웹 사이트를 만들 때마다 독립적으로 생선된다.
plug-in은 미디어 파일 재생 등을 돕는다.

Interprocess Communication

Interprocess Communication

• Processes within a system may be independent or cooperating
• Cooperating process can affect or be affected by other processes, including sharing data
• Reasons for cooperating processes:
  • Information sharing
  • Computation speedup
  • Modularity
  • Convenience
• Cooperating processes need interprocess communication (IPC)
• Two models of IPC
  • Shared memory
  • Message passing

프로세스끼리의 연관 관계는 다양하다.
그 중에는 프로세스 간에 협력을 해야하는 관계도 있다.
웹 브라우저, 렌더러, 플러그인 등에서는 여러 프로세스가 동시에 협력을 해서 동작을 한다.
운영체제에서 interprocess communication API가 제공되며 어느 정도 규모가 있는 대부분의 프로그램은 인터프로세스 커뮤니케이션을 한다.
프로세스 협력의 이유로는 정보 공유, 속도 향상, 유지 보수(Module별로 관리), 편리성이 있다.
IPC 모델로는 아래의 두 개가 있따.
shared memory 모델 : 프로세스 간의 공유할 수 있는 메모리 공간이 있어서 write하고 read함으로써 통신한다.
message passing : 직접 데이터가 또 다른 곳으로 이동하는 형태이다.

Communication Models

shared memory 모델은 shared memory 공간이 있어서 한 프로세스가 write한 것을 또 다른 프로세스가 read해서 통신한다.
message passing 모델이다. process A가 B에게 어떤 데이터를 전달한다. A의 user 영역의 데이터가 커널의 message queue로 가서 message queue의 주소로 가져다가 놓고 프로세스 B가 가져와서 자신의 user 영역에서 사용한다. 실제 데이터가 이동한다. message queue를 이용하는 형태도 있고, 데이터를 직접 전달하는 형태도 있다.
A가 B에게 데이터를 전달할 때 커널 영역의 버퍼 또는 메시지 큐를 이용을 하게 되는데 프로그래머 관점에서 A는 B에게 데이터를 보낼 때 send한다. A는 데이터를 보내고 B는 데이터를 receive한다.

Cooperating Processes

• Independent process cannot affect or be affected by the execution of another process
• Cooperating process can affect or be affected by the execution of another process
• Advantages of process cooperation
  • Information sharing
  • Computation speed-up
  • Modularity
  • Convenience

프로세스는 independent 관계, cooperating 관계가 있다.
한 앱 안에서 여러 프로세스가 협력하는 관계가 cooperating 관계이다.
협력하는 관계는 IPC를 이용함으로써 많은 혜택이 있다.
정보교환, 속도향상, 수월성, 편리성을 제공한다.

Producer-Consumer Problem

• Paradigm for cooperating processes, producer process produces information that is consumed by a consumer process
  • unbounded-buffer places no practical limit on the size of the buffer
  • bounded-buffer assumes that there is a fixed buffer size

프로세스를 작성할 때 규모가 있는 대부분의 프로그램은 multi process로 동작한다.
application에는 종류가 많다. 많은 것을 일일히 학습하기 힘들어서 모델을 만든다.
애플리케션이 여러 프로세스로 나뉘어져서 프로그래밍을 하고 프로세스 간에 interface하는 것이 비교적 수의 모델로 모델링할 수 있다.
여러 모델링이 있는데, Producer-Consumer 모델에 대해 알아볼 것이다.
Producer는 데이터를 생성하고 Consumer는 데이터를 소비한다.
많은 애플리케이션에서 사용하고 있다. 프린터 작업을 할 때 프린터할 작업을 printer spooler에 가져다 놓는다. 그것이 producer이다. printer device driver는 printer spooler에 있는 것을 printing 작업을 한다.
버퍼가 있는데 producer는 버퍼에 데이터를 생성하고 consumer는 producer가 생산해 놓은 데이터를 가져가서 사용한다.
unbounded-buffer는 무한정 큰 버퍼이고, bounded-buffer는 제약이 있는 버퍼이다.물리적으로는 buffer size는 메모리에 있어서 bounded-buffer가 맞다. 우리는 buffer 0번부터 1024번까지 데이터를 저장해놓을 수 있는 공간이 있을 수 있다. 그러면 1024를 다 사용하고 난 다음에 다시 0번으로 되돌아갈 수 있을 것이다.
가상으로 무한정 많은 버퍼가 있는 것처럼 사용을 할 수 있다.
producer가 생성할 때 consumer가 앞에서부터 가져가서 빈 공간을 만들어주어야 한다. 그래야 producer가 끝까지 가서 다 채워놨을 때 consumer가 앞에서 생성해 놓은 것을 가져가야 빈공간이 만들어지고 그 빈공간에 producer가 생산을 할 수 있을 것이다.

IPC in Shared-Memory Systems

Interprocess Communication - Shared Memory

• An area of memory shared among the processes that wish to communicate
• The communication is under the control of the users processes not the operating system.
• Major issues is to provide mechanism that will allow the user processes to synchronize their actions when they access shared memory.
• Synchronization is discussed in great details in Chapters 6 & 7.

shared memory model을 사용할 때 주의해야 할 점은 동기화이다.
shared memory model이 있고 여러 가지 프로세스가 data에 동시에 access할 때 data가 conflict가 일어나면 안된다.
예를 들어 예약 상태를 데이터에 저장한다고 생각했을 때 두 개 이상의 사용자가 동일한 좌석에 예약하려 할 때 한 자리를 한 사용자에만 할당해주어야 한다. 이것이 동기화이다.

Bounded-Buffer - Shared-Memory Solution

• Shared data
  

shared data를 한 개부터 여러 개의 producer와 consumer가 하나의 데이터 공간을 access한다. 이때 item structure는 데이터를 저장해두는 공간이다.
buffer의 사이즈만큼 아이템을 저장할 수 있다.
in은 프로듀서가 생산해 놓을 때 생산해놓을 데이터를 in할 위치이다.
consumer가 밖으로 읽어가는데 out은 가져가는 pointer이다.

즉, buffer 공간에서 producer는 데이터를 쌓아둘 것이고 (in은 producer가 생산할 위치), consumer는 item들을 가져간다(out은 consumer가 가져가는 위치).

• Solution is correct, but can only use BUFFER_SIZE-1 elements
  

shared memory 모델을 이용해서 프로듀서의 프로그램을 작성할 수 있다. 프로듀서는 in pointer에 producer를 하려 하는데 in producer의 위치가 out과 같다는 것은 빈 공간이 꽉 차있다는 것이다. 그러면 producer는 consumer가 가져가서 빈 공간을 만들기를 기다린다. 그리고 생산할 item을 buffer의 in 포인트에 가져다 놓고 in 포인트를 하나 높인다.
consumer도 마찬가지로 program을 작성하는데 in과 out이 같은 것은 비어있는 상태라는 것이고, producer가 item을 생성하기를 기다려야 한다. out하고 가져가서 next item을 자기가 사용하면 된다. out 포인트를 하나 가져가고 next item에서 사용하고, out 포인트를 하나 증가시킨다.

consumer process나 producer process는 shared memory 공간을 이용해서 프로그램을 작성한다.

IPC in Message-Passing Systems

Interprocess Communication - Message Passing

• Mechanism for processes to communicate and to synchronize their actions
• Message system – processes communicate with each other without resorting to shared variables
• IPC facility provides two operations:
  • send(message)
  • receive(message)
• The message size is either fixed or variable

message passing은 한 프로세스가 다른 프로세스에게 데이터를 전달한다. OS는 send, receive API를 제공한다. 운영체제마다 제공하는 IPC API를 통해 다양한 형태의 시스템 프로그래밍을 쉽게 할 수 있다.

• If processes P and Q wish to communicate, they need to:
  • Establish a communication link between them
  • Exchange messages via send/receive
• Implementation issues:
  • How are links established?
  • Can a link be associated with more than two processes?
  • How many links can there be between every pair of communicating processes?
  • What is the capacity of a link?
  • Is the size of a message that the link can accommodate fixed or variable?
  • Is a link unidirectional or bi-directional?

process P와 Q가 커뮤니케이션 했을 때 다양한 option이 존재한다.
먼저 communication link가 설정되어야 하고 이후 데이터를 send, recive한다.
implementation을 했을 대 link(connection 연결)이 어떻게 되고, 여러 개의 프로세스가 동시에 연결할 수가 있는건지. 두 사람의 통화가 단체 통화가 되는건지, 링크의 용량, 그 밖에 다양한 옵션이 있다. 다양한 API들은 다양한 옵션을 프로그래머가 선택해서 사용할 수 있다. window, linux, java 마다 다양한 형태의 message passing API가 있다. 요구사항에 따라서 다양한 옵션을 선택하고 사용하는 것이 중요하다.

• Implementation of communication link
  • Physical:
    • Shared memory
    • Hardware bus
    • Network
  • Logical:
    • Direct or indirect
    • Synchronous or asynchronous
    • Automatic or explicit buffering

communication link를 구현하는 방법은 다음과 같다.
물리적으로 shared memory, hardware bus, network 등으로 communication link가 물리적으로 다양할 수 있다.
논리적으로는 다음과 같다.
직접적으로 하는 건지, 간접적으로 하는 건지.
synchronous에서는 데이터가 올때까지 기다리던지, 없는대로 실패하는지. asynchronous에서는 데이터 receive를 할 때 데이터가 왔음을 signal로 알려주는 기능이 있다. 물론 대부분의 운영체제에서는 synchronous와 asynchronous 모두 지원한다. 요구사항에 따라 선택해서 사용한다.

Direct Communication

• Processes must name each other explicitly:
  • send (P, message) – send a message to process P
  • receive(Q, message) – receive a message from process Q
• Properties of communication link
  • Links are established automatically
  • A link is associated with exactly one pair of communicating processes
  • Between each pair there exists exactly one link
  • The link may be unidirectional, but is usually bi-directional

목적지 주소를 통해 우편물을 보내는 것에 비유된다.
send: P에게 메시지를 전달한다.
recevie: Q로부터 메시지를 받아서 메시지를 저장한다.
직접적으로 데이터를 주고 받는다.
여러 옵션이 존재한다. 대부분의 운영체제는 다양한 선택사항을 제공하고 있어서 프로그래머가 선택해서 사용하면 된다.

Indirect Communication

• Messages are directed and received from mailboxes (also referred to as ports)
  • Each mailbox has a unique id
  • Processes can communicate only if they share a mailbox
• Properties of communication link
  • Link established only if processes share a common mailbox
  • A link may be associated with many processes
  • Each pair of processes may share several communication links
  • Link may be unidirectional or bi-directional

메일박스나 게시판으로 비유할 수 있다.
제 3의 공간에 데이터를 주고 데이터를 받는다. indirect communication의 대표적인 예는 mailbox이다.
데이터를 보내고 받는 사람이 주소에 합의를 봐서 그 주소의 mail box에 데이터를 집어넣고 받는 사람은 데이터를 받아가면 된다.

• Operations
  • create a new mailbox (port)
  • send and receive messages through mailbox
  • destroy a mailbox
• Primitives are defined as:
  • send(A, message) – send a message to mailbox A
  • receive(A, message) – receive a message from mailbox A

indirect communication에서는 메일박스를 생성하고 메일박스에서 데이터를 주고 받는다. 메시지를 받아서 메시지 버퍼에 집어넣는다. A가 메일박스 주소이다. 메일박스 주소를 서로 약속하고 데이터를 받아가게 된다.

• Mailbox sharing
  • P1, P2, and P3 share mailbox A
  • P1, sends; P2 and P3 receive
  • Who gets the message?
• Solutions
  • Allow a link to be associated with at most two processes
  • Allow only one process at a time to execute a receive operation
  • Allow the system to select arbitrarily the receiver. Sender is notified who the receiver was.

메일박스 공유를 할 때 process 1,2,3번이 공유하고 1번이 보내고 2,3번은 받는다.
상식적으로 p1은 메일박스에 집어넣는데 2번 3번이 메일박스로 받아가려고 할 때 서로 메시지를 받아가려고 경쟁을 하게 될 것이다.
API를 통해서 어떻게 control을 할 수 있는지. 먼저 open해서 가져가는 것이 우선권이 있는데 아니면 p3가 번갈아가면서 메일박스에서 데이터를 가져가게 할지.
app 요구사항에 따라서 다양한 option들을 선택해서 사용할 수 있다.

Synchronization

• Message passing may be either blocking or non-blocking
• Blocking is considered synchronous
  • Blocking send -- the sender is blocked until the message is received
  • Blocking receive -- the receiver is blocked until a message is available
• Non-blocking is considered asynchronous
  • Non-blocking send -- the sender sends the message and continue
  • Non-blocking receive -- the receiver receives:
    • A valid message, or
    • Null message
• Different combinations possible
  • If both send and receive are blocking, we have a rendezvous

메시지를 주고 받을 때 blocking이냐 nonblocking이냐, synchronous냐 asynchronous인지를 구분해야 한다. 지금 자기가 작성하는 app이나 system software에서 어느 모델을 사용할 것인지를 파악을 해서 선택해서 사용하면 된다.

blocking은 send나 recevice할 때 완성할 때까지 기다리는 것을 말한다.
blocking receive는 데이터를 읽으려고 하는데 데이터가 없으면 데이터가 올 때까지 기다리는 것이다.
non-blocking은 sender는 send하고 send함수가 return된다.
non-blocking receive는 receive를 하는데 데이터가 있으면 recieve하고 데이터가 없으면 데이터가 없는대로 receive가 return된다.
blocking non-blockin의 차이는 완성이 될 때까지 기다리는 것/바로 return하는 것에서 있다.

엄밀히 말하면 asynchronous는 recieve를 했는데 바로 return이 되고 데이터가 도착하면 signal을 통해서 알려주기 때문에 signal handler routine에 의해서 데이터를 받을 수 있는 것이다.

Producer - Shared Memory

producer에서는 생산한다.
message passing에서는 send, shared memory에서는 write한다.

send이기 때문에 message passing 모델이다.

Consumer - Shared Memory

consumer, recieve이기 때문에 message passing 모델로 recieve하면 된다.

consumer와 sender는 모두 process이다.

Buffering

• Queue of messages attached to the link.
• Implemented in one of three ways
  • 1. Zero capacity – no messages are queued on a link.Sender must wait for receiver (rendezvous)
  • 2. Bounded capacity – finite length of n messagesSender must wait if link full
  • 3. Unbounded capacity – infinite length Sender never waits

버퍼링은 양단의 차이가 많이 있다. CPU와 I/O의 관계에 있어서 buffer를 두어서 느린 I/O가 천천히 가져다 놓으면 빠른 I/O가 빠르게 가져다 놓을 수 있다.
양쪽에 차이를 양화해주는 것이 buffering이다.
buffer가 없는 경우, buffer size가 한 개가 있는 것, buffer 사이즈가 무한정 있는 것이 있다.
일반적으로 IPC에서 Process 사이 buffer가 있다. bounded, unbounded는 사이즈의 차이이다.

Examples of IPC Systems

Examples of IPC Systems - POSIX

• POSIX Shared Memory
  • Process first creates shared memory segment
    • shm_fd = shm_open(name, O CREAT | O RDWR, 0666);
  • Also used to open an existing segment
  • Set the size of the object
    • ftruncate(shm_fd, 4096);
• Use mmap() to memory-map a file pointer to the shared memory object
• Reading and writing to shared memory is done by using the pointer returned by mmap().

POSIX 표준의 IPC.
Shared Memory 모델. shm_open을 통해서 공유할 수 있는 shared memory를 생성한다. ftruncate를 통해서 size를 설정한다. map()을 통해서 open했을 때의 file descripter를 메모리 주소 공간으로 mapping 한다.

IPC POSIX Producer

POSIX Producer 프로그램의 예시이다. (shared memory를 생성한다. ftruncate를 통해서 size를 설정한다. map()을 통해서 open했을 때의 file descripter를 메모리 주소 공간으로 mapping 한다.)

IPC POSIX Consumer

POSIX Consumer 프로그램의 예시이다. 이전에는 Producer에서 생성한 것을 readonly로 읽기만 한다. map()을 통해서 return된 pointer를 통해서 생성한 데이터를 읽어간다.

Examples of IPC Systems - Mach

• Mach communication is message based
  • Even system calls are messages
  • Each task gets two ports at creation- Kernel and Notify
  • Messages are sent and received using the mach_msg() function
  • Ports needed for communication, created via
    • mach_port_allocate()
  • Send and receive are flexible, for example four options if mailbox full:
    • Wait indefinitely
    • Wait at most n milliseconds
    • Return immediately
    • Temporarily cache a message

애플의 MAC OS.
mach_msg(). 메시지를 통해서 데이터를 주고받는다.
mach_port_allocate(). 커뮤티케이션 포트를 설정했다.

Mach Messages

포트를 먼저 설정한다.

Mach MEssage Passing - Client

먼저 mach_msg()를 통해서 자신이 send라는 것을 표시하고 포트는 미리 설정을 해두었기 때문에 메시지 send를 할 수 있다. (?)

Mach Message Passing - Server

먼저 mach_msg()를 통해서 자신이 recieve라는 것을 표시하고 서버의 포트에서 데이터를 읽는다.

Examples of IPC Systems - Windows

• Message-passing centric via advanced local procedure call (LPC) facility
  • Only works between processes on the same system
  • Uses ports (like mailboxes) to establish and maintain communication channels
  • Communication works as follows:
    • The client opens a handle to the subsystem’s connection port object.
    • The client sends a connection request.
    • The server creates two private communication ports and returns the handle to one of them to the client.
    • The client and server use the corresponding port handle to send messages or callbacks and to listen for replies.

• 고급 로컬 프로시저 호출(LPC) 시설을 통한 메시지 전달 중심
  • 동일한 시스템의 프로세스 간에만 작동
  • 통신 채널을 설정하고 유지하기 위해 포트(사서함 등)를 사용한다.
  • 통신은 다음과 같이 작동한다.
    • 클라이언트가 하위 시스템의 연결 포트 개체에 대한 핸들을 연다.
    • 클라이언트가 연결 요청을 보낸다.
    • 서버는 두 개의 개인 통신 포트를 만들고 그 중 하나의 핸들을 클라이언트로 반환한다.
    • 클라이언트와 서버는 해당 포트 핸들을 사용하여 메시지 또는 콜백을 보내고 응답을 수신한다.

procedure call은 function call을 이야기한다. 한 프로세스 안에서 function을 call할 수 있다. 기능별로 분리한다.
한 프로세스 안에서만 function을 call한다. 또 다른 프로세스나 computer에서는 function call을 할 수가 없다.
window에서는 remote procedure call이 있다. 원격지에 있는 함수를 call한다. local과는 형태가 유사하다.
function call은 한 프로세스 안에 있는 function을 call한다.
remote는 다른 컴퓨터에 있는 다른 프로세스 안의 function call.
local은 한 컴퓨터에 있는 다른 프로세스 안의 function call.
window local

Local Procedure Calls in Windows

서버는 client가 연결할 수 있는 handle을 제공한다. handle을 통해서 connection을 요청한다. 연결 설정에 해당한다.
서버는 communication port를 생성한다. client의 port, server의 port를 만들어서 통신한다.
local procedure call은 window에서 제공하며, 한 computer 안에 있는 process끼리 function을 호출할 수 있는 것을 말한다.

Pipes

• Acts as a conduit allowing two processes to communicate
• Issues:
  • Is communication unidirectional or bidirectional?
  • In the case of two-way communication, is it half or full-duplex?
  • Must there exist a relationship (i.e., parent-child) between the communicating processes?
  • Can the pipes be used over a network?
• Ordinary pipes – cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created.
• Named pipes – can be accessed without a parent-child relationship.

• 두 프로세스가 통신할 수 있는 통로 역할을 한다.
• 문제:
  • 통신은 단방향인가, 양방향인가?
  • 쌍방향 통신의 경우 반이중인가, 아니면 전이중인가?
  • 의사소통 과정 사이에 관계(즉, 부모-자녀)가 존재해야 하는가?
  • 파이프를 네트워크를 통해 사용할 수 있는까?
• 일반 파이프 – 파이프를 만든 프로세스 외부에서 액세스할 수 없다. 일반적으로 상위 프로세스는 파이프를 생성하고 파이프를 사용하여 생성한 하위 프로세스와 통신한다.
• 명명된 파이프 – 부모-자녀 관계 없이 액세스할 수 있다.

parent-child relationship이 있어야 pipe를 통해서 데이터를 주고 받을 수 있다.
parent가 pipe를 생성한다. parent는 child를 fork해서 생성한다.
이때 parent가 생성한 pipe 또한 child가 물려받는다.
생성한 pipe를 통해서 parent-child가 통신한다.

Ordinary pipe : 일반적인 pipe는 parent-child relationship이 있다.
Named pipe : parent-child relation이 없다. 한 컴퓨터에 있는 서로 상관없는 일반적인 프로세스가 mk FIFO를 통해서 데이터를 주고 받는다.

Ordinary Pipes

• Ordinary Pipes allow communication in standard producer-consumer style

• Producer writes to one end (the write-end of the pipe)

• Consumer reads from the other end (the read-end of the pipe)

• Ordinary pipes are therefore unidirectional

• Require parent-child relationship between communicating processes
  

• Windows calls these anonymous pipes

• 일반 파이프를 통해 표준 생산자-소비자 스타일로 통신 가능

• Producer는 한쪽 끝에 쓴다 (파이프의 write-end)

• Consumer가 다른 쪽 끝에서 읽는다(파이프의 *read-end)

• 따라서 일반 파이프는 단방향입니다.

• 커뮤니케이션 프로세스 간에 부모-자녀 관계 필요하다.
  

• Windows에서 이러한 익명 파이프를 호출합니다.

pipe를 만들 수 있는 api는 pipe이다.
file descripter라는 argument를 줘야한다. fd는 array이다. (fd[0], fd[1]..)
pipe는 단방향이다.

Named Pipes

• Named Pipes are more powerful than ordinary pipes
• Communication is bidirectional
• No parent-child relationship is necessary between the communicating processes
• Several processes can use the named pipe for communication
• Provided on both UNIX and Windows systems

• 명명된 파이프는 일반 파이프보다 강력하다.
• 통신은 양방향입니다.
• 통신 프로세스 간에 부모-자녀 관계가 필요하지 않다.
• 여러 프로세스가 명명된 파이프를 사용하여 통신할 수 있다.
• UNIX 및 Windows 시스템에서 모두 제공된다.

file처럼 pipe 이름이 있어서 parent-child relationship이 없어도 이름으로 open한다.
데이터를 fifo로 읽는다. 즉, 먼저 write한 것이 먼저 읽혀진다.

Communication in Client-Server Systems

• Sockets
• Remote Procedure Calls

원격 computer간의 통신해서 사용할 수 있다. computer간의 통신은 운영체제에서 process간의 통신이다. socket은 network에서 tcp,ip.. 통신 프로토콜을 네트워크 환경에서 프로그래밍하는 프로그래머가 api를 제공하는데 이를 socket이라고 부른다.
remote procedure call은 서로 다른 computer의 process끼리 function을 call할 수가 있다는 것이다. RPC는 어떤 function을 어떤 parameter로 부르겠다라는 것을 message를 통해서 보내야 한다. message는 socket을 사용한다.

Sockets

• A socket is defined as an endpoint for communication
• Concatenation of IP address and port – a number included at start of message packet to differentiate network services on a host
• The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8
• Communication consists between a pair of sockets
• All ports below 1024 are well known, used for standard services
• Special IP address 127.0.0.1 (loopback) to refer to system on which process is running

• 소켓은 통신을 위한 끝점으로 정의된다.
• IP 주소와 포트의 연결 – 메시지 패킷 시작 시 포함된 번호로 호스트에서 네트워크 서비스를 구분한다.
• 소켓 161.25.19.8:1625는 호스트 161.25.19.8의 포트 1625를 나타낸다.
• 통신은 한 쌍의 소켓 사이에서 이루어진다.
• 1024 미만의 모든 포트가 잘 알려져 있으며, 표준 서비스에 사용된다.
• 프로세스가 실행 중인 시스템을 참조하는 특수 IP 주소 127.0.0.1(루프백)

Socket Communication

ip주소:port번호

Sockets in Java

• Three types of sockets
  • Connection-oriented (TCP)
  • Connectionless (UDP)
  • MulticastSocket class– data can be sent to multiple recipients
• Consider this “Date” server in Java:

• 3종류의 소켓
  • 연결 지향(TCP)
  • 무연결(UDP)
  • MulticastSocket 클래스 - 데이터를 여러 수신자에게 보낼 수 있다.
• Java의 "날짜" 서버를 생각해 보라.

TCP, UDP는 연결설정의 여부 차이이다.

양쪽에서 socket을 만들고 connection 요청을 하고 accept하고 연결 설정이 되면 send/recieve, write/read한다.

• The equivalent Date client
  

  socket을 만들고 connection 설정을 하고 날짜 정보를 read한다.

Remote Procedure Calls

• Remote procedure call (RPC) abstracts procedure calls between processes on networked systems
  • Again uses ports for service differentiation
• Stubs – client-side proxy for the actual procedure on the server
• The client-side stub locates the server and marshalls the parameters
• The server-side stub receives this message, unpacks the marshalled parameters, and performs the procedure on the server
• On Windows, stub code compile from specification written in Microsoft Interface Definition Language (MIDL)

• RPC(원격 프로시저 호출)가 네트워크 시스템의 프로세스 간 프로시저 호출을 추상화한다.
  • 서비스 차별화를 위해 다시 포트를 사용한다.
• Stubs – 서버의 실제 절차를 위한 클라이언트 측 프록시이다.
• 클라이언트 측 stub은 서버와 marshalls 매개 변수를 찾습니다.
• 서버측 stub은 이 메시지를 수신하고, 마샬링된 매개변수를 풀고, 서버에서 절차를 수행한다.
• Windows에서 stub code는 Microsoft Interface Definition Language(MIDL)로 작성된 사양에서 컴파일된다.

원격지 함수 호출한다. 어떤 함수를 호출하고 parameter가 무엇인지를 socket interface와 같은 network api를 이용한다.
일종의 middleware이다.
stub는 client와 server에 있어서 복잡한 network 설정을 해준다.
parameter들을 client stub가 message 형태로 바꾸어서 보내야하는데 이를 marshalling이라고 한다.

• Data representation handled via External Data Representation (XDL) format to account for different architectures
  • Big-endian and little-endian
• Remote communication has more failure scenarios than local
  • Messages can be delivered exactly once rather than at most once
• OS typically provides a rendezvous (or matchmaker) service to connect client and server

• 외부 데이터 표현(XDL) 형식을 통해 처리되는 데이터 표현은 다양한 아키텍처를 고려한다.
  • Big-endian 및 little-endian
• 원격 통신에 로컬보다 더 많은 장애 시나리오가 있음
  • 메시지는 최대 한 번이 아니라 정확히 한 번 전달될 수 있습니다.
• OS는 일반적으로 클라이언트와 서버를 연결하기 위한 랑데부(또는 매치메이커) 서비스를 제공합니다.

숫자를 표현할 때 1000 숫자를 메모리에 끝자리에 둘 것인지 뒷자리에 둘 것인지를 결정하는 것이 Big-endian과 little-endian이다.
RPC는 변환을 해줘야 한다. 이를 XDL이라고 한다.
matchmaker는 client가 원격지 함수를 호출하는데 원격지 함수를 찾아가는 정보를 제공한다.

Execution of RPC

왼쪽은 client, 오른쪽은 server.
client는 procedure X를 matchmaker에서 누가 procedure X를 제공하는지에 대한 정보를 물어보고 prot p에게 원격지 호출을 보내고 결과를 client로 보내준다.
즉, remote computer 함수를 호출하는 것이다.