CSE

  • Operating Systems

    UNIT - II

    Process Management

    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 includes:
    * Program counter
    * Stack
    * Data section
    Process in Memory

    Process State
    As a process executes, it changes stat *
    * 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
    Diagram of Process State

    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

    CPU Switch From Process to Process

    Process Scheduling Queues
    * 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
    * Processes migrate among the various queues
    Ready Queue And Various I/O Device Queues

    Representation of Process Scheduling

    Schedulers
    * Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue
    * Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU
    Addition of Medium Term Scheduling

    * 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
    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
    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
    * 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 Creation

    C Program Forking Separate Process

    int main()
    {
    pid_t pid;
    /* fork another process */
    pid = fork();
    if (pid < 0) { /* error occurred */
    fprintf(stderr, "Fork Failed");
    exit(-1);
    }
    else if (pid == 0) { /* child process */
    execlp("/bin/ls", "ls", NULL);
    }
    else { /* parent process */
    /* parent will wait for the child to complete */
    wait (NULL);
    printf ("Child Complete");
    exit(0);
    }
    }

    A tree of processes on a typical Solaris

    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
    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
    Communications Models

    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
    Bounded-Buffer – Shared-Memory Solution

    Shared data
    #define BUFFER_SIZE 10
    typedef struct {
    . . .
    } item;
    item buffer[BUFFER_SIZE];
    int in = 0;
    int out = 0;
    Solution is correct, but can only use BUFFER_SIZE-1 elements

    Bounded-Buffer – Producer

    while (true) {
    /* Produce an item */
    while (((in = (in + 1) % BUFFER SIZE count) == out)
    ; /* do nothing -- no free buffers */
    buffer[in] = item;
    in = (in + 1) % BUFFER SIZE;
    }

    Bounded Buffer – Consumer

    while (true) {
    while (in == out)
    ; // do nothing -- nothing to consume
    // remove an item from the buffer
    item = buffer[out];
    out = (out + 1) % BUFFER SIZE;
    return item;
    }

    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
    1. Zero capacity – 0 messages
    Sender must wait for receiver (rendezvous)
    2. Bounded capacity – finite length of n messages
    Sender must wait if link full
    3. Unbounded capacity – infinite length
    Sender never waits
    Examples of IPC Systems - POSIX
    * POSIX Shared Memory
    * Process first creates shared memory segment
    * Segment id = shmget(IPC PRIVATE, size, S IRUSR | S IWUSR);
    * Process wanting access to that shared memory must attach to it
    * Shared memory = (char *) shmat(id, NULL, 0);
    * Now the process could write to the shared memory
    * Printf(shared memory, "Writing to shared memory");
    * When done a process can detach the shared memory from its address space
    * Shmdt(shared memory);
    Examples of IPC Systems - Mach
    * Mach communication is message based
    * Even system calls are messages
    * Each task gets two mailboxes at creation- Kernel and Notify
    * Only three system calls needed for message transfer
    * Msg_send(), msg_receive(), msg_rpc()
    * Mailboxes needed for commuication, created via
    * Port_allocate()
    Examples of IPC Systems – Windows XP
    * Message-passing centric via 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
    Local Procedure Calls in Windows XP

    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
    Socket Communication

    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
    Execution of RPC

    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

    Marshalling Parameters

    Threads
    * To introduce the notion of a thread — a fundamental unit of CPU utilization that forms the basis of multithreaded computer systems
    * To discuss the APIs for the Pthreads, Win32, and Java thread libraries
    * To examine issues related to multithreaded programming
    Single and Multithreaded Processes

    Benefits
    * Responsiveness
    * Resource Sharing
    * Economy
    * Scalability
    Multicore Programming
    Multicore systems putting pressure on programmers, challenges include
    * Dividing activities
    * Balance
    * Data splitting
    * Data dependency
    * Testing and debugging
    Multithreaded Server Architecture

    Concurrent Execution on a Single-core System

    Parallel Execution on a Multicore System

    User Threads
    * Thread management done by user-level threads library
    * Three primary thread libraries:
    * POSIX Pthreads
    * Win32 threads
    * Java threads
    Kernel Threads
    Supported by the Kernel
    Examples:
    * Windows XP/2000
    * Solaris
    * Linux
    * Tru64 UNIX
    * Mac OS X
    Multithreading Models
    * Many-to-One
    * One-to-One
    * Many-to-Many
    Many-to-One
    Many user-level threads mapped to single kernel thread
    Examples:
    * Solaris Green Threads
    * GNU Portable Threads

    One-to-One
    Each user-level thread maps to kernel thread
    Examples
    * Windows NT/XP/2000
    * Linux
    * Solaris 9 and later

    Many-to-Many Model
    * Allows many user level threads to be mapped to many kernel threads
    * Allows the operating system to create a sufficient number of kernel threads
    * Solaris prior to version 9
    Windows NT/2000 with the ThreadFiber package

    Two-level Model
         Similar to M:M, except that it allows a user thread to be bound to kernel thread
    Examples:
    * IRIX
    * HP-UX
    * Tru64 UNIX
    * Solaris 8 and earlier

    Thread Libraries
    * Thread library provides programmer with API for creating and managing threads
    * Two primary ways of implementing
    * Library entirely in user space
    * Kernel-level library supported by the OS
    Pthreads
    * May be provided either as user-level or kernel-level
    * A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization
    * API specifies behavior of the thread library, implementation is up to development of the library
    * Common in UNIX operating systems (Solaris, Linux, Mac OS X)
    Java Threads
    * Java threads are managed by the JVM
    * Typically implemented using the threads model provided by underlying OS
    * Java threads may be created by:
    * Extending Thread class
    * Implementing the Runnable interface
    Threading Issues
    * Semantics of fork() and exec() system calls
    * Thread cancellation of target thread
    * Asynchronous or deferred
    * Signal handling
    * Thread pools
    * Thread-specific data
    * Scheduler activations
    Thread Cancellation
    * Terminating a thread before it has finished
    * Two general approaches:
    * Asynchronous cancellation terminates the target thread immediately
    * Deferred cancellation allows the target thread to periodically check if it should be cancelled
    Signal Handling
    * Signals are used in UNIX systems to notify a process that a particular event has occurred
    * A signal handler is used to process signals
    * 1. Signal is generated by particular event
    * 2. Signal is delivered to a process
    * 3. Signal is handled
    * Options:
    * Deliver the signal to the thread to which the signal applies
    * Deliver the signal to every thread in the process
    * Deliver the signal to certain threads in the process
    * Assign a specific threa to receive all signals for the process
    Thread Pools
    * Create a number of threads in a pool where they await work
    * Advantages:
    * Usually slightly faster to service a request with an existing thread than create a new thread
    * Allows the number of threads in the application(s) to be bound to the size of the pool
    Thread Specific Data
    * Allows each thread to have its own copy of data
    * Useful when you do not have control over the thread creation process (i.e., when using a thread pool)
    Scheduler Activations
    * Both M: M and Two-level models require communication to maintain the appropriate number of kernel threads allocated to the application
    * Scheduler activations provide upcalls - a communication mechanism from the kernel to the thread library
    * This communication allows an application to maintain the correct number kernel threads
    Windows XP Threads

    Implements the one-to-one mapping, kernel-level
    * Each thread contains
    * A thread id
    * Register set
    * Separate user and kernel stacks
    * Private data storage area
    * The register set, stacks, and private storage area are known as the context of the
    threads
    * The primary data structures of a thread include:
    * ETHREAD (executive thread block)
    * KTHREAD (kernel thread block)
    * TEB (thread environment block)
    Linux Threads

    * Linux refers to them as tasks rather than threads
    * Thread creation is done through clone() system call
    * Clone() allows a child task to share the address space of the parent task (process)
    CPU Scheduling
    * To introduce CPU scheduling, which is the basis for multiprogrammed operating systems
    * To describe various CPU-scheduling algorithms
    * To discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular system
    * Maximum CPU utilization obtained with multiprogramming
    * CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait
    * CPU burst distribution
    Histogram of CPU-burst Times

    Alternating Sequence of CPU And I/O Bursts

    CPU Scheduler
         Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them
    CPU scheduling decisions may take place when a process:
    1. Switches from running to waiting state
    2. Switches from running to ready state
    3. Switches from waiting to ready
    4. Terminates
    Scheduling under 1 and 4 is nonpreemptive
    All other scheduling is preemptive
    Dispatcher
    * Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
    * Switching context
    * Switching to user mode
    * Jumping to the proper location in the user program to restart that program
    * Dispatch latency – time it takes for the dispatcher to stop one process and start
    another running
    Scheduling Criteria
    * CPU utilization – keep the CPU as busy as possible
    * Throughput – # of processes that complete their execution per time unit
    * Turnaround time – amount of time to execute a particular process
    * Waiting time – amount of time a process has been waiting in the ready queue
    * Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
    * Max CPU utilization
    * Max throughput
    * Min turnaround time
    * Min waiting time
    * Min response time
    First-Come, First-Served (FCFS) Scheduling
                Process                Burst Time
                    P1                          24
                    P2                           3
                    P3                           3
    * Suppose that the processes arrive in the order: P1 , P2 , P3
    * The Gantt Chart for the schedule is:

    * Waiting time for P1 = 0; P2 = 24; P3 = 27
    * Average waiting time: (0 + 24 + 27)/3 = 17
    Suppose that the processes arrive in the order
    * P2 , P3 , P1
    * The Gantt chart for the schedule is:
    * Waiting time for P1 = 6; P2 = 0; P3 = 3
    * Average waiting time: (6 + 0 + 3)/3 = 3
    * Much better than previous case
    * Convoy effect short process behind long process

    Shortest-Job-First (SJF) Scheduling
    * Associate with each process the length of its next CPU burst. Use these lengths to
    schedule the process with the shortest time
    * SJF is optimal – gives minimum average waiting time for a given set of processes The difficulty is knowing

    SJF scheduling chart
    * Verage waiting time = (3 + 16 + 9 + 0) / 4 = 7 the length of the next CPU request


    Determining Length of Next CPU Burst
    * Can only estimate the length
    * Can be done by using the length of previous CPU bursts, using exponential averaging
    Prediction of the Length of the Next CPU Burst

    Examples of Exponential Averaging
    a =0
    tn+1 = tn
    Recent history does not count
    a =1
    tn+1 = a tn
    Only the actual last CPU burst counts
    If we expand the formula, we get:
    tn+1 = a tn+(1 - a)a tn -1 + …
    +(1 - a )j a tn -j + …
    +(1 - a )n +1 t0
    Since both a and (1 - a) are less than or equal to 1, each successive term has less weight than its predecessor
    Priority Scheduling
    * A priority number (integer) is associated with each process
    * The CPU is allocated to the process with the highest priority (smallest integer º highest priority)
    * Preemptive
    * Nonpreemptive
    * SJF is a priority scheduling where priority is the predicted next CPU burst time
    * Problem º Starvation – low priority processes may never execute
    * Solution º Aging – as time progresses increase the priority of the process
    Round Robin (RR)
    * Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
    * If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.
    * Performance
    * q large Þ FIFO
    * q small Þ q must be large with respect to context switch, otherwise overhead is too high
    Example of RR with Time Quantum = 4

                Process                Burst Time
                    P1                          24
                    P2                           3
                    P3                           3
    The Gantt chart is:

    Typically, higher average turnaround than SJF, but better response
    Time Quantum and Context Switch Time

    Turnaround Time Varies With The Time Quantum

    Multilevel Queue
    * Ready queue is partitioned into separate queues:
    foreground (interactive)
    background (batch)
    * Each queue has its own scheduling algorithm
    * Foreground – RR
    * Background – FCFS
    * Scheduling must be done between the queues
    * Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.
    * Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR 20% to background in FCFS
    Multilevel Queue Scheduling

    Multilevel Feedback Queue
    * A process can move between the various queues; aging can be implemented this way
    * Multilevel-feedback-queue scheduler defined by the following parameters:
    * Number of queues
    * Scheduling algorithms for each queue
    * Method used to determine when to upgrade a process
    * Method used to determine when to demote a process
        Method used to determine which queue a process will enter when that process needs service
    Example of Multilevel Feedback Queue
    Three queues:
    * Q0 – RR with time quantum 8 milliseconds
    * Q1 – RR time quantum 16 milliseconds
    * Q2 – FCFS
    * Scheduling
    * A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1.
    * At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2.
    Multilevel Feedback Queues

    Thread Scheduling
    * Distinction between user-level and kernel-level threads
    * Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP
    * Known as process-contention scope (PCS) since scheduling competition is within the process
    * Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system
    Pthread Scheduling
    * API allows specifying either PCS or SCS during thread creation
    * PTHREAD SCOPE PROCESS schedules threads using PCS scheduling
    * PTHREAD SCOPE SYSTEM schedules threads using SCS scheduling.
    Pthread Scheduling API

    #include <pthread.h>
    #include <stdio.h>
    #define NUM THREADS 5
    int main(int argc, char *argv[])
    {
    int i;
    pthread t tid[NUM THREADS];
    pthread attr t attr;
    /* get the default attributes */
    pthread attr init(&attr);
    /* set the scheduling algorithm to PROCESS or SYSTEM */
    pthread attr setscope(&attr, PTHREAD SCOPE SYSTEM);
    /* set the scheduling policy - FIFO, RT, or OTHER */
    pthread attr setschedpolicy(&attr, SCHED OTHER);
    /* create the threads */
    for (i = 0; i < NUM THREADS; i++)
    pthread create(&tid[i],&attr,runner,NULL);
    /* now join on each thread */
    for (i = 0; i < NUM THREADS; i++)
    pthread join(tid[i], NULL);
    }
    /* Each thread will begin control in this function */
    void *runner(void *param)
    {
    printf("I am a thread\n");
    pthread exit(0);
    }

    Multiple-Processor Scheduling
    * CPU scheduling more complex when multiple CPUs are available
    * Homogeneous processors within a multiprocessor
    * Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing
    * Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes
    * Processor affinity – process has affinity for processor on which it is currently running
    * Soft affinity
    * Hard affinity
    NUMA and CPU Scheduling

    Multicore Processors
    * Recent trend to place multiple processor cores on same physical chip
    * Faster and consume less power
    * Multiple threads per core also growing
    * Takes advantage of memory stall to make progress on another thread while memory retrieve happens
    Multithreaded Multicore System

    Operating System Examples
    * Solaris scheduling
    * Windows XP scheduling
    * Linux scheduling
    Solaris Dispatch Table

    Solaris Scheduling

    Windows XP Priorities

    Linux Scheduling
    * Constant order O(1) scheduling time
    * Two priority ranges: time-sharing and real-time
    * Real-time range from 0 to 99 and nice value from 100 to 140
    Priorities and Time-slice length

    List of Tasks Indexed According to Priorities

    Algorithm Evaluation
    * Deterministic modeling – takes a particular predetermined workload and defines the performance of each algorithm for that workload
    * Queueing models
    * Implementation
    Evaluation of CPU schedulers by Simulation

Industry      Interaction

Higher Education

Job Skills

Soft Skills

Comm. English

Mock Test

E-learning