首页 > 试题广场 >

用 C 语言写一个函数来执行一串任务。任务是互相依赖的。比如

[问答题]

用 C 语言写一个函数来执行一串任务。任务是互相依赖的。比如 B 任务依赖 A 任务，则 A 完成 B 才能执行。不考虑并发限制，假设所有的任务都能一次执行成功，所有的任务执行时间都相等。任务数据结构原型为：

typedef struct {
    //该任务的 ID
    int id;
    //该任务依赖的任务的 ID
    int *child;
    //该任务依赖的任务个数
    int child_num;
} task;

// 函数原型：
bool doschedule(task*pask，inttask_num);

//以下函数可以直接调用：
void dotask(int id); //执行一个进程

//等待 timeout 时间，并返回一个执行成功的任务的 id，如果没有任务在时间片内完成，则返回-1
int waittask(int timeout);

bool killtask(int id); //杀掉一个进程

查看答案及解析

一只咕咕咕

1.通过拓扑排序来建立执行顺序.

2. 对于无关联的拓扑节点可以并发执行

发表于 2014-10-25 00:26:02 回复(1)

渊鸿

bool doschedule(task* pask, int task_num) {     const int Timeout = 10;     int* pFlag = new int[task_num];     for (int i=0; i<task_num; ++i)     {         pFlag[i] = pask[i].child_num;     }     int Count = 0;     while (true)     {         int Index = -2;         for (int i=0; i<task_num; ++i)         {             if (pFlag[i] == 0)             {                 Index = i;                 break;             }         }         if (Count == task_num)         {             return true;         }         else if (pFlag[Index] == -2)         {             return false;         }         else         {             dotask(Index);                 waittask(Index);             pFlag[Index]--;             Count++;             for (int k=0; k<task_num; ++k)             {                 int* pChild = pask[k].child;                 int NumChild = pask[k].child_num;                 for (int m=0; m<NumChild; ++m)                 {                     if (pChild[m] == Index)                     {                         pFlag[k]--;                         break;                     }                 }             }             }     } }

发表于 2015-09-10 18:36:51 回复(0)