投稿
  1. 首页
  2. 随笔

数据结构与算法的深入应用-调度算法

支付盾•2022-12-17•随笔•阅读42

数据结构与算法的深入应用-调度算法,第1张

数据结构与算法的深入应用-调度算法

调度算法常见于 *** 作系统，因为系统的资源时有限的，当有多个进程（或多个进程发出的请求）要使用系统资源时，就需要按照一定的原则来选择进程（请求）来占用系统资源。这就是所谓的调度。常见的调度算法有以下几种

1，先来先服务（FCFS）

1）概述
先来先服务，就是按照请求的提交时间顺序，依次执行。
2）实现
定义一个task作为任务实例，BlockingQueue作为任务队列

package com.xieq.algorithm.schedule;

import java.util.Random;
import java.util.concurrent.linkedBlockingQueue;
import java.util.concurrent.TimeUnit;


public class FCFS {

    public static void main(String[] args) throws InterruptedException {
        linkedBlockingQueue queue = new linkedBlockingQueue<>();
        new Thread(() -> {
            while (true) {
                try {
                    Task task = queue.take();
                    task.exec();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }

        }).start();

        for (int i = 1; i <= 5; i++) {
            System.out.println("add task" + i);
            Task task = new Task("task" + i, (long) new Random().nextInt(1000));
            queue.put(task);
        }
    }
}

class Task {
    
    private String name;
    
    private Long execTime;
    
    private Long addTime;

    public Task(String name, Long execTime) {
        this.name = name;
        this.execTime = execTime;
        this.addTime = System.currentTimeMillis();
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Long getExecTime() {
        return execTime;
    }

    public void setExecTime(Long execTime) {
        this.execTime = execTime;
    }

    public Long getAddTime() {
        return addTime;
    }

    public void setAddTime(Long addTime) {
        this.addTime = addTime;
    }

    public void exec() throws InterruptedException {
        TimeUnit.MILLISECONDS.sleep(this.execTime);
        System.out.printf("task：%s,执行耗时%s,添加时间：%s%n", this.getName(), this.getExecTime(), this.getAddTime());

    }
}

运行输出如下：

add task1
add task2
add task3
add task4
add task5
task：task1,执行耗时529,添加时间：1642488289550
task：task2,执行耗时77,添加时间：1642488289550
task：task3,执行耗时641,添加时间：1642488289550
task：task4,执行耗时775,添加时间：1642488289550
task：task5,执行耗时734,添加时间：1642488289550

add按顺序放入，时间有序exec也安顺序执行，

4）优缺点

    多用于CP密集型任务，对io密集型任务不利时间相对均衡的任务可以使用，比如现实中的排队打卡如果业务需要依赖大量外部因素，执行时间片时间长短不一，FCFS不利于整体任务的处理进度，可能会因为一个长时间的任务而造成大量的阻塞.
2，短作业优先（SJF）

1）概述
执行时间短的优先调度执行，需要任务在提交前申请一个需要的cpu执行时间。
2）实现
使用treeMap来对任务进行排序

package com.xieq.algorithm.schedule;

import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import java.util.concurrent.TimeUnit;


public class SJF {

    public static void main(String[] args) {
        TreeMap map = new TreeMap<>();

        for (int i = 1; i <= 5; i++) {
            Task task = new Task("task" + i, (long) new Random().nextInt(1000));
            map.put(task.getExecTime(), task);
            System.out.println("add test" + i);
        }

        new Thread(() -> {
            while (true) {
                try {
                    Map.Entry entry = map.pollFirstEntry();
                    if (entry == null) {
                        Thread.sleep(1000);
                    } else {
                        entry.getValue().exec();
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }).start();


    }
}

运行输出如下：

add test1
add test2
add test3
add test4
add test5
task：task5,执行耗时125,添加时间：1642491369135
task：task1,执行耗时736,添加时间：1642491369135
task：task4,执行耗时788,添加时间：1642491369135
task：task2,执行耗时967,添加时间：1642491369135
task：task3,执行耗时977,添加时间：1642491369135

可见任务的执行顺序并非任务的添加顺序，而是任务的执行时间从小到大的排序顺序执行。

3， 时间片轮询（RR）

1）时间片轮询，
2）实现
基于数字作为数据插槽方式实现

package com.xieq.algorithm.schedule;

import java.util.Random;
import java.util.concurrent.TimeUnit;


public class RR {

    private Integer[] tasks = new Integer[3];

    public void addTask(Integer i) {
        int index = 0;
        //任务添加成功，推出循坏，添加不成功一直循环，知道任务添加成功为止
        while (true) {
            if (tasks[index] == null) {
                tasks[index] = i;
                System.out.println("--->添加task" + i);
                break;
            } else {
                index++;
            }
            //达到末尾，冲头再来
            if (index == tasks.length) {
                index = 0;
            }
        }
    }

    public void execTask() {
        new Thread(() -> {
            int index = 0;
            while (true) {
                Integer task = tasks[index];
                if (task != null) {
                    try {
                        //模拟任务执行时间
                        TimeUnit.MILLISECONDS.sleep(new Random().nextInt(1000));
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println("exec task index:" + index + " value: " + tasks[index]);
                    //任务执行完就把当前槽位置空
                    tasks[index] = null;
                    continue;
                }
                index++;
                //达到末尾，冲头再来
                if (index == tasks.length) {
                    index = 0;
                }
            }
        }).start();
    }

    public static void main(String[] args) {
        RR rr = new RR();
        rr.execTask();
        for (int i = 0; i < 10; i++) {
            rr.addTask(i);
        }
    }
}

运行输出如下：

—>添加task0
—>添加task1
—>添加task2
exec task index:0 value: 0
—>添加task3
exec task index:1 value: 1
—>添加task4
exec task index:2 value: 2
—>添加task5
exec task index:2 value: 5
—>添加task6
exec task index:2 value: 6
—>添加task7
exec task index:0 value: 3
exec task index:1 value: 4
—>添加task8
—>添加task9
exec task index:2 value: 7
exec task index:0 value: 9
exec task index:1 value: 8

add任务，index无需value有序，说明是按顺序提交的，但是插槽无序，哪里有空放哪里exec执行index有序，value无序，说明任务是轮询执行的，每个插槽里面的任务不一定是谁的
优缺点：做到了机会的相对公平，不会因为某个任务的执行时间超长而得不到执行缺乏任务的主次管理，重要的任务不会优先执行，必须等到时间片轮到了才能执行 4，优先级调度（HPF）

1）根据任务优先级调度
2）实现
task类新增一个属性：priority 优先级

class Task {
    
    private String name;
    
    private Long execTime;
    
    private Long addTime;

    
    private Integer priority;

    public Task(String name, Long execTime) {
        this.name = name;
        this.execTime = execTime;
        this.addTime = System.currentTimeMillis();
    }

    public Task(String name, Long execTime, Integer priority) {
        this.name = name;
        this.execTime = execTime;
        this.priority = priority;
        this.addTime = System.currentTimeMillis();
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Long getExecTime() {
        return execTime;
    }

    public void setExecTime(Long execTime) {
        this.execTime = execTime;
    }

    public Long getAddTime() {
        return addTime;
    }

    public void setAddTime(Long addTime) {
        this.addTime = addTime;
    }

    public Integer getPriority() {
        return priority;
    }

    public void setPriority(Integer priority) {
        this.priority = priority;
    }

    public void exec() throws InterruptedException {
        TimeUnit.MILLISECONDS.sleep(this.execTime);
        System.out.printf("task：%s,优先级：%s,执行耗时%s,添加时间：%s%n", this.getName(), this.getPriority(), this.getExecTime(), this.getAddTime());

    }
}



package com.xieq.algorithm.schedule;

import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import java.util.concurrent.TimeUnit;


public class HPF {

    public TreeMap map = new TreeMap<>();

    public void addTask(Task task) {
        map.put(task.getPriority(), task);
        System.out.printf("added task name:%s,优先级:%s%n", task.getName(), task.getPriority());
    }

    public void execTask() throws InterruptedException {
        while (true) {
            Map.Entry en = map.pollFirstEntry();
            if (en != null) {
                en.getValue().exec();
            }
            TimeUnit.MILLISECONDS.sleep(500);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        HPF hpf = new HPF();
        for (int i = 0; i < 5; i++) {
            Task task = new Task("task" + i, (long) new Random().nextInt(1000), 5-i);
            hpf.addTask(task);
        }
        hpf.execTask();
    }

}

运行输出如下：
added task name:task0,优先级:5
added task name:task1,优先级:4
added task name:task2,优先级:3
added task name:task3,优先级:2
added task name:task4,优先级:1
task：task4,优先级：1,执行耗时849,添加时间：1642496269976
task：task3,优先级：2,执行耗时217,添加时间：1642496269976
task：task2,优先级：3,执行耗时928,添加时间：1642496269976
task：task1,优先级：4,执行耗时50,添加时间：1642496269976
task：task0,优先级：5,执行耗时86,添加时间：1642496269956

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/zaji/5706801.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
支付盾支付盾一级用户组
00
上一篇 2022-12-17
下一篇2022-12-17

发表评论

登录后才能评论

评论列表（0条）

    保存