tz8g3m37

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