Midterm Exam PDF - Operating Systems

Chapter 1: Introduction Outline What Operating Systems Do Computer-System Organization Computer-System Architecture Operating-System Operations Resource Management Security and Protection Distributed Systems Virtualization Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Computer System Structure Computer system can be divided into four components: – Hardware CPU, memory, I/O devices – Operating system – System and Application programs – Compilers, assembler, word processors, your first hello world program… – Users People Four Components of a Computer System What Operating Systems Do? A software that acts between a users/applications and the computer hardware. Program 1 Program 2 OS Device 1 Device 2 Device 3 Goal – Manages the computer hardware and provides an environment for application programs to run Defining Operating System A common definition – The OS is the one program running at all times on the computer Usually called the kernel Outline What Operating Systems Do Computer-System Organization Computer-System Architecture Operating-System Operations Resource Management Security and Protection Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Outline What Operating Systems Do Computer-System Organization – Interrupts – Storage structure Computer-System Architecture Operating-System Operations Resource Management Security and Protection Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems A Computer System A computer system consists of CPU and multiple device controllers, connect through a bus (see the following slide) Device controller: hardware – In charge of a specific device – Contains local buffer and special-purpose registers Device drivers: software – Part of an OS (see the following slide) – A device driver for each device controller A Computer System CPU registers device registers Local buffer A Computer System https://www.tutorialspoint.com/operating_system/os_io_software.htm Device Driver https://itw01.com/F9NUEAQ.html 問題 1: CPU如何通知周邊裝置？問題 2:周邊裝置如何通知CPU？ registers Answer 1: 藉由讀寫Device Controller的內部暫存器 Answer 2: Device controller informs CPU by causing an interrupt Starting an I/O operation Starting an I/O operation (e.g., read data from disks) – Device driver loads the appropriate registers within the device CPU-Device controller (see the following slide) – Device controller Device Examines the contents of these registers processing and notifying CPU – Determine what action to take Start the actions – Transfer of data from the device to its local buffer Once completed – Device controller informs the CPU via an interrupt A Computer System CPU registers device registers Local buffer Interrupts Interrupt: signals an occurrence of a hardware event. – The completion of an I/O, a keypress, In general – Device controller raises an interrupt By asserting a signal on the interrupt-request line – CPU catches the interrupt – CPU dispatches it to the interrupt handler – Interrupt handlers serve the device Interrupt Hardware Concepts Device raise an interrupt CPU catch an interrupt https://www.renesas.com/eu/en/support/engineer-school/mcu-programming-peripherals-04-interrupts CPU Dispatch an Interrupt to ISR … mov eax, 0x60; 0x1000 … CPU ….. interrupt CPU dispatch an OS interrupt to ISR Interrupt Service Routine (ISR) Interrupt Processing Flow https://www.hackster.io/rafitc/interrupts-basics-f475d5 Interrupts (Cont.) When an interrupt occurs, i.e., CPU is interrupted – Stop what it is doing – Transfer execution to a fixed address Executes the interrupt service routine (ISR) for the interrupt – Interrupt service routine Perform a state save - Service the interrupt Perform a state restore - Executes a retrun_from_interrupt instruction – CPU resumes the interrupted computation Without State Save and Restore … mov eax, 0x60; add eax, ebx; CPU … eax 10 59 ebx 525 ….. interrupt OS Interrupt Service Routine (ISR) State Save and Restore PC=0x1000 memory eax=10, ebx=5 ecx =9, edx = 11 etc. save Interrupt Start …… Interrupt End process P1 process P1 restore CPU eax=10, ebx=5, eax=6, ebx=9, ecx=9, ecx=3, edx =11 =32 pc= … pc= 0x58000… 0x1000… 0x1000 With State Save and Restore … mov eax, 0x60; add eax, ebx; CPU … eax 10 59 ebx 525 ….. interrupt eax=10; ebx=5; …… OS Interrupt Service Routine (ISR) Interrupt Processing Flow Interrupt Service Routine https://www.renesas.com/eu/en/support/engineer-school/mcu-programming-peripherals-04-interrupts Outline What Operating Systems Do Computer-System Organization – Interrupts – Storage structure Computer-System Architecture Operating-System Operations Resource Management Security and Protection Virtualization Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Storage Structure There are many different storage media – Differ in sizes, speed, cost, volatility (揮發性)… So, current storage systems are organized in hierarchy. – As shown in the following slide – The top four levels are constructed using semi-conductor memory Storage-Device Hierarchy (volatile) (common , non-volatile) Cless consumer usage) Performance of Various Levels of Storage Storage Structure (Cont.) Primary storage – Main memory: RAM The only large storage media that the CPU can access directly. Secondary storage – Extension of main memory to provide large nonvolatile capacity Main memory is usually too small and volatile – Electrical-based: Flash memory (SSD) – Mechanical-based: hard-disk drives (HDD) (or called magnetic disks) Tertiary storage – Usually for storing backup copies Outline What Operating Systems Do Computer-System Organization Computer-System Architecture – Single-Processor Systems – Multiprocessor Systems – Clustered Systems Operating-System Operations Resource Management Security and Protection Virtualization Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Single-Processor Systems Only one general-purpose processor But have other special-purpose processors – Disk controllers, USB controller, graphics adatpers… A Computer System CPU registers device registers Local buffer Outline What Operating Systems Do Computer-System Organization Computer-System Architecture Operating-System Operations Resource Management Security and Protection Virtualization Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Outline What Operating Systems Do Computer-System Organization Computer-System Architecture Operating-System Operations – Multiprogramming and Multitasking – Dual-Mode and Multi-mode Operation – Timers Resource Management Security and Protection Virtualization Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems 基本問題：作業系統何時被執行？ Program 1 Program 2 OS Device 1 Device 2 Device 3 Event-Driven OS OS is event-driven Event – Interrupt: driven by hardware – Trap (or exception): a software-generated interrupt, caused by Error: Division by zero, illegal instructions System calls or monitor calls – Functions provided by OS to provide service to applications – read(), write(), open()…… Event-Driven OS: Interrupt … 2 mov eax, 0x60; … CPU ….. I interrupt 3 OS Interrupt Service Routine (ISR) Event-Driven OS: Trap (Error) … I a = b/0; … CPU ….. 2 trap 3 OS Handling : Terminate program (most likely OS > Event-Driven OS: Trap (System Call) … I int 0x10; // read(); … CPU ….. 2 trap (gets function from OS) OS 補充：何謂System Calls the OS Requesting a function from Example #include #include #include #include #include #include //for exit() #include //for strlen() int main(){ int fd; fd = open("myfile.txt", O_CREAT | O_WRONLY, 0600); if (fd < 0){ printf("Failed to open the fild.\n");exit(1); } int size; size = write(fd, "e", strlen("e") ); close(fd); printf("length of write data=%d \n", strlen("e")); printf("Number of bytes written on success=%d \n\n", size); exit(0); 68 } Program 1 Program 2 open()… read()… User Mode system call Kernel Mode open(), read() open() { …. } read() OS { … } Storage Summary: Interrupts and Traps … … open() … a=0; b=10/a; … Trap caused by Trap caused by System Call to … software error ask the kernel provide services OS (or Kernel) Interrupt cause kernel to service NIC … Keyboard I/O devices Hardware OS is Event-Driven Program 1 Program 2 User Mode exceptions Kernel Mode read(), write() OS interrupts Device 1 Device 2 Device 3 Outline What Operating Systems Do Computer-System Organization Computer-System Architecture Operating-System Operations – Multiprogramming and Multitasking – Dual-Mode and Multi-mode Operation – Timers Resource Management Security and Protection Virtualization Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Operating-System Structure Single-programming systems Multi-programmed systems Time-sharing (or multitasking) systems Operating-System Structure Single-programming systems Multi-programmed systems Time-sharing (or multitasking) systems Operating-System Structure: Single-programming systems (DOS era) Single-programming systems – One job at a time After a job is finished, then the next job – Very inefficient CPU is idle when the running program is doing I/O (next slide) Uni- vs. Multi-Programming (a) uni-programming Waiting for 210 (b) multi-programming Operating-System Structure Single-programming systems Multi-programmed systems Time-sharing (or multitasking) systems Operating-System Structure: Multiprogramming Why use multiprogramming? for efficiency – Run multiple programs keep either the CPU or the I/O devices busy at all times – Give an example in your usual life: 小朋友玩遊戲 Memory Layout for a Multiprogramming System A set of jobs is kept in memory Operating-System Structure Single-programming systems Multi-programmed systems Time-sharing (or multitasking) systems Operating-System Structure: Timesharing (Multitasking) Problem of Multi-programming systems – Does not provide user interaction: see the following slide Solutions: Timesharing (Multitasking) – CPU switches jobs so frequently (not until jobs doing I/O) Response time is short – Create an interactive computing environment (e.g., using keyboards or mouse) Problems of Multiprogramming Systems program A RUN wait program B wait RUN (word) Bad: long response time interactive task Timesharing (Multitasking) program A RUN wait RUN program B wait RUN (word) Good: short response time interactive task Outline What Operating Systems Do Computer-System Organization Computer-System Architecture Operating-System Operations – Multiprogramming and Multitasking – Dual-Mode and Multi-mode Operation – Timers Resource Management Security and Protection Virtualization Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Dual-Mode and Multimode Operations To ensure proper execution of the system – Must distinguish between the execution of OS code and user program code – Why? (see the following slide) Solution: CPU supports dual-mode or multimode operations Distinguish Between the Execution Of OS Code And User Program Code USER LBE EJ , E !) … cli; clear interrupt => -E interruptt … # interrupt B , ER CPU E ….. V … OSTIE cli; J interrupt · … OS Dual-Mode Operation Modern CPUs have at least two execution modes: – User mode – execution done on behalf of a user Limited set of usable instructions – Monitor mode– execution done on behalf of operating system Also called supervisor mode, system mode, or privileged mode Can executed · all of the instructions, including privileged instructions – Controlled by a mode bit. 1.3.1 SIC Machine Architecture (Cont.) Registers – Five registers – Each register is 24 bits in length Mnemonic Number Special use A 0 Accumulator X 1 Index register L 2 Linkage register PC 8 Program counter SW 9 Status word 1.3.1 SIC Machine Architecture (Cont.) Status Word register contents Bit position Field name Use 0 MODE 0=user mode, 1=supervisor mode 1 IDLE 0=running, 1=idle 2~5 ID Process identifier 6~7 CC Condition code 8~11 MASK Interrupt mask 12~15 Unused 16~23 ICODE Interruption code Dual-Mode Operation (Cont.) Privileged instructions – Instructions that may cause harm – Can only be executed in the supervisor mode. – Example: I/O control, timer management, interrupt management Why uses Dual-mode operation? – For protection – Privileged instruction can only execute in kernel mode & If executed in user mode, hardware will cause a trap Trap cause CPU jump to the OS, that terminates the application (next slide) Dual-Mode Operation … mov eax,10 cli; //clear interrupt … User Mode Executing privilege instruction trap cause a trap to the OS Kernel Mode OS (or Kernel) NIC … Keyboard Hardware Dual-Mode Operation … cli; … CPU & mode = 0; ….. not in monitor mode & trap OS Dual-Mode Operation (Cont.) Entering Monitor Mode (the same as entering OS) – As the result of an interrupt – Through a system call trap – As a result of an error trap User read(), trap Process User Mode System Call Interface Kernel Mode File System I/O interrupt Hardware Mode Bit Change: Interrupt … out eax, 0x60; … CPU mode = 1; 0; ….. interrupt OS Interrupt Service Routine (ISR) … interrupt iret return Mode Bit Change : Trap (Error) … & a = b/0; … CPU mode = 1; 0; … x = x + 1; ….. … trap OS iret Mode Bit Change : Trap (Error) … cli; … CPU mode = 1; 0; … x = x + 1; ….. … trap OS iret Mode Bit Change: Trap (System Call) … int 0x 10; // read(); … CPU mode = 1; 0; ….. interrupt OS iret Dual-Mode Operation: Trap (System Call) … int 0x 10; // read(); … CPU mode = 1; 0; ….. trap OS iret Dual-Mode Operation: Trap (System Call) 0 1 0 - 1 - Multi-Mode Examples – x86 CPU has four protection rings (modes) Windows runs in the ring 0 (kernel mode) User applications runs in the ring 3 (User mode) ! – ARM8 has seven modes Outline What Operating Systems Do Computer-System Organization Computer-System Architecture Operating-System Operations – Multiprogramming and Multitasking – Dual-Mode and Multi-mode Operation – Timers Resource Management Security and Protection Virtualization Distributed Systems Kernel Data Structures Computing Environments Free and Open-Source Operating Systems Timer Question: how to prevent a user program from getting the CPU forever ? (next slide) – That is, how to implement time sharing systems? – See the following three slides We must have a way to enter OS – System call traps – Error Traps – Interrupts Your choice? – See the following next slide Problem program A RUN … j program B wait (word) Bad: long response time interactive task Problem: Example User … for (;;) - Applications executes a infinite Applications a=a+1; loop, occupying CPU … User Mode Kernel Mode OS (or Kernel) Hardware Problem: Example (Cont.) … go for (;;) a=a+1; Program A … CPU … add eax, ebx; ….. … OS Interrupt Service Routine (ISR) Your Choice? ? 1 0 OS https://www.geeksforgeeks.org/dual-mode-operations-os/ Solution We must have a way to enter OS P6). – System call traps – Error Traps 3 controlled as such , by running they're unfeasible program (which infinitely loops – Interrupts Timer (Cont.) Solution: timer – Cause timer interrupt periodically – CPU is returned back to the OS (ISR) Run another task or still the same task An so on…(see the following two slides) – Clearly, instructions that modify the content of the timer are privileged With a Timer … for (;;) User a=a+1; Applications Change to execute another application User Mode … Kernel Mode timer_interrupt_handler() { If (current process executes too long) change to execute another application } Interrupt cause CPU just to the Timer kernel Hardware With a Timer (Cont.) … for (;;) a=a+1; … CPU 1...... … add eax, ebx; ….. … interrupt Timer OS Interrupt Service Routine (ISR) Interrupts As shown in the figure, a quiet macOS desktop generated 23,000 interrupts over 10 seconds Summary Computer System Structure – Hardware, operating system, system and application programs, users Computer-System Organization – Interrupts – Storage structure Computer-System Architecture – Single-Processor Systems – Multiprocessor Systems – Clustered Systems Operating-System Operations – Multiprogramming and Multitasking – Dual-Mode and Multi-mode Operation – Timers Chapter 2 Operating-System Structures Outline Operating System Services User and Operating-System Interface System Calls System Services Linkers and Loaders Why Applications Are Operating-System Specific Operating-System Design and Implementation Operating-System Structure Building and Booting an Operating System Operating System Debugging Outline Operating System Services User and Operating-System Interface System Calls System Services Linkers and Loaders Why Applications Are Operating-System Specific Operating-System Design and Implementation Operating-System Structure Building and Booting an Operating System Operating System Debugging Operating System Services OS provides services to programs and users – E.g., Program execution Manage hardware …… Program 1 Program 2 User Mode Kernel Mode OS hardware 1 hardware 2 hardware 3 Outline Operating System Services Operating-System Interface to Users System Calls System Services Linkers and Loaders Why Applications Are Operating-System Specific Operating-System Design and Implementation Operating-System Structure Building and Booting an Operating System Operating System Debugging User Operating System Interface For users, fundamental approaches to interface with the OS (see the following slide) – Command-line interface (CLI) (or command interpreter) – Batch interface – Graphical User Interface (GUI) – Touch-Screen Interface User Operating System Interface For users, fundamental approaches to interface with the OS (see the following slide) – Command-line interface (CLI) (or command interpreter) – Batch interface # : T-TN *bat , – Graphical User Interface (GUI) – Touch-Screen Interface user 1 user 2 User Mode Kernel Mode OS hardware 1 hardware 2 hardware 3 User Operating System Interface : CLI Command interpreter (CLI) allows directly typing commands – Fetch a command from user and execute – Implemented as a system program Not part of OS – In Linux, multiple choices are implemented – shells Bourne shell (bash), C shell (csh), Korn shell (ksh) Shell Command Interpreter User Shell OS hardware User Operating System Interface For users, fundamental approaches to interface with the OS (see the following slide) – Command-line interface (CLI) (or command interpreter) – Batch interface – Graphical User Interface (GUI) – Touch-Screen Interface User Operating System Interface : Batch Interfaces cc -g -c menu.c cc -g -o driver driver.c menu.o driver < test_data > test_out lpr -PthePrinter test_out tar cvf driver_test.tar menu.c driver.c test_data test_out uuencode driver_test.tar driver_test.tar >driver_test.encode A “shell script” batch File from “Operating Systems by NUTT” User Operating System Interface For users, fundamental approaches to interface with the OS (see the following slide) – Command-line interface (CLI) (or command interpreter) – Batch interface – Graphical User Interface (GUI) – Touch-Screen Interface User Operating System Interface : GUI User-friendly desktop interface – Mouse-based window-and-menu User Operating System Interface For users, fundamental approaches to interface with the OS (see the following slide) – Command-line interface (CLI) (or command interpreter) – Batch interface – Graphical User Interface (GUI) – Touch-Screen Interface User Operating System Interface : Touchscreen Interfaces Touchscreen devices Voice commands Outline Operating System Services Operating-System Interface to Users System Calls System Services Linkers and Loaders Why Applications Are Operating-System Specific Operating-System Design and Implementation Operating-System Structure Building and Booting an Operating System Operating System Debugging 補充: Example of Programs Using Libraries in Linux int add(int arg) { a.c arg++; return arg; } int sub(int arg) { arg--; return arg; } int abc() { … } int sum(int arg1, int arg2) b.c { return (arg1+arg2); } int xyz() { …… } 21 補充: Example of Programs Using Libraries in Linux (Cont.) library & libtmp.a a.c Compiler a.o & link utility a.o Compiler b.o b.c b.o Creating a library called libtmp.a 22 補充: Example of Programs Using Libraries in Linux (Cont.) Compile source programs to object programs – gcc –c main.c – gcc –c a.c – gcc –c b.c Create/add/replace object programs into library – ar –r libtmp.a a.o – ar –r libtmp.a b.o List contents of library – ar –t libtmp.a Delete object programs from library – ar –d libtmp.a b.o 23 補充: Example of Programs Using Libraries in Linux (Cont.) main.c int & add(int arg) { a.c arg++; #include return arg; E } extern int extern int add(int); sub(int); & int sub(int arg) { arg--; extern int sum(int, int); return arg; } main() { int abc() { int ret1, ret2, ret3; … } ret1 = add(5); ret2 = sub(5); ret3 = sum(ret1, ret2); int & sum(int arg1, int arg2) b.c { printf("\n ret from add()= %d", ret1); return (arg1+arg2); printf("\n ret from sub()= %d", ret2); } printf("\n ret from sum()= %d", ret3); int xyz() } { …… } 24 補充: Example of Programs Using Libraries in Linux (Cont.) Object file executable file Source file main.c Compiler main.o main.o linker libtmp.a libtmp.a a.o a.o b.o b.o Link with libtmp.a to create the executable file 25 補充: Example of Programs Using Libraries in Linux (Cont.) Compile source programs to object programs – gcc –c main.c Using library in programs – Ex. gcc main.o libtmp.a –o prog – Ex. gcc main.o –L. –ltmp –o prog Linking editor – ld under Liunx References – man gcc under Linux – man ar under Linux – man ld under Linux System Calls System calls – Functions provided by OS to provide service to user applications – Example: open(), read(), write(), close()…… – Even simple program (see the following example) may make heavy use of the system calls Example #include #include #include #include #include #include //for exit() #include //for strlen() int main(){ int fd; fd = open("myfile.txt", O_CREAT | O_WRONLY, 0600); if (fd < 0){ printf("Failed to open the fild.\n");exit(1); } int size; size = write(fd, "e", strlen("e") ); close(fd); printf("length of write data=%d \n", strlen("e")); printf("Number of bytes written on success=%d \n\n", size); exit(0); 31 } Program 1 Program 2 open()… read()… User Mode Kernel Mode open(), read() open() { …. } read() OS { … } Storage Examples of Windows and Unix System Calls 問題：為什麼system call介面不一樣? System Calls (Cont.) Typically, a number is associated with each system call – OS maintain a table indexed according to these numbers System Calls (Cont.) … int 0x10; // read(); … CPU mode = 1; 0; ….. trap OS APIs (call library > - system call) However, system calls are often accessed indirectly via a Application Program Interface (API) – Rather than directly calling the system call – fopen(), fread(), fwrite(), printf()….are APIs – See the following slide Program 2 Program 1 fopen(); O fopen() { … open(); C library … } User Mode Kernel Mode open() { …. } read() OS { … } Storage C program invoking fopen () library call, which in turn calls open () system call Example: Standard C Library #include int main() { printf(“Greeting”); Application … } printf() { C Library … int 0x80; (libc provides a wrapper of … system calls.) } write() { … OS … } Hardware Hardware 39 C program invoking printf() library call, which in turn calls write() system call System Call and APIs ↓ d Application Program ↳ Library API Function (Ex:C Library, Windows Library) OS Function Hardware Calling System Call and APIs: Example #include #include #include #include #include #include //for exit() #include //for strlen() int main(){ int fd; fd = open("myfile.txt", O_CREAT | O_WRONLY, 0600); if (fd < 0){ printf("Failed to open the fild.\n");exit(1); } int size; size = write(fd, "e", strlen("e") ); close(fd); printf("length of write data=%d \n", strlen("e")); printf("Number of bytes written on success=%d \n\n", size); exit(0); 42 } System Call and APIs APIs (Cont.) API: a set of functions that can be called by the programs – Three most common APIs Win32 API for Windows POSIX API for POSIX-based systems – All versions of UNIX, Linux, and Mac OS X Java API for the Java virtual machine (JVM) – Supported by library Kernel32.lib is the library of Win32 API (see the following slide) - 複習：組合語言(Linking to a Library) The two LIB files: irvine32.lib, and kernel32.lib – The irvine32.lib is provided by book’s author – The kernel32.lib is part of the Microsoft Win32 Software Development Kit (SDK) links Your program Irvine32.lib to links to can link to kernel32.lib executes kernel32.dll 45 Some of POSIX APIs Example: Standard C Library APIs (Cont.) Why use APIs rather than system calls? – Portability Application using APIs can be compiled and run on another platform using the same API See the following three slides – Easier to use System calls oftenAPI)be more detailed and difficult to use than APIs (from – E.g., printf() function provides output formatting, whereas the write() system call just outputs a block of bytes Programmer knows nothing about how the system call is implemented – Details of system calls are hidden by APIs Examples of Windows and Unix System Calls Portability (Cont.) Low Portability Change to Linux … … CreateProcess() fork() … Need to modify … source code CreateProcess() fork() * since system call interface Windows is different Linux Portability … … pthread_create() Change to VxWorks pthread_create() … … Don’t need to modify source code POSIX Library POSIX Library fork() new_thread() even system call interface Linux is different VxWorks Summary … SYS_XYZ(…); CPU … ….. OS SYS_XYZ() { … } Idea: Storage Hierarchy System Call Parameter Passing Three methods used to pass parameters to the OS (from Assembly language) – Pass the parameters in registers In some cases, may be more parameters than registers (disadvantage ( – Parameters stored in a block in memory, and address of block passed as a parameter in a register Taken by Linux and Solaris – Parameters pushed onto the stack by the program and popped off the stack by the OS Block and stack methods do not limit the number or length of parameters Passing Parameters to System Calls: CPU Registers mov eax, 10 mov ebx, 20 int SYS_XYZ; …… User Mode system_call Kernel Mode SYS_XYZ : & mov a, eax; a = 10; mov b, ebx; b = 20; …… Passing Parameters to System Calls: CPU Registers … mov eax, 10 mov ebx, 20 & CPU int 0x10; //SYS_XYZ; eax 10 … ebx 20 ….. OS SYS_XYZ() { … } Passing Parameters to System Calls: Memory Block eax 0x1000 mov eax, 0x1000 int SYS_XYZ; 0x1000 User Mode …… & greetings Kernel Mode system_call SYS_XYZ : user parameters pointed by eax …… memory Passing Parameters to System Calls: Memory Block … move eax, 0x1000 int 0x10; //SYS_XYZ; CPU … eax & 0x1000 & ….. greetings startingis OS SYS_XYZ() { read parameter from [eax] } Passing Parameters to System Calls: Stack & push 10 push 20 int SYS_XYZ; …… User Mode system_call Kernel Mode SYS_XYZ: & pop a; // a = 20; pop b; // b = 10; …… Passing Parameters to System Calls: Stack … push 10 push 20 CPU int 0x10; //SYS_XYZ; … ….. 10 20 OS SYS_XYZ() { … } Outline Operating System Services User and Operating-System Interface System Calls System Services Linkers and Loaders Why Applications Are Operating-System Specific Operating-System Design and Implementation Operating-System Structure Building and Booting an Operating System Operating System Debugging Operating System Structure Operating system structure – Monolithic (龐大的) structure – Layered approach – Microkernels – Modules – Hybrid systems Operating System Structure Operating system structure – Monolithic (龐大的) structure – Layered approach – Microkernels – Modules – Hybrid systems Monolithic Structure Do not have well-defined structures Examples – MS-DOS: - – Original UNIX - - Everything between the system call interface and physical hardware is the kernel. An enormous amount of functions in one level=> monolithic (龐大的) kernel Original UNIX Architecture Monolithic Structure Monolithic Structure – Bad: Difficult to implement and extend – Good: Have a distinct performance advantage Very little overhead in the system-call interface and communication within the kernel is fast Discussed later – Thus, UNIX, Linux and Windows are monolithic kernels Operating System Structure Operating system structure – Monolithic structure – Layered approach – Microkernels – Modules – Hybrid systems Layered Approach OS is divided into a number of layers Layer approach: each layer uses functions and services of only lower-level layers Advantages: – Simplicity of construction and debugging Starts from the lowest layer - – Information hiding Do not have to know the details of the other layers Figure 2-15 TCP/IP and OSI Model The McGraw-Hill Companies, Inc., 2000 Layered File System: File System Organized into Layers Layered Approach (Cont.) Difficulties – Hard to determine the number of layers – Hard to define functionality of each layer – Less efficient A service may involve multiple layers But each layer adds overhead Trend: - fewer layers with more functionality Operating System Structure Operating system structure – Monolithic structure – Layered approach – Microkernel – Modules – Hybrid systems Microkernel Motivation: due to UNIX became large and difficult to manage Idea: moves as much from the kernel into user space – A smaller kernel – Mach: the first microkernel by CMU What a microkernel should provide ? – Typically, minimal process and memory management, and a communication facility – Will be introduced in later chapters Communication facility – Provide communication between the client program and the various services (called servers) – Provided by message passing Ch 3. Microkernel System Structure part of o now Microkernel (Cont.) Advantages: – Easier to extend the OS By adding new services and do not require kernel modification – Easier to port the OS to new architectures The kernel is small and the changes tend to be fewer – More reliable and more secure Most services are running as user processes If a service failed, the rest of the OS remains untouched Disadvantages: – Performance overhead by message passing between services – Window NT: microkernel, Windows XP: a monolithic kernel Operating System Structure Operating system structure – Monolithic structure – Layered approach – Microkernels – Modules – Hybrid systems Modules Best current methodology in OS design An OS consists of – A core kernel – A set of loadable kernel modules (LKMs) that can dynamically loadable at run time Modules https://www.researchgate.net/figure/Interaction-of-Linux-kernel-modules-with-their-environment_fig1_299373758 Example: Solaris Modular Approach Solaris is organized around a core kernel with seven types of loadable kernel modules Operating System Structure Operating system structure – Monolithic structure – Layered approach – Microkernels – Modules – Hybrid systems Hybrid Systems Modern operating systems do not adopt a single structure – Hybrid systems combine multiple structures – Linux is monolithic, + modules for dynamic loading of functionality – Windows is mostly monolithic + personalities (user-level services) (microkernel) + modular for dynamic loading of functionality Chapter 3: Processes Outline Process Concept Process Scheduling Operations on Processes Interprocess Communication IPC in Shared-Memory Systems IPC in Message-Passing Systems Examples of IPC Systems Communication in Client-Server Systems Outline Process Concept – The Process – Process State – Process Control Block Process Scheduling Operations on Processes Interprocess Communication IPC in Shared-Memory Systems IPC in Message-Passing Systems Examples of IPC Systems Communication in Client-Server Systems Overview Process – a program in execution – Also called jobs, tasks Program – passive ; Process – active Programs and Processes Process The running instantiation of a program, stored in RAM Program An executable file in storage 5 CS 5600 Computer Systems Overview (Cont.) A process need certain resources: – CPU Status of the current activity: PC (Program Counter), registers… – Memory Text section: program code (fixed size) Data section: global variable (fixed size) 1 datal. Stack section: temporary data - – Parameter, return address, local variable… > (in order) Heap section: memory that are dynamically allocated by calling malloc() and free() – Files…… 6 Process CPU eax=10, ebx=5,… pc= 0x1000 Ition 複習: EIP (or PC) EIP 1009 1000 mov eax, Y; 1003 add eax, 4; 1006 mov ebx 3; 1009 imul ebx; 100C mov X, eax; 100F … 1012 … Again: Storage-Device Hierarchy Stack: Example 1 main() & ↓ stack { arugment. a main() ESP return address &. local variables a = a + 1; F argument function_1(…); function- i) ESP & · function return address exit(1); local variables }. 21) ESP argument return address * local variables function_1() { b = b - 1; function_2(…); · return; } function_2() { … return; } Stack: Example 2 stack frame 11 https://eecs280staff.github.io/notes/02_ProceduralAbstraction_Testing.html Stack: Example 3 main PROC.. By the time Sub3 is called, the stack contains call Sub1 exit main ENDP three stack frames Sub1 PROC.. call Sub2 (ret toframe stack main) ret Sub1 ENDP Sub2 PROC (ret toframe stack Sub1).. call Sub3 ret (ret toframe stack Sub2) ESP Sub2 ENDP Sub3 PROC.. ret Sub3 ENDP Heap main() {.. malloc(1024);& & si X ……; & 2048 X b = b - 1; malloc(2048) & & 1024 X & heap ……; malloc(512); ③ & free(512) free(2048); free(1024); } Actual Memory Layout of a C Program As shown in the following slide, in fact – The global data section is divided into initialized data and uninitialized data sections – A separate section is provided for the argc and argv parameters Actual Memory Layout of a C Program to argument argumen Actual Memory Layout of a Process https://techaccess.in/2021/05/07/sections-of-a-process/ Memory Layout of a C Program To obtain the size of the segment of a program – size executable-file-name – text: code segment – data: initialized global data – bss (block start by symbol): uninitialized global data – dec and hex: sum of three sections Outline Process Concept – The Process – Process State – Process Control Block Process Scheduling Operations on Processes Interprocess Communication IPC in Shared-Memory Systems IPC in Message-Passing Systems Examples of IPC Systems Communication in Client-Server Systems Process State As a process executes, it changes state – new: The process is being created – running: Instructions are being executed – waiting: The process is waiting for some event to occur – ready: The process is waiting to be assigned to a processor The process is runable – terminated: The process has finished execution Only one process can be running on a core – Many processes may be ready or waiting Diagram of Process State for example waiting , for disk Outline Process Concept – The Process – Process State – Process Control Block PCB Process Scheduling Operations on Processes Interprocess Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems Process Control Block (PCB) (or Process Descriptor) For each process, OS maintain a data structure called process control block (also called task control block, process descriptor, task descriptor) to keep information with each process Keep information associated with each process – Process state – Program counter: address of the next instruction (special case of CPU register Saved when an interrupt occurs or context switches occurs – CPU registers Saved when an interrupt or context switches occurs (introduce later) – CPU scheduling information: process priority…… – Memory-management information Will be introduced later – Accounting information CPU time and real time used…..(see following slide) – I/O status information Open files and devices… Process Control Block (PCB) Process Control Block (PCB) … out eax, 0x60; add eax, ebx; … … out eax, 0x30; add ebx, ebx; ….. … P1 PCB pc = x, eax=y, ….., P2 PCB OS pc = i, eax=j, ….., OS Process Representation in Linux Represented by the C structure task_struct pid t_pid; long state; unsigned int time_slice struct task_struct *parent; struct list_head children; struct files_struct *files; struct mm_struct *mm; Accounting Outline Process Concept Process Scheduling Operations on Processes Inter-Process Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems Process Scheduling Term Definition – Process scheduler (or CPU scheduler) Selects a ready processes for execution on a CPU core – Degree of multiprogramming The number of processes currently in memory Outline Process Concept Process Scheduling – Scheduling Queues – CPU Scheduling – Context Switch Operations on Processes Interprocess Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems Scheduling Queues OS maintains scheduling queues of processes – Ready queue – set of all processes residing in main memory, ready and waiting to execute – A set of wait queues – set of processes waiting for events, e.g., completion of I/O – Processes migrate among the ready queue and various wait queues (see following two slides) The Ready Queue and Wait Queues Diagram of Process State Various I/O Wait Queues There may be a set of wait queues Queuing-Diagram Representation of Process Scheduling Once a process is executing, one of following events would occur (see the following slide) – The process issue an I/O request The process is placed in an I/O wait queue – The process creates a new child process The process is placed in a wait queue waiting for child’s termination – The process is removed from the core due to interrupt The process is placed in the interrupt wait queue – The process is removed from the core, due to its time slice expire The process is put back in the ready queue Queuing-Diagram Representation of Process Scheduling terminate Free PCB and resources Outline Process Concept Process Scheduling – Scheduling Queues – CPU Scheduling – Context Switch Operations on Processes Interprocess Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems CPU Scheduling CPU Scheduler (or Process Scheduler) – Select a process from ready queues and allocates a CPU core to it – See the following two slides CPU Scheduler … for (;;) User a=a+1; Applications Change to execute another application User Mode … Kernel Mode CPU_scheduler () { If (current process executes too long) select another process to run } Hardware Example: Scheduler is Invoked when a Timer Interrupt Occurs … for (;;) a=a+1; … CPU … add eax, ebx; ….. … interrupt Timer CPU Scheduler OS Interrupt Service Routine (ISR) 補充：CPU scheduler is not only invoked when timer interrupts fire. 第五章會介紹 CPU Scheduling (CPU) CPU scheduler is invoked very frequently – At least once very 100 milliseconds – Why? But, CPU scheduler cannot be invoked extremely too frequently – Why? (introduced later) CPU Scheduling Some OS introduces an intermediate from of scheduling – Swapping Swapping – Removes processes from memory when memory space is not enough Reduce the degree of multiprogramming – At some later time, the process can be re-introduced into memory Increase the degree of multiprogramming Swap Out and Swap In Disk (swap space) Outline Process Concept Process Scheduling – Scheduling Queues – CPU Scheduling – Context Switch Operations on Processes Interprocess Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems Context Switch Context switch: CPU switches from one process to another process – OS must save the state (context) of the old process in its PCB – Then OS must restore the saved state (context) of the new process from PCB 複習：Storage-Device Hierarchy Context Switch (Cont.) Context (state): – CPU registers (including Program Counter), – Memory areas – Various tables – …… – They constitute the environment or context of a process. 複習：Without State Save and Restore estette & … out eax, 0x60; add eax, ebx; CPU … eax 10 59 … ebx 525 add eax, 0x30; add ebx, eax; … ….. OS Context Switch P1’s PCB PC=0x1000 eax=10, ebx=5 ecx =9, edx = 11 etc. & save context …… context process P1 switch switch process P1 & restore CPU eax=10, eax=6, ebx=9, ebx=5, ecx=3, edx =32 ecx=9, =11 pc= pc=0x58000… 0x1000… 所以，切換Process時 (Context Switch)，必須要儲存當下Process的state，然後復原接下來要執行的Process的state! 儲存的state記錄會在PCB當中(Page 18). Context Switch P0’s PCB P1’s PCB process P0 process P1 Context Switch 1 … out eax, 0x60; add eax, ebx; CPU … context eax 59 10 … switch ebx 25 5 out eax, 0x30; add ebx, ebx; ….. … P1 PCB eax=10; ebx=5;…… eax=x; ebx=y;…… P2 PCB OS eax=59; ebx=25;…… OS Context Switch 2 … out eax, 0x60; add eax, ebx; CPU … context eax 10 100 … switch ebx 5 35 out eax, 0x60; add eax, ebx; ….. … P1 PCB eax=10; ebx=5;…… eax=x; ebx=y;…… P2 PCB OS eax=59; ebx=25;…… eax=100; ebx=35;…… OS 比較：ISR Has no State to Be Saved/Restored P0’s PCB P0’s PCB process P0 ISR Context Switch (Cont.) Context-switch time is overhead (wasted time) – System does not execute user applications while switching Hardware support for reducing context switch overhead – Existence of special instructions A single instruction to save/load all registers (See p. 13 in Chapter 5 of Assembly Language) – Sun UltraSPARC provides multiple sets of registers Content switch ⇨ change to use the current register set 複習：Related Instructions PUSHFD and POPFD – Push and pop the EFLAGS register PUSHAD pushes 32-bit general-purpose registers on stack – Order: EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI POPAD pops the same registers off stack in reverse order – PUSHA and POPA do the same for 16-bit registers.data push saveFlags ; push saved flag values saveFlags DWORD ? popfd ; copy into a variable.code pushfd ; push flags on stack pop saveFlags ; copy into a variable Multiple Sets of Registers CPU eax1=1; eax2=4; ebx1=5; ebx2=3; ecx1=8; ecx2=7; …… edx1=6; edx2=8; …… …… process P1 process P2 Outline Process Concept Process Scheduling Operations on Processes – Process creation – Process termination Interprocess Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems Process Creation A process may create several new processes – The creating process is called parent – The new processes are called children of that process – Forming a tree of processes (next slide) A Tree of Processes in Linux OS identify processes according to a unique process identifier (or pid) Process Creation (Cont.) Execution – Parent and children execute concurrently, or – Parent waits until children terminate wait() system call in Linux Address space – Child duplicate of parent (has the same program and data as the parent), or fork() system call creates a new process in Linux – Child has a new program loaded into it exec() system call replaces the process’ memory space with a new program in Linux The fork() System Call Memory Copy from Original original fork() image image New image NCHU System & Network Lab The exec() System Call Memory Copy from Original original image image fork() => Parent &childrething Load ↓then... overwrite child code New image another exec() => with another image NCHU System & Network Lab UNIX Process Creation See the following slide! Each process has a unique process id (PID) A new process is created by the fork() system call (copy) – The new (child) process duplicates the address space of the parent process Child and parent continue execution at the instruction after the fork() system call – Child: return value of fork is& S 0 – Parent: return value of fork is PID of the child process The execlp() system call is used to load a new binary file into memory – destroying the old code C Program Forking Process & 3 pid=153 returns PER memory runs for child process runs for parent wait for child process (changes to 15) parent’ code copy & pid=0 child’ code ls Process Creation Outline Process Concept Process Scheduling Operations on Processes – Process creation – Process termination Interprocess Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems Process Termination Process invokes exit() system call – Return a status value with its process identifier to parent – Parent obtains the status value and the process identifier of the child via the wait() system call – Then, process’ resources are deallocated by OS #include #include pid_t pid; int status; void exit(int status); pid_t wait(int *stat_loc); Process Termination in Linux When a process terminates and before parent calls wait() – The terminated process becomes a zombie(殭屍) process Since its process control block (PCB) still exists for storing the exit status value See the following two slides But, if parent did not invoke wait() and is terminated – The child process becomes as orphans – Thus, Linux set the child’s parent to the init init process periodically calls wait() to collect children’s exit status value See the following next slide Zombie Process wait() parent fork() exit status value child exec() exit() zombie Zombie Process A = A +1; D … & ⑫ wait(); CPU & … After running, exit(1); the code block can & ⑯ be released but not the PCB (due the status still P1 PCB to being stored & P2 PCB Zombie Process P2 PCB OS - exit status = 1 OS Orphans Process init exit() parent fork() child (no wait)) a=a+1; exec() b=b-1; orphan … Outline Process Concept Process Scheduling Operations on Processes Interprocess Communication IPC in Shared-Memory Systems Examples of IPC Systems Communication in Client-Server Systems Cooperating Processes Processes may share data with each other ⇨ cooperating processes – E.g., for information sharing Interprocess Communication (IPC) Cooperating processes require an interprocess communication (IPC) mechanism Two common models – Message passing – Shared memory Communications Models (a) Message passing. (b) Shared memory Message Passing Process A receive_msg() Process B send_msg() send_msg() memory memory copy copy Shared Memory Interprocess Communication (IPC) (Cont.) Comparisons – Message passing Useful for exchanging smaller amounts of data Easier to implement Slower; requires system calls for sending/receiving messages (via memory copying) No conflict need to be avoided – Shared memory Faster; requires no system calls when reading/writing data But need protection and synchronization Charder to implement) Microkernel System Structure message passing - (performance loss) Microkernel (Cont.) Advantages: – Easier to extend the OS By adding new services to user space and do not require kernel modification – Easier to port the OS to new architectures The kernel is small and the changes tend to be fewer – More reliable and more secure Most services are running as user processes If a service failed, the rest of the OS remains untouched Disadvantages: – Performance overhead by message passing between services – Window NT: microkernel, Windows XP: a monolithic kernel Outline Process Concept Process Scheduling Operations on Processes Interprocess Communication IPC in Shared-Memory Systems (skip for now IPC in Message Passing Systems Examples of IPC Systems Communication in Client-Server Systems Shared-Memory Shared memory remove the restriction that one process cannot access another process’s memory Shared Memory Outline Process Concept Process Scheduling Operations on Processes Interprocess Communication IPC in Shared-Memory Systems IPC in Message Passing Systems – Synchronous or asynchronous communication Examples of IPC Systems Communication in Client-Server Systems Synchronous or Asynchronous Message passing may be either blocking or non-blocking – Also known as synchronous or asynchronous Blocking - process suspended until I/O completed (synchronous – Easy to use but insufficient for some needs Nonblocking - I/O call returns immediately with as much as data available Casynchronous – With a return value indicating how many bytes were transferred Synchronous or Asynchronous I/O Example Program 2 Program 1 recvfrom ()… User Mode Kernel Mode recvfrom() receive from recvfrom () { …. …. …. } OS 網路卡 Blocking I/O waits until datagram received (occupies resources and waits for the entire time) https://medium.com/@clu1022/%E6%B7%BA%E8%AB%87i-o-model-32da09c619e6 Non-Blocking I/O returns when not app. instead of ready waiting the whole time https://medium.com/@clu1022/%E6%B7%BA%E8%AB%87i-o-model-32da09c619e6 Blocking and Nonblocking I/O Blocking is considered synchronous – Blocking send: sender blocked until the message is received by the receiver – Blocking receive: receiver blocks until a message is available send status Non-blocking is considered asynchronous may be unknown – Non-blocking send: sender sends the message and resumes operation & – Non-blocking receive: receiver retrieves either a valid message or a null Chapter 4 Thread & Concurrency Outline Overview Multicore Programming Multithreading Models Thread Library Implicit Threading Threading Issues Operating-System Examples Motivations Problem: global warming (全球暖化) & Solutions – 1. Reduces personal desires analogue – 2. Resource sharing L Problem: process is high overhead – Why? Solutions – 1. Reduces personal desires: minimize code size or shorten execution time – 2. Resource sharing: by threads Example: Matrix Multiplication- Single Process Solution memory Assume four CPU Core 1 code cores are available data Core 2 stack ….. Core 3 - 1. Three CPU cores are idle 2. This process has long Core 4 execution time Example: Matrix Multiplication- Multiple Processes Solution code Assume four CPU & Core 1 data fork() cores are available stack fork() fork() Core 2 … code Core 3 data stack 1. All of the four CPUs are used. 2. But, the code and data sections Core 4 … of these four processes are all the same (memory wastage) … … Example: Matrix Multiplication- One Process with Multiple Threads Solution one memory process Assume four CPU &code shared cores are available Core 1 data pthread_create() pthread_create() stack pthread_create() individual Core 2 stack stack 1. All CPU Cores are busy 2. Memory usage is economic Core 3 stack 3. The process’s execution time is short Core 4 問題:同一個Process的Threads哪些可以共享? 哪些不行? stack code, heap data, Thread Overview Process: High overhead abstraction to execute a program – E.g., creating process is as an expensive operation. Each process have its own code, data, heap, and stack segments Solutions: thread – A basic unit of CPU utilization – Like process, also need resources like thread ID, program counter, register set, and stack… – Some resources are shared with other threads belonging to the same process Code section, data section, and other OS resources, such as open files and signals Single and Multithreaded Processes · (register) If Three CPU Cores are Available main() { a process pthread_create(runner()); I Thread 1 x = x +1; Thread 1 y = y + 1; } runner() { If three CPU cores pthread_create(readrun()); Thread 2 are available, these i = i + 6; three threads can j = j * 8; 2 Thread 2 run in parallel } readrun() { Thread 3 3 c = c + 2; Thread 3 d = 10 ; } Multithreaded Process: an application can have several different threads of activity within the same address space Create a Process v.s Create a Thread memory memory one process code code data data fork() thread_create() stack stack … … stack New thread code … New data process stack … Thread Control Block (or Thread Descriptor) TCB Thread ID Thread State (Run, Waiting…) Program Counter Registers …… Each thread has its own TCB, like each process has its PCB 問題：為什麼TCB 必須記錄Program Counters 和Registers Values? 也就是為什麼同一個Process下的Threads不共享 Program Counters和Registers Values (see the following slide) Answer: Threads也有自己的執行狀態。所以，Context Switch時必須 (1)將目前正在執行Thread的狀態儲存到TCB (2)復原接下來要執行Thread的狀態 (see the following slide) Context Switches between Threads - Similar to Context Switch between Processes Thread 1 CPU main() eax = 3; 8 8;; { ebx = 19; 11; I! Thread 1. Thread 1 a = a +1; Context switch pthread_create(..runner()); #T2 } Thread 2 runner() {.. Thread 2 eax = 8 ; ebx = 11; TCB1 b = b + 5; TCB Thread 2 (in memory) c = b * 10; TCB2 } Context switch Change to Thread 1 eax = 3 ; ebx = 19; E Why Can’t Share the Same Stack main()D stack {. 3 stackframe arugment a ESP return address. local variables a = a + 1; argument function_1(…); ESP 2 return address function - 1C) exit(1); local variables } ESP argument return address function. function_1() local variables { b = b - 1; function_2(…); o return; } function_2() { … return; } From above figure, do you know why threads of the same process cannot share the same stack? Benefits Responsiveness – If one thread is blocked or performing a lengthy operation, other threads can continue running Resource Sharing – Threads share the memory (code and data) and resources of the process to which they belong Economy – Create and context-switch thread is much quickly than processes – Compared with processes, 30 times faster in creating and 5 times faster when context switch Scalability – Multithreading on a multi-CPU machine increases concurrency – Each thread may be running in parallel Examples A lot of software packages are multi-threaded – File servers or web servers Needs to handle several requests over a short period How to do ? – 1. Process sequentially: bad – 2. Create a single process for each request » Process creation is time consuming and resource intensive – 3. Create a single thread for each request » More efficient – Web browser: One thread: display images or text, one thread: retrieve data – Matrix multiplication – …… (Traditional) Multi-Process I/O Solution 1. Receive requests Dispatcher process 2. create a process to service the request Multi-process I/O model. Each process handles 1 client at a time. https://www.rubyraptor.org/how-we-made-raptor-up-to-4x-faster-than-unicorn-and-up-to-2x-faster-than-puma-torquebox/ Multi-Thread I/O Solution thread thread thread thread 1. Receive requests Dispatcher 2. create a thread to thread service the request Multi-thread I/O model. Each thread handles 1 client at a time. https://www.rubyraptor.org/how-we-made-raptor-up-to-4x-faster-than-unicorn-and-up-to-2x-faster-than-puma-torquebox/ 複習：Example: Matrix Multiplication- One Process with Multiple Threads Solution one memory process Assume four CPU code cores are available Core 1 data pthread_create() pthread_create() stack pthread_create() Core 2 stack stack 1. All CPU Cores are busy 2. Memory usage is economic Core 3 stack 3. The process’s execution time is short Core 4 Outline Overview Multicore Programming – Concurrency v.s. Parallelism – Types of Parallelism – Multi-Core Programming Challenges Multithreading Models Thread Library Implicit Threading Threading Issues Operating-System Examples Concurrency v.s. Parallelism All running , but only one is being processed at a time On a single-processor system, processes were running concurrently, but not in parallel – Concurrency supports more than one task making progress However, with multicore systems, processes can run in parallel – Parallelism implies a system can perform more than one task simultaneously Concurrency vs. Parallelism Four Threads: T1, T2, T3, T4 Concurrent Execution on a Single-core System Parallel Execution on a Multi-core System Outline Overview Multicore Programming – Concurrency v.s. Parallelism – Types of Parallelism – Multi-Core Programming Challenges Multithreading Models Thread Library Implicit Threading Threading Issues Operating-System Examples Types of Parallelism Two types of parallelism: data parallelism v.s. task parallelism Data parallelism – Running the same task on different components of data – Ex: summing an array of size 1000 (if two cores) Thread A on one core sums the element … summing first half summing second half Thread B on another core sum the element ….. Task parallelism – Running many tasks on the same data – Ex: summing and multiplying an array of size 1000 (if two cores) Thread A on one core sums the element … summing Thread B on another core performs element x x…x multiplying Data Parallelism and Task Parallelism Types of Parallelism (Cont.) Hybrid – Most applications use data parallelism + task parallelism – Ex: summing and multiplying an array of size 1000 (if four cores) Thread A on one core sums the element … Thread B on another core performs element x x…x Thread C on another core performs element x x…x Thread D on another core performs element x x…x Outline Overview Multicore Programming – Concurrency v.s. Parallelism – Types of Parallelism – Multi-Core Programming Challenges Multithreading Models Thread Library Implicit Threading Threading Issues Operating-System Examples Multi-Core Programming Challenges Multicore programming is challenge – Divide activities Divide an application into separate threads – Balance Each thread perform equal work of equal value – Data splitting Data accessed by each thread must be divided to run on each core – Data dependency Discussed in Chapter 6 – Testing and debugging More difficult than single-threaded applications Outline Overview Multicore Programming Multithreading Models Thread Library Implicit Threading Threading Issues Operating-System Examples Supporting Threads 思考 1: – fork() is used to create process. – 所以，程式設計師需要一個function來create thread, 假設此一function 為 pthread_create() 思考 2: – fork() function is provided by OS // calling fork() calls OS’s function – So, pthread_create() is provided by ? OS User-level library (Many-to-one) Thread Types User threads – Support for thread is provided at the user level – Usually by user-level library Kernel threads – Support for thread is provided at the kernel level – Usually by OS Multithreading Models Many-to-One Model One-to-One Model Many-to-Many Model Many-to-One Used on systems that do not support kernel threads. Thread management is done by thread library in user space: Efficient – Why? (shown later) Many-to-One: many user-level threads mapped to single kernel thread, i.e., kernel process – 傳統沒有使用thread的processes我們視為single thread process Blocking problem: entire process is blocked if a thread makes a blocking system call No support for running in parallel on MP – Since the kernel only sees a single thread (process) Many-to-One Model (process kernel thread Many-to-One Model (If Only One Processor or Even Multiple Processors) Code Section Thread 1 main() a process { I Thread 1 a = a +1; they can't run at the Thread 1 pthread_create(runner()); same time, as user-level Tester I Context switch code can't change how } 1- 2 Thread 2 the user-level threads are runner() { assigned to the CPU's cores.

Midterm Exam PDF - Operating Systems

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue