基本的に、マルチレベルのプライオリティ キューを実装する xv6 カーネル用のスケジューラを実装しています。私は理解できない深刻な問題を抱えており、私のコースの TA は理解していません。また、このプロジェクトの締め切りに間に合わなかったので、今私を助けても追加ポイントは得られませんが、知りたいです。なぜ私は次のような行動をとっています...
まず、これは私がxv6 用に変更している元のスケジューラです(比較のために - これは私の実装ではありません)。
// Per-CPU process scheduler.
// Each CPU calls scheduler() after setting itself up.
// Scheduler never returns. It loops, doing:
// - choose a process to run
// - swtch to start running that process
// - eventually that process transfers control
// via swtch back to the scheduler.
void
scheduler(void)
{
struct proc *p;
for(;;){
// Enable interrupts on this processor.
sti();
// Loop over process table looking for process to run.
acquire(&ptable.lock);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p->state != RUNNABLE)
continue;
// Switch to chosen process. It is the process's job
// to release ptable.lock and then reacquire it
// before jumping back to us.
proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&cpu->scheduler, proc->context);
switchkvm();
// Process is done running for now.
// It should have changed its p->state before coming back.
proc = 0;
}
release(&ptable.lock);
}
}
新しいスケジューラのアイデアは次のとおりです。ptable 内に proc 構造体で満たされた配列があります。この proc 配列でこれらの各要素を 'p' と呼び、基本情報 (持っている「チケット」の数や状態など) を保持します。1 つのタイム スライスですべての優先度の高い (HP) p を実行してから、それらの優先度を低に変更する必要があります。HP proc がない場合、「ランダムに」LP proc を選択し、それを 2 つのタイム スライスで実行します。私のアルゴリズムは次のとおりです。
scheduler()
for(;;) //scheduler NEVER completes
//information gathering
for (entire proc array) //goes over it once
gather how many HP and LP procs
count total HP and LP tickets in each proc (for lottery)
if #HP > 1 //randomly choose a HP proc
hold HP lottery, run one HP proc //afterwards,
int rand = random() % num_HP_tickets
for (entire array)
curr_index_of_tickets += p->num_tickets;
if (curr_index_of_tickets >= rand) //we found the right p!
run p for one time slice
else if #HP == 1
find and run the one HP proc
else if #HP < 1 //then no HP procs! Time to run LP
if #LP > 1
hold LP lottery, run one LP proc for two time slices, similar to above
else if #LP == 1
find the LP proc, run it
ここに問題があります... 私の proc は常に 0 に等しいように見えます。p に入れられた情報を見たことがない、p から proc 情報を収集していないなどです。理由はわかりません。
私は大量の出力ステートメントでテストしました。その出力を最初にここに投稿します。
entered scheduler
entered INFORMATION loop: iteration 0
Proc is 0
Proc is 0 even after proc gets p from for loop
Information 0: found 0 HP procs
Information 0: found 0 LP procs
Num HP: 0
Num LP: 0
Num HP Tickets: 0
Num LP Tickets: 0
This concludes loop #: 0
entered INFORMATION loop: 1
Proc is 0
entered INFORMATION loop: 2
Proc is 0
entered INFORMATION loop: 3
Proc is 0
etc.....
繰り返しますが、なぜこれが機能しないのかわかりません...複数のエラーがあると確信しており、どこで問題が発生しているかを確認するためだけに大量のステートメントを出力しています。これにはかなりのデバッグ作業も必要なので、誰かが答えを持っているかどうかについて私はあまり楽観的ではありません...その目的のために、これらの警告とともに、ここに私のスケジューラ関数全体を示します。長々とすみません…
void
scheduler(void)
{
struct proc *p;
for(;;){
//TODO: Remove statement
cprintf("entered scheduler\n");
// Enable interrupts on this processor.
sti();
// Loop over process table looking for process to run.
acquire(&ptable.lock);
//keeps track of number of procs (to be used for lottery RNG)
int num_LP_t = 0;
int num_HP_t = 0;
int num_HP = 0;
int num_LP = 0;
int rand = 0;
int curr_tickets = 0;
//goes through once to complete information gathering for HP and LP queue
//TODO: remove i - for testing only
int i = -1;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
i++;
//TODO: Remove statement
cprintf("entered INFORMATION loop: %d\n", i);
if (proc == 0) cprintf("Proc is 0\n");
if(p->state != RUNNABLE)
continue;
// Switch to chosen process. It is the process's job
// to release ptable.lock and then reacquire it
// before jumping back to us.
//TODO: uncomment? proc = p;
if (proc == 0) cprintf("Proc is 0 even after proc gets p in INFORMATION LOOP\n");
cprintf("Information %d: found %d HP procs\n", i, num_HP);
cprintf("Information %d: found %d LP procs\n", i, num_LP);
cprintf("Num HP: %d\n", num_HP);
cprintf("Num LP: %d\n", num_LP);
cprintf("Num HP Tickets: %d\n", num_HP_t);
cprintf("Num LP Tickets: %d\n", num_LP_t);
cprintf("This concludes loop #: %d\n", i);
if (p->priority_level == 1){
num_HP++;
num_HP_t += p->num_tickets;
}
if (p->priority_level == 0){
num_LP++;
num_LP_t += p->num_tickets;
}
}//end information loop
cprintf("Begin HP Queue:\n");
if (num_HP > 1){
cprintf("HP Queue had: %d procs to run\n", num_HP);
rand = random() % num_HP_t;
cprintf("We choose our random to be: %d\n", rand);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if (p->state != RUNNABLE) continue;
//TODO: uncomment? proc = p;
if (proc == 0) cprintf("Proc is 0 even after setting proc = p in HP queue\n");
if (p->priority_level == 1){
cprintf("Found a HP Proc while searching for rand, currently at: %d\n", curr_tickets);
curr_tickets += p->num_tickets;
if (curr_tickets >= rand){
if (proc == 0)
cprintf("proc is 0 while in HP queue 1\n");
//proc = p;
switchuvm(p);
p->state = RUNNING;
/*cprintf("Proc Info:");
cprintf("uint sz: %d", proc->sz);
cprintf("enum procstate state: %s", proc->state);
cprintf("volatile int pid: %d", proc->pid);
cprintf("int killed: %d", proc->killed);
cprintf("int priority_level: %d", proc->priority_level);*/
swtch(&cpu->scheduler, proc->context);
switchkvm();
if (p->state == RUNNABLE){
cprintf("HP process still runnable after 1 TS.\nHere is the updated information\n");
p->priority_level = 0;
num_HP--;
num_LP++;
num_HP_t -= p->num_tickets;
num_LP_t += p->num_tickets;
cprintf("Num HP: %d\n", num_HP);
cprintf("Num LP: %d\n", num_LP);
cprintf("Num HP Tickets: %d\n", num_HP_t);
cprintf("Num LP Tickets: %d\n", num_LP_t);
}
}
}
}
}
else if (num_HP == 1){
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if (p->state != RUNNABLE) continue;
//TODO: Uncomment? proc = p;
if (proc == 0) cprintf("Proc is 0 even after setting proc = p in HP == 1 queue\n");
if (p->priority_level == 1){
//proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&cpu->scheduler, proc->context);
switchkvm();
if (p->state == RUNNABLE){
p->priority_level = 0;
num_HP--;
num_LP++;
num_HP_t -= p->num_tickets;
num_LP_t += p->num_tickets;
}
}
}
}//end else num_HP = 1
else if (num_HP < 1){
if (num_LP > 1){
rand = random() % num_LP_t;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if (p->state != RUNNABLE) continue;
//TODO: uncomment? proc = p;
if (proc == 0) cprintf("Proc is 0 even after setting proc = p in LP > 1 queue\n");
if (p->priority_level == 0){
curr_tickets += p->num_tickets;
if (curr_tickets >= rand) {
//proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&cpu->scheduler, proc->context);
switchkvm();
if (p->state != RUNNABLE){
num_LP--;
num_LP_t -= p->num_tickets;
}
}
}
}
}
else if (num_LP == 1){
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if (p->state != RUNNABLE) continue;
//TODO: Uncomment? proc = p;
if (proc == 0) cprintf("Proc is 0 even after setting proc = p in LP == 1 queue\n");
if (p->priority_level == 0){
//proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&cpu->scheduler, proc->context);
switchkvm();
if (p->state != RUNNABLE){
num_LP_t -= p->num_tickets;
}
}
}
}
}//end lp
proc = 0;
release(&ptable.lock);
}//end outer for loop (;;)
}// end scheduler