Scheduler - wtrr59/Xv6-Scheduler GitHub Wiki

STRIDE & MLFQ SCHEDULING

How to Implement

Scheduling Procedure in Xv6

  1. Pick a runnable state process in ptable.proc
  2. Context switch and run the process
  3. Return to the cpu scheduler and repeat above procedure

๋ณธ๋ฌธ์—์„œ๋Š” ์ฒซ๋ฒˆ์งธ ์ ˆ์ฐจ๋ฅผ ์ˆ˜์ •ํ•  ๊ฒƒ์ด๋‹ค.

Main Concept

img1

Scheduling Procedure in STRIDE & MLFQ algorithm

  1. Check that a runnable process is exist in table.proc
    Pick the list or process which has min pass
    If the list is selected, pick a process corresponding each rules in the list
  2. Context switch and run the process
  3. Return to the cpu scheduler, repeat above procedure

Stride Scheduler ๋ถ€๋ถ„์—์„œ๋Š” ptable.proc ๋‚ด์— Runnable process๊ฐ€ ์กด์žฌํ•˜๋Š”์ง€ ํ™•์ธํ•˜๊ณ  ์—†์„ ๊ฒฝ์šฐ ๋ฐ˜๋ณต๋ฌธ์„ ๊ณ„์† ๋Œ๊ธฐ๋งŒ ํ•œ๋‹ค.

Stride List ์™€ MLFQ List ๊ทธ๋ฆฌ๊ณ  ๋ชจ๋“  Share process๋Š” ๊ฐ๊ฐ์˜ Pass๋ฅผ ๊ฐ–๊ณ ์žˆ๋‹ค.

๋”ฐ๋ผ์„œ ์…‹ ์ค‘์— ๊ฐ€์žฅ Pass๊ฐ€ ๋‚ฎ์€ ๊ฒƒ์„ ์ฐพ์•„ ์–ด๋–ค ํ”„๋กœ์„ธ์Šค๋ฅผ ์„ ํƒํ• ์ง€ ๊ฒฐ์ •ํ•œ๋‹ค.

.

Proc Structure

struct proc {
...
  union sched_data data;
  enum schedstate sched_state;  // Scheduling state
};

union sched_data{
    struct share_data share;
    struct mlfq_data mlfq;
    struct stride_data stride;
};

struct stride_data {
    int swtch; // Default process์˜ ์‹คํ–‰ ์—ฌ๋ถ€
};
struct share_data {
    double pass;
    double strd;
    int share; // cpu_share๋ฅผ ํ†ตํ•ด ํ• ๋‹นํ•œ ์ ์œ ์œจ
};
struct mlfq_data {
    int level; // MLFQ ๋‚ด์˜ level
    int exec_count; // Process ์‹คํ–‰ ํšŸ์ˆ˜
};

Proc ๊ตฌ์กฐ์ฒด์—๋Š” Stride ์Šค์ผ€์ค„๋ง์„ ์œ„ํ•œ union๊ณผ ํ•ด๋‹น Process๊ฐ€ ์–ด๋–ค Scheduling์„ ์ ์šฉํ•ด์•ผํ•˜๋Š”์ง€ ๊ตฌ๋ถ„ํ•˜๋Š” enum์ด ์ถ”๊ฐ€๋˜์—ˆ๋‹ค.
๊ณต์šฉ์ฒด๋ฅผ ์‚ฌ์šฉํ•จ์œผ๋กœ์จ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์„ ์ตœ์ ํ™” ํ•˜์˜€๋‹ค.

.

Linked List Data Structure

img2

//proc.c
struct proc_list proc_l[NPROC];

...

//proc.h

struct proc_list{
    struct proc *p;
    struct proc_list *next;
    int use;
};

struct proc_header{
    int proc_num;
    struct proc_list *start;
    struct proc_list *end;
};

.

Stride List ์™€ MLFQ List ๋ชจ๋‘ Slab ์„ ํ™œ์šฉํ•œ Linked List ๋กœ ๊ตฌ์„ฑ๋˜์žˆ๋‹ค.
Xv6๊ฐ€ ์ƒ์„ฑํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ํ”„๋กœ์„ธ์Šค์˜ ๊ฐœ์ˆ˜ ๋งŒํผ ํ• ๋‹นํ•˜๋ฉฐ proc_list์˜ use ๋ณ€์ˆ˜๋ฅผ ํ†ตํ•ด ์‚ฌ์šฉ ์ค‘์ธ์ง€ ์•„๋‹Œ์ง€ ํŒ๋‹จํ•œ๋‹ค.
๋˜ํ•œ ์•ž์— ํ—ค๋”์˜ proc_num์„ ํ†ตํ•ด List ๋’ค์— ๋ช‡ ๊ฐœ์˜ node๊ฐ€ ์žˆ๋Š”์ง€ ๋จผ์ € ํŒ๋‹จํ•  ์ˆ˜ ์žˆ๋‹ค.

.

Stride structure

Stride ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ธฐ๋ณธ์ ์ธ ์ž‘๋™ ๋ฐฉ์‹์€ ์ง€๋ถ„์œจ(ticket)์— ๋”ฐ๋ฅธ Stride๋ฅผ ๊ฐ์ž ๊ฐ–๊ณ  ์ง€๋‚˜์˜จ Pass๋ฅผ ํ™•์ธ ํ•จ์œผ๋กœ์จ ์šฐ์„ ์ˆœ์œ„๋ฅผ ๊ฐ€๋ฅด๊ฒŒ ๋˜์–ด์žˆ๋‹ค.
๊ทธ๋Ÿฌ๋‚˜ ๋ณธ๋ฌธ์—์„œ๋Š” ์•ฝ๊ฐ„์˜ ๋ณ€ํ˜•์„ ์ค„ ๊ฒƒ์ด๋‹ค.

Default Case

cpu_share ๋˜๋Š” run_MLFQ๋ฅผ ์‹คํ–‰ํ•˜์ง€ ์•Š์•˜๋‹ค๋ฉด Default stride๋ฅผ ๊ฐ–๊ฒŒ๋œ๋‹ค.
Default case์™€ ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” Stride๊ฐ€ ์ง€๋ถ„์œจ / Default Stride์˜ ๊ฐœ์ˆ˜์ด๋‹ค.
๊ทธ๋Ÿฌ๋ฏ€๋กœ Default process ๋ผ๋ฆฌ๋Š” RR๋ฐฉ์‹์œผ๋กœ ๋Œ์•„๊ฐ€๊ฒŒ๋œ๋‹ค.

๊ตณ์ด RR ๋ฐฉ์‹์„ ์ฑ„ํƒํ•˜๊ฒŒ๋œ ์ด์œ ๋Š” ๋งŒ์•ฝ default stride๊ฐ€ ๋ชจ๋‘๊ฐ€ ํ•œ ๋ฒˆ์”ฉ ๋Œ์ง€์•Š์•˜์„ ๋•Œ (์„œ๋กœ์˜ Stride์˜ ์ฐจ์ด๊ฐ€ ๋ฐœ์ƒํ–ˆ์„ ๋•Œ)
์ƒˆ๋กœ์šด Default Stride๊ฐ€ ๋“ค์–ด์˜ค๊ฒŒ ๋˜๋ฉด ์ƒˆ๋กœ์šด Stride๋กœ Pass๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๊ฒŒ๋œ๋‹ค.
๊ฒฐ๊ตญ์—” pass์˜ ์ฐจ์ด๊ฐ€ ๋ฐœ์ƒํ•˜๊ณ  ์ด๊ฒƒ์ด ์ปค์ง€๊ฒŒ ๋˜๋ฉด ์‹คํ–‰ ํšŸ์ˆ˜์˜ ์ฐจ์ด๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ ํ”„๋กœ์„ธ์Šค๋Š” ์ž์‹ ๋งŒ์˜ swtich๋ฅผ ๊ฐ–๊ฒŒ๋˜๊ณ 
STRIDE_struct์˜ ๊ตฌ์กฐ์ฒด์— ์žˆ๋Š” switch num๊ณผ ๋น„๊ต๋ฅผ ํ†ตํ•ด ์‹คํ–‰๋œ process์ธ์ง€ ํ™•์ธํ•œ๋‹ค.

๊ทธ๋Ÿฌ๋ฏ€๋กœ Default Stride๋Š” ๊ณต์œ  Pass๋ฅผ ๊ฐ€์ง€๋ฏ€๋กœ ๋„์ค‘์— ์ƒˆ๋กœ์šด Process๊ฐ€ ๋“ค์–ด์™€๋„ Pass๊ฐ€ ํ‹€์–ด์ง€๋Š” ์ผ์ด ์—†์œผ๋ฉฐ
์—…๋ฐ์ดํŠธ ๋˜ํ•œ ์ƒˆ๋กœ์šด ํ”„๋กœ์„ธ์Šค๋ฅผ ํฌํ•จํ•œ Stride๋กœ ์—…๋ฐ์ดํŠธ๋œ๋‹ค.

struct STRIDE_struct {
    struct proc_header list;
    double pass;
    double stride;
    int switch_num;
};

SHARE case

cpu_share๋ฅผ ์š”์ฒญํ•˜๊ฒŒ๋  ๊ฒฝ์šฐ Stride List์—์„œ ๋ฒ—์–ด๋‚˜ ์ž๊ธฐ๋งŒ์˜ Stride, Pass, Share(์ง€๋ถ„์œจ)์„ ๊ฐ–๊ฒŒ๋˜๋ฉฐ
Stride ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋”ฐ๋ผ ์„ ํƒ๋œ๋‹ค.

.

MLFQ structure

struct MLFQ_struct {
    struct proc_header first;
    struct proc_header second;
    struct proc_header third;
    int boosting_period;
    double pass;
};

MLFQ๋Š” 3๊ฐœ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ–๊ณ ์žˆ์œผ๋ฉฐ ๊ฐ๊ฐ์˜ ํ—ค๋”์— ์žˆ๋Š” proc_num์„ ํ†ตํ•ด ์‹คํ–‰ํ•  ํ”„๋กœ์„ธ์Šค๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.
์ƒˆ๋กœ ์ƒ์„ฑ๋ผ์„œ ๋“ค์–ด์˜จ ํ”„๋กœ์„ธ์Šค๋Š” Highest ๋ฆฌ์ŠคํŠธ์˜ ์ œ์ผ ๋’ค์— ์ถ”๊ฐ€๋˜๋ฉฐ ์‹คํ–‰์€ ๊ฐ€์žฅ ์•ž์—์žˆ๋Š” Process๊ฐ€ ์‹คํ–‰๋œ๋‹ค.
time quantum ์„ ๋‹ค ์‹คํ–‰ํ–ˆ์„ ๊ฒฝ์šฐ List์˜ ๊ฐ€์žฅ ๋’ค๋กœ ๊ฐ€๊ฒŒ๋œ๋‹ค.
time allotment์— ๋„๋‹ฌํ–ˆ์„ ๊ฒฝ์šฐ ๋‹ค์Œ ํ์˜ ์ œ์ผ ๋’ค๋กœ ๊ฐ€๊ฒŒ๋œ๋‹ค.

๋˜ํ•œ ์ง€๋ถ„์œจ์„ 20%๋กœ ๊ณ ์ •ํ•ด์คŒ์œผ๋กœ์จ Stride์— ๋”ฐ๋ฅธ ์„ ํƒ์„ ๋ฐ›๊ฒŒ๋œ๋‹ค.

Result

CNT img3

TICK
img4

Xv6์˜ 1tick ๋‹น ์‹œ๊ฐ„๊ณผ Test program์˜ 1cnt ๋‹น ์‹œ๊ฐ„์ด ์ผ์น˜ํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์œ„์™€๊ฐ™์€ ์ฐจ์ด๊ฐ€ ๋ฐœ์ƒํ•˜๊ฒŒ๋œ๋‹ค.