1:Compare the array and linked list implementations of queues. What are the adva

Question

1:Compare the array and linked list implementations of queues. What are the advantages and disadvantages of each implementation? Consider memory space, the complexity of the implementation, and the time efficiencies of the implementations.

2: Consider a scenario in which the requests for service arrive periodically at a fixed rate (in other words, constant arrival rate). Is a queue necessary in such a scenario? Why or why not?

3: Let us say your company has a collection of identical Web servers to handle incoming Web transactions. How would you distribute the incoming processing requests?

4: Do a Web search and explain what happens to a queuing system in a Web server when it is hit by “denial of service” attack.

5: Let us make the queuing the system more flexible: Servers are dynamically added and deleted depending on the queue length. When the queue length exceeds a particular limit, a new server is added. When the queue length goes below another lower limit, a server is deleted. Discuss the impact on waiting time when the arrival rate, the threshold for adding a server and the threshold for deleting a server are changed.

Explanation / Answer

1.

Array implementation of queues:

A queue can be implemented as singly linked list with a head and tail pointer. Enqueue into the linked list by appending at the back of singly linked list which take worst case time of O (1). Implement the dequeue operation by removing first element which takes worst case time O (1).

Linked list implementation of queues:

A queue can be implemented using an array as a circular buffer backed by an array. When queue is implemented by using a linked list, then enqueue into buffer such that insertion is done at next free position in circular buffer. This takes best case time of O(1) and worst case time of O(n) and amortized time of O(1).

Advantage of array implementation:

Disadvantage of array implementation:

Advantage of linked list implementation:

Disadvantage of linked list implementation:

2.

A scenario in which the requests for service arrive periodically at a fixed rate is that of a customer service center in which a lot of inbound calls are being entertained. In this situation, a queue will be required to serve the requests of the customers. The requests will arrive in a queue and will reach to the customer who will call first.

3.

If a company has a collection of identical Web servers to handle incoming web transactions. The incoming processing requests can be distributed with the help of multiple servers that form a server farm. The servers in the farm have different characteristics and this collection of web servers will help to distribute the incoming processing requests to different servers.

4.

Denial of service (DoS) attack is an attack that can disrupt the entire network by flooding it with useless requests and traffic. It can block the queueing system, because the queue will be over burdened by the useless requests.

5.

When the arrival rate, the threshold for adding a server and the threshold for deleting a server are changed, the waiting time will change accordingly. When the queue length exceeds a limit, a new server is added, which means that the threshold for adding a server is changed. In this case the waiting time will decrease because more and more servers will be added to the queue to serve the requests.

In the same way, when the queue length goes below another lower limit, a server is deleted, which means that the threshold for deleting a server is changed. In this case, the waiting time will increase because the requests will block the queue and more and more requests will remain un acknowledged.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.