Process Concept
• An operating system executes a variety of programs:
- 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 includes:
- program counter
- Stack
- data section
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 (CPU)
- terminated: The process has finished execution
• The state of a process is defined in part by the current activity of that process.
• It is important to realize that only one process can be running on any processor at any instant.
• Many processes may be ready and waiting states.
Process Control Block (PCB)
• Each process is represented in the operating system by a process control block (PCB).
• Information associated with each process
- Process state
- Program counter
- CPU registers
- CPU scheduling information
- Memory-management information
- Accounting information
- I/O status information
To be exact……
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 for program execution on the CPU
• For a single-processor system, there will never be more than one running process.
- The rest will have to wait until the CPU is free and can be rescgeduled
Process Scheduling Queues
• Processes migrate among the various queues for process scheduling.
• Job queue – set of all processes in the system
• Ready queue – set of all processes residing in main memory, ready and waiting to execute
• Device queues – set of processes waiting for an I/O device
- Each device has it’s own device queue.
Process Scheduling
• A new process is initially put in the ready queue and waits there until it is selected for execution. (dispatched)
• Once the process is allocated the CPU and is executing until one of the following events occur:
- The process issues an I/O request
- The process creates a new child process
- The process waits for an interrupt (timer event)
- The time slice assigned is expired
Schedulers
• is a component of OS the role of which is to select a process for execution among a set of processes in various queues
• In a batch and multiprogramming system
- More processes are submitted than can be executed immediately.
- These processes are spooled to a disk, where they are kept for later execution
- Long-term scheduler (or job scheduler) – selects which processes should be brought from disk into the ready queue
- Short-term scheduler (or CPU scheduler) – selects which process should be executed next from the ready queue and allocates CPU• Long-term scheduler is invoked very infrequently (seconds, minutes) => (may be slow)
• Short-term scheduler is invoked very frequently (milliseconds) =>(must be fast)
• The long-term scheduler controls the degree of multiprogramming
- The number of processes in memory
- The degree of multiprogramming must be stable
• The rate of process creation == the rate of process termination - The long term scheduler may need to be invoked only when a process leaves the system.
• It is important that the long-term scheduler make a careful selection.
• Processes can be described as either:
- I/O-bound process – spends more time doing I/O than computations, many short CPU bursts (ex, find)
- CPU-bound process – spends more time doing computations; few very long CPU bursts (ex. Sort)
• 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
- If all processes are CPU bound, the I/O waiting queue will almost always be empty
• In time-sharing system such as UNIX and Windows
- No long-term scheduler is used.
- simply put every new process in memory for the short-term scheduler.
- The stability of these systems depends on a physical limitation or on the self-adjusting nature of human users.
• In time-sharing system, a medium-term scheduler is used.
- It sometimes can be advantageous to remove processes from memory and thus reduce the degree of multiprogramming.
- Later, the process can be reintroduced into memory, and its execution can be continued.
- We call it swapping
Context Switch
• is a task of switching CPU to another process
- which requires performing a state saving of the current process and a state restoring of a different process
• 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
- When an interrupt occurs, the OS saves the context of current running process in its PCB.
• Context-switch time is overhead; the system does no useful work while switching
- Time dependent on memory speed, number of registers, etc.
- Typical speeds are a few millisecond.
• 멀티프로세스 환경이고 cpu가 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선순위의 프로세스가 실행되어야 하는 상황 발생
• -> 기존 프로세스 상태 or 레지스터 값(context)를 저장. cpu가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 or 레지스터 값(context)를 교체하는 과정
• context는 CPU가 프로세스를 실행하기 위한 해당 프로세스의 정보. PCB에 저장됨.
Operations of Processes
• The Processes in most system can execute concurrently, they may be created and deleted dynamically.
• Process Creation Process Termination
Process Creation
• Parent process creates children processes, which, in turn create other processes, forming a tree of processes
- via create-process system call
• Three possibilities in terms of resource sharing
- Parent and children share all resources
- Children share subset of parent’s resources
- Parent and child share no resources, child receives resources from OS directly.
• Two possibilities in terms of execution
- Parent and children execute concurrently
- Parent waits until children terminate
• Two possibilities in terms of address space
- Child is a duplicate of parent;
• child has same program and data as the 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
fork() & exec()
• A new process is created by the fork() system call
• The new process consists of a copy of the address space of the original process
• Both processes (parent & child) continue execution at the instruction after the fork().
• The return code for the fork() is zero for the child process, whereas the (nonzero) pid of the child process is returned to the parent
• The exec() loads a binary file into memory, destroys the memory image of the program, and starts its execution.
Process Termination
• Process executes last statement and asks the operating system to delete it (exit)
- Status value returned from child to parent (via wait)
- Process’ resources are de-allocated by operating system
• Memory, open files, I/O buffers
• Parent may terminate execution of children processes (abort) with various reason
- 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
Cooperating Processes
• The Processes executing concurrently in the operating system may be either
independent processes or cooperating processes
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; parallelism may speed up the computation
- Modularity; dividing the system function into separate process
- Convenience; concurrently running environment.
InterProcess Communication
• Cooperating processes require an InterProcess Communication (IPC) mechanism that will allow them to exchange data and information
Interprocess Communication (IPC)
- is a mechanism for processes to communicate and to synchronize their actions
• Two fundamental models
- Shared memory
- Message passing
• In the shared-memory model, a region of memory that is shared by cooperating process is established.
- IPC is performed by reading and writing data to the shared region
• In the message-passing model, IPC takes place by means of messages exchanged between the cooperating processes.
- IPC is performed by sending and receiving data
• Many system implements both.
Communications Models
(a) message-passing mechanism (b) shared-memory mechanism
Interprocess Communication (IPC)
• Message-passing
- is useful for exchanging smaller amounts of data, due to no conflicts
- is easier to implement than shared memory
• Shared-memory
- allows maximum speed and convenience of communication
- It can be done at memory speeds
- is faster than message passing
Shared-Memory System
• Creation of shared-memory
- A process creates a shared-memory segment in the address space of the process.
- Other processes attach it to their address space
• Termination of shared-memory
- requires the agreement from all processes to remove it
• Exchange of information
- By reading and writing data in the shared areas
• The form of the data and the location are determined by these processes, not OS. Processes are responsible for synchronized access.
Producer-Consumer Problem
• Paradigm for cooperating processes,
- producer process produces information that is consumed by a consumer process
• Example
- compiler produces assembly code, consumed by assembler
- Assembler produces object modules, consumed by loader
• Producer-consumer problem can be solved by shared- memory
- Producer and consumer processes runs concurrently
- They communicate to each other via shared-memory (buffer)
- Producer produces an item and store it to the buffer
- Consumer consumes an item from the buffer
- The producer and consumer must be synchronized, so that
the consumer consumes an item only when available.
• Two types of buffer can be used.
- unbounded-buffer places no practical limit on the size of the buffer
- bounded-buffer assumes that there is a fixed buffer size
• In unbounded-buffer
- The consumer may have to wait for new items
- The producer can always produce new items
• In bounded-buffer
- The consumer must wait if the buffer is empty
- The producer must wait if the buffer is full
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 direct communication link
-
Links are established automatically, processes need to know only each other’s identity
-
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
-
Two addressing mode
- Symmetry in addressing
• Both sender and receiver must name the other to communicate
- Asymmetry in addressing
• Only the sender names the recipient, the recipient is not required to name the sender.- send (P, message) – send a message to process P - receive (id, message) – receive a message from any process, id is set to the name of the sender with which communication has taken place -
Disadvantages in direct communication (symmetry & asymmetry)
- Limited modularity of the resulting process definition
- Changing the id of a process may necessitate examining all other process definitions.
Indirect Communication
• Messages are directed and received from mailboxes (also referred to as ports)
- Mailbox(EMAIL) is an object into which messages can be placed and from which messages can be removed.
- Each mailbox has a unique id
- Processes can communicate only if they share a mailbox
• Properties of indirect 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
Synchronization
• Message passing may be either blocking or non-blocking
• Blocking is considered synchronous (=>lining up, giving them order to execute)
- Blocking send has the sender blocked until the message is received
- Blocking receive has the receiver blocked 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
• When both send() and receive() are blocking, we have a rendezvous between sender and receiver
• For the producer and consumer problem.
- Blocking method is desirable
- Use blocking send() and blocking receive() primitives.
• The producer
- merely invokes the blocking send() call and
- waits until the message is delivered to either the receiver or the mailbox.
• When the consumer invokes receive(),
- it blocks until a message is available
