Readings

The OSTEP book covers scheduling in these sections:

• 7. Scheduling: Introduction
• 8. Scheduling: The Multi-Level Feedback Queue
• 9. Scheduling: Proportional Share (Lottery Scheduling)
• 10. Multiprocessor Scheduling

These provide a lot more detail on several of the scheduling policies we discuss in class, as well as several policies we didn't cover in class. You are not expected to know details of other scheduling policies beyond what we discuss in class and what you explore in PS3, but you should find these sections well worth reading.

The Shortest Job First and Shortest Time-to-Completion First policies described in Section 7 are similar to the SRPT policy you are implementing for PS3 Problem 5 (you should consider which one of these is closer to what you should do for PS3).

Scheduling Recap

When is planned scheduling used?

What is a hard real-time system?

Scheduling Strategies

First Come, First Served (FIFO): processes run to completion, in the order they are started.

Round-Robin: each process gets to run for a given time slice (or until it finishes or is blocked).

What are the advantages and disadvantages of Round-Robin scheduling compred to First Come, First Served?

Exploring Processes and Priorities

What does the priority of a process mean?

Try this: ps -w -e -o pri,pid,pcpu,vsz,cputime,command | sort -n -r --key=5 | sort --stable -n --key=1

Preemptive Priority Scheduling

• Always run the highest priority process that is ready to run
• Round-robin schedule among equally high, ready to run, highest-priority processes

What are the advantages and disadvantages of preemptive priority scheduling?

What really happened on Mars? Glen Reeve's account

Is priority inheritance a good solution?

Lottery Scheduling

Carl Waldspurger's PhD dissertation: Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management (If you are considering going to grad school and want a good model of what a PhD involves, this is the best example I know of a dissertation worth reading.)

Stride Scheduling

What are the advantages of stride scheduling over lottery scheduling?

comments powered by Disqus

goto fail;

Apple's SSL implementation (extracted from sslKeyExchange.c): (original indentation and whitespace preserved for lack-of-clarity)

static OSStatus
SSLVerifySignedServerKeyExchange(SSLContext *ctx, bool isRsa, SSLBuffer signedParams,
                                 uint8_t *signature, UInt16 signatureLen)
{
    OSStatus        err;
    SSLBuffer       hashOut, hashCtx, clientRandom, serverRandom;
    uint8_t         hashes[SSL_SHA1_DIGEST_LEN + SSL_MD5_DIGEST_LEN];
    SSLBuffer       signedHashes;
    uint8_t         *dataToSign;
    size_t          dataToSignLen;

    signedHashes.data = 0;
    hashCtx.data = 0;

    clientRandom.data = ctx->clientRandom;
    clientRandom.length = SSL_CLIENT_SRVR_RAND_SIZE;
    serverRandom.data = ctx->serverRandom;
    serverRandom.length = SSL_CLIENT_SRVR_RAND_SIZE;

    ...
    hashOut.data = hashes + SSL_MD5_DIGEST_LEN;
    hashOut.length = SSL_SHA1_DIGEST_LEN;
    if ((err = SSLFreeBuffer(&hashCtx)) != 0)
        goto fail;

    if ((err = ReadyHash(&SSLHashSHA1, &hashCtx)) != 0)
        goto fail;
    if ((err = SSLHashSHA1.update(&hashCtx, &clientRandom)) != 0)
        goto fail;
    if ((err = SSLHashSHA1.update(&hashCtx, &serverRandom)) != 0)
        goto fail;
    if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
        goto fail;
        goto fail;
    if ((err = SSLHashSHA1.final(&hashCtx, &hashOut)) != 0)
        goto fail;

    err = sslRawVerify(ctx,
                       ctx->peerPubKey,
                       dataToSign,              /* plaintext */
                       dataToSignLen,           /* plaintext length */
                       signature,
                       signatureLen);
    if(err) {
        sslErrorLog("SSLDecodeSignedServerKeyExchange: sslRawVerify "
                    "returned %d\n", (int)err);
        goto fail;
    }

fail:
    SSLFreeBuffer(&signedHashes);
    SSLFreeBuffer(&hashCtx);
    return err;

}

Test your SSL implementation Apple's Security Post Apple's SSL/TLS Bug (Adam Langley)

What are differences between Rust and C that make this time of fail much less likely?

What software development practices should be followed for any production code to greatly reduce the chances of these types of mistakes not being caught?

Theory Excursion

How hard is it to detect unreachable code in theory?

What should compilers do when desired decision procedures are undecidable?

Catch up on your theory with Dori-Mic and the Universal Machine!

Sharing across Tasks

unsafe2.rs

static mut count: uint = 0; 

fn update_count() { unsafe { count += 1; } }

fn main() {
    for _ in range(0u, 10) {
        spawn(proc() {
           for _ in range(0u, 1000) {
              update_count();
           }
        });
    }
    println!("Count: {:}", unsafe { count });
}

Assembly code produced by rustc -S unsafe2.rs: unsafe2.s

    .section    __TEXT,__text,regular,pure_instructions
    .align  4, 0x90
__ZN12update_count19h86817af0b0797e96al4v0.0E:
    .cfi_startproc
    cmpq    %gs:816, %rsp
    ja  LBB0_0
    movabsq $16, %r10
    movabsq $0, %r11
    callq   ___morestack
    ret
LBB0_0:
    pushq   %rbp
Ltmp2:
    .cfi_def_cfa_offset 16
Ltmp3:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp4:
    .cfi_def_cfa_register %rbp
    pushq   %rax
    movq    __ZN5count19hc6afed277fb1b6c3ah4v0.0E(%rip), %rax
    addq    $1, %rax
    movq    %rax, __ZN5count19hc6afed277fb1b6c3ah4v0.0E(%rip)
    movq    %rdi, -8(%rbp)
    addq    $8, %rsp
    popq    %rbp
    ret
    .cfi_endproc
...

Where is the data race?

RWArc - automatically reference-counter storage protected by a reader-writer lock

Why is it useful to have separate locks for reading and writing?

extern mod extra; 
use extra::arc::RWArc;

fn update_count(counter: RWArc<int>) {
    counter.write(|count: &mut int| { *count += 1; });
}

fn main() {
    let counter: RWArc<int> = RWArc::new(0);

    for _ in range(0, 10) {
        let ccounter = counter.clone(); // need the clone - this moves counter
        spawn(proc() {
           for _ in range(0, 1000) {
              update_count(ccounter.clone()); // shouldn't be necessary!?
           }
        });
    }

    counter.read(|count| {
       println!("Count: {:d}", *count);
    });

}

Why is the printed count still not 10000?

Scheduling

What are the two main decisions the supervisor needs to make on each kernel timer interrupt?

Max Ehrmann's "Desiderata":

Go placidly amid the noise and haste, and remember what peace there may be in silence. As far as possible without surrender be on good terms with all persons. Speak your truth quietly and clearly; and listen to others, even the dull and the ignorant; they too have their story. Avoid loud and aggressive persons, they are vexations to the spirit... Exercise caution in your business affairs; for the world is full of trickery... And whether or not it is clear to you, no doubt the universe is unfolding as it should... whatever your labors and aspirations, in the noisy confusion of life keep peace with your soul. With all its sham, drudgery, and broken dreams, it is still a beautiful world. Be cheerful. Strive to be happy.

Why is there a fundamental tradeoff between maximizing resource utilization and fairness in scheduling?

comments powered by Disqus