f6j5QJ6D

1---------------------------------
2CS 143A
3---------------------------------
4
5What is an operating system?
6OS is the software that acts as an intermediary between the applications and computer hardware
7
8
9Operating System Roles:
10
11- Referee:
12Allocation of resources among applications, users
13Isolation of different applications, users from each other
14Communication between users, applications
15
16- Illusionist:
17Each application appears to have the entire machine to itself
18Infinite number of processes, (near) infinite amount of memory, reliable storage, reliable network transport
19
20- Glue:
21Libraries, user interface widgets
22Reduces cost of developing software
23
24
25OS Challenges:
26
27- Reliability
28Does the system do what it was designed to do?
29
30- Availability
31How much time does the system spend working and other metrics like
32Mean Time to Failure (MTTF), and Mean Time to Repair (MTTR)
33
34- Security
35Can the system be compromised by an attacker?
36
37- Privacy
38Data is only accessible to authorized users
39
40- Performance
41-- Latency/response time : How long does an operation take to complete?
42-- Throughput : How many operations can be completed per unit time?
43-- Overhead : How much extra work is done by the OS?
44-- Fairness : How equal is the performance received by different users?
45-- Predictability : How consistent is it in its performance over time?
46
47- Portability
48For programs : Application Programming Interface
49For the Kernel : Hardware abstraction layer
50
51
52---------------------------------------------------------- Consider reading up on the history of Operating Systems from the slides as well ----------------------------------------------------------------------------
53
54
55How is I/O sped up through DMA?
56DMA (Direct Memory Access) allows data to be moved directly between I/O devices and memory, freeing up the CPU to work on other processes
57
58 
59I/O Completion in Batch Processes : How do we know when I/O is complete?
60
61- Polling
62Device sets a flag when it is busy
63Program tests the status of the flag in a loop waiting for completion of I/O
64
65- Interrupts
66Device interrupts the CPU on completion of I/O to jump to another instruction that handles the Interrupt sub-routine
67CPU jumps back to the code it was executing after the interrupt has been processed
68
69Multiprogramming:
70
71- Use interrupts to run multiple programs simultaneously : When a program performs I/O, instead of polling, let the CPU execute another program until an interrupt is received
72- Requires secure memory and I/O for each program
73- Requires intervention if a program runs into an infinite loop
74- Requires CPU scheduling to determine the next job to run
75
76CPU Execution Cycle:
77
78- Fetch instruction from memory
79- Decode the instruction 
80- Execute the instruction
81- Write the result to memory
82- Increment the program counter and find the next instruction
83- Repeat
84
85I/O Devices and Buffer:
86
87- I/O Devices and the CPU execute concurrently
88- Every controller is responsible for a type of I/O devices and every controller has a local buffer. I/O is from the device to the local buffer of a controller
89- CPU is responsible for moving data from/to main memory to/from the local buffers
90
91
92Interrupts:
93
94- Interrupts transfers control to the interrupt service routine ; Interrupt Service Routine : Segments of code that dictate the actions to be taken for an interrupt
95
96- Determining the type of interrupt:
97Polling: The same interrupt handler is called for all interrupts, all devices are then polled to see where the interrupt came from
98Interrupt Vector table: different interrupt handlers are called for different interrupts
99
100- During interrupt handling, the OS preserves the state of the CPU : Stores registers and the program counter 
101
102What happens to a new interrupt when the CPU is handling one interrupt?
103- Incoming interrupts can be disabled (masked) when one interrupt is currently being processed, and the new interrupt may either get lost of placed on a buffer or delivered later
104- Incoming interrupts can also be delivered on the spot, creating nested interrupts
105
106
107
108- In Direct Memory Access, device controllers transfer blocks of memory directly from local buffers to main memory without CPU intervention
109- The CPU is interrupted when the memory transfer is complete
110
111
112What is a process?
113A process is an instance of a program running with limited rights
114- Threads: A sequence of instructions within a process
115- Processes also have rights associated with it : 1) memory that the process can access 2) other permissions the process has like what system calls it can make, what files it can access etc.
116
117
118Dual Mode Operation:
119
120- Provide hardware support to differentiate between at least two modes of operation
1211. User Mode : Execution is done on behalf of the user
1222. Kernel Mode : Execution is done on behalf of operating system
123- "Privileged" instructions are only executable in kernel mode
124- Execution privileged instructions in user mode "traps" into kernel mode
125
126- Another bit called a Mode bit is added to computer hardware to indicate the current mode: User mode or kernel mode
127- When an interrupt occurs, the hardware switches to kernel mode
128
129
130The Timer:
131
132- Sometimes processes need to be controlled from execution indefinitely, in which case we make use of a timer that interrupts the process after a certain period of time and returns control to the processor
133- The timer is also used to help implement timesharing
134- The timer is also used to compute the current time
135- Programming the timer can only be done in the kernel since it requires privileged instructions
136
137
138Address translation and Memory Protection Cycle:
139
140- The processor takes a virtual address and attempts to translate it
141- If the translation is invalid, an error is raised
142- If the translation is valid, the translation is a physical address that is used to locate the address in memory
143- Data from the physical address is sent back to the processor
144
145Memory Protection:
146
147- When a process is running, only memory within that process space should be accessible
148- When executing in kernel mode, the kernel has unrestricted access to all memory
149
150
151Memory Protection : Base and Bounds:
152
153- To provide memory protection, add two registers to determine the range of legal memory addresses: 
154Base Register: Hold the memory address of the smallest legal memory address
155Limit Register: Contains the size of the range
156- Memory outside the range is protected
157
158Implementation of Base and Bounds?
159
160- The virtual address in the processor is added to the base address. 
161- If the sum of the address is greater than the bounds, an exception is raised 
162- Else, the sum of the addresses form the physical address used to access physical memory
163
164The ability to load the base and limit registers are privileged instructions
165
166
167I/O Protection : All I/O instructions are privileged instructions
168Given that these instructions are privileged instructions, how do users perform I/O?
169- Via system calls - The method used by a process to request action by the operating system
170
171System Calls : User code can issue a syscall, which traps into kernel mode. Kernel handles the syscall
172
173User process Execution --> User process calls system calls --trap--> kernel mode executes system call --return--> return to user process from system call
174
175
176Storage Device Hierarchy:
177- Registers
178- cache
179- Main memory
180- solid-state disk
181- hard-disk
182
183Monolithic vs Microkernel OS:
184
185- Monolithic OSes have large kernels with lot of components
186- Microkernels move as much from the kernel into "user" space
187
188
189------------------------------------------------------------------------------------------------Worth trying to understand monolithic and microkernel OS ---------------------------------------------
190
191OS Task : Process management
192
193- OS is responsible for the following management activities:
194Process creation and deletion
195Process suspension and resumption
196Process synchronization and interprocess communication
197Process interactions - deadlock detection, avoidance and correction
198
199
200OS Task : Memory management
201
202- OS is responsible for:
203Allocation and deallocation of memory to processes
204Managing multiple process within memory - keep track of which parts of memory are used by which processes and also manages the sharing of memory between processes
205Determining which processes to load when memory becomes available
206
207
208Another OS task is : Secondary Storage and I/O Management
209
210OS Task : File Management
211
212- OS is responsible for:
213File creation and deletion
214Directory creation and deletion
215Supporting primitives for file/directory manipulation
216Mapping files to disks (secondary storage)
217
218Another OS Task : Protection and Security
219
220
221
222----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
223
224
225Our assumption will rest on processes having only one thread of execution, thereby the process execution takes place in a sequential fashion
226
227Process =? Program
228
229A process is one instance of a program in execution
230A program can invoke more than one process
231
232
233Process States:
234
235- New : The process is being created
236- Ready : The process is waiting to be assigned to a processor
237- Running : The instructions of the process are being executed
238- Waiting : The process is waiting for an event to occur
239- Terminated : The process is finished execution
240
241Process changes:
242
243New --> Ready : Process admitted
244Ready --> Running : Scheduler dispatch
245Running --> Ready : Interrupt
246Running --> Waiting : I/O or event wait
247Waiting --> Ready : I/O or event completion
248Running --> Terminated : exit
249
250
251Process Control Block:
252
253Contains the information associated with each process
254- Process State (eg) Running, waiting, etc.
255- Program Counter - location of next instruction to execute
256- CPU Registers
257- CPU Scheduling Information
258- Memory Management Information
259- Accounting information
260- List of all open files
261
262
263Enabling Concurrency and Protection in the OS
264
265Concurrency:
266Give out CPU time to different processes (Scheduling) - Only one process running at a time, Give more CPU time to important processes
267
268Protection:
269Give pieces of resources to different processes (Protection) - Controlled access to non-CPU resources
270
271What is a context switch?
272Operation that switches CPU from one process to another process
273
274How to enable concurrency in context switching:
275The CPU saves the state of the current process to the PCB and loads the state of the new process from the PCB
276
277The time it takes to do context switching is overhead:
278- System does not do any useful work when context switching
279- Overhead sets minimum practical switching time; can become a bottleneck
280
281
282
283Process Scheduler 
284- Selects among available processes for next execution on the CPU
285- Maintains scheduling queues of processes
286-- Job queue: set of all processes in the system
287-- Ready queue: set of all processes residing in main memory, ready and waiting to execute
288-- Device queue: set of processes waiting for an I/O device
289- processes migrate among the various queues
290
291
292Schedulers
293
294- Short term Scheduler : Determines which process is to be executed next and allocates it to the CPU
295Sometimes the only scheduler in a system
296Called very frequently and works very fast (milliseconds)
297
298- Long term Scheduler : Determines which process to add to the ready queue
299Invoked infrequently and is relatively slow (seconds, minutes)
300Determines the degree of multiprogramming
301
302Processes can be described as either : 1) I/O Bound processes - which spends more time doing I/O than computations (many short CPU bursts) or 2) CPU-bound processes - which spend more time doing computations (few long CPU bursts)
303Long term scheduler strives for good process mix
304
305
306
307Process Creation:
308
309- Processes are created by other processes
310- Processes that create other processes are called parent processes, the created process is called a child process
311- The result is a tree of processes
312
313
314What does it take to create a new process?
315- Must construct new PCB : not very expensive
316- Must set up the address space ( e.g set up new page tables for address space) : More expensive
317- Copy data from parent process : Expensive
318- Copy I/O state - medium expense
319
320
321
322What is multithreading?
323A single program made up of a number of different concurrent activities
324
325Single and Multithread processes:
326
327- Code, Data and files are shared among threads
328- Registers and stacks are private to each stack
329
330- Threads encapsulate execution and concurrency
331- Processes encapsulate protection
332
333- In a multi-threaded process, while one thread is blocked and waiting, a second thread in the same task can run
334
335
336Thread State
337
338- State shared by all threads in the process
339- State private to each thread
340Kept in TCB (Thread Control Block)
341Threads also have states of execution ( new, ready, running, etc.)
342
343- Only one thread can run on a CPU at a time, but switching between threads does take up any memory management related work only a register set switch
344
345
346Types of Threads:
347
348- Kernel-supported threads
349- User level threads
350There exist some hybrid approaches that involve implementation of both user-level and kernel-supported threads
351
352
353Kernel Threads
354
355Supported by the kernel:
356- threads created and managed directly by the kernel
357- Threads can run or block independently
358- One process may have several threads waiting on different things
359
360Downside: Expensive for the thread to keep having to cross into kernel mode for scheduling
361
362
363User Threads:
364
365Supported above the kernel, via a set of library calls at the user level : may have several user level threads per kernel thread
366- One advantage of user threads is that they are cheap and fast because they do not need to cross over into the kernel for scheduling.
367- A disadvantage however, is that only one thread at a time per kernel thread, these threads will not run in parallel
368
369Multithreading models:
370
371- One to one : One user level thread mapped to a kernel thread
372- Many to one : Multiple user level threads mapped to one kernel thread
373- Many to many : Allows many user level threads to be mapped to one kernel thread
374
375Two Level Model:
376
377It is similar to many-to-many, except that it allows a user-level thread to be BOUND to a kernel thread
378
379
380What is a signal?
381Signals are used in UNIX systems to notify a process that a particular event has occurred
382
383
384A signal handler is used to process signals:
385- Signal is generated by a particular event
386- Signal is delivered to process
387- Signal is handled by either default handler or user-defined handler
388
389
390
391Ways of delivering signals to a multithreaded process?
392- Deliver the signal to every thread in the process
393- Deliver the signal only to the thread to which the signal applies
394- Deliver the signal to a specific thread designated to receive signals
395- Deliver the signal to certain threads in the process
396
397
398Thread Pools:
399
400Create a number of threads in a pool awaiting work
401Advantages:
402- Usually faster to service a request with an existing thread than to create a new one
403- Allows the number of threads in the application(s) to be bound to the number of threads in the pool
404
405
406Thread Local Storage:
407
408TLS (Thread Local Storage) allows each thread to have its own copy of data
409- Different from local variables in that TLS is visible across all functional invocations and is not local to one single function
410
411
412Multi- Definitions:
413
414Multiprocessing: Multiprocessors/CPUs
415Multiprogramming: Multiple jobs/processes
416Multithreading: Multiple threads per process
417
418
419Interprocess Communication:
420
421- Processors within a system may be independent or cooperating
422Processes may cooperate with each other for many reasons:
423- - Sharing information
424- - Speed up computation
425- - Convenience
426- - Modularity
427
428Cooperating processes thus need to communicate and share data. For this purpose, they use Interprocess communication (IPC)
429
430Two models of IPC:
431- Shared memory
432- Message passing
433
434
435Shared Memory:
436
437- An area of memory shared among the processes that wish to communicate
438- The communication is under the control of the processes not the operating system
439- Issues of synchronization of actions of user processes when they access shared memory
440
441
442
443Producer-Consumer problem:
444
445Paradigm for cooperating processes, producer processes produces information that is consumed by consumer processes
446
447
448Message Passing
449
450Mechanism for processes to communicate with each other without having to access shared data
451IPC facility provides two options:
452- Send(message)
453- Receive(message)
454
455The message size is usually fixed or variable
456
457
458If processes P and Q wish to communicate, they need to
459- Establish a communication link between them
460- Exchange messages via send/receive 
461
462
463Direct Communication
464
465Processes must name each other explicitly:
466- Send(P, message)
467- Receive(message, Q)
468
469Properties : 
470(1) Links are established automatically
471(2) Each link is associated with a pair of processes
472(3) Between each pair there exists exactly one link
473(4) Links may be either unidirectional or bi-directional
474
475
476Indirect Communication
477
478messages are directed and received from mailboxes (usually a port)
479- Processes must share a common mailbox for a link to be established 
480- each mailbox will have a unique id
481
482Properties:
483(1) Links are established only if processes share a common mailbox
484(2) Each link may be associated with multiple processes
485(3) There may be more than one link between processes
486(4) Links may be either unidirectional or bi-directional
487
488
489Operations:
490- Create a mailbox
491- Send or Receive a message to/from a mailbox
492- Destroy a mailbox
493
494
495Synchronization:
496
497Message passing may be either blocking or non-blocking
498Blocking is considered synchronous
499- blocking send: the sender is blocked until the message is received 
500- blocking receive: the receiver is blocked until a message is blocked
501Non blocking is considered asynchronous
502- non-blocking send: the sender can send a message and continue
503- non-blocking receive: the receiver receives: 1) a valid message or 2) a null message
504
505If both send and receive are blocking, we have a rendezvous
506
507
508Buffering:
509
510Queue of messages attached to the link is implemented in one of three ways:
511- Zero capacity: no messages are queued on the link, sender must wait for receiver 
512- Bounded Capacity: Finite length of n messages. Sender must wait if link full
513- Infinite capacity: Infinite length, sender never waits
514
515
516Sockets
517
518- A socket is defined as an endpoint for communication
519- it is the concatenation of an IP address and a port ( a number included at the start of message packets to differentiate network services on a host )
520- Communication consists between a pair of sockets
521
522
523Remote Procedure Calls
524
525- RPC abstracts procedure calls between processes on networked systems
526Stubs: Client side proxies for the actual procedure on the server
527- The client-side stub locates the server and marshalls the parameters
528- The server side stub receives this message, unpacks the marshalled parameters and performs the procedure on the server
529
530Pipes
531
532- acts as a conduit for communication between two processes
533Ordinary pipe: cannot be accessed from outside the process that created it. Usually created by a parent process for communication with the child process that it created
534Named pipe: can be accessed without a parent-child relationship
535
536
537Ordinary Pipes:
538
539- Ordinary pipes allow communication in typical producer-consumer style
540- producer writes to one end of the pipe (the write end of the pipe)
541- consumer reads from other end of the pipe (the read end of the pipe)
542- Ordinary pipes are thus unidirectional
543- Require parent-child relationship between communicating processes
544
545
546Named pipes:
547
548- Named pipes are much more powerful
549- named pipes are bidirectional
550- No parent child relationship is necessary for the communicating processes 
551- Several processes can use the named pipe for communication
552- is provided on both UNIX and windows systems
553
554
555
556
557Basic concepts of CPU Scheduling
558
559- Maximum CPU utilization obtained with multiprogramming
560- CPU - I/O Burst cycle : Process execution consist of a cycle of CPU execution and I/O wait
561
562Issues to consider in CPU Scheduling:
563
564- I/O Boundedness
565Short burst of CPU before blocking for I/O
566- CPU Boundedness
567Extensive use of CPU before blocking for I/O
568- Frequency of preemption
569- Urgency and priorities
570- Process execution time
571- Time sharing : amount of execution time process has already received 
572
573Levels of Scheduling
574
575- High level scheduling or Job Scheduling
576Selects jobs allowed to compete for CPU and other system resources
577- Low level (CPU) Scheduling
578Selects the ready process that will be assigned for the CPU
579Ready queue contains PCBs of processes that are ready to be dispatched
580
581
582CPU Scheduler :
583
584Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them
585
586
587Non-preemptive scheduling:
588- Once CPU has been allocated to a process, the process keeps the CPU until:
589The process exits the CPU
590The process switches to the waiting state
591
592Preemptive Scheduling:
593- The process can be interrupted and must release the CPU
594
595
596CPU Scheduling Decisions:
597
598- CPU may make schedule decisions when a process:
599- -  switches from ready to running state (non-preemptive)
600- - switches from running state to ready state (preemptive)
601- - switches from waiting state to ready state (preemptive)
602- - terminates (non-preemptive)
603
604
605Dispatcher:
606
607Dispatcher module transfers control of the CPU to the process that is selected by the short-term scheduler
608This involves:
609- switching contexts
610- switching into user mode
611- jumping to the proper location in the user program to restart that program
612Dispatcher latency:
613- time it takes for the dispatcher to stop one process and start another running
614- Dispatcher needs to be fast
615
616
617Scheduling Criteria:
618
619- CPU utilization
620keep the CPU as busy as possible
621
622- Thoroughput
623the number of processes that complete their execution per time unit
624
625- Turnaround time
626amount of time to execute a particular process from its entry time
627
628- Waiting time
629amount of time a process has been in the waiting queue
630
631- Response time ( in timesharing systems )
632amount of time it takes after a request was submitted to when a response was first (not final output) produced
633
634
635Optimization criteria:
636
637- Max CPU utilization
638- Max Thoroughput
639- Min Turnaround time
640- Min Waiting time
641- Min response time
642
643
644
645First Come First Served Scheduling (FCFS):
646
647- Process that submits a request for the CPU FIRST is allocated to the CPU first
648Non-preemptive algorithm
649- implemented using a FIFO queue:
650New processes are added to the tail of the queue
651The CPU selects a process to execute from the head of the queue
652
653
654
655Shortest Job First Scheduling : 
656
657Scheduling algorithm that picks processes based on their CPU burst times; in that it pics the process with the least burst time next
658Two schemes:
659Non-preemptive:
660- once the process has been allocated to the CPU, the process will be executed until it has finished execution and cannot be preempted
661Preemptive:
662- When a process is executing and another process enters that has a lower CPU burst time, the currently executing process is preempted and the newer one is executed instead. Also called Shortest Remaining Time First
663
664SJF is optimal - gives minimum average waiting time for a given set of processes.
665The only difficulty is knowing the length of the next CPU request
666
667
668Determining length of Next CPU Burst:
669
670- One can only estimate the length of the next CPU burst
671- Use the lengths of previous CPU bursts and perform exponential averaging
672tn = actual value of nth burst
673Tn+1 - predicted value of next CPU burst
674alpha = 0, 0<=1<=alpha
675Define 
676Tn+1 = alpha(tn) + (1-alpha)Tn
677
678at alpha = 0, recent history does not count
679at alpha = 1, only the actual last CPU burst counts
680Commonly, alpha is set to 0.5
681
682
683Priority Scheduling :
684
685- A priority number is associated with each process and is usually an integer. This number may be based on:
686Cost to user
687Importance to user
688Age
689% of CPU time used in last X hours
690- CPU is allocated to process with highest priority
691preemptive
692non-preemptive
693
694
695Shortest Job first is a type of priority scheduling where the priority value is the next CPU burst time
696Problem - Starvation : Low priority processes may never execute
697Solution - Aging: As a process spends more time waiting its priority increases
698
699
700Round Robin (RR):
701
702Each Process is allocated a fixed amount of CPU time and the process is then preempted and added to the end of the ready queue
703- The amount of CPU time allocated is usually a time quantum between 10-100 milliseconds
704For n processes, each process usually gets 1/nth CPU time for a time chunk of Q
705- if n is too large, FIFO behaviour starts getting executed
706- if n is too small, there is high context switching overhead
707
708
709Multilevel Queue:
710
711- Ready queue is partitioned into separate queues
712- Different scheduling algorithms are used on each queue
713- Processes assigned to one queue permanently
714- Scheduling must be done between the queues 
715Fixed priority: serve all from foreground, then from background - possibility of starvation
716Time slice: each queue gets some CPU time that it schedules 
717
718
719Multilevel Queue scheduling priority order:
720
721- system processes  <-- highest priority 
722- interactive processes
723- interactive editing processes
724- batch processes
725- student processes  <-- lowest priority
726
727
728Multilevel feedback queue:
729A process can move between the queues
730- aging is implemented this way
731Parameters for a multilevel feedback queue scheduler:
732- The number of queues 
733- The scheduling algorithm used for each queue and between queues
734- Which process to promote to another queue
735- Which process to demote to another queue
736- the method for determining which queue a process will enter when a new process needs servicing
737
738
739Thread Scheduling:
740
741- When threads support scheduling, threads are scheduled instead and not processes
742- The CPU scheduler schedules kernel threads
743- In many-to-one and many-to-many, thread library schedulers user-level threads to run on a kernel thread
744
745
746Multiple Processor Scheduling:
747
748- Scheduling of processes becomes more complex when there are multiple processors involved:
749
750Symmetric Multiprocessing (SMP):
751- each processor dispatches a job from the ready queue
752- there is one common ready queue of all processes for the processors, or each has its own private queue of ready processes
753- homogeneous processors within a multiprocessor 
754- currently the most common multiprocessor set up
755- Difficulties : access to shared data structure and making sure that all processes are scheduled and that no process is scheduled by separate processors
756
757Asymmetric Multiprocessing:
758- master-slave system where one processor schedules the other processors
759- Only one processor accesses the data structure, alleviating the need for data sharing
760
761
762Multicore processors:
763
764- there has been a recent trend of placing multiple cores on the same processor
765- faster and consumes less power
766
767
768Hyperthreading:
769
770- multiple threads per core
771Takes advantage of memory stall to make progress on another thread when memory retrieve happens
772- One CPU core looks like two cores to the operating system with hyperthreading
773
774
775Methods of algorithm evaluation:
776
777- Deterministic evaluation:
778uses a pre-determined workload and defines the performance of each algorithm for that workload. Too specific, requires exact knowledge to be useful
779
780- Queuing Models and Queuing Theory:
781Make use of CPU and I/O burst times and knowing arrival and service rates - can compute utilization, average queue length, average wait time, etc. 
782
783Other techniques: simulations, implementation
784
785
786Producer-Consumer problem:
787
788Paradigm for cooperating processes
789- Producer processes produce information and consumer processes receive the information
790We need buffer of items that can be filled by producer and emptied by consumer
791- Unbounded buffer: this buffer places no practical limit on the amount of information it can hold. Consumers may wait, producers never wait.
792- Bounded buffer: this buffer has a limit to the amount of messages/information it can hold. Consumers have to wait for new information and producers will wait if the buffer is full
793Producers and consumers must synchronize
794
795
796Problem with shared memory solution to the Bounded Buffer problem
797
798- The problem with this solution to the bounded buffer problem is that at most n-1 items are allowed in the buffer at the same time
799
800Solution to the problem is above ( the need to have N items in the buffer ) is to initialize a variable called counter that keeps track of the number items in the buffer
801- incremented when the producer adds an item
802- decremented when the consumer removes an item
803
804Problems with this solution (lol wtf):
805
806- Access to shared memory between concurrent processes can result in data inconsistency
807- To protect data consistency, there needs to be mechanisms in place that ensure the orderly execution of cooperating processes
808
809Atomic operations:
810
811Shared data statements that can cause inconsistency problems like:
812counter++
813counter--
814must be executed atomically
815
816Which means the operation must run to completion or not at all.
817(done by assigning value to register and then increment the register and then assigning it back to counter)
818
819
820Race condition:
821
822If threads are working on separate threads, we dont need to worry about race conditions
823However, there can be race conditions if we have shared data ; where one variables value is non deterministic because it can one of numerous values depending on the order of execution of the threads statements
824
825
826Critical Section Problem:
827
828Consider a set of n processes competing to access shared data
829Each process has a critical section segment of code ; where in this section it updates variables, changes tables, writes to files, etc.
830At any given time, only process should be allowed to be in its critical section
831This problem is to design protocol to achieve/solve this
832Each process must ask for permission to enter the critical section in its entry section, and then may follow critical section with exit section, and then remainder section
833
834
835Requirements of the critical section problem:
836
837Mutual Exclusion : if one process is in its critical section, no other process must be allowed to be in its critical section
838Progress : If no process is currently in its critical section and there are processes requesting to access their critical section, then the selection of the processes that will enter its critical section cannot be postponed indefinitely 
839Bounded Waiting : a bound must exist on the number of times processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
840
841Assumptions:
842- Assume that processes execute their critical section at a nonzero speed, that is every process finishes execution of critical section once it enters
843- There is no relative speed between processes
844- A process may be stuck in an infinite loop in its remainder section (eg) non terminating while loop
845
846
847Synchronization Hardware:
848
849Many software based solution like Peterson's solution and Bakery Algorithm may not work on modern day computers because of how they perform basic machine level instructions (eg out of order execution)
850Many systems provide hardware support for implementing the critical section
851Solutions based on idea of locking :-
852
853do { acquire lock; 
854critical section;
855release lock;
856remainder section
857} while (TRUE);
858
859
860We need atomic execution
861- atomic = non-interruptible
862To do this on uniprocessors we can disable interrupts
863- currently running code would execute without preemption
864- too inefficient for multiprocessors systems - operating systems might use this but not broadly scalable
865Modern machines provide special atomic hardware instructions
866- either test memory word or set memory value
867- or compare and swap the contents of two memory words
868
869
870test_and_set instruction
871
872boolean test_and_set ( boolean *target )
873{
874boolean *rv = *target;
875*target = TRUE;
876return *rv;
877}
878- executed atomically
879- returns the original value of passed parameter
880- sets the new parameter value to TRUE
881
882
883compare_and_swap instruction
884
885int compare_and_swap(int *value, int expected_value, int new_value)
886{
887int temp = *value
888
889if ( *value == expected ) *value = new_value;
890return temp
891}
892
893- executed atomically
894- returns the original value of passed parameter
895- Set the variable value to be the value of the passed parameter new_value if value == expected_value. The swap only takes place under this condition
896
897
898Mutex locks:
899
900Previous solutions discussed are too complication for application programmers
901OS designers usually design software tools to help with the critical section problem
902The simplest ones are called mutex locks
903To protect a critical section, a process must acquire() a lock and then release() the lock when it leaves the critical section
904- Calls to these functions return a boolean value
905Calls to acquire() and lock() must be atomic
906- usually implemented using atomic hardware instructions
907- - but this solution requires busy waiting
908- - this lock is therefore called a spinlock
909
910acquire()
911{
912while (!available); // busy wait
913available = false;
914}
915
916release()
917{
918available = true;
919}
920
921
922Semaphores:
923
924Semaphore S - integer variable (non-negative)
925- Semaphores are used to represent number of abstract resources
926Can only be accessed via two atomic operations:
927- wait(S):
928while ( S <= 0 );
929S--;
930
931- signal(S): S++;
932
933P or wait used to acquire a resource, waits for semaphore to become positive and then decrements it by 1
934V or signal used to release a resource and increments the semaphore by 1 wake up any waiting processes if any
935If P is performed on a count of <= 0, process must wait for V or the release of a resource
936
937
938
939Semaphores as a general Synchronization tool
940
941- Execute B in Pj only after A has executed in Pi
942- initialize semaphore flag at 0
943
944Pi    Pj
945--    --
946--    --
947A    wait(S)
948signal(s)   B
949
950
951Problem...
952
953Synchronization involves waiting
954- Busy waiting, uses CPU that others could use. This type of lock is called spinlock
955- - Waiting thread may take cycles away from thread holding lock
956- - Ok for short times since it prevents a context switch
957- - Priority inversion: Thread that is waiting has higher priority than thread holding lock --> problem
958- should sleep if waiting for a longer time
959For longer runtimes, need to modify P and V so processes can block and resume
960
961Semaphore Implementation with no busy waiting:
962
963Instead of the semaphore just being an integer value, make it a struct that also has a list
964In the wait function, start of by decrementing no matter what. If the value has gone negative, add it to S->list. Then block()
965In the signal function, increment and if the value is <= 0, remove a process P from the list
966Then wakeup(P)
967
968
969Deadlock and Starvation:
970
971Deadlock: two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
972
973Starvation: Indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended
974
975
976In the Producer-Consumer Bounded Buffer problem:
977
978The producer: P(empty), V(full)
979The consumer: P(full), V(empty)
980
981
982Problems With Semaphores:
983
984Incorrect use of semaphore operations can result in deadlock and/or starvation
985- signal(mutex) ... wait(mutex)
986- wait(mutex) ... wait(mutex)
987- omitting of wait(mutex) or signal(mutex) or both
988
989
990Monitors:
991
992A high-level abstraction that provides a convenient and effective mechanism for process synchronization
993Abstract type, internal variables are accessible only by code within the procedure
994Only one process may be active within the monitor at a time
995But not powerful enough to model some synchronization schemes
996
997Condition variables
998
999condition x, y
1000Two operations are allowed on a condition variable:
1001- x.wait() - a process that invokes the operation is suspended until x.signal()
1002- x.signal() - resume one of processes (if any) that invoked x.wait()
1003- - if no x.wait() on variable then has no effect on the variable
1004
1005What happens in the event that P is in the monitor and invokes x.signal() and process Q is suspended on x.wait()?
1006Both P and Q cannot execute in parallel in the monitor, if Q is resumed then P must wait
1007Options:
1008- Signal and wait: P waits until Q either leaves the monitor or waits for another condition
1009- Signal and continue: Q waits until P either leaves the monitor or waits for another condition