CS2106 Entire Syllabus Notes PDF

Preview

Summary

CS2106 Lecture 0-1 Introduction and Intro to OSOperation System – Program that acts as an intermediary between a computer user and hardwareAn Operation System (OS) is a system software that manages computer hardware, software resources, and provides common services for computer programsComputer: Win...

Description

CS2106 Lecture 0-1 Introduction and Intro to OS Operation System – Program that acts as an intermediary between a computer user and hardware An Operation System (OS) is a system software that manages computer hardware, software resources, and provides common services for computer programs

Computer: Windows 10/8/XP, Mac OS X, Linux, Solaris Mobile: iOS, Android, Windows Mobile History of OS: 1. NO OS (Program directly interact with hardware a. minimal overhead (any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to perform a specific task.) b. not portable and inefficient use of computer 2. Batch OS a. Execute user program one job at a time b. User Job: interact with hardware directly with additional information for the OS i. Resource required ii. Job specification c. Simple batch processing is inefficient (CPU idle when performing I/O) d. Multiprogramming can be used to improve Batch OS. Loads multiple jobs and run other jobs when I/O needs to be done Motivation for OS: 1. Abstraction a. Hide the low level details b. Present common high level functionality to user c. User then can perform essential tasks through operating systems d. Efficiency, programmability and portability 2. Resource allocation a. Program execution requires multiple resources: i. CPU, memory, I/O devices b. For better utilization of resources, multiple programs should be allowed to execute simultaneously c. OS is a resource allocator and manages all resources e.g., memory, CPU, I/O and arbitrate potentially conflicting requests e.g., scheduling problems 3. Control Program a. Controls execution of programs i. Prevent errors and improper use of computer ii. Provides security, isolation and protection

CS2106 Lecture 0-1 Introduction and Intro to OS

Kernel Mode: Complete access to all hardware resources User Mode: Limited (or controlled) access to hardware resources

OS is also known as the kernel • Deals with hardware issues • Provide system call interface • Special code for interrupt handlers, device drivers Kernel Code has to be different from normal programs and is written in HLL

Structuring an Operating System • Monolithic OS

CS2106 Lecture 0-1 Introduction and Intro to OS o Unix, DOS, Window 9x o Well understood and good performance o However, highly coupled components and usually devolved into complicated internal structure

•

Microkernel OS o Kernel is very small and clean ▪ Provides IPC, address space management, thread management o Higher level OS services ▪ Run as server process outside of the kernel ▪ Use IPC to communicate o Advantages: ▪ Kernel is more robust and extendible ▪ Better isolation and protection between kernel and high level services o Disadvantage: ▪ Lower performance

•

Layered System o Generalization of monolithic system Client-Server Model o Variation of microkernel o Client process request server from server process o Server process built on top of the microkernel o Client and server process can be on separate machine!

•

CS2106 Lecture 0-1 Introduction and Intro to OS

Virtual Machines • OS assumes total control of hardware • OS is hard to debug and monitor Virtual Machine: • A software emulation of hardware • Virtualization of underlying hardware o Illusion of complete hardware to level above: memory, CPU, hard disk • Normal OS can then run on top of virtual machine Created and managed by Hypervisor aka Virtual Machine Monitor (VMM)

CS2106 Lecture 2 Notes – Process Abstraction Memory o Storage for instruction and data • Cache: o Duplicate part of memory for faster access o Split into instruction and data cache • Fetch Unit: o Loads instruction from memory o Location indicated by special register: PC • Functional units: o Carry out instruction execution and dedicated to different instruction type • Registers: o Internal storage for fastest access speed o General Purpose Register (GPR): Accessible by user program o Special Register: Program Counter (PC), Stack Pointer (SP), Frame Pointer (FP) Basic Instruction Execution: 1. Instruction X is fetched (Memory location indicated by PC) 2. Instruction X dispatched to corresponding Functional Unit (read operands, compute, and write values to memory or GPR) 3. Instruction X is completed (PC updated for the next instruction) •

More information used when program is under execution: Memory Context: Text and Data Hardware Context: GPR, PC, … Function Calls Control Flow Issues: • Need to jump to function body • Need to resume when the function call is done • Minimally, need to store the PC of the caller Data Storage Issues: • Need to pass parameters to function • Need to capture return result • May have local variables declaration. Need a new region of memory that dynamically used by function invocations. Stack Memory Region – memory region to store information for function invocation. Information of a function invocation is described by a stack frame. Stack frame contains: • Return address of the caller • Arguments (Parameters) for the function • Storage for local variables

CS2106 Lecture 2 Notes – Process Abstraction

•

CS2106 Lecture 2 Notes – Process Abstraction

Stack Pointer: The top of stack region (first unused location) • Most CPU has a specialized register for this • Stack frame is added on top when a function is invoked (stack grows) • Stack frame is removed from top when function call ends (stack pops) A program counter is a register containing the address of the next instruction to be executed. Although it could be incremented after execution of the instruction instead of after fetching it, in which case it would be the address of the current instruction, but I don’t think that’s particularly common. A stack pointer is typically a register which points to the current stack frame. In terms of high-level languages, you can think of the stack frame as the storage for local variables, but there are normally a couple of other things stored there as well. Program counters point to instructions. Stack pointers point to data. Stack Frame Setup Different ways to setup stack frame: • Known as function call convention No universal way: Hardware and programming language dependent

Prepare to make a function call: • Caller: Pass parameters using registers and/or stack

CS2106 Lecture 2 Notes – Process Abstraction • • • • • •

Caller: Save Return PC (The program counter stores the address of each instruction and tells the CPU in what order they should be carried out.) on stack Transfer Control from Caller to Callee Callee: Save the old stack pointer (SP) Callee: Allocate space for local variables of callee on stack Callee: Adjust SP to point to new stack top.

Teardown call: On returning from function call: • Callee: Place return result in register (if applicable) • Callee: Restore saved Stack Pointer • Transfer control back to caller using saved PC • Caller: Utilize return result (if applicable) • Caller: Continues execution in caller.

Frame Pointer – to facilitate the access of various stack frame items. • Stack pointer is hard to use as it can change • Some processors provide a dedicated register Frame Pointer. •

Frame pointer points to a fixed location in a stack frame o Other items are accessed as a displacement from the frame pointer

CS2106 Lecture 2 Notes – Process Abstraction •

The usage of FP is platform dependent.

Saved Registers • Number of GPR on most processors are very limited (MPS 32, x86 has 16) When GPRs are exhausted: • Use memory to temporary hold the GPR value • GPR can then be reused for other purpose • GPR value can be restored afterwards • Known as register spilling Similarly, a function can spill the registers it intends to use before function starts (callee- saved) Restore those registers at end of function

Stack Frame Setup/Teardown [Updated with FP] On execution function call: • Caller: pass arguments with registers and/or stack • Caller: Save Return PC on stack • Transfer control from caller to callee • Callee: Save registers used by callee. Save old FP, SP • Callee: Allocate space for local variable of callee on stack • Callee: Adjust SP to point new stack top On return function call: • Callee: Restore saved value: FP, SP • Transfer control from callee to caller using saved PC • Caller: continues execution in caller Dynamically Allocated Memory – acquire memory space during execution time e.g. In C: malloc() function call In C++ and Java: the new keyword Allocated only at runtime ->Size is not known during compilation time -> Cannot place in Data region

CS2106 Lecture 2 Notes – Process Abstraction No definite deallocation timing -> can be freed by programmer in C/C++ -> Cannot place in Stack region Solution: Setup a separate heap memory region.

Managing Heap Memory: • Heap memory is a lot harder to manage due to: o Variable size o Variable allocation / deallocation timing Process Management As the OS, to be able to switch from running Program A to Program b requires: 1. Information regarding execution of program A needs to be stored. 2. Program A’s information is replaced with information required to run B. We need • Abstraction to describe running a program -> process

CS2106 Lecture 2 Notes – Process Abstraction

Process / Task / Job – dynamic abstraction for executing program • Information required to describe a running program

Process Identification – to distinguish processes from each other. • Common approach is to use process ID (PID) • Unique among processes PIDs are reused since PID length is 32 bits. (There is a limit to max no of processes) Process State – indication of execution status since a process can be either Running or Not-running Process Model State Diagram

Generic 5-State Process Model

CS2106 Lecture 2 Notes – Process Abstraction

New o New process created o May still be under initialization -> not yet ready ▪ Ready o Process is waiting to run ▪ Running o Process being executed on CPU ▪ Blocked o Process waiting (sleeping) for event o Cannot execute until event is available o I/O might result in running to block (e.g. require user input) ▪ Terminated o Process has finished execution, may require OS cleanup Transitions ▪ Create (nil → New): o New process is created ▪ Admit (New → Ready): o Process ready to be scheduled for running ▪ Switch (Ready → Running): o Process selected to run ▪ Switch (Running → Ready): o Process gives up CPU voluntarily or prompted by scheduler (Time quanta) ▪ Event Wait (Running → Blocked): o Process requests event/resource/service which is not available/in progress o E.g. Acquiring lock, waiting for I/O (printf, scanf) ▪ Event occurs (Blocked → Ready): o Event occurs → process can continue ▪

Given N processes: -

With 1 CPU core o  1 process in running state o Conceptually 1 transition at a time

CS2106 Lecture 2 Notes – Process Abstraction -

With m CPUs (cores): o  m process in running state o Possibly parallel transition

Different processes may be in different states: each process may be in different part of its state diagram

• • •

More than 1 process can be in ready + blocked queues May have separate event queues Queuing model gives global view of the processes, i.e., how the OS views them

Process Table & Process Control Block • The entire execution content for a process: Process Control Block (PCB) or Process Table Entry • Kernel maintains PCB for all processes

System Calls – programmatic way in which a computer program requests a service from kernel of operation system on which it is executed. System Calls provide an essential interface between a process and operation system. • Application Program Interface (API) to OS o Provides way of calling facilities/services in kernel o NOT the same as normal function call

CS2106 Lecture 2 Notes – Process Abstraction

•

▪ Have to change from user mode to kernel mode Different OS have different APIs: o Unix Variants: ▪ Most follow POSIX standards (no of calls: ~100) o Windows Family ▪ Uses Win API across different Window versions ▪ Huge no of calls ~1000

In C/C++ program, system call can be invoked almost directly Majority of system calls have a library version with same name and same parameters Function Wrapper e.g. getpid, read, write A few library functions present a more user-friendly version to programmer. Function Adaptor e.g. printf, scanf

General System Call Mechanism 1. User program invokes library call a. Using the normal function call mechanism 2. Library call (usually in assembly code) places the system call number in designated location e.g., Register 3. Library call executes a special instruction to switch from user mode to kernel mode (instruction is known as a TRAP) 4. Now in kernel mode, appropriate system call handler is determined: a. Save CPU state b. Using syscall number as index c. Step is usually handled by a dispatcher 5. System call handler is executed (carry out actual request) 6. System call handler ends: a. Restores CPU state, and return to library call b. Switch from kernel mode to user mode 7. Library call return to user program: a. Via normal function return mechanism

CS2106 Lecture 2 Notes – Process Abstraction

Exception • Executing a machine level instruction can cause exception • Examples: o Arithmetic Errors: Overflow, Division by Zero o Memory Errors: Illegal memory address, misaligned memory access • Exception is synchronous o Occur due to program execution • Effects of an exception: o Have to execute an exception handler o Similar to a forced function call Interrupt • External events can interrupt the execution of a program • Usually hardware related e.g.: Timer, Mouse movement, keyboard pressed • Interrupt is asynchronous o Event that occurs independent of program execution • Effect of interrupt: o Program execution is suspended o Interrupt handler executed automatically • Interrupts are important because they give the user better control over the computer. Without interrupts, a user may have to wait for a given application to have a higher priority over the CPU to be ran. This ensures that the CPU will deal with the process immediately.

CS2106 Lecture 2 Notes – Process Abstraction

Control + Z : Suspends Fg: Brings suspended process back Control + C: Terminate Signal Process Abstraction in UNIX 1. Identification • PID: Process ID (an integer value) 2. Information • Process State: o Running, Sleeping, Stopped Zombie • Parent PID: o PID of parent process • Cumulative CPU time: o Total amount of CPU time used so far Unix Command: “ps” Process Creation in UNIX: fork()

Returns: • PID of newly created process (for parent process) OR • 0 (for child process) Behavior: • Creates a new process (known as child process) • Child process is a duplicate of current executable image o Same code, same address space o Memory in child is a copy of parent • Child differs only in: o Process id (PID) o Parent (PPID) ▪ Parent = process which executed the fork() o Fork() return value [To distinguish between parent and child] Total no of processes = 2n where n is no of fork system calls Both parent and child processes continue executing after fork()

CS2106 Lecture 2 Notes – Process Abstraction

Common usage is to use parent/child process differently • Parent spawn child to do work • Parent does another task

Fork() itself is not useful (Still need to provide full code for child process which is inefficient) • Make use of exec() system calls family • Execv, execl, execle, execlv etc.

Execl() System Call

CS2106 Lecture 2 Notes – Process Abstraction To replace current executing process image with a new one • Code replacement • PID still intact

Path: location of executable Arg0,…arg[n] : Command Line Argument(s) NULL: to end list of argument

Fork + Exec() • Spawn off a child process using fork() • Let child process perform a task using exec() Master Process: Special initial process: • Init process • Created in kernel at boot up time • Traditionally has a PID = 1 • Watches for other processes and respawns when needed Fork() creates process tree:

CS2106 Lecture 2 Notes – Process Abstraction

• Init is the root process Process Termination in Unix

• • •

Status is returned to the parent process Unix Convention: o 0: Normal Termination (Successful execution) o !0: Indicate problematic execution Function does not return

Process finished execution • Most system resources used by process are released on exit • E.g. File descriptor Some basic process resources not releasable: • PID & status needed o For parent & child synchronization • Process accounting info e.g., CPU time Implicit exit() • Most programs have no explicit exit() call

CS2106 Lecture 2 Notes – Process Abstraction

Return from main() implicitly calls exit() • Open files also get flushed automatically Parent/Child Synchronization in UNIX • Parent process can wait child process to terminate

• •

•

•

•

Returns PID of terminated child process Status (passed by address) o Stores the exit status of terminated child process o Use NULL if you do not want info

Behavior: o The call is blocking: ▪ Parent process blocks until at least one child terminates o The call cleans up remainder of child system resources ▪ Not removed on exit() ▪ Kills zombie processes Other variants of wait o Waitpid() ▪ Wait for specific child process o Waitid() ▪ Waits for any child process to change status On exit, o Most resources are released o Becomes Zombies o Cannot delete all processes o Cannot kill zombie

CS2106 Lecture 2 Notes – Process Abstraction

Zombie Process and Orphan Process 1. Orphan: Parent process terminates before child process ▪ Init process becomes “pseudo” parent for child ▪ Child does not terminate ▪ Child termination signals init which utilizes wait() to clean up 2. Zombie: Child process terminates before parent but parent does not call wait. ▪ Child process becomes a zombie process ▪ Fills up process table (becomes messy to need reboot to clear table)

CS2106 Lecture 2 Notes – Process Abstraction Issues with fork() ▪ Memory copy is expensive -> potentially need to copy whole memory space ▪ Copy on write – optimization for memory copy operation o Only duplicate memory location when it is written to o Otherwise parent and child share the same memory location ▪ Not versatile if you want partial duplication ▪ Linux provides clone() which supersedes fork()

CS2106 Lecture 2 Notes – Process Abstraction

Tutorial 3 2a. dataX is a global variable stored in Data storage, dataY is a local variable and is stored in stack segment, *dataZptr is in the stack segment but memory location it is point to (dynamically allocated memory) is stored in the heap segment 2b. Each process at the same phase prints the same values. Showing that processes at each phase is running independently of each other. The PIDs are assigned sequentially also 2e. Yes it is possible and it depends on the process scheduling algorithm determined by the OS to choose which processes to run at which time. 2f. * and # will not change order because of how the code is written sequentially. Given they are in the same phase. Likewise for ** and ##. Phase 1 messages will always be written before the other phase messages.

[PID 100]: x = 8,y=0

CS2106 Lecture 4 Process Scheduling Notes I/O bound refers to condition in which time taken to complete a computation is determined principally by period spent waiting for input/output operations to be completed CPU bound means the rate at which process progresses is limited b...