4

さまざまなスケジューリング アルゴリズムをシミュレートする C プログラムがあります。プロセス情報はファイルから読み取られます。ファイル内の各プロセスの情報は、以下の構造体に保存されます。

struct task_struct {
  volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
  unsigned int flags; /* per process flags, defined below */
  int on_rq;
  int prio, static_prio, normal_prio;
  const struct sched_class *sched_class;
  struct list_head tasks;
  pid_t pid;
  int arr;
  /* simplify accounting */
  int ticks;
  int start_tick;
  int end_tick;
  int burst;
};

タスク/プロセスのリストを保持する「キュー」構造があります

struct rq {
  struct task_struct *curr, *idle, *stop;
  struct list_head task_root;
};

カーネルのリンクされたリストがどのように機能するかをある程度理解しており、list.h のユーザー バージョンを持っています。リストとのやり取りのほとんどは、list.h で定義されているようです。そのファイル内の関数を使用して、並べ替えアルゴリズム (おそらくマージ) を実装しようとする方法について、誰もがアイデアを持っていますか?

4

1 に答える 1

10

list_sortdefined in を使用しないのはなぜlinux/list_sort.hですか? 構文は次のとおりです。

/**
 * list_sort - sort a list
 * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 *
 * This function implements "merge sort", which has O(nlog(n))
 * complexity.
 *
 * The comparison function @cmp must return a negative value if @a
 * should sort before @b, and a positive value if @a should sort after
 * @b. If @a and @b are equivalent, and their original relative
 * ordering is to be preserved, @cmp must return 0.
 */
void list_sort(void *priv, struct list_head *head,
        int (*cmp)(void *priv, struct list_head *a,
            struct list_head *b))
于 2013-10-10T07:20:50.457 に答える