Operating Systems

Von Neumann

Processor fetches instruction from memory, decodes it (figures out what it is), and executes it(does the thing it's supposed to do), then continues to the next one until completion

Operating System (OS)

Body of software responsible for making it easy to run programs such as seemingly running multiple at the same time, allowing programs to share memory, interact with devices

• Does this by virtualization why we call OS as a virtual machine

• Provides interfaces (APIs) for users to call to tell it what to do, accessing its features

  • OS has many system calls made available to applications, which is a part of standard library to applications

OS is resource manager, as CPU, memory, disk, are resources to manage them efficently and / or fairly 

Virtualization

• OS takes physical resource like processor, or memory, or disk) and transforms it into a virtual form)

What’s the illusion here by the CPU

makes illusion that it has multiple large virtual CPUs] (virtualizing CPU into many)

What’s the illusion here

Running it multiple time starts p off at the same address and slowly update and prints the results

Each process access its own private virtual address space (sometimes called address space) which is how it seemingly allocated the pointer to the same space but updates them independently

Somehow OS mas onto physical memory of machine that doesn't interfere with other processes or OS itself

OS juggles many things at once, running one process tthen another

Multi threaded, creates two new threads which is a function within the same memory space as other functions more than on them active at a time

Creates two threads using Pthread_create(), with threads being functions that run within

Persistence

• certain memory is easily loss as devices such as DRAM store values in volatile manner, on power off it all is erased

  • Need hardware and software to store data persistently 

• Hardware comes in form some kind of input /output or I/O device in modern, hard drive is a common repository for long live information, although solid state drives are making a head way arena

  • software in OS manages the disk is the file system, storing any files the user

• Does hellow worle, does oepn write close these are system call routed to the file system which handles request and returns some error code to the user

  • Has to know where in disk it will reside, keeping track of it in various structure of the file system (which requires I/O to underlying storage device) but OS has simple way to do it called standard library 

  • devices have certain capabilities, intricate write protocol such as journalin or copy on write carefully ordering

Process

• Running program

  • We often want tens or even hundreds running at a time

  • program is lifeless sitting on disk with all its instructions and static data, but OS makes it run

    • Program is passive

      Code and data

      Prc is running program

      stack, regs, program counter

      If we both run firefox, it is the same program, but different processes

Virtualizing the CPU

running on process, stopping it, running another, and so on (called time sharing the CPU)

This allows user to run many concurrent process with a potential cost in performance (as they will run more slowly if CPU is shared)

Context Switch

OS ability to stop running one program and start another on a given CPU, a time sharing mechanism used by all modern OSes

register context will hold for stopped process (contents of registers will be saved to the memory location).

OS will resume by putting those values back in the registers

Space Sharing

resource is dividend (in space) among those who wish to use it, such as disk space being assigned to file, and can only be used  again if deleted

Mechanisms

• Low level methods or protocols that implement a functionality

  • Answers the how question of a system

Policies

algorithms for making a decision within the OS

Answers the which question of a system

Scheduling Policy

determines which program to run on the CPU when given multiple option using historical information, workload knowledge, performance metrics, etc

Machine State

what a program can read or update when it is running

address space, memory, PC, Registers stack pointer, I/O information etc.

Address Space

Memory a process can address and is part of the process

running program view of memory in the  system, containing all memory state of a program

Memory

instructions are here, so is the data that is read and written

Registers

many instructions explicitly read or update these and part of execution of process

Program Counter (PC) (also called the instruction pointer or IP)

register that tells us which instruction of the program will execute next

Stack pointer and frame pointer

used to manage stack for function parameters, local variables and return addresses

Process API

• these capabilities are available on any modern OS

  • Create: OS must have a way to make new processes (such as double clicking an application or running a command in the shell)

  • Destroy: Need way to forcefully destroy a process, for when they don't just run and exit on their own

  • Wait: useful to wait for a process to stop running

  • Miscellaneous Control: Most OS provide a method to suspend a process (stop it running for a while) and then resume it (continue it running)

  • Status: interface to get information about a process as well (how long it has run, its state, etc)

Process Creations

• First: OS must load its code and any static data (i.e initialized ;variables) into memory, in address space of the process

  • Programs initially reside on disk (or flashed-based SSDs) in an executable format, so these have to be read and put in memory somewhere

  • Loading process used to be done eagerly (all at once before running the program

  • Loading process are now done lazily: loading piexes of code or data only as needed during a program's execution

    • Swapping and paging are two machinary vital for this

• Next: Some memory must be allocated for the program's run-time stack (or just stack)

  • OS gives this to processes (in C this is used for local variables , function parameters, and return addresses)

  • Likely will initialize it such as parameters to the main() function (argc and argv array)

• Next: OS may allocate some memory for program's heap (used for explicitly requested dynamically allocated data in C)

  • Called using malloc() and explicitly freed using free()

  • Needed for Linked lists, hash tables, trees

  • Will grow and allocate more memory to the process to satisfy calls

• Next: OS will initalize aspects related to input / output (I/O)

  • in UNIX, each process by default as 3 file descriptors (standard input, output, and error) letting the programs read input, print output to screeen

• Finally ready fro Program execution starting at teh entry point at main(), transfering control of CPU to the newly created process  jumping to main

Process states

Running, Read, Blocked

• Sometimes a system will have an initial state that the process is in when it is being created

  • Could be placed in final state where it has exited but not yet clean (the zombie state in UNIX systems),

    • allows other processes (usually the parent that created it) to examin teh return code of processes just to see if just finished executed successfully (unusally, programs return 0 in Unix based systems when accomplished a task successfully and non-zero)

  • When finished, the parent will make one final (wait()) to wait for completion of child and indicate to clean it up

Running

process is running on a processor, meaning it's executing instructions, can be descheduled into ready, or I/O intiate to blcoked, terminate when done,

Ready

process is ready to run, but OS has chosen to not run it at this given moment for some reason, can be scheduled to running

Blocked

process has performed an operation it is not ready to run until another event takes place

when process initiate an I/O request ot a disk, becomes blocked so some other process can use it
When done it becomes ready

Process List / Task List

OS keeps a list to track state for each process such as all that is ready and some additional information, blocked processes, I/O events, and wake correct one to run again

Process Control Block (PCB) / Product Descriptor

 C structure that contains information about each process

fork()

the process made is an (almost) exact copy of the calling program, which means that to the OS, there is two copies of the program running and both are about to return from the fork (that’s where it starts existing)

• the child isn't an exact copy, as it has its own address space, PC, and the value returned to caller

  • Parent fork() returns the PID of the new child, the child just returns a value of 0

  • CPU might run either first, so somtimes, on will print out before the other, the output is not deterministic

<unistd.h>

you call it ocne it returns twice, once in orgiinal, cone in the brand new one both carry on

return tells you which you are in 0 means you are the child

Child is copy: same code, same variables same open files, but its own memory . changing a variable in one does not change the other

takes no arguments

Before using fork, flush output using fflush(stdout);

pid_t example = fork()

example < 0 there is an error

if example == 0 it is the child process getpid()

ielse parent and get pid

He has two print statement, when you run fork, you have two processes running concurrently, which finishes first depends on scheduler which could change run by run

wait()

• parent calls wait() system call or (waitpid()), parent process calls wait () to block / delay its execution until child finishes doing executing, after which parent is unblock and wait() is returned

•  Child will always return first, because if CPU ever went to run, it calls wait, meaning it won't return until child has run and exited so no message is printed

blocks, parent (children wolnd't wait for parent, if you need that, rewrite the logic)  stop on this line until one child finishes, that makes ouput order predictable

Status is not the exit code, it backs sever outcomes inot one int ask what happne than unpack it

Skip it, and the finished child become a zombie, don running but still holding till someone collects it

wait will write to the point in status

WIFEXITED (status) did it exit normally

WEXITSTATUS: cod passed to exit()

WIFSIGnNALED was it killed instead? alwasy as wifexited before trusting wexistatus

child awlays finishes first

exit (3) is the 3 the parent reads back out of status

Exec()

Family of functions

• Useful if you want to run copies of same program, often you want to run a different program

• Child Process calls ececvp() in order to run wc, a word counting program

• exec() when given the name of an executable and some arguments, it loads code and static data from that executable and overwrites its current code segment (and current static data), heap, stack, are reintitialized

  • Then OS runs it, passing the arguments as argv of that process

  • Does NOT create a new process rather transforms the current one into a different one

    • Successful calls to exec() never return

kill()

•  sends signals to process including directives to pause, die, and other imperatives

  • Certain key strokes sent signal to currently running process

  • Control c is SIGINT (interrupt) to process often killing it

  • Control z sends SIGSTP (pauses process and can resume it, fg)

• Can send signals to individual processes or process groups

  • process uses signal to catch so it suspends and runs code based on code

• There is users so that not anyone can send signals, have control over their own processes but OS gives em resources to do it

• Often have an admin that can kill a process even if they tehmselves didn't start it, often given to superuser and root,

Limited Direct Execution

"Direct execution": Program runs directly on the CPU, so when OS wants to start a program, it creates a process entry on list, allocates memory, loads the code into emory, locates entry point and jumps to it and starts running

• Problem with this is that if it just runs, how can we stop it from doing anything we don't want it to do while still running it efficiently

• 
  

• How does OS stop it from running and switching to another to do the timesharing we require?

  • Solution 1: restricted operations

    • introduce processor mode known as user mode, code run in mode is restricted in what it can and cannot do

    • Also have a kernel mode, where OS or kernel runs it, so the code can do whatever it wants (make the i/o requests and executing instruction)

    • Leave restricted operations to system calls (made from trap table intialized at boot time that CPU remembers)

  • Solution 2 Swithcin process

    • Cooperative approach :

     

    • Non Cooperative Approach:

System Calls

• allow kernel to carefully expose key pieces of functionality to user programs

  • To execute program must execute a special trap instruction, simultanesouly jumping to kernel, raising privilege level to kernel mode, and then once done, it does the return from trap instruction, reducing privilege back down to user mode

  • When executing trap, must save all callers registers to return correctly when it returns, on x86 it pushes the pc flags and other registers to kernel stack which will pop the valuses off stack and resume in user mode when returning

• Knows where to jump by kernel trap table at boot time (booting up is done in kernel mode) and configures hardware as needed, inccluding what code to run when exceptional events occur 

  • It informs the locations of trap handlers usually with some special instruction, once told, it remembers until rebooted thus knows what to do in case of system calls or exceptional events (this is a privileged operation)

• System call number is usually assigned to each system call, so user is responsible for putting that number in a register or location on stack

Cooperative approach to switching Processes

• Wait for system calls

  •   OS trust processes to behave responsibly and if it run for too long are assumed to give up the CPU so OS can run another task

  • Could also do it when they did something illegal, generating a trap to the OS (likely terminating offending processes )

  • Transfer of control is done by making system calls, so often include a yield system call which does nothing but transfer control so it can run other to OS

  • Susceptible to infinit loops and may never make it to a system call or may be malicious

Non cooperative approach to switching Processes

• OS takes control

  • OS can't do much at all when a process refuses ot make system calls (or mistakes and thus return control to the OS) beside reboot

  • Use a timer interrupt: timer device programmed to interrupt every so many milliseconds and when raised, the running process is halted, an interrupt handler in OS runs

    • OS then can do what it pleases, (start or stop processes)  OS tells hardware which code to run at timer interrupt at boot time and start the timer. It can be turned off

    • All that is privileged operations

  • Hardware, when interrupt occurs, saves enought state that when a return from trap will start the program running correclty (very timilar to a system call)

    • Does a context switch ang does back

• Timer interrupts, user reigsters of running process are implicitly saved by the hardware using kernel stack of that process

  • Disabled when during interrupt processing (could miss them) or have a locking scheme to protect concurrent acces to internal data structure so multiple things go on in kernel at on

getopt()

• Part of c standard libarary

• optarg

• optind

• getopt looks at teh argv, and every call it returns next option it knows to look for or else it is a -1

• argc and argv, pass from main function

• options

Strtok()

Workload

The processes running in the system, determining this is crucial for building policies and the more you know, the more detail the policy

Metric

 just something we use to measure something

Turnaround time

time at which the job completes minus time at which job arrived

T_turnaround = T_completeion - T_arrival

a performance metric, another metric of interest is fairness. Perfromance and fairness are often at odds

• If turnaround ever matters, short job first (SJF) is considered ideal

FIFO Scheduling

Simple easy to implement

• Say we have 3 jobs on system, A, B, C arriving at the same time  (T_arrival = 0 though order is A, B, C), with each job running for 10 seconds 

  • Average Turnaround Time: (10 (A finished) + 20 (B finished) + 30 (C finished)) / 3 = 20

• But if they don’t arrive at the same time  example (A is for 100 Seconds, B and C is 10 each)

  • A runs for 100 seconds, then B, then C

    • Turnaround Time = (100 (A finishes) + 110 (B finishes), + 120 (C finishes)) / 3=110

Convoy Effect

relatively short potential customers get queued behind a heavy weight

Shortest Job First Scheduling

Runs the shortest jobs first (shocking) Example (A still 100, B and C still 10, T_arrival for all is 0)

• Turnaround time = (10 (B finishes) + 20 (C finishes) + 120 (A finishes)) / 3 = 50

• Better than the 110 we had for FIFO in this stiuation

• T_arrival of A is 0 and job takes 100, T_Arrival of B and C is 10, with each taking 10

  

• Turnaround time = (100 (A finishes of 100 - 0) + 100 (110 - 10 for B's completion - arrival) + 110 (C finishes completion - arrival)) / 3 = 103.333

Preemptive

schedulers are willing to stop one process to run another so scheduler can perform a context switch, stoppign one running process to resume / starting another

Nonpremptive

Run jobs to completion (SJF is non preemptive scheduler by our definition here)

Shortest Time To Completion First (Preemptive Shortest Job First)

• We may relax assumption 3 (jobs must run to completion) and the machinary in scheduler, so we'll give it a timer interrupts and context switching, and give it ability to be preemptive

• Any time a new job enters the system, scheduler determines remaining jobs (including new jobs) has the least time left and schedules that one

• Example 

  • 
    

    

  • Turnaround Time = (120 (120 - 0 for A) + 10  (B for 20 -10) + (30-10 for C)) / 3 = 50

Response times

• Time shared machines: user would sit at terminal and demand interactive performance from system as well

• New metric Response Time

  • Time when job arrives to first time it is schedule = T response = TFirstRun - T_arrival

• SCTF is not good at respnse time, as when 3 jobs arrive at once, 2 have to wait for the third to run all the way before being scheduled once, good for turnaround bad for response time / interactivity

  

Round Robin / Time Slicing

• Run a job for a time slice / scheuling quantum: then switch to teh newxt job in the run queue, repeating till completion (length of time slice must be multiple of timer interrupt)

• Say we assume A, B, C arrive at the same time with each wishing to run for 5 seconds

  • SJF: run each job to completion (figure 7.6)

    • Response Time of SJF ( 0 (0 - 0 for A) + 5 (5-0 for B) + 10 (10 - 0 for C)) / 3 = 5

  • RR with time slice of one second: quickly cycle through jobs (Figure 7.7)

    • Response Time for RR ( 0 (0 - 0 for A) + 1 (1-0 for B) + 2 (2 - 0 for C)) / 3 = 1

    • Shorter the time slice, the better it is under response metric, but if too short, cost of context switching dominates overall performance, so we have to make it long enough to amortize

• When we context switch OS saves and restores regists, build up CPU caches, TLBs, branch predictors, hardware, all of which have to be wiped and adopted

  • Turnaround time for RR = (13 (13-0 for A) + 14 (14-0 for B) + 15 (15-0 for c)) / 3 = 14

  • RR is atrocious for turnaround time as it stretches each job for as long as it can

• RR is fair: evenly divides CPU among active processes on small time scale, but this often comes at cost to turnaround time

• Overlap operations to maximize utilization of systems, overlap useful for performing I/O or send messages to remote, starting and switching is good and imporve utilization and efficiency

Amortization

• Amortization: commonly used in systems where there is no fixed cost to some operation, the cost is reduced

  • Say time slice is 10ms but a context switch takes 1 ms, roughly 10% of time is on time slice, but if it were 100ms it would be 1%

MLFQ

Basic Rules

• Most approaches of this are similar

• MLFQ has dstinct queues, each with a different priority level

  • Job ready to run is on a single queue, and MLFQ uses priorities to decide which job to run at a given time, highest priority is what goes first

  • If on same queue, the two jobs run in Round Robin

• In short

  • Rule 1: If priority (A) > priority (B), A runs and B doesn't

  • Rule 2: If prioirty (A) = Priiority(B), A and B run in Round Robin (RR)

• MLFQ then varies priority of job based on observed  behavior, if a job frequently relinquishes CPU while waiting for CPU, MLFQ will assign it high priority as it ishow an interactive program should behave

  • If process uses CPUfor longer stretches, MLFQ reduce priority

  • MLFQ uses history of job, learns it, and uses it to predict future behavior

• Two jobs (A and B) are given high priority, while JOb C is in middle, and D at bottom

  • 
    

  • But by this appearance, it seems as if C and D don't run till A and B finish, so job priority changes over time

• Attempt 1: How to change priority

  • Have to keep in mind workload is a mix of short running interactive jobs (frequently relinquishing CPU) and longer "CPU bound" jobs but response time may not be important

  • Allotment: amount of time a job can spend at a given priority before scheduler reduces its priority

    • Rule 3: when job enters a system, placed on highest priority

    • Rule 4a: if job uses allotment when running, priority is reduced (moves down a queue)

    • Rule 4b: If job gives up the CPU (perforoming I/O operation), before allotment is up, stays at same priority level (allotment is reset)

  • Example 1: a Single Long Running Job

    • 
      

    • Say time slice is same as allotment (for simplicity), shows what happens over time, it goes to the bottom

  • Example 2: Along came the short job

    • If there is a job A (long running CPU intensive) and B (short running interactive)

      • 
        

      • Left plot simulates scenarios that A (black) runs on lowest priority as a long runnes does, with B arriving at time 100, and inserted at top queue, has a 20 ms run, and is complete fefore reaching the bottom, to which A starts

        • First assumes short job, and if it actually is, will be done otherwise only don in bbackground

  • Example 3:

    • If it has I/O, we keep it at same priority, as it is interactive that has a lot of I/O we want it near teh top, not wanting to penalize it we keep it at same level

  • Probelms with our currnet MLFQ

    • Starvation: if there are too many interactive jobs, they combing to consume all CPU time and so long running will never have any time

    • Smart user could game teh scheduler, tricking it to give you more than fair share of the resource

      • If giving up for an I/O operation right as your allotment is almost up so it keeps you at same priority

    • Prg may change behavior over time, what could be CPU bound may be interactive, and so would be out of luck

• Attempt 2: Priority Boost

  • Periodically boost priority of jobs in system,

    • Rule 5: after some time period S, move all jobs in System to top most queue

  • Process won't starve as interacted in round robin fashion and get some service, and if it is now interactive, will be treated as such

  • 
    

  • Say boost happens every 100 ms so gets to run periodically

  • But what should S be these are voo doo constants as black magic is needed to get them right this is left to admin then (avoid when possible)

• Attempt 3: Better Accounting

  • How dow we prevent gaming schedule , weaponizes rule 4 a adn 4b

  • 
    

  • Don't forget the allotment of a process used at a given level when does I/O, and when it does do I/O, should keep track, and when allottment done it's demoted

  • Rule 4 becomes: once job uses time allotment at a level (regardless of how many times it gave up CPU) priority is reduces (moves down a queue)

    • Can't dominate CPU time regardless of I/O behavior

• Tuning MLFQ

  • How to parameterize such a scheduler, how many queues, how many time slice, allotment, how often should their be a boost

    • High priority queue jobs are usually given short time slices as they are interactive

    • Low priority are longer time slices

  • Solaris MLFQ / Time sharing Schedule

    • Gives a set table of how priority is altered and when to boost, and can mess this up

    • Default for table is 60 queues with slowly increasing time slice lengtsh

  • Free BSD scheduler uses formula in mathh to adjust to how much of the CPU the process has used

    • Others use decay usage algorithms

  • Some schedulers relegate OS operations for high priority some allow user advice to set prioirty using programs

Threads

"Lightweight Process "

• Execution streams that share an address space

• Can directly read / write memory

• Can have multiple threads within a single process

• OS doesn't care that it's pointing the same memory as another, OS is helping out in the background to make a thread construct

Job

current execution of a process, Alternates between CPU and I/O, Moves between ready and blocked queues, also a task

Starvation

occurs when a process is prevented from making program because another process as resource it needs

FIFO and SJF

non preemptive

Lottery Scheduling

Proportional share shcduler / fair share scheduler

try to guarantee each job obtain a certain percentage of CPU time

Example is lottery scheduling

Processes get tickets to represent share a resource that a process  (or user) should recieve

Percentage of tickets a process use has represented share

Hold a lottery every time slice (OS should know how many tickets there are)

Random avoid strange corner cases, lightweight, very little tracking, and is very quick

Lottery can also be used with memory

Advantage of randomness

avoids corner case behaviors that is hard (for example with LRU replacement struggling with cyclic workloads) we don't dorry about it

Requiring very little state to track alternatives

Fast

Ticket  Mechanisms

Ticket currency: allows a user with a set of tickets to allocate them among their own jobs in whatever currency they would like, which the system converts into the global value

Example, say user A and B both have 100 tickets, with user A running two jobs

Ticket Transfer: process can hand off its tickets to another process particularly useful in the client / server setting that when request is sent, also sends tickets with it to speed up the work

Ticket inflaction: process can temporarily raise or lower the num of tickets it owns but only do it in processes that trust one another to not be greedy with it, but can then do it if they need more CPU time

 

Implementations

Just need a random number generator and a data strucutre to track processes of system and total number of tickets

Just loops a counter up untill it finds which processes is supposed to run (order it from lowest to highest to keep it fas)

An example

Fairness is time first job completes divided by the time the second job completes, perfectly fair would be quite close to one

How to assign tickets

assume user knows best, but that is a non solution, ticket assignment remains open

Stride scheduling

a deterministic faire share scheduler, each job has a stride (inverse proportion to number of tickets it has)

Take a big number and divide the tickets by it, this is the value of stride for each, and every time a process runs, we increase a counter for it (pass value) to track global  prgress

Say tickets for A: 100, B: 50, C:250 and we divide these from 10,0000,

A_stride: 100, B Stride: 200, C stride: 40

Pick the one with the lowest pass value so far and increm

ent its pa

ss counter by its side

 

Flaw is that it has a global state vairable making updating and adding a new process problematic (as in lottery we just added and wrote how many total tickets there were

Linux Compltely Fair Scheduler

Linux Completely Fair Scheduler

 

Divide the CPU evenly among all competing processes doing a virtual runtime

as process runs, it accumulates vruntime, with each doing so at same rate in proportion to real time, when scheduling, picks the lowest vruntime

Main question is when do you choose the switch as too often impact performance but too few (reducing impact of context switching)and you end up bad short term fairness

Sched_latency determines how long on process should run before making a switch, determining the slice in a dyanmic way

Often does 48 ms and divides it by number of processes but then too many processes runs into the problem of too much context switch

min_granulatrity: 6ms, never sets it below a certain time slice. to prevent sched_latency from being to divided

Has a timer interrupt to determine if it is time to make  decisions, don't need a job to have time slice that's a perfect multiple as it track vruntime precisely so over long haul it is shared

Weighting (Niceness)

CFS gives control to processes priority and allowing some to get more CPU, dones with the nice lvele (-20 to +19 with default of 0) positive is lower prioirty and negative is higher priority

 

 

Weight allows us to compute the time slice but now accounting for priority difference

 

 

 

It keeps the CPU proportionality ratios when difference nice values is constant if a difference of 5 priority cpu will be always scheduled the same regardless of specific priority

Use red black trees

uses red black tree which is a simple binary tree to keep running  or runnable processes, while sleeping processes are removed from tree and kept track of elsewhere otdered by v runtime

insertion and deletion is Olog n operation in red trees

Sleeping processes

Don't just make the v run time of a job not  happen when it sleeps because it would then fall behind and monopolize when it comes back

Sets the return to the smallest value in the tree

Temporal Locality

when data is accessed, likely to be again in near future

Spatial Locality

when data is accessed at address x, likely to access near x again

Think arrays or instruction flow

Single Queue Mulithred (?) Scheduling (sQMS)

Put all jobs in a single queue, simple but suffers in scalability, to ensure it works, there will be locks to ensure it works but that affects performance (could eventually spend more time locking than working)

NO cache affinity (unless put in system for that but that gets complex) as it provide affinity for some but not others so move to balance the load

Does not scale well due to synchronization overhead

Multi queue Scheduling

multiple queues, each following a particular scheduling discipline, when job is put in system, it's put on exactly one queue by some heuristic (random fewer), scheduled independenlty, avoids sharing and synchronization

Much more scalable and so lock and cache contention is not problem, and in born cach affinity

Flaw is load imbalance, if one queu finishes, could have an idle CPU or a CPU running only one process which isn't fair

Move jobs around by migration, may solve some simple  problems, other solutions exist but how to decide how to enacle migration (continuous migration if one process is on 1 but theres two on the others

Work stealing: a queue that is low will look at another to see how full it is, and if it is more so, will steal on to balance load

High overhead and scaling if done too often but if not then load imbalances

Code

•  program (instructions) live in memory

  •  is static, easy to place in memory so we put it at the top and know it won't need more

Stack

• teep track of where it is in the function call chain as well as allocate local variables and pass parameters and return values to and from routines

  • Grows negatively (to lower addresses)

allocations and deallocations are managed implicitely by the compiler for you

Done automatically, just declaring or intializing a variable does it  

Makes usre you have the space when you call into function, when returnning, it deallocates, so if you want it living past call invoaction don't put on stack

Pointer between allocated and free space

Allocate: decrement pointer

Free: Increment pointer

Heap

• dynamically allocated user managed memory such as that you might receive from a call to malloc

  • Grows positively

  • Stack and heap both will change in size

  • Many ways to arrange especially when you take threads into account as they coexist in address space

 Long lived, explicitly handled by you,

Both stack and heap are called, stack holds the pointer to the place in heap where the integer is stored

Malloc

Free

To free, simply call free on whatever variable is in heap, the memory allocation library deals with it from there

mmap

creates anonymous memory region not associated with any particular file, but rather swap space something that will be later and is treated like a heap

Allocation Errors

Uniprogramming

One process runs at a time

Disadvantages: Only one process at a time

Process can destroy OS

Multiprogramming goals

Transparency: process is unaware of sharing

Protection: cannot corrupt OS or other process memory

Efficiency: Do not waste memory or slow down processes

Sharing: Enable sharing between cooperating processes

Static Data

Code and some global variables

Dynamic data

 Stack and Heap

Process organization

From lowest address (Code, Heap growing up, free space, stack growing down)

rbp

base pointer, pointing to the base of the current stack frame

rip

instruction pointer / program counter

int x;

int main(int argc, char *argv[]){

int y;

int *z = malloc (sizeof(int)););

}

Where are locations (static data/code, stack, heap) of x, main, y, z, z*

Adddress	Location
x	static data
main	static code
y	Stack
z	stack
z*	heap

Time Sharing

• Take all code in program state, move it into memory construct stack and heap, then start running the program, say we need context switch, run another process, take all the memory and move it back onto disk and then load up the other process

• Problems with this

  • Access to disk is very slow, slow is relative but yeah

    • If you have a lot of data in process it is very time consuming and slow

    • Could work but it would be very slow, unlike registers, not just amount of it

  • Ridiculously poor performance

  • Better alternative: space sharing

    • Same time, space of memory is divided across processes, remainder of solutions all use space sharing

Static Relocation

• OS rewrites each program before loading it as a process in memory

• Each rewrite for different process uses different addresses and pointers

• Change jumps, loads static data

• Layout in memory

  • why didn't OS rewrite the stack address (see diagram)

  • Stack is always relative to the frame so just make sure it does it properly

• Disadvantages

  • No protection

    • Process can destroy OS or other processes

    • No privacy

  • Cannot move address space after it has been places

    • May not be able to allocate new process

Dynamic Relocation

• Goal to protect processes from one another

• Requires hardware support

  • Memory Management Unit (MMU)

• MMU dynamically changes process address at every memory reference

  • Process generates logical or virtual addresses (in their address space)

  • Memory hardware uses physical or real addresses

• to make it easier to manage multiple processes use virtual addresses

  • independent of location in physical memory (RAM) that referenced data lives

    • OS determines location in physical memory (so two process at two different places in physical addresses could both think they live at the same logical  address )

  • Instructions issued by CPU reference virtual addresses

    • pointers, arguments to load / store instruction PC

  • Virtual addresses are translated by hardware into physical addresses (with some help from OS)

• Privileged (protected, kernel) mode: OS runs

  • When enter OS (trap, system calls, interrupts, exceptions)

  • Allows certain instructions to be executed (Can manipulate contents of MMU)

  • Allows OS to access all of physical memory

•   User Mode: User Processes run

  • Perform translation of logical address to physical address

• Implementation: Base Reg

  • Translation on every memory access of user process, MMU adds base register to logical address to form physical address

  • Diagram

  • Translate virtual addresses to physical by adding a fixed offset each time

    • Store offset in base register

  • Each process has different value in base register

    • Dynamic relocation by changing value of base register

• But they can still load more than the address (buffer over flow) to write into another process

  • So add a bound

Base and Bounds

• Dynamic Relocaation with Base and Bound

  • Limit the address space with bounds register

    • Base register: smallest physical address (starting location)

    • Bounds register: size of this processes "virtual address space"

      • Sometimes defined as largest physical address (base +size)

    • OS kills process if process if loads/stores beyond bounds

  • Implementation

    • Translation on every memory access of user process,

    • MMU compares logical address to bounds register if logical address is greater, then generate error

    • MMU adds base register to logical address to form physical address

  • Solves one of the problems

  • Managing Processes with Base and Bounds

    • Context Switch: add base and bound registers to PCB

    • Steps

      • Changed to privileged mode

      • Save base and bounds registers of old process

      • Load base and bounds registers of new process

      • Change to user mode and jump to new process

    • Protection requirement

      • User process cannot change base and bounds register

      • User can't change to privileged mode

  • advantages

    • provides protections (read and write) across address spaces

    • Support dynamic relocation

      • Can place process at different locations initially and move address spaces

    • Simple inexpensive implementation: Few registers, little logic in MMU

    • Fast: Add and compare in parallel

  • Disadvantages

    • Each process must be allocated contiguously in physical memory

      • Must allocate memory that may not be used by process

    • No partial sharing, cannot share parts of address space

Segmentation

• Divide address space into logical segments

  • Each segment corresponds to logical entity in address space (code, stack, heap)

• Each segment has separate base / bound registers

• Segmented addressing

  • Process now specifies segment and offset within segment

  • How does process designate a particular segment?

  • Use part of logical address

    • Top bits of logical address select segment

    • Low bits of logical address select offset within segment

  • What if small address space, not enough bits?

  • Implicitly by type of memory reference

  • Special registers

• Segmentation Implementation

  • MMU contains Segment Table (per process)

    • Each segment has own base and bounds, protection bits

    • Example: 14 bits logical address, 4 segments

• Advantages

  • Enables sparse allocation of address space

  • Stack and heap grow independently

    • Heap if no data on free list, dynamic memory allocator requests more from OS (UNIX: malloc calls sbrk())

    • Stack: OS recognizes reference outside legal segment, extends stack implicitly

  • Different protection for different segments

    • Enables sharing of sleect segments

    • rEad only status for code

  • Supports dynamic relocation of each segment

• Disadvantages

  • May not have sufficient physical memory for large segments leading to external fragmentation

  • Each segment must be allocated contiguously

Paging

Paging

• Goal: Eliminate requirement that adr space is contiguous

  • Eliminate external fragmentation

  • Grow segments as needed

• Idea:

  • Divide address spaces and phsycial memory into fixed sized pages

  • size: 2^n, example 4kb

• Translation

  • How to tranlate logical address to physical address

    • High order bits of address designate page number

    • Low order bits of address designate offset within page

  • Page num / frame number

    • No addition is needed just append bits correctly

Virtual > Physical page mapping

Number of bits in virtual address

need not equal

number of bits in physical address

How translate VPN to PPN

free lists

• Free space is easy with paging

  Easy when space is dividied into fixed sized unity as you keep a list, we can return first entry but when variable sized units because of the user level memory allocation an an OS using segmentation to implement virtual memory

  external fragmentation: free space gets chopped into littl pieces of different size

  May fail if no contiguous space can satisfy request even it total free space exceeds size of request

   

  
  

   

   

   

   

   

  17.1 Assumptions

  • we assume that basic interface provided by malloc() and free()

    • void *malloc(size t size) takes a single parameter, size, which is the number of bytes request by application

    • void free (void *ptr) takes pointer and rees corresponding  chunk

      • Doesn't inform library of its size so library has to figure out

    • space that this library manages is known historically as the heap and generic data structure used to manage free space in the heap is some kind of free list

  • Internal frgamentation: If an allocator hands out chunks of memory bigger than that requested any unasked for (and thus unused) space is considered this

    • Waste occurs in allocated unit

  • Assume once memory it can't be reallocated (once a program calls malloc and gives pointer, it is owned by the program and can't be moved by the library unless given a corresponding call to free)

    • thus no compaction of freespace

    • Compaction could be used when implementing segmentation

    • Allocator manages contiguous region and could ask that region to grow (but rn we'll assume it does not do that)

  • 17.2 Low level mechanisms

    • Splitting and Coalescing

      • Free list contains set of elmeents that are free space still in heap, will find a free chunk of memory, than split it into two, with first chunt returning to caller while second called remaining in the list (splitting)

      • Coalescing of free space, say if we free we can put it back into list but then it will be 3 10 byte free chunks despite having 30 bytes free being right next to each other so you combine them

      • Look at nearby free blocks and if you can combine it than you do it

    • Tracking the size of allocated regions

      • 
        

      • Free has no size so if pointer we have a header block just before handed out chunk of memory

        • Contains header block which usually has its size so can quickly see how much size it ise

        • 
          

        • Size tells it the size of block pointed to by pointer (in this case 20)

        • Magic number. is used to provide integrity checks

      • To find the header, just do pointer arithmatic to find out where it is

      • 
        

      • Can easily check if magic number manages expected value and caclulate total size of region that's new freed (size of header plus size of block)

      • When user requests N bytes, library doesn't search for N bytes rather it searches for Nbytes plus header size

   

  • Embedding a free list

    • Need to build the list inside the freespace itself say we start with a 4096 byte chunk (heap is 4KB)

    • 
      

    • we assume heap is built within free space acquired by call to mmap() which while not the only way to build such a heap bu serves well

    • 
      

    • After, the status is one entry of 4088 with head pointer being the beginning address of range

      • Says it starts at virtual address 16kb

   

  • 
    

  • We allocated chunk of 100 bytes, only had one option, so we split the chunk into two (one big enough for the request and its header and one as the remaining free chunk)

    • We assume an 8 byte header (integer for size, integer in magic number

  • Library thus allocated 108 bytesof existing free chunk, returning ptr above and stashing header information immediately before

    • Shrinks free node from 4088 by 108 to 3980

  
  

  First 324 (108 *3) bytes are allocated, and free list is just at the end pointed to by head

  
  

  Library figures out side of free region and add free chunk at head of free space

  Call free (16500) 16500 is the 16384 of virtual address then 108 for previous chunk and then another 8 for header showed by sptr, can immedietly see size and free it

   

  
  

   

  • Growing Heap

    • tries to make a system call to sbrk to grow

  Basic strategics

  Best fist: search through free list and find the memory that is perfect size or bigger (but smallest one)

  naive impmentation are perfformance heavy

  Worst fit: find largest chunk and return the requested amount keep the remaining large chunk, leaves a lot of big chunks free

  Perfroms badly

  High overhead and has external fragmentation

  First fit: find first possible fit, just populates beginnin with small objects and that's polluting and how allocator manages free list order

   

  Uses address base ordering by keeping lit ordered by address of free sapce, easing coalescing and fragmentation

  Next Fit: keeps piont in list it was last looking to avoid splintering instead of first fit going to beginning, avoids axhaustive

  Examples

  Other Approaches.

  Segregated lists

  if application has one or few popular sized request, keep a separate list to manage objects of just that zie with all others bieng tow the general memory allocator

  Makes free and allocation requests quick

  But how much memory do you give it

  slab allocator

  allocates a number of object caches for kernel objects request frequently, so they are segregated free lists of given size and serve allocation and free quickly (all done on boot)

  When cache is running low, requests slabs of memory from more general memory allocator (total amount request being multiple of page size and object in question)

  If the slab are all 0, general allocator cna reclaim them when it needs more memory

  Intialization and destruction of data structures is costly, keeping freed objects in particular list in state, the slav avoids frequent intialization and destruction cycles per object lowering overhead

  Buddy Allocation

  binary buddy allocator makes coalescing simple

  Basically find a block of free memory which are in powers of two and keep splitting it till it is perfect for request

  Has internal fragmentation as it is only of certain size

  Upon free, checks if the buddy is free, coalescing qucikly

  
  

  Address of free space only differ by a single bit, which bit is determined by the tree

  other ideas

  problem with many approaches described above is scaling (searching list is slow)

  Lot of effort in making things work well for multiprocessor