[ C:TaPiC ]
Lab 1 Lab 2 Lab 3 Lab 4 Lab 5 Lab 6 Lab 7 Lab 8
Further work on eager queues has moved to the Eager Queue Protocol project on SourceForge.
This practical introduces the protocol UDP (user datagram protocol). As an example of UDP a scheduling mechanism is set up that combines take scheduling and FIFO (first in first out) scheduling across a network of processors.
There are many different trends in computing. For heterogeneous environments the trend has been to use ever more powerful processors based on the Von-Nuemann architecture. This trend is continuing and now virtual computers are running on top of a single processor architecture.
As computer performance increases the abiliy to design and implement better software has not kept up. A major factor limiting ease of software development is versioning and software conflicts. This continues to be the case even with advances such as the .Net framework and the Java Virtual Machine.
For the first example we will assume:
Assume we have a pool of processors, say L = N + 1 in all. Any processor can make a job request and broadcasts this request on the schedulilng channel. All of the other processors are idle and want to work. They all bid for the request and their bids conflict on the scheduling channel.
How can it be organised so that this conflict is removed and work is picked up as quickly as possible?
Let u be the unit of time. If it takes u units of time to broadcast a request and u units of time to respond to a request when there is no conflict, can we design a mechanism where the total time to allocate a job, where processors are available, is 2u?
An eager process is made up of two main components, the Worker Process and the Scheduler Process.
The scheduler process spends its life listening for and responding to job requests on the scheduling chanel. It tries to keep its worker process as busy as possible.
The worker process gets jobs from the scheduler process and ...
O-------
| O----- Data Channels
| | O---
| | |
|-----------|
| Worker |
| Process |
|-----------|
| |
|-----------|
| Scheduler |
| Process |
|-----------|
|
O-- Scheduling Channel
The datagrams transmitted on the scheduling channel have the following structure:
0 7 8 15 16 23 24 31
+--------+--------+--------+--------+
| Source | Destination |
| Port | Port |
+--------+--------+--------+--------+
| | |
| Length | Checksum |
+--------+--------+--------+--------+
| Scheduling |
| Code |
+--------+--------+--------+--------+
/ Last Known Transmission /
/ Vector /
+--------+--------+--------+--------+
The LKT vector is transmitted in every scheduling datagram and a copy is also held on every scheduler processor. The structure of the LKT vector is made up of "last known transmission" - state pairs where the first item of the pair is the last known transmission from a processor measured in transmission counts and the second item of the pair is the state of the processor when it was last known to transmit.
+------------------+-----------------+
Processor 1 | Last Known | Processor |
| Transmission | State |
+------------------+-----------------+
Processor 2 | Last Known | Processor |
| Transmission | State |
+------------------+-----------------+
Processor 3 | Last Known | Processor |
| Transmission | State |
+------------------+-----------------+
.
.
.
+------------------+-----------------+
Processor L | Last Know | Processor |
| Transmission | State |
+------------------+-----------------+
At this point it is worth considering an example. Start with no proceesors available for scheduling.
+------------------+-----------------+
| UPDATE |
+------------------+-----------------+
| 1 | WAITING |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
At some later point anoth processor wants to join the network.
+------------------+-----------------+
| UPDATE |
+------------------+-----------------+
| 2 | WAITING |
+------------------+-----------------+
| 1 | WAITING |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
While no job requests are being made each processor will keep updating the network state. After a given amount of time the processor at the head of the queue is expected to transmit an update. The processor at the head of the queue is the processor with the oldest last know transmission. In the example the next expected transmission will be:
+------------------+-----------------+
| UPDATE |
+------------------+-----------------+
| 1 | WAITING |
+------------------+-----------------+
| 2 | WAITING |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
+------------------+-----------------+
| -1 | ADDRESS_FREE |
More processors can continue to join the network and update their status in a similar way. In this way the LKT vector might end up as follows:
+------------------+-----------------+
| UPDATE |
+------------------+-----------------+
| 3 | WAITING |
+------------------+-----------------+
| 2 | WAITING |
+------------------+-----------------+
| 4 | WAITING |
+------------------+-----------------+
| 5 | WAITING |
+------------------+-----------------+
| 1 | WAITING |
Processor 3 now broadcasts a job request:
+------------------+-----------------+
| JOB REQUEST |
+------------------+-----------------+
| 4 | WAITING |
+------------------+-----------------+
| 3 | WAITING |
+------------------+-----------------+
| 1 | BUSY |
+------------------+-----------------+
| 6 | WAITING |
+------------------+-----------------+
| 2 | WAITING |
The oldest queued processor responds immediately:
+------------------+-----------------+
| ACCEPT JOB |
+------------------+-----------------+
| 5 | WAITING |
+------------------+-----------------+
| 4 | WAITING |
+------------------+-----------------+
| 2 | BUSY |
+------------------+-----------------+
| 1 | BUSY |
+------------------+-----------------+
| 3 | WAITING |
© 2009 Novell, Inc. All Rights Reserved.
