5CCS12OSC – Operating Systems and
Concurrency
Processes and CPU Scheduling
Dr Sahar Al-Sudani Spring, 2020
1/8/2020
Objectives
• To introduce the notion of a process — a program in execution, which forms the basis of all computation
• To describe the various features of processes, including scheduling, creation and termination, and communication
Process Concept (Cont.)
Program is passive entity stored on disk (executable file), process is active Program becomes process when executable file loaded into memory
Execution of program started via GUI mouse clicks, command line entry of its name, etc One program can be several processes
Consider multiple users executing the same program
Process in Memory
• Stack: Contains temporary data: function parameters, return addresses, local variables.
• Heap: Dynamically allocated memory (e.g. Objects created using new): the memory the process can use.
• Data: Global Variables (incl. e.g. Java static variables).
• Text: Code (compiled binary) for the program the process is executing.
N.B. Register values and programme counters are stored either in the registers (when the process is executing); or in the PCB (when it is not).
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 processor terminated: The process has finished execution
Process Control Block (PCB)
Information associated with each process
(also called task control block)
Process state – running, waiting, etc
Program counter – location of instruction to next execute CPU registers – contents of all process-centric registers CPU scheduling information- priorities, scheduling queue pointers
Memory-management information – memory allocated to the process
Accounting information – CPU used, clock time elapsed since start, time limits
I/O status information – I/O devices allocated to process, list of open files
CPU Switch From Process to Process
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
The more complex the OS and the PCBthe longer the context switch
Time dependent on hardware support
Some hardware provides multiple sets of registers per CPUmultiple contexts loaded at once
Ready Queue And Various I/O Device Queues
Maximize CPU use, quickly switch processes onto CPU for time sharing
Process scheduler selects among available processes for next execution on CPU
Maintains scheduling queues of processes
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
Representation of Process Scheduling
Queueing diagram represents queues, resources, flows
Schedulers
Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU Sometimes the only scheduler in a system
Short-term scheduler is invoked frequently (milliseconds) (must be fast)
Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue Long-term scheduler is invoked 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 Long-term scheduler strives for good process mix
Basic Concepts
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 followed by I/O burst CPU burst distribution is of main concern
CPU Scheduler
Short-term scheduler selects from among the processes in ready queue, and allocates the CPU to one of them
Queue may be ordered in various ways
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
Consider access to shared data
Consider preemption while in kernel mode
Consider interrupts occurring during crucial OS activities
Criteria for Scheduling Algorithm Performance
• CPU Utilisation: the percentage of the time the CPU is executing a process.
• Waiting time: the total time a process spends waiting in the ready queue.
• Turnaround time: the time between arrival of a process in the ready queue and it completing execution.
• Response time: the time between arrival of the process and the production of the first response (depends on how long a process takes to make a response, it may not need to complete in order to do so).
• Throughput: the number of processes completed per unit time (clearly affected by process duration).
• We can also ask for average (mean) waiting/turnaround/response time or total (sum) waiting/turnaround/response time, or maximum/minimum waiting/turnaround/response time for a set of processes.
First Come First Serve Schduling (FCFS)
Process
Arrival
Duration
P1
4
5
P2
0
3
P3
2
4
P4
12
2
P2
P3
P1
P4
0 3 7 1214
Average Waiting Time = (0 + (3 – 2) + (7 – 4) + (12 – 12) ) / 4 = 1 Average Turnaround Time = (3 + (7 – 2) + (12 – 4) + (14 – 12)) / 4 = 4.5 Throughput = 4 / 14 = 0.29
FCFS: Order Sensitivity
Process
Arrival
Duration
P1
0
5
P2
4
3
P3
2
4
P4
12
2
P1
P3
P2
P4
0 5 91214
Average Waiting Time = (0 + (5 – 2) + (9 – 4) + (12 – 12) ) / 4 = 2 Average Turnaround Time = (5 + (9 – 2) + (12 – 4) + (14 – 12)) / 4 = 5.5 Throughput = 4 / 14 = 0.29
FCFS: Advantages/Disadvantages
+ Simple algorithm;
+ Only one context switch per process.
− Average waiting time typically poor.
− Average waiting time highly variable: dependent on order in
which processes arrive.
− CPU Bound processes can hog the CPU: imagine a system with one CPU bound process and many I/O bound processes.
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 the length of the next CPU request
• Could ask the user
Shortest Job First (SJF)
Remember: Jobs can only be scheduled when they have arrived!
Process
Arrival
Duration
P1
0
5
P2
0
4
P3
1
2
P4
10
3
P2
P3
P1
P4
0 4 6 11 14 Average Waiting Time = (0 + (4 – 1) + (6 – 0) + (11 – 10) ) / 4 = 2.5 Average Turnaround Time = (4 + (6 – 1) + (11 – 0) + (14 – 10)) / 4 = 6 Throughput = 4 / 14 = 0.29
BREAK TIME
10 minutes Break
1/8/2020
Pre-emptive Scheduling
• Non-pre-emptive scheduling: The process that is executing on the CPU continues until it has finished its CPU burst.
• Pre-emptive scheduling: If another process arrives the process currently running can be stopped, and the new process started.
• Scheduling decisions occur when a new process is added to the ready queue (the arcs marked P below can cause new scheduling decisions).
PP P
N
N
Pre-emptive Shortest Job First Shortest Remaining Time First (SRTF)
If a new job arrives that is shorter than the remaining time of the current job then execute it.
Process
Arrival
Duration
P1
0
5
P2
0
4
P3
1
2
P4
10
3
P2
P3
P2
P1
P4
0136 1114
Average Waiting Time = (6 + 2 + 0 + 1 ) / 4 = 2.25 (vs 3.5 for FCFS)
Average Turnaround Time = ((11 – 0) + (6 – 0) + (3 – 1) + (14 – 10) / 4 = 5.75
SJF: Advantages/Disadvantages
+ Short processes do not have to wait for long processes to complete before executing (especially if pre-emptive scheduling is used). That is, CPU Bound processes cannot hog the CPU.
+ Maximises throughput (for this imagine a queue where processes continually arrive).
+ Average waiting time is smaller (for the same set of processes) since no process waits for
the longest to complete.
− Risk of starvation for long processes; or alternatively long waiting times.
− Multiple context switches for each process if pre-emptive.
− Can we reliably estimate process duration before execution?
− Overheads in inserting processes in a sorted queue.
Activity-1 Duration (10) minutes
1/8/2020
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 priority scheduling where priority is the inverse of predicted next CPU burst time
Problem Starvation – low priority processes may never execute Solution Aging – as time progresses increase the priority of the process
Non-pre-emptive Priority Scheduling
Add jobs to at the appropriate position in the ready queue according to their priority.
Process
Arrival
Duration
Priority
P1
2
2
3
P2
0
4
4
P3
0
3
0
P4
6
5
2
P3
P1
P2
P4
0 3 5 9 14 Average Waiting Time = (1 + 5 + 0 + 3 ) / 4 = 2.25
Average Turnaround Time = ((5 – 2) + (9 – 0) + (3 – 0) + (14 – 6) / 4 = 5.75
Pre-emptive Priority Scheduling
If a process arrives with higher priority than the one currently executing, execute it; otherwise insert it in the appropriate position in the ready queue according to priority.
Process
Arrival
Duration
Priority
P1
2
2
7
P2
0
4
14
P3
0
3
0
P4
6
5
3
P3
P1
P2
P4
P2
0356 1114 Average Waiting Time = (1 + 10 + 0 + 0 ) / 4 = 2.75
(notice individual waiting time vs priority)
Average Turnaround Time = ((5 – 2) + (14 – 0) + (3 – 0) + (11 – 6) / 4 = 6.25
Priority Scheduling: Advantages/Disadvantages
+ Short waiting times for high priority processes (e.g. interactive user programs).
+ Users (or admin) have some control over the scheduler.
+ Deadlines can be met by giving processes high priority.
− Risk of starvation for low priority processes; or alternatively long waiting times.
+ Can alleviate starvation risk by using an aging scheme: gradually increase the priority of a process over time.
− Multiple context switches for each process if pre-emptive.
− Overheads in inserting processes in a sorted queue.
Round Robin Scheduling (RR)
• Features a time quantum: the length of time each process is allowed to run for (usually 10-100ms);
• When a process has run for this length of time it is pre-empted and another process from the ready queue can be scheduled.
• Performance varies according to q:
– If q is large round robin tends to First Come First Served;
– If q is small, context switching overheads become significant.
– A heuristic for efficiency: a quantum that is longer than 80% of CPU bursts should be chosen.
Round Robin (q = 5)
Take the first job from the queue (FCFS) and schedule it to run for q units. Then place it on the back of the queue. New processes join the back of the queue on arrival.
Process
P1
P2
P3
P4
Arrival
4
0
17
2
Duration
4
10
17
18
P2
P4
P1
P2
P4
P3
P4
P3
P4
P3
P3
0 5 1014 19 24 29 34 3942 4749 Average Waiting Time = (6 + 9 + 15 + 22) / 4 = 13
Average Turnaround Time = ((14 – 4) + (19 – 0) + (49 – 17) + (42 – 2) / 4 = 25.25
Round Robin: Advantages/Disadvantages
+ No Starvation.
+ Each process must wait no more than (n-1) * q time units
before beginning execution.
+ Fair sharing of CPU between processes.
− Poor average response time
− Waiting time depends on number of processes, rather than
priority.
− Particularly large number of context switches for each process so large overhead;
− Hard to meet deadlines because waiting times are generally high.
Activity-2 5- minutes Discussion with class mate.
Q1. Given n processes to be scheduled on one processor, how many possible different schedules are there?
Q2. What (if any) relation holds between Priority and SJF algorithms?
a. The SJF is slower than Priority Algorithm for the same set of processes.
b. Both are non-preemptive algorithms
c. The SJF has the highest Priority
d. No relation between the two algorithms
1/8/2020
Multilevel Queue
Ready queue is partitioned into separate queues, eg:
foreground (interactive)
background (batch)
Process permanently in a given queue
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 Examples
Scenario 1:
• • •
Each queue has absolute priority over lower priority queues
e.g. no process in the batch queue can run unless the queues above it are empty
This can result in starvation for the processes in the lower priority queues
Scenario 2:
• Time slice amongst queues;
• Each gets a fixed percentage of CPU time.
• e.g.
– 40% System
– 30% Interactive
– 20% Interactive Editing
– 6% Batch
– 4% Student
• Again each queue can use its own scheduling algorithm.
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
Activity-3 5 minutes
1/8/2020
Multitasking in Mobile Systems
Some mobile systems (e.g., early version of iOS) allow only one process to run, others suspended
Due to screen real estate, user interface limits iOS provides for a
Single foreground process- controlled via user interface
Multiple background processes– in memory, running, but not on the display, and with limits
Limits include single, short task, receiving notification of events, specific long-running tasks like audio playback
Android runs foreground and background, with fewer limits
Background process uses a service to perform tasks
Service can keep running even if background process is suspended Service has no user interface, small memory use
Multi-Processor Scheduling
• Multiple CPUs can be used to share load
– Problem becomes more complex if the CPUs have different capabilities (e.g.
certain jobs can only run on some CPUs).
– Here we focus on CPUs with the same capabilities.
• Every process can run on any CPU.
• TwoVariants:
– Asymmetric multiprocessing (one processor controls all scheduling); – Symmetric multi-processing (each processor schedules itself).
Asymmetric vs Symmetric
• Asymmetric multiprocessing (ASMP)
– One processor makes all scheduling decisions, and handles I/O processing, and
other system activities
– The other processors execute user code only.
– The need for data sharing is reduced because only one processor handles all system
processes.
• Symmetric multiprocessing (SMP)
– Each processor does its own scheduling.
– –
–
•
• –
There may be a single ready queue, or a queue for each processor.
Whichever is used, each processor selects a process to execute from the ready queue.
Efficient CPU use (high utilisation) requires load balancing for even distribution, two approaches:
Push migration: a specific process regularly checks the load on each processor and redistributes waiting processes.
Pull migration: an idle processor pulls a waiting job from the queue of a busy processor All major modern operating systems support SMP.
Hyperthreading
• Multiprocessing uses multiple (physical) CPUs to run processes in parallel; Hyperthreading (AKA Symmetric Multithreading) allows the same thing but using multiple logical processors.
• Logical processors:
– Share the hardware of the CPU: cache, busses etc.
– Are responsible for their own interrupt handling.
• Appears as 2 CPUs instead of one: can do Floating point computations for one process, whilst doing Arithmetical/Logical computations for another.
ID
FPU
ALU
ID
Logical CPUs
Physical CPU
BREAK TIME
10 minutes Break
1/8/2020
Scheduling in Windows (XP)
• Pre-emptive priority scheduling, with time quanta. Priority levels are integers from 0 to 31 (unusually: higher number = higher priority).
• When a process is selected to run (highest priority ready thread) it executes, until either:
– Its time quantum is used;
– another higher priority process arrives; – It terminates;
– It makes a system call e.g. I/O request;
• A queue is maintained for each priority level and a process is selected from the queue with the highest priority. If no thread is available for execution a special “system idle process” is executed.
• Pre-emption by higher priority threads ensures that real-time threads can access the CPU when required.
Priorities in Windows (XP)
• Processes start at the base priority of their class (inherited from parent);
• Priorities (excl. real time) are variable within their class.
– When a process completes its time quantum its priority is lowered (never below the base priority for its class). Prevents CPU bound threads from hogging CPU.
– When a process completes waiting its priority is boosted (e.g. Keyboard I/O large boost; Disk I/O smaller boost). Gives good response for interactive processes.
• Gives good I/O device utilisation; whilst allowing CPU bound processes to use spare CPU cycles.
• Interactive processes being run by the user typically all boosted: generally given a quantum 3 times as long.
Win32 API Priority Class
Priority Within Class
Scheduling in Linux (2.5)
• Linux uses a pre-emptive priority-based algorithm with two separate priority ranges:
– A range from 0 to 99
– A nice real-time value ranging from 100 to 140
• These two ranges map into a global priority scheme: lower values => higher priority.
• Higher priority tasks receive longer time quanta than lower priority ones.
Linux (2.5) Scheduling Algorithm
• A runnable task is eligible for execution if it has time remaining in its quantum;
• When a task has exhausted its quantum it is expired and not eligible for execution
again until all other tasks have also exhausted their time quanta
• Because of its support for SMP, each processor maintains its own runqueue and schedules itself independently
• The scheduler selects the eligible task with the highest priority for execution;
• When all tasks have exhausted their time slices all tasks become eligible for execution.
Priorities in Linux (2.5)
• Real time processes have static priorities;
• All other tasks have dynamic priorities, based on their nice value and the number 5.
– Interactivity of a task is determined by the time spent sleeping waiting for I/O;
– I/O bound processes will sleep for more time than CPU bound processes.
– For highly interactive processes (lots of I/O) 5 will be subtracted from their priority, thus it is increased;
– For processes with very little interaction (CPU bound) 5 is added to their priority and thus it is lowered.
• Priority is recomputed on expiration of the time quantum.
Operations on Processes: 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 options:
• Parent and children share all resources
• Children share subset of parent’s resources
• Parent and child share no resources
Execution options:
• Parent and children execute concurrently
• Parent waits until children terminate
Address space options
• Child process is a duplicate of the parent process (same program and data)
• Child process has a new program loaded into it
Process Creation in Unix
• fork() system call creates a new process
• exec() system call used after a fork() to replace the memory space of the process
with a new program
• Can use these commands directly in C langauge.
Process Termination
• Process executes last statement and asks the operating system to terminate it (exit)
– Exit status value from child is received by the parent (via wait()) • Indicates success or abnormal exit.
– Process’ resources are deallocated by operating system
• Parent may terminate execution of child processes (kill()) – If a child has exceeded allocated resources;
– If the task assigned to child is no longer required;
– At will.
• If parent is exiting
– Some operating system do not allow child to continue if its parent
terminates;
– All children terminated – cascading termination.
1/8/2020
Mock QUIZ
Contact details/for more information
Sahar.al-sudani@kcl.ac.uk
Thanks for you Attention !
© 2020 King’s College London. All rights reserved
5CCS12OSC – Operating Systems and
Concurrency
Threads and Critical Section Problem
Dr Sahar Al-Sudani
Spring, 2020
1/16/2020
Lecture Topics
• Introduction to Threads;
• Basic Threading in Java;
• The Critical Section Problem;
• Solutions to the Critical Section Problem.
Slides based on Chapter 4 of “Operating Systems Concepts” Silberschatz, Galvin and Gagne and Chapters 3 and 4 of “Principles of Concurrent and Distributed Programming” M. Ben-Ari
With additional Java Examples
What is a Thread?
A thread, is a lightweight process, is a basic unit of CPU utilisation.
It comprises a thread ID, a program counter, a register set, and a stack.
It shares with other threads belonging to the same process its code section, data section, and other operating-system resources, such as open files and signals.
A traditional process has a single thread of control.
If the process has multiple threads of control, it can do more than one task at a time.
Processes and Threads
Process:
Isolated with its own virtual address space Contains process data like file handles Lots of overhead
Every process has AT LEAST one thread
Threads:
Shared virtual address space Contains running state data Less overhead
From the OS’s point of view, this is what is scheduled to run on a CPU
User Threads and Kernel Threads
User threads – management done by user-level threads library Three primary thread libraries:
POSIX Pthreads Windows threads Java threads
Kernel threads – Supported by the Kernel
Examples – virtually all general purpose operating systems, including: Windows
Solaris
Linux
Tru64 UNIX
Mac OS X
Multi-Threading
Most of the software you run is multi-threaded; Examples:
A web browser might have one thread display images or text while another thread retrieves data from the network.
A word processor may have a thread for displaying graphics, another thread for reading keystrokes from the user, and a third thread for performing spelling and grammar checking in the background.
This is good because if one thread is blocked waiting for I/O (e.g. loading an image) the remainder of the threads can still execute and remain responsive.
You don’t know it yet, but the Java programs you write with GUIs are multi-threaded automatically.
Multi-Threading 2
A program might need to perform a similar task many times: Examples:
A web server needs to serve many connected clients at once:
• Multi-threaded: create a new thread each time a client arrives to serve that client;
• Sequential (Non-Threaded): Each client has to wait until the earlier ones have finished before
connecting (bad!).
An expensive computation needs to be done many times with different parameters:
• E.g.: protein folding method needs to run to check interactions between two proteins (thousands of
pairs); or we need to calculate the colour of each pixel in a fractal.
• Multi-Threaded: Create a thread to run the method with each type of parameter, run the threads in parallel on many CPUs (or even different machines).
• Sequential: each one has to wait for the previous one to complete, even if we have 100 CPUs…
Processes/Tasks in Linux/Windows
Linux and Windows do not distinguish between processes and threads, multi-threaded processes make many threads that share resources.
Benefits of Multi-Threading
Responsiveness: If one thread is blocked (e.g. waiting for I/O) the other threads in the process can still run, meaning the user can still interact with the program;
Resource Sharing: Avoids duplication, allows threads to interact with each other easily;
Efficiency: Threads are cheaper to create and to context switch. (Faster)
Multi-processor Utilisation: A single threaded process can only ever run on one CPU. Multiple threads can be distributed over multiple CPUs: more concurrency = faster execution time.
Lecture Topics
• Introduction to Threads;
• Basic Threading in Java;
• The Critical Section Problem;
• Solutions to the Critical Section Problem.
Making an Object a Thread
public class PrintP extends Thread {
public void run(){
for(int i = 0; i < 100; ++i){
System.out.println(“P”); }
} }
public class PrintQ implements runnable extends SomethingElse {
public void run(){
for(int i = 0; i < 30; ++i){
System.out.println(“Q”); }
} }
•
• •
Two ways of making an object able to run as a thread:
– Extend the class Thread;
– Implement runnable;
Why two? Java does not allow multiple inheritance, so if something is already extending something else we can’t extend Thread.
Both ways require the implementation of a method run():
– This is the method that will be called when the thread is started, i.e. the code that determines what the thread will do.
Starting a Thread
public class myMain {
public static void main(String[] args){
Thread p = new PrintP();
Thread q = new Thread(new PrintQ()); p.start();
q.start();
for(int i = 0; i < 200; ++i){
System.out.println(“R”); }
} }
(Extended Version)
Instantiate objects of the appropriate type:
• •
•
Thread has a method start() which tells the JVM to create a new thread and then call the run() method
in that new thread;
Do not call run() directly: otherwise the creating a new thread part is missed out and the run() method runs just as any other method.
Notice because PrintQ implements runnable and we need a Thread to call start, we have to use the constructor of Thread that takes a runnable object as an argument, to get a Thread object for PrintQ.
Runnable qRun = new PrintQ(); Thread q = new Thread(qRun);
How Many Threads Are Running?
public class myMain {
public static void main(String[] args){
Thread p = new PrintP();
Thread q = new Thread(new PrintQ()); p.start();
q.start();
for(int i = 0; i < 200; ++i){
System.out.println(“R”); }
} }
How many threads are running:
No, not 2, 3!
The main method itself is in a thread (the original one for the program) that carries on executing whilst the other threads also execute.
What is the output? Different every time, or at least it will be if the content of the
methods is significant enough to so they don’t finish before context switching occurs:
The output is at the mercy of the scheduler: unpredictable.
Output: 3 Runs
Threads execute so quickly that the chance of a context switch during execution is small.
RRQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
RRRRPPPPPPPPPPPPPPPPPPPPPPRRRPPPPPPPPPPPRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRPPPPPPPPPPPPPPPPPP
p.start();
q.start();
for(int i = 0; i < 200; ++i){
System.out.println(“R”); }
PPRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPPQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
Wasting Some Time
public class PrintP extends Thread {
public void run(){
for(int i = 0; i < 100; ++i){
System.out.println(“P”);
//waste some time }
} }
int n = 0;
for(int j = 0; j < 1000000; ++j){
++n;
--n; }
PQPQPPQPPQPQPQPQPQPQPQPQPQPQQPQPQPQPQPQPQPQPQPQPQPQPQP QPQPQPQPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
QPQPQPQQPQPQPQPQPQPQPQPQPQPQPQPQPQPQPQQQPQPPPQQPQPQPQQ PQPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
Wasting Time More Graciously
public class PrintP extends Thread { public void run(){
for(int i = 0; i < 100; ++i){ System.out.println(“P”); try{
Thread.sleep(30);
} catch (InterruptedException e){
e.printStackTrace();
}
} }
}
public class PrintQ implements runnable extends SomethingElse {
public void run(){
for(int i = 0; i < 30; ++i){
System.out.println(“Q”); }
try{
Thread.sleep(50);
} catch (InterruptedException e){ e.printStackTrace();
} }
}
• Threads can sleep: this stops their execution and allows other threads to run:
– Why? Suppose a thread is checking a value waiting for it to change, we don’t want to hog the CPU (more later).
– When threads sleep they enter a blocked state so context switches happen.
PRRRR...RRRRQRRR..RRRPPQPQPPQPPQPQPPQPQPPQPPQPPQPQP PQPPQPQPPQPPQPQPPQPPQPQPPQPQPPQPPQPQPPQPPQPPQPQPP PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
Waiting for a Thread:join()
public static void main(String[] args){ Thread p = new PrintP();
Thread q = new Thread(new PrintQ()); p.start();
q.start();
q.join(); //try catch needed around this for(int i = 0; i < 200; ++i){
System.out.println(“R”); }
}
Sometimes we might want to wait for a thread we start to finish before we continue. q.join()
QPPQPPQPQPPQPPQPQPPQPPQPQPPQPPQPQPPQPPQPQPPQPPQPPQPQPPQPP QPQPPQPPQPQPPQPPQPQPPQPPRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
p.join()
QPPQPPQPQPPQPPQPQPPQPPQPPQPQPPQPPQPQPPQPPQPQPPQPPQPQPPQP PQPQPPQPPQPQPPQPPQPQPPQPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
What is this InterruptedException?
In general there are two methods for cancelling (killing) threads:
Asynchronous Cancellation: The thread is terminated immediately; Deferred Cancellation: The thread checks periodically to see whether it is to
terminate.
In Java a thread might be killed whilst it is sleeping:
In this case an InterruptedException is thrown:
• When this is caught the thread can do whatever tidying up it needs to do when it is terminated;
• Doesn’t need to check all the time whether it is to be terminated but can still clean up (e.g. close
files).
Java Thread Lifecycle
run()
(Scheduler)
Running
yield()
(Scheduler) sleep() or
run() ends
Thread()
Created
Start()
Runnable more to come
sleep() ends
or more to come Blocked
Terminated
Activity-1 - 10 minutes
Q1. Which of the two techniques explained earlier you think is the most common technique for writing multithreaded Java programs?
Answer : Using Runnable interface
Q2. A computer game, controlled by the keyboard, has a character that the user must control, a single 'enemy' that will chase the user, suggest 5 different threads this program could use to parallelise its activity?
Answer: A thread to do keyboard I/O; A thread to update the enemy position; a thread to update the character position; a thread to update the user interface; a main thread to start the other threads and do any other necessary computation.
Q3. Why might a web server need to be multithreaded?
Answer: If a web server were not multi-threaded then only one user would be able to connect at once, and others would have to wait until that user had completed all tasks and disconnected before they could connect. This would be very inefficient.
1/16/2020
Shared Resources
public static void main(String[] args){ int[] buffer = new int[10];
Thread p = new pcThread(buffer); Thread q = new pcThread(buffer); p.start();
q.start(); }
These two threads now both use the same array to perform operations on.
Not a copy of the same array, but actually the same physical space in memory. Can use this to pass data between them.
Let’s have a look at what can happen.
Consider a method addData(int n) which puts n at the end of the buffer.
Shared Class Variables
210
Buffer = [..............................]
addData(20)
{
buffer[spaceUsed] = 20; ++spaceUsed;
}
spaceUsed = 0;
addData(10)
21
{
buffer[spaceUsed] = 10;
++spaceUsed;
}
• We don’t know what order the threads will be interleaved: – Sometimes we will get a crash;
– Sometimes we won’t;
– Race condition.
• Makes bug fixing much harder.
It Gets Worse...
Each line of Java in the previous slide gives rise to multiple machine code instructions (remember CPUs run machine code not Java...);
Let’s take the simplest one: ++spaceUsed;
movR1,.spaceUsed //putaddressofspaceUsedintoRegisterR1
ldm R0, [R1]
add R0, R0, 1
stm R0, [R1]
//load to R0 from memory address in R1 //R0 = R0 + 1
//store R0 in memory address in R1
Interleaving
movR1,.spaceUsed ldm R0, [R1]
R1 .SpaceUsed R0
mov R1, .spaceUsed
ldm R0, [R1]
R1 .SpaceUsed R0 add R0, R0, 1
stm R0, [R1]
R1 .SpaceUsed R0 1 add R0, R0, 1
stm R0, [R1]
R1 .SpaceUsed R0 1
//putaddressofspaceUsedintoRegisterR1 //load to R0 from memory address in R1
0
=> Context switch store R0,R1 in memory
//put address of spaceUsed into Register R1
//load to R0 from memory address in R1
0 => Context switch store R0,R1 in memory load R0,R1.
//R0 = R0 + 1
//store R0 (1) in memory address in R1
=> Context switch store R0,R1
in memory load R0,R1.
//R0 = R0 + 1
//store R0 (1) in memory address in R1
=> Now spaceUsed = 1
Atomicity
An atomic statement is a single statement that cannot be interrupted:
Cannot split the atom in CS (ignore physics!).
Concurrency is the interleaving of atomic statements;
To save us having to work in machine code, we’ll assume that assignment statements are atomic: the same theory applies at machine code level to allow use to make sure they are.
Each line in the pseudocode we see from now on we will assume is an atomic instruction.
We still have problems, in the earlier example we saw interleaving of two lines of code that we assumed to be atomic causing problems.
Activity-2 (5-miutes)
1/16/2020
BREAK TIME
10 minutes Break
1/16/2020
Lecture Topics
• Introduction to Threads;
• Basic Threading in Java;
• The Critical Section Problem;
• Solutions to the Critical Section Problem.
Slides based on Chapter 4 and Chapter 6 of “Operating Systems Concepts” Silberschatz, Galvin and Gagne With additional Java Examples
Critical Section
addData(10) addData(20)
{{ }}
buffer[spaceUsed] = 10;
++spaceUsed;
buffer[spaceUsed] = 20;
++spaceUsed;
A Critical Section : the part of a program which needs to be executed atomically (w.r.t. other related threads)
If two or more threads enter the critical section simultaneously then errors could occur.
Critical Sections in Java
Java provides the keyword synchronized which can be used to mark a method as a critical section;
If this keyword is used, then for each instance of the given object only one synchronised method can be run at once.
More than one method can be marked as synchronized in which case none of these methods can be run at the same time.
How does Java manage this? That’s the topic of the next few lectures, but for now we’ll get familiar with using it.
Synchronisation Example
We are assuming that the buffer is sufficiently big that it won’t get full.
No two threads may be allowed to call add at once;
Also no thread can be allowed to call print whilst something else is adding.
We assume print is not called on an empty buffer
public class Buffer { int[] buffer;
int spaceUsed;
public Buffer(int size){ buffer = new int[size]; spaceUsed = 0;
}
public synchronized void add(int toAdd){ buffer[spaceUsed] = toAdd;
++spaceUsed;
}
public synchronized void printBuffer(){ System.out.print(buffer[0]);
for(int i = 1; i <= spaceUsed; ++i){
System.out.print(", " + buffer[i]);
}
System.out.println(); }
}
public class Producer extends Thread {
int value;
Buffer buffer;
public Producer(Buffer toUse,
int toProduce){
value = toProduce;
buffer = toUse;
}
public void run(){
for(int i = 0; i < 5; ++i){
buffer.add(value);
buffer.printBuffer(); //then optionally waste some time...
}}} //on one line to save slide space
public static void main(String[] args){ Buffer buffer = new Buffer(10); Thread p = new Producer(buffer,1); Thread q = new Producer(buffer,2); p.start();
q.start(); }
With and Without Synchronized (and some time wasting)
[1]
[1, 2]
[1, 2, 1]
[1, 2, 1, 2]
[1, 2, 1, 2, 1]
[1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 1, 2, 1]
[1, 2, 1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 1, 2, 1, 2, 1] [1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
[1]
[1, 1]
[1, 1, 1]
[1, 1[1, 1, 1, 2, 1]
, 1, 2, 1]
[1, 1, 1, 2[1, 1, 1, 2]
, 1, 1, 2, 1, 1, 2]
[1, 1, 1, 2, 1, 1, 2, 2]
[1, 1, 1, 2, 1, 1, 2, 2, 2] [1, 1, 1, 2, 1, 1, 2, 2, 2, 2]
With synchronized (left) the output is sensible;
Without synchronized (right) one thread prints in the middle of the other printing.
Update errors are also possible, but didn’t occur this run.
Homework - Practice with Threads programs Provided on KEATS
• Programs are available under week-2 study materials on KEATS: -Basic Threads that we explained today for print Q,P and R.
-Thread Synchronization
• Additional 2 programs that you may have practiced in your previous study which is now implemented using Threads for you to practice and testing only.
-Matrix Multiplication program and sorting using threads.
1/16/2020
Lecture Topics
• Introduction to Threads;
• Basic Threading in Java;
• The Critical Section Problem;
• Solutions to the Critical Section Problem.
Synchronising Critical Sections
Global Variables
p
q
local variables loop_forever
non-critical section
preprotocol
critical section
postprotocol
local variables loop_forever
non-critical section
preprotocol
critical section
postprotocol
• preprotocol: check that it is okay to enter critical section; • postprotocol: signal that critical section is complete.
• Together called a synchronisation mechanism.
Properties of a Solution
1. Mutual Exclusion: Only one process can enter the critical section at once. 2.Freedom from Deadlock: If some processes are waiting to enter their critical
section, eventually one must succeed;
If all processes are waiting then we have deadlock.
3. Freedom from Starvation (Success in the Absence of Contention): If a process is waiting to enter its critical section it must do so eventually (regardless of whether others have finished executing).
Note that this does not guarantee ‘fairness’ if one process gets 10000 entries into its critical section before another enters the other process is not starved.
Starvation vs Deadlock: In deadlock processes must be waiting for a variable assignment that will never happen (there is no chance of escape); in starvation it can be that an assignment might not happen due to interleaving but could happen on a different one.
There must be no interleaving that breaks these properties.
Assumptions
Global Variables
p
q
local variables loop_forever
non-critical section preprotocol critical section postprotocol
local variables loop_forever
non-critical section preprotocol critical section postprotocol
• A process will complete its critical section i.e : -It will not exit;
-There is no infinite loop.
• A process may terminate during its non-critical section.
• The CPU scheduler will not starve a process.
• No variables used in the critical and non-critical sections are used in
the protocols and vice versa.
First Attempt
integer turn1
p
q
loop_forever
p1: non-critical section p2: await turn = 1
p3: critical section p4: turn2
loop_forever
q1: non-critical section q2: await turn = 2
q3: critical section q4: turn1
await turn = 1 is an implementation-independent notion for a
statement that waits until the condition turn=1 becomes true.
Does this work?
First Attempt
integer turn1
p
q
loop_forever
p1: non-critical section p2: await turn = 1
p3: critical section p4: turn2
loop_forever
q1: non-critical section q2: await turn = 2
q3: critical section q4: turn1
State Diagram Begins:
Full State Diagram
Shows all execution traces.
Never are we in p3,q3 therefore mutual
exclusion holds!
Deadlock? Well, the only place we can gets stuck is at await: p2p3 or q2q3 (red arrows).
Deadlock will only happen in (p2,q2,_).
But if we’re in those states then either turn = 1 or turn = 2.
• turn = 1 Eventually p will be scheduled and progress.
• turn = 2: eventually q will be scheduled and progress.
Freedom from Starvation (Success in the Absence of Contention)
integer turn1
p
q
loop_forever
p1: non-critical section p2: await turn = 1
p3: critical section p4: turn2
loop_forever
q1: non-critical section q2: await turn = 2
q3: critical section q4: turn1
Suppose we have:
(p1,q1,1), (p2,q1,1), (p3,q1,1), (p4,q1,1), (p1,q1,2) then q exits (or has an infinite loop) during its non-critical section (which is permitted).
p1 cannot continue to execute.
First attempt does not have this property!
Second Attempt
boolean wantpfalse, wantqfalse
p
q
loop_forever
p0: non-critical section p1: await wantq = false p2: wantptrue
p3: critical section p4: wantpfalse
loop_forever
q0: non-critical section q1: await wantp = false q2: wantqtrue
q3: critical section q4: wantqfalse
First Attempt failed as both were relying on a single global variable. Let’s fix that by having two variables: one that says p wants to go into its critical section, and one that q does.
To be fair, each will set this variable to false before their non-critical section.
Mutual Exclusion: Execution Trace
boolean wantpfalse, wantqfalse
p
q
loop_forever non-critical section
p1: await wantq = false
p2: wantp = true
critical section p3: wantpfalse
loop_forever non-critical section
q1: await wantp = false
q2: wantq = true
critical section q3: wantqfalse
Process p
Process q
wantp
wantq
p1: await wantq = false
false
false
q1: await wantp = false
false
false
p2: wantp true
true
false
q2: wantq true
true
true
critical section
true
true
critical section
true
true
Does Not Satisfy Mutual Exclusion
Lesson: it’s a lot easier to prove something is incorrect than to prove that it is correct;
Prove incorrect: find one trace that is a counter example; Prove correct: show that every trace is safe.
Solution 2 didn’t work so let’s try another...
BREAK TIME
10 minutes Break
1/16/2020
Third Attempt
boolean wantpfalse, wantqfalse
p
q
loop_forever
p1: non-critical section p2: wantptrue
p3: await wantq = false p4: critical section p5: wantpfalse
loop_forever
q1: non-critical section q2: wantqtrue
q3: await wantp = false q4: critical section q5: wantqfalse
Mutual Exclusion didn’t work so let’s swap the order. Now let’s try to prove mutual exclusion.
Informal proofs here: formal proofs in bonus material.
Types of proof (jokes):
http://school.maths.uwa.edu.au/~berwin/humour/invalid.proofs.html
Mutual Exclusion (Informal)
State diagrams can get big and cumbersome to draw, so we’re going to prove this differently.
For mutual exclusion to hold we must show that (p4, q4, _,_,) cannot be true.
To get to that state one of the two must already be @4 (and stay there) the other must move from 3 to 4.
Processes are symmetric so it doesn’t matter which one.
So let’s assume p is at p4: What is the value of wantp?
q cannot modify wantp.
The only lines that modify wantp are p2 and p5, if we are at p4 then the last one to execute was p2: wantp = true.
For q to transition from q3 to q4 wantp = false
But if p is in p4 wantp = true;
Therefore q cannot transition from q3 to q4 if p = p4.
Freedom from Deadlock
boolean wantpfalse, wantqfalse
p
q
loop_forever
p1: non-critical section p2: wantptrue
p3: await wantq = false p4: critical section p5: wantpfalse
loop_forever
q1: non-critical section q2: wantqtrue
q3: await wantp = false q4: critical section q5: wantqfalse
Process p
Process q
wantp
wantq
p1: non-critical section
false
false
q1: non-critical section
false
false
p2: wantp true
true
false
q2: wantq true
true
true
p3: await wantq = false
true
true
q3: await wantp = false
true
true
Attempt 4
boolean wantpfalse, wantqfalse
p
q
loop_forever
p1: non-critical section p2: wantptrue
P3: while wantq
p4: wantp false
P5: wantp true
p6: critical section p7: wantpfalse
loop_forever
q1: non-critical section q2: wantqtrue
q3: while wantp
q4: wantq false
q5: wantq true
q6: critical section q7: wantqfalse
• This algorithm satisfies some but not all of the three properties.
• Exercise, which? Provide proofs.
Attempt 5: Peterson’s Algorithm
boolean wantpfalse, wantqfalse, integer last1
p
q
loop_forever
p1: non-critical section p2: wantptrue
P3: last1
p4: await wantq = false or
last = 2
P5: critical section
p6: wantpfalse
loop_forever
q1: non-critical section q2: wantqtrue
q3: last2
q4: await wantp = false or
last = 1
q5: critical section
q6: wantqfalse
This algorithm satisfies all of the required properties.
Mutual Exclusion (Informal)
For mutual exclusion to hold we must show that (p5, q5, _,_,_) cannot be true.
To get to that state one of the two must already be @5 (and stay there) the other must move from 4 to 5.
Processes are symmetric so it doesn’t matter which one.
So let’s assume p is at p5: What is the value of wantp?
Only p can change wantp: at lines p2 and p6.
Since we’re at p5 the last of these two to execute must be p2, therefore wantp = true.
Also note that last = 1 or last = 2 (by inspection of the program: these are the only values ever assigned).
Mutual Exclusion II (Informal)
p4: await wantq = false or last = 2
q4: await wantp = false or last = 1
We know: (p5,q4,true,_,1 or 2);
We want to show that q cannot transition from q4 to q5 :
wantp = true (from previous slide) so q can only proceed if last = 1. The only line of code that can set last = 1 is p3.
When p executed p4 and transitioned to p5 either:
wantq = false:
• That means q was at q1 or q2 (inspection of the program);
• Therefore q must execute q3 setting last =2 before q4;
• Since p remains at p5 it cannot execute last =1;
• Therefore last = 2 and q stops at q4;
last = 2
• If last = 2 at p4 and p remains in p5, p3 has not been executed to set last = 1 • therefore last = 2 and q stops at q4.
Deadlock (Informal)
For deadlock to occur both processes must be stuck at line 4:
await wantq = false or last = 2
await wantp = false or last = 1
Both wantp and wantq are true (set at p2 and q2) and not changed Both looping would require last = 2 and last = 1.
Contradiction: an integer cannot take 2 values. Therefore no deadlock.
Peterson’s Algorithm
boolean wantpfalse, wantqfalse, integer last1
p
q
loop_forever
p1: non-critical section p2: wantptrue
P3: last1
p4: await wantq = false or
last = 2 P5: critical section
p6: wantpfalse
loop_forever
q1: non-critical section q2: wantqtrue
q3: last2
q4: await wantp = false or
last = 1 q5: critical section
q6: wantqfalse
Freedom from Starvation (Informal)
Show: If p is at p4 then eventually it will execute p5.
If p is at p4 it can proceed unless: wantq = true and last = 1
Where could q be?
if wantq = true, q is at q3 or q4 or q5 (inspection of the code).
If q is at q3:
• It will execute last = 2
• It will then remain at q4 until p executes. If q is at q4:
• It will continue to q5 as last = 1
• Proceed to q6 (non-termination in cs)
• Execute q6 (set wantq to false);
• Execute q1 and either:
• Terminate, p can proceed as wantq is false; or • Execute q2 setting wantq to true.
• Execute q3 setting last = 2;
• It will then remain at q4 until p executes.
If q is at q5:
• Follow from step 2 for q4.
Activity-3 (5- Minutes)
1/16/2020
Activity-4 ( 10 minutes)
1/16/2020
Contact details/for more information
Sahar.al-sudani@kcl.ac.uk
Thanks for you Attention !
© 2020 King’s College London. All rights reserved
5CCS12OSC – Operating Systems and
Concurrency : Advanced solutions to the Critical
Section Problem
Dr Sahar Al-Sudani,
Spring, 2020
1/28/2020
Lecture Topics
• The Critical Section Problem with n Processes; – Bakery Algorithm;
• SynchronisationHardware; • Semaphores:
– The Producer Consumer Problem;
• Infinite buffer;
• Finite buffer;
– The Dining Philosophers Problem; • SemaphoresinJava.
Chapters 6 of “Operating Systems Concepts” Silberschatz, Galvin, Gagne
Chapters 5 and 6 of “Principles of Concurrent and Distributed Programming” M. Ben-Ari
Advanced Algorithms
• So far all of our solutions to the critical section problem have considered two threads.
• Now we will consider algorithms that work for n-threads: – After all, this is more realistic.
• We will consider some primitives provided by operating systems to implement synchronisation.
Bakery Algorithm
• Our first algorithm is the Bakery Algorithm.
– Inspired by service in bakeries (and other shops) where
customers take a ticket on arrival and are called to be served
in order of ticket number.
• Upon entering customers take a ticket, and when service is available the customer with the lowest ticket number is served.
The Bakery Algorithm for 2 Threads
integer np0, integer nq0
p
q
loop_forever
p1: non-critical section p2: np nq + 1
p3: await nq = 0 or np <= nq p4: critical section
p5: np 0
loop_forever
q1: non-critical section q2: nq np + 1
q3: await np = 0 or nq < np q4: critical section
q5: nq 0
• Simple version for 2 threads;
• np and nq are the ticket numbers.
– Zero indicates thread does not want to enter its critical section.
– A positive number indicates the process is in the queue to enter, the queue is
sorted lowest number first.
• For equal ticket numbers we will arbitrarily favour p (p3 <=, q3 <).
Proofs of Properties
• In this week’s exercises!
The Bakery Algorithm for N Threads
integer array[1...N] number[0,...,0]
loop_forever
p1: non-critical section
p2: number[i] 1 + max(number)
P3: for all other threads j
p3: await number[j] = 0 or number[i] << number[j] p4: critical section
p5: number[i] 0
• Each thread has a unique id, i, in the range [1..N].
• N threads executes the same algorithm except i is referring to the thread id • For all other threads j means for j=1 to N if j !=i
• number[i] << number[j] means either:
– number[i] < number[j] or:
– number[i] = number[j] and i < j.
• For equal ticket numbers we will arbitrarily favour lower id thread.
The Bakery Algorithm for N Threads
integer array[1...N] number[0,...,0]
loop_forever
p1: non-critical section
p2: number[i] 1 + max(number)
P3: for all other processes j
p3: await number[j] = 0 or number[i] << number[j] p4: critical section
p5: number[i] 0
• Pick a ticket number that is larger than any currently held ticket.
• Enter critical section when no other process is waiting to enter (value is zero) or none holds a lower numbered ticket (break ties on id);
• Set ticket number to zero (I am not waiting enter CS).
Note on Atomicity for the Astute
• There is a big assumption here:
– Finding the max of an array is an atomic operation.
• This can be fixed, but the algorithm is more complicated.
integer array[1...N] number [0,...,0] choosing[false,...,false]
loop_forever
p1: non-critical section
P2: choosing[i] true
p3: number[i] 1 + max(number)
p4: choosing[i] false
p5: for all other processes j
p6: await choosing[j] false
p7: await number[j] = 0 or number[i] << number[j] p8: critical section
p9: number[i] 0
The Good and The Bad
• Good:
– No global variable is written to by more than one process;
– Mutual Exclusion, Freedom from Deadlock and Freedom for Starvation hold.
• Bad:
– Unbounded ticket numbers if some process is always in the critical
section;
– Each process must query all others to see if it can enter CS, even if no others want to enter.
• Overall: algorithm too inefficient to use in practice.
Lecture Topics
• The Critical Section Problem with n Processes; – Bakery Algorithm;
• Synchronisation Hardware; • Semaphores:
• •
•
– The Producer Consumer Problem; Infinite buffer;
Finite buffer;
– The Dining Philosophers Problem; Semaphores in Java.
Synchronisation Hardware
• So far we have been assuming an atomic assignment operator.
– This would, of course, have to be provided at a lower level, e.g. OS or hardware.
• Instead we can consider a more general idea:
– A solution to the critical section problem requires a lock: a thread
must obtain the lock in order to enter its critical section.
• In fact, hardware can provide us with primitives to allow us to do synchronisation much more easily.
Single vs Multi-Processor Solutions
• In a single processor environment we could solve the critical section problem simply by disabling interrupts whilst shared data is being modified.
• In a multi-processor environment however:
– Message has to be passed to each processor every time a CS is entered: slows down
system.
– Also disabling interrupts affects the system clock if the clock is kept up to date by interrupts.
Test and Set
boolean lockfalse
p
loop_forever
p1: non-critical section p2: await(!testAndSet(lock)) p3: critical section
p4: lock = false;
boolean testAndSet(Boolean lock){ boolean toReturn =
lock.getValue();
lock.setValue(true);
return toReturn; }
• Single processor instruction that will both test the value of a variable and set it to a new value.
• Test and set will return the value of the lock (false means no one is in cs) and set the value of the lock to true;
– Does no harm if it is already true
• If two processors attempt to execute this instruction simultaneously the hardware will
ensure the instructions will be executed sequentially (in some arbitrary order);
• Works for n processes: atomic assignment no longer required.
Swap
boolean lockfalse
p
boolean keytrue
loop_forever
p1: non-critical section
P2: key = true
p3: while(key = true)
swap(lock,key);
p4: critical section
p5: lock = false;
void swap(Boolean lock,
Boolean key){
boolean tmp = lock.getValue();
lock.setValue(key.getValue());
key.setValue(tmp); }
• Single processor instruction that will swap the value of two Booleans.
• Again hardware ensures this instruction is not simultaneously executed.
• Works for n processes: atomic assignment no longer required.
• N.B. Both of these algorithms could lead to starvation but it is unlikely (see Section 6.4 of “Operating Systems Concepts” for details of how to get around this).
Lecture Topics
• The Critical Section Problem with n Processes; – Bakery Algorithm;
• SynchronisationHardware; • Semaphores:
– The Producer Consumer Problem;
• Infinite buffer;
• Finite buffer;
– The Dining Philosophers Problem; • SemaphoresinJava.
Semaphores
• Application programmers do not typically reason with hardware- level instructions;
• Instead higher-level software mechanisms are generally provided that make use of the lower-level hardware instructions.
– Less prone to error as more abstract: less complex; – Nicer to work with.
• Semaphores are an example of a commonly used synchronisation mechanism.
– Provided by most operating systems.
• Proposed by Dijkstra in 1965.
What is a Semaphore (Busy-Wait)?
• A semaphore comprises:
– An integer variable, v;
– A set of processes, blocked, (initially empty).
• A semaphore has two methods:
Naïve Version (busy wait): Wait(S){
while(S.v <= 0){
//do nothing
}
S.v = S.v - 1;
}
Naïve Version (busy wait): Signal(S){
S.v = S.v + 1; }
while(S.v <= 0){} Also called a spin lock.
What is a Semaphore (Blocked-Set)?
• A semaphore comprises:
– An integer variable, v;
– A set of processes, blocked, (initially empty).
• A semaphore has two methods:
Wait(S){
S.v = S.v - 1; if(S.v < 0) {
S.blocked = S.blocked U this;
this.state = blocked; }
}
Signal(S){
S.v = S.v + 1;
select one q from S.blocked: q.state = runnable;
}
Critical Section Problem for 2 Threads with Semaphores
Semaphore S (1, Ø)
p
q
loop_forever
p0: non-critical section
p1: wait(S)
p2: critical section
p3: signal(S)
loop_forever
q0: non-critical section
q1: wait(S)
q2: critical section
q3: signal(S)
• Initially S.v = 1;
• Before a thread enters its critical section:
– S.v will be decremented: zero means some thread is in cs.
– So if the other process calls wait(S) S.v = 0 and it will be blocked.
• When a process leaves its critical section:
– Signal adds 1 to S.v so that when a process leaves its critical section S.v = 1 and other
processes can enter.
– If the other process is waiting it is unblocked.
State Diagram (Excl. non-cs)
p3 q1
p2:CS q1:blocked S: {-1, {q}}
p2 p3:Signal(S) q1:blocked
S: {-1, {q}}
q1
p2: CS q1:wait(S) S: {0, Ø}
p3
q3
q2
p1 q3
p2
p3:Signal(S) q1:wait(S) S: {0, Ø}
p1
p1:wait(S) q1:wait(S) S: {1, Ø}
p1
p1:blocked q2 p1:blocked q2:CS q3:signal(S) S: {-1, {p}} S: {-1, {p}}
No state (p2,q2,_), therefore mutual exclusion holds. No state in which both are blocked therefore no deadlock.
q1
p1:wait(S) q2:CS
S: {0, Ø}
p1: Wait(S) q3:Signal(S) S: {0, Ø}
Starvation
• When a process is awoken it leaves the blocked state and continues straight into its critical section (setting S.v to 1).
• The absence of starvation relies on this:
– Otherwise if the thread wasn’t scheduled before the other thread, then the other thread could be scheduled to run and complete wait(S) first each time (this is unlikely but possible: as Attempt 4 in the previous lecture a continuous execution of the same interleaving).
– Read more details about this in your text book.
Properties of Busy-Wait Semaphores
Semaphore S (1, Ø)
p
q
loop_forever
p1: non-critical section
p2: wait(S)
p3: critical section
p4: signal(S)
loop_forever
q1: non-critical section
q2: wait(S)
q3: critical section
q4: signal(S)
• S.v > 0 always;
• S.v = init + #signal(S) – #wait(S);
• #CS + S.v = 1;
• #CS = #wait(S) – #signal(S).
BREAK TIME
10 minutes Break
1/28/2020
Solution for N Processes
Semaphore S (1, Ø)
p
loop_forever
p1: non-critical section
p2: wait(S)
p3: critical section
p4: signal(S)
• Mutual Exclusion and Freedom from Deadlock hold by arguments applied to 2 processes, and properties of semaphores.
• Let’s take a look at starvation.
Scenario for Starvation
Thread p
Thread q
Thread r
S
p1: wait(S)
q1: wait(S)
r1: wait(S)
(0, Ø)
p2: critical-section
q1: wait(S)
r1: wait(S)
(-1,{q})
p2: critical-section
q1: blocked
r1: wait(S)
(-2,{q,r})
p2: critical-section
q1: blocked
r1: blocked
(-2,{q,r})
p3: signal(S)
q1: blocked
r1: blocked
(-2,{q,r})
p1: wait(S)
q1: blocked
r2: critical-section
(-1,{q})
p1: wait(s)
q1: blocked
r3: signal(S)
(-2,{p,q})
p1: blocked
q1: blocked
r3: signal(S)
(-2,{p,q})
p2: critical-section
q1: blocked
r1: wait(S)
(-1,{q})
p3: signal(S)
q1: blocked
r1: wait(S)
(-2,{q,r})
p3: signal(S)
q1: blocked
r1: blocked
(-2,{q,r})
• Again requires a specific interleaving so improbable but possible;
• Can fix this by using a queue (FIFO) in the semaphore instead of a set (blocked- queue semaphore).
Other Application of Semaphores: Waiting for Other Threads Using Semaphores
Semaphore S1(0, Ø), Semaphore S2(0, Ø)
p
q
r
p1: non-critical section p2: signal(S1)
p1: non-critical section p2: signal(S2)
r1: wait(S1)
r2: wait(S2)
r3: continue
• •
• •
Similar to join() but r did not start p and q.
Can be used when one thread might need to wait for another:
– e.g. mergesort:
Split array in half;
– P sorts one half, q sorts the other half R does merging after completion
Activity-1 (10 minutes)
1/28/2020
Lecture Topics
• The Critical Section Problem with n Processes; – Bakery Algorithm;
• Synchronisation Hardware; • Semaphores:
• •
•
– The Producer Consumer Problem; Infinite buffer;
Finite buffer;
– The Dining Philosophers Problem; Semaphores in Java.
The Producer Consumer Problem
• Aproducerprocesscreatesdata;
• A consumer process takes the data and uses it;
• This pairing is common in computer science.
• For asynchronous communication we need a buffer.
• Twoissuescanoccur:
– Buffer is empty, consumer cannot take data; – Buffer is full, producer cannot add data;
Infinite Buffer Producer/Consumer
Semaphore notEmpty (0, Ø), infinite queue
producer
consumer
loop_forever
p1: dproduce
p2: append(d,buffer) p3: signal(notEmpty)
loop_forever
q1: wait(notEmpty) q2: dtake(buffer) q3: consume(d)
• Infinite buffer case: only need to synchronise removal.
• Notice the semaphore is initialised to 0, not 1 as in previous examples;
• This is because we don’t want wait to be able to consume until something has been added to the buffer;
• Here the semaphore value is 0 if the buffer is empty.
Finite Buffer Producer/Consumer
Semaphore notEmpty (0, Ø), Semaphore notFull (N, Ø), size N queue
producer
consumer
loop_forever
p1: dproduce
P2: wait(notFull) p3: append(d,buffer) p4: signal(notEmpty)
loop_forever
q1: wait(notEmpty) q2: dtake(buffer) q3: signal(notFull) q4: consume(d)
• Finite buffer case: create an analogy, producer makes non-empty buffers for the consumer; consumer makes non-full buffers for the producer.
• Notice the notFull semaphore is initialised to N, so it can be decremented N times (i.e. N things can be added to the buffer) before it reaches zero.
• This technique is called split semaphores (we also used it to wait for other threads).
Initialising Semaphores to Values Other than 1 or 0
Semaphore S (N, Ø)
p
loop_forever
p1: non-critical section p2: wait(S)
p3: critical section p4: signal(S)
• Now N threads can successfully proceed through wait, before one is blocked to call signal: e.g. N = 3, 3 threads can enter at once.
• Clearly this doesn’t enforce mutual exclusion, but it does allow a limit on the number of threads that could be in their critical section.
• Can be useful if e.g. want to limit number of processes which can have a file open, or can connect to a server, or perhaps we have 3 instances of a resource, so 3 threads can use the resource at once.
Types of Semaphore
• Busy Wait Semaphore: the first type we saw where a process continually loops checking s;
• Blocked-SetSemaphore(weaksemaphore):thetypeof semaphore we have been using, stores blocked processes in a set and wakes one arbitrarily;
• Blocked-Queue Semaphore (strong semaphore): uses a queue instead of a set.
Lecture Topics
• The Critical Section Problem with n Processes; – Bakery Algorithm;
• Synchronisation Hardware; • Semaphores:
• •
•
– The Producer Consumer Problem; Infinite buffer;
Finite buffer;
– The Dining Philosophers Problem; Semaphores in Java.
The Dining Philosophers Problem
• Canonical problem in concurrent programming literature;
• 5 Philosophers sit around a table.
• Each alternates between thinking and
eating.
• Caveat:
– A philosopher requires two forks to eat.
– There are only 5 forks on the table, one between each pair of philosophers.
• Not entirely a compelling problem, but illustrates some important issues.
Image: Wikipedia
Philosophers as Threads
Philosopher
loop_forever p1: think
p2: preprotocol p3: eat
P4: postprotocol
• No two philosophers can hold the same fork simultaneously.
• Each philosopher can pick up the fork on his right or left but only one
at a time (mutual exclusion)
• Freedom from starvation (literally)
• Freedom from deadlock.
First Proposed Solution
Semaphore array fork [1,1,1,1,1]
loop_forever
p1: think
p2: wait(fork[i]) //left fork p3: wait(fork[i+1]) //right fork p4: eat
p5: signal(fork[i+1])
P6: signal(fork[i])
• Each fork can now only be held by one philosopher.
• What happens if the execution trace is:
– p1,q1,r1,s1,t1,p2,q2,r2,s2,t2?
-Deadlock! : None of the philosophers will be able to eat!
Second Attempt
Semaphore array fork [1,1,1,1,1], Semaphore room 4
loop_forever
p1: think
P2: wait(room)
p3: wait(fork[i]) //left fork p4: wait(fork[i+1]) //right fork p5: eat
p6: signal(fork[i+1])
P7: signal(fork[i])
P8: signal(room)
• Now only 4 philosophers may enter the room at once.
• Solves the problem, but not very sociable.
Freedom From Starvation
• If philosopher 1 is starved then they are waiting forever for a semaphore.
• Case fork[1] (left fork): this means that philosopher 0 is holding fork[0] as a right fork, i.e. also already has a left fork and is eating, therefore will eventually signal fork[1] so this philosopher can continue.
• Case fork[2] (right fork): this means that philosopher 2 must have taken their left fork (fork[2]) and, if they cannot proceed, must be unable to take their right fork, fork[3].
– This in turn means p3 has taken fork[3] and cannot get fork[4];
– And that p4 has taken fork[4] and cannot get fork[0];
– And that p0 has taken fork[0] and cannot get fork[1];
– But we know that not all philosophers are in the room due to the room semaphore so this cannot be the case.
• Case room (out of the room): if we ensure that room is a blocked queue semaphore then because none of the philosophers can be blocked indefinitely when in the room (see above) one will eventually complete and signal room, allowing the other to enter.
A More Sociable Solution
Semaphore array fork [1,1,1,1,1]
Philosopher 4
loop_forever
p1: think
p2: wait(fork[0]) //right fork p3: wait(fork[4]) //left fork p4: eat
p5: signal(fork[0])
P6: signal(fork[4])
• This is an asymmetric solution: philosopher 4 picks up right then left, all others left then right.
• Exercise: show that this is starvation free.
BREAK TIME
10 minutes Break
1/28/2020
Lecture Topics
• The Critical Section Problem with n Processes; – Bakery Algorithm;
• Synchronisation Hardware; • Semaphores:
• •
•
– The Producer Consumer Problem; Infinite buffer;
Finite buffer;
– The Dining Philosophers Problem; Semaphores in Java.
Semaphores in Java
• API Documentation:
– http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Semaphore.ht
ml
– import java.util.concurrent.Semaphore; • Constructor:
– Semaphore(int permits) Creates a Semaphore with the given number of permits and nonfair fairness setting.
– Semaphore(int permits, boolean fair) Creates a Semaphore with the given number of permits and the given fairness setting.
• Important Methods:
– void acquire() Acquires a permit from this semaphore, blocking until one is
available, or the thread is interrupted. Throws InterruptedException
– void release() Releases a permit, returning it to the semaphore.
– N.B. acquire() = wait, release() = signal.
– boolean isFair() Returns true if this semaphore has fairness set true.
Example 1: Producer Consumer
public class Buffer {
LinkedList
Semaphore access;
public Buffer(){
buffer = new LinkedList(); access = new Semaphore(1);
}
public Integer removeItem(){
…
}
public void addItem(Integer i){
…
} }
• Accesses to the buffer (add/remove) are the critical sections.
• Weneeda semaphore to make sure that access to the buffer is atomic.
• Initialisingthe semaphore to 1 makes sure only one thread can modify the buffer at once.
Adding and Removing
public Integer removeItem(){
try{
access.acquire();
} catch (Exception e){
e.printStackTrace();
}
Integer toReturn =
buffer.removeFirst();
access.release();
System.out.println(“Buffer size
” + buffer.size());
return toReturn;
public void addItem(Integer i){
try{
access.acquire();
} catch (Exception e){ e.printStackTrace();
}
buffer.addLast(i);
access.release();
System.out.println(“Buffer size
” + buffer.size());
}
}
• addItem and removeItem can run in parallel;
• But, the critical sections cannot as they are protected by a semaphore;
• Notice we call release as soon as we finish with the shared resource, not after printing.
public class Producer extends Thread { Semaphore notFull;
Semaphore notEmpty;
Buffer buffer;
public Producer(Semaphore isNotFull, Semaphore isNotEmpty, Buffer toUse){
notFull = isNotFull; notEmpty = isNotEmpty; buffer = toUse; }
public void run(){
for(int i = 0; i < 10; ++i){
try{
notFull.acquire();
} catch (Exception e){
e.printStackTrace();
} buffer.addItem(i); notEmpty.release();
//waste some time }
Notice that the semaphore that is released (signalled) is not the same semaphore that is acquired (waited for).
}}}
public class Consumer extends Thread { Semaphore notFull;
Semaphore notEmpty;
Buffer buffer;
public Consumer(Semaphore isNotFull, Semaphore isNotEmpty, Buffer toUse){
notFull = isNotFull; notEmpty = isNotEmpty; buffer = toUse; }
public void run(){
for(int i = 0; i < 10; ++i){
try{
notEmpty.acquire();
} catch (Exception e){
e.printStackTrace();
}
Integer item = buffer.removeItem(); notFull.release();
//waste some time (a bit more than producer) System.out.println("Got " + item);
}}}
Notice that the semaphores are now used in the opposite order.
public class ProducerConsumerSemaphore {
}
public static void main(String[] args) { Semaphore notEmpty = new Semaphore(0);
//determines the size of the buffer
Semaphore notFull = new Semaphore(5);
Buffer buffer = new Buffer();
Producer p = new Producer(notFull,notEmpty,buffer); Consumer c = new Consumer(notFull,notEmpty,buffer);
c.start();
p.start(); }
• Notice notEmpty = 0, zero threads can be allowed to consume.
• NotFull = 5, 5 threads can produce before any need to be blocked.
Example 2: Dining Philosophers
public class Philosopher extends Thread {
int position;
Semaphore[] forks;
public Philosopher (int pos, Semaphore[] forksIn){ position = pos;
forks = forksIn;
}
public void run () { ...
} }
public void run () {
while(true){
System.out.println("Philosopher " + position + " Thinking...."); try{
Thread.sleep(100);
int left = position;
int right = position + 1;
//nicer would be int right = (position + 1) % 5; if(right == 5){
right = 0; }
forks[left].acquire();
forks[right].acquire();
System.out.println("Philosopher " + position + " Eating"); Thread.sleep(100);
forks[right].release();
forks[left].release();
} catch(Exception e){
e.printStackTrace();
}
} }
Main Method
public class DiningPhilosophersSemaphore {
public static void main(String[] args) {
Semaphore[] forks = new Semaphore[5];
for(int i = 0; i < 5; ++i){
forks[i] = new Semaphore(1); }
for(int i = 0; i < 5; ++i){
Philosopher phil = new Philosopher(i,forks); phil.start();
} }
}
• Semaphores set to 1, only one philosopher can use each fork.
• Create 5 philosopher threads and start them running.
public void run () {
while(true){
System.out.println("Philosopher " + position + " Thinking...."); try{
Thread.sleep(100);
int left = position;
int right = position + 1;
if(right == 5){ //swap right and left to avoid deadlock
}
forks[left].acquire();
forks[right].acquire();
System.out.println("Philosopher " + position + " Eating"); Thread.sleep(100);
forks[right].release();
forks[left].release();
} catch(Exception e){
e.printStackTrace(); }
} }
left = 0;
right = 4;
Summary
• The Critical Section Problem with n Processes; – Bakery Algorithm;
• Synchronisation Hardware; • Semaphores:
• •
•
– The Producer Consumer Problem; Infinite buffer;
Finite buffer;
– The Dining Philosophers Problem; Semaphores in Java.
Mock QUIZ
1/28/2020
Contact details/for more information
Sahar.al-sudani@kcl.ac.uk
Thanks for you Attention !
© 2020 King’s College London. All rights reserved
5CCS12OSC – Operating Systems and Concurrency: Monitors and Concurrency in Java
Dr Sahar Al-Sudani
Spring, 2020
2/4/2020
Lecture Topics
Motivation for Monitors;
Monitor Concept;
Monitors using semaphores; Semaphores using monitors;
Canonical problems:
The Dining Philosophers Problem; The readers and writers problem
Concurrency in Java.
Train Bridge Example; Swing Threads.
Chapter 6 of “Operating Systems Concepts” Silberschatz, Galvin, Gagne
Chapter 7 of “Principles of Concurrent and Distributed Programming” M. Ben-Ari Plus Additional Java Examples and extracts from the Java API.
Issues with Semaphores
Whilst they represent an effective way to manage the critical section problem, which is more user- friendly than hardware provided systems semaphores are still prone to errors.
All programmers of a system must correctly implement the pattern:
wait(S), Critical Section, signal(S);
If one gets it wrong (deliberately, to avoid being blocked by other processes, or accidentally) the whole system could suffer violation of mutual exclusion.
If a system is being contributed to by a large team this is more than likely to happen... Common errors:
• • •
•
One programmer forgets to signal -> deadlock;
One programmer forgets to wait -> mutual exclusion violated; Wrong order of signal/wait:
signal(S), Critical Section, wait(S);
Use of wait instead of signal:
wait(S), Critical Section, wait(S);
Solving the Problem: Monitors
Invented by Hoare and Hansen.
Idea:
In OO programming objects are encapsulated in classes. A monitor is similar to a class.
The shared resource is represented by a monitor which has methods through which other threads/processes can access that resource.
The only way to access the resource is through these methods.
• Think of the resource as a private instance variable with public accessor methods.
Now we simply impose the requirement that none of these methods can execute
concurrently.
Now only one process can modify/use the resource at once.
Advantages of Monitors
• Responsibility for mutual exclusion is centralised with the creator of the (monitor for) resource.
-There is therefore, less scope for individual programmers to create synchronisation bugs.
-Critical section is within the monitor rather than duplicated in processes. Still not perfect though…
• Distributed management of resources:
-Each resource (or related group of resources) can be handled by a separate
monitor.
-If processes are requesting to run methods on the same monitor mutual exclusion can be enforced;
-If processes are requesting to run processes of two separate monitors they can
be executed concurrently.
• Fits well with OO design principles.
Lecture Topics
Motivation for Monitors;
Monitor Concept;
Monitors using semaphores;
Semaphores using monitors;
Producer consumer problem using monitors.
Canonical problems:
The Dining Philosophers Problem; The readers and writers problem
Concurrency in Java.
Train Bridge Example; Swing Threads.
Simple Example of a Monitor
monitor Integer
Integer n = 0;
method increment()
n = n + 1; method decrement()
n = n – 1;
p
q
p1: Integer.increment() p2: Integer.decrement()
q1: Integer.increment() q2: Integer.decrement()
• All methods in the monitor are executed in mutual exclusion; A process must acquire the lock for the monitor to execute a method.
• increment (decrement) cannot be executed by both processes at the same time;
• P cannot execute decrement whilst q executes increment and vice versa.
Implementing a Monitor Using Semaphores
class Monitor
semaphore s = 1;
//any required variables
method method1()
s.wait()
//actual method implementation s.signal()
method method 2() s.wait()
//actual method implementation
s.signal()
etc.
Those feeling pedantic might find issue with this, but it suffices to illustrate the point (read 6.7.2 of “Operating Systems Concepts if interested).
Simulating Semaphores using Monitors
monitor Semaphore
Integer s = k
method semaphoreWait()
while(s < 0)
wait() s=s–1
method semaphoreSignal() s=s+1
notifyAll()
P
q
loop forever:
p0: non-critical section
p1: Semaphore.semaphoreWait() p2: critical-section
p3: Semaphore.semaphoreSignal()
loop forever:
q0: non-critical section
q1: Semaphore.semaphoreWait() q2: critical-section
q3: Semaphore.semaphoreSignal()
Monitor wait() and notifyAll()
Maintain a set blocked of threads that are waiting.
wait():
-adds the current thread to the set blocked. -sets its status to blocked.
-releases the monitor lock.
notifyAll():
-Removes all process from the set blocked (if blocked is non empty);
-Sets their states to ready (whichever thread the scheduler selects to run first will acquire the lock,
the other processes will be blocked on entry).
Threads can only call wait/notifyAll/notify if they hold the monitor lock (i.e. inside the monitor).
wait(){
blocked = blocked U this;
this.status = blocked
lock.release()
}
notifyAll(){
while(blocked not empty){
p = blocked.remove();
p.status = ready;
}}
notifyAll() versus notify()
notifyAll():
-Removes all process from the set blocked (if blocked is non empty);
-Sets their states to ready (whichever thread the scheduler selects to run first will
acquire the lock, the other processes will be blocked on entry).
notify():
-selects and removes a process from the set blocked (if blocked is non empty); -Sets the state of that thread to ready (i.e. it is the next one allowed to execute).
notifyAll(){
while(blocked not empty){
p = blocked.remove();
p.status = ready; }}
notify(){
if(blocked not empty){
p = blocked.remove();
p.status = ready;
}}
Producer Consumer Problem using Monitors
monitor Buffer int[5] buffer int spaceUsed;
method addItem(int i)
while(spaceUsed == 5)
wait() buffer[spaceUsed] = i ++spaceUsed notifyAll()
method removeItem()
while(spaceUsed == 0)
wait()
i = buffer[spaceUsed] --spaceUsed notifyAll()
return i
p
q
loop forever:
p1: i <- produce
p2: Buffer.addItem(i)
loop forever:
q1: i <-Buffer.removeItem() q2: consume(i)
notifyAll() versus notify()
• Suppose that a producer calls notify() but it is another producer that is woken up The consumers remain blocked because they have not been awoken.
• Suppose, in a more general scenario, the thread selected to run by notify() then waits on some other condition.
The other threads cannot then run and acquire the monitor lock because they are in the blocked state.
• notifyAll() gets around this by waking up multiple threads, then if one thread were to wait on another condition, another thread will be in the ready queue, and can acquire the monitor lock and run;
However, in waking all threads and allowing the scheduler to select which one is running notifyAll() gives rise to more context switching.
• If you are certain that an arbitrary thread that is woken up will not become blocked then you can use notify(). In general though notifyAll() is safer (what if your code is extended later?), even though it gives rise to more overhead.
We have to Notify Producers of Empty and Consumers of Full
• Actually it would be useful if we could only wake up the processes that are actually waiting for the condition that is true.
• The classical monitor concept does allow for this.
• In classical monitors this is achieved by adding conditions to the
monitor on which processes can wait
Wait takes as an argument the condition for which the thread is waiting. Signal signals a specific condition.
monitor Buffer int[5] Buffer
int spaceUsed;
condition notEmpty condition notFull
method addItem(int i) while(spaceUsed = 5)
wait(notFull)
buffer[spaceUsed] = i
++spaceUsed
notifyAll(notEmpty)
method removeItem() while(spaceUsed == 0)
wait(notEmpty)
i = buffer[spaceUsed]
--spaceUsed
notifyAll(notFull)
return i
p
q
loop forever:
p1: i <- produce
p2: Buffer.addItem(i)
loop forever:
q1: i <-Buffer.removeItem() q2: consume(i)
Now maintain a separate queue for each condition.
notifyAll(cond) versus notify(cond)
notifyAll():
-Removes all process from the set cond (if cond is non empty);
-Sets their states to ready (whichever thread the scheduler selects to run first will acquire the lock, the other processes will be blocked on entry).
notify():
-selects and removes a process from the set cond (if cond is non empty);
-Sets the state of that thread to ready (i.e. it is the next one allowed to execute).
notify(cond){
if(cond not empty){
p = cond.remove();
p.status = ready;
}}
notifyAll(cond){
while(cond not empty){
p = cond.remove();
p.status = ready;
}}
Can we use a Queue instead of a Set for the condition variable?
It would only be worth doing this if we can call notify() and wake only the head of the queue:
If we are going to unblock all processes the order they are stored is irrelevant.
In the buffer consumer case if all processes waiting on the same condition are in the same queue, then yes we could use a queue and wake up the head of the queue:
Avoids the potential starvation caused by simply allowing the scheduler to decide which process to run.
In general though need to be careful: make absolutely sure that threads are waiting on the same condition.
Thread States w.r.t. Monitors
Waiting to Enter the monitor (E); Waiting to be notified (W); Executing notify (N)
E
N.B. in this case the process N currently holds the lock.
In Java priority is given to thread
N, with threads E and W having
equal priority:
E=W < N
W N
Monitor
• Monitors are an other higher level synchronisation mechanism and also more powerful than Semaphore.
• A monitor is an instance of a class that can be used safely by several threads by having methods that are executed with mutual exclusion. So at most one thread can execute a method of the monitor at the same time.
• Monitors have an other feature, the possibility to make a thread waiting for a condition by a condition variable. During the wait time, the thread temporarily gives up its exclusive access and must reacquire it after the condition has been met.
2/4/2020
Activity-1
What is/are the main difference(s) between Monitor and Semaphore synchronisation mechanisms ?
A. Unlike Semaphores, when using monitor, all the synchronization code is centralized in one location and the users of this code don’t need to know how it’s implemented- OOP concept of Encapsulation.
A. In monitor, the code doesn't depend on the number of processes like semaphores, instead it works for as many processes that want to use the monitor.
A. Unlike Semaphores, when using monitor, application programmers don’t need to worry about release something i.e like signal (semaphore), so they cannot forget to do it.
2/4/2020
BREAK TIME
10 minutes Break
2/4/2020
Lecture Topics
Motivation for Monitors;
Monitor Concept;
Monitors using semaphores; Semaphores using monitors;
Canonical problems:
The readers and writers problem.
The Dining Philosophers Problem (exercise).
Concurrency in Java.
Train Bridge Example; Swing Threads.
Readers and Writers Problem
Related to the critical section problem:
• Abstraction of reading from and writing to databases.
• There are two types of thread: reader and writer. -Many readers can access the database at once.
-Only one writer can access the database at once.
-No reader can access the database at the same time as a writer.
Next slide: a solution using monitors.
Reader-Writer solution using Monitor
monitor Buffer
int readerCount = 0 boolean writing = false
method startRead()
while(writing)
wait()
++readerCount;
method endRead() --readerCount;
notifyAll()
method startWrite()
while(writing ||
readerCount != 0)
wait()
writing = true;
method endWrite() writing = false;
notifyAll()
P
q
loop forever:
p1: startRead()
p2: read from database p3: endRead()
loop forever:
q1: startWrite()
q2: write to database q3: endWrite()
Breaking up Conditions
method startWrite() while(writing ||
readerCount != 0)
wait()
writing = true;
method startWrite() while(writing)
wait()
while(readerCount != 0)
wait()
writing = true;
• On the left both conditions are checked together so we know both hold when we set writing = true; • On the right we could have violation of our required properties:
-Wait for writing to be false;
-Continue to wait for reader count to be zero;
It’s possible that some other writer, also waiting for reader count to be zero, is scheduled before us when reader count becomes zero;
-It starts writing but has not yet finished.
-This writer is awoken, checks reader count is still zero and continues to write.
Two writers are now writing simultaneously!.
Writer Starvation
monitor Buffer
int readerCount = 0 boolean writing
method startRead() while(writing)
wait()
++readerCount;
method endRead() --readerCount;
notifyAll()
method startWrite() while(writing ||
readerCount != 0)
wait()
writing = true;
method endWrite()
writing = false;
notifyAll()
There is a real risk here that writers will be starved:
so long as one reader is reading other readers will be able to enter while writers will be blocked.
Writer Preference
monitor Buffer int readerCount
boolean writing, waitingToWrite = false
method startRead() while(writing ||
waitingToWrite)
wait()
++readerCount;
method endRead()
--readerCount;
notifyAll()
method startWrite() while(writing ||
readerCount != 0)
waitingToWrite = true
wait()
writing = true;
waitingToWrite = false
method endWrite() writing = false; notifyAll()
But what about the readers?
monitor Buffer
int readerCount, waitingReaders = 0
boolean writing, waitingToWrite, readerTurn = false
method startRead()
while(writing || (waitingToWrite && !readerTurn))
++waitingReaders
wait()
--waitingReaders
++readerCount; readerTurn = false
method startWrite()
waitingToWrite = true
wait()
writing = true
waitingToWrite = false
readerTurn = true;
//end read and end write as before
while(writing || readerCount != 0 || (waitingReaders > 0 && readerTurn))
Monitor Solution to the Dining Philosophers Problem
In the exercises.
Lecture Topics
Motivation for Monitors;
Monitor Concept;
Monitors using semaphores; Semaphores using monitors;
Canonical problems:
The readers and writers problem.
The Dining Philosophers Problem (exercise).
Concurrency in Java.
Train Bridge Example; Swing Threads.
Monitors in Java
• Java’s primary means of providing solutions to mutual exclusion is via monitors.
• Monitors are not explicitly represented, rather every class can be thought of as a
monitor.
• Unlike traditional monitors not all methods are required to be mutually exclusive.
• Instead methods that the programmer requires to be executed in mutual exclusion are marked using the keyword synchronized.
Why not just make everything automatically synchronized?
Answer: Then no two methods could ever run at the same time on any object even if mutual exclusion is not required.
Object: Java API
protected Object clone()
Creates and returns a copy of this object.
boolean equals(Object obj)
Indicates whether some other object is “equal to” this one.
protected void finalize()
Called by the garbage collector on an object when garbage collection determines that there are no more references to the object.
Class getClass()
Returns the runtime class of this Object.
int hashCode()
Returns a hash code value for the object.
void notify()
Wakes up a single thread that is waiting on this object’s monitor.
void notifyAll()
Wakes up all threads that are waiting on this object’s monitor.
String toString()
Returns a string representation of the object.
void wait()
Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object.
void wait (long timeout)
Causes the current thread to wait until either another thread invokes the notify() method or the notifyAll() method for this object, or a specified amount of time has elapsed.
wait(long timeout, int nanos)
Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object, or some other thread interrupts the current thread, or a certain amount of real time has elapsed.
Java Thread Lifecycle
run()
(Scheduler)
Runnable
sleep() ends notify() notifyAll()
Running
run() ends
Terminated
Thread()
Created
Start()
yield()
(Scheduler) sleep() or
wait()
Blocked
Activity-2
Which of the following statements are TRUE about Monitors’ implementation in java? :
A. In Java, monitor is a synchronization mechanism placed at class hierarchy root: java.lang.Object. B. There is a Java built-in class Monitor that is part of javax.management,monitor.Monitor
that the application programmer can inherit by using the extend command.
C. There are wait(), notify(), and notifyAll() methods that will also use object’s monitor to
communication among different thread.
D. In Java, all the monitor methods must use the keyword synchronised.
2/4/2020
Single-Track Bridge Example
Problem:
• A bridge running east to west, has only room for a single lane of traffic.
• Traffic must therefore not enter the bridge going in opposite directions.
• The roads on either side are two-way so traffic can pass on those.
What happens in the code on the next slide?
public class Vehicle extends
Thread(){
Bridge bridge; String name;
boolean westbound;
public Vehicle(Bridge toCross,
boolean west, String n){ bridge = toCross;
name = n; westbound = west;
}
public void run(){
bridge.cross(this); }
public String toString(){
String dir = “west ”;
if(!westbound) dir = “east ”;
return name + “ going “ + dir;
}}
public class Bridge(){
boolean westbound = false;
public void cross(Vehicle v){ System.out.println(v +
“entering bridge”);
try{
Thread.sleep(100);
} catch (InterruptedException e){ e.printStackTrace();
}
System.out.println(v +
}}
“leaving bridge”);
public static void main (String[] args){
Bridge b = new Bridge(); boolean dir = false;
for(int i = 0; i < 5; ++i){
Thread t = new Vehicle(b, dir, “car” + i);
t.start();
dir = !dir;}}
What Happens?
car0 going east entering bridge
car2 going east entering bridge car1 going west entering bridge car3 going west entering bridge car4 going east entering bridge car0 going east leaving bridge car2 going east leaving bridge car1 going west leaving bridge car3 going west leaving bridge car4 going east leaving bridge
• Nothing prevents the cars from entering the bridge simultaneously in opposite directions.
• Can we fix it first so that only one car can use the bridge at once? Yes, easily!
public class Vehicle extends
Thread(){
Bridge bridge; String name;
boolean westbound;
public Vehicle(Bridge toCross,
boolean west, String n){ bridge = toCross;
name = n; westbound = west;
}
public void run(){
bridge.cross(this); }
public String toString(){
String dir = “west ”;
if(!westbound) dir = “east ”;
return name + “ going “ + dir;
}}
public class Bridge(){
boolean westbound = false;
public synchronized void cross(Vehicle v){
System.out.println(v +
“entering bridge”);
try{
Thread.sleep(100);
} catch (InterruptedException e){
e.printStackTrace();
}
System.out.println(v +
}}
“leaving bridge”);
public static void main (String[] args){
Bridge b = new Bridge(); boolean dir = false;
for(int i = 0; i < 5; ++i){
Thread t = new Vehicle(b, dir, “car” + i);
t.start();
dir = !dir;}}
Fixed!
car1 going west entering bridge
car1 going west leaving bridge
car4 going east entering bridge
car4 going east leaving bridge
car2 going east entering bridge
car2 going east leaving bridge
car0 going east entering bridge
car0 going east leaving bridge
car3 going west entering bridge
car3 going west leaving bridge
Done.
But... there are unnecessary delays:
actually as many cars as we want could enter the bridge (length dependent) so long as they are going in the same direction;
Let’s say 1 car can go westbound and up to 3 cars can go eastbound at any given time, but still cars cannot cross simultaneously in opposite directions.
Allowing Multiple Cars
public class Bridge(){
int carCount = 0;
boolean westbound = 0;
public synchronized void enterBridge(Vehicle v){
//enter if it is okay to do so, if not wait }
public void cross(Vehicle v){
//cross the bridge
}
public synchronized void exitBridge(Vehicle v){
//leave and notify all waiting threads
}
}
We cannot synchronize cross() since more than one car can now use the bridge at once.
Instead we need to split into, enter, cross and exit, so we can check on entrance and exit.
This is a general idiom for multiple threads using a resource at once.
Allowing Multiple Cars
public class Bridge{
int carCount = 0; boolean westbound = false; public synchronized void enterBridge(Vehicle v){
while((v.getWestbound() != westbound && carCount > 0) || (!v.getWestbound() && carCount > 2) || (v.getWestbound() && carCount > 0)) {
try{ wait();
} catch (InterruptedException e){ e.printStackTrace();} }
westbound = v.getWestbound(); //set direction to your direction ++carCount; //increment cars using bridge
System.out.println(v + “ entering the bridge”); } …
Car must wait if:
It is not going in the same direction the bridge is set to and there are cars on the bridge (i.e. a car is on the bridge going the other way); OR
It is going eastbound and there are more than 2 cars on the bridge; OR
It is going westbound and there is a car on the bridge.
Allowing Multiple Cars
//int carCount = 0; boolean westbound = false; public void crossBridge(){
try{
Thread.sleep(100);
} catch (InterruptedException e){ e.printStackTrace();
} }
public synchronized void exitBridge(Vehicle v){ –carCount;
System.out.println(v + “ exiting the bridge”); notifyAll();
} }
Cross just sleeps to simulate taking some time to cross.
Exit decrements carCount and must then call notifyAll() to see if anyone who is waiting can now enter.
Modifying Run
public void run(){ bridge.enterBridge(this); bridge.crossBridge(); bridge.exitBridge(this);
}
Now all cars must call enterBridge(this), then crossBridge() then exitBridge(this). Also added the getWestbound() method.
Main Method
public static void main (String[] args){
Bridge b = new Bridge(); boolean dir = false; for(int i = 0; i < 5; ++i){
Thread t = new Vehicle(b, dir, "car" + i); t.start();
dir = !dir;
try{
Thread.sleep(70);
} catch (InterruptedException e){
e.printStackTrace();
}
} }
Note I made the main method sleep between creating threads:
Otherwise all threads are created during the first bridge crossing;
Therefore all the eastbound traffic goes across followed by all westbound and the output doesn’t demonstrate the intended function.
We could fix this another way similar to how we did for readers/writers.
Output
car0 going east entering the bridge car0 going east exiting the bridge car1 going west entering the bridge car1 going west exiting the bridge car2 going east entering the bridge car4 going east entering the bridge car2 going east exiting the bridge car4 going east exiting the bridge car3 going west entering the bridge car3 going west exiting the bridge
Interestingly here there is nothing to stop the cars exiting the bridge in a different order to which they entered.
We could prevent this but it doesn’t really matter we can just look at the entrance order and derive the exit order from that.
Really we only need exit to show the code works as desired, and so that we can call notifyAll().
BREAK TIME
10 minutes Break
2/4/2020
Lecture Topics
Motivation for Monitors;
Monitor Concept;
Monitors using semaphores; Semaphores using monitors;
Canonical problems:
The readers and writers problem.
The Dining Philosophers Problem (exercise).
Concurrency in Java.
Train Bridge Example;
Swing Threads.
Inbuilt Concurrency in Swing
• When working with Swing Java automatically uses threads to allow parallelism to ensure that GUIs are responsive.
This means you can get concurrency bugs without even having explicitly created a thread;
• Swing has a special thread: the event dispatch thread.
All event-handling code is executed in this thread (this prevents threading issues between event handlers).
Most code that interacts with the Swing framework must also execute on this thread.
• This automatically runs in parallel with your main thread (and any others that you create from it) without you doing anything.
• Can also implement swing worker threads to perform time-consuming tasks (e.g. to load background images).
Surprising Problems
public class BallPanel extends JPanel {
ArrayList
Random r;
public BallPanel(){
balls = new ArrayList(); setPreferredSize(new Dimension(600,600)); r = new Random();
for(int i = 0; i < 50; ++i){
balls.add(new Ball(r));
}
} ...
Here is a JPanel that we have extended and on which we will draw balls, the ball constructor creates a ball object with random x,y,width, height.
Painting
@Override
public void paintComponent(Graphics g){
System.out.println("paint " + Thread.currentThread().getName()); super.paintComponent(g);
g.setColor(Color.black);
g.drawRect(0, 0, 600, 600);
for(Ball b : balls){
g.setColor(b.getColour());
g.fillOval(b.getX(), b.getY(), b.getWidth(), b.getHeight());
}
}
Overriding paint replaces what would normally be drawn on the JPanel with what we want to draw, in this case our balls.
When paintComponent is called it will be run in the event dispatch thread, in parallel with our code. From the println we see: paint AWT-EventQueue-0
Moving Balls Around
public void animate(){
System.out.println("animate " + Thread.currentThread().getName()); Ball fiveBounce = null;
for(Ball b : balls){
b.move();
if(b.getBounces() >= 5) fiveBounce = b;
}
Thread.sleep(10); //surrounded by try catch
repaint(); //what happens if we call paint(getGraphics());? if(fiveBounce != null){
balls.remove(fiveBounce);
} }
This is non-swing code so will run in the main thread.
It moves each ball (by 1 to 3 pixels horizontally and vertically bouncing if the side is hit, see
ball.move()) then calls repaint() to draw the new positions. Each ball is removed from the list once it has bounced 5 times.
What Happens?
Exception in thread “AWT-EventQueue-0”
java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:819) at java.util.ArrayList$Itr.next(ArrayList.java:791)
at bouncingballs.BallPanel.paintComponent(BallPanel.java:37)
at javax.swing.JComponent.paint(JComponent.java:1054)
at javax.swing.JComponent.paintToOffscreen(JComponent.java:5221)
at javax.swing.RepaintManager$PaintManager.paintDoubleBuffered(RepaintManager.java:1512) at javax.swing.RepaintManager$PaintManager.paint(RepaintManager.java:1443)
at javax.swing.RepaintManager.paint(RepaintManager.java:1236)
at javax.swing.JComponent._paintImmediately(JComponent.java:5169)
at javax.swing.JComponent.paintImmediately(JComponent.java:4980)
at javax.swing.RepaintManager$3.run(RepaintManager.java:796)
at javax.swing.RepaintManager$3.run(RepaintManager.java:784)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:76)
at javax.swing.RepaintManager.paintDirtyRegions(RepaintManager.java:784)
at javax.swing.RepaintManager.paintDirtyRegions(RepaintManager.java:757)
at javax.swing.RepaintManager.prePaintDirtyRegions(RepaintManager.java:706)
at javax.swing.RepaintManager.access$1000(RepaintManager.java:62)
at javax.swing.RepaintManager$ProcessingRunnable.run(RepaintManager.java:1651)
at java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:251)
at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:727)
at java.awt.EventQueue.access$200(EventQueue.java:103)
at java.awt.EventQueue$3.run(EventQueue.java:688)
at java.awt.EventQueue$3.run(EventQueue.java:686)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:76)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:697)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:242) at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:161)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:150) at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:146)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:138)
at java.awt.EventDispatchThread.run(EventDispatchThread.java:91)
What Happened?
Paint was doing this in the event dispatch thread:
for(Ball b : balls){
g.setColor(b.getColour());
g.fillOval(b.getX(), b.getY(), b.getWidth(), b.getHeight());
}
… and in the middle of that animate did this in the main thread
balls.remove(fiveBounce);
If a list is modified during iteration a ConcurrentModificationException is thrown, which is exactly
what happened.
Fixing it
@Override
public synchronized void paintComponent(Graphics g){
//etc. }
Paint will still run in a separate thread but now must not execute in parallel with removeBall.
public synchronized void removeBall(Ball toRemove){ balls.remove(toRemove);
}
Make animate call removeBall(fiveBounces) instead of removing the ball.
Don’t just synchronize the whole of animate because then paint can’t run even when it is sleeping.
An Event Handler
//window constructor
startAgain = new JButton(“Start Again”); add(startAgain,BorderLayout.SOUTH); startAgain.addActionListener(new Restarter());
class Restarter implements ActionListener{ @Override
public void actionPerformed(ActionEvent e) {
System.out.println(“Action Listener ” + Thread.currentThread().getName());
} }
When we invoke the ActionListener by clicking the button we see: Action Listener AWT-EventQueue-0
It is running in the event dispatch thread, the same one as paint.
Summary
Motivation for Monitors;
Monitor Concept;
Monitors using semaphores; Semaphores using monitors;
Canonical problems:
The readers and writers problem.
The Dining Philosophers Problem (exercise).
Concurrency in Java.
Train Bridge Example; Swing Threads.
Contact details/for more information
Sahar.al-sudani@kcl.ac.uk
Thanks for you Attention !
© 2020 King’s College London. All rights reserved
5CCS12OSC – Operating Systems and Concurrency : DeadLock
Dr Sahar Al-Sudani,
Spring, 2020
2/12/2020
Lecture Topics
What is Deadlock?
Necessary Conditions for Deadlock; Handling Deadlock:
Prevention;
Detection;
Recovery.
Deadlock
Images Wikipedia
World’s worst traffic jam: on the Beijing-Zhangjiakou highway in China traffic congestion stretched more than 100 kilometres (62 mi) from 14th to 26th August 2010 including at least 11 days of total gridlock, it took some drivers 5 days to cross this stretch of highway.
Deadlock
Single track bridge deadlock:
Two cars enter straight on;
We saw last time how hard we worked to avoid this.
If it happens can be resolved by one of the cars on the bridge reversing, but then, of course the cars behind it might also need to reverse.
In the Computer World
Three processes want to copy a DVD:
Each one acquires the resource of a single DVD drive;
Each then waits for another to become available.
Of course it won’t do because no process can get one to write and complete it’s operation.
Similar to the philosophers and their forks.
Deadlock with Semaphores
Semaphore S1 (1, Ø), Semaphore S2 (1, Ø)
p
q
loop_forever
p1: non-critical section p2: wait(S1)
p2: wait(S2)
p3: critical section p4: signal(S2)
p4: signal(S1)
loop_forever
q1: non-critical section q2: wait(S2)
q2: wait(S1)
q3: critical section q4: signal(S1)
q4: signal(S2)
This interleaving gives rise to deadlock:
p1,q1,p2,q2
General rule: request semaphores in the same order in every thread.
Program Concurrently with Care
The risk of deadlock is high when writing concurrent programs.
Deadlock occurs in interaction between threads, so the cause is not always visible in a single part of the code.
You may have to run your code for some time before it deadlocks if the deadlock is rather improbable.
The longer your program will be left to run for the more risk there is it will deadlock if there is potential for it to do so.
Lecture Topics
What is Deadlock?
Necessary Conditions for Deadlock;
Handling Deadlock:
Prevention; Detection; Recovery.
System Model
We will consider a number of processes (or threads if you prefer); A number of resources:
Physical resources: e.g. Disk Semaphores/locks.
Each process requests resources as it needs to use them;
And releases them when it has finished with them;
Some tasks may need more than one resource;
We may have multiple instances of each resource (e.g. DVD writer).
Necessary Conditions for Deadlock
Coffman conditions: all must hold for deadlock to be possible:
1. Mutual exclusion: only one process at a time can use an (instance of a) resource.
2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.
3. No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that: P0 is waiting for a resource that is held by P1,
P1 is waiting for a resource that is held by P2,
…, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.
Lecture Topics
What is Deadlock?
Necessary Conditions for Deadlock; Handling Deadlock:
Prevention;
Detection;
Recovery.
What do Operating Systems Do?
“Ostrich” Algorithm.
Ignore deadlock.
Assume that programmers will write correct programs and therefore it won’t be a problem.
Why?
– Deadlock detection and prevention are expensive (time and resource, not money…).
– Deadlock is rare: if deadlock occurs quickly enough in a given program the programmer will usually notice it and fix it.
Resource Allocation Graphs
• A graph where there is a vertex representing each process, and one representing each resource.
Request edge: An edge from a process to a resource means that process has requested an instance of that resource;
Assignment edge: An edge from a resource to a process means that process currently holds an instance of that resource.
• When a process gets a resource it has requested the request edge is removed and the assignment edge is added.
• Convention: represent resources with rectangles and processes with circles.
Graph Components
A process
Resource with 4 instances
P1 requests an instance of R1. P1 holds an instance of R1
Pi
Rj
Pi
Rj
Resource Allocation Graph
Defined by three sets:
P = {P1,P2,P3},
R = {R1,R2,R3,R4},
E ={P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1,R3 → P3} And the number of instances of each resource: R1:1,R2:2,R3:1,R4:3
Resource Allocation Graph with Deadlock
Resource Allocation Graph with a Cycle but no Deadlock
Cycles in Resource Allocation Graphs
• If there are no cycles in the graph then there is no deadlock.
• If there are cycles in the graph:
-If there is only one instance of each resource then there is deadlock.
-If there are multiple instances of resources then there is a possibility of deadlock.
Handling Deadlocks
Prevention: We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state.
Cure: We can allow the system to enter a deadlocked state, detect it, and recover.
Ignorance: Ostrich approach, We ignore the problem altogether and pretend that deadlocks never occur in the system.
Lecture Topics
What is Deadlock?
Necessary Conditions for Deadlock; Handling Deadlock:
Prevention;
Detection;
Recovery.
Deadlock Prevention
Break one of the conditions required for deadlock.
Mutual Exclusion: not easy since if a resource needs mutual exclusion that must be respected; however we can reduce the risk of a problem by only enforcing mutual exclusion on resources that absolutely require it, rather than on all resources if it is not necessary.
Hold and Wait: Guarantee that whenever a process requests a resource it does not hold any others:
Process must request and hold all its resources before it can begin; Or process can only request resources when it has none.
Problems: low resource utilisation; possible starvation.
Deadlock Prevention II
Pre-emption:
if a process requests a resource that cannot be allocated immediately, then it must immediately release all resources it holds (pre-emption).
A list of which resources the process is waiting for is maintained (including the pre- empted ones);
The process is only restarted when all the resources it is waiting for are available.
Circular wait:
Impose a total ordering on resource types and make all processes request resources in increasing order.
BREAK TIME
10 minutes Break
2/12/2020
Deadlock Avoidance
To avoid deadlock extra information about processes is needed:
e.g. max number of resources of each type a process will need. Is it realistic to assume that we know this?
We can use the resource allocation state of a system to enforce the condition that we will never permit a circular wait.
• Single instance of each resource, we can check this using a resource allocation graph;
• Multiple instances of each resource, we must use the Banker’s algorithm.
Resource allocation state is defined by the number of available and allocated resources along with the maximum number of resources each process can need.
Safe State
Each time a process requests a resource the system must decide if allocation of that resource leaves the system in a safe state.
System is in safe state if there exists a sequence
Therefore a process can never be holding a resource, but waiting for a process with a higher number to release a resource.
This means circular wait cannot occur: Pj is allowed to hold resources and wait for Pi but Pi can’t hold resources and wait for Pj.
Note this is not a fixed number for each process, but rather at any point processes must be able to be assigned numbers such that the condition holds.
Safe States and Deadlock
If a system is in a safe state it cannot deadlock;
If a system is in an unsafe state it may deadlock;
We can avoid deadlock by preventing unsafe states.
Resource Allocation Graph Method
only works with single resource instances Add a new type of edge to the RAG: a claim edge.
Claim edges Pi Rj indicate that a process Pi can request a resource Ri . That is, the system specified apriori that process may require that resource.
Illustrated with a dashed line.
Claim edge becomes an assignment edge when Ri is allocated to Pi. Assignment edge reverts to a claim edge when Pi releases Ri.
All resources must be requested apriori i.e. all claim edges are known and put in the graph initially.
Resource Allocation Graph Algorithm
If a process Pi requests a resource Rj. The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph
Resource Allocation Graphs
Safe State Unsafe State
Basic Idea: Safety Check
1. Find a process for which there are sufficient available resources now to meet its maximum need.
2. Simulate executing the process i.e. release all its resources (make them to available);
3. Go back to 1;
4. If all processes have completed execution the system is safe.
5. If you cannot find such a process, but there are still processes that
haven’t executed, then the system is unsafe.
Abuse of Syntax
Array1 >= Array2 (both same length) means:
Array1[i] > Array2[i] for all i.
Array1 += Array2 means:
Array1[i] += Array2[i] for all i;
Banker’s Algorithm
Multiple instances
Each process must a priori claim maximum use
When a process requests a resource it may have to wait
When a process gets all its resources it must return them in a finite amount of time
Data Structures for the Banker’s Algorithm
Let n = number of processes, and m = number of resources types.
Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj
Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task
Need [i,j] = Max[i,j] – Allocation [i,j]
Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
2. Find an i such that both: Finish [i] = false
Needi Work
If no such i exists, go to step 4
3. Work = Work + Allocationi Finish[i] = true
go to step 2
4. If Finish [i] == true for all i, then the system is in a safe state
Example of Banker’s Algorithm
5 processes P0 through P4; 3 resource types:
A (10 instances), B (5 instances), and C (7 instances) Snapshot at time T0:
P0 P1 P2 P3 P4
Allocation Max Available A BC A B C A B C
0 1 0 7 5 3 3 3 2
2 0 0 3 0 2 2 1 1 0 0 2
3 2 2 9 0 2 2 2 2
4 3 3
Example (Cont.)
The content of the matrix Need is defined to be Max – Allocation
Need AB C
P07 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1
Safety Algorithm
1.
2.Find and i such that both:
Work = (3,3,2) Finish [F,F,F,F,F]
Allocation Max Available
Need ABC
P07 4 3
Finish [i] = false Needi Work
If no such i exists, go to step 4
3. Work = (3,3,2) + P1(2,0,0)=(5,3,2)
Finish[F,T,F,F,F] go to step 2
Work = (5,3,2) + P3(2,1,1)=(7,4,3) Finish[F,T,F,T,F]
go to step 2
….
….
4. If Finish [i] == true for all i, then the system is in a safe state
A BC P0010 P1200 P23 0 2 P32 1 1 P4002
A B C
7 5 3 3 22
90 2 2 22 43 3
A B C
3 32
The system is in a safe state since the sequence < P , P
satisfies safety criteria 1 3 4 2 0
P 1 22
P1 6 0 0
P20 1 1
P34 3 1 4
, P , P , P >
Activity-1
2/12/2020
BREAK TIME
10 minutes Break
2/12/2020
Resource-Request Algorithm for Process Pi
Request = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj. For example : P1 Request (1,0,2)
1. If Requesti Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim
2. If Requesti Available, go to step 3. Otherwise Pi must wait, since resources are not available
3. Pretend to allocate requested resources to Pi by modifying the state as follows: Available = Available – Request;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
If safe the resources are allocated to Pi
If unsafe Pi must wait, and the old resource-allocation state is restored
Example: P1 Request (1,0,2)
Check that Request Need (that is, (1,0,2) (1,2,2) true Check that Request Available (that is, (1,0,2) (3,3,2) true
Available = Available – Requesti : (3,3,2)-(1,0,2)= (2,3,0) Allocationi = Allocationi + Requesti :(2,0,0)+(1,0,2)= (3,0,2) Needi = Needi – Requesti :(1,2,2)-(1,0,2) = (0,2,0)
P0 P1 P2 P3 P4
Allocation AB C
0 1 0
3 0 2
3 0 1
2 1 1
0 0 2
Need A B C 7 4 3
0 2 0
6 0 0 0 1 1 4 3 1
Available AB C
2 3 0
Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirement Can request for (3,3,0) by P4 be granted?
Can request for (0,2,0) by P0 be granted?
Activity-2
In a real computer system, neither the resources available nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the banker’s algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances?
a) Increase Available (new resources added).
Answer: This could safely be changed without any problems.
b) Decrease Available (resource permanently removed from system).
Answer: This could have an effect on the system and introduce the possibility of deadlock as the safety of the system assumed there were a certain number of available resources.
2/12/2020
Activity-2
c) Increase Max for one process (the process needs or wants more resources than allowed). Answer: This could have an effect on the system and introduce the possibility of deadlock.
d)Decrease Max for one process (the process decides it does not need that many resources).
Answer: This could safely be changed without any problems.
e) Increase the number of processes.
Answer: This could be allowed assuming that resources were allocated to the new process(es) such that the system does not enter an unsafe state.
f) Decrease the number of processes.
This could safely be changed without any problems.
2/12/2020
Lecture Topics
What is Deadlock?
Necessary Conditions for Deadlock; Handling Deadlock:
Prevention;
Detection;
Recovery.
Deadlock Detection
Instead of preventing deadlock we could allow deadlock to happen and then detect and resolve it.
If there is a single instance of each resource then we can look for cycles in the resource allocation graph;
If there are multiple instances of each resource, we can use a slight variation of the Banker’s algorithm:
Instead of using the maximum number of resources a process might need (max), use the resources a process is currently requesting (request).
Banker’s Algorithm Deadlock Detection
1. Let Work and Finish be arrays of length m and n, respectively. Initialize: Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
If Pi has no resources currently allocated Finish [i] = true.
2. Find an i such that both: Finish[i] = false and Request[i] Work
If no such i exists, go to step 4
3. Work = Work + Allocation[i]
Finish[i] = true
go to step 2
4. If Finish [i] == true for all i, then the system is in a safe state otherwise if Finish[i] == false then pi is deadlocked.
Optimistic Assumption
2. Find and i such that both: Finish[i] = false and Request[i] Work
If no such i exists, go to step 4
3. Work = Work + Allocation[i] Finish[i] = true
go to step 2
• We assume that if Pi has sufficient resources to continue now it will complete.
• But actually it may require to request more resources in the future.
• That is okay, however, since we will detect that deadlock when those resources are requested.
Example
Allocation R0 R1 R2
Requested R0 R1 R2
Work
R0 R1 R2
010
2
0
0
3
0
3
2
1
1
0
0
2
0
0
0
2
0
1
0
0
1
1
0
0
0
0
2
0
0
0
P0 P1 P2 P3 P4
P0 P1 P2 P3 P4
Finished
P0 P1 P2 P3 P4
F
F
F
F
F
Example
Allocation R0 R1 R2
Requested R0 R1 R2
Work
R0 R1 R2
0
1
0
200
3
0
3
2
1
1
0
0
2
0
0
0
2
0
1
0
0
1
1
0
0
0
0
2
0
1
0
P0 P1 P2 P3 P4
P0 P1 P2 P3 P4
Finished
P0 P1 P2 P3 P4
T
F
F
F
F
When to Call Detection Algorithm
When, and how often, to invoke depends on:
How often a deadlock is likely to occur?
How many processes will need to be rolled back?
• one for each disjoint cycle
If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock
Now we have detected a deadlock how can we recover?
Lecture Topics
What is Deadlock?
Necessary Conditions for Deadlock; Handling Deadlock:
Prevention;
Detection;
Recovery.
Recovery From Deadlock: Process Termination
Abort all deadlocked processes
Abort one process at a time until the deadlock cycle is eliminated
In which order should we choose to abort?
• Priority of the process
• How long process has computed, and how much longer to completion
• Resources the process has used
• Resources process needs to complete
• How many processes will need to be terminated
• Is process interactive or batch?
Recovery from Deadlock: Resource Pre-emption
Select a process and take resources away from it to break the deadlock. Rollback – return to some safe state, restart process from that state Selecting a victim – minimize cost
Starvation – same process may always be picked as victim, include number of rollbacks in cost factor
Activity- 3
2/12/2020
Summary
What is Deadlock?
Necessary Conditions for Deadlock; Handling Deadlock:
Prevention;
Detection;
Recovery.
Contact details/for more information
Sahar.al-sudani@kcl.ac.uk
© 2019 King’s College London. All rights reserved
Memory-Management Strategies
Operating System Concepts with Java – 8th Edition 8.1 Silberschatz, Galvin and Gagne ©2009
Objectives
To provide a detailed description of various ways of organizing memory hardware.
To discuss various memory-management techniques, including paging and segmentation
Operating System Concepts with Java – 8th Edition 8.2 Silberschatz, Galvin and Gagne ©2009
Memory Management
Background
Dynamic Linking and Dynamic Loading Swapping
Contiguous Memory Allocation
Paging
Structure of the Page Table
Segmentation
Operating System Concepts with Java – 8th Edition 8.3
Silberschatz, Galvin and Gagne ©2009
Background
Program must be brought (from disk) into memory and placed within a process for it to be run
Main memory and registers are only storage CPU can access directly
Registers are built into CPU. Register access in one CPU clock (or less)
Main memory can take many cycles. Therefore processor need to stall.
Cache sits between main memory and CPU registers
Protection of memory required to ensure correct operation
Operating System Concepts with Java – 8th Edition 8.4 Silberschatz, Galvin and Gagne ©2009
Base and Limit Registers
A pair of base and limit registers define the logical address space
• To protect memory space, the CPU hardware compares every address generated in the user mode with the registers.
• Any attempt by a program executing in user mode to access operating-system memory or other user’s memory results in a trap to the operating system, which treats the attempt as fatal error.
Operating System Concepts with Java – 8th Edition 8.5
Silberschatz, Galvin and Gagne ©2009
Logical vs. Physical Address Space
The concept of a logical address space that is bound to a separate physical address space is central to proper memory management
Logical address – generated by the CPU; also referred to as virtual address
Physical address – address seen by the memory unit
Operating System Concepts with Java – 8th Edition 8.6 Silberschatz, Galvin and Gagne ©2009
Memory-Management Unit (MMU)
Hardware device that maps virtual to physical address
In MMU scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory
The user program deals with logical addresses; it never sees the real physical addresses
The memory mapping hardware converts logical addresses into physical addresses.
Operating System Concepts with Java – 8th Edition 8.7 Silberschatz, Galvin and Gagne ©2009
Dynamic relocation using a relocation register
Operating System Concepts with Java – 8th Edition 8.8 Silberschatz, Galvin and Gagne ©2009
Dynamic Loading
Routine is not loaded until it is called
Better memory-space utilization; unused routine is never loaded
Useful when large amounts of code are needed to handle infrequently occurring cases
Relocatable linking loader is called to load the desired routine. This is happens when a call make to a routine and it is not in the main memory.
No special support from the operating system is required implemented through program design.
It is the responsibility of the user to design their programs to take advantage of the libraries provided by OS that supports dynamic loading.
Operating System Concepts with Java – 8th Edition 8.9 Silberschatz, Galvin and Gagne ©2009
Dynamic Linking
Linking postponed until execution time
Small piece of code, stub, used to locate the appropriate memory-resident
library routine
Stub replaces itself with the address of the routine, and executes the routine
Operating system needed to check if routine is in processes’ memory address
Dynamic linking is particularly useful for libraries
System also known as shared libraries
Operating System Concepts with Java – 8th Edition 8.10 Silberschatz, Galvin and Gagne ©2009
Swapping
A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution
Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed
Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped
Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows)
System maintains a ready queue of ready-to-run processes which have memory images on disk
Operating System Concepts with Java – 8th Edition 8.11 Silberschatz, Galvin and Gagne ©2009
Schematic View of Swapping
Operating System Concepts with Java – 8th Edition 8.12 Silberschatz, Galvin and Gagne ©2009
Contiguous Allocation
Main memory usually into two partitions:
Resident operating system, usually held in low memory with
interrupt vector
User processes then held in high memory
Relocation registers used to protect user processes from each other, and from changing operating-system code and data
Base register contains value of smallest physical address
Limit register contains range of logical addresses – each
logical address must be less than the limit register
MMU maps logical address dynamically
Operating System Concepts with Java – 8th Edition 8.13 Silberschatz, Galvin and Gagne ©2009
Hardware Support for Relocation and Limit Registers
Operating System Concepts with Java – 8th Edition 8.14 Silberschatz, Galvin and Gagne ©2009
Contiguous Allocation (Cont)
Multiple-partition allocation
Hole – block of available memory; holes of various size are
scattered throughout memory
When a process arrives, it is allocated memory from a hole large enough to accommodate it
Operating system maintains information about: a) allocated partitions b) free partitions (hole)
OS
process 5
process 8
process 2
OS
process 5
process 2
OS
process 5
process 9
process 2
OS
process 5
process 9
process 10
process 2
Operating System Concepts with Java – 8th Edition 8.15 Silberschatz, Galvin and Gagne ©2009
Dynamic Storage-Allocation Problem
How to satisfy a request of size n from a list of free holes First-fit: Allocate the first hole that is big enough
Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
Produces the smallest leftover hole
Worst-fit: Allocate the largest hole; must also search entire list
Produces the largest leftover hole
Simulations have shown that both first-fit and best-fit better than
worst-fit in terms of speed and storage utilization.
Neither first fit nor best fit is clearly better than the other in terms of storage utilization, but first first is generally faster.
Operating System Concepts with Java – 8th Edition 8.16 Silberschatz, Galvin and Gagne ©2009
Fragmentation
External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous
Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used
Reduce external fragmentation by compaction
Shuffle memory contents to place all free memory together in
one large block
Compaction is possible only if relocation is dynamic, and is done at execution time
Operating System Concepts with Java – 8th Edition 8.17 Silberschatz, Galvin and Gagne ©2009
Paging
Logical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available
Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8,192 bytes)
Divide logical memory into blocks of same size called pages
Keep track of all free frames
To run a program of size n pages, need to find n free frames and load program
Set up a page table to translate logical to physical addresses
Internal fragmentation
Operating System Concepts with Java – 8th Edition 8.18 Silberschatz, Galvin and Gagne ©2009
Address Translation Scheme
Address generated by CPU is divided into:
Page number (p) – used as an index into a page table which
contains base address of each page in physical memory
Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit
page number page offset
m-n n
For given logical address space 2m and page size 2n
p
d
Operating System Concepts with Java – 8th Edition 8.19 Silberschatz, Galvin and Gagne ©2009
Paging Hardware
Operating System Concepts with Java – 8th Edition 8.20 Silberschatz, Galvin and Gagne ©2009
Paging Model of Logical and Physical Memory
Operating System Concepts with Java – 8th Edition 8.21 Silberschatz, Galvin and Gagne ©2009
Paging Example
32-byte memory and 4-byte pages
Operating System Concepts with Java – 8th Edition 8.22 Silberschatz, Galvin and Gagne ©2009
Free Frames
Before allocation
After allocation
Operating System Concepts with Java – 8th Edition 8.23 Silberschatz, Galvin and Gagne ©2009
Activity-1 – Voting
Correct answer last statement: D
Operating System Concepts with Java – 8th Edition 8.24 Silberschatz, Galvin and Gagne ©2009
Activity-1 – Voting-2
Correct answer : C
Operating System Concepts with Java – 8th Edition 8.25 Silberschatz, Galvin and Gagne ©2009
BREAK TIME
10 minutes Break
Operating System Concepts with Java – 8th Edition 8.26 Silberschatz, Galvin and Gagne ©2009
Structure of the Page Table
Hierarchical Paging Hashed Page Tables
Operating System Concepts with Java – 8th Edition 8.27 Silberschatz, Galvin and Gagne ©2009
Hierarchical Page Tables
Break up the logical address space into multiple page tables A simple technique is a two-level page table
Operating System Concepts with Java – 8th Edition 8.28 Silberschatz, Galvin and Gagne ©2009
Two-Level Page-Table Scheme
Operating System Concepts with Java – 8th Edition 8.29 Silberschatz, Galvin and Gagne ©2009
Two-Level Paging Example
A logical address (on 32-bit machine with 1K page size) is divided into: a page number consisting of 22 bits
a page offset consisting of 10 bits
Since the page table is paged, the page number is further divided into: a 12-bit page number
a 10-bit page offset
Thus, a logical address is as follows: page number
10
page offset
10
pi
p2
d
12
where pi is an index into the outer page table, and p2 is the displacement within the page of the outer page table
Operating System Concepts with Java – 8th Edition 8.30 Silberschatz, Galvin and Gagne ©2009
Address-Translation Scheme
Operating System Concepts with Java – 8th Edition 8.31 Silberschatz, Galvin and Gagne ©2009
Three-level Paging Scheme
Operating System Concepts with Java – 8th Edition 8.32 Silberschatz, Galvin and Gagne ©2009
Hashed Page Tables
Common in address spaces > 32 bits
The virtual page number is hashed into a page table
This page table contains a chain of elements hashing to the same location
Virtual page numbers are compared in this chain searching for a match
If a match is found, the corresponding physical frame is extracted
Operating System Concepts with Java – 8th Edition 8.33 Silberschatz, Galvin and Gagne ©2009
Hashed Page Table
Operating System Concepts with Java – 8th Edition 8.34 Silberschatz, Galvin and Gagne ©2009
Activity-2 Answers
Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?
– First-fit: 212K is put in 500K partition (leaving a 288K partition). 417K is put in 600K partition. 112K is put in 288K partition 426K must wait (cannot be allocated)
– Best-fit: 212K is put in 300K partition. 417K is put in 500K partition 112K is put in 200K partition 426K is put in 600K partition
– Worst-fit: 212K is put in 600K partition (leaving a 388K partition) 417K is put in 500K partition 112K is put in 388K partition 426K must wait (cannot be allocated)
Operating System Concepts with Java – 8th Edition 8.36 Silberschatz, Galvin and Gagne ©2009
BREAK TIME
10 minutes Break
Operating System Concepts with Java – 8th Edition 8.37 Silberschatz, Galvin and Gagne ©2009
Segmentation
Memory-management scheme that supports user view of memory A program is a collection of segments
A segment is a logical unit such as: main program
procedure
function
method
object
local variables, global variables common block
stack symbol table arrays
Operating System Concepts with Java – 8th Edition 8.38 Silberschatz, Galvin and Gagne ©2009
User’s View of a Program
Operating System Concepts with Java – 8th Edition 8.39 Silberschatz, Galvin and Gagne ©2009
Logical View of Segmentation
1
4
2
3
3
1
2
4
user space physical memory space
Operating System Concepts with Java – 8th Edition 8.40 Silberschatz, Galvin and Gagne ©2009
Segmentation Architecture
Logical address consists of a two tuple:
Segment table – maps two-dimensional physical addresses; each table entry has:
base – contains the starting physical address where the segments reside in memory
limit – specifies the length of the segment
Segment-table base register (STBR) points to the segment
table’s location in memory
Segment-table length register (STLR) indicates number of segments used by a program;
segment number s is legal if s < STLR
Operating System Concepts with Java – 8th Edition 8.41 Silberschatz, Galvin and Gagne ©2009
Segmentation Architecture (Cont.)
Protection
With each entry in segment table associate:
validation bit = 0 illegal segment
read/write/execute privileges
Protection bits associated with segments; code sharing
occurs at segment level
Since segments vary in length, memory allocation is a dynamic storage-allocation problem
A segmentation example is shown in the following diagram
Operating System Concepts with Java – 8th Edition 8.42 Silberschatz, Galvin and Gagne ©2009
Segmentation Hardware
Operating System Concepts with Java – 8th Edition 8.43 Silberschatz, Galvin and Gagne ©2009
Example of Segmentation
Operating System Concepts with Java – 8th Edition 8.44 Silberschatz, Galvin and Gagne ©2009
Linear Address in Linux
Broken into four parts:
Operating System Concepts with Java – 8th Edition 8.45 Silberschatz, Galvin and Gagne ©2009
Three-level Paging in Linux
Operating System Concepts with Java – 8th Edition 8.46 Silberschatz, Galvin and Gagne ©2009
Activity-3
Assume the size of a memory control block is 16 bytes, and that you are using a contiguous memory allocation model.
Consider the following class:
class Coordinate {
public: int x; int y; int z; };
• If int variables are 32 bits, what is the size of object of this class, in bytes?
The following code is then executed:
for (int i = 0; i < 16; ++i) { new Coordinate(); }
• At this point, how much memory is used to store Coordinate objects?
• If we are using a contiguous memory allocation model, starting with one hole of size 10000 bytes, how much of this memory has now been used to store Memory Control Blocks?
Operating System Concepts with Java – 8th Edition 8.47 Silberschatz, Galvin and Gagne ©2009
Activity-3 solution
Size of the objects: 4 bytes per variable x 3 variables = 12 bytes Memory used after the loop (which creates 16 objects) = 16 * 12 = 192 bytes
Using a contiguous memory allocation model: 16 holes were created, i.e. one per object.
These are 16 bytes each (it says in the question). 16 * 16 = 256 bytes for memory control blocks.
Operating System Concepts with Java – 8th Edition 8.48 Silberschatz, Galvin and Gagne ©2009
Activity-4 : Stack Management
Consider the Java code available on KEATS and try to answer the following two questions:
1. What is printed to the screen when this code executes?
2. What values are on the stack when execution reaches line 1253?
Operating System Concepts with Java – 8th Edition 8.49 Silberschatz, Galvin and Gagne ©2009
Activity-4 : Voting
Correct answer : B
Operating System Concepts with Java – 8th Edition 8.50 Silberschatz, Galvin and Gagne ©2009
End
Operating System Concepts with Java – 8th Edition 8.51 Silberschatz, Galvin and Gagne ©2009
Virtual-Memory Management
Operating System Concepts with Java – 8th Edition 9.1 Silberschatz, Galvin and Gagne ©2009
Objectives
To describe the benefits of a virtual memory system
To explain the concepts of demand paging, page- replacement algorithms, and allocation of page frames
Operating System Concepts with Java – 8th Edition 9.2 Silberschatz, Galvin and Gagne ©2009
Chapter 9: Virtual Memory
Background
Demand Paging
Page Replacement Thrashing Operating-System Example
Operating System Concepts with Java – 8th Edition 9.3 Silberschatz, Galvin and Gagne ©2009
Background
Virtual memory – Part of the secondary storage (high speed disk) will be acted as a virtual memory and the virtual memory manager is responsible on managing and transferring the parts of the programs to main memory only when there is a need to execute them.
separation of user logical memory from physical memory.
Only part of the program needs to be in memory for execution
Logical address space can therefore be much larger than physical address space
Allows address spaces to be shared by several processes
Allows for more efficient process creation
Virtual memory can be implemented via: Demand paging
Demand segmentation
Operating System Concepts with Java – 8th Edition 9.4 Silberschatz, Galvin and Gagne ©2009
Virtual Memory That is Larger Than Physical Memory
Operating System Concepts with Java – 8th Edition 9.5 Silberschatz, Galvin and Gagne ©2009
Virtual-address Space
Operating System Concepts with Java – 8th Edition 9.6 Silberschatz, Galvin and Gagne ©2009
Shared Library Using Virtual Memory
Operating System Concepts with Java – 8th Edition 9.7 Silberschatz, Galvin and Gagne ©2009
Demand Paging
Bring a page into memory only when it is needed Less I/O needed
Less memory needed
Faster response
More users
Page is needed reference to it
invalid reference abort
not-in-memory bring to memory
Lazy swapper – never swaps a page into memory unless page will be needed
Swapper that deals with pages is a pager
Operating System Concepts with Java – 8th Edition 9.8 Silberschatz, Galvin and Gagne ©2009
Transfer of a Paged Memory to Contiguous Disk Space
Operating System Concepts with Java – 8th Edition 9.9 Silberschatz, Galvin and Gagne ©2009
Valid-Invalid Bit
With each page table entry a valid–invalid bit is associated (v in-memory, i not-in-memory)
Initially valid–invalid bit is set to i on all entries Example of a page table snapshot:
Frame # valid-invalid bit
v
v
v
v
i
....
i
i
page table
During address translation, if valid–invalid bit in page table entry
is I page fault
Operating System Concepts with Java – 8th Edition 9.10 Silberschatz, Galvin and Gagne ©2009
Page Table When Some Pages Are Not in Main Memory
Operating System Concepts with Java – 8th Edition 9.11 Silberschatz, Galvin and Gagne ©2009
Page Fault
If there is a reference to a page, first reference to that page will trap to operating system:
page fault
1. Operating system looks at another table to decide: Invalid reference abort
Just not in memory
2. Getemptyframe
3. Swap page into frame
4. Resettables
5. Setvalidationbit=v
6. Restarttheinstructionthatcausedthepagefault
Operating System Concepts with Java – 8th Edition 9.12 Silberschatz, Galvin and Gagne ©2009
Steps in Handling a Page Fault
Operating System Concepts with Java – 8th Edition 9.13 Silberschatz, Galvin and Gagne ©2009
Performance of Demand Paging
Page Fault Rate 0 p 1.0
if p = 0 no page faults
if p = 1, every reference is a fault
Effective Access Time (EAT)
EAT = (1 – p) x memory access
+ p (page fault overhead + swap page out
+ swap page in
+ restart overhead
)
Effective access time = (1−p)×ma + p×page fault time
Operating System Concepts with Java – 8th Edition 9.14 Silberschatz, Galvin and Gagne ©2009
Demand Paging Example
Effective access time = (1−p)×ma + p×page fault time Memory access time = 200 nanoseconds
Average page-fault service time = 8 milliseconds
EAT = (1 – p) x 200 + p (8 milliseconds) = (1 – p x 200 + p x 8,000,000
= 200 + p x 7,999,800
If one access out of 1,000 causes a page fault, then EAT = 8.2 microseconds.
This is a slowdown by a factor of 40!!
Operating System Concepts with Java – 8th Edition 9.15 Silberschatz, Galvin and Gagne ©2009
What happens if there is no free frame?
Page replacement – find some page in memory, but not really in use, swap it out
algorithm
performance – want an algorithm which will result
in minimum number of page faults
Same page may be brought into memory several times
Operating System Concepts with Java – 8th Edition 9.16 Silberschatz, Galvin and Gagne ©2009
Page Replacement
Prevent over-allocation of memory by modifying page- fault service routine to include page replacement
Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk
Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory
Operating System Concepts with Java – 8th Edition 9.17 Silberschatz, Galvin and Gagne ©2009
Need For Page Replacement
Operating System Concepts with Java – 8th Edition 9.18 Silberschatz, Galvin and Gagne ©2009
Basic Page Replacement
1. Find the location of the desired page on disk
2. Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page
replacement algorithm to select a victim frame
3. Bring the desired page into the (newly) free frame;
update the page and frame tables
4. Restart the process
Operating System Concepts with Java – 8th Edition 9.19 Silberschatz, Galvin and Gagne ©2009
Page Replacement
Operating System Concepts with Java – 8th Edition 9.20 Silberschatz, Galvin and Gagne ©2009
Page Replacement Algorithms
Want lowest page-fault rate
Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string
In all our examples, the reference string is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Operating System Concepts with Java – 8th Edition 9.21 Silberschatz, Galvin and Gagne ©2009
Graph of Page Faults Versus The Number of Frames
Operating System Concepts with Java – 8th Edition 9.22 Silberschatz, Galvin and Gagne ©2009
First-In-First-Out (FIFO) Algorithm
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 frames (3 pages can be in memory at a time per process)
1
2
3
4 frames
1 2
3
1 2
45 1 3
24
54 1 5 2
9 page faults
1
2
3
4
3 43
10 page faults
Belady’s Anomaly: more frames more page faults
Operating System Concepts with Java – 8th Edition 9.23 Silberschatz, Galvin and Gagne ©2009
FIFO Illustrating Belady’s Anomaly
Operating System Concepts with Java – 8th Edition 9.24 Silberschatz, Galvin and Gagne ©2009
FIFO Page Replacement
Operating System Concepts with Java – 8th Edition 9.25 Silberschatz, Galvin and Gagne ©2009
BREAK TIME
10 minutes Break
Operating System Concepts with Java – 8th Edition 9.29 Silberschatz, Galvin and Gagne ©2009
Optimal Algorithm
Replace page that will not be used for longest period of time 4 frames example
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 4
6 page faults
5 How do you know this?
Used for measuring how well your algorithm performs
1
2
3
4
Operating System Concepts with Java – 8th Edition 9.30 Silberschatz, Galvin and Gagne ©2009
Optimal Page Replacement
Operating System Concepts with Java – 8th Edition 9.31 Silberschatz, Galvin and Gagne ©2009
Least Recently Used (LRU) Algorithm
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
2
5
3
1
2
4
3
1
2
3
4
5
2
4
3
1
2
5
4
Counter implementation
Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter
When a page needs to be changed, look at the counters to determine which are to change
Operating System Concepts with Java – 8th Edition 9.32 Silberschatz, Galvin and Gagne ©2009
LRU Page Replacement
Operating System Concepts with Java – 8th Edition 9.33 Silberschatz, Galvin and Gagne ©2009
Thrashing
If a process does not have “enough” pages, the page-fault rate is very high. This leads to:
low CPU utilization
operating system thinks that it needs to increase the
degree of multiprogramming
another process added to the system
Thrashing a process is busy swapping pages in and out A process is thrashing if it is spending more time paging
than executing.
Operating System Concepts with Java – 8th Edition 9.37 Silberschatz, Galvin and Gagne ©2009
Operating System Example:Windows XP
Uses demand paging with clustering. Clustering brings in pages surrounding the faulting page
Processes are assigned working set minimum and working set maximum
Working set minimum is the minimum number of pages the process is guaranteed to have in memory
A process may be assigned as many pages up to its working set maximum
When the amount of free memory in the system falls below a threshold, automatic working set trimming is performed to restore the amount of free memory
Working set trimming removes pages from processes that have pages in excess of their working set minimum
Operating System Concepts with Java – 8th Edition 9.38 Silberschatz, Galvin and Gagne ©2009
End
Operating System Concepts with Java – 8th Edition 9.39 Silberschatz, Galvin and Gagne ©2009
System Protection
Operating System Concepts with Java – 8th Edition 14.1 Silberschatz, Galvin and Gagne ©2009
Objectives
◼ Discuss the goals and principles of protection in a modern computer system
◼ Explain how protection domains combined with an access matrix are used to specify the resources a process may access
◼ Examine capability and language-based protection systems
Operating System Concepts with Java – 8th Edition 14.2 Silberschatz, Galvin and Gagne ©2009
Chapter 14: Protection
◼ Goals of Protection
◼ Principles of Protection
◼ Unix File Protection
◼ Domain of Protection
◼ Access Matrix
◼ Access Control
◼ Language-Based Protection ◼ Protection in Java
Operating System Concepts with Java – 8th Edition 14.3
Silberschatz, Galvin and Gagne ©2009
Goals of Protection
◼ Operating system consists of a collection of objects, hardware or software
◼ Each object has a unique name and can be accessed through a well- defined set of operations
◼ Protection problem - ensure that each object is accessed correctly and only by those processes that are allowed to do so
◼ Policies decide what will be done. Mechanisms determine how something will be done.
Operating System Concepts with Java – 8th Edition 14.4 Silberschatz, Galvin and Gagne ©2009
Principles of Protection
◼ Guiding principle – principle of least privilege
⚫ Programs, users and systems should be given just enough
privileges to perform their tasks.
⚫ A privilege is the right to execute a system call or to use an option
within that system call (such as opening a file with write access).
⚫ An OS following the principle of least privilege implements its features, programs, system calls, and data structures so that failure or compromise of a component does the minimum damage.
⚫ An OS also provides system calls and services that allow applications to be written with fine-grained access controls.
⚫ An OS provides mechanisms to enable privileges when they are needed and to disable them when they are not needed.
Operating System Concepts with Java – 8th Edition 14.5 Silberschatz, Galvin and Gagne ©2009
Principles of Protection
◼ Guiding principle – principle of least privilege
⚫ Also beneficial is the creation of audit trails for all privileged function access. The audit trail allows the programmer, systems administrator, or law-enforcement officer to trace all protection and security activities on the system.
⚫ The principle of least privilege can help produce a more secure computing environment. Unfortunately, it frequently does not.
⚫ Windows 2000 has a complex protection scheme at its core and yet has many security holes. By comparison, Solaris is considered relatively secure.
⚫ One reason for the difference may be that Windows 2000 has more lines of code and more services than Solaris and thus has more to secure and protect.
⚫ Another reason could be that the protection scheme in Windows 2000 is incomplete or protects the wrong aspects of the operating system, leaving other areas vulnerable.
Operating System Concepts with Java – 8th Edition 14.6 Silberschatz, Galvin and Gagne ©2009
File Protection (UNIX)
❑ Sharing of files on multi-user systems is desirable ❑ Sharing may be done through a protection scheme
File attributes
◼ Name – only information kept in human-readable form
◼ Identifier – unique tag (number) identifies file within file system
◼ Type – needed for systems that support different types
◼ Location – pointer to file location on device
◼ Size – current file size
◼ Protection – controls who can do reading, writing, executing (rwx)
◼ Time, date, and user identification – data for protection, security, and usage monitoring
◼ Information about files are kept in the directory structure, which is maintained on the disk.
Protection section of Chapter-10
Operating System Concepts with Java – 8th Edition 14.7 Silberschatz, Galvin and Gagne ©2009
File Protection Mechanism (UNIX)
❑The most general scheme to implement identity dependent access is to associate with each file and directory an access-control list (ACL)specifying user names and the types of access allowed for each user.
❑When a user requests access to a particular file, the operating system checks the access list associated with that file.
❑If that user is listed for the requested access, the access is allowed. Otherwise, a protection violation occurs, and the user job is denied access to the file.
❑It’s disadvantage is maintaining the long list of users its variable size given that the number of users may increase over time.
Protection section-Chapter-10
Operating System Concepts with Java – 8th Edition 14.8 Silberschatz, Galvin and Gagne ©2009
File Protection Mechanism (UNIX)
To condense the length of the access-control list, many systems recognize
three classifications of users in connection with each file:
❑ Owner. The user who created the file is the owner.
❑ Group. A set of users who are sharing the file and need similar access is a group, or work group.
❑ Universe. All other users in the system constitute the universe.
The most common approach is to combine access-control lists with the more general(and easier to implement) owner, group,and universe access control scheme.
Protection section 10.6 -chapter 10
Operating System Concepts with Java – 8th Edition 14.9 Silberschatz, Galvin and Gagne ©2009
Domain Structure
◼ Access-right =
where rights-set is a subset of all valid operations that can be performed on the object.
◼ Domain = set of access-rights (rwx…)
Operating System Concepts with Java – 8th Edition 14.10 Silberschatz, Galvin and Gagne ©2009
Domain Structure
A domain can be realized in a variety of ways:
• Each user may be a domain. In this case, the set of objects that can be accessed depends on the identity of the user. Domain switching occurs when the user is changed generally when one user logs out and another user logs in.
• Each process may be a domain. In this case, the set of objects that can be accessed depends on the identity of the process. Domain switching occurs when one process sends a message to another process and then waits for a response.
• Each procedure may be a domain. In this case, the set of objects that can be accessed corresponds to the local variables defined within the procedure. Domain switching occurs when a procedure call is made.
Operating System Concepts with Java – 8th Edition 14.11 Silberschatz, Galvin and Gagne ©2009
Domain Implementation (UNIX)
◼ System consists of 2 domains: ⚫ User
⚫ Supervisor
◼ UNIX
⚫ Domain = user-id
⚫ Domain switch accomplished via file system
Each file has associated with it a domain bit (setuid bit)
When file is executed and setuid = on, then user-id is set to owner of
the file being executed. When execution completes user-id is reset
Operating System Concepts with Java – 8th Edition 14.12 Silberschatz, Galvin and Gagne ©2009
BREAK TIME
◼10 minutes Break
Operating System Concepts with Java – 8th Edition 14.13 Silberschatz, Galvin and Gagne ©2009
Access Matrix
◼ View model protection as a matrix (access matrix)
◼ Rows represent domains
◼ Columns represent objects
◼ Each entry in the matrix consists of a set of access rights
◼ Access(i, j) is the set of operations that a process executing in Domaini can invoke on Objectj
Operating System Concepts with Java – 8th Edition 14.14 Silberschatz, Galvin and Gagne ©2009
Access Matrix
Operating System Concepts with Java – 8th Edition 14.15 Silberschatz, Galvin and Gagne ©2009
Use of Access Matrix
◼ If a process in Domain Di tries to do “op” on object Oj, then “op” must be in the access matrix
◼ Can be expanded to dynamic protection
⚫ Operations to add, delete access rights ⚫ Special access rights:
owner of Oi
copy op from Oi to Oj
control – Di can modify Dj access rights transfer – switch from domain Di to Dj
Operating System Concepts with Java – 8th Edition 14.16 Silberschatz, Galvin and Gagne ©2009
Use of Access Matrix (Cont)
◼ Access matrix design separates mechanism from policy ⚫ Mechanism
Operating system provides access-matrix + rules
If ensures that the matrix is only manipulated by authorized
agents and that rules are strictly enforced ⚫ Policy
User dictates policy
Who can access what object and in what mode
Operating System Concepts with Java – 8th Edition 14.17 Silberschatz, Galvin and Gagne ©2009
Implementation of Access Matrix
◼ Each column = Access-control list for one object Defines who can perform what operation.
Domain 1 = Read, Write Domain 2 = Read Domain 3 = Read
◼ Each Row = Capability List (like a key)
Fore each domain, what operations allowed on what objects.
Object 1 – Read
Object 4 – Read, Write, Execute Object 5 – Read, Write, Delete, Copy
Operating System Concepts with Java – 8th Edition 14.18 Silberschatz, Galvin and Gagne ©2009
Access Matrix of Figure A With Domains as Objects
Figure B
Operating System Concepts with Java – 8th Edition 14.19 Silberschatz, Galvin and Gagne ©2009
Access Matrix with Copy Rights
Operating System Concepts with Java – 8th Edition 14.20 Silberschatz, Galvin and Gagne ©2009
Access Matrix With Owner Rights
Operating System Concepts with Java – 8th Edition 14.21 Silberschatz, Galvin and Gagne ©2009
Modified Access Matrix of Figure B
If control right is applicable only to domain objects. If access(i,j) includes the control right, then a process executing in domain Di can remove any access right from row j.
Operating System Concepts with Java – 8th Edition 14.22 Silberschatz, Galvin and Gagne ©2009
Access Matrix Implementation
◼ Global Table : consisting of a set of ordered triples
▪ Whenever an operation M is executed on an object Oj within domain Di, the global table is searched for a triple
◼ Access Lists for Objects : Each column in the access matrix can be implemented as an access list for one object. The resulting list for each object consists of ordered pairs
▪ This approach can be extended easily to define a list plus a default set of access rights. When an operation M on an object Oj is attempted in domain Di, we search the access list for object Oj, looking for an entry
❑ Capability Lists for Domains: A capability list for a domain is a list of objects together with the operations allowed on those objects. An object is often represented by its physical name or address, called a capability.
▪ ToexecuteoperationMonobjectOj,theprocessexecutestheoperationM,specifyingthe capability(or pointer) for object Oj as a parameter. Simple possession of the capability means that access is allowed.
▪ Examples of Capability-Based system are Hydra, Cambridge CAP system For more information read the module text book on comparison of these three types in Chapter-14.
Operating System Concepts with Java – 8th Edition 14.23 Silberschatz, Galvin and Gagne ©2009
Access Control
◼ Protection can be applied to non-file resources ◼ Solaris 10 provides role-based access control
(RBAC) to implement least privilege
⚫ Privilege is right to execute system call or use an
option within a system call
⚫ Can be assigned to processes
⚫ Users assigned roles granting access to privileges and programs
Operating System Concepts with Java – 8th Edition 14.24 Silberschatz, Galvin and Gagne ©2009
Role-based Access Control in Solaris 10
Operating System Concepts with Java – 8th Edition 14.25 Silberschatz, Galvin and Gagne ©2009
BREAK TIME
◼10 minutes Break
Operating System Concepts with Java – 8th Edition 14.26 Silberschatz, Galvin and Gagne ©2009
Language-Based Protection
◼ Protection is usually achieved through an operating- system kernel, which acts as a security agent to inspect and validate each attempt to access a protected resource.
◼ Operating Systems have become more complex and the goals of protection become much more refined.
◼ The protection system designers drawn heavily on ideas generated from programming languages eg. Abstract data type and objects.
Operating System Concepts with Java – 8th Edition 14.27 Silberschatz, Galvin and Gagne ©2009
Language-Based Protection
◼Compiler-BasedEnforcement: Specifyingthe desired control of access to a shared resource in a system is making a declarative statement about the resource
◼ Specification of protection in a programming language allows the high-level description of policies for the allocation and use of resources
◼ Language implementation can provide software for protection enforcement when automatic hardware- supported checking is unavailable
Operating System Concepts with Java – 8th Edition 14.28 Silberschatz, Galvin and Gagne ©2009
Language-Based Protection.. cont
◼ Protection needs are simply declared, rather than programmed as a sequence of calls on procedures of an operating system.
◼ Protection requirements can be stated independently of the facilities provided by a particular operating system.
◼ The means for enforcement need not be provided by the designer of a subsystem.
◼ A declarative notation is natural because access privileges are closely related to the linguistic concept of data type.
Operating System Concepts with Java – 8th Edition 14.29 Silberschatz, Galvin and Gagne ©2009
Protection in Java -2
◼ Protection is handled by the Java Virtual Machine (JVM)
◼ Java support dynamically loading untrusted classes over a network
and for executing mutually distrusting classes within the same JVM.
◼ A class is assigned a protection domain when it is loaded by the JVM
◼ The protection domain indicates what operations the class can (and cannot) perform
◼ If a library method is invoked that performs a privileged operation, the stack is inspected to ensure the operation can be performed by the library
Operating System Concepts with Java – 8th Edition 14.30 Silberschatz, Galvin and Gagne ©2009
Stack Inspection
Operating System Concepts with Java – 8th Edition 14.31 Silberschatz, Galvin and Gagne ©2009
Java Type Safety
◼ Type safety ensures that classes cannot treat integers as pointers, write past the end of an array, or otherwise access memory in arbitrary ways.
◼ A program can access an object only via the methods defined on that object by its class. This is the foundation of Java protection, since it enables a class to effectively encapsulate and protect its data and methods from other classes loaded in the same JVM.
◼ A variable can be defined as private so that only the class that contains it can access it or protected so that it can be accessed only by the class that contains it, subclasses of that class, or classes in the same package.
◼ Type safety ensures that these restrictions can be enforced.
Operating System Concepts with Java – 8th Edition 14.32 Silberschatz, Galvin and Gagne ©2009
Summary
▪ Objects may be hardware (such as memory, CPU time, and I/O devices) or software (such as files, programs, and semaphores
▪ An access right is permission to perform an operation on an object
▪ A domain is a set of access rights.
▪ Processes execute in domains and may use any of the access
rights in the domain to access and manipulate objects.
▪ Process may be either bound to a protection domain or allowed to
switch from one domain to another.
▪ The access matrix is a general model of protection that provides
a mechanism for protection without imposing a particular
protection policy on the system or its user
▪ Three methods to implement access matrix (Global Table, Access
List, Capability list for domains)
▪ Language-based protection provides finer-grained arbitration of
requests and privileges than the operating system is able to
provide.
▪ A Java program cannot directly access memory; it can manipulate
only an object for which it has a reference.
Operating System Concepts with Java – 8th Edition 14.33 Silberschatz, Galvin and Gagne ©2009
OSC JUST Before End of Term Competition!!!
Operating System Concepts with Java – 8th Edition 14.34 Silberschatz, Galvin and Gagne ©2009
End
Operating System Concepts with Java – 8th Edition 14.35 Silberschatz, Galvin and Gagne ©2009
System Security
Operating System Concepts with Java – 8th Edition 15.1 Silberschatz, Galvin and Gagne ©2009
Objectives
◼ To discuss security threats and attacks
◼ To explain the fundamentals of encryption and
authentication
◼ To examine the uses of cryptography in computing
◼ To describe the various countermeasures to security attacks
Operating System Concepts with Java – 8th Edition 15.2 Silberschatz, Galvin and Gagne ©2009
Chapter 15: Security
◼ The Security Problem
◼ Program Threats
◼ System and Network Threats
◼ Cryptography as a Security Tool ◼ User Authentication
◼ Implementing Security Defenses ◼ An Example: Windows XP
Operating System Concepts with Java – 8th Edition 15.3 Silberschatz, Galvin and Gagne ©2009
The Security Problem
◼ Security must consider external environment of the system, and protect the system resources
◼ Intruders (crackers) attempt to breach security
◼ Threat is potential security violation such as the discovery of a
vulnerability.
◼ Attack is attempt to breach security
◼ Attack can be accidental or malicious
◼ Easier to protect against accidental than malicious misuse
Operating System Concepts with Java – 8th Edition 15.4 Silberschatz, Galvin and Gagne ©2009
Security Violations
◼ Categories
⚫ Breach of confidentiality ⚫ Breach of integrity
⚫ Breach of availability
⚫ Theft of service
⚫ Denial of service
◼ Methods
⚫ Masquerading (breach authentication) ⚫ Replay attack
Message modification ⚫ Man-in-the-middle attack ⚫ Session hijacking
Operating System Concepts with Java – 8th Edition 15.5 Silberschatz, Galvin and Gagne ©2009
Standard Security Attacks
Operating System Concepts with Java – 8th Edition 15.6 Silberschatz, Galvin and Gagne ©2009
Security Measure Levels
◼ Security must occur at four levels to be effective: ⚫ Physical
⚫ Human
Avoid social engineering, phishing, dumpster diving
⚫ Operating System
⚫ Network
◼ Security is as weak as the weakest link in the chain
Operating System Concepts with Java – 8th Edition 15.7 Silberschatz, Galvin and Gagne ©2009
Program Threats
◼ Trojan Horse
⚫ Code segment that misuses its environment
⚫ Exploits mechanisms for allowing programs written by users to be executed by other users
⚫ Spyware, pop-up browser windows, covert channels ◼ Trap Door
⚫ Specific user identifier or password that circumvents normal security procedures
⚫ Could be included in a compiler ◼ Logic Bomb
⚫ Program that initiates a security incident under certain circumstances ◼ Stack and Buffer Overflow
⚫ Exploits a bug in a program (overflow either the stack or memory buffers)
Operating System Concepts with Java – 8th Edition 15.8 Silberschatz, Galvin and Gagne ©2009
C Program with Buffer-overflow Condition
#include
#define BUFFER SIZE 256
int main(int argc, char *argv[]) {
char buffer[BUFFER SIZE]; if (argc < 2)
return -1;
else {
strcpy(buffer,argv[1]);
return 0; }
}
Operating System Concepts with Java – 8th Edition 15.9 Silberschatz, Galvin and Gagne ©2009
Layout of Typical Stack Frame
Operating System Concepts with Java – 8th Edition 15.10 Silberschatz, Galvin and Gagne ©2009
Program Threats (Cont.)
◼ Viruses
⚫ Code fragment embedded in legitimate program
⚫ Very specific to CPU architecture, operating system, applications ⚫ Usually borne via email or as a macro
Visual Basic Macro to reformat hard drive Sub AutoOpen()
Dim oFS
Set oFS =
CreateObject(’’Scripting.FileSystemObject’’)
vs = Shell(’’c:command.com /k format
c:’’,vbHide)
End Sub
Operating System Concepts with Java – 8th Edition 15.11 Silberschatz, Galvin and Gagne ©2009
Program Threats (Cont.)
◼ Virus dropper inserts virus onto the system
◼ Many categories of viruses, literally many thousands of viruses
⚫ File
⚫ Boot
⚫ Macro
⚫ Source code ⚫ Polymorphic ⚫ Encrypted
⚫ Stealth
⚫ Tunneling
⚫ Multipartite ⚫ Armored
Operating System Concepts with Java – 8th Edition
15.12 Silberschatz, Galvin and Gagne ©2009
A Boot-sector Computer Virus
Operating System Concepts with Java – 8th Edition 15.13 Silberschatz, Galvin and Gagne ©2009
System and Network Threats
◼ Worms – use spawn mechanism; standalone program ◼ Internet worm
⚫ Exploited UNIX networking features (remote access) and bugs in finger and sendmail programs
⚫ Grappling hook program uploaded main worm program ◼ Port scanning
⚫ Automated attempt to connect to a range of ports on one or a range of IP addresses
◼ Denial of Service
⚫ Overload the targeted computer preventing it from doing any useful
work
⚫ Distributed denial-of-service (DDOS) come from multiple sites at once
Operating System Concepts with Java – 8th Edition 15.14 Silberschatz, Galvin and Gagne ©2009
The Morris Internet Worm
Operating System Concepts with Java – 8th Edition 15.15 Silberschatz, Galvin and Gagne ©2009
Cryptography as a Security Tool
◼ Broadest security tool available
⚫ Source and destination of messages cannot be trusted without
cryptography
⚫ Means to constrain potential senders (sources) and / or receivers
(destinations) of messages ◼ Based on secrets (keys)
Operating System Concepts with Java – 8th Edition 15.16 Silberschatz, Galvin and Gagne ©2009
Secure Communication over Insecure Medium
Operating System Concepts with Java – 8th Edition 15.17 Silberschatz, Galvin and Gagne ©2009
Encryption
◼ Encryption algorithm consists of
⚫ Set of K keys
⚫ Set of M Messages
⚫ Set of C ciphertexts (encrypted messages)
⚫ A function E : K → (M→C). That is, for each k K, E(k) is a function for generating ciphertexts from messages
Both E and E(k) for any k should be efficiently computable functions
⚫ A function D : K → (C → M). That is, for each k K, D(k) is a function for generating
messages from ciphertexts
Both D and D(k) for any k should be efficiently computable functions
◼ An encryption algorithm must provide this essential property: Given a ciphertext c C, a computer can compute m such that E(k)(m) = c only if it possesses D(k).
⚫ Thus, a computer holding D(k) can decrypt ciphertexts to the plaintexts used to produce them, but a computer not holding D(k) cannot decrypt ciphertexts
⚫ Since ciphertexts are generally exposed (for example, sent on the network), it is important that it be infeasible to derive D(k) from the ciphertexts
Operating System Concepts with Java – 8th Edition 15.18 Silberschatz, Galvin and Gagne ©2009
Symmetric Encryption
◼ Same key used to encrypt and decrypt
⚫ E(k) can be derived from D(k), and vice versa
◼ DES is most commonly used symmetric block-encryption algorithm (created by US Govt)
⚫ Encrypts a block of data at a time
◼ Triple-DES considered more secure
◼ Advanced Encryption Standard (AES), twofish up and coming
◼ RC4 is most common symmetric stream cipher, but known to have vulnerabilities
⚫ Encrypts/decrypts a stream of bytes (i.e wireless transmission) ⚫ Key is a input to psuedo-random-bit generator
Generates an infinite keystream
Operating System Concepts with Java – 8th Edition 15.19 Silberschatz, Galvin and Gagne ©2009
Asymmetric Encryption
◼ Public-key encryption based on each user having two keys:
⚫ public key – published key used to encrypt data
⚫ private key – key known only to individual user used to decrypt data
◼ Must be an encryption scheme that can be made public without making it easy to figure out the decryption scheme
◼ Most common is RSA block cipher (Rivest, Shamir, and Adleman)
⚫ Efficient algorithm for testing whether or not a number is prime
⚫ No efficient algorithm is know for finding the prime factors of a number
Operating System Concepts with Java – 8th Edition 15.20 Silberschatz, Galvin and Gagne ©2009
Asymmetric Encryption (Cont.)
◼ Formally, it is computationally infeasible to derive D(kd , N) from E(ke , N), and so E(ke , N) need not be kept secret and can be widely disseminated
⚫ E(ke , N) (or just ke) is the public key
⚫ D(kd , N) (or just kd) is the private key
⚫ N is the product of two large, randomly chosen prime numbers p and q (for example, p and q are 512 bits each)
⚫ Encryption algorithm is E(ke , N)(m) = mke mod N, where ke satisfies kekd mod (p−1)(q −1) = 1
⚫ The decryption algorithm is then D(kd , N)(c) = ckd mod N
Operating System Concepts with Java – 8th Edition 15.21 Silberschatz, Galvin and Gagne ©2009
Asymmetric Encryption Example
◼ Forexample.makep=7andq=13
◼ We then calculate N = 7∗13 = 91 and (p−1)(q−1) = 72
◼ We next select ke relatively prime to 72 and< 72, yielding 5
◼ Finally,we calculate kd such that kekd mod 72 = 1, yielding 29
◼ We how have our keys
⚫ Public key, ke, N = 5, 91
⚫ Privatekey,kd ,N=29,91
◼ Encrypting the message 69 with the public key results in the
cyphertext 62
◼ Cyphertext can be decoded with the private key
⚫ Public key can be distributed in cleartext to anyone who wants to communicate with holder of public key
Operating System Concepts with Java – 8th Edition 15.22 Silberschatz, Galvin and Gagne ©2009
Encryption and Decryption using RSA Asymmetric Cryptography
Operating System Concepts with Java – 8th Edition 15.23 Silberschatz, Galvin and Gagne ©2009
User Authentication
◼ Crucial to identify user correctly, as protection systems depend on user ID
◼ User identity most often established through passwords, can be considered a special case of either keys or capabilities
⚫ Also can include something user has and /or a user attribute
◼ Passwords must be kept secret
⚫ Frequent change of passwords
⚫ Use of “non-guessable” passwords ⚫ Log all invalid access attempts
◼ Passwords may also either be encrypted or allowed to be used only once
Operating System Concepts with Java – 8th Edition 15.24 Silberschatz, Galvin and Gagne ©2009
Example: Windows XP
◼ Security is based on user accounts
⚫ Each user has unique security ID
⚫ Login to ID creates security access token
Includes security ID for user, for user’s groups, and special privileges
Every process gets copy of token
System checks token to determine if access allowed or
denied
◼ Each object in Windows XP has a security attribute defined by a security descriptor
⚫ For example, a file has a security descriptor that indicates the access permissions for all users
Operating System Concepts with Java – 8th Edition 15.25 Silberschatz, Galvin and Gagne ©2009
Summary
• Protection is strictly an internal problem: How do we provide controlled access to programs and data stored in a computer system? Security, on the other hand, requires not only an adequate protection system but also consideration of the external environment within which the system operates.
• Various types of attacks have been explored on both computer and network levels.
• Cryptography provides means to secure data. (Block and stream cipher examples)
• SymmetricandAsymmetricCryptography
Operating System Concepts with Java – 8th Edition 15.26 Silberschatz, Galvin and Gagne ©2009
End
Operating System Concepts with Java – 8th Edition 15.27 Silberschatz, Galvin and Gagne ©2009
The Linux System
Operating System Concepts with Java – 8th Edition 16.1 Silberschatz, Galvin and Gagne ©2009
Objectives
◼ To explore the history of the UNIX operating system from which Linux is derived and the principles which Linux is designed upon
◼ To examine the Linux process model and illustrate how Linux schedules processes and provides interprocess communication
◼ To look at memory management in Linux
◼ To give some practical tips on how to use Linux
Operating System Concepts with Java – 8th Edition 16.2 Silberschatz, Galvin and Gagne ©2009
The Linux System
◼ Linux History
◼ Design Principles
◼ Process Management ◼ Scheduling
◼ Memory Management ◼ Security
◼ Practical Tips
Operating System Concepts with Java – 8th Edition
16.3 Silberschatz, Galvin and Gagne ©2009
History
◼ Linux is a modern, free operating system based on UNIX standards
◼ Linux is a Unix clone written from scratch by Linus Torvalds with
assistance from a loosely-knit team of hackers across the Net.
◼ Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs.
◼ Linux and Unix strive to be POSIX compliant.
◼ 64% of the world’s servers run some variant of Unix or Linux. The
Android phone run Linux.
◼ Many, varying Linux Distributions including the kernel, applications, and management tools
Operating System Concepts with Java – 8th Edition 16.4 Silberschatz, Galvin and Gagne ©2009
Linux Distributions
◼ Standard, precompiled sets of packages, or distributions, include the basic Linux system, system installation and management utilities, and ready-to- install packages of common UNIX tools
◼ The first distributions managed these packages by simply providing a means of unpacking all the files into the appropriate places; modern distributions include advanced package management
◼ Red Hat and Debian are popular distributions from commercial and noncommercial sources, respectively.
◼ A table providing an overview and comparison of most Linux distributions is available at
http://en.wikipedia.org/wiki/Comparison_of_Linux_distributions
Operating System Concepts with Java – 8th Edition 16.5 Silberschatz, Galvin and Gagne ©2009
Linux Distributions
Source: http://www.muylinux.com/wp-content/uploads/2009/04/logos-distros.jpg
Operating System Concepts with Java – 8th Edition 16.6 Silberschatz, Galvin and Gagne ©2009
KCL-NMS Operating System Support
NMS Windows 10, 8.1
•Desktops and laptops supported
•Integrated with NMS networked storage (home directories and shared folders) •Anti-virus and automatic patching enabled
•Laptops configured with encryption (GDPR compliant)
NMS CentOS
•Desktops supported
•Integrated with NMS networked storage (home directories and shared folders) •Patching schedule managed by NMS Computing Support
Source: https://apps.nms.kcl.ac.uk/wiki/computingsupport/provision/start#nms_windows_10_81
Operating System Concepts with Java – 8th Edition 16.7 Silberschatz, Galvin and Gagne ©2009
KCL-NMS Operating System Support
Note: In summer 2019 the university began a project to transition to Ubuntu as University standard Linux distribution. CentOS will continue to supported for the 2019/20 academic year. A migration plan for existing CentOS systems will be planned in 2020.
NMS Ubuntu
Launching for the start of the 2019/20 academic year for deployment to new PhD students using Linux.
•Desktops and laptops supported
Mac OS
•NMS Computing Support will assist with initial setup of devices for encryption and network drive access
•Support is provided on a “best efforts” basis
•The Support Waiver Disclaimer will need to be accepted
Note: There are efforts underway to provide official support mechanisms for Mac users, and
this is being worked on in collaboration with King’s IT.
Source: https://apps.nms.kcl.ac.uk/wiki/computingsupport/provision/start#nms_windows_10_81
Operating System Concepts with Java – 8th Edition 16.8 Silberschatz, Galvin and Gagne ©2009
The Linux System
◼ Linux History
◼ Design Principles
◼ Process Management ◼ Scheduling
◼ Memory Management ◼ Security
◼ Practical Tips
Operating System Concepts with Java – 8th Edition
16.9 Silberschatz, Galvin and Gagne ©2009
Design Principles
◼ Linux is a multiuser, multitasking system with a full set of UNIX-compatible tools
◼ Its file system adheres to traditional UNIX semantics, and it fully implements the standard UNIX networking model
◼ Main design goals are speed, efficiency, and standardization
◼ Linux is designed to be compliant with the relevant POSIX documents;
Operating System Concepts with Java – 8th Edition 16.10 Silberschatz, Galvin and Gagne ©2009
Components of a Linux System
Operating System Concepts with Java – 8th Edition 16.11 Silberschatz, Galvin and Gagne ©2009
Components of a Linux System (Cont)
◼ Like most UNIX implementations, Linux is composed of three main bodies of code; the most important distinction between the kernel and all other components
◼ The kernel is responsible for maintaining the important abstractions of the operating system
⚫ Kernel code executes in kernel mode with full access to all the physical resources of the computer
⚫ All kernel code and data structures are kept in the same single address space
Operating System Concepts with Java – 8th Edition 16.12 Silberschatz, Galvin and Gagne ©2009
Components of a Linux System (Cont)
◼ The system libraries define a standard set of functions through which applications interact with the kernel, and which implement much of the operating-system functionality that does not need the full privileges of kernel code
◼ The system utilities perform individual specialized management tasks
Operating System Concepts with Java – 8th Edition 16.13 Silberschatz, Galvin and Gagne ©2009
The Linux System
◼ Linux History
◼ Design Principles
◼ Process Management ◼ Scheduling
◼ Memory Management ◼ Security
◼ Practical Tips
Operating System Concepts with Java – 8th Edition
16.14 Silberschatz, Galvin and Gagne ©2009
Process Management
◼ UNIX process management separates the creation of processes and the running of a new program into two distinct operations.
⚫ The fork system call creates a new process
⚫ A new program is run after a call to execve
◼ Under UNIX, a process encompasses all the information that the operating system must maintain to track the context of a single execution of a single program
◼ Under Linux, process properties fall into three groups: the process’s identity, environment, and context
Operating System Concepts with Java – 8th Edition 16.15 Silberschatz, Galvin and Gagne ©2009
Process Identity
◼ Process ID (PID). The unique identifier for the process; used to specify processes to the operating system when an application makes a system call to signal, modify, or wait for another process
◼ Credentials. Each process must have an associated user ID and one or more group IDs that determine the process’s rights to access system resources and files
◼ Personality. Not traditionally found on UNIX systems, but under Linux each process has an associated personality identifier that can slightly modify the semantics of certain system calls
⚫ Used primarily by emulation libraries to request that system calls be compatible with certain specific flavors of UNIX
Operating System Concepts with Java – 8th Edition 16.16 Silberschatz, Galvin and Gagne ©2009
Process Environment
◼ The process’s environment is inherited from its parent, and is composed of two null-terminated vectors:
⚫ The argument vector lists the command-line arguments used to invoke the running program; conventionally starts with the name of the program itself
⚫ The environment vector is a list of “NAME=VALUE” pairs that associates named environment variables with arbitrary textual values
◼ Passing environment variables among processes and inheriting variables by a process’s children are flexible means of passing information to components of the user-mode system software
◼ The environment-variable mechanism provides a customization of the operating system that can be set on a per-process basis, rather than being configured for the system as a whole
Operating System Concepts with Java – 8th Edition 16.17 Silberschatz, Galvin and Gagne ©2009
Process Context
◼ The (constantly changing) state of a running program at any point in time
◼ The scheduling context is the most important part of the process context; it is the information that the scheduler needs to suspend and restart the process
◼ The kernel maintains accounting information about the resources currently being consumed by each process, and the total resources consumed by the process in its lifetime so far
Operating System Concepts with Java – 8th Edition 16.18 Silberschatz, Galvin and Gagne ©2009
Processes and Threads
◼ Linux uses the same internal representation for processes and threads; a thread is simply a new process that happens to share the same address space as its parent
◼ A distinction is only made when a new thread is created by the clone system call
⚫ fork creates a new process with its own entirely new process context
⚫ clone creates a new process with its own identity, but that is allowed to share the data structures of its parent
◼ Using clone gives an application fine-grained control over exactly what is shared between two threads
Operating System Concepts with Java – 8th Edition 16.19 Silberschatz, Galvin and Gagne ©2009
The Linux System
◼ Linux History
◼ Design Principles
◼ Kernel Modules
◼ Process Management ◼ Scheduling
◼ Memory Management ◼ Security
◼ Practical Tips
Operating System Concepts with Java – 8th Edition
16.20 Silberschatz, Galvin and Gagne ©2009
Scheduling
◼ The job of allocating CPU time to different tasks within an operating system
◼ While scheduling is normally thought of as the running and interrupting of processes, in Linux, scheduling also includes the running of the various kernel tasks
◼ Running kernel tasks encompasses both tasks that are requested by a running process and tasks that execute internally on behalf of a device driver
◼ As of 2.5, new scheduling algorithm – preemptive, priority-based ⚫ Real-time range
⚫ nice value
Operating System Concepts with Java – 8th Edition 16.21 Silberschatz, Galvin and Gagne ©2009
Relationship Between Priorities and Time-slice Length
Operating System Concepts with Java – 8th Edition 16.22 Silberschatz, Galvin and Gagne ©2009
Process Scheduling
◼ Linux uses two process-scheduling algorithms:
⚫ A time-sharing algorithm for fair preemptive scheduling
between multiple processes
⚫ A real-time algorithm for tasks where absolute priorities are more important than fairness
◼ A process’s scheduling class defines which algorithm to apply
◼ In time-sharing algorithm, tasks are assigned dynamic priorities that are based on the nice value plus or minus a value up to the value 5.
Operating System Concepts with Java – 8th Edition 16.23 Silberschatz, Galvin and Gagne ©2009
Process Scheduling (Cont)
◼ Linux implements the FIFO and round-robin real-time scheduling classes; in both cases, each process has a priority in addition to its scheduling class
⚫ The scheduler runs the process with the highest priority; for equal- priority processes, it runs the process waiting the longest
⚫ FIFO processes continue to run until they either exit or block
⚫ A round-robin process will be preempted after a while and moved to the end of the scheduling queue, so that round-robing processes of equal priority automatically time-share between themselves
Operating System Concepts with Java – 8th Edition 16.24 Silberschatz, Galvin and Gagne ©2009
The Linux System
◼ Linux History
◼ Design Principles
◼ Kernel Modules
◼ Process Management ◼ Scheduling
◼ Memory Management ◼ Security
◼ Practical Tips
Operating System Concepts with Java – 8th Edition
16.25 Silberschatz, Galvin and Gagne ©2009
Memory Management
◼ Linux’s physical memory-management system deals with allocating and freeing pages, groups of pages, and small blocks of memory
◼ It has additional mechanisms for handling virtual memory, memory mapped into the address space of running processes
◼ Due to specific hardware characteristics, Linux splits memory into 3 different zones due to hardware characteristics
Operating System Concepts with Java – 8th Edition 16.26 Silberschatz, Galvin and Gagne ©2009
Relationship of Zones and Physical Addresses on 80x86
Operating System Concepts with Java – 8th Edition 16.27 Silberschatz, Galvin and Gagne ©2009
Virtual Memory
◼ The VM system maintains the address space visible to each process: It creates pages of virtual memory on demand, and manages the loading of those pages from disk or their swapping back out to disk as required
◼ The VM manager maintains two separate views of a process’s address space:
⚫ A logical view describing instructions concerning the layout of the address space
The address space consists of a set of nonoverlapping regions, each representing a continuous, page-aligned subset of the address space
⚫ A physical view of each address space which is stored in the hardware page tables for the process
Operating System Concepts with Java – 8th Edition 16.28 Silberschatz, Galvin and Gagne ©2009
Virtual Memory (Cont)
◼ Virtual memory regions are characterized by:
⚫ The backing store, which describes from where the pages for a region come; regions are usually backed by a file or by nothing (demand-zero memory)
⚫ The region’s reaction to writes (page sharing or copy-on-write)
◼ The kernel creates a new virtual address space
1. When a process runs a new program with the exec system call 2. Upon creation of a new process by the fork system call
Operating System Concepts with Java – 8th Edition 16.29 Silberschatz, Galvin and Gagne ©2009
Virtual Memory (Cont)
◼ The VM paging system relocates pages of memory from physical memory out to disk when the memory is needed for something else
◼ The VM paging system can be divided into two sections:
⚫ The pageout-policy algorithm decides which pages to write out to
disk, and when
⚫ The paging mechanism actually carries out the transfer, and pages data back into physical memory as needed
Operating System Concepts with Java – 8th Edition 16.30 Silberschatz, Galvin and Gagne ©2009
Static and Dynamic Linking
◼ A program whose necessary library functions are embedded directly in the program’s executable binary file is statically linked to its libraries
◼ The main disadvantage of static linkage is that every program generated must contain copies of exactly the same common system library functions
◼ Dynamic linking is more efficient in terms of both physical memory and disk-space usage because it loads the system libraries into memory only once
Operating System Concepts with Java – 8th Edition 16.31 Silberschatz, Galvin and Gagne ©2009
The Linux System
◼ Linux History
◼ Design Principles
◼ Kernel Modules
◼ Process Management ◼ Scheduling
◼ Memory Management ◼ Security
◼ Practical Tips
Operating System Concepts with Java – 8th Edition
16.32 Silberschatz, Galvin and Gagne ©2009
Security
◼ The pluggable authentication modules (PAM) system is available under Linux
◼ PAM is based on a shared library that can be used by any system component that needs to authenticate users
◼ Access control under UNIX systems, including Linux, is performed through the use of unique numeric identifiers (uid and gid)
◼ Access control is performed by assigning objects a protections mask, which specifies which access modes—read, write, or execute—are to be granted to processes with owner, group, or world access
Operating System Concepts with Java – 8th Edition 16.33 Silberschatz, Galvin and Gagne ©2009
Security (Cont)
◼ Linux augments the standard UNIX setuid mechanism in two ways:
⚫ It implements the POSIX specification’s saved user-id mechanism, which allows a process to repeatedly drop and reacquire its effective uid
⚫ It has added a process characteristic that grants just a subset of the rights of the effective uid
◼ Linux provides another mechanism that allows a client to selectively pass access to a single file to some server process without granting it any other privileges
Operating System Concepts with Java – 8th Edition 16.34 Silberschatz, Galvin and Gagne ©2009
The Linux System
◼ Linux History
◼ Design Principles
◼ Kernel Modules
◼ Process Management ◼ Scheduling
◼ Memory Management ◼ Security
◼ Practical Tips
Operating System Concepts with Java – 8th Edition
16.35 Silberschatz, Galvin and Gagne ©2009
Connecting to a Linux Host - Windows Client
◼ Run MobaXterm educational app from the start menu.
◼ Create a new session which will open a new window asking to
select the session type which is SSH.
◼ Enter the host name: YOUKNUMBER@bastion.nms.kcl.ac.uk
◼ Login:
◼ Password
Operating System Concepts with Java – 8th Edition 16.36 Silberschatz, Galvin and Gagne ©2009
Connecting to a Linux Host – Mac OS X Client
◼ Terminal
⚫ Type ssh –X YOUKNUMBER@bastion.nms.kcl.ac.uk
⚫ or ssh –Y YOUKNUMBER@bastion.nms.kcl.ac.uk (less secure)
Operating System Concepts with Java – 8th Edition 16.37 Silberschatz, Galvin and Gagne ©2009
Practice with Linux
“Small programs that do one thing well”
Network: ssh, scp, ping, telnet, nslookup, wget
Shells: BASH, TCSH, alias, watch, clear, history, chsh, echo, set, setenv, xargs System Information: whoami, man, info, which, free, echo, date, cal, df, free Command Information: man, info
Symbols: |, >, >>, <, &, >&, 2>&1, ;, ~, ., .., $!, !:
Filters: grep, egrep, more, less, head, tail
Hotkeys:
File System: ls, mkdir, cd, pwd, mv, ln, touch, cat, file, find, diff, cmp, /net/
Line Editors: awk, sed
File Editors: vim, gvim, emacs –nw, emacs
Process Management: ps, top, kill, killall, fg, bg
SGE (Sun Grid Engine)Cluster: qsh, qstat, qsub, qhost
Operating System Concepts with Java – 8th Edition 16.38 Silberschatz, Galvin and Gagne ©2009
The SHELL
◼ A shell is a command interpreter that allows you to type commands from the keyboard to interact with the operating system kernel.
◼ A shell is a computer program that interprets the commands you type and sends them to the operating system. Secondly, it provide a programming environment consisting of environment variables.
◼ Sh: The sh shell was the earliest shell, being developed for UNIX back in the late 1970s.
◼ Bash :The bash shell is an improved version of the sh shell and is one of the most popular shells today. It’s the default shell used by most Linux distributions.
◼ KCL-NMS support BASH. The most popular and powerful Linux shell today is BASH.
◼ To determine your shell type:
⚫ echo $SHELL (shell prints contents of env)
◼ To determine the path to the shell program, type: ⚫ which bash
Operating System Concepts with Java – 8th Edition 16.39 Silberschatz, Galvin and Gagne ©2009
System information
◼ After you connect, type
⚫ whoami
⚫ hostname
⚫ date
⚫ cal
⚫ Free (displays the total amount of free and used memory and the buffers used by the kernel.
◼ Commands have three parts; command, options and parameters. Example: cal –j 3 1999. “cal” is the command, “-j” is an option (or switch), “3” and “1999” are parameters.
◼ Options have long and short forms. Example: ⚫ date –u
⚫ date –universal
Operating System Concepts with Java – 8th Edition 16.40 Silberschatz, Galvin and Gagne ©2009
Output of the Commands
Output of the hostname, date, cal and free
Operating System Concepts with Java – 8th Edition 16.41 Silberschatz, Galvin and Gagne ©2009
Other commands that you can try on your own time!
/ : denote root directory
./ : denote current directory
halt This command shuts down the operating system, but can only be run by the root user.
reboot This command shuts down and restarts the operating system. It also can only be run by root.
Try the history command
Choose from the command history by using the up ↑ and down ↓ arrows
What do the left ← and right → arrow do on the command line?
Try the and
top This command is a very useful command that displays a list of all applications
and processes currently running on the system.
which This command is used to display the full path to a shell command or utility. Ex: which ls
It display: /bin/ls
Operating System Concepts with Java – 8th Edition 16.42 Silberschatz, Galvin and Gagne ©2009
End of Lecture
Operating System Concepts with Java – 8th Edition 16.43 Silberschatz, Galvin and Gagne ©2009