When is a situation called as congestion?

- Network congestion is quite a common problem in the queuing theory and data networking. 

- Sometimes, the data carried by a node or a link is so much that its QoS (quality of service) starts deteriorating. 

- This situation or problem is known as the network congestion or simply congestion. 

This problem has the following two typical effects:

Ø  Queuing delay

Ø  Packet loss and

Ø  Blocking of the new connections

- The last two effects lead to two other problems. 

- As the offered load increases by the increments, either the throughput of the network is actually reduced or the throughput increases by very small amounts. 

- Aggressive re-transmissions are used by the network protocols for compensating for the packet loss. 

- The network protocols thus tend to maintain a state of network congestion for the system even if the actual initial load is too less that it cannot cause the problem of network congestion. 

- Thus, two stable states are exhibited by the networks that use these protocols under similar load levels. 

- The stable state in which the throughput is low is called the congestive collapse. 

- Congestive collapse is also called congestion collapse.

- In this condition, the switched computer network that can be reached by a packet when because of congestion there is no or little communication happening.

- In such a situation even if a little communication happens it is of no use. 

- There are certain points in the network called the choke points where the congestion usually occurs.

- At these points, the outgoing bandwidth is lesser than the incoming traffic. 

- Choke points are usually the points which connect the wide area network and a local area network. 

- When a network falls in such a condition, it is said to be in a stable state. 

- In this state, the demand for the traffic is high but the useful throughput is quite less.

- Also, the levels of packet delay are quite high. 

- The quality of service gets extremely bad and the routers cause the packet loss since their output queues are full and they discard the packets. 

- The problem of the network congestion was identified in the year of 1984. 

- The problem first came in to the scenario when the backbone of the NSF net phase dropped 3 times of its actual capacity. 

- This problem continued to occur until the Van Jacobson’s congestion control method was implemented at the end nodes.

Let us now see what is the cause of this problem? 

- When the number of packets being set to a router exceeds its packet handling capacity, many packets are discarded by the routers that are intermediate. 

- These routers expect the re-transmission of the discarded information. 

- Earlier, the re-transmission behavior of the TCP implementations was very bad. 

- Whenever a packet was lost, the extra packets were sent in by the end points, thus repeating the lost information. 

- But this doubled the data rate. 

- This is just the opposite of what routine should be carried out during the congestion problem. 

- The entire network is thus pushed in a state of the congestive collapse resulting in a huge loss of packets and reducing the throughput of the network. 

- Congestion control as well as congestion avoidance techniques are used by the networks of modern era for avoiding the congestive collapse problem. 

- Various congestion control algorithms are available that can be implemented for avoiding the problem of network congestion. 

- There are various criteria based up on which these congestion control algorithms are classified such as amount of feedback, deploy-ability and so on. 

What is Polling?

- Polling is often referred to as the polled operation.

- When the statuses of the external devices are actively sampled by a client program just like a synchronous activity is referred to as the polling. 

- The common use of the polling is in the input and output operations. 

- In rare cases, polling is also called as the software driven I/O or just simply as polled I/O. 

- As and when required, polling is also carried out with the busy waiting synonymous. 

- Polling is then referred to as the busy–wait polling. 

- In this case whenever it is required to carry out an input/ output operation, the system just checks the status of the device required for fulfilling this operation until it is idle. 

- When it becomes idle it is accessed by the I/O operation. 

- Such polling may also refer to a state in which the status of the device is checked again and again for accessing it if idle. 

- If the device is occupied, the system is forced to return to some other pending task. 

- In this case the CPU time is wasted less when compared to what happens in busy waiting. 

- However, this is not a better alternative to interrupt driven I/O polling. 

- In single purpose systems that are too simple, using busy-wait polling is perfectly fine if the system cannot take any action until the I/O device has been accessed. 

- But traditionally, the polling was thought to be a consequence of the operating systems and simple hardware that do not support multitasking. 

- The polling works intimately with the low level hardware usually. 

- For example, a parallel printer port can be polled for checking whether or not it is ready for printing another character. 

- This involves just the examination of a bit. 

- The bit to be examined represents the high or low voltage stage of the single wire in the cable of the printer during the time of reading. 

- The I/O instruction by which this byte is read is also responsible for transferring the voltage state directly to the eight flip flops or circuits. 

- These 8 flip flops together constitute one byte of a register of CPU. 

Polling also has a number of disadvantages. 

- One is that there is limited time for servicing the I/O devices. 

- Polling has to be done within this time period only. 

- But in some cases there are many devices to be checked which cause the polling time to exceed the given limit. 

- The host keeps on hitting the busy bit until the device becomes idle or clear. 

- When the device is idle, the state is written in to the command register and also in the data out register. 

- The command ready bit is set to 1. 

- The controller sets the busy bit once it knows that the command ready bit has been set.  

- After reading from the command register, the controller carries out the required I/O operation on the device. 

- On the other hand, if the read bit has been set to one, the controller loads the device data in to the data in register. 

- This data is further read by the host. 

- Once the whole action has been completed, the command ready bit is cleared by the controller. 

- The error bit is also cleared for showing that the operation has been completed successfully. 

- At the end the busy bit is also set.

- Polling can be seen in the terms of master slave scenario where the master sends inquiring about the working status slave devices i.e., whether they are clear or engaged. 

What is the difference between a passive star and an active repeater in fiber optic network?

There are two important components of a fiber optic network namely passive star coupler and active repeaters. 

Passive Star in Fiber Optic Network

- Passive star couplers are single mode fiber optic couplers with reflective properties.  

- These couplers are used for optical local area networking at very high speeds. 

- These couplers are made from very simple components such as mirrors and 3 db couplers. 

- Besides this, these star couplers save a lot of optical fiber when compared to its trans-missive counterpart. 

- They are free of any multi-paths so as to avoid any interference. 

- A fiber optic network may consist of any number of passive star couplers and each of them is capable of connecting a number of users. 

- The input and output from every passive star coupler is given to the output and input of an active coupler. 

- The round trip transmission tile is stored by the active star coupler. 

- When it receives a signal from a passive star coupler, it stops the output to that coupler for the duration of the signal.

- It also inhibits the incoming data from all the other passive star couplers for the round trip transmission delay plus signal duration. 

- The purpose of a star coupler is to take one input signal and then splitting it in to a number of output signals. 

- In telecommunications industry and fiber optics communication, this coupler is used in network applications being a passive optical device. 

- If an input signal is introduced to one of the input ports, it is distributed to all of the output ports of the coupler. 

- As per the construction of the passive star coupler, the number of ports it will have is given by the power of 2. 

- For example, in a two port coupler or in a directional coupler or splitter, there are 2 input ports and 2 output ports.

- In a four port coupler, there are 4 i/p ports and 4 o/p ports and so on. 

- The digital equipment corporation also sold a device by the name of star coupler which was used for interconnecting the links and computers through coaxial cable instead of using optical fibers. 

Active Repeater in Fiber Optic Network 

- Active repeater is an important telecommunications device used for re transmitting the signal it receives to a higher level and with higher basically to the other side of an obstacle so that long distances can be covered. 

- Repeater is an electro-mechanical device that helps in regenerating the telegraphy signals. 

- It may be defined as an analog device for amplifying the input signal, reshaping it, re-timing it for re-transmission. 

- A re-generator is a repeater that can perform the re-timing operation. 

- Repeaters just tend to amplify the physical signal without interpreting the data transmitted by the signal. 

- The 1^st layer i.e., the physical layer is where the repeaters operate. 

- Repeaters are employed for boosting the signals in optical fiber lines as well as in twisted pair and coaxial cables. 

- When a signal travels through a channel, it gets attenuated with the distance and time because of the energy loss (dielectric losses, conductor resistance etc.). 

- When light travels in optical fibers, it scattered and absorbed and hence is attenuated. 

- Therefore, in long fiber lines, repeaters are installed at proper intervals for regenerating and strengthening the signal. 

Repeater in optical communication performs the following functions:

Ø  Takes the input signal

Ø  Converts it in to electrical signal

Ø  Regenerates it.

Ø  Converts it in to optical signal

Ø  Re-transmits it

- These repeaters are usually employed in submarine as well as transcontinental communication cables as the loss is unacceptable in these cases.  

Explain the various File Operations

A number of operations can be carried out on a file. However, there are 6 basic file operations. As we know a file is an ADT or abstract data type. Certain operations need to be considered for defining a file. Operating systems makes calls to these operations. 

Following are the six basic operations:

1. Creation of a file: 

- This operation involves two steps. 

- Firstly, a sufficient space has to be found for storing the file in the file system. - Secondly, for this new file an entry should be made in the directory.

2. Writing to a file: 

- For writing data to a file, a system call has to be made with name and the data to be written as its arguments. 

- A writer pointer is kept by the system at the location in the file where the next write operation is to be carried out. 

- This pointer is updated whenever a write operation occurs.

3. Reading from a file: 

- Just like the write operation, in order to read information from a file, a system call has to be generated along with the name of the file and the location of the content to be read as its arguments. 

- Here, instead of a write pointer there is a read pointer that will indicate the location where the next read operation is to take place. 

- The location at which the current operation is being carried out is kept as a “per – process current – file – position” pointer since the process is either writing to or reading from the file. 

- The same pointer can be used by both the read and write operations in order to reduce the complexity of the system as well as for saving space.

4. Re-positioning within a file: 

- System carries out search in the directory looking for the appropriate entry. 

- When found, the current file position pointer is re-pointed to this position. 

- This file operation does not require carrying out any input or output operation in actual. 

- Another name for this file operation is the file seek.

5. Deletion of a file: 

- For deletion of the file, the system searches through the directory to find the appropriate entry. 

- When found, the space held by this file is released and the entry in the directory is destroyed so that this space can be reused by other files.  

6. Truncating a file: 

- Sometimes you may require deleting only the contents of a file while keeping it attributes. 

- Deleting the file and recreating it is not an efficient solution. 

- This file operation lets you to erase the contents of the file but save its attributes.

- But here the length attribute of the file will be changed to zero after truncation. 

- The file space is released after truncating.

The above mentioned six basic file operations constitute the minimal file operations set. These operations are primary ones and if combined can perform some other secondary file operations such as copying. A table known as the open file table is maintained by the operating system that stores all the information about the files that are currently open. When the file is closed, its entry is deleted from the open file table. Some files have to be opened explicitly with the function open() before using it. The name of the file is passed as an argument to this function. Then it looks in the directory for this file and an entry is made in the open file table.  Each file has some access rights. It is in these access modes that a process uses the file. A process can perform only those operations which are permitted by the access rights of the file. 

What is CPU Scheduling Criteria?

Scheduling is an essential concept that serves in the multitasking, multiprocessor and distributed systems. There are several schedulers available for this purpose. But these schedulers also require a criterion up on which they can decide how to schedule the processes. In this article we discuss about these scheduling criteria. Today a number of scheduling algorithms are available and all these have different properties. This is why these may work up on different scheduling criteria. Also the chosen algorithm may favor one class of processes more than the other.

What Criteria is used by algorithms for Scheduling?

Below mentioned are some of the criteria used by these algorithms for scheduling:
1. CPU utilization:
- It is a property of a good system to keep the CPU as busy as possible all the time.
- Thus, this utilization ranges from 0 percent to 100 percent.
- However, in the systems that are loaded lightly, the range is around 40 percent and for the systems heavily loaded it ranges around 90 percent.

2. Throughput:
- The work is said to be done if the CPU is busy with the execution of the processes.
- Throughput is one measure of CPU performance and can be defined as the number of processes being executed completely in a certain unit of time.
- For example, in short transactions throughput might range around like 10 processes per second.
- In longer transactions this may range around only one process being executed in one hour.

3. Turnaround time:
- This is an important criterion from the point of view of a process.
- This tells how much time the processor has taken for execution of  a processor.
- The turnaround time can be defined as the time duration elapsed from the submission of the process till its completion.

4. Waiting time:
- The amount of time taken for the process for its completion is not affected by the CPU scheduling algorithms.
- Rather, these algorithms only affects the time when the process is in waiting state.
- The time for which the process waits is called the waiting time.

5. Response time:
- The turnaround is not a good criterion in all the situations.
- The response time is favorable in the case of the interactive systems.
- It happens many a times that a process is able to produce the output in a fairly short time compared to the expected time.
- This process then can continue with the next instructions.
- The time taken for a process from its submission till production of the first response is calculated as the response time and is another criterion for the CPU scheduling algorithms.

All these are the primary performance criteria out of which one or more can be selected by a typical CPU scheduler. These criteria might be ranked by the scheduler depending up on their importance. One common problem in the selection of performance criteria is the possibility of conflict ion between them.
For example, increasing the number of active processes will increase the CPU utilization but at the same time will decrease the response time. This is often desirable to produce reduction in waiting time and turnaround time also. In a number of cases the average measure is optimized. But there are certain cases also where it is more beneficial to optimize the maximum or the minimum values.
It is not necessary that a scheduling algorithm that maximizes the throughput will decrease the turnaround time. Out of a mix of short and long jobs, if a scheduler runs only the short jobs, it will produce the best throughput. But at the same time the turnaround time for the long jobs will be so high which is not desirable.

Explain the various Disk Allocation methods? – Part 2

In this article we discuss about the non-contiguous disk allocation methods i.e., the linked allocation and the indexed allocation. 

What is a Linked Allocation?

- In linked allocation a single file might be stored all over the disk and these scattered parts are linked to each other just like a linked list. 

- Few bytes in the memory block are used for storing the address of the following linked block.

- This type of allocation has two major advantages mentioned below:

1. Simplicity and
2. Non – requirement of disk compaction

- Since the nature of the allocation method is non-contiguous, it does not lead to any external fragmentation of the disk space.

- And since all the memory blocks have been linked to each other, a memory block available anywhere in the memory can be used for satisfying the requests made by the processes. 

- Declaring the file size for the linked allocation is not required during its creation. 

- There are no issues even if the file continues to grow as long as free blocks are available and since the blocks can always be linked up. 

- As a consequence of all this, the need for disk compaction is eliminated. 

Disadvantages of Linked Allocation

But there are disadvantages of using linked allocation. They are:

Direct access to the disk blocks becomes slow: 

For finding a particular block of the file, the search has to begin at the starting point of the file and the successive pointers have to be followed till the destination block is reached.

Space required by the pointers: 

- Suppose out of 512 words of a memory block, 2 are required for storing the pointers, then we have 39 percent of the total disk being used by the pointers rather than for data. 

- This adds to the space requirement of the file blocks.

Reliability: 

- Because of all the blocks being linked via the pointers, even if one pointer gets damaged or wrong, the successive blocks can become inaccessible. 

- This problem is quite common and thus most of the operating systems avoid this problem by keeping redundant copies of these pointers in a special file. 

- The basic idea here is to keep the list of the pointers in the physical memory of the system. 

- This also allows for the faster access to the disk blocks.

What is Indexed allocation?

- The linked allocation method does not provide support for the direct access and this problem is solved by the indexed allocation method. 

- In this method, all the pointers are placed over an index. 

- Thus, these pointers together form the index block. 

- The address of this address block is then stored in the directory. 

- The pointer at the nth number in the index block points to the nth block of the associated file. 

- The purpose of the index blocks is somewhat similar to that of the page map tables; however both of these are implemented in a different way.
- First level index is used for searching the index of second level and the second one is used for searching the third one and the process may continue till the fourth level. 

- But in most of the cases the indexes of the first two levels are sufficient. 

- With this method, second level index blocks (128 x 128) can be easily addressed and files of size of up to 8mb can be supported. 

- Assuming the same thing, files of size up to 1 gb can be addressed.

Advantages and Disadvantage of Indexed Allocation

- The major advantage of this allocation technique is that it does not give rise to external fragmentation and offers a high level of efficiency in random accessing. 

- Also, using this technique mapping can be done around the disk blocks that are known to be bad. 

-Bit mapping can be used for indexing the free space. 

The biggest disadvantage of this allocation technique is the large number disk accesses required for the retrieval of the address of the destination block in the memory. 

Explain the various Disk Allocation methods? – Part 1

Management of space of the secondary data storage devices is one of the most necessary functions of the file system. This includes tracking which blocks of memory or disk are being allocated to the files and which blocks are free to be allocated. 

There are two main problems faced by the system during allocation of the space to different files. Firstly, the access to the files has to be fast and secondly, the disk space has to be effectively utilized. Both of these combine to form the big problem of disk management. These two problems are more common with the physical memory of the system. 

However, the secondary storage of the system also introduces 2 additional problems which are long disk access time and blocks of larger size to deal with. In spite of all these problems, there are considerations that are common for both the storage such as the non – contiguous and contiguous space allocation. 

Types of Disk Allocation Methods

The following are the 3 widely used allocation techniques:

Ø  Contiguous

Ø  Linked

Ø  Indexed

- The linked and the indexed allocation techniques fall under the category of the non-contiguous space allocation. 

- All the methods have their own pros and cons.

- It is in the term of blocks that all the input and output operations are carried out on the disk. 

- Software is responsible for converting from the logical record to physical storage blocks.

Contiguous Allocation: 

- This allocation technique assigns only the contiguous memory blocks to the files. 

- The size of the memory required is mentioned by the user in advance for the holding the file. 

- The file is then created only if that much amount of memory is available otherwise not. 

- It is the advantage of the contiguous memory allocation technique that all the successive file records are saved adjacent to each other physically. 

- This causes an increase on the disk access time of the files. 

- This can be concluded from the fact that if the files are scattered all about the disk, then it takes a lot more time to access them. 

- Accessing files when they have been organized in a proper order is quite easy.

- To access the files sequentially, the system uses the address of the last memory block and if required moves to the next one. 

- Both direct and sequential accesses are supported by the contiguous memory allocation technique. 

- The problem with this allocation method is that every time a new contiguous space cannot be found for the new files if a majority of the memory is already in use and if the file size is larger than the available memory.  

Non–Contiguous Memory Allocation: 

- It happens a lot of time that the files grow or shrink in size with usage and time. 

- Therefore, it becomes difficult to determine the exact space required for the files since the users do not have any advance knowledge about the growing size of their files. 

- This is why the systems using the contiguous memory allocation techniques are being replaced by the ones with the non-contiguous storage allocation which is more practical and dynamic in nature. 

- The linked allocation technique mentioned above in the article, is a disk – based implementation of the linked list. 

- Each file is considered to be a list of the disk blocks linked to each other. 

- It does not matter whether the blocks are scattered about the disk. 

- In each block, few bytes are reserved for storing the address of the next block in chain.

- The pointer to the first and the last block of the file is stored in the directory. 

What are the various Desk Scheduling methods?

About Disk Scheduling

The I/O system has got the following layers:

1. User processes: The functions of this layer including making I/O calls, formatting the I/O and spooling.
2. Device independent software: Functions are naming, blocking, protection, allocating and buffering.
3. Device drivers: Functions include setting up the device registers and checking their status.
4. Interrupt handlers: These perform the function of waking up the I/O drivers up on the completion of the I/O.
5. Hardware: Performing the I/O operations.

- Disk drives can be pictured as large 1 – D array consisting of logical blocks that are smallest unit of transfer.  

- These blocks are mapped in to the disk sectors in a sequential manner. 

- Mapping is done in the same manner. 

- The responsibility of using the hardware efficiently is the duty of the operating system for the disk drives for increasing the speed of access and bandwidth of the disk. 

Algorithms for Scheduling Disk Requests

There are several algorithms existing for the scheduling of the disk requests:

Ø  SSTF: 

- In this method the request having the minimum seek time is selected from the present head position. 

- This method is a modification of the SJF (shortest job first) scheduling and therefore contains some possibility of process starvation.

Ø  SCAN: 

- From one end of the disk, the disk arm starts and continues in the direction of the other end, serving to the requests till the opposite end. 

- At this end the head is reversed and the process continues. 

- This is sometimes called as the elevator algorithm.

Ø  C – SCAN: 

- A better algorithm then the previous one. 

- This one offers a more uniform waiting time than the previous one. 

- The movement of the head is from one end to another while it services the requests encountered along the way. 

- However, the difference is that when it comes to the other it straightaway goes to the beginning without heeding to any of the requests in the way and then again starts. 

- The cylinders are treated as the circular list wrapped around last and the first cylinder.

Ø  C – Look: 

- This is a modified version of the C – SCAN. 

- Here the arm or the head travels only up to the last request rather than going till the far end. 

- Then immediately the direction is reversed and the process continues.

- For disk scheduling it is important that the method be selected as per the requirements only. 

- The first one is the most commonly used and appeals to the needs naturally. 

- For a system where often there is a heavy load on the disk, the SCAN and C- SCAN methods can help. 

- The number as well as the kind of requests affects the performance in a number of ways.

- On the other hand, the file – allocation method influences the requests for the disk services. 

- These algorithms have to be written as an individual module of the OS so that if required it can be replaced with a different one easily. 

- As a default algorithm, the LOOK or the SSTF is the most reasonable choice. 

Ways to attach to a disk

There are two ways of attaching the disk:

Ø  Network attached: This attachment is made via a network. This is called the network attached storage. All such connected storage devices together form the storage area network.

Ø  Host attached: This attachment is made via the I/O port.

All these disk scheduling methods are for the optimization of the secondary storage access and for making the whole system efficient. 

Explain the various File Access methods?

One of the most important functions of the mainframe operating system is the access methods that make it possible for you to access the data from external devices such as the tape or disk. 

What are access methods?

- Access methods are very useful in providing an API for transferring the data from one device to another.

- Another best thing about this API was that it worked as the device driver for the operating systems on non-mainframe computers. 

- There have been a lot of reasons behind the introduction of the access methods. 

- A special program had to be written for the I/O channel and there has to be a processor entirely dedicated to controlling the access to the peripheral storage device as well as data transfer from and to the physical memory. 

- Special instructions constitute these channel programs and are known as the CCWs or the channel command words.

- To write such programs, very detailed knowledge is required regarding the characteristics of the hardware. 

Benefits of File Access Methods

There are 3 major benefits of the file access methods:

Ø  Ease of programming: The programmer does not have to deal with the procedures of the specific devices, recovery tactics and error detection. A program designed to process a particular thing will do it no matter where the data has been stored.

Ø  Ease of hardware replacement: A program cannot be altered by the programmer during the migration of data from older to newer model of the storage device provided the same access methods are supported by the new model.

Ø  Ease in sharing the data set access: The access methods can be trusted for managing the multiple accesses to the same file. At the same it ensures the security of the system and data integrity.

Some File/Storage Access Methods

Ø  Basic direct access method (BDAM)

Ø  Basic sequential access method (BSAM)

Ø  Queued sequential access method (QSAM)

Ø  Basic partitioned access method (BPAM)

Ø  Indexed sequential access method (ISAM)

Ø  Virtual storage access method (VSAM)

Ø  OAM (object access method)

- For dealing with the records of a data set both the types of access i.e., the queued and the basic are suitable. 

- The queued access methods are an improvement of the basic file access methods. 

- Read ahead scheme and internal blocking of data is well supported by these methods. 

- This allowed combining the multiple records in to one unit, thus increasing the performance. 

- In sequential methods, it is assumed that there’s only a sequential way for processing the records which is just the opposite of the direct access methods. 

- There are devices like the magnetic tape that only enforce the sequential access 

- Sequential access can be used for writing a data set and then later the direct manner can be used for processing it.

Today we have access methods that are network-oriented such as the following:

Ø  Basic telecommunications access method or BTAM

Ø  Queued tele – processing access method or QTAM

Ø  Telecommunications access method or TCAM

Ø  Virtual telecommunications access method or VTAM

- The term access method was used by the IMS or the IBM information management system for referring to the methods for manipulation of the database records. 

- The access methods used by them are:

Ø  GSAM or generalized sequential access method

Ø  HDAM or hierarchical direct access method

Ø  HIDAM or hierarchical indexed direct access method

Ø  HISAM or hierarchical indexed sequential access method

Ø  HSAM or hierarchical sequential access method

Ø  PHDAM or partitioned hierarchical direct access method

Ø  PHIDAM or partitioned hierarchical indexed direct access