Transcript pentest

COMP091 – Operating Systems 1
Processes
Process
•
A process is a program in execution
•
A process includes
–
Address space
–
Resource handles (file handles)
–
Program counter
–
Various data structures
Process in Memory
Process State
•
During its lifetime, a process changes state
frequently
•
OS creates and deletes processes
•
And handles state changes
Process State
•
States include:
–
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
dispatched
–
Terminated: The process has finished
execution
Process State Changes
PCB
•
Process Control Block
–
Process state
–
Program counter
–
CPU registers
–
CPU scheduling information
–
Memory-management information
–
Accounting information
–
I/O status information
Process Scheduling Queues
•
Job queue
–
•
Ready queue
–
•
Processes residing in main memory, ready to
execute
Device queues
–
•
All processes in the system
Processes waiting for an I/O device
Processes move from queue to queue
Schedulers
•
•
•
Long-term or job scheduler
–
Brings processes into the ready queue
–
Infrequent, need not be fast
Short-term or CPU scheduler
–
Selects which process should be executed next
–
Frequent
–
Must be fast
Medium term scheduler
–
Swaps processes in and out of memory
Swapping
Dispatcher
•
Dispatcher gives control of CPU to the process
selected by the short-term scheduler
•
This involves:
•
–
Switching context
–
Switching to user mode
–
Jumping to proper location to restart the program
Dispatch latency - time it takes for the
dispatcher to stop one process and start another
running
Context Switching
•
Switching processes requires saving state and
loading new state
–
–
Considered to be expensive overhead
Hardware support can reduce cost
•
I/O-bound processes change state to wait for I/O
•
CPU-bound processes change state when time
slice expires
Switching Processes
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
Algorithms
•
First-Come, First-Served
•
Shortest-Job-First
–
•
Based on predicted next CPU burst
Priority scheduling
–
Increase with age to prevent starvation
•
Round Robin with time quantum
•
Multilevel ready queue
–
Foreground RR (may be multiple with differing
quanta)
–
Background FCFS
Other Scheduling Types
•
Multi-processor scheduling
– Asymmetric multiprocessing - one
processor accesses the system data
structures, and is the scheduler
– Symmetric multiprocessing (SMP)
•
•
Each processor is self-scheduling,
Common ready queue, or each has its own private
queue
– Processor affinity
•
Process has affinity for processor on which it is
currently running
Other Scheduling Types
•
Thread scheduling
–
User threads = process-contention scope
–
Kernel threads = system-contention scope
Re-entrant
• Shared code, like shared operating system
routines, may be simultaneously executed by
multiple processes
• For this to be possible, code and data need to be
separate
– No global data
• Each process using the code follows a separate
and independent thread of execution through the
code
Threads
• When multiple processes each share a re-entrant
OS routine, they each have a thread of execution
through the same code
• Multi-threaded processes can establish multiple
separate threads of execution through their own
code
• The term “thread” is now used mainly to refer to
these Multi-threaded processes
Single and Multi-threaded Processes
Threads
•
•
•
Browser
–
One thread renders images
–
One thread retrieves data
A word processor
–
One thread reads keystrokes
–
One thread performs spell checking in the
background
A web server
–
One thread accepts requests
–
Each request gets separate thread
Threads are Sub-processes
•
No data segment or heap
•
Must exist within a process
•
Can be more than one thread in a process
•
Inexpensive creation
•
Inexpensive context switching
Benefits of Threads
•
Responsiveness
–
•
One thread is blocked, browser still responds
Resource Sharing
–
Share the same address space
–
Reduce overhead
Benefits of Threads

•
Economy
–
Creating a new process costs memory and
resources
–
Solaris is 30 times slower creating process than
thread
Utilization of MP Architectures
–
Threads can be executed in parallel on multiple
processors
–
Increase concurrency and throughput
Types of Threads
•
Kernel-supported threads
•
User-level threads
•
Hybrid approach implements both user-level
and kernel-supported threads
Kernel Threads
•
Supported by the Kernel
•
Every thread can run or block independently
•
One process may have several threads waiting
on different things
•
Downside of kernel threads: a bit expensive
–
•
Need to make a crossing into kernel mode to
schedule
Examples
–
Windows XP/2000 ..., Solaris, Linux,Tru64
UNIX, Mac OS X, Mach, OS/2
User Threads
•
Supported by user level library calls which
provide scheduler and thread package
•
May have several user threads per kernel thread
•
User threads may be scheduled non-premptively
relative to each other (only switch on yield())
User Threads
•
•
Advantages
–
Cheap, Fast
–
Threads do not need to call OS and cause
interrupts to kernel
Disadvantage:
–
•
If only one kernel thread, system call from any
user thread can block the entire task.
Examples
–
POSIX Pthreads, Win32 threads, Java threads
Process Creation
•
Processes ask OS to create “child” processes
•
Child can have its own child process
•
Result is a process tree
•
Child process may share some of parents
resources, or not
•
Child and parent can execute concurrently
–
Or parent may wait on child process
Termination
•
•
•
Process exits
–
Data returned to parent if waiting
–
Resources deallocated by OS
Parent can terminate (abort) child
–
No longer needed
–
Bad behavior
When parent exits child may be terminated also
Cooperating Processes
•
•
Independent process
–
Does not affect the execution of another process
–
Is not affected by the execution of another
process
Cooperating process can affect each other
–
Information sharing
–
Computation speed-up
–
Modularity
–
Convenience
Interprocess Communication (IPC)
•
Communication and synchronization
•
IPC facility provides operations:
•
–
Send(message) - message size fixed or variable
–
Receive(message)
To communicate
–
Establish a communication link
–
Exchange messages via send/receive
Shared or Central
Direct IPC
•
P and Q name each other explicitly:
–
Send (P, message)
–
Receive(Q, message)
•
Links are established for processes
•
Unique link is associated with one pair of
communicating processes
–
May be unidirectional
–
Usually bi-directional
Indirect IPC
•
Messages pass through mailboxes (ports)
•
Mailbox has unique id
•
Processes can communicate if they share a
mailbox
•
Link may be associated with many processes
•
Pair of processes may share several links
•
Link may be unidirectional or bi-directional
Synchronization
•
Message may be blocking or non-blocking
•
Blocking = synchronous
•
–
Blocking send has sender wait until message is
received
–
Blocking receive has receiver wait until message
is available
Non-blocking = asynchronous
–
Non-blocking send has sender send message and
continue
–
Non-blocking receive has receiver receive a valid
message or null
Size of Queue
•
Zero capacity
–
•
Finite length of n messages
–
•
Sender waits for receiver (rendezvous)
Sender must wait if link full
Unbounded capacity
–
Sender never waits
Client-Server with Sockets
•
Socket = an endpoint for communication
–
Like plugging a wire into a socket
•
Communication takes place between pairs of
sockets
•
Internet, Systems Network Architecture (SNA),
Unix domain sockets
•
Usually we are referring to Internet sockets
–
Use network protocol stack
–
Defined by an IP address and Port number
Client Server Model
• One server may communicate with many clients
– Separate threads or processes
• Clients only communicate with the server
• Server waits for client to send request then
sends response to client
• Client may wait or poll for response
– Communication is buffered
• May be on same or different systems
RPC
•
Remote Procedure Call
– Tries to look like local procedure call
•
Client calls server
•
Client has stub making remote procedure seem
local
•
Stub locates server and marshals the parameters
in RPC message
•
Server gets parameters from message and
performs service
RPC Messages
Unix Domain Sockets
• Function much like network (TCP/IP) sockets
– But on same machine only
• A type of inode in the file system
• Processes can open the socket to communicate
– Server has to do so first to receive
communication from client
• Stream (like tcp) or datagram (like udp)
• Can send file descriptor to unprivileged process
– To grant access to restricted file
Pipes
• Invented for unix in 1973
• Unidirectional, shared (not central)
• Can be buffered
– Linux channel capacity 65536 bytes
• Blocking send if buffer full
• Blocking receive
• Command line pipes ( process-a | process-b )
known as anonymous pipes
– Exist only as long as the processes exist
Pipeline
Named Pipes (unix)
• Persistent objects in the file system
• Sometimes called FIFOs
– First In First Out
• Two processes can open
– One to read, one to write
• Buffered (non-blocking send)
• Accessible to command line processes
– cat file > my_pipe
– gzip -9 -c < my_pipe > out.gz &
Name Pipes (Windows)
• Not part of the normal file system
• Not available to command line
• Named Pipes File System mounts pipe named foo at
\\.\pipe\foo
• Blocking or non-blocking
• Remote or local
– Remote not very efficient
• Temporary (non-persistent)
• Uni-directional or bi-directional
References
•
Short, but good intro
–
•
http://en.wikipedia.org/wiki/Process_%28comput
ing%29
Scheduling
–
http://en.wikipedia.org/wiki/Scheduling_%28com
puting%29