Transcript PPT
Networking Operating Systems (CO32010)
3.1
Introduction
2. Processes
3.2
Interprocess communication and
3.3
Flags and semaphores
scheduling
3.4
RPC
3.5
Multi-processor systems
Exercises
1.3.6
Operating
Systems
7. Encryption
Objectives:
6. Routers
3. Distributed
processing
• To define the concept of distributed processing, and
contrast centralized systems against distributed ones.
8. NT,
UNIX control, such as
• To define mechanisms
of interprocess
andand
NetWare
pipes, semaphores, flags,
message queues.
• To define, in detail, how semaphores are used, and how
the can prevent deadlock.
• To define the conditions for deadlock.
• To outline algorithms to prevent deadlock, such as the
4. Distributed
Algorithm.
5.Banker’s
Routing
• Toprotocols
outline practical interprocess control protocols,
file systems
especially RPC.
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.1 Centralised v. Distributed
Distributed:
Decision making
Account management
Logistics
Head
Office
Customers
Staff
Logistics
Regional
Office
Local
Office
ATM
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.2 Client/server architecture
Client requests
a remote process
and passes process
parameters
Network
Server runs process and
returns the results to the
client
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.3 IPC methods
Connection over
a network over
locally
Process
A
Process
A
Process
A
Shared
memory
Process
A
Sleep until
ready
Process
B
Process
A
Process
B
3. Shared
memory
Process A | Process B
http://www.soc.napier.ac.uk/~bill/nos.html
1. Socket
2. Semaphores
Message
queue
Gets access
Resource
to resource
and increments
a semaphore
(wait)
Process
B
Process
B
Process
B
5. Message
queue
4. Pipe
bill@napier, 2001
3.4 Semaphore usage in a program
Process A
Semaphore
1
wait ();
Wait decrements
the semaphore
0
code that must be
mutually exclusive
signal ();
Process B will go
to sleep as the
semaphore has
a zero value
Process B
wait ();
1
Signal increments
the semaphore
Process B will wake
up when the
semaphore value
becomes a non-zero
http://www.soc.napier.ac.uk/~bill/nos.html
code that must be
mutually exclusive
signal ();
bill@napier, 2001
3.5 Consumer-producer example
#define MAX_BUFF 100
int buffer_count=0;
/*
/*
maximum items in buffer
*/
current number of items in buffer */
void producer_buffer(void)
{
while (TRUE){/* Infinite loop */
put_item();
/*
Put item*/
if (buffer_count==MAX_BUFF) sleep(); /* Sleep, if buffer full */
enter_item(); /*
Add item to buffer*/
buffer_count = buffer_count + 1; /*
Increment number of items in the
if (buffer_count==1) wakeup(consumer);
/*was buffer empty?*/
}
}
void consumer_buffer(void)
{
while (TRUE) {/* Infinite loop */
if (buffer_count==0) sleep(); /* Sleep, if buffer empty */
get_item(); /* Get item */
buffer_count = buffer_count - 1; /* Decrement number of items
in the buffer*/
if (buffer_count==MAX_BUFF-1) wakeup(producer_buffer);
consume_item(); /*remove item*/
}
}
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.6 Deadlock
•
•
Resource locking. This is where a process is waiting for a resource
which will never become available. Some resources are pre-emptive,
where processes can release their access on them, and give other
processes a chance to access them. Others, though, are non-preemptive, and processes are given full rights to them. No other
processes can then get access to them until the currently assigned
process is finished with them. An example of this is with the
transmission and reception of data on a communication system. It
would not be a good idea for a process to send some data that required
data to be received, in return, to yield to another process which also
wanted to send and receive data.
Starvation. This is where other processes are run, and the deadlocked
process is not given enough time to catch the required event. This can
occur when processes have a low priority compared with other ones, as
higher priority tasks tend to have a better chance to access the
required resources.
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.7 Analogy to deadlock
C
B
A
D
E
F
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.8 Four conditions for deadlock
• Mutual exclusion condition. This is where processes get
exclusive control of required resources, and will not yield the
resource to any other process.
• Wait for condition. This is where processes keep exclusive
control of acquired resources while waiting for additional
resources.
• No pre-emption condition. This is where resources cannot be
removed from the processes which have gained them, until they
have completed their access on them.
• Circular wait condition. This is a circular chain of processes on
which each process holds one or more resources that are
requested by the next process in the chain.
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.9 Banker’s Algorithm (Safe condition)
Process A requires a maximum of 50MB.
Process B requires a maximum of 40MB.
Process C requires a maximum of 60MB.
Process D requires a maximum of 40MB.
The current state would be safe as Process A can complete which releases
50 MB (which allows the other processes to complete):
Process
Current allocation
Maximum allocation
required
A
40
50
B
20
40
C
20
60
D
10
40
Resource unallocated
10
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.10 Banker’s Algorithm(Unsafe condition)
Process A requires a maximum of 50MB.
Process B requires a maximum of 40MB.
Process C requires a maximum of 60MB.
Process D requires a maximum of 40MB.
The current state would be unsafe as no process can complete:
Process
Current allocation
Maximum allocation
required
A
15
50
B
30
40
C
45
60
D
0
40
Resource unallocated
5
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.11 Banker’s Algorithm
Each resource has exclusive access to resources that have been
granted to it.
Allocation is only granted if there is enough allocation left for at least
one process to complete, and release its allocated resources.
Processes which have a rejection on a requested resource must wait
until some resources have been released, and that the allocated
resource must stay in the safe region.
Problems:
Requires processes to define their maximum resource requirement.
Requires the system to define the maximum amount of a resource.
Requires a maximum amount of processes.
Requires that processes return their resources in a finite time.
Processes must wait for allocations to become available. A slow
process may stop many other processes from running as it hogs the
allocation.
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.12 RPC
Application
Application
program
program
Remote
Remote
process
process
Session layer (RPC) supports
the running of remote
processes and passing run
parameters and results
Transport layer sets up
a virtual connection, and
streams data
Network layer responsible
for the routing data over the
network and delivering it at the
destination
Application
program
Application
Application
Presentation
Presentation
Session
Session
RPC
Transport
Transport
TCP/IP
UDP/IP
Network
Network
Network
Data
DataLink
Link
Physical
Physical
Ethernet/ISDN/
FDDI/ATM/etc
Data link
http://www.soc.napier.ac.uk/~bill/nos.html
bill@napier, 2001
3.13 RPC operation
Server
Client
The caller process
sends a call message,
with all the
procedure’s
parameters
Server process waits
for a call
Process, and
parameters
Server reads
parameters and runs
the process
Caller process waits
for a response
The caller process
sends a call message,
with all the
procedure’s
parameters
Server sends results
to the client
Results
http://www.soc.napier.ac.uk/~bill/nos.html
Server process waits
for a call
bill@napier, 2001