OS:program that manages the computer hardware.

Provides a basis for application programs & acts as an intermediary between the computer user & the hardware. OS Goals: Execute user programs, Ease of Use/Efficient Use of Hardware 4 component of computers: hardware, OS, the applications programs, & the users. Two viewpoints of OS: User View Varies based on interface used Single user, terminal ,workstation System View: OS is the program most involved with the hardware. 1. Resource allocator: Os acts as manager of resources: CPU time, memory space, file-store space, IO. Must decide between conflicting requests of resources for fair & efficient use. 2. Control Program: manages the execution of user programs to prevent errors and improper use of the computer. Mostly concerned with the operation and control of I/O devices Kernel: the one program running at all times on the computer. (Aka the OS) Systems programs: associated with the OS but are not part of the kernel Applications Programs: include all programs not associated with system operation. Mutiprogramming increase CPU utilization so that the CPU always has jobs to execute. A trap (or an exception) is a software-generated interrupt caused by an error or by a specific request from a user program that an operating system service be performed. Dual mode operation: user mode and kernel mode(aka supervisor mode, system mode, privileged mode) The mode bit indicate the current mode: kernel(0) user(1) Two ways operating system services are provided (2 ways a service can be called): System calls (provides an interface to the services made available by OS. Normally C or C++) System programs (associated with the OS but are not part of the kernel) Services that are helpful to the user include (ease of use): User Interface (Command line, batch or GUI). Program execution I/O operations. File System manipulation: need to read, write, create, delete, search, list. Communications: Between processes, via shared memory or msg passing. Error detection. OS needs to be aware of errors in hardware & user programs Services that ensure efficient operation (efficient use): Resource Allocation: OS manages many diff resources Accounting: Keep track of which users use how much and what kinds of computer resources to either bill users or for usage statistics Protection & security: access to system resources is controlled & security of the system from outsiders, authenticate with a password Most system calls are accessed by Application Program Interface (API) such as Win32 System calls six major categories: process control, file manipulation, device manipulation, information maintenance, communications and protection. System programs six major categories: file management, status information, file modification, programming-language support, program loading & execution, communications. System generation: System must be configured or generated for each specific computer site. This allows you to customize your OS to your specific installation. This can be done with system probe to see what hardware is there or the operator telling it. Bootstrap program Stored in ROM or EPROM (known as firmware), Initializes all aspects of system, loads OS kernel into memory and starts

Process, which is a program in execution, contains program code (in the text section), program counter, stack (temporary data like local variables), data section (global variables), heap, (memory allocated dynamically) Process States: New: The process is being created. Running: Instructions are being executed. Waiting: The process is waiting for some event to occur (such as I/O completion) Ready: The process is waiting to be assigned to a processor. Terminated. The process has finished execution. PCB (Process control block) contains: Process State (new, ready, etc) Program Counter (address of next instruction) CPU registers (accumulators, general purpose, etc) CPU scheduling information (process priority, pointers to scheduling queues) Memory management information (value of base and limit registers, page tables) Accounting information (CPU time used, job or process #s) I/O status information (list of I/O devices allocated to the process, list of open files.) Queues: job queue(consists of all processes in system) ready queue (processes that are residing in main memory and are ready and waiting to execute), device queue(each process waiting for a particular I/O device). Queues are generally linked list with a header containing pointers to the first and final PCBs in the list. Longterm Scheduler: selects processes from mass storage device & loads them into memory for execution. Controls the degree of multiprogramming (# of processes in memory). Short term scheduler: selects from among the processes that are ready to execute & allocates the CPU to one of them. Must select a new process for CPU frequently I/O Bound: spends more time doing I/O than computations, many short CPU bursts CPU Bound: spends more time doing computations, few very long CPU bursts Scheduling I/O Bound and CPU Bound: It is important that the long term scheduler select a good process mix of I/O bound & CPU-bound processes. If all processes are I/O bound, the ready queue will almost always be empty, and the short term scheduler will have little to do. If all processes are CPU bound, the I/O waiting queue will almost always be empty, devices will go unused and the system will be imbalanced. This distribution can be important in the selection of an appropriate CPU-scheduling algorithm. Context switch: The kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. Context includes: values of CPU registers, the process state, memory management info.
CPU scheduling decisions take place: 1. When a process switches from running to waiting state (when I/O request) 2. When a process switches from running to ready (when an interrupt occurs) 3. When a process switches from waiting to ready (at completion of I/O) 4. When a process terminates. Nonpreemptive or cooperative: Once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU by terminating or by switching to the waiting state. Preemptive: #2, #3 Process can be interrupted with interrupt or from waiting to ready.

Dispatcher: gives control of the CPU to the process selected by the short term scheduler. Scheduling criteria: CPU utilization: Keep cpu busy as possible. Throughput: The number of processes that are completed per time unit. Turnaround time: The interval from the time of submission of a process to the time of completion. wait+execution Waiting time: the sum of the periods spent waiting in the ready queue Response time: the time it takes to start responding, not the time it takes to output the response. Desirable to maximize CPU utilization and throughput and minimize turnaround time, waiting time and response time. First Come First Serve: Process that requests the CPU first is allocated CPU first. Uses a queue. Average waiting time is long. Nonpremptive. Shortest Job First: Assigns CPU to process with smallest next CPU burst. FCFS scheduling for ties. Optimal. Gives minimum average waiting time. Can't be implemented. Can be preemptive or nonpremptive. Is a special case of the general priority scheduling algorithm. Priority Scheduling: A priority is associated with each process and the CPU allocated to process with the highest priority. Tie breakers are FCFS. Can be preemptive or nonpreemptive. A major problem is indefinite blocking or starvation. Round Robin: Designed for time sharing systems. Similar to FCFS but preemption is added to enable the system to switch between processes. Small unit of time called a time quantum or time slice is defined. The ready queue is treated as a circular queue. Average waiting time is often long. Average turnaround can be improved if most processes finish their next CPU burst in a single time quantum. Time quantum that is too large just makes FCFS. Multilevel Queue Scheduling Algorithm: partitions the ready queue into several separate queues. The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process priority, or process type. Each queue has its own scheduling algorithm. Separate queues might be used for foreground (RR ) and background processes (FCFS). There also must be scheduling among the queues, commonly this is fixed-priority preemptive scheduling. Ex from high to low: system processes, interactive processes, interactive editing processes, batch processes, student processes. Multilevel FEEDBACK Queue Scheduling Algorithm: allows a process to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts. Process that uses too much CPU will be moved to lower priority queue. This leave I/O bound and interactive processes in higher queue. Process waiting too long in lower queue can also be moved up to prevent starvation. Advantage of different time quantum sizes at different levels of a multilevel queue: Processes that need less of a time quantum like I/O bound & Interactive processes will get priority and finish quickly. Whereas other processes that need more time for processing can be in a lower priority which will allow for less context switches. Variant of RR with two pointers: It would give it double the CPU time. Advantage: Priority (Prioritize a job to run before others. Prioritize jobs to lower overall wait time) Disadvantage: complexity with pointers, going against RR, shorter jobs take longer than necessary. Use Variable time quantum in PCB instead. Exponential Averaging: 1.tn = actual length of nth CPU burst 2. n+1 = predicted value for the next CPU burst 3 , 0 1 (commonly set to 1/2) Formula: n+1 = *tn + (1-)n

Race Condition: several processes access and manipulate the same data concurrently, outcome depends on which order each access takes place. Atomically: one interruptible unit Critical Section Problem (the key thing is that Im trying to update some shared structure or shared memory, I have multiple processes trying to do it so were trying to avoid race conditions which will get the wrong result) Solution requires a lock. Critical section could be solved simply in single processor environment if we could prevent interrupts from occurring while a shared value is modified. Solution to Critical Section Problem: Mutual exclusion is preserved, progress requirement is satisfied(Process can't be held up forever), and bounded waiting requirement is met (progress must be made in a bounded period of time). Busy waiting: while a process is in its critical section and any other process that tries to enter its critical section must loop continuously in the entry code. Deadlock: Two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes Test and Set (boolean variable called lock initialized to false) Swap (boolean variable lock initialized to false. Each process has a variable key.) Semaphores (synchronization tool) can be counting or binary aka mutex locks. A transaction is a program unit that must be executed atomically; that is either all the operations associated with it are executed to completion, or none are performed. To ensure atomicity despite system failure, we can use a write ahead log. wait(flag) Normal operation. <critical section> Wait decrements and means <Acquire lock> signal(flag) Critical Section is 0 Signal increments and means<Release lock> wait(flag) <critical section> <critical section> signal(flag) signal(flag) <critical section> wait(flag) signal(flag) <critical section> Would cause starvation by leaving it locked deadlock Makes mutual exclusion violated. Data could get corrupted. It never locked the resource. So may have mutual exclusion violated, while in here others could be in here as well. Doesn't lock. Mutual exclusion is violated

Gantt Chart: Bar chart that illustrates a particular schedule, including start and finish times.

P1

P2

P3

P4
13 14

P5
19

0 10 11 Turn around: P1 = 10, P2=11,P3=13,P4=14,P5=19 Avg Turn around Time = 13.4

Wait Time: P1=0,P2=10,P3=11,P4=13,P5=14 Average wait time = 9.6 SJF has 7 TA and 3.2 W; Priority has 12 TA and 8.2 W; RR has 9.2TA and 5.4W RR for Wait either count all other processes until desired one ends or take last wait when process ran