Transcript 06_OSSupport

Organizational Communications and
Distributed Object Technologies
Week 11: Operating Systems
Support Coulouris Chapter 6
95-702 OCT
Master of Information System
Management
1
OS Support
• Modern operating systems support
distributed applications and
middleware
– Network OS
– Distributed OS
– Processes, threads, ports, and
support for invocation mechanisms.
95-702 OCT
Master of Information System
Management
2
System layers
Applications, services
OS: kernel,
libraries &
servers
OS1
Process es , threads,
communic ation, ...
Figure 2.1
Middlew are
Software and hardware
service layers in distributed
systems
OS2
Process es , threads,
Applications, services
ation, ...
communic
Platform
Middlew are
Computer &
netw ork hardw are
Computer &
netw ork hardw are
Operating s ys tem
Node 1
95-702 OCT
Master of Information System
Management
Node 2
Platform
Computer and netw ork hardw are
3
Middleware Support
• Middleware implements abstractions that
support network-wide programming.
Examples:
• RPC and RMI (Sun RPC, Corba, Java RMI,
Web Services)
• Messaging, event distribution and filtering
(Corba Event Notification, JMS, MOM)
• Resource discovery for mobile and ubiquitous
computing
• QoS Guarantees for multimedia streaming
95-702 OCT
Master of Information System
Management
4
OS Types
• Traditional DOS's (e.g. early Unix,
Windows 3.0)
– simplify, protect and optimize the use of local
resources
• Network OS's (e.g. UNIX, Windows NT)
– do the same but they also support a wide range of
communication standards.
– For example, TCP and UDP sockets are available
from the operating system.
- Machines are still autonomous
95-702 OCT
Master of Information System
Management
5
OS Types
A distributed OS:
• Presents users (and applications) with an integrated computing
platform that hides the individual computers.
• Has control over all of the nodes (computers) in the network and
allocates their resources to tasks without user involvement.
• In a distributed OS, the user doesn't know (or care) where
his programs are running.
• Research examples have been built.
• Not in widespread use.
The combination of middleware plus a network O.S. provides for
some autonomy and some distribution.
95-702 OCT
Master of Information System
Management
6
OS Support Required by
Middleware
An OS manages resources:
– processing, memory, persistent storage and communication.
The task of the OS is to:
– raise the programming interface for these
resources to a more useful level:
• By providing abstractions of the basic resources such as:
processes, unlimited virtual memory, files, communication
channels
• Protection of the resources used by applications
• Concurrent processing to enable applications to complete
their work with minimum interference from other applications
– provide the resources needed for (distributed) services and
applications to complete their task:
• Communication - network access provided
• Processing - processors scheduled at the relevant computers
95-702 OCT
Master of Information System
Management
7
Core OS functionality
Figure 6.2
Proc es s manager
Communic ation
manager
Thread manager
Memory manager
Supervisor
95-702 OCT
Master of Information System
Management
8
Core OS functionality
Create, synchronize
and schedule
Handles the creation of and operation on processes.
Proc es s manager
Typical kernal
services
run with
complete
access
Communic ation
manager
Thread manager
Physical
and virtual
memory
Machine
dependent
code
Memory manager
Supervisor
95-702 OCT
Master of Information System
Management
Between threads in different 9
processes
Threads concept and
implementation
The traditional process was
found to be unequal to the
demands of distributed
systems
Process
Threads can improve
throughput but all this
sharing can be tricky
Heap (dynamic storage,
objects, global variables)
95-702 OCT
Master of Information System
Management
Thread activations
Activation stacks
(parameters, local variables)
'text' (program code)
system-provided resources
(sockets, windows, open files)
10
The Advantage of
Threads(1)
Assume a single process computer and all arrivals are
queued with no threading.
1 request = 8 ms of disk input + 2 ms of processor time
= 10 ms
N requests
1000 ms
======= X ====== = 100 Request/Second
N*10 MS
1 Second
95-702 OCT
Master of Information System
Management
11
The Advantage of
Threads(2)
Allow for two threads. The processor runs in parallel with I/O.
Thread1
Thread2
8,2,8,2,8,2,8,2,8,2,8
8,2,8,2,8,2,8,2,8
While waiting for disk the other thread
can use the CPU
N request is roughly (and ideally) N * 8 ms.
N Requests
=======
N*8 ms
1000 ms
X =====
1 second
= 125 Requests/Second
If a cache is associated with the disk and you add more processors
this gets even better.
95-702 OCT
Master of Information System
Management
12
Client and server with
threads
Figure 6.5
Input-output
Thread 2 makes
Receipt &
requests to server
queuing
and may block until
reply.
Thread 1
generates
results for
server and
needs no reply.
Requests
N threads
Server
Client
The 'worker pool' architecture
N threads read from a shared queue of
95-702 OCTarrivals.
Master of Information System
Management
13
Alternative Server
Architectures
FigureThreading
6.6
server
process
workers
I/O
remote
objects
a. Thread-per-request
server
process per-connection threads
remote
objects
b. Thread-per-connection
server
process
per-object threads
I/O
remote
objects
c. Thread-per-object
(a) would be useful for UDP-based service, e.g. NTP. See Fig.
4.6.
(b) is the most commonly used - matches the TCP connection
model. Many requests may be made over the connection.
(c) is used where the service is encapsulated as an object. E.g.
could have multiple shared whiteboards with one thread
95-702 OCT
each. Each object
has only one thread, avoiding the need for
14
Master of Information System
thread synchronization
within
objects.
Management
Threads Versus Multiple
Processes
• Creating a thread is (much) cheaper than a
process (~10-20 times)
• Switching to a different thread in same process is
(much) cheaper (5-50 times)
• Threads within same process can share data and
other resources more conveniently and efficiently
(without copying or messages)
• Processes are generally protected from each other.
• Threads within a process are not protected from
each other.
95-702 OCT
Master of Information System
Management
15
Threads Implementation
Threads can be implemented:
– In the OS kernel (Win NT, Solaris,
Mach)
– At user level (e.g. by a thread library:
C threads, pthreads),
– In the language (Ada, Java).
95-702 OCT
Master of Information System
Management
16
But Threading Means
Sharing
• E.g. Global variables may be
shared.
• This permits threads to share
information and coordinate.
• But often times, a thread needs
private access to data and we are
concerned that an another thread
will interrupt this access.
95-702 OCT
Master of Information System
Management
17
Mutual Exclusion?
occupied = false
Begin
while(occupied) do {}
occupied = true
End
{ critical section }
Begin
occupied = false
End
95-702 OCT
Master of Information System
Management
Begin
while(occupied) do
{}
occupied = true
End
{ critical section }
Begin
occupied = false
End
18
Mutual Exclusion?
occupied = true
Begin
while(occupied) do {}
occupied = true
End
{ critical section }
Begin
occupied = false
End
95-702 OCT
Master of Information System
Management
Begin
while(occupied) do
{}
occupied = true
End
{ critical section }
Begin
occupied = false
End
19
Mutual Exclusion?
occupied = true
Begin
while(occupied) do {}
occupied = true
End
{ critical section }
Begin
occupied = false
End
95-702 OCT
Master of Information System
Management
Begin
while(occupied) do
{}
occupied = true
End
{ critical section }
Begin
occupied = false
End
20
Mutual Exclusion?
occupied = false
Begin
while(occupied) do {}
occupied = true
End
{ critical section }
Begin
occupied = false
End
95-702 OCT
Master of Information System
Management
Begin
while(occupied) do
{}
occupied = true
End
{ critical section }
Begin
occupied = false
End
21
Mutual Exclusion?
occupied = false
Begin
while(occupied) do {}
occupied = true
End
{ critical section }
Begin
occupied = false
End
Begin
while(occupied) do
{}
occupied = true
End
{ critical section }
Begin
occupied = false
End
The busy wait loop may be replaced with a call on wait().
95-702 OCT
Master of Information System
Management
22
Mutual Exclusion? No.
occupied = false
Begin
while(occupied) do {}
occupied = true
End
{ critical section }
Begin
occupied = false
End
95-702 OCT
Master of Information System
Management
Begin
while(occupied) do
{}
occupied = true
End
{ critical section }
Begin
occupied = false
End
23
Mutual Exclusion? No.
occupied = true
Begin
while(occupied) do {}
occupied = true
End
{ critical section }
Begin
occupied = false
End
95-702 OCT
Master of Information System
Management
Begin
while(occupied) do
{}
occupied = true
End
{ critical section }
Begin
occupied = false
End
24
Why be concerned about
mutual
exclusion anyway?
occupied = true
Begin
while(occupied) do {}
occupied = true
End
{ critical section
x = 4;}
Begin
occupied = false
End
Begin
while(occupied) do
{}
occupied = true
End
{ critical section
x = 9000; }
Begin
occupied = false
End
Perhaps the writing of 9000 to x is interrupted by the writing of 4.
Now, x has a little95-702
of 9000
and a little of 4.
OCT
25
Master of Information System
Management
Dekker’s Algorithm (1964)
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Dekker solves the problem
using software for two
processes.
Dijkstra and other solutions
exist for more than two
processes.
26
Dekker’s Algorithm (1964)
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Begin
occupied2 = true
while(occupied1) {
if(which == 1) {
occupied2 = false
while(which == 1) {}
occupied2 = true
}
}
End
critical section
Begin
which = 1
occupied2 = false
27
End
Dekker’s Algorithm (1964)
occupied1 false occupied2 false which 1
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Begin
occupied2 = true
while(occupied1) {
if(which == 1) {
occupied2 = false
while(which == 1) {}
occupied2 = true
}
}
End
critical section
Begin
which = 1
occupied2 = false
28
End
Dekker’s Algorithm (1964)
occupied1 false occupied2 false which 2
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Begin
occupied2 = true
while(occupied1) {
if(which == 1) {
occupied2 = false
while(which == 1) {}
occupied2 = true
}
}
End
critical section
Begin
which = 1
occupied2 = false
29
End
Dekker’s Algorithm (1964)
occupied1 true occupied2 false which 2
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Begin
occupied2 = true
while(occupied1) {
if(which == 1) {
occupied2 = false
while(which == 1) {}
occupied2 = true
}
}
End
critical section
Begin
which = 1
occupied2 = false
30
End
Dekker’s Algorithm (1964)
occupied1 true occupied2 false which 2
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Begin
occupied2 = true
while(occupied1) {
if(which == 1) {
occupied2 = false
while(which == 1) {}
occupied2 = true
}
}
End
critical section
Begin
which = 1
occupied2 = false
31
End
Dekker’s Algorithm (1964)
occupied1 false occupied2 false which 2
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Begin
occupied2 = true
while(occupied1) {
if(which == 1) {
occupied2 = false
while(which == 1) {}
occupied2 = true
}
}
End
critical section
Begin
which = 1
occupied2 = false
32
End
Dekker’s Algorithm (1964)
occupied1 false occupied2 false which 2
Begin
occupied1 = true
while(occupied2) {
if(which == 2) {
occupied1 = false
while(which == 2) {}
occupied1 = true
}
}
End
critical section
Begin
which = 2
occupied1 = false
End
95-702 OCT
Master of Information System
Management
Begin
occupied2 = true
while(occupied1) {
if(which == 1) {
occupied2 = false
while(which == 1) {}
occupied2 = true
}
}
End
critical section
Begin
which = 1
occupied2 = false
33
End
Dijkstra’s Semaphore
(1965)
• From train terminology, one train
at a time on one section of track.
• A semaphore is an integer variable
that may be changed by just two
primitive operations - P and V.
• P and V stand for Dutch
equivalents of test and increment.
• P an V may not be interrupted.
Processors are built this way.
95-702 OCT
Master of Information System
Management
34
Semaphore Operations
S
Test or wait
P(s): if (s > 0) s = s - 1
else suspend this process
Increment or signal
V(s): if a process is suspended as a
result of P(s) then resume it
else s = s + 1
95-702 OCT
Master of Information System
Management
35
Mutual Exclusion
S
Begin
P(s)
End
critical section
Begin
V(s)
End
95-702 OCT
Master of Information System
Management
1
Begin
P(s)
End
critical section
Begin
V(s)
End
36
Mutual Exclusion
S
1
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
95-702 OCT
Master of Information System
Management
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
37
Mutual Exclusion
S
0
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
95-702 OCT
Master of Information System
Management
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
38
Mutual Exclusion
S
0
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
95-702 OCT
Master of Information System
Management
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
39
Mutual Exclusion
S
0
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
Begin
if(s > 0) s = s - 1
else suspend this process
End
critical section
Begin
if a process is suspended
as a result of P(s), resume it
else s = s + 1
End
S changes back to 1.
Quiz: What will happen if s starts off at 0?
95-702 OCT
Master of Information System
Management
40
Semaphores
• May be extended to mutual exclusion
over multiple processes.
• May be used to solve the producer
consumer problem.
Process P1
Process P2
:
:
E1
E2
:
:
• We need E1 to produce before E2
consumes.
95-702 OCT
Master of Information System
Management
41
Producer/Consumer
Process P1
:
E1
store data
in buffer
95-702 OCT
Master of Information System
Management
Process P2
:
E2
read data from
buffer
42
Producer/Consumer
Process P1
:
:
Event E1
V(S)
Process P2
:
P(S)
Event E2
:
S is initially zero. Assume writes are
queued.
Do three writes followed by four
reads. What happens?
95-702 OCT
Master of Information System
Management
43
The Circular Buffer Problem Is
Generalized Producer Consumer
occupied: semaphore (initially 0 - number of filled locations)
empty : semaphore (initially n - number of empty locations)
j=0
repeat
We can’t write
if none are
empty.
P(empty)
store data in location j
j = (j + 1) mod n
V(occupied)
Until forever
95-702 OCT
Master of Information System
Management
i=0
repeat
We can’t read
if none are
occupied.
P(occupied)
get data from location i
i = (i + 1) mod n
V(empty)
until forever
44
The Circular Buffer Problem Is
Generalized Producer Consumer
occupied: goes from 0 to 1
empty : goes from 3 to 2
j=0
repeat
We can’t write
if none are
empty.
P(empty)
store data in location j
j = (j + 1) mod n
V(occupied)
Until forever
95-702 OCT
Master of Information System
Management
i=0
repeat
We can’t read
if none are
occupied.
P(occupied)
get data from location i
i = (i + 1) mod n
V(empty)
until forever
45
The Circular Buffer Problem Is
Generalized Producer Consumer
occupied: goes from 1 to 2
empty : goes from 2 to 1
j=0
repeat
We can’t write
if none are
empty.
P(empty)
store data in location j
j = (j + 1) mod n
V(occupied)
Until forever
95-702 OCT
Master of Information System
Management
i=0
repeat
We can’t read
if none are
occupied.
P(occupied)
get data from location i
i = (i + 1) mod n
V(empty)
until forever
46
The Circular Buffer Problem Is
Generalized Producer Consumer
occupied: goes from 2 to 3
empty : goes from 1 to 0
j=0
repeat
We can’t write
if none are
empty.
P(empty)
store data in location j
j = (j + 1) mod n
V(occupied)
Until forever
95-702 OCT
Master of Information System
Management
i=0
repeat
We can’t read
if none are
occupied.
P(occupied)
get data from location i
i = (i + 1) mod n
V(empty)
until forever
47
The Circular Buffer Problem Is
Generalized Producer Consumer
occupied: goes from 3 to 2 and back to 3
empty : goes from 1 to 0
j=0
repeat
We can’t write
if none are
empty.
P(empty)
store data in location j
j = (j + 1) mod n
V(occupied)
Until forever
i=0
repeat
We can’t read
if none are
occupied.
P(occupied)
get data from location i
Resume
i = (i + 1) mod n
writer
V(empty)
until forever
95-702 OCT
Master of Information System
Management
48
Locks
• A lock is a variable associated with a data
item and describes the status of that item with
respect to possible operations that can be
applied to that item.
• Generally, there is one lock for each item.
• Locks provide a means of synchronizing the
access by concurrent transactions to the
items.
• Locks lead to big atomic actions.
95-702 OCT
Master of Information System
Management
49
Example: Binary Lock (1)
Lock_Item(x)
Not interleaved with other
code until this terminates or
B: if(Lock(x) == 0)
waits.
Lock(x) = 1
else {
wait until Lock(x) == 0 and
we are woken up.
GOTO B
}
95-702 OCT
Master of Information System
Management
50
Example: Binary Lock(2)
Unlock_Item(x)
Lock(x) = 0
if any transactions are waiting then
wake up one of the waiting
transactions.
Not interleaved with other
code.
95-702 OCT
Master of Information System
Management
51
Locks Can Support
Concurrent Transactions
Transaction T1
Transaction T2
Lock_Item(x)
Lock_Item(y)
T1 uses x
T2 uses y
Unlock_Item(x) Unlock_Item(y)
If x differs from y these two transactions proceed concurrently.
If both want to use x, one waits until the other completes.
95-702 OCT
Master of Information System
Management
52
Support for Communication
and Invocation
• The performance of RPC and RMI
mechanisms is critical for effective
distributed systems.
–
–
–
–
–
Typical times for 'null procedure call':
Local procedure call < 1 microsecond =10-6 sec
Remote procedure call ~ 10 ms = 10-2 sec
That is about 100 times slower!
'network time' (involving about 100 bytes
transferred, at 100 megabits/sec.) accounts for
only .01 millisecond; the remaining delays must
be in OS and middleware - latency, not
communication time.
95-702 OCT
Master of Information System
Management
53
Where Does The Time Go?
•Factors affecting RPC/RMI performance
–marshalling/unmarshalling + operation
dispatch at the server
–data copying:- application -> kernel space ->
communication buffers
–thread scheduling and context switching:including kernel entry
–protocol processing:- for each protocol layer
–network access delays:- connection setup,
network latency
95-702 OCT
Master of Information System
Management
54
Implementation of
Invocation Mechanisms
• Most invocation middleware (Corba,
Java RMI, HTTP) is implemented over
TCP
– For universal availability, unlimited message
size and reliable transfer;
– Sun RPC (used in NFS) is implemented over
both UDP and TCP and generally works
faster over UDP
– RPC is heavily used on backend systems
95-702 OCT
Master of Information System
Management
55
Implementation of
Invocation Mechanisms
• Research-based systems have
implemented much more efficient
invocation protocols
• Concurrent and asynchronous
invocations (getting a lot of
attention - Messaging)
– middleware or application doesn't
block waiting for reply to each
invocation
95-702 OCT
Master of Information System
Management
56
Invocations Between
Address Spaces
Figure 6.11
(a) System call
Control transfer via
trap instruction
Thread
Control transfer via
privileged instructions
User
Kernel
Protection domain
boundary
(b) RPC/RMI (within one computer)
Thread 1
Thread 2
User 1
Kernel
User 2
(c) RPC/RMI (between computers)
Thread 1
95-702 OCT User 1
Network
Thread 2
User 2
Kernel 1
Master of Information System
Management
Kernel 2
57
Summary
• The OS provides local support for the
implementation of distributed applications
and middleware:
– Manages and protects system resources
(memory, processing, communication)
– Provides relevant local abstractions:
• files, processes
• threads, communication ports
• Middleware provides general-purpose
distributed abstractions
– RPC, RMI, Messaging, streaming
95-702 OCT
Master of Information System
Management
59