Section 1
Preview this deck
lock(&lock)
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
6 years ago
Date created
Mar 1, 2020
Cards (59)
Section 1
(50 cards)
lock(&lock)
If no threads hold the lock when a thread gets to lock, it will acquire the lock and proceed. If a thread holds the lock, it will wait until that threads unlocks it.
Turnaround time
completion time - arrival time
Persistence
Achieving long-term storage for important information
What is a process?
A running instance of a program
Are all programs threaded?
Yes all programs have at least 1 thread.
Process States
Running Ready Blocked
Wait() overview
Wait until something finishes. Won't return until a child finishes Can use child PID as argument to wait for a specific one.
Fork() overview
Makes an exact copy of parent process - called child. Child has its own copy of address space, registers, and PC. Non-deterministic
timedlock(&lock, time)
returns after a timeout or after acquiring the lock, whichever happens first
Stride Scheduling
Each job in the system has a stride, which is inverse in proportion to the number of tickets it has. A process runs, increment a counter (pass value) for it by its stride. Choose the process with the lowest pass value to run next Quantum changes depending on the number of processes scheduled
fork() return values
< 0 - Error 0 - Child > 0 - parent, value is PID of child
trylock(&lock)
returns failure if the lock is already held
Virtualization
Transforms physical resources into more general, powerful, easy-to-use virtual forms
Three key ideas of OS
Virtualization Concurrency Persistence
Exec() overview
Execute a separate program than the running one
Ready Process State
a process is waiting to be assigned to a CPU
function to wait for condition variable
wait()
Rules for MLFQ
Higher priority jobs are run If jobs are tied, RR them When a job first arrives in system, give it the highest priority Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (moves down on queue) Periodically boost all jobs
Effects of a small quantum
Better response time Cost of context switching will dominate overall performance
Blocked Process State
a process has made an I/O request and is awaiting return from request.
Components of a proccess
Memory and Machine state
Limited Direction Execution Protocol
The way to run processes on the CPU Phase 1: initialize trap table upon boot Phase 2: switch to user mode upon process runtime
Single-queue multiprocessor scheduling (SQMS)
Reuse all the basic framework for a single processor for the multi- have a single queue and if you have 2 CPUs choose the best 2 jobs to run Has problems with locking, scaling, and keeping cache affinity
Process vs Program
Program: dead, static code/data on disk Process: dynamic instance of code and data
Four components of computer system
hardware, operating system, application programs, users
TestAndSet code
int TestAndSet(int *old_ptr, int new) { int old = *old_ptr; //fetch old value at old_ptr *old_ptr = new; // store 'new' into old_ptr return old; // return the old value }
Trap instruction
instruction that jumps into the kernel - used in system calls
MLFQ Scheduler
Multi Level Feedback Queue Uses multiple queues at different priorities to determine which job to run. Each is given a time slice.
PCB
(Process Control Block) Unique to every process. Serves as the repository for any information that may vary from process to process. -Process state -Program counter -CPU registers -Scheduling Info -Memory Management Info -Accounting Info -I/O info
throughput
amount of jobs completed per unit of time
CFS sched latency
determine how long one process should run before considering a switch (effectively determining its time slice but in a dynamic fashion). Runs processes for the sched latency time / the number of processes
Proportional Share scheduler
(aka Fair Share Scheduler) ensures all process get the same percentage of CPU not optimized for response or turnaround time
Completely Fair Scheduler
CFS A type of Stride Scheduler - Processes accumulate vruntime (virtual runtime) and the OS runs the processes with the least vruntime. Utilizes 'niceness'
Concurrency
Lockout processes to avoid collisions and conflicts
CFS Min granularity
time slice never gets smaller than this value
Multi-queue multiprocessor scheduling (MQMS)
Have multiple queues When a job arrives, it gets placed on a random queue (possibly algorithmically determined) Problem is imbalance - migration fixes this. A queue can 'work steal' from another queue if it doesn't have enough work and the other queue has a lot
Effects of a large quantum
Amortize (make worth it) the cost of switching Worse response time
FIFO scheduler
First in, first out. Problem: convoy effect - turnaround time can suffer if a short job is 'stuck behind' a long job Realistic use: real-time systems
function to send condition variable
signal()
Niceness (CFS)
How CFS prioritizes processes Ranges from -19 to +20 Default is 0 Higher niceness means lower priority
Thread
Thread is a lightweight process, it's an execution stream that shares an address space Each thread has its own stack
Round Robin Scheduler
Cycles through jobs running a time slice of each job. Great response time, poor turnaround time. Good for fairness.
What is different between threads?
Stack, registers, TCBs(for context switching)
STCF scheduler
Shortest to completion first introduces preemption to SJF. Bad for response time
Running process state
instructions of a process are being executed
Response time
initial schedule time - arrival time
Problems with basic MLFQP
You can game the scheduler (relinquish CPU after using 99% of time slice to maintain high priority) if there are too many 'interactive' jobs in the system, long-running jobs will be starved Programs could change behavior over time (Last two problems are countered by the periodic boost)
REMEMBER TO STUDY THREAD CODE
--- THREAD CODE ---
SJF Scheduler
Shortest Job first Problem: if you start running a job and a shorter one arrives, you cannot switch.
What is the time slice in Round Robin called?
scheduling quantum
Section 2
(9 cards)