讷讷！讷讷！

操作系统实验三

  • ~5.87K 字
  1. 1. 处理器调度——实时调度算法EDF
    1. 1.1. 1.clone和pthread_create的区别？
    2. 1.2. 2.调度算法中ci_left和ti_left作用？
    3. 1.3. 3.EDF算法任务执行序列如下，请分析你的实验结果是否与次一致，为什么？如何修改？（给出修改部分的代码）

处理器调度——实时调度算法EDF

实验内容：

  1. 在Linux环境下采用用户级别线程模拟实现EDF实时调度算法。
  2. 给定一组周期性实时任务并判断是否可调度。
  3. 如果可调度，请按算法模拟调度次序，并在终端给出Gantt图。

设计原理：

  1. select_proc()实现调度算法，proc()执行任务，idle()没有可执行任务时执行，main()初始化。
  2. 为每个线程设计了一个等待锁，暂不运行的任务等待在相应的锁变量上。
  3. 主线程按调度算法唤醒子线程，子线程执行一个时间单位后把控制权交给主线程判断是否需要重新调度

实验过程如下

处理器调度——实时调度算法EDF

文本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <math.h>
#include <pthread.h>
#include <sched.h>
#include <semaphore.h>
#include "stdio.h"
#include "stdlib.h"
#include <unistd.h>

typedef struct { // 实时任务描述
  char task_id;
  int call_num; // 任务发生次数
  int ci;       // Ci
  int ti;       // Ti
  int ci_left;
  int ti_left;
  int flag;     // 任务是否活跃，0否，2是
  int arg;      // 参数
  pthread_t th; // 任务对应线程
} task;
void proc(int *args);
void *idle();
int select_proc();
int task_num = 0;
int idle_num = 0;
int curr_proc = -1;
int demo_time = 100; // 演示时间
task *tasks;
pthread_mutex_t proc_wait[100];
pthread_mutex_t main_wait, idle_wait;
float sum = 0;
pthread_t idle_proc;
int main(int argc, char **argv) {
  pthread_mutex_init(&main_wait, NULL);
  pthread_mutex_lock(&main_wait); // 下次执行lock等待
  pthread_mutex_init(&idle_wait, NULL);
  pthread_mutex_lock(&idle_wait); // 下次执行lock等待
  printf("Please input number of real time tasks:\n");
  scanf("%d", &task_num);
  tasks = (task *)malloc(task_num * sizeof(task));
  int i;
  for (i = 0; i < task_num; i++) {
    pthread_mutex_init(&proc_wait[i], NULL);
    pthread_mutex_lock(&proc_wait[i]);
  }
  for (i = 0; i < task_num; i++) {
    printf("Please input task id, followed by Ci and Ti:\n");
    getchar();
    scanf("%c,%d,%d,", &tasks[i].task_id, &tasks[i].ci, &tasks[i].ti);
    tasks[i].ci_left = tasks[i].ci;
    tasks[i].ti_left = tasks[i].ti;
    tasks[i].flag = 2;
    tasks[i].arg = i;
    tasks[i].call_num = 1;
    sum = sum + (float)tasks[i].ci / (float)tasks[i].ti;
  }
  printf("algorithm EDF\n");
  printf("Please input demo time:");
  scanf("%d", &demo_time);
  double r = 1;   // EDF算法
  if (sum > r) { // 不可调度
    printf("(sum=%lf > r=%lf) ,not schedulable!\n", sum, r);
    exit(2);
  }

  pthread_create(&idle_proc, NULL, (void *)idle, NULL); // 创建闲逛线程
  for (i = 0; i < task_num; i++) // 创建实时任务线程
    pthread_create(&tasks[i].th, NULL, (void *)proc, &tasks[i].arg);
  for (i = 0; i < demo_time; i++) {
    int j;
    if ((curr_proc = select_proc()) != -1) {    // 按调度算法选线程
      pthread_mutex_unlock(&proc_wait[curr_proc]); // 唤醒
      pthread_mutex_lock(&main_wait);              // 主线程等待
    } else { // 无可运行任务，选择闲逛线程
      pthread_mutex_unlock(&idle_wait);
      pthread_mutex_lock(&main_wait);
    }
    for (j = 0; j < task_num; j++) { // Ti--，为0时开始下一周期
      if (--tasks[j].ti_left == 0) {
        tasks[j].ti_left = tasks[j].ti;
        tasks[j].ci_left = tasks[j].ci;
        pthread_create(&tasks[j].th, NULL, (void *)proc, &tasks[j].arg);
        tasks[j].flag = 2;
      }
    }
  }
  printf("\n");
  sleep(10);
};

void proc(int *args) {
  while (tasks[*args].ci_left > 0) {
    pthread_mutex_lock(&proc_wait[*args]); // 等待被调度
    if (idle_num != 0) {
      printf("idle(%d)", idle_num);
      idle_num = 0;
    }
    printf("%c%d ", tasks[*args].task_id, tasks[*args].call_num);
    tasks[*args].ci_left--; // 执行一个时间单位
    if (tasks[*args].ci_left == 0) {
      printf("(%c-ci:%d)\n", tasks[*args].task_id, tasks[*args].ci);
      tasks[*args].flag = 0;
      tasks[*args].call_num++;
    }
    pthread_mutex_unlock(&main_wait); // 唤醒主线程
  }
};
void *idle() {
  while (1) {
    pthread_mutex_lock(&idle_wait); // 等待被调度
    printf("->");                   // 空耗一个时间单位
    idle_num++;
    pthread_mutex_unlock(&main_wait); // 唤醒主控线程
  }
};
int select_proc() {
  int j;
  int temp1, temp2;
  temp1 = 10000;
  temp2 = -1;
  for (j = 0; j < task_num; j++) {
    if (tasks[j].flag == 2) {
 // EDF算法
        if (temp1 > tasks[j].ti_left) {
          temp1 = tasks[j].ti_left;
          temp2 = j;
        }
    }
  }
  return temp2;
}

编译并运行，结果如下

运行结果

1.clone和pthread_create的区别？

  1. 功能：

    • clone：clone函数是Linux系统提供的系统调用，它可以创建一个新的进程或线程。它提供了更灵活的选项，可以指定新线程所继承的父线程的资源，如文件描述符表、内存空间等。因此，clone函数可以创建线程，也可以创建进程，还可以实现进程间的共享资源。
    • pthread_create：pthread_create函数是POSIX线程库（pthread）提供的函数，用于创建一个新的线程。它只能用于创建线程，不能创建进程。它创建的线程与父线程共享进程的资源，如文件描述符表和内存空间。

  2. 调用方式：

    • clone：clone函数是一个系统调用，使用时需要通过提供一个函数指针作为参数，指定新线程要执行的函数。调用clone函数时，需要指定一系列的标志和选项来设置新线程的行为和继承关系。
    • pthread_create：pthread_create函数是一个库函数，使用时需要提供一个函数指针作为参数，指定新线程要执行的函数。调用pthread_create函数时，只需要提供线程的属性和参数等少量参数即可。

  3. 平台兼容性：

    • clone：clone函数是Linux特有的系统调用，因此只能在Linux系统上使用。
    • pthread_create：pthread_create函数是POSIX标准定义的函数，几乎所有的主流操作系统都支持POSIX线程库，所以pthread_create函数可以在多个操作系统上使用。

clone函数提供了更多的灵活性，可以创建线程或进程，并且可以继承父线程的资源。而pthread_create函数只能创建线程，并且新线程与父线程共享进程的资源。选择使用哪个函数取决于具体的需求和平台的兼容性要求。

2.调度算法中ci_left和ti_left作用？

在这段代码中，ci_left和ti_left分别表示实时任务的剩余执行时间和剩余周期时间。

  • ci_left：表示实时任务的剩余执行时间。在每个时间单位内，实时任务的ci_left会递减，表示任务执行了一个时间单位。当ci_left减至0时，表示该任务完成了当前周期的执行。

  • ti_left：表示实时任务的剩余周期时间。在每个时间单位内，实时任务的ti_left会递减。当ti_left减至0时，表示当前周期结束，任务需要开始下一个周期的执行。

这两个变量在调度算法中的作用是：

  1. 执行实时任务：当调度器选择一个实时任务进行执行时，会通过减少ci_left的值来模拟任务的执行。每次执行一个时间单位，ci_left减1，直到减至0表示任务完成当前周期的执行。

  2. 控制周期性执行：通过递减ti_left的值，判断是否需要开始下一个周期的执行。当ti_left减至0时，表示当前周期结束，调度器会将ti_left重置为初始周期时间，以便任务开始下一个周期的执行。

这样，通过ci_left和ti_left的管理，调度器可以控制实时任务的执行时间和周期，实现实时任务的周期性执行和调度。

3.EDF算法任务执行序列如下，请分析你的实验结果是否与次一致，为什么？如何修改？（给出修改部分的代码）

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct { // 实时任务描述
  char task_id;
  int call_num; // 任务发生次数
  int ci;       // Ci
  int ti;       // Ti
  int ci_left;
  int ti_left;
  int flag;     // 任务是否活跃，0否，2是
  int arg;      // 参数
  int deadline;
  pthread_t th; // 任务对应线程
} task;
1
2
3
4
if (temp1 > tasks[j].deadline) {
  temp1 = tasks[j].deadline;
  temp2 = j;
}

1686150350605

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,