【Reinforcement Learning】强化学习下的多级反馈队列（MFQ）算法

举报
不去幼儿园 发表于 2024/12/03 08:31:56 2024/12/03
【摘要】 在强化学习（Reinforcement Learning, RL）相关背景下，多级反馈队列（Multilevel Feedback Queue, MFQ）算法可以作为调度问题的求解框架，用于优化资源分配和任务调度策略。在这种情况下，MFQ的概念和机制可以被调整为一种面向学习的形式，其中调度策略通过强化学习算法来动态优化。

​

 📢本篇文章是博主强化学习（RL）领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉强化学习专栏：

       【强化学习】（11）---《强化学习下的多级反馈队列（MFQ）算法》

强化学习下的多级反馈队列（MFQ）算法

目录

1.前言

2.背景与问题描述

3.多级反馈队列与强化学习的结合

状态定义

动作定义

奖励设计

强化学习算法

4.实现机制

5.强化学习背景下的优势

[Python] 强化学习环境下的多级反馈队列（MFQ）实验

1. 定义强化学习环境

2. RL智能体

[Notice]  实验设计

6.实际应用与挑战

7.总结

​

 1.前言

        在强化学习（Reinforcement Learning, RL）相关背景下，多级反馈队列（Multilevel Feedback Queue, MFQ）算法可以作为调度问题的求解框架，用于优化资源分配和任务调度策略。在这种情况下，MFQ的概念和机制可以被调整为一种面向学习的形式，其中调度策略通过强化学习算法来动态优化。

        以下是强化学习背景下多级反馈队列的详细介绍：

2.背景与问题描述

在强化学习的场景中，任务调度通常涉及以下挑战：

  1. 多任务竞争：多个任务需要使用有限的资源（如CPU时间片、内存等），如何有效调度以提高系统性能。
  2. 不确定性：任务的执行时间、到达时间和优先级可能是动态变化的。
  3. 优化目标：调度策略需要权衡不同目标，如最小化等待时间、提高吞吐量或响应时间。

多级反馈队列调度问题可以建模为一个强化学习问题，其中：

  • 环境：表示任务到达、队列状态和系统资源状况。
  • 智能体：负责决定如何在不同的队列中分配任务。
  • 动作：调度策略决定将任务分配到哪个队列，或是否调整队列的优先级。
  • 奖励：根据调度效果（如任务完成时间、系统吞吐量等）反馈奖励信号。

3.多级反馈队列与强化学习的结合

        在强化学习背景下，MFQ可以通过强化学习算法动态优化调度策略，从而提升其性能。以下是具体机制：

  • 状态定义

状态可以包括以下信息：

                当前所有队列中的任务数量和属性（如执行时间、优先级）。

                每个队列的时间片大小。

                系统的资源使用状况（如CPU占用率）。

                当前时间和系统运行状态。

  • 动作定义

智能体可以采取的动作包括：

  1. 将新到达的任务分配到某个队列。
  2. 调整现有任务的优先级（将任务从低优先级队列提升到高优先级队列）。
  3. 调整时间片的大小，以适应任务负载的动态变化。

  • 奖励设计

奖励信号反映调度策略的好坏，可以包括：

  • 正向奖励：当任务完成、吞吐量提高或等待时间减少时给予正向奖励。
  • 负向奖励：当任务等待时间过长或资源利用率低下时给予负向奖励。
  • 多目标优化：奖励函数可以综合考虑多个目标，如响应时间、吞吐量、资源利用率等。

强化学习算法

以下RL算法可以用于优化多级反馈队列调度策略：

  1. Q-Learning：通过表格方式学习队列状态和动作的值函数。
  2. 深度Q网络（DQN）：适用于高维状态空间，利用神经网络预测动作的价值。
  3. 策略梯度方法：直接优化策略，适用于连续动作空间。
  4. 强化学习结合元学习：通过学习任务特性自适应调整调度策略。

4.实现机制

强化学习背景下的多级反馈队列可以通过以下流程实现：

  • 队列初始化：

                定义多级队列（如三层队列）。

                设置初始的时间片大小和优先级规则。

  • 任务到达与分配：

                当新任务到达时，智能体根据当前状态选择将其分配到哪个队列。

                可以在初始阶段使用启发式规则，逐渐过渡到强化学习决策。

  • 动态调度与反馈：

                智能体根据强化学习策略决定：

                        调度哪个队列中的任务。

                        是否调整时间片大小或优先级。

                系统环境根据任务的完成情况生成奖励反馈。

  • 更新策略：

                智能体根据奖励信号更新调度策略，优化长期累计奖励。

5.强化学习背景下的优势

  1. 动态性与适应性：

    • 强化学习算法可以根据任务的动态变化自适应调整调度策略。
    • 与传统静态规则相比，能够处理任务到达分布的非平稳性。

  2. 多目标优化：

    • 强化学习允许通过设计复杂的奖励函数同时优化多个性能指标。

  3. 长期收益：

    • 强化学习关注长期累计奖励，而非仅关注当前任务，从而能平衡短期和长期性能。

[Python] 强化学习环境下的多级反馈队列（MFQ）实验

设计思路

  • 状态空间：

                定义为系统当前的任务队列状态（例如：各队列任务数量、优先级等）。

  • 动作空间：

                定义为调度器的决策，例如：选择某个队列中的任务执行或任务的优先级调整。

  • 奖励函数：

        优化目标通常包括：

                最小化任务平均等待时间。

                最小化任务完成时间。

                最大化系统资源利用率。

  • RL智能体：

                使用深度Q学习（DQN）或策略梯度方法优化调度策略。

                DQN的目标是通过学习动作-价值函数Q(s, a)，来找到最优策略，使得智能体在每个状态s下执行动作a能获得的未来累积奖励最大化。

                Q值函数：Q值函数表示在状态 s编辑下执行动作 a编辑 后能够获得的期望回报：

Q(s, a) = \mathbb{E}\left[ \sum_{t=0}^\infty \gamma^t r_t \mid s_0 = s, a_0 = a \right]

  • r_t: 第t步的奖励。
  • \gamma: 折扣因子，控制未来奖励的权重。

                深度Q网络：DQN使用神经网络来近似Q值函数 Q(s, a; \theta)，其中\theta 是网络参数。网络输入是状态 s，输出是对应每个动作的Q值。

        🔥若是下面代码复现困难或者有问题，欢迎评论区留言；需要以整个项目形式的代码，请在评论区留下您的邮箱📌，以便于及时分享给您（私信难以及时回复）。

以下使用 gym 库模拟强化学习环境，并实现 RL 智能体优化 MFQ。

1. 定义强化学习环境

环境类继承自 gym.Env，实现 MFQ 逻辑。

"""《强化学习环境下的多级反馈队列（MFQ）实验》
    时间：2024.11
    环境：gym
    作者：不去幼儿园
"""
import gym
from gym import spaces
import numpy as np
from collections import deque


class MFQEnvironment(gym.Env):
    def __init__(self, num_queues=3, time_slices=[2, 4, 8], max_tasks=10):
        super(MFQEnvironment, self).__init__()
        
        self.num_queues = num_queues
        self.time_slices = time_slices
        self.queues = [deque() for _ in range(num_queues)]
        self.current_time = 0
        self.max_tasks = max_tasks
        
        # Define action and observation space
        # Actions: [0..num_queues-1], representing which queue to pick a task from
        self.action_space = spaces.Discrete(num_queues)
        # Observations: queue lengths + task remaining times (flattened)
        self.observation_space = spaces.Box(
            low=0, high=max_tasks, shape=(num_queues,), dtype=np.int32
        )
        
        self.tasks = []
        self._initialize_tasks()
    
    def _initialize_tasks(self):
        """Initialize a random set of tasks"""
        for i in range(self.max_tasks):
            arrival_time = np.random.randint(0, 5)
            burst_time = np.random.randint(1, 10)
            task = {
                'task_id': i,
                'arrival_time': arrival_time,
                'burst_time': burst_time,
                'remaining_time': burst_time,
                'priority': 0
            }
            self.queues[0].append(task)
    
    def step(self, action):
        """Execute the action and return new state, reward, done, info"""
        # Select queue and execute the first task
        if len(self.queues[action]) > 0:
            task = self.queues[action].popleft()
            time_slice = self.time_slices[action]
            execution_time = min(task['remaining_time'], time_slice)
            
            # Simulate execution
            self.current_time += execution_time
            task['remaining_time'] -= execution_time
            
            if task['remaining_time'] == 0:
                reward = 1  # Task completed successfully
            else:
                # Move task to a lower-priority queue
                next_priority = min(task['priority'] + 1, self.num_queues - 1)
                task['priority'] = next_priority
                self.queues[next_priority].append(task)
                reward = -0.1  # Penalize for incomplete task
        else:
            reward = -1  # Penalize invalid action (empty queue)
        
        # Check if all tasks are completed
        done = all(len(queue) == 0 for queue in self.queues)
        
        # Observation: current queue lengths
        observation = np.array([len(queue) for queue in self.queues])
        return observation, reward, done, {}
    
    def reset(self):
        """Reset the environment to the initial state"""
        self.queues = [deque() for _ in range(self.num_queues)]
        self.current_time = 0
        self.tasks = []
        self._initialize_tasks()
        return np.array([len(queue) for queue in self.queues])
    
    def render(self, mode='human'):
        """Render the current state"""
        print(f"Current time: {self.current_time}")
        for i, queue in enumerate(self.queues):
            print(f"Queue {i}: {[task['task_id'] for task in queue]}")

2. RL智能体

使用 DQN 智能体来学习优化调度策略。

import random
import torch
import torch.nn as nn
import torch.optim as optim


class DQNScheduler(nn.Module):
    def __init__(self, input_size, output_size):
        super(DQNScheduler, self).__init__()
        self.fc = nn.Sequential(
            nn.Linear(input_size, 64),
            nn.ReLU(),
            nn.Linear(64, 64),
            nn.ReLU(),
            nn.Linear(64, output_size)
        )
    
    def forward(self, x):
        return self.fc(x)



def train_dqn(env, episodes=500):
    input_size = env.observation_space.shape[0]
    output_size = env.action_space.n
    dqn = DQNScheduler(input_size, output_size)
    optimizer = optim.Adam(dqn.parameters(), lr=0.001)
    loss_fn = nn.MSELoss()
    replay_buffer = deque(maxlen=1000)
    gamma = 0.99
    epsilon = 1.0
    epsilon_decay = 0.995
    min_epsilon = 0.1

    for episode in range(episodes):
        state = env.reset()
        total_reward = 0
        done = False

        while not done:
            if random.random() < epsilon:
                action = env.action_space.sample()
            else:
                with torch.no_grad():
                    q_values = dqn(torch.tensor(state, dtype=torch.float32))
                    action = q_values.argmax().item()

            next_state, reward, done, _ = env.step(action)
            replay_buffer.append((state, action, reward, next_state, done))
            total_reward += reward
            state = next_state

            # Replay buffer training
            if len(replay_buffer) >= 32:
                batch = random.sample(replay_buffer, 32)
                states, actions, rewards, next_states, dones = zip(*batch)
                
                states = torch.tensor(states, dtype=torch.float32)
                actions = torch.tensor(actions, dtype=torch.int64).unsqueeze(1)
                rewards = torch.tensor(rewards, dtype=torch.float32)
                next_states = torch.tensor(next_states, dtype=torch.float32)
                dones = torch.tensor(dones, dtype=torch.float32)

                q_values = dqn(states).gather(1, actions).squeeze()
                next_q_values = dqn(next_states).max(1)[0]
                target_q_values = rewards + gamma * next_q_values * (1 - dones)

                loss = loss_fn(q_values, target_q_values.detach())
                optimizer.zero_grad()
                loss.backward()
                optimizer.step()

        epsilon = max(min_epsilon, epsilon * epsilon_decay)
        print(f"Episode {episode + 1}/{episodes}, Total Reward: {total_reward}")

    return dqn

[Notice]  实验设计

  1. 目标： 测试智能体在动态任务到达场景中优化任务调度的性能。
  2. 评价指标：
    • 平均等待时间。
    • 系统资源利用率。
    • 总任务完成时间。
  3. 环境参数：
    • 三级队列，时间片为 2、4、8 单位。
    • 任务到达时间与执行时间随机分布。

        由于博文主要为了介绍相关算法的原理和应用的方法，缺乏对于实际效果的关注，算法可能在上述环境中的效果不佳或者无法运行，一是算法不适配上述环境，二是算法未调参和优化，三是没有呈现完整的代码，四是等等。上述代码用于了解和学习算法足够了，但若是想直接将上面代码应用于实际项目中，还需要进行修改。

定义实验测试用例，生成任务和调度日志

 import random
import pandas as pd

# Generate test cases for MFQ environment
def generate_test_tasks(num_tasks=10, max_arrival_time=10, max_burst_time=15):
    tasks = []
    for task_id in range(num_tasks):
        arrival_time = random.randint(0, max_arrival_time)
        burst_time = random.randint(1, max_burst_time)
        task = {
            'Task ID': task_id,
            'Arrival Time': arrival_time,
            'Burst Time': burst_time,
        }
        tasks.append(task)
    return tasks

# Log generation for MFQ execution
def generate_execution_log(tasks, scheduler_output):
    logs = []
    for log in scheduler_output:
        logs.append({
            'Time': log['time'],
            'Queue': log['queue'],
            'Task ID': log['task_id'],
            'Action': log['action']
        })
    return pd.DataFrame(logs)

# Simulate test tasks
num_tasks = 10
test_tasks = generate_test_tasks(num_tasks=num_tasks)
task_df = pd.DataFrame(test_tasks)

# Display generated tasks
import ace_tools as tools; tools.display_dataframe_to_user(name="Generated Test Tasks for MFQ", dataframe=task_df)

​​​​​​6.实际应用与挑战

实际应用

  • 云计算资源调度：通过强化学习优化虚拟机任务调度。
  • 操作系统任务管理：动态调整任务优先级和队列时间片。
  • 嵌入式系统：在资源有限的情况下优化任务调度。

主要挑战

  1. 状态空间复杂：多任务和多队列导致状态空间维度高，难以用传统表格方法处理。
  2. 学习效率低：在线学习可能需要较长时间才能收敛到优良策略。
  3. 奖励延迟问题：调度的效果可能在较长时间后才能显现，增加了学习难度。

7.总结

        在强化学习背景下，多级反馈队列算法的调度策略不再是静态规则，而是通过强化学习实现动态优化。这种方法充分利用了强化学习的自适应性和长期优化特性，使得MFQ能够更高效地应对动态任务调度问题。通过设计合理的状态、动作和奖励函数，强化学习驱动的MFQ可以在多任务场景中显著提升调度性能。

更多文章，请查看文章：

【MADRL】多智能体深度强化学习《纲要》

        博客都是给自己看的笔记，如有误导深表抱歉。文章若有不当和不正确之处，还望理解与指出。由于部分文字、图片等来源于互联网，无法核实真实出处，如涉及相关争议，请联系博主删除。如有错误、疑问和侵权，欢迎评论留言联系作者，或者添加VX：Rainbook_2，联系作者。✨

【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
Python 人工智能 任务调度 机器学习 深度学习
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入