commit 51d6db529796db5216e0977d31eb09d4a23643bb
parent 25781bccecdc70d76fc412bc6f318fef1ef4dd5b
Author: Andrew Laack <andrew@laack.co>
Date: Tue, 5 May 2026 15:48:15 -0500
Some notes from OS course
Diffstat:
7 files changed, 207 insertions(+), 2 deletions(-)
diff --git a/docs/Hyperthreading.md b/docs/Hyperthreading.md
@@ -0,0 +1,15 @@
+# Hyperthreading
+
+**Source:** CS6200
+
+**Definition:** Hyperthreading is when a CPU has multiple sets of registers to allow for fast context switching between different execution contexts.
+
+## Details
+
+Despite having multiple sets of registers, the CPU can only execute one program at a time.
+
+Hyperthreading is also referred to as
+
+- Hardware multithreading
+- Chip Multithreading (CMT)
+- Simultaneous multithreading (SMT)
diff --git a/docs/OperatingSystems.md b/docs/OperatingSystems.md
@@ -53,3 +53,5 @@
- [POSIX](POSIX.md)
- [Interrupt](Interrupt.md)
- [Signal](Signal.md)
+- [Hyperthreading](Hyperthreading.md)
+- [TLB](TLB.md)
diff --git a/docs/Scheduler.md b/docs/Scheduler.md
@@ -13,3 +13,106 @@ If there is currently a process running the OS must preempt (interrupt and save
## Scheduler Optimization
If the scheduler runs frequently, it will both result in more cache misses, and spend more cycles on scheduling. This is because the scheduler takes ~the same amount of time to run regardless of timeslice (the amount of time allocated to a scheduled process).
+
+## Process
+
+Assuming there is some number of tasks in the ready queue, the scheduler will read some number of the tasks from the ready queue and schedule one to run on the CPU.
+
+## Dispatching Options
+
+### FCFS
+
+The choice to dispatch tasks immediately is simple and often referred to as FCFS (first come first serve) scheduling.
+
+Pros
+
+- Minimizes computation performed by scheduler
+- Easy to reason about
+ - Both from development side and usage side
+
+### SJF
+
+SJF (shortest job first) assigns the simplest tasks first.
+
+#### Pros
+
+- Maximizes throughput
+
+#### Cons
+
+- Maximally bad to clear the entire queue assuming all tasks in the queue at t=0 (throughput)
+
+#### Example
+
+Tasks:
+
+T1 = 1s
+T2 = 10s
+T3 = 1s
+
+All tasks arrive at t = 0
+
+Schedule:
+
+0-1 T1
+1-2 T3
+2-12 T2
+
+Throughput: 3/12 = 0.25 tasks / second
+
+Average completion time: (1 + 2 + 12) / 3 = 5 seconds
+
+Average wait time: (0 + 1 + 2) / 3 = 1 second
+
+### Complex Tasks First
+
+The goal of assigning complex tasks first is to maximize resource utilization where resources may be CPU, interrupt devices, memory, and anything else that may be utilized.
+
+#### Pros
+
+- Maximizes resource utilization
+- Tries to minimize total execution time
+
+### Round Robin Scheduling
+
+When running tasks that have the same priority, it is popular to perform round robin scheduling. With this approach, we perform what amounts to FCFS scheduling, but tasks may yield to each other (like when they perform I/O operations) which then places them at the end of the queue.
+
+### Priority Scheduling
+
+Frequently tasks will be assigned priorities based on how important their execution is. As such, priority scheduling is frequently applied on top of other scheduling techniques to ensure higher priority tasks are scheduled before lower priority tasks.
+
+#### Priority Aging
+
+Priority queues can suffer from task starvation where lower priority tasks may not get scheduled. One mitigation for this issue is priority aging where tasks increase in priority the longer they are not scheduled.
+
+#### Priority Inversion
+
+Priority inversion occurs when a lower priority task completes prior to a higher priority task. This can happen when a lower priority task acquires a lock, gets preempted, and the higher priority task then tries to acquire the same lock. Since it can't it will get preempted by the lower priority task again, and if the lower priority task holds the lock until it completes it will finish execution prior to the higher priority task.
+
+A common technique to help with this problem is to temporarily boost the priority of the mutex owner when a higher priority task tries to acquire the lock held by the lower priority task.
+
+## Preemption Options
+
+Preemptive scheduling can be applied to any scheduling option.
+
+An issue with preemptive scheduling is it can impose costly context switches, especially if one is trying to strictly adhere to something like complex tasks first.
+
+### Run-to-completion
+
+Run-to-completion is a preemption option where the scheduler never preempts a running task.
+
+#### Pros
+
+- Simple
+
+#### Cons
+
+- Hanging tasks can cause halting
+
+## Runtime Estimation
+
+Estimating the execution time for a task is difficult because there are many factors that dictate execution time. As such, we frequently use heuristics to create these estimates.
+
+## Links
+
+- [Timeslice](Timeslice.md)
diff --git a/docs/Scheduling.md b/docs/Scheduling.md
@@ -1,5 +1,3 @@
# Scheduling
-
-
CPU Scheduling is done on the OS level and is generally simply about the clocks given. This can cause issues with [DRAM](DRAM.md) because the DRAM controller prioritizes requests associated with buffered rows of memory meaning that even if two processes have the same priority they will not necessarily get the same access to memory because of optimizations done in the DRAM controller.
diff --git a/docs/TLB.md b/docs/TLB.md
@@ -0,0 +1,5 @@
+# TLB (Translation Lookaside Buffer)
+
+**Source:** CS 6200
+
+**Definition:** The TLB is a cache inside the CPU that speeds up memory accesses by storing virtual to physical memory mappings.
diff --git a/docs/Timeslice.md b/docs/Timeslice.md
@@ -0,0 +1,29 @@
+# Timeslice
+
+**Source:** CS 6200
+
+**Chapter:** P3L1
+
+**Definition:** A timeslice is the maximum amount of uninterrupted time that can be given to a task.
+
+Also referred to as a "time quantum".
+
+## Selection
+
+For I/O bound tasks smaller timeslices are generally better because CPU bound tasks will more frequently yield for I/O bound tasks which in turn yield once they initiate an I/O request.
+
+For CPU bound tasks larger timeslices are generally better because they reduce the rate of context switches.
+
+## Multi-Timeslices
+
+Since I/O bound tasks prefer smaller timeslices and CPU bound tasks prefer larger timeslices it can make sense to have different collection data structures for different degrees of I/O or CPU boundedness.
+
+### Single Queue
+
+One approach to support multi-timeslices is for the scheduler to check if a task is more I/O or CPU bound and preempt it accordingly.
+
+### Multi-Queue
+
+When using multiple queues, we generally push tasks down to lower levels (meaning they are more CPU bound) when they use the entirety of their timeslice. Conversely, if a task consistently yields prior to reaching the timeslice it should be pushed up to a higher collection.
+
+The scheduler will generally prioritize the most I/O intensive tasks.
diff --git a/scratch/scheduling.md b/scratch/scheduling.md
@@ -0,0 +1,53 @@
+priority-based scheduler with preemption.
+
+| Task | Arrival Time | Exec Time | Priority |
+| ---- | ------------ | --------- | -------- |
+| T1 | 5 | 3 | 1 |
+| T2 | 3 | 4 | 2 |
+| T3 | 0 | 4 | 3 |
+
+
+0-3 T3
+
+T3 has 1 second left then preempted
+
+3-5 T2
+
+T2 has 2 seconds left then preempted
+
+5-8 T1 completes
+
+8-10 T2 completes
+
+10-11 T3 completes
+
+---
+
+T1 finishes at 8
+
+T2 finishes at 10
+
+T3 finishes at 11
+
+---
+
+single cpu; 10 i/o bound tasks 1 cpu bound
+i/o bound tasks issue i/o every 1ms
+i/o operations always take 10ms
+context switching is .1ms
+all tasks are long running
+
+
+1ms timeslice:
+
+91% cpu utilization
+
+10ms timeslice:
+
+95% total utilization then.
+
+---
+
+This is because of the .1 ms context switching
+
+1ms / 1ms + .1 ms = .91
