Transcript Operating Systems I: Chapter 4

Chapter 4: Processes
•
•
•
•
What is a process?
– Informally: A program in execution
 Analogies: A script Vs. a play. A recipe Vs. cooking.
– Formally: Any CPU activity
 batch system: jobs
 time-shared system: tasks
 user programs
 batch programs
 interactive programs, etc.
Assumption of Finite Progress:
– Process execution must progress in a sequential fashion
Execution: CPU Burst, [I/O Burst, CPU/Burst]*, CPU Burst with
interrupts due to hardware (timer, etc.)
Textbook uses the terms job and process almost interchangeably.
CEG 433/633 - Operating Systems I
4.1
Dr. T. Doom
Process Concept
•
A process includes:
– text
 The program code
– data section
 Explicitly declared memory/variables
– stack
 Implicitly declared memory
– activation record
– subroutine parameters
– local variables
– program counter
 Current instruction/point of execution
CEG 433/633 - Operating Systems I
4.2
Dr. T. Doom
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 process.
– terminated: The process has finished execution.
Processes are generally I/O-bound or CPU-bound
CEG 433/633 - Operating Systems I
4.3
Dr. T. Doom
Process Control Block (PCB)
Information associated with each process.
•
•
•
•
•
•
•
Process state
Program counter
CPU registers
CPU scheduling information
– priority
– pointers to scheduling queues
Memory-management information
– base/limit registers
Accounting information
I/O status information
– pointers to open file table
CEG 433/633 - Operating Systems I
4.4
Dr. T. Doom
CPU Switch From Process to Process
CEG 433/633 - Operating Systems I
4.5
Dr. T. Doom
Process Scheduling Queues
•
•
•
For a uniprocessor system, only one process can be active
As processes appear or change state, they are placed in 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.
The OS controls process migration between the various queues
– Some migration events are require no decision making
– Some migration events require decision making (scheduling)
CEG 433/633 - Operating Systems I
4.6
Dr. T. Doom
Representation of Process Scheduling
Long Term Scheduler
CEG 433/633 - Operating Systems I
Short Term Scheduler
4.7
Dr. T. Doom
Ready Queue And Various I/O Device Queues
•
Each process PCB is in exactly one queue
– Ready queue: Ready to run
– I/O Queue: Awaiting I/O completion (interrupt)
CEG 433/633 - Operating Systems I
4.8
Dr. T. Doom
Long-Term Schedulers
•
•
Long-term scheduler (or job scheduler) – selects which processes
should be brought into the ready queue
– Long-term scheduler is invoked only on process
creation/completion
– very infrequently called (seconds, minutes)  (may be slow)
– controls the degree of multiprogramming
 Number of “ready” processes
– controls the “process mix”
 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
Long-term schedulers are not generally used in interactive timesharing Operating Systems
– Commonly used in multiprogrammed batch systems
CEG 433/633 - Operating Systems I
4.9
Dr. T. Doom
Short-Term Schedulers
•
•
•
•
Short-term scheduler (or CPU scheduler) – selects which process
should be executed next and allocates CPU
– Dispatches from ready queue based on priority
– Process executes until it creates an event or an interrupt occurs.
 Events: I/O Request, fork a child, wait for an interrupt
 Interrupt: Timeslice expired, I/O Completion, etc.
– If the process creates the event, it is removed from the ready
queue and placed on an I/O or event wait queue
Context Switch - a change of active process
– save/load CPU Registers to/from PCB (overhead)
Short-term scheduler is invoked very frequently
– (milliseconds)  (must be fast)
Multi-programmed systems must provide short-term scheduling
CEG 433/633 - Operating Systems I
4.10
Dr. T. Doom
Medium-Term Schedulers
•
Medium-Term schedulers - control the process mix and degree of
multiprogramming for interactive time-shared systems
– All jobs are accepted (little or no long-term scheduling)
– Resource restrictions may not permit all jobs to be in memory
concurrently
 Partially executed processes may be swapped out to disk and
brought back into memory later.
CEG 433/633 - Operating Systems I
4.11
Dr. T. Doom
Process Creation
•
•
•
•
A process may create new processes via system call
– fork()
– The creating process is called the “parent”
– The created process is called the “child”
Parent process creates children processes, which, in turn create
other processes, forming a tree of processes
Parents may share resources with their children
– Option 1: Parent and children share all resources.
– Option 2: Children share subset of parent’s resources.
– Option 3: Parent and child share no resources.
Execution
– Option 1: Parent and children execute concurrently
– Option 2: Parent waits until children terminate
CEG 433/633 - Operating Systems I
4.12
Dr. T. Doom
Process Creation (Cont.)
•
UNIX example
– fork system call creates new process
– Created child process is a duplicate of parent
 Same memory image, nearly identical PCB
– The OS must provide some mechanism to allow modification
 exec family of system call used after a fork to overload the
process’ memory space with new text/program
 setuid() allows a change of “owner”
– Consider the login process
pid_t pid;
pid = fork();
if (pid<0) { fprintf(stderr,”Fork Error\n”; exit(1) }
if (pid = 0) { /* child block - execve(), etc. */ }
else { /* parent block */ - wait(), etc. */ }
/* Common Block */
CEG 433/633 - Operating Systems I
4.13
Dr. T. Doom
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
 Memory, open files, I/O buffers, etc.
Process can be terminated by interrupts or other events:
– Bus error, Seg Fault, etc.
Processes can be terminated by signals
– Parent may terminate child with signals (abort(),kill())
 Child has exceeded allocated resources
 Task assigned to child is no longer required
– Parent sends a termination signal to all childer on exit
 Operating system does not allow child to continue if its
parent terminates
 Cascading termination
CEG 433/633 - Operating Systems I
4.14
Dr. T. Doom
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
 files, memory, partial results, etc.
– Computation speed-up
 Parallel implementations
– Modularity
 Os system programs, daemons, etc.
– Convenience
 User-level multi-tasking: CNTL-Z, bg, &, fg, jobs
CEG 433/633 - Operating Systems I
4.15
Dr. T. Doom
Producer-Consumer Problem
•
•
•
Paradigm for cooperating processes, producer process produces
information that is consumed by a consumer process.
General model for processes that run concurrently and must share a
synchronized buffer.
– unbounded-buffer places no practical limit on the size of the buffer.
– bounded-buffer assumes that there is a fixed buffer size.
The buffer is provided by the OS through IPC or shared memory
Producer
Consumer
REPEAT
wait until buffer not full()
Produce item (takes time)
UNTIL FALSE
REPEAT
wait until buffer not empty()
Consume item (takes time)
UNTIL FALSE
CEG 433/633 - Operating Systems I
4.16
Dr. T. Doom
Threads
•
•
•
•
A process is an exact duplicate of its parent with its own (replicated)
memory space, stack space, and PCB.
– It is useful to allow the creation of tightly-coupled children that don’t
require unique copies of the code/data memory or OS resources
A thread (or lightweight process) is a basic unit of CPU utilization; it
consists of:
– program counter
– register set
– stack space
A thread shares with its peer threads its:
– code section
– data section
– operating-system resources
collectively know as a task.
A traditional or heavyweight process is equal to a task with one thread
CEG 433/633 - Operating Systems I
4.17
Dr. T. Doom
Why use Threads?
•
•
•
In a multiple threaded task, while one server thread is blocked and
waiting, a second thread in the same task can run.
– Threads provide a mechanism that allow sequential processes to
make blocking system calls while also achieving parallelism.
– Cooperation of multiple threads in same job confers higher
throughput and improved performance.
– Applications that require sharing a common buffer (i.e., producerconsumer) benefit from thread utilization.
– Possible immediate advantage to running code on multiprocessor system
Thread context switch is fast
– Only PC and GPRs must be restored
– No memory management necessary (no cache purge required)
BEWARE: There is no security between threads
– Debugging can be difficult
CEG 433/633 - Operating Systems I
4.18
Dr. T. Doom
Threads Support
•
•
•
Kernel-supported threads (Mach and OS/2): the OS is “aware” of
threads, each thread has a PCB and is scheduled by the OS
– Advantage:
 Multiple System Calls in operation concurently
– Disadvantage:
 Context switch is “slower” requires OS intervention
 Fairness issues for CPU time
User-level threads: supported above the kernel, via a set of library
calls at the user level (Project Andrew from CMU).
– Advantage:
 Fast context switch - no OS overhead
– Disadvantage:
 Kernel sees only one process, one system call halts all
threads.
Some operating systems offer a hybrid approach (Solaris 2).
CEG 433/633 - Operating Systems I
4.19
Dr. T. Doom
Threads Support in Solaris 2
•
•
•
Hybrid approach implements both user-level and kernel-supported
threads (Solaris 2). Solaris 2 is a version of UNIX with support for
threads at the kernel and user levels, symmetric multiprocessing,
and real-time scheduling.
Light Weight Process (LWP) – intermediate level between user-level
threads and kernel-level threads.
Resource needs of thread types:
– LWP: PCB with register data, accounting and memory
information,; switching between LWPs is relatively slow.
– User-level thread: only need stack and program counter; no
kernel involvement means fast switching. Kernel only sees the
LWPs that support user-level threads.
– Kernel thread: small data structure and a stack; thread
switching does not require changing memory access
information – relatively fast.
CEG 433/633 - Operating Systems I
4.20
Dr. T. Doom
Threads in Solaris 2
CEG 433/633 - Operating Systems I
4.21
Dr. T. Doom
Interprocess Communication (IPC)
•
•
IPC is covered in CEG434/634
Skip section 4.6
CEG 433/633 - Operating Systems I
4.22
Dr. T. Doom