Transcript Implementing Processes, Threads, and Resources

Slide 6-1
6
Threads and
Scheduling
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Announcements
• Program Assignment #1 due Tuesday Feb.
15 at 11 am
– TA will explain parts b-d in recitation
• Read chapters 7 and 8
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-2
Round Robin Scheduling
Slide 6-3
• The ready queue is treated as a circular queue, and the
CPU scheduler rotates among the processes in the ready
queue, giving each a time slice, after which it is preempted
by a timer interrupt and the next process is started
– useful for time sharing multitasking systems - most widely used
scheduling algorithm
– combines FCFS and preemption
• simple and fair, though wait times can be long
– Fair: If there are n processes, each process gets 1/n of CPU
– Simple: Don’t need to know service times a priori
• A process can finish before its time slice is up. The
scheduler just selects the next process in the queue
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-4
Round Robin Scheduling
• Suppose we use a time slice of 4
Process
ms, and ignoring context switch
overhead
• Now P1 is time sliced out, and P2
and P3 are allowed to run sooner
P1
than FCFS
• average wait time is 5.66 ms
P2
P3
P1
0
P2
4
Copyright © 2004 Pearson Education, Inc.
P2
7
10
P1
P1
14
P1
18
CPU
Service
Time
(ms)
24
3
3
P1
22
Operating Systems: A Modern Perspective, Chapter 6
P1
26
30
Round Robin Scheduling
• Weighted Round Robin - each process is
given some number of time slices, not just
one per round
• this is a way to provide preferences or
priorities even with preemptive time slicing
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-5
Multi-level Queue Scheduling
Slide 6-6
• Partitions ready queue into several queues
– different processes have different needs, e.g.
foreground and background
– so don’t apply the same scheduling policy to
every process, e.g. foreground gets RR,
background gets FCFS
• Queues can be organized by priority, or
each given a percentage of CPU, or a hybrid
combination
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Multi-level Feedback Queues
Slide 6-7
• Allows processes to move between queues
• Criteria for movement could depend upon:
– age of a process: old processes move to higher priority
queues
– behavior of a process: could be CPU-bound processes
move down the hierarchy of queues, allowing
interactive and I/O-bound processes to move up
• give a time slice to each queue, with smaller time slices higher
up
• if a process doesn’t finish by its time slice, it is moved down to
the next lowest queue
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Signals
• Allows one process to interrupt another
process
• A message that notifies a process that some
event has occurred
• 30 types of signals on Linux systems
• Each signal corresponds to some kind of
system event
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-8
Signals
•
Prior to signals, low-level hardware exceptions are processed by kernel’s
exception handlers, and are not normally visible to user processes
– compare to:
• software “interrupts” - traps/system calls, process calls OS
• hardware interrupts - OS handles the interrupt, can resume a blocked process after I/O is
complete
•
•
•
•
•
Signals expose occurrences of such low-level exceptions to user processes
If a process attempts to divide by zero, kernel sends a SIGFPE signal (number
8)
If a process makes an illegal memory reference, the kernel sends it a
SIGSEGV signal (number 11)
If you type a ctrl-C, this sends a SIGINT to foreground process
A process can terminate another process by sending it a SIGKILL signal (#9)
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-9
Signals
• Kernel sends a signal to a destination process by
updating some state in the context of destination
process
• A destination process receives a signal when it is
forced by the kernel to react in some way to the
delivery of the signal:
– ignore signal
– terminate
– catch the signal by executing a user-level function
called the signal handler
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-10
Signals
Slide 6-11
• A signal that has been sent but not yet received is called a pending
signal
• At any point in time, there can be at most one pending signal of a
particular type
• a process can selectively block the receipt of certain signals
• when a signal is blocked, it can be delivered, but the resulting pending
signal will not be received until the process unblocks the signal
• A pending signal is received at most once
• For each process, the kernel maintains the set of pending signals in the
pending bit vector, and the set of blocked signals in the blocked
bit vector
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-12
Signals
Number
Name
Event
2
SIGINT
11
SIGSEGV
14
SIGALRM
29
SIGIO
Interrupt from
keyboard
invalid
memory ref
Timer signal
from alarm fn
I/O now
possible on
descriptor
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Signals
Slide 6-13
• Default action is to terminate a process
• Sending signals with kill function
– kill -9 PID
• A process can send SIGALRM signals to itself by calling
the alarm function
– alarm(T seconds) arranges for kernel to send a SIGALRM signal to
calling process in T seconds
– see code example
• #include<signal.h>
• uses signal function to install a signal handler function that is
called asynchronously, interrupting the infinite while loop in main,
whenever the process receives a SIGALRM signal
• When handler returns, control passes back to main, which picks up
where it was interrupted by the arrival of the signal
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Signals
Slide 6-14
• Receiving signals:
– when a kernel is returning from some exception handler, it checks
to see if there are any pending signals for a process before passing
control to process
– default action is typically termination
– signal(signum, handler) function used to change the
action associated with a signal
• if handler is SIG_IGN, then signals of type signum are ignored
• if handler is SIG_DFL, then revert to default action
• otherwise handler is user-defined function call the signal handler.
This installs or registers the signal handler.
– Invocation of the signal handler is called catching the signal
– Execution of signal handler is called handling the signal
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Signals
Slide 6-15
• When a process catches a signal of type k, the
handler installed for signal k is invoked with a
single integer argument set to k
• This argument allows the same handler function to
catch different types of signals
• When handler executes its return statement
(finishes), control usually passes back to the
instruction where the process was interrupted
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Signals
Slide 6-16
• Handling multiple signals
– choose to handle the lower number signals first
– pending signals are blocked,
• e.g. if a 2nd SIGINT is received while handling 1st SIGINT, the
2nd SIGINT becomes pending and won’t be received until after
the handler returns
– pending signals are not queued
• there can be at most one pending signal of type k
– system calls can be interrupted
• slow system calls that are interrupted may not resume in some
systems, and may return immediately with an error
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Signals
Slide 6-17
• Portable signal handling: sigaction() is a standard POSIX
API for signal handling
– allows users on Posix-compliant systems such as Linux and Solaris
to specify the signal-handling semantics they want, e.g. whether
sys call is aborted or restarted
• sigaction(signum, struct sigaction*act, struct sigaction
*oldact)
• each struct sigaction can define a handler, e.g.
action.sa_handler = handler;
• In part iv of PA #1, use sigaction() to define the handler,
e.g. reschedule
• Also need to set up the timer (use setitimer instead of
alarm). A SIGALRM is delivered when timer expires.
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6