RESERVATION BASED SCHEMES
Polling
Polling is the process where the computer or controlling device waits for an external device to check for its readiness or state, often with low-level hardware. For example, when a printer is connected via a parallel port, the computer waits until the printer has received the next character. These processes can be as minute as only reading one bit.
Polling is sometimes used synonymously with busy-wait polling. In this situation, when an I/O operation is required, the computer does nothing other than check the status of the I/O device until it is ready, at which point the device is accessed. In other words, the computer waits until the device is ready. Polling also refers to the situation where a device is repeatedly checked for readiness, and if it is not, the computer returns to a different task. Although not as wasteful of CPU cycles as busy waiting, this is generally not as efficient as the alternative to polling, interrupt-driven I/O.
In a simple single-purpose system, even busy-wait is perfectly appropriate if no action is possible until the I/O access, but more often than not this was traditionally a consequence of simple hardware or non-multitasking operating systems. Polling is often intimately involved with very low-level hardware. For example, polling a parallel printer port to check whether it is ready for another character involves examining as little as one bit of a byte.
That bit represents, at the time of reading, whether a single wire in the printer cable is at low or high voltage. The I/O instruction that reads this byte directly transfers the voltage state of eight real world wires to the eight circuits (flip flops) that make up one byte of a CPU register. Polling has the disadvantage that if there are too many devices to check, the time required to poll them can exceed the time available to service the I/O device. ≠
Algorithm
Polling can be described in following steps:
1. The host repeatedly reads the busy bit of the controller until it becomes clear.
2. When clear, the host writes in the command register and writes a byte into the data-out register.
3. The host sets the command-ready bit (set to 1).
4. When the controller senses command-ready bit is set, it sets busy bit.
5. The controller reads the command register and since write bit is set, it performs necessary I/O operations on the device. If the read bit is set to one instead of write bit, data from device is loaded into data-in register, which is further read by the host.
6. The controller clears the command-ready bit once everything is over, it clears error bit to show successful operation and reset busy bit (0).
Types
A polling cycle is the time in which each element is monitored once. The optimal polling cycle will vary according to several factors, including the desired speed of response and the overhead (e.g., processor time and bandwidth) of the polling.
In roll call polling, the polling device or process queries each element on a list in a fixed sequence. Because it waits for a response from each element, a timing mechanism is necessary to prevent lock-ups caused by non-responding elements. Roll call polling can be inefficient if the overhead for the polling messages is high, there are numerous elements to be polled in each polling cycle and only a few elements are active.
In hub polling, also referred to as token polling, each element polls the next element in some fixed sequence. This continues until the first element is reached, at which time the polling cycle starts all over again.
Polling can be employed in various computing contexts in order to control the execution or transmission sequence of the elements involved. For example, in multitasking operating systems, polling can be used to allocate processor time and other resources to the various competing processes. In networks, polling is used to determine which nodes want to access the network. It is also used by routing protocols to retrieve routing information, as is the case with EGP (exterior gateway protocol).
An alternative to polling is the use of interrupts, which are signals generated by devices or processes to indicate that they need attention, want to communicate, etc. Although polling can be very simple, in many situations (e.g., multitasking operating systems) it is more efficient to use interrupts because it can reduce processor usage and/or bandwidth consumption.
Token Bus
Token Bus is described in the IEEE 802.4 specification, and is a Local Area Network (LAN) in which the stations on the bus or tree form a logical ring. Each station is assigned a place in an ordered sequence, with the last station in the sequence being followed by the first, as shown below. Each station knows the address of the station to its "left" and "right" in the sequence.
This type of network, like a Token Ring network, employs a small data frame only a few bytes in size, known as a token, to grant individual stations exclusive access to the network transmission medium. Token-passing networks are deterministic in the way that they control access to the network, with each node playing an active role in the process. When a station acquires control of the token, it is allowed to transmit one or more data frames, depending on the time limit imposed by the network.
When the station has finished using the token to transmit data, or the time limit has expired, it relinquishes control of the token, which is then available to the next station in the logical sequence. When the ring is initialised, the station with the highest number in the sequence has control of the token. The physical topology of the network is either a bus or a tree, although the order in which stations are connected to the network is not important.
The network topology means that we are essentially dealing with a broadcast network, and every frame transmitted is received by all attached stations. With the exception of broadcast frames, however, frames will only be read by the station to which they are addressed, and ignored by all other stations. As the token frame is transmitted, it carries the destination address of the next station in the logical sequence. As each individual station is powered on, it is allocated a place in the ring sequence (note that in the diagram above, station two is not participating in the ring). The Token Bus medium access control protocol allows stations to join the ring or leave the ring on an ad-hoc basis. Token Bus networks were conceived to meet the needs of automated industrial manufacturing systems and owe much to a proposal by General Motors for a networking system to be used in their own manufacturing plants -Manufacturing Automation Protocol (MAP).
Ethernet was not considered suitable for factory automation systems because of the contention-based nature of its medium access control protocol, which meant that the length of time a station might have to wait to send a frame was unpredictable. Ethernet also lacked a priority system, so there was no way to ensure that more important data would not be held up by less urgent traffic.
A token-passing system in which each station takes turns to transmit a frame was considered a better option, because if there are n stations, and each station takes T seconds to send a frame, no station has to wait longer than T seconds to acquire the token. The ring topology of existing token-passing systems, however, was not such an attractive idea, since a break in the ring would cause a general network failure.
A ring topology was also considered to be incompatible with the linear topology of assembly-line or process control systems. Token Bus was a hybrid system that provided the robustness and linearity of a bus or tree topology, whilst retaining the known worst-case performance of a token-passing medium access control method. The transmission medium most often used for broadband Token Bus networks is 75 Ohm coaxial cable (the same type of cable used for cable TV), although alternative cabling configurations are available. Both single and dual cable systems may be used, with or without head-ends.