read more

Lecture 1:

Batch Processing: For a bunch of independent jobs, load whatever is shared between the jobs and then load and execute each of the jobs. This essentially cuts down on redundant loading of code.

Throughput: Number of jobs completed / observation interval.

Multiprogramming: have the processor switch between executing different jobs, essentially. So for instance when one job has a read from disk, which will take a while, have the processor working on another job until it gets an interrupt that the read from disk is done.

Timesharing: (this still currently happens): have an interrupt occurring at regular intervals, which calls some function in the OS called (schedule) which figures out if the CPU should start executing a different job/program. This is decided algorithmically in the scheduler.

Multiprocessing: Just having multiple processors. You could have the OS shared among the CPUs (as you’d see in our personal, multicore computers), or distributed for each CPU, or partially distributed (asymmetric).

Lecture 2:

Process: So the OS really thinks about a process based on context or state, sort of. So a process is really just a memory state, processor state, and execution state. Where memory state is what info is in memory, processor state is like what the instruction counter was, what was in the registers, and execution state is like what the process was doing (waiting for I/O or running).

Context switch: When the OS changes what’s in memory, on the CPU, etc so that it matches different programs that were interrupted during execution.

Process Creation: Called fork/join, you’ve got a parent process which apparently has all the code for itself and the child process it wants to spawn. Then what happens is it’ll have a line like childPID=fork(); and that’s spawn an instance of itself (called the child) which will start execution after that line which runs in parallel with it. Typically after that point the parent will have had code checking to see what it should run based on what the value of childPID is (fork() will return a PID), and because the parent actually has some value for childPID and its child doesn’t, the parent will end up executing some code and the child will execute something else.

Lecture 3:

Scheduling: Inserting a process into a queue, where the queue could be the “ready” queue, the waiting queue, or running queue. Can insert items anywhere in queue using algorithm based on what needs to be handled first, etc.

Dispatching: Removing process from queue.

Processes Control Block: The structure of a process in the queue. It’ll have a PID, memory pointers, register values, and then pointers to what’s next in the queue and what’s before. This is the stuff that’ll get loaded when we context switch.

CPU Bound & I/O Bound: A processes is limited by how much CPU/I/O time is allowed for it.

Convoy: Clumping of jobs on different stages (I/O, CPU, etc). This is bad because you’re not using both the I/O and CPU at once, which means you don’t get as good performance. A Long-term scheduler would be called every so often to manage and prevent this by organizing jobs so that this is minimized.

Medium-term Scheduler: This will look for the same thing as the long term scheduler, but it’ll suspend processes to allow things to flow better.

Short-term scheduler: This will get called in many instances, such as when a process goes from running to waiting, and other less obvious cases. In all these instances, the short term scheduler is run to figure out what if any new process should be run. Should remember how when doing a context switch during dispatch, you’re changing the stack pointer which means variables get all changed so you have some weird stuff going on where the values of local variables change midway through its execution.

Lecture 4:

Scheduling policies and their effectiveness: First in first out, not very effective because if your first job was the longest, then the jobs after that have an unnecessarily long response time. Shortest job first: sort the queue by how long it’s estimated to complete the job, and execute in that order (this is optimal, which means that there’s nothing better than it). Priority scheduling: assign an integer to each processes (low=high priority), and then execute them based on that. To handle the problem where low priority jobs would never execute as new high priority ones come up, we would “age” the processes, which would slowly increase its priority over time. Round-Robin: have a queue that’s first come first serve, and a process gets to execute for a certain amount of time (a quantum or time slide) until an interrupt occurs and it goes to the back of the queue. Multi-level feedback (actually used in practice): (combination of priority and round robin). You essentially have multiple queues (which behave as round robin) each of which is responsible for all the processes with a given priority. The quanta for the high priority are very small while the ones at low priority are big. If a processes doesn’t finish in its quanta, it gets demoted down one priority. Deadline scheduling (for real-time processes): essentially each processes is given a priority based on its deadline (this is a preemptive scheduler).

Pre-emptive vs Nonpreemptive scheduling: If you’re doing it nonpreemptively, that means that you let the jobs finish to they’re done, and preemptive means that you could interrupt a processes if another job could be completed faster.

Approximating job execution time (for means of scheduling): You can keep track of the time that a process is in the running state. You then could use the formula estimated_time = alpha * last_time + (1-alpha) * last_estimate.

Lecture 5:

Shared Memory: a way of process communication. So you could have it that you pass the OS a call to read with certain parameters, and when the read is done, the OS would write the values to those parameters (so shared memory in that the OS is actually writing values to the stack of the program). Not only could the OS do this, but processes can do it as well. So they share some global variables, essentially, that they can all access. You can reach a problem with this, which is called a “critical section” problem, in which you’re assuming that two processes aren’t going to try to modify a variable at the same time, but because of essentially the possibility of a random interrupt, they could end up altering the same variable at the same time.

Mutual Exclusion: This solves the problem that came up when dealing with shared memory. Essentially, just have it so that no two processes can modify the same variable at the same time, so you have a check in each processes to make sure nobody is executing the “critical section” which is the shared variable code, essentially. Expedient would be if you made some mutual exclusion without one process unnecessarily having to wait for the other. Fail safe: means that if one processes were to fail, the other could go about its business and it doesn’t rely on the other. Bounded waiting: no matter what, the processes will stop waiting at some point.

Atomic: an instruction is atomic if it’s completely indivisible. That is, essentially, its corresponding assembly code is a one liner.

Lecture 6:

Semaphore: something that can be used so that mutual exclusion can be implemented without having to employ busy waiting (which is essentially having a loop that executes NOOP, that is, nothing). A semaphore is a primitive (so it’s just a data structure in the operating system) that can be used to make this synchronization easier. It has a down and up function, and an integer. Its value is non-negative. In down, if its value is >0, then you decrement. If it’s not >0 (==0) then you wait until it is >0 and then decrement. Up just adds to one to its value. Up and down are assumed to be atomic. Always give the initial value of the semaphore.

Binary Semaphore: semaphore but its value can only be 0 or 1. Figured out a way to make its up and down atomic, by using disable/enabling interrupts or test and set.

Condition Synchronization: waiting to synchronize based on some condition. Not really understanding condition synchronization and how it fits in with mutual exclusion. It seems like it’s just a way of implementing mutual exclusion.

Enable/disable Interrupts: One great use for this is to make some portion of code appear atomic. Great for implementing semaphores.

Test and Set: So instead of disabling and enabling interrupts, there’s an assembly test and set function that you can use, which will do a load, compare and store all in one operation so things can’t be interrupted during it.