2.12 Database Example: Queuing Disciplines

Suppose that the database server is serving both queries and update transactions and that the response time SLA of queries is more important than that of update transactions. In this case, queries should be given preferential treatment, such as a higher priority at the CPU, so that they execute faster than updates. Many different queuing disciplines can be considered in a QN:

  • First Come First Served (FCFS). Customers are served in the order of arrival at a queue, as in a supermarket cash register.

  • Priority Queuing. When the server becomes available, the customer that has the highest priority is served next. If there is more than one customer with the same priority, FCFS is used to break the tie within each priority class. There are many possible variations of priority-based queuing disciplines: static priorities vs. dynamic priorities, preemptive vs. non-preemptive, preemptive resume vs. preemptive restart. In the static priority case, the priority of a customer does not change with time. With preemptive priority, arriving customers of higher priority are allowed to immediately seize a resource that is being used by a customer of lower priority. Preempted customers may continue from where they left off (the preemptive resume case) or they may have to to restart (preemptive restart). Chapter 11 present results for single queues with priorities and Chap. 15 discusses approximation results for QNs with queues that use priority-based queuing disciplines.

  • Round Robin (RR). In this case, each transaction is served for a short period of time, called a quantum or timeslice, after which the resource is switched to the next transaction in a circular fashion. Thus, if there are n transactions in a queue, the resource allocates a timeslice to transactions in the following order: 1, 2, ···, n, 1, 2, ···. This type of scheduling discipline is commonly used by operating systems to schedule the CPU to the set of ready processes.

  • Processor Sharing (PS). This is the theoretical limit of RR as the timeslice approaches zero. Another way of thinking about PS when there are n transactions in a queue is that all n of them are served simultaneously, but each one sees a resources n times slower. It is typical to assume for modeling purposes that the context switch time for all queuing disciples is negligible.

Many other queuing disciples are possible and have been analyzed, including shortest job first, multi-level feedback, Last Come First Serve-Preemptive Resume (LCFS-PR), and random.

Performance by Design. Computer Capacity Planning by Example
Performance by Design: Computer Capacity Planning By Example
ISBN: 0130906735
EAN: 2147483647
Year: 2003
Pages: 166

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net