Flashcards
Operating Systems - Part 3 & 4
Cards in this deck (40)
- 1Process (loca) address spaceOS Kernel Space (user code cannot read from nor write to these addresses otherwise Segmentation Fault) – Stack (automatic variables (local to a functions scope)) – Heap(dynamic memory allocation through malloc/new free/delete) – BSS(unitialized static variables, filled with 0s) – Data(static variables explicity initialized – text (binary image of process (eg bin/ls)
- 2Processes need to communicate but must maintain system integerity 3 problems?1. How to share info between processes
2. How to prevent processes getting in each others way
3. How to ensure correct sequencing - 3Mechanism shared memory examplego over diagram and lecture
- 4Race conditions and critical sections: processes often work together by sharing common storage eg print service:User process adds name of a file to shared print spooler file. Printer service periodically checks spooler file. If filenames in spooler file, printer service: removes next filename from spooler file list, gets file from filesystem and sends file to printer.
- 5Daemontype of computer program that runs in the background, performing various tasks without direct interaction from user
- 6Print spooler examplesPrint spooler examples: Printer daemon: read control file out value. Remove filename at spooler file slot/line. Get file and send to printer. Update out value.
User processes: read control file in value. Put new filename at spooler file slot/line. Update in value. - 7Solution for spool file sequence for 2 user processesSolution: mutual exclusion. Problem is B using shared data before A finished. Need to prevent more than one process reading and writing shared data at same time. Need mutual exclusion in critical region (where process accesses shared data (eg access to ctrl_file or spool_file (critical section))
- 8Critical regions: 4 conditions for communicating processes to share data correctly and efficiently:1. No 2 proccess simultaneously in their critical regions
2. No assumptions made about number or speed of CPU’s
3. No process outside a critical region may block another process
4. No process should wait forever to enter critical region - 9Mutual exclusion by disabling interruptseach process disables all interrupts just after entering critical region. No interrupts == no clock interrupts. No other process can be scheduled and current process has exclusive access to CPU. Simple solution. Kernel may do it for critical operations ie updating list of ready processes.
- 10Mutual exclusion with busy waiting: 3 approachesBusy waiting == loop doing nothing in program code.
Approach 1: lock variables: have single shared (lock) variable initialized to 0. When process wants to enter critical region it tests lock. Acquire lock set to 1 otherwise wait. (flaw: think if 2 at onces how decide or how wait work – can do priority? – look at lecture). Moves race condition.
Approach 2: strict alternation. Avoids race conditions but doesn’t satisfy condition 3: process outside critical region can block other processes.
Approach 3: Peterson’s solution (usage): functions enter_region and leave_region demarcate access to critical region and operations on share data. 2 processes with ids 0 and 1.
Global variables: turn and interested array of 2 elements to indicate process interest ( 1 interest, initialized to {0,0} - 11Perterson's solution truth tablePeterson’s solution truth table: process only want to be in critical region if interested element is set. Process busy waits if interested and turn is set to their id and other process is interested.
- 12Priority inversion problemPriority inversion problem: busy waiting wastes CPU and can result in priority inversion.
Consider 2 processes: H with high priory and L with low priory. Sceduling rule: run H whenever ready. 1. H is blocked on I/O outside critical region (can’t run) L is in critical region. I/O completes, H becomes read. H runs, L is put on ready queue (not running). H begins busy waiting for L to leave critical region but L is never rescheduled because H is busy on processer doing nothing. - 13Mutual exclusion without busy waitingMutual exclusion without busy waiting: use IPC primitives to block processes until safe to enter critical region. The producer-consumer or bounded buffer problem: - 2 processes share fixed side buffer – producer process puts items in – consumer process takes items out – if buffer is full, producer cannot add item, if buffer is empty consumer cannot take item.
- 14Lost wakeupsLost wakeups: assume buffer empty and consumer reads count as 0. Before consumer does count==0 and calles sleep(), scheduler preempts consumer and runs producer. Producer adds item, count to 1 and calls wakeup(consumer but consumer is not asleep just preempted. Consumer runs again, checks count(0) and calls sleep(). Producer continues to add items until buffer full then calls sleep(). Now both processes are asleep and will never receive wakeup. A wakeup sent to process that is not yet asleep is lost.
- 15Dijkstra’s semaphore solution to lost wakeupsDijkstra’s semaphore solution to lost wakeups:
semaphore – special counter variable with 2 atomic operations:
- down(semaphone): if value > 0, decrement value and continue. If value == 0 sleep without completing down. Up(semaphore): increment value. If any process asleep on value, OS chooses a process to wake and completes its down. Semaphore value changes after wakeup. Down can block up cannot. - 16Sempahore solution to producer-consumerSempahore solution to producer-consumer: use 2 semaphores: - full: to count the number of slots that are full – empty: to count number of slots empty – mutex: gurad buffer – for mutual exclusion. Consumer and producer annot access buffer at same time.
Initialisation: full = 0, empty = N (total number of slots, mutex to 1 (buffer available) - 17Problems with semaphoresProblems with semaphores: solve busy waiting and lost wakeup problems but are low-level and error prone. Incorrect order of operations can lead to deadlock. Solution: introduce higher level, programming language constructs called mutexes and monitors.
- 18MutexesMutexes (binary semaphores): only ever has value 0 (locked) or 1 (unlocked). Provides mutual exclusion to a shared resource.
- 19MonitorsMonitors: only one active process in a monitor at a time. Monitor Buffer insert(item) {} item remove {}
compiler translates monitor into lower level system calls on sempahores and mutexes. Injects semaphore calls in insert and remove funcitons. Producers and consumers written in terms of monitor functions. - 20Implementing semaphoresImplementing semaphores: implement up and down as system calls: OS disables interrupts, tests semaphore value, updates if necessary, puts calling process to sleep, os enables interrupts.
- 21Why schedule? Multiprocessing – have to decide which process to run ( or schedule ). 4- Early batch systems – run next job on tape.
- Timesharing sytems – multiple users waiting for service
- PCs with one user at a time do not reduce complexity – may be one foreground task but many background processes
- Increase in power and number of processors doesn’t remove need to schedule processor time - 22Process Behaviro - fall into 2 categories:Almost all processes alternate bursts of computation with I/O requests and fall into 2 categories:
1. Compute bound – most time spent compution (long CPU bursts)
2. I/O bound – most time waiting for I/O (short CPU burst) - 23When to make scheduling decision: 2- Required: process exits, process block on I/O (or waiting for a resource)
- Normally: when new process created, I/O interrupt occurs, clock interrupt occurs. Decide if current process has run for long enough. - 24Non-preemptive schedulingNon-preemptive scheduling – pick process and let it run until it blocks or voluntarily gives up processor
- 25Preemptive schedulingPreemptive scheduling – pick process and let it run for a maximum time interval
- 26Schdeuling algorithm goals: all systems: 3- Fairness
- Policy enforcement – give priory to critical processes
- Balance – keep all parts of system busy - 27Goals batch systems 3- Maximize throughput (jobs)
- Minimize turnaround (average wait for output)
- Maximize utilization – less important - 28goals interactive ystsems 2- Optimize response time – favour foreground tasks
- Proportionality – attempt to meet user expectations of how long tasks should take - 29Goals: real-time systesms- meet deadlines – avoid loosing time-critical data
- Predictability – avoid quality degradation - 302 types of batch system sheduling alogirthmsFCFS
SJF - 31Describe FCFS. Give 1 adv 1 dis- First come First Served FCFS:
o Non preemptive
o Assign processes to CPU in order they request it
o Single queue of ready processes
o First job runs until blocks or terminates
o New jobs put on end of ready queue
o Adv: simple and easy to program
o Dis: compute bound processes dominate - 32Describe SJF- Shortest Job First SJF:
o Nonpreemptive
o Known runtimes
o All jobs equally important
o Pick shortest job first
o Probably optimal - 33LectureTable things – lecture – calculate turnaround time
- 34Shortest remaining time next 4- Preemptive ersion of shortest job first
- Pick process with shortest remaining time
- On arrival of new job: compare total time to current process’ remaining time. If new process needs less time, preempt current process and run new job.
- New short jobs get good service - 35Interactive system scheduling algorithjm goal?Interactive system scheduling algorithm:
maximize response time and proportionality - 36Round-robin scheduling 4- Each process assigned a time interval (quantum)
- If still running at end of its quantum, preempt and give CPU to another process
- Maintain list of ready/runnable processes, preempted processes are put at end of list.
- In large enough time perion N processes will have 1/N of processor time - 37Go over quantum is key round robin parameter – questions. Cases. Tradeoffs of quantum being too short or too longTrade-off: quantum too short: frequent process switches (wastes CPU
Quantum too long: poor response to short interactive requests - 38Priority Scheduling: give CPU to runnable process with highest priority Preempt process if higher priority process is ready. Problems: 2- high priority processes could run indefinitely
- if do not prioritise I/O bound processes, will idly consume memory waiting for both I/O and CPU – better to allow them to use CPU to initiate next I/O request - 39One scheduling queue per priority class: 3- as long as there are processes on a class 4 queue run them before running processes in class 3…
- use Round robin scheduling within a priority class
- must adjust priorites to ensure processes in lower priority classes run - 40Policy versus mechanism: assuming processes belong to dif users: shedulers job is to ensure fairness… Solution:Solution: separate cheduling mechanism from scheduling policy – allow parameterization of scheduling by user processes ie kernel provides call for parent processes to set priorities among children. Mechanism provided by knernel, policy determined by user process
Information
- Description
- Uni Uni Second Level (Software Systems) Flashcards on Operating Systems - Part 3 & 4, created by HRYN red on 16/12/2024.
- Created by
- HRYN red
- Views
- 3
- Rating