מתזמן ומדיניות זמן מעבד

מוכן לריצה ועדיין מחכה

נניח ששני תהליכונים מסוגלים להתקדם, אבל שניהם מוגבלים לאותו מעבד. הקרנל צריך לבחור מי ירוץ עכשיו, לכמה זמן ומתי ישנה את הבחירה. משימה שממתינה לנתון אינה מתחרה באותו אופן כמו משימה שכבר מוכנה לרוץ. לכן נפריד בין אירוע שמעיר משימה לבין אירוע שבו היא באמת מקבלת זמן מעבד.

תורי הריצה הם מבני נתונים של המתזמן שמארגנים משימות וישויות תזמון לפי המחלקה והמצב. במערכת מרובת מעבדים קיימים גם שיקולי איזון, זיקה וטופולוגיה. עצם קיומו של מעבד פנוי במערכת אינו מבטיח שמשימה מסוימת רשאית לרוץ עליו, משום שמסכת הזיקה, קבוצת הבקרה ומדיניות אחרת יכולות לצמצם את האפשרויות.

הוגנות בזמן וירטואלי

התכנון ההיסטורי של CFS השתמש בזמן ריצה וירטואלי כדי לתאר כמה שירות קיבלה ישות ביחס למשקלה. ישות בעלת משקל גדול יותר צוברת זמן וירטואלי בקצב שונה עבור אותו זמן פיזי. הרעיון מאפשר להשוות שירות שניתן למשימות בעלות משקלים שונים, במקום לספור רק מספר החלפות הקשר.

בעץ הייחוס שלנו מסלול ההוגנות משתמש בבחירה ממשפחת EEVDF. הבחירה משלבת זכאות לפי הפער בין השירות שהישות קיבלה לבין חלקה, ומועד וירטואלי שמסייע להחליט בין הישויות הזכאיות. ישות שקיבלה יותר מחלקה אינה נבחרת רק מפני שמועד כלשהו שלה קטן. ההבחנה בין זכאות לבין סדר בין זכאיות חשובה להבנת האלגוריתם.

נבחן דוגמה מושגית עם שלוש ישויות. לראשונה פער חיובי ומועד וירטואלי מאה, לשנייה פער שלילי ומועד חמישים, ולשלישית פער חיובי ומועד שמונים. הבחירה בין הזכאיות תעדיף את השלישית על הראשונה, בעוד השנייה אינה הופכת לזכאית רק בגלל המועד המוקדם. המספרים הם מודל הסבר ואינם פלט של קרנל שנמדד.

קריאה של המימוש שנבנה

נחפש בעץ v6.12 את בחירת הישות ואת בדיקת הזכאות. השמות עדיין כוללים חלק מהמינוח ההיסטורי, ולכן שם קובץ או מבנה לבדו אינו הוכחה שהאלגוריתם נשאר זהה לגרסה ישנה. נקרא את השימוש בשדות ולא נסתפק בזיהוי ראשי תיבות.

rg -n 'pick_eevdf|entity_eligible|update_deadline|vlag' kernel/sched/fair.c
rg -n 'try_to_wake_up|context_switch|__schedule' kernel/sched/core.c

משימה שמתעוררת צריכה לעבור ממודל ההמתנה למודל הריצה, והמערכת עשויה לבקש החלפת משימה לפי סדרי העדיפויות וההקשר. השהיה קצרה אינה אמורה לאפשר למשימה למחוק באופן שרירותי את חשבונאות השירות שלה. בעץ שנבחר נבדוק גם את הטיפול בישויות ישנות ובמצב ההוצאה הדחויה, במקום להשליך כללים של גרסה אחרת.

ניסוי משקל בתוך מעבד אחד

נבנה תוכנית עם התלות libc = "0.2". היא בוחרת מעבד מתוך מסכת הזיקה המותרת, מצמצמת את עצמה אליו ויוצרת שני עובדים. אחד נשאר בעדיפות הרגילה והשני מוריד את עדיפותו באמצעות ערך נימוס גבוה יותר. הניסוי מיועד להתחלה בערך נימוס אפס ובמדיניות רגילה במכונת המעבדה.

use std::io;
use std::sync::{Arc, Barrier};
use std::time::{Duration, Instant};

fn cpu_seconds() -> io::Result<f64> {
    let mut time: libc::timespec = unsafe { std::mem::zeroed() };
    if unsafe { libc::clock_gettime(libc::CLOCK_THREAD_CPUTIME_ID, &mut time) } == -1 {
        return Err(io::Error::last_os_error());
    }
    Ok(time.tv_sec as f64 + time.tv_nsec as f64 / 1e9)
}

fn main() -> io::Result<()> {
    let mut allowed: libc::cpu_set_t = unsafe { std::mem::zeroed() };
    if unsafe { libc::sched_getaffinity(0, std::mem::size_of_val(&allowed), &mut allowed) } == -1 {
        return Err(io::Error::last_os_error());
    }
    let cpu = (0..libc::CPU_SETSIZE as usize)
        .find(|&cpu| unsafe { libc::CPU_ISSET(cpu, &allowed) })
        .ok_or_else(|| io::Error::other("no allowed CPU"))?;
    let mut one: libc::cpu_set_t = unsafe { std::mem::zeroed() };
    unsafe { libc::CPU_ZERO(&mut one); libc::CPU_SET(cpu, &mut one); }
    if unsafe { libc::sched_setaffinity(0, std::mem::size_of_val(&one), &one) } == -1 {
        return Err(io::Error::last_os_error());
    }
    println!("selected_cpu={cpu}");
    let barrier = Arc::new(Barrier::new(3));
    let mut workers = Vec::new();
    for nice in [0, 10] {
        let barrier = barrier.clone();
        workers.push(std::thread::spawn(move || -> io::Result<(i32, f64, u64)> {
            if unsafe { libc::setpriority(libc::PRIO_PROCESS, 0, nice) } == -1 {
                return Err(io::Error::last_os_error());
            }
            barrier.wait();
            let begin_cpu = cpu_seconds()?;
            let begin = Instant::now();
            let mut value = 1_u64;
            while begin.elapsed() < Duration::from_secs(2) {
                for _ in 0..10_000 {
                    value = std::hint::black_box(value.wrapping_mul(33).wrapping_add(1));
                }
            }
            Ok((nice, cpu_seconds()? - begin_cpu, value))
        }));
    }
    barrier.wait();
    for worker in workers {
        let (nice, seconds, value) = worker.join().unwrap()?;
        println!("nice={nice} cpu_seconds={seconds:.6} value={value}");
    }
    Ok(())
}

הזיקה עוברת לעובדים שנוצרו לאחר השינוי, ולכן הם מתחרים באותו מעבד. שינוי הנימוס מתבצע מתוך כל עובד ומשפיע על המשימה המתאימה בלינוקס. נמדוד זמן מעבד של כל עובד ולא רק מספר איטרציות, משום שהאחרון תלוי גם במהדר ובחומרה.

המחסום מניח ששינוי העדיפות הצליח בשני העובדים. לכן לפני הרצת הניסוי נוודא את תנאי ההתחלה, ובגרסת כלי כללית נחליף את ההנחה בפרוטוקול התחלה שמאפשר לדווח על כשל לפני המתנה. אם אחד העובדים חוזר מוקדם משגיאה לפני המחסום, האחרים יכולים להמתין לעד. זאת דוגמה לכך שגם כלי מדידה צריך חוזה כשל, ובתרגול נתקן אותו.

משקל אינו מכסה

ערך הנימוס משפיע על חלק יחסי בתחרות במחלקה הרגילה. הוא אינו מבטיח אחוז קבוע מזמן המכונה ואינו גבול קשיח שמונע ניצול של זמן פנוי. כאשר נסיר את המתחרה, המשימה בעלת המשקל הנמוך יכולה לקבל הרבה יותר זמן. לעומת זאת מכסת קבוצת בקרה יכולה לעצור אותה גם כאשר יש מעבד פנוי.

נרשום את קבוצת הבקרה, מדיניות התזמון ומסכת הזיקה של הניסוי. תחרות מחוץ לקבוצה או מגבלה מעליה יכולה לשנות את המספרים. שינוי יחס המשקלים בלי תיעוד ההקשר אינו מספיק כדי להאשים או לשבח את אלגוריתם התזמון.

מחלקות זמן אמת ומועדים

המדיניות SCHED_FIFO משתמשת בעדיפויות סטטיות ובכללי ריצה שונים מהמחלקה ההוגנת. המדיניות SCHED_RR מוסיפה סבב בין משימות מתאימות באותה עדיפות. משימה בעלת עדיפות גבוהה שאינה נחסמת יכולה לפגוע בהתקדמות משימות אחרות, ולכן ניסוי כזה דורש סביבת מעבדה ומגבלת זמן ומשאבים חיצונית מתאימה.

המדיניות SCHED_DEADLINE מתארת תקציב ריצה, מועד ותקופה, וכוללת מנגנוני קבלה ואכיפת תקציב. היא אינה פשוט ערך נימוס גבוה במיוחד. בקשה למדיניות יכולה להידחות בגלל הרשאות, תצורה או דרישות שאינן עומדות בתנאים. קבלת המדיניות אינה הוכחה שכל מערכת היישום תעמוד במועד כאשר היא תלויה בנעילה או בהתקן חיצוני.

הגדרות קדימות, תצורת השהיה של הקרנל, פסיקות וזמני קטעים שאינם ניתנים להשהיה משפיעים על זמן התגובה. נגדיר קודם מהו מועד שאנחנו רוצים לעמוד בו ואילו מקורות המתנה קיימים, ורק אחר כך נבחר מדיניות. העלאת עדיפות בלי הבנת גרף ההמתנה יכולה להשאיר את המשימה החשובה תלויה במשימה פחות חשובה.

ההבחנה בין המימוש ההיסטורי לבחירה החדשה מתועדת בתכנון ההוגנות ובתיאור הבחירה בגרסת הייחוס. ממשקי המדיניות מתוארים במדריך התזמון, אך שמות ותיאורים היסטוריים במדריך אינם מחליפים קריאה של עץ הקרנל המסוים שבנינו.