[IOS] Ch3 Process Concept

Process Concept

• An operating system executes a variety of programs: 
• Batch system – jobs
• Time-shared systems – user programs or tasks

• Textbook uses the terms job and process almost interchangeably

• Process – a program in execution; process execution must progress in sequential fashion

• A process is more than the program code, which is sometimes known as the text section.

• A process includes:
• program counter: includes current activity
• stack: contains temporary data
• data section: contains global variables
• heap: memory dynamic allocated during process run time

• Informally, as mentioned earlier, a process is a program in execution.

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

• only one process can be running on any processor at any instant.

Process Control Block (PCB)

Each process is represented in the operating system by a process control block (PCB), also called a task control block.

Information associated with each process:

• Process state: The state may be new, ready running, waiting, halted, and so on

• Program counter: The counter indicates the address of the next instruction to be executed for this process.

• CPU registers

• CPU scheduling information: includes a process priority, pointers to scheduling queues, and any other scheduling parameters.

• Memory-management information

• Accounting information: includes the amount of CPU and real time used, time limits, account numbers, job or process numbers, and so on.

• I/O status information: includes the list of I/O devices allocated to the process, a list of open files, and so on.

Along with the program counter, this state information must be saved when an interrupt occurs, to allow the process to be continued correctly afterward

In brief, the PCB simply serves as the repository for any information that may
vary from process to process.

Threads

The process model discussed so far has implied that a process is a program
that performs a single thread of execution. For example, when a process is
running a word-processor program, a single thread of instructions is being
executed. This single thread of control allows the process to perform only one task at one time. The user cannot simultaneously type in characters and run the spell checker within the same process, for example. Many modern operating systems have extended the process concept to allow a process to have multiple threads of execution and thus to perform more than one task at a time. On a system that supports threads, the PCB is expanded to include information for each thread. Other changes throughout the system are also needed to support threads.

Process Scheduling

The objective of multiprogramming is to have some process running at all
times, to maximize CPU utilization. The objective of time sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running. To meet these objectives, the process scheduler selects an available process (possibly from a set of several available processes) for program execution on the CPU. For a single-processor system, there will never be more than one running process. If there are more processes, the rest will have to wait until the CPU is free and can be rescheduled.

Scheduling queues

• Job queue 
• set of all processes in the system
• As processes enter the system, they are put into a job queue

• Ready queue
• set of all processes residing in main memory ready and waiting to execute
• generally stored as a linked list. 
• header contains pointers to the first and final PCBs in the list. 
• Each PCB includes a pointer field that points to the next PCB in the ready queue.

• Device queues
• set of processes waiting for an I/O device

• Processes migrate among the various queues

• A common representation of process scheduling is a queueing diagram

Each rectangular box represents a queue. Two types of queues are present: the ready queue and a set of device queues. The circles represent the resources that serve the queues, and the arrows indicate the flow of processes in the system.

A new process is initially put in the ready queue. It waits there until it is
selected for execution, or is dispatched. Once the process is allocated the CPU and is executing, one of several events could occur:

• The process could issue an I/O request and then be placed in an I/O queue.

• The process could create a new subprocess and wait for the subprocess's termination.

• The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue.

In the first two cases, the process eventually switches from the waiting state
to the ready state and is then put back in the ready queue. A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated.


Schedulers

• Long-term scheduler (or job scheduler):
• selects which processes should be brought into the ready queue
• selects processes from this pool and loads them into memory for execution.

• Short-term scheduler (or CPU scheduler):
• selects which process should be executed next and allocates CPU

• Short-term scheduler is invoked very frequently (milliseconds)(must be fast)

• Long-term scheduler is invoked very infrequently (seconds,minutes) (may be slow)

• The long-term scheduler controls the degree of multiprogramming

• Processes can be described as either:
• I/O-bound process – spends more time doing I/O than computations, many short CPU bursts
• CPU-bound process – spends more time doing computations; few very long CPU bursts

• It is important that the long-term scheduler select a good process mix of I/O-bound and CPU-bound processes. 
• If all processes are I/O bound, the ready queue will almost always be empty (大部份都會卡在 waiting queue 等待 I/O), and the short-term scheduler will have little to do. 
• If all processes are CPU bound, the I/O waiting queue will almost always be empty ( 大多卡在 ready queue 等待 scheduler dispatch), devices will go unused, and again the system will be unbalanced. 
• The system with the best performance will thus have a combination of CPU-bound and I/O-bound processes.

Multiprogramming System(多元程式系統)

1. Def：允許系統 (or memory) 內存在多個 process (處理程序) 同時執行，透過 CPU scheduling 技術，當某個 process 取得 CPU 執行時，若因為某些事情發生 (eg. wait for I/O complete, resource not available, etc.) 而無法往下執行時，則 OS 可將 CPU 切換給其他 process 使用，如此一來，CPU 在各個 processes 切換，則CPU 總是 Busy ∴可以避免 CPU idle，提高 CPU utilization
2. Multiprogramming Degree：系統內存在執行的process數目，一般而言Multiprogramming Degree 越高，則 CPU utilization 越高(p.s. ch7 Thrashing除外)
3. 多個process同時執行，mode有兩種
1. Concurrent(並行)
2. Parallel(平行)

Time Sharing System(分時系統)

• Def：
  是 Multiprogramming 的一種，在CPU排班法則方面，其使用RR(Round-Robin)法則，【即 OS 規定一個 CPU time quantum，若process在取得CPU後，未能於quantum 內完成工作，則必須被迫放棄CPU，等待下一次輪迴。】對每個user皆是公平的
• 適用在 user interactive 且 response time (反應時間)要求較短的系統環境
• 透過resource sharing技術(eg. CPU scheduling, memory sharing, spooling達到 I/O Device共享) 使得每個 user 皆認為有專屬的系統存在。

Medium-term scheduler

• sometimes it can be advantageous to remove processes from memory (and from active contention for the CPU) and thus reduce the degree of multiprogramming. 
• Later, the process can be reintroduced into memory, and its execution can be continued where it left off. 
• This scheme is called swapping. The process is swapped out, and is later swapped in, by the medium-term scheduler. 
• Swapping may be necessary to improve the process mix or because a change in memory requirements has overcommitted available memory, requiring memory to be freed up.

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

• Time dependent on hardware support

Operations on Process

Process creation

A process may create several new processes, via a create-process system call, during the course of execution. The creating process is called a parent process, and the new processes are called the children of that process. Each of these new processes may in turn create other processes, forming a tree of processes.

• Generally, process identified and managed via a process identifier (pid)

• Resource sharing
• Parent and children share all resources
• Children share subset of parent’s resources
• Parent and child share no resources

• Execution
• Parent and children execute concurrently
• Parent waits until children terminate

• 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

Process Termination

• Process executes last statement and asks the operating system to delete it (exit)
• Output data from child to parent (via wait)
• Process’ resources are deallocated by operating system

• Parent may terminate execution of children processes (abort)
• Child has exceeded allocated resources
• Task assigned to child is no longer required
• If parent is exiting
• Some operating system do not allow child to continue if its parent terminates
• All children terminated - cascading termination

• that a parent needs to know the identities of its children. Thus, when one process creates a new process, the identity of the newly created process is passed to the parent.

• A parent may terminate the execution of one of its children for a variety of reasons, such as these:

• The child has exceeded its usage of some of the resources that it has been allocated. (To determine whether this has occurred, the parent must have a mechanism to inspect the state of its children.)

• The task assigned to the child is no longer required.

• The parent is exiting, and the operating system does not allow a child to continue if its parent terminates.

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:
• Since several users may be interested in the same
  piece of information (for instance, a shared file), we must provide an environment to allow concurrent access to such information.
• Computation speedup:
• If we want a particular task to run faster, we must break it into subtasks, each of which will be executing in parallel with the
  others. 
• Notice that such a speedup can be achieved only if the  computer has multiple processing elements (such as CPUs or I/O channels).
• Modularity
• We may want to construct the system in a modular fashion,
  dividing the system functions into separate processes or threads.
• Convenience
• Even an individual user may work on many tasks at the same time. 
• For instance, a user may be editing, printing, and compiling in
  parallel.

• Cooperating processes need interprocess communication (IPC)

• Two models of IPC
• Shared memory:
• 存取速度較快
• 沒有 event driven 的機制（例如 A 要拿 B 改過後的資料，但是不知他何時改完，就要一直 check 非常麻煩） 
• allows maximum speed and convenience of communication
• Message passing
• implement by system call (透過 OS 控制 (較慢))
• useful for exchanging smaller amounts of data, because no conflicts need be avoided
• easier to implement
• system calls are required only to establish shared-memory
  regions, once shared memory is established, all accesses are treated as routine
• 如果他不太需要頻繁的 IPC 時，使用 message passing will be better than share memory
   

Message passing v.s. Share memory

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

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

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) – message size fixed or variable
• receive(message)

• If P and Q wish to communicate, they need to:
• establish a communication link between them
• exchange messages via send/receive

• implementation of communication link
• physical (e.g., shared memory, hardware bus)
• logical (e.g., logical properties)

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

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

•  Operations
• create a new mailbox
• 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

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

Synchronization

• Message passing may be either blocking or non-blocking

• Blocking is considered synchronous
• Blocking send has the sender block until the message is received
• Blocking receive has the receiver block until a message is available

• Non-blocking is considered asynchronous
• Non-blocking send has the sender send the message and continue
• Non-blocking receive has the receiver receive a valid message or null

Buffering

• Queue of messages attached to the link; implemented in one of three ways
• Zero capacity – 0 messages:
• Sender must wait for receiver (rendezvous)
• Bounded capacity – finite length of n messages
• Sender must wait if link full
• Unbounded capacity – infinite length
• Sender never waits

Communications  in Client-Server Systems

• Sockets

• Remote Procedure Calls

• Remote Method Invocation (Java)

Sockets

• A socket is defined as an endpoint for communication

• Concatenation of IP address and port

• The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8

• Communication consists between a pair of sockets

Remote Procedure Calls

• Remote procedure call (RPC) abstracts procedure calls between processes on networked systems

• 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 peforms the procedure on the server

Remote Method Invocation

• Remote Method Invocation (RMI) is a Java mechanism similar to RPCs

• RMI allows a Java program on one machine to invoke a method on a remote object

Reference:  
Operating System Concepts 8th, by Silberschatz, Galvin, Gagne
Wikipedia 
http://www.csie.ntnu.edu.tw/~swanky/os/chap1.htm#TimeSharingSystem