Chp 3 Process

tags: 作業系統

• Chp 3 Process
  • Structure of Process
  • Process Control Block (PCB)
  • Scheduling
    • Scheduling queues
    • Scheduler Type
    • Process Type according to Time Consumption
    • Multitasking in Mobile Systems
    • Context Switch
  • Operations on Processes
    • Creation
    • Termination
  • InterProcess Communication (IPC)
    • process cooperation
    • Producer-Consumer Problem
    • Communication Models (待整理)
  • Examples of IPC Systems (待補)
    • POSIX
    • Mach
  • Communication in Client-Server Systems
    • Sockets
    • Remote Procedure Calls (RPC)
    • Pipes

Structure of Process

• 考Layout
  

• Process 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

考

Note: Buffer Overflow

分配Memory時process占用到kernel的部分
Omnom

Process Control Block (PCB)

• a.k.a task control block
• Definition: Store information associated with each process
• Contents
  • Process state
  • Program counter
  • CPU registers
  • CPU scheduling information
  • Memory-management information
  • Accounting information
  • I/O status information

Scheduling

Scheduling queues

1. Job queue
   • contain all process
   • 通常在大型主機才有
2. Ready queue
   • 待在main memory的process準備被執行
3. Device queue
   • wait for I/O device

Scheduler Type

• CPU scheduler (Short-term)
  • select next-executed process and allocates CPU
  • invoke frequently
• Job scheduler (Long-term)
  • select process brought into the ready queue
  • find good process mix
  • invoke infrequently
  • long-term scheduler strives for good process mix
• Medium-term
  • Remove process from memory, store on disk, bring back in from disk to continue execution: swapping
  • Removing process from memory reduces the degree of multiprogramming

Process Type according to Time Consumption

• I/O-Bound
  • spend more time seeking I/O operations
  • CPU burst : many, short
• CPU-Bound
  • spend more time on Computations
  • CPU burst : few, long

Multitasking in Mobile Systems

• foreground:
  • application currently open
  • appearing on the display.
• background:
  • application remains in memory
  • does not occupy the display screen

Context Switch

• with context switch, Multitasking is possible
• time it takes are highly dependent on hardware support
  

Operations on Processes

Creation

• Process is identified and managed via a process identifier (pid)
• Resource sharing option
  • Parent and children share all resources
  • Children share subset of parent’s resources
  • Parent and child share no resources
• Execution option
  • Parent & Child excecute concurrently
  • Parent wait for child's termination
• Example
  • fork(): create new process
  • exec(): a new process
    

Termination

• Child finished and then exit
• Aborted by Parent
  1. Child exceeds allocated resource
  2. task assigned to child isn't required
  3. parent exit

InterProcess Communication (IPC)

• independent v.s. cooperating (待補)

一個task分成好幾個subtask由好幾個process同時進行運算，就是cooperating process的一種情況(computation speedup)，或者說這些process會使用到大家一起分享的記憶體區塊，所以說會彼此影響。
Neko

process cooperation

1. Information Sharing
   • e.g. copy, paste
2. Computational Speedup
   • break task into subtasks
   • subtasks execute in parallel
   • require multiple processing cores
3. Modularity
   • dividing the system functions into separate processes or threads

Producer-Consumer Problem

$i.e.$ Buffer using

Bounded Buffer在例子中看起來是circular queue
Omnom

Communication Models (待整理)

Shared Memory

• 宣告memory時OS才參與，剩餘管理交由user process
• 需要 Process Synchronization
• Pros: Faster
• Cons:
  cache coherence issues, ensures no writing to the same location simultaneously
• Producer-Consumer Problem
  • unbounded-buffer : no limit on the size of the buffer
  • bounded-buffer : a fixed buffer size

Message Passing

• OS管理、mailbox
• Pros:
  useful for exchanging small amounts of data, no conflicts, easier to implement in a distributed system
• Cons: Slower
• require Communication Link (待修)
  Issues

  • How to establish ?
  • one link multiple processes?
  • pair of processes mul tiple link?
  • Capacity of a link
  • size of a message fixed or variable?
  • unidirectional or bi-directional?
• Implementation
  • Physical
    1. Shared memory
    2. Hardware bus
    3. Network
  • Logical:
    1. Direct or indirect
    2. Synchronous or asynchronous
    3. Automatic or explicit buffering

Logical Implementation

• Direct

  • Processes must name each other explicitly
  • message contain process name
  • Links are established automatically
  • A link is associated with exactly one pair of communicating processes
  • usually bi-directional
  • send(P, message)、receive(Q, message), P、Q are processes

• Inderect (use mailbox)

  • message contain mailbox name(mailbox不用時可以destroy掉)
  • Each mailbox has a unique id
  • Processes can communicate only if they share a mailbox
  • A link may be associated with many processes
  • send(A, message)、receive(A, message), A is a mailbox
  • operation:
    • create a new mailbox (port)
    • send and receive messages through mailbox
    • destroy a mailbox

• Message-passing can be blocking or non-blocking

• Synchronous(Blocking)

  • Blocking send: sender is blocked until the message is received
  • Blocking receive: receiver is blocked until a message is available
  • If both send and receive are blocking, we have a rendezvous

• Asynchronous(Non-Blocking)

  • Non-blocking send: the sender sends the message and continue(送完後不等，直接往下走)
  • Non-blocking receive: the receiver receives:
    • A valid message, or
    • Null message

• buffering

  • buffer messages (Queue)
  1. Zero capacity: no messages are queued. (need rendezvous)
  2. Bounded capacity: finite length, sender waits if queue is full
  3. Unbounded capacity: infinite length, sender never waits

Examples of IPC Systems (待補)

POSIX

Mach

Communication in Client-Server Systems

Sockets

• Define: endpoint of communication
• in Java:
  1. Connection-oriented (TCP)(待補)
     • Virtual
     • reliable
  2. Connectionless (UDP)
     • unreliable
  3. MulticastSocket class
     • data can be sent to multiple recipients

Remote Procedure Calls (RPC)

1. abstract the procedure-call mechanism for use between systems with network connections
   Stubs : client-side proxy for the actual procedure on the server
2. Data representation handled via External Data Representation (XDL) format to account for different architectures (Big-endian and little-endian

e.g. [摘]
因為數據傳輸的數據包必須是二進位的，你直接丟一個Java對象過去，人家可不認識，你必須把Java對象序列化為二進位格式，傳給Server端，Server端接收到之後，再反序列化為Java對象。

原文網址：RPC
Omnom

• 考 Difference between Sockets and Remote Procedure Calls (RPC):
  • Sockets allow only unstructured stream of bytes(傳送的資料無結構)
  • RPC provides functions to pass parameters(傳送的資料有結構)

Pipes

• Definition: allowing two processes to communicate
• Ordinary pipes(單向): a.k.a. anonymous pipes
  • a parent process creates a pipe and communicate with its child process
  • Producer writes to one end, Consumer reads from the other end

看起來就是Queue
不過和messeage passing的差異是啥？
Omnom

Pipe是FIFO，但是message queue其實不是。
要從message queue裡面讀資料要使用msgrcv()這個function
ssize_t msgrcv(int msqid, void *msgp, size_t msgsz, long msgtyp,int msgflg);
可以藉由指定msgtyp決定要從message queue中讀出什麼type的資料，說明文件中說了If msgtyp is greater than 0, then the first message in the queue of type msgtyp is read
而這也顯示出了Pipe跟message queue的差異，Pipe是沒有辦法指定型態的，你在讀寫的時候可以指定要讀出或寫入多少的byte，也就是說你自己必須要知道你這次讀要讀多少資料才會是完整的message，這是程式設計者要自己處理的問題。
另外，pipe只能被創建他的Process以及child process使用，而message queue則沒有此限制，pipe在其中一端的process終止後，就沒辦法再被其他的process讀取，在message queue的情況下process可以寫入資料後就終止，但其他的process仍然可以讀取到他剛剛被寫入的資料。
Neko

• Named pipes(雙向):
  more powerful than ordinary pipes.
  can be accessed without a parent-child relationship.