Operating Systems: Process Concepts

Process Concept

• An operating system executes multiple programs as processes
• A process is a program in execution, progressing sequentially without parallel instruction execution
• The status of a process is indicated by the program counter's value and the processor's registers' content

Program States

• A program is a passive entity that is stored on a disk; process is active when loaded into memory
• Program execution starts via GUI or command line
• A single program can have multiple processes, especially with multiple users

Process In Memory

• Executable program code is in the text section
• Stack is used to store temporary data when a function is invoked
• Function parameters, return addresses, and local variables are stored in the stack
• Data section holds global variables
• Heap contains dynamically-allocated memory

Memory Layout of a C Program

• Global data section has initialized and uninitialized data
• A section is available for the argc and argv parameters passed to the main() function

Process States

• Process state changes during execution
• New is process creation
• Running is instruction execution
• Waiting is waiting for an event
• Ready is waiting to be assigned to a processor
• Terminated is finished execution

Process Control Block (PCB)

• Each process is represented by a PCB, also known as a task control block
• The process state can be new, ready, running, waiting, or halted
• The program counter indicates the address of the next instruction
• CPU registers vary based on computer architecture
• Accumulators, index registers, stack pointers, and general-purpose registers are types of CPU registers
• Condition-code information is included in CPU registers
• State data is saved during interrupts so that the process can resume correctly when rescheduled
• CPU scheduling data includes process priority, queue pointers, and scheduling parameters
• Memory management information depends on the OS's memory system
• Accounting data includes CPU time, real time used, time limits, account numbers, and process numbers
• Information contained in PCBs include I/O devices allocated to the process and open files

Process Representation in Linux

• The PCB is represented by the task struct in Linux
• This structure contains necessary process information
• Includes state, scheduling, memory management, open files, parent and child pointers, and sibling data
• Key fields include:
  • pid_t_pid: process identifier
  • long state: state of the process
  • unsigned int time_slice: scheduling information
  • struct task_struct *parent: indicates parent process
  • struct list_head children: indicates process's children
  • struct files_struct *files: lists open files
  • struct mm_struct *mm: indicates address space
• The long state field of task struct represents the state of the process
• In the Linux kernel, all active processes are maintained as a doubly linked list of task structs
• The kernel uses a pointer called current to denote the currently executing process

Process Scheduling

• A process scheduler selects available processes for CPU core execution
• Goal is to maximize CPU use and quickly switch processes
• Maintains scheduling queues
  • Ready queue contains processes in main memory, ready to execute
  • Wait queues contain processes waiting for an event, like I/O
• Processes move among various queues

Ready and Wait Queues

• Queues are generally stored as linked lists
• Ready-queue headers contain pointers to the first PCB
• Each PCB includes a pointer field to the next PCB

Process Scheduling Actions

• New processes are initially placed in the ready queue until selected for execution
• Executing processes may encounter certain events
  • Issue an I/O request and move to the I/O wait queue
  • Create a new child process and move to a wait queue while waiting for termination
  • Can be forced off the core due to interrupts or time slice expiration, returning to the ready queue
• Processes in waiting states return to the ready queue
• Processes continue until termination
• Upon termination, all queues are removed and its PCB and resources are deallocated

Context Switch

• Interrupts cause the OS to switch the CPU core to a kernel routine
• During an interrupt, the system saves the current process's context to restore it later
• PCB stores the context including CPU registers, process state, and memory management data
• Switching requires a state save and a state restore, known as a context switch

Context Switch Overhead

• Context switch time is pure overhead because no useful work is performed
• Switching speed depends on memory speed, register count for copying, and special instructions
• Typical speeds are several microseconds, and are reliant on hardware support
• Some processors provide multiple sets of registers, allowing a switch by changing the register set pointer
• Complex operating systems increase the amount of work done during context switches

Operations on Processes

• Operating systems functionalities include Process creation and Process Termination

Process Creation

• Parent processes create child processes, forming a process tree
• Processes identification are handled via a process identifier (pid)
• Resources share options
  • Parent and children share all resources
  • Children share a subset of parent's resources
  • Parent and child share no resources
• The execution options of a process are:
  • Parent and children execute concurrently
  • Parent waits until children terminate

Process Creation in UNIX

• Child duplicate of parent address space
• Child has a program loaded into it
• fork() system call creates new processes
• exec() system call replaces memory after fork() to load in new programs
• wait() is called by parent, and waits for the termination of the child

Process Termination

• Processes executes the last statement and ask the operating system to delete it using the exit() system call.
  • Status data is then sent to parent using Wait()
  • Processes’ resources are deallocated by operating system
• Parents can terminate processes that may have exceeded the allocated resources
• Termination occurs when task assigned to child is no longer required
• Processes terminates if parent is exiting

Cascading Termination

• Children are terminated if parent terminates
• Termination is initiated by the operating system
• Parent process may wait for termination of a child process
• Can call wait() and receive data and pid of the terminated process

Interprocess Communication

• Processes are either independent (cannot affect others) or cooperating (can affect others)
• Reasons for cooperating processes include Information sharing, Computation speedup, and Modularity
• Cooperating processes need interprocess communication (IPC)
• Two IPC Models exist
  • Shared Memory
  • Message Passing

Communication Models

• Shared memory allows processes to access a shared memory region to exchange data
• Message passing involves processes exchanging messages

Producer-Consumer Problem

• The consumer process and the producer process illustrates the paradigm for cooperating processes
• Producer process produces information consumed by the consumer process
• Two possible variations
  • Unbounded buffer places no practical limit on buffer size
    • Producer does not wait
    • Consumer does not wait if there is no buffer to consume
  • Bounded buffer assumes buffers are a fixed size
    • Producer wait if buffers are full
    • Consumer waits if there is no buffer to consume

Shared Memory IPC

• Processes share a memory area to communicate
• Communication is managed by the user processes and not the OS
• Synchronization is needed when accessing shared memory and is detailed in chapters 6 and 7

Message Passing IPC

• Processes communicate without using shared variables: involves send and receive calls
• send(message)- sends a message
• receive(message)- receives a message
• Message sizes are dynamic or of of a fixed size

Message Passing

• Communication requires processes to establish a communication link and exchange messages via send/receive

Communication Link

• Physical Methods
  • Shared memory, hardware bus and network
• Logical
  • Direct or indirect, synchronous or asynchronous, and Automatic or explicit buffering

Direct Communication

• Processes name each other explicitly
  • send(P,message) sends a message to process P
  • receive(Q,message) receives a message from process Q
• Communication link properties
  • Links are established automatically
  • Associated with one pair of process
  • One link between process
  • Links may be unidirectional or bi-directional

Indirect Communication

• Messages are directed and received from mailboxes (aka ports) with unique IDs
• Processes share a mailbox to communicate

Properties of Communication links

• A link is established only if processes share a common mailbox
• A link may be linked with many processes
• May share multiple communication links
• Can be unidirectional or bi-directional

Indirect Communication Continued

• The OS must Create a new mailbox (port), Send and receive messages through mailbox, and Delete a mailbox
• Primitives
  • send(A, message) sends to mailbox A
  • receive(A, message) receives from mailbox A

Mailbox Sharing 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 randomly select the receiver and notify sender of selection

Synchronization Types

• Blocking is the act of synchronous programming
  • Sender is block until message is received when Blocking send is in use
• Recipient is block until a message is available when Blocking Receive is in use
• Non-Blocking is the act of asynchronous programming
  • Sender will send a message and continue when Non-blocking send is in use
• Recipient receives valid or null message when Non Blocking Receive is in use

Different Combination Types

• A rendezvous (meeting) occurs when sender and recipient are blocked

Buffering

• Messages attach to the queue of links
• Queue of messages are zero capacity or infinite length
  • Sender must wait for receiver in zero capacity buffers
  • Sender must wait for receiver when buffer is full in bounded capacity buffers
  • Sender never waits in unbounded capacity Buffers

Pipes

• Conduit is used to allow processes to communicate
• The OS must handle: Unidirectional or Bidirectional communication, Two-way communication, Parent-child presence, Using them across networks
• Ordinary Pipes
  • Unable to access processes from the outside
  • Parents calls for pipes to create children
• Named Pipes:
  • Accessed with a parent-child relationship

Ordinary Pipes

• Allow communication in the standard producer-consumer model
• Treated as special files, accessed via regular read() and write() system calls in UNIX systems
• Producer writes to the write-end, and the consumer reads from the read-end of the pipe
• Communication is unidirectional
• Require a parent-child relationship between processes.
• These are called anonymous pipes in Windows

Named Pipes

• Named pipes are bidirectional
• Do not require a parent-child relationship between communicating programs
• Can be used by several operations
• Available through UNIX and Windows

Communication in Client Server Systems

• Sockets
• Remote Procedure Calls

Sockets

• Communication is done through sockets defined as an endpoint
• IP address concatenation and port, with the starting port being used to distinguish the network services
• Socket 161.25.19.8:1625 refers to post 1625 for host 161.25.19.8
• Communication requires a pair of sockets
• All ports below 1024 are well known and used for standardized services
• The loopback address 127.0.0.1 refers to to system running the process

Remote Procedure Calls (RPC)

• RPC abstracts and manages procedure calls between networked system processes
• Ports are used for service differentiation
• Stubs act as a client proxy for the server's procedure and marshal the parameters
• A server side stub then processes the incoming message by unpacking the marshall and initiating processes on the server