CS370 Midterm #1 2023 with complete solution questions and answers

Define operating system in terms of what they do - manages the computer's resources - establish a user interface - execute and provide services for applications software What is dual mode operation? How does it switch between modes? allows OS to protect itself and other system components kernel and user mode --> privileged instructions can only execute in kernel mode volatile main storage loses its contents when power is turned off non-volatile second storage long-term persistent storage I/O bound jobs vs CPU bound jobs I/O: bottleneck in any input/output processes CPU: job spends more time using CPU time-sharing CPU executes multiple jobs by switching among them - response time < 1 second interrupt operating systems are interrupt driven can be signaled by hardware or software - causes the OS to change a CPU from its current task and to run a kernel routine when can hardware trigger an interrupt? anytime when can software trigger an interrupt? by executing a special operation called a system call interrupt vector holds the addresses of the interrupt service routines for the various devices kernel mode bit = 0 CPU has instructions to manage memory and how it can be accessed, ability to access disk and switch itself from running one program to another - trap or interrupt occurs - OS gains control of the computer - system boot time (turning on) user mode bit = 1 access to memory is limited to only some memory locations, cannot access devices what resources must be protected by OS I/O Memory CPU hardware CPU memory I/O devices bootstrap program initial program How does the CPU load instructions? only from memory Disadvantage with main memory too small to store all programs and data volatile what is the most common secondary memory magnetic disk non-volatile single-processor system one main CPU multi-processor system has multiple CPU's increased throughput symmetric multiprocessing no boss-worker relationship all processors are peers each processor has its own set of registers and cache and performs all tasks asymmetric multiprocessing boss and workers each process is assigned a specific task multicore two or more CPU's working together on the same chip are multiprocessor systems but not vice versa mode bit is provided by what? hardware memory management to execute instructions they must be in memory all of the data that is needed must be in memory layered approach for OS retain greater control over the computer and applications layer 0 = hardware layer N = user interface - a layer is an implementation of an abstract object made up of data and the operations that can manipulate those data - a layer can only use lower-level layers advantages of layered appraoch - simplicity of constructions and debugging disadvantages of layered approach - special planning since a layer can only access lower level layers - less efficient what is a kernel - computer program that constitutes the central core of the OS - it has complete control over everything that occurs - first program loaded on startup --> manages the remainder of startup command interpreter and how can it be implemented - to get and execute the next user-specified command 2 ways to implement: 1. the CI itself contains the code to execute the command 2. implements most commands through system programs, CI does not understand the command but uses the command to identify a file to be loaded into memory and executed system calls provide an interface to the services made available by OS what is a process a program in execution process is a ________ entity active program is a ___________ entity passive valid process states ready -> running (scheduler dispatch) running -> ready (interrupt) running -> waiting/blocked (I/O) running -> terminated (exit) waiting -> ready (I/O) process control block contains information associated with each process - process state - program counter (location of instruction to next execute) - CPU registers - CPU scheduling info (priorities) - Memory management (CPU used, clock) - Account info - I/O status info queues on an OS scheduling queues - job queue - ready queue - device queue what does the long-term scheduler do? selects processes from the pool and loads them into memory for execution - executes less frequently - controls degree of multiprogramming determines which programs are admitted to the system for processing. It selects processes from the queue and loads them into memory for execution. what does medium-term scheduler do? uses swapping what does short-term scheduler do? also known as CPU scheduler selects from among the processes that are ready to execute and allocates the CPU to one of them - must select a new process for the CPU frequently multiprogramming keeping several jobs in memory simultaneously and switching between them degree of multiprogramming the number of processes in memory when is the long-term scheduler invoked? only when a process leaves the system what is a context switch? when a CPU switches to another process, the system must save the state of the old process and load the saved state for the new process what does the kernel do during a 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 describe the producer/consumer problem - a producer must wait until the buffer has space before it can put something in - a consumer must wait until something is in the buffer before it can take something out problem: make sure that the producer won't try to add data into the buffer if it's full and the consumer won't try to remove data from an empty buffer mutex provides mutual exclusion for accesses to the buffer pool and is initialized to 1 if = 0 --> not available if = 1 --> available semaphore empty value = n semaphore full value = 0 parent process the creating process creates child processes init process the root parent process for all user processes, once its booted it can create various user processes What happens when a process is created? a child process is created it can either contain its resources from the OS (new process) or contain a subset from the parent process (duplicate of parent) what happens to the parent process when a child process is created? 1. the parent continues to execute concurrently with its child 2. the parent wait until some or all of its children have terminated return value for fork() child = 0 parent = PID of child what does it mean when return value of fork() = 0 < 0 > 0 = 0 --> running child < 0 --> error > 0 --> running parent wait(), abort(), exit() wait() --> allows caller to suspend execution until child's status is done abort() --> terminates child process exit() --> terminates and starts exit process what happens when a process terminates? will terminate when it finishes executing and asks the OS to delete it by using the exit() - resources are deallocated from memory - return a status value zombie a child process that has finished executing but who's parent has not yet called wait(), so it has finished but not terminated orphan a parent who did not invoke wait() and terminated which leaves the child alone - in this case the init process will be assigned to it what is IPC? interprocess communication allows cooperating processes to exchange data and information independent process cannot affect or be affected by the execution of another process cooperative process can affect and be affect by other processes unbounded buffer no limit on the size of the buffer - the consumer may have to wait for new items but the producer can always produce new items bounded buffer assumes a fixed buffer size - the consumer must wait if the buffer is empty and the producer must wait if the buffer is full direct communication each process that wants to communicate must explicitly name the recipient or sender ex. send(P, message); --> send a message to process P - link is established between every pair of processes that want to communicate - between each pair of processes, there exist exactly one link indirect communication messages are sent and received from mailboxes - processes can only communicate with a shared mailbox ex. send (A, message); --> send message to mailbox A - a link is only established if both processes share the same mailbox - a link may be associated with two processes - many links can exist between a pair of processes asymmetric direct communication the sender names the recipient but the receiver uses an id symmetric direct communication both the sender and the receiver must name the other to communicate synchronous blocking blocking send, blocking receive asynchronous not blocking non-blocking receive, non-blocking send rendezvous both send and receive are blocked pipes allowing two processes to communication one directional two communicate in both directions - need two pipes what is a thread? basic unit of CPU utilization contains: - thread ID - program counter - register set - stack multiple threads path of execution in a process, can perform more than one task at a time -share code, data and files - can do anything a process can do difference between thread and process threads -> used for small tasks, if they are in the same process they share address space process -> used for heavyweight tasks user threads user level supported above the kernel and are managed without kernel support kernel threads kernel level supported and managed by OS many-to-one many user-level threads to one kernel thread - the entire process will block if a thread makes a blocking system call - one thread can access the kernel at a time, no parallel running one-to-one each user has a kernel - creating a user thread creates a kernel thread - more concurrency - parallelism - most common many-to-many allow many user threads to be mapped to a smaller or equal amount of kernels - two level mode: allows user to bound to a kernel context-switch between threads virtual memory space remains the same pthreads pthread_t -> thread ID pthread_attr_t -> set of thread attributes pthread_attr_init(&attr) ->sets attributes pthread_create() ->create thread - (&id, &attr, run, argv[1]) pthread_join(id, NULL) -> wait for thread pthread_detach(id) ->set thread to release resources java threads states new -> dead new->runnable (start()) runnable->runnings (run()) running->dead (end of execution) running->wait(sleep or wait) wait->dead CPU burst CPU execution starts then followed by I/O burst I/O burst I/O execution FIFO first in first out preemptive stop or pause a current scheduled task in favor of a higher priority task non-preemptive keeps the CPU until process releases when does CPU scheduling make decisions? running -> waiting running -> ready waiting -> ready terminated dispatcher module that gives control of the CPU to the process elected by short-term scheduler - switching context - switching to user mode - jumping to proper location in the user program to restart the program maximize or minimize: - CPU utilization - throughput - turnaround time - waiting time - response time - CPU util ->maximize -throughput ->maximize -TA time -> minimize - waiting time -> minimize - response time -> minimize throughput number of processes that are completed per time unit wait time amount of time process had to wait before finishing in the ready queue turn-around time burst time + wait time FCFS first come first serve the process that requests the CPU first is allocated to the CPU first advantages and disadvantages of FCFS advantages: - easily managed by FIFO queue disadvantages: - waiting time is long - convoy effect -> lower CPU util - non-preemptive, process will run until it finishes Gnatt char bar chart that illustrates a particular schedule SJF shortest job first when the CPU is available, it is assigned to the process that has the smallest next CPU burst advantages and disadvantages of SJF advantages: - waiting time decreases -throughput is high disadvantages: - cause starvation - elapsed time SRJF SJF with preemption - will preempt the currently executing running process is it has a shorter CPU burst SJF and priority the priority is the inverse of the next CPU burst -> larger the CPU burst the lower the priority internal properties determined by OS using factors such as time limits, memory requirements external properties assigned by administrators starvation indefinite blocking, a process that is ready to run but waiting for the CPU can be considered blocked aging increasing the priority of a process that has been waiting a long time Round Robin made for time-sharing systems uses time quantum used as circular queue - starvation free little's law n = λ x W n = average queue length λ = average arrival rate into queue W = average waiting time critical section part of program where memory is shared -> process may be changing things solution to race condition race condition several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place critical section problem only one process can be in the critical section at a time - design protocol to solve - each process must ask permission to enter critical section 3 requirements for critical section solution 1. mutual exclusion: if process Pi is executing in its CS, no other processes can be executing in their CS 2. progress: if no process is executing in its CS and there exist some processes that wish to enter their CS, the next selection of the processes that will enter the CS next cannot be postponed indefinitely 3. bounded waiting: a bound must exist on the # of times a process is allowed to enter their CS after a process has made a request to enter its CS atomic uninterruptible variables used in Peterson's algorithm and what are common in both processes? int turn -> indicates who turn it is to enter its CS boolean flag[2] -> indicates if a process is ready to enter the CS if flag[i]= true --> Pi is ready locking protecting CS through the use of locks mutex locks protect CS and prevent race conditions - process must acquire lock before entering CS -> acquire() - it will release lock when it exits CS -> release() -simplest semaphore int variable, accessed through only wait() and signal() deadlock two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes T or F without a hardware timer, preemption of processes for round robin scheduling is not possible true T or F for a set of processes involved in a race condition, the outcome depends on the order in which data accesses take place true T or F the CS is a segment of code where changes are made to resources shared by multiple processes true T or F solutions to the CS problem must target mutual exclusion but not necessarily bounded-wait false T or F in Peterson's solution, bounded wait is possible because the algorithm allows processes to take turn entering the CS true T or F a process executing an atomic instruction can be context-switched if it takes several clock cycles to complete that instruction, in the middle of that instruction false a solution to the CS problem does not have to satisfy which of the following requirements? a. mutual exclusion b. atomicity c. progress d. bounded waiting atomicity T or F race conditions are prevented by requiring that critical regions be protected by locks true preemption is when an OS moves a process between these states running->ready T or F all processes in UNIX are created using the fork() system call expect the initial one true Consider a Thread T1 that invoked method x, which resulted in the invocation of method y, which resulted in the invocation of z. How many frames exist on thread T1's stack? Do all stack frames on thread T1's stack must be the same size? 3, no a time-decayed exponential average of previous CPU bursts allows a scheduler to pick the process that will be most likely block on I/O soonest with soft affinity on a multiprocessor system, the scheduler will try to use the same processor for the same process but move it if another processor has no work can shortest job first result in starvation? yes can first come first serve result in starvation no can round robin result in starvation no can priority result in starvation (when priorities don't change over time) yes a process can be context-switched when it is executing an atomic operation supported by the CPUs ISA yes a process may have multiple unrelated CS yes In solutions to the CS problem, processes that are executing in their remainder section next make decisions about who gets to enter the CS next no, Processes {P0, P1, ..., Pn-1} are coordinating their accesses to a critical section where they make changes to common variables. It is OK for one of the processes to disregard the protocol for accessing critical sections and just directly access the critical section no dead lock cannot access resources