Unit- IV

Syllabus : Policies and mechanisms for Resource Management, Applications of control

Theory to Task Scheduling on a cloud, Stability of a Two level Resource allocation
Architecture, Feedback Control Based on Dynamic Thresholds. Coordination of specialized
Autonomic Performance Managers, Resource Bundling, Scheduling Algorithms for computing
clouds- Fair Queuing, Start Time Fair Queiuing.
Resource Management : In cloud computing, resource management refers
to the process of managing the usage of resources in a cloud environment. This
includes compute resources (like CPU and memory), storage resources (like disk
space), and network resources (like bandwidth).
• Resource management is crucial for optimizing the performance and cost
of a cloud environment.
• It involves monitoring resource usage, allocating resources, and managing
resource capacity.
Resource management works by monitoring the usage of resources, allocating
resources to applications and services based on their needs, and managing the
capacity of resources to ensure they are used efficiently.
• It can involve automated tools and systems to help manage resources
effectively.
• It's a key part of ensuring high performance and cost-effectiveness in a
cloud environment.

Policies and mechanisms for resource management

Resource management is a critical function in computing systems, including operating systems,
cloud platforms, and data centers, where multiple users and processes share limited resources
such as CPU, memory, storage, network bandwidth, and energy. Its main goal is to ensure that
resources are used efficiently, fairly, and reliably, while preventing system overload,
starvation of processes, or performance degradation. Effective resource management relies on
two complementary aspects: policies and mechanisms. Policies define what should be done
— the rules or guidelines for allocation and sharing — while mechanisms define how it should
be done, i.e., the practical methods for implementing the policies.
A policy typically refers to the principal guiding decisions, whereas mechanisms represent the means
to implement policies. Separation of policies from mechanisms is a guiding principle in computer
science. Butler Lampson and Per Brinch Hansen offer solid arguments for this separation in the context
of operating system design.

Cloud resource management policies can be loosely grouped into five classes:
• Admission control.
• Capacity allocation.
• Load balancing.
• Energy optimization.
• Quality-of-service (QoS) guarantees.

Policies in resource management include different rules. Admission control policy checks
before admitting a new process or user into the system to ensure enough resources are
available, otherwise it rejects the entry to prevent overload. Capacity allocation policy
decides how available resources are divided among different processes, either equally or
based on priority. Load balancing policy ensures that work is evenly spread across resources
so that no single resource is overloaded while others are idle. Energy optimization policy
focuses on saving power by shutting down idle resources or using low-power modes. Quality
of Service (QoS) policy guarantees promised performance, speed, and reliability for important
applications like video calls or banking.

Mechanisms are the practical implementation techniques that enforce these policies.
Scheduling mechanisms decide the order in which processes access resources such as CPU or
I/O devices, using algorithms like First Come First Serve (FCFS), Round Robin, or Priority
Scheduling, to ensure fairness and efficiency. Capacity allocation mechanisms divide
resources like CPU cycles, memory, and network bandwidth according to the rules defined by
the capacity allocation policy, ensuring high-priority processes get adequate resources. Load
balancing mechanisms use algorithms to dynamically distribute workloads across servers,
processors, or network links, preventing overloading of any single resource and improving
overall throughput. Pooling mechanisms group similar resources into a shared pool to
maximize utilization and reduce overhead, such as connection pools in databases where
multiple applications can reuse the same connections. Monitoring and feedback mechanisms
continuously observe resource usage, detect performance issues, overload, or starvation, and
adjust allocations dynamically, ensuring efficiency, fairness, and compliance with QoS
requirements.

Applications of control Theory to Task Scheduling on a cloud

Control Theory : Cloud has multiple users and tasks running at the same time. Here the
resources are limited. SO, the problem is too many tasks can cause to overload , delay or waste
resources. So, to overcome this problem we have to use control theory to manage the resources
smartly.
Control theory is the study of monitoring a system and adjusting it to reach the desired state
or behaviour.

Example : when 100 students are login to a cloud system at the same time, The system has
finite resources are there. The system can handel 70 percent student smoothly without
overload this state is called desired state. But, it is reach to goal state(100%) By using control
theory the system continuously monitors CPU, RAM and network usage compares it with
desired state and adjusts task allocation or balances the load. This ensures that the system
gradually and safely moves towards the goal state, completing all tasks on time while keeping
resource stable and efficiently used.

Working of an Optimal Controller (Queueing System) :

This diagram shows the working of an optimal controller in a queueing system. Here k=
current time step/iteration . The process starts with external traffic λ(k), which goes directly
into the queueing dynamics (where packets or jobs are added into the queue) and also to the
predictive filter (which analyzes the traffic to forecast future arrivals and disturbances). The
predictive filter produces a forecast signal (s) that tells the controller what traffic load may
come ahead. Alongside this, the system has a reference signal (r) which represents the desired
target or performance requirement (like keeping delay low or processing at a certain rate). The
optimal controller takes three important inputs – the forecast signal (s), the reference signal
(r), and the current queue state q(k) which is fed back from the queue – and then calculates the
optimal control action u∗(k). This control signal is applied to the queueing dynamics together
with the incoming traffic λ(k), so that the system can process the traffic efficiently and generate
the output ω(k). At the same time, the current queue length or state q(k) is continuously sent
back to the controller as feedback, so that it can adjust its decisions. Disturbances (unexpected
changes in traffic) may occur, but the predictive filter and the feedback loop help the controller
to anticipate and minimize their impact. In short, every block in the diagram works together to
balance the incoming traffic, predict future loads, and control the queue in an optimal way to
keep the system stable and efficient.

Simply to say :

1. Inputs:
o External traffic λ(k): Incoming jobs or requests.
o Reference signal r: Desired performance (e.g., low delay, target processing
rate).
o Forecast signal s: Predicted future load from the predictive filter.
2. Process:
o The controller takes current queue state q(k), forecast signal s, and reference
r to calculate the optimal control action u∗(k).
 o The control action adjusts task allocation or resource usage in the queueing
system.
3. Feedback Loop:
o The current queue state q(k) is continuously fed back to the controller.
o This allows the system to adjust decisions dynamically and handle unexpected
disturbances efficiently.
4. Output:
o Efficient processing of tasks (ω(k))
o Balanced queue lengths
o Stable and efficient use of resources

Applications of Control Theory in Cloud Systems

Control theory is widely applied in cloud computing to adaptively manage resources and
ensure efficient task execution. Some important applications are:

1. Task Scheduling:

o Control theory dynamically allocates resources such as CPU, memory, and

storage to tasks.

o Ensures that tasks meet deadline or response-time requirements, preventing

system overload.

o For example, if one server is heavily loaded while others are underutilized, the
controller shifts tasks to maintain balance.

2. Quality of Service (QoS) Adaptation:

o QoS is measured in terms of response time, throughput, or delay.

o Control theory monitors these metrics and adjusts resource allocation to keep
performance within desired levels.

o For instance, if response time increases beyond the desired set point, the
controller can allocate more CPU or scale resources to reduce delay.

3. Power and Energy Management:

o Cloud servers consume significant energy. Control theory helps adjust

processor frequencies or shut down idle resources to reduce power
consumption.

o The system ensures that energy savings do not compromise QoS.

4. Load Balancing:

o Incoming requests are distributed among multiple servers based on feedback

from the system.
o Prevents some servers from being overloaded while others remain idle.

o Helps maintain efficient use of resources and avoids bottlenecks.

 5. Self-Managing (Autonomic) Systems:

o Control theory enables autonomic behavior: the system monitors itself, makes
decisions, and adjusts resources automatically.

o Can be applied in distributed web servers, database servers, high-

performance servers, and even mobile/embedded systems.

o Reduces the need for human intervention while keeping the system stable.

6. Performance-Energy Tradeoff Optimization:

o Often, improving performance requires more energy, while saving energy can
reduce performance.

o Control theory provides a mathematical framework to optimize this tradeoff,

ensuring that both QoS and energy efficiency are considered.

Key Insights :
1. Dynamic Adaptation:

o Control theory allows cloud systems to react in real-time to changing

workloads.

o Unlike static allocation, resources are adjusted continuously based on

feedback.

2. Optimal Resource Utilization:

o Ensures CPU, memory, and network bandwidth are used efficiently.

o Prevents waste of resources and avoids situations where some servers are idle
while others are overloaded.
3. System Stability:

o Feedback loops and predictive filters help the system anticipate disturbances
and prevent oscillations or crashes.

o Ensures that even during sudden spikes (like many users logging in
simultaneously), the system remains stable and reliable.

4. Improved QoS and User Experience:

o By monitoring metrics like queue length and response time, control theory
ensures tasks are completed on time, reducing delays for users.

o Users experience smooth performance even under high load.

5. Scalability and Autonomy:
o Makes it easier to scale cloud systems by automatically allocating resources as
needed.
 o Enables the system to operate without constant human supervision, making
large-scale cloud management practical.

Stability of a two-level resource allocation architecture

We can assimilate a server with a closed-loop control system and we can apply control theory principles to
resource allocation. In this section we discuss a two-level resource allocation architecture based on control
theory concepts for the entire cloud. The automatic resource management is based on two levels of
controllers, one for the service provider and one for the application, see Figure 6.2.

The main components of a control system are the inputs, the control system components, and the
outputs. The inputs in such models are the offered workload and the policies for admission control,
the capacity allocation, the load balancing, the energy optimization, and the QoS guarantees in the
cloud. The system components are sensors used to estimate relevant measures of performance and
controllers that implement various policies; the output is the resource allocations to the individual
applications.

The controllers use the feedback provided by sensors to stabilize the system; stability is related
to the change of the output. If the change is too large, the system may become unstable. In our
context the system could experience thrashing, the amount of useful time dedicated to the execution
of applications becomes increasingly small and most of the system resources are occupied by
management functions.
There are three main sources of instability in any control system:

• The delay in getting the system reaction after a control action.

• The granularity of the control, the fact that a small change enacted by the controllers
leads to very large changes of the output.

• Oscillations, which occur when the changes of the input are too large and the control is
too weak, such that the changes of the input propagate directly to the output.
Two types of policies are used in autonomic systems: (i) threshold-based policies and (ii) sequential
decision policies based on Markovian decision models. In the first case, upper and lower bounds on
performance trigger adaptation through resource reallocation. Such policies are simple and intuitive but
require setting per-application thresholds.

Lessons learned from the experiments with two levels of controllers and the two types of policies are
discussed in. A first observation is that the actions of the control system should be carried out in a
rhythm that does not lead to instability. Adjustments should be carried out only after the performance
of the system has stabilized. The controller should measure the time for an application to stabilize and
adapt to the manner in which the controlled system reacts.

If upper and lower thresholds are set, instability occurs when they are too close to one another if the
variations of the workload are large enough and the time required to adapt does not allow the
system to stabilize. The actions consist of allocation/deallocation of one or more virtual machines;
sometimes allocation/deallocation of a single VM required by one of the thresholds may cause crossing
of the other threshold and this may represent, another source of instability.

Feedback control based on dynamic thresholds

Introduction

In cloud computing and distributed systems, workload varies dynamically due to multiple
users and tasks running concurrently. Efficient resource management is critical to avoid
system overload, underutilization, or violation of Quality of Service (QoS). Traditional static
threshold-based controls, where resource limits are fixed, often fail to adapt to real-time
changes, leading to inefficiency or instability. Dynamic threshold-based feedback control
provides a solution by continuously adjusting thresholds according to system behavior and
workload, allowing the system to respond proactively and maintain optimal performance.

Concept of Dynamic Thresholds

• A threshold defines a boundary or limit for a system metric (e.g., CPU utilization,
memory usage, response time) beyond which corrective action is triggered.

• In dynamic thresholds, this limit is not fixed; it is updated periodically based on

feedback from the system metrics.

• This approach enables the system to adapt to fluctuating workloads and maintain
desired performance levels.
Example:

• Target CPU utilization: 70%

• Current CPU utilization: 80%

• Feedback mechanism adjusts the threshold downwards to prevent overload.

• Threshold update formula (Proportional control):

Where K is the gain factor controlling how fast the threshold adapts.

Feedback Control Loop with Dynamic Thresholds

The dynamic threshold system works in a closed-loop feedback manner:

1. Monitor Metrics: Continuously measure system parameters like CPU load, memory,
task queue length, or response time.

2. Compute Error: Compare the current value with the target (desired) value:

Update Threshold: Adjust the threshold using proportional, integral, derivative, or PID
control based on the error.

3. Trigger Action: If the system metric crosses the updated threshold, corrective actions
are taken (e.g., scaling resources, throttling tasks, load redistribution).

4. Repeat: The loop continuously monitors and adapts to maintain stability and optimal
performance.

PID-based dynamic threshold formula:

Advantages of Feedback Control with Dynamic Thresholds

• Adaptability: Automatically adjusts to changing workloads.

• Better Resource Utilization: Reduces idle resources and prevents overloading.

• Improved QoS: Minimizes response time violations and prevents system instability.

• Flexibility: Can be integrated with different control strategies for precise

management.

• Scalability: Useful in cloud environments where resources and tasks scale

dynamically.

Applications in Cloud Computing

• Task Scheduling: Dynamically adjust task acceptance thresholds to balance load

across servers.

• Load Balancing: Monitor server performance and redistribute tasks based on dynamic
thresholds.

• Autoscaling: Adjust VM or container thresholds for CPU/memory usage to scale

resources up or down.
 • QoS Management: Ensure response times and throughput meet the desired targets
under fluctuating demand.

Coordination of Specialized Auntonomic Performance Managers

Introduction & Motivation

• In modern cloud / data center environments, multiple autonomic controllers/managers

often coexist (e.g. one for performance, one for power, one for reliability, etc.).

• These “specialized” managers may have conflicting goals (e.g. performance wants
more resources, power manager wants to reduce consumption).

• The challenge: coordinate them so that the overall system meets SLAs / quality-of-
service goals while optimizing resource usage (e.g. energy, cost).

• Rather than building one monolithic manager, the idea is to let specialized ones
remain (for modularity, existing products, domain separation) and devise coordination
strategies.

The purpose is to ensure all resources specific mangers work together without conflicts
to maintain overall system performance and stability. It enables automatic efficient and
adaptive management of resources in the cloud.
The APMS can maintains the system stability efficiency and quality of services .

APMSARCHITECTURE

The Autonomic Manager Reference Architecture (MAPE-K) represents the self-management

process used in autonomic computing systems. It consists of four main phases — Monitor,
Analyze, Plan, and Execute — all connected through a shared Knowledge base. The Monitor
component collects data from the system and its environment using sensors, while the Analyze
component processes this data to identify performance trends, detect problems, or predict
future behaviour. Based on this analysis, the Plan component formulates actions or strategies
to maintain or improve system performance. The Execute component then implements these
actions on the system through effectors, which make configuration or resource adjustments.
The Knowledge component serves as a common repository that stores system models,
historical data, and policies used by all stages to make intelligent decisions. Together, these
components form a continuous feedback control loop that enables the managed resource
(such as a cloud service or server) to automatically adapt to changing conditions without
human intervention, ensuring optimal performance and reliability.

Role of Coordination Among APMs

1. Conflict Resolution:
o Different APMs have different objectives.
▪ Example: Performance APM wants higher CPU frequency → better response
time.
Power APM wants lower CPU frequency → save energy.
o Coordination ensures these conflicting actions are aligned or balanced, so the
system doesn’t oscillate between extremes.
2. Maintaining System Stability:
o Independent managers acting without coordination may trigger unintended
interactions.
o Coordination ensures actions are harmonized, avoiding resource thrashing or
performance degradation.
3. Optimizing Overall Goals:
o Instead of each APM optimizing only its own goal, coordination enables global
optimization — combining performance, energy, reliability, and cost
considerations.
4. Communication & Information Sharing:
o Coordination allows managers to share their state, plans, and intentions.
o This enables smarter joint decision-making rather than isolated actions.
5. Enabling Modularity & Scalability:
o With coordination, managers can remain specialized and modular.
o New APMs or resources can be added without redesigning the entire system
— the coordination mechanism integrates them.
6. Conflict-free Resource Allocation:
o Coordination ensures that resources are allocated efficiently without one APM
“stealing” resources at the expense of others.

Benefits
• Improved system stability and QoS.
• Efficient resource utilization and energy saving.
• Enables automatic, adaptive, and conflict-free management of cloud systems.
• Supports scalability — more managers or nodes can be added easily.
• Reduces human intervention and management complexity.
Challenges
• Ensuring stability — avoiding oscillations when multiple managers act simultaneously.
• Managing communication overhead between managers.
• Designing effective utility functions and conflict-resolution policies.
• Handling heterogeneous environments with different types of resources and
workloads.

RESOURCE BUNDLING

Resources in a cloud are allocated in bundles, allowing users get maximum benefit from a specific
combination of resources. Indeed, along with CPU cycles, an application needs specific amounts of
main memory, disk space, network bandwidth, and so on. Resource bundling complicates traditional
resource allocation models and has generated interest in economic models and, in particular, auction
algorithms. In the context of cloud computing, an auction is the allocation of resources to the highest
bidder.

Resource bundling is the technique of grouping multiple cloud resources together to form a package or
“bundle” that can be allocated to users or applications as a single unit. It allows cloud providers to manage,
allocate, and optimize resources more efficiently.

Purpose:
• To simplify resource management and allocation.
• To improve utilization of resources by combining underutilized resources.
• To meet the specific performance and SLA (Service Level Agreement) requirements of users.

Key Concepts :
Compute Resources
• Definition: Compute resources provide the processing power required to run applications and
perform calculations.
• Examples:
o CPU (Central Processing Unit): Handles general-purpose computing tasks, such as
running applications or system operations.
o GPU (Graphics Processing Unit): Specialized processor for tasks like AI/ML
computations, image rendering, and high-performance computing.
o Virtual Machines (VMs): Emulated computers that run an operating system and
applications independently on shared physical hardware.
• Purpose: Enables the execution of software and processing of data. Choosing the right compute
resources ensures optimal performance for workloads.

2. Storage Resources
• Definition: Storage resources provide space to store and manage data, applications, and
backups.
• Examples:
o Block Storage: Data is stored in fixed-size blocks. Ideal for databases and file systems
that require fast read/write access.
o Object Storage: Stores data as objects (with metadata). Used for large-scale data
storage, such as media files, backups, and cloud-native applications.
• Purpose: Ensures reliable data storage, accessibility, and management according to the
application needs.
3. Network Resources
• Definition: Network resources allow communication between different components,
applications, or services.
• Examples:
o Bandwidth: The maximum rate of data transfer across the network. Higher bandwidth
supports faster data movement.
o Virtual Network Interfaces (VNI): Virtualized network cards that allow VMs or
containers to connect to the network securely and efficiently.
• Purpose: Ensures that applications and services can communicate seamlessly, whether
internally within a data center or externally over the internet.

4. Software Resources
• Definition: Software resources are pre-installed applications, services, or tools included in the
resource bundle.
• Examples:
o Operating system packages (Linux, Windows)
o Middleware (e.g., web servers, databases, message brokers)
o Development frameworks or pre-configured applications
• Purpose: Reduces setup time and simplifies deployment by providing ready-to-use software
environments.

Resource bundling techniques :

1. Static Bundling
Static bundling means the resources in a bundle are fixed and pre-defined. Once the bundle is
created, the amount and type of resources cannot be changed. For example, a virtual machine
package may come with 2 CPUs, 8 GB RAM, 100 GB storage, and pre-installed Linux. This
bundle will always have the same configuration, no matter how much the workload changes.
The main advantage of static bundling is that it is easy to deploy and predictable because you
know exactly what resources are included. However, it is not flexible and cannot adjust if the
application needs more resources.

2. Dynamic Bundling
Dynamic bundling means the resources in a bundle are not fixed and can change according to
demand. Resources are taken from a shared pool and can increase or decrease as needed. For
example, if a web application is hosted in the cloud, it may start with 2 virtual machines. When
more users visit the website, the system can automatically add more VMs or storage to handle
the extra load. The advantage of dynamic bundling is that it uses resources efficiently and can
adapt to changing workloads. The downside is that it is slightly more complex to manage
because the system has to monitor and adjust resources automatically.

3. User-Defined Bundling
User-defined bundling allows users to choose the exact resources they need and create their
own bundle. For example, a user may select 4 virtual machines, 200 GB storage, 2 Gbps
network, and a pre-installed database to create a custom bundle for their application. The
main benefit of this approach is that it is highly flexible and ensures that users get only the
resources they require, reducing wastage. However, users need to have some knowledge about
their application’s requirements, and mistakes in configuration can lead to resource shortages or
inefficiency.
Combinatorial Auctions. Auctions in which participants can bid on combinations of items, or
pack-ages, are called combinatorial auctions . Such auctions provide a relatively simple,
scalable, and tractable solution to cloud resource allocation. Two recent combinatorial auction
algorithms are the simultaneous clock auction and the clock proxy auction . The algorithm
discussed in this chap-ter and introduced in is called the ascending clock auction (ASCA). In
all these algorithms the current price for each resource is represented by a “clock” seen by all
participants at the auction.

1. ASCA – Ascending Clock Auction

The Ascending Clock Auction (ASCA) is a type of combinatorial auction where the price of
each resource gradually increases over multiple rounds. Participants place bids on bundles
of resources at the current prices. If the demand for any resource exceeds the available supply,
the price for that resource increases in the next round. This process continues until the demand
matches the supply for all resources. ASCA is simple, transparent, and scalable, as all
participants can see the current prices and decide whether to continue bidding. For example, if
multiple users want CPU resources, the CPU price will keep increasing until only the users
who value it most remain in the auction.

2. SCA – Simultaneous Clock Auction

The Simultaneous Clock Auction (SCA) is similar to ASCA, but here all resources have their
prices (“clocks”) running simultaneously. Participants can bid on combinations of resources
at the same time, and the prices of all resources increase in parallel if demand exceeds supply.
The auction continues until the total demand equals the available supply for each resource.
SCA is more efficient when bidders need multiple resources because it allows them to place
bids on entire bundles at once. For example, a user wanting 2 CPUs and 50 GB of storage can
continue bidding until either the CPU or storage price becomes too high.

3. SCVA – Simultaneous Clock with Virtual Auction

The Simultaneous Clock with Virtual Auction (SCVA) is an advanced version of SCA. In
SCVA, participants can bid on virtual bundles of resources, which may not yet exist
physically. The system then calculates the best allocation based on all virtual bids, ensuring
that resources are used efficiently. This type of auction is useful when there are complex
dependencies between resources, such as CPU, storage, and bandwidth needed together for an
application. For example, if a user wants 3 CPUs, 50 GB storage, and high-speed bandwidth,
SCVA allows the system to consider multiple virtual combinations and allocate resources in a
way that maximizes utilization
Cloud Proxy Auction (CPA) combines clock auctions with automation: users indicate the
bundles they want during the clock phase, and a proxy agent automatically bids on their
behalf in the proxy phase, making the process simpler and ensuring efficient allocation without
constant user monitoring. Together, these combinatorial auction types help cloud providers
allocate resources fairly, efficiently, and in a way that matches user needs.
 Scheduling algorithms for computing clouds
Scheduling is a critical component of cloud resource management. Scheduling is responsible for
resource sharing/multiplexing at several levels. A server can be shared among several virtual machines,
each virtual machine could support several applications, and each application may consist of multiple
threads. CPU scheduling supports the virtualization of a processor, the individual threads acting as
virtual processors; a communication link can be multiplexed among a number of virtual channels, one
for each flow.

In addition to the requirement to meet its design objectives, a scheduling algorithm should be efficient,
fair, and starvation-free. The objectives of a scheduler for a batch system are to maximize the throughput
(the number of jobs completed in one unit of time, e.g., in one hour) and to minimize the turnaround
time (the time between job submission and its completion). For a real-time system the objectives are to
meet the deadlines and to be predictable. Schedulers for systems supporting a mix of tasks – some with
hard real-time constraints, others with soft, or no timing constraints – are often subject to contradictory
requirements. Some schedulers are preemptive, allowing a high-priority task to interrupt the execution
of a lower-priority one; others are nonpreemptive.

here the scheduling algorithms in the cloud

1) Fair queuing
2) Start Fair Queuing

Fair Queuing
Computing and communication on a cloud are intimately related. Therefore, it should be no surprise
that the first algorithm we discuss can be used for scheduling packet transmission as well as threads.
Interconnection networks allow cloud servers to communicate with one another and with users. These
networks consist of communication links of limited bandwidth and switches/routers/gateways of limited
capacity. When the load exceeds its capacity, a switch starts dropping packets because it has limited
input buffers for the switching fabric and for the outgoing links, as well as limited CPU cycles.

A switch must handle multiple flows and pairs of source-destination endpoints of the traffic. Thus,
a scheduling algorithm has to manage several quantities at the same time: the bandwidth, the amount
of data each flow is allowed to transport; the timing when the packets of individual flows are
transmitted; and the buffer space allocated to each flow. A first strategy to avoid network congestion is
to use a FCFS scheduling algorithm. The advantage of the FCFS algorithm is a simple management of
the three quantities: bandwidth, timing, and buffer space. Nevertheless, the FCFS algorithm does
not guarantee fairness; greedy flow sources can transmit at a higher rate and benefit from a larger share
of the bandwidth.
To address this problem, a fair queuing algorithm proposed in requires that separate queues,
one per flow, be maintained by a switch and that the queues be serviced in a round-robin
manner. This algorithm guarantees the fairness of buffer space management, but does not
guarantee fairness of bandwidth allocation. Indeed, a flow transporting large packets will
benefit from a larger bandwidth.
Fair Queuing is a scheduling algorithm designed to share resources fairly among multiple
tasks or flows in a system. It ensures that every user/task gets an equal portion of the
resource, such as CPU time or network bandwidth.
Key Points:
 • Works by dividing CPU time into virtual slots and assigning them to each task
proportionally.
• Tasks are served in a round-robin fashion but weighted according to their demand.
• Prevents starvation because every task eventually gets its turn.
• Useful in cloud computing where multiple virtual machines (VMs) or tasks need fair
access to shared resources.

****The Fair Queing can give the allocation based on end time of the application

Start-time fair queuing

Start-Time Fair Queuing (STFQ) is an advanced CPU and resource scheduling algorithm that
improves upon traditional Fair Queuing (FQ). Unlike FQ, which allocates resources based on
finish times, STFQ schedules tasks based on their start times, ensuring that resources are
distributed fairly while reducing latency. It is especially useful in cloud computing, real-time
systems, and interactive applications where tasks of varying lengths and priorities must be
managed efficiently.
Main Idea is the core concept of STFQ is that each task is assigned a virtual start time (S_i)
and a virtual finish time (F_i), which are used to determine the order of execution. Resources
are allocated in ascending order of start times, allowing shorter or higher-priority tasks to
access resources earlier. This ensures both fairness and efficiency while maintaining low
latency for critical tasks.

**** The Start-time fair queuing can give the allocation based on starting time of the
application .
Example :