Threads

Lots of kernel resources used to create multiple processes. …

Processes are not the right choice for a network server because:

• they are running the same program (asynchronously) with the same privileges, code and data (recall its duplicate of the parent address space), and open files, so the only difference between the processes are the CPU registers, program counter, and stack pointer.
• It’s a lot of overhead, so we want a lighter-weight process. Don’t duplicate the things that will be the same

Threads are An abstraction of the PC, CPU registers, and call stack, essentially a “virtual CPU.”

• Threads run within a process, which provides the address space user identity and privileges, and files + I/O resource (table of open file).
• Multiple stacks and registers that share the same code, data, and files.

Previously, when the OS kernel makes a scheduling decision it picks a process to run, but Now with threads, the OS needs to pick a thread to run.

• Data structure: thread control block (TCB). Very light weight compared to a process.

If there are multiple threads are running and then there’s an interrupt:

• if it’s single core, then it interrupts whatever thread is running
• If it’s multi core, then many threads may be running at once. There’s many interrupts for each CPU core, so it would interrupt whatever is running on that CPU core.

When you have an OS running on multi core CPU, then the core has access to any process and any thread.

Utility of threads: lightweight mechanism for concurrency (do many tasks at the same time e.g., communicate with clients) / parallelism (take advantage of multiple CPU cores):

Cost of threads: all threads run in the same address space / have full access to all Memory in the address space.

• access to shared data without synchronization leads to undesirable outcomes, and synchronization is difficult
• A bug in a thread that is executed can affect other threads. Bugs can be challenging to identify and fix (race conditions, deadlocks)
• Threads are not good for fault tolerant system. You would want separate address spaces for different tasks

To create a thread:

• create a data structure to let the threads know about the resources it will be working with.
• Then create a thread and till it what function to run and give it access to the object that tells it what resources it can access.
• In a network server: each thread will handle one client. Delay in one thread will not affect another one since the CPU schedules them asynchronously.
• To wait for the child to finish, the parent will be put into a wait queue and will be woken up When done.

To create thread in the kernel:

1. Create TCB for new thread
2. Allocate kernel stack
3. Prepare stack (push data onto thread stack if necessary)
4. Initialize thread context (initial value of the CPU registers)
   1. Stack pointer points to the appropriate location in the thread’s satck
   2. PC points to the first instruction
   3. If the thread is executing in user mode, we need some “trampoline” code to arrange for thee transfer fo control to a user space code address before it is executed in the first time
5. Add TCB in the ready queue, making it available for scheduling

What values are initially on the stack and what values are initially in CPU registers depends the calling convention the compiler is using.

• 32 bit x86 arguments are passed on the stack.

To create a thread in a user process:

• makes a system call to request that the kernel create a kernel thread
• …

Kernel vs user threads:

• Assume every user thread has a matching kernel thread (this is a design choice called 1:1 model) but some kernel threads aren’t associated with a process, they are called “kernel only” threads and they never execute user-modes. They perform housekeeping tasks.
• Every kernel thread has a kernel stack within the kernel address space.
• Every user-mode thread has a user-mode stack within its process address space.’

In 1:1 threading, each user thread is supported by a single kernel thread.

• scheduling of user threads is therefore handled by the kernel scheduler
• What ever capability the kernel scheduler has (like preemption, maintaining fairness, scheduling workloads in a way that minimizes latency,etc ), now pertains to user threads.
• This style of thread is known as a “lightweight process”
• Pros: simple, user threads are “seen” by the kernel, so they can be scheduled on any CPU core (so they can be used for parallelism)
• Cons: thread context switch requires transition into and out of the kernel, synchronization operations require kernel support, kernel resources (TCB, kernel stack) needed for every thread (kernel level resource cost)

Another module is user-level threading.

• OS kernel has no concept of threads, they are entirely implemented in the user space.
• Thread functions thread_create(), etc are just library functions. Scheduling can be cooperative or preemptive (preemption requires a mechanism for asynchronous interruption like SIGALARM signal, analog interval timer to provide regular interrupts).
• Pros: very lightweight (no kernel resources, kernel is not required for scheduling or synchronization) and context switch cost approaches cost of functions all (ten of instructions rather than hundreds)
• Cons: kernel can’t see the threads, so they can’t take advantage of multiple CPUs. What happens if a thread makes a blocking system call.
  • How would the library detect this and schedule a different thread
  • How would the thread library know when the blocking operations finished
• Could the thread library cooperate with the kernel?

M:n threading: multiple user threads (m) onto some number of kernel threads (n)

• Pros: only need a fixed number of kernel threads (one per CPU core)
• Cons: blocking system still must be dealt with (if a thread calls reads, then you don’t want that kernel thread to be blocked), user threads could run on any kernel thread
  • Scheduler data is accessed by multiple LWPs (lightweight process), must be synchronized appropriately
• Solerious OS does this, at the cost of serious complication

Implementing user-level thread

• types
  • timer event that is asynchronous with the thread is preemptive.
  • cooperative scheduling: threads voluntarily give up the CPU with yield().

yield(): gives up CPU to another thread

• i.e., context switches to another thread
• yield to return means another thread called yield.

Coroutines: similar to cooperative thread. Main difference is that the yield() function takes an argument specifying which coroutine to transfer control to.

• the application determines which thread to schedule next.
• The developer has to think about the live-ness of the program.

Preemptive thread scheduling:

• non-preemptive threads have to voluntarily give up CPU.
  • Long running threads will take over the machine
  • Only voluntarily calls to yield, sleep, or finish cause a context switch
• Relies on the system to maintain the live-ness of the program.
  • But now threads need to be more careful about synchronization
• Causes an involuntary context switch
  • Need to regain control of processor asynchronously
  • Use timer interrupt, and the handler forces the current thread to “call” yield.

... catch up mechanics of thread switching in pintos

Conclusion

Priority scheduling: associate a numeric priority with each process (e.g, in unix/BSD, smaller number means higher priority or in Pintos, smaller number means lower priority). Give the CPU the process with highest priority (like airline check-in for first class passengers) and this can be done preemptively or non-preemptively. This can also implement SJF, = priority =1 / (expected CPU burst)

• problem: starvation, low priority jobs can wait indefinitely
  • solution: "age" process
    • Increase priority as a function of waiting time
    • decrease priority as a function of CPU consumption

Priority inversion: caveat from using priority scheduling w synch primitives

• This priority scheduling rule could cause a priority inversion problem: 1) always pick the highest-priority thread 2) unless a lower-priority thread is holding a resource the highest-priority thread wants to get.
  • imagine two task, H (high priority) and L (low priority).
    • L acquires lock k
• Caused the famous Mars PathFinder failure in 1997 where a low-priority data gathering and a high priority communications task prevented the critical bus management task from running
• Solution: "donate" our priority if we get blocked.
  • whenever a high-priority task has to wait for some shared resource that is held by an executing a low priority task, that task should be temporarily assigned the priority of the highest waiting priority task for the duration of its use of the shared resource. Once it is released, it continues at its original priority
  • since the low-priority task is temporarily boosted, it keeps the medium priority task from pre-empting the (originally) low priority task.
  • Example: ...
  • Nested priority donation is extra credit.

Multilevel queue scheduling (MLFQ). (High to low) processes of type

1. system
2. interactive
3. interactive editing
4. batch
5. student

• How is this different from just priority queue.
  • it captures the dynamic nature
  • tasks of similar run time will end up being in the same queue
• Achieves
  • goal 1: optimize job turnaround time for batch jobs
  • goal 2: minimize response time for "interactive" jobs
• challenge: no prior knowledge of what type a job is, what is its next burst, etc. Can the job tell us its "niceness"
  • we could change its priority based on its past behavior (history "feedback")
• Attempt:
  • rule A: processes start at the top priority