memo from the small room

Table of contents [ hide ] Designing programs is a common job for every engineer, so templates help simplify the job of designing each program. Update History Let everyone know the latest version and update information. background Write down why we need this program and what is the background for building this program. Target Target functionality The goal of the program, what function to achieve, the main module and submodule, and these modules' relationship. Target performance Specific benchmarks such as QPS or milliseconds to evaluate programs. Target architecture Stability. Readability. Maintainability. Extendability. ... Others Target Overall design Design principles and thinking Explain how and why the program was designed. Overall architecture An overall architectural picture. Dependency Module dependencies on other modules or programs. Detail design Program flow design Program flow design diagram. API design The details of the API, and how to interact with the frontend ...

Table of contents [ hide ] I/O hardware Port: a connection point between I/O devices and the host. E.g.: user ports. Bus: a set of wires and a well-defined protocol that specifies messages sent over the wires. E.g.: PCI bus. Controller: a collection of electronics that can operate a port, a bus, or a device. A controller could have its own processor and memory. Etc. (e.g.: SCSI controller). Basic I/O Method (Port-mapped I/O) Each I/O port (device) is identified by the unique port address. Each I/O port consists of four registers (1~4bytes). Data-in register: read by the host to get input Data-out register: written by the host to send output Status register: read by the host to check I/O status Control register: written by the host to control the device The program interacts with an I/O port through special I/O instructions (different from mem. access). X86: IN, OUT I/O methods Categorization Depending on how to address a device: Port-mapped I/O. Use different address spaces for me...

Table of contents [ hide ] Virtual memory Separation of user logical memory from physical memory. To run an extremely large process. Logical address space can be much larger than physical address space. To increase CPU/resource utilization. A higher degree of multiprogramming degree. To simplify programming tasks. A free programmer from memory limitation. To run programs faster. Less I/O would be needed to load or swap. Process & virtual memory Demand paging: only bring in the page containing the first instruction. Copy-on-write: the parent and the child process share the same frames initially, and frame-copy. when a page is written. Allow both the parent and the child process to share the same frames in memory. If either process modifies a frame, only then a frame is copied. COW allows efficient process creation(e.g., fork()). Free frames are allocated from a pool of zeroed-out frames(for security reasons). The content of the frame is erased to 0 Memory-Mapped File: map a fi...

Table of contents [ hide ] Modern operating systems use paging to manage memory. In this process, physical memory is divided into fixed-sized blocks called frames and logical memory into blocks of the same size called pages. Memory-management unit Hardware devices that map virtual to the physical address. The value in the relocation register is added to every address generated by a user process at the time it is sent to memory. Logical vs Physical Address Logical address: generated by CPU, a.k.a. virtual address. Physical address:  seen by the memory module. Compile-time & load-time address binding: Logical address = physical address. Execution-time address binding: logical address != physical address. The user program deals with logical addresses; it never sees the real physical address. Swap A process can be swapped out of memory to a backing store, and later brought back into memory for continuous execution. Backing store: a chunk of the disk, separated from t...

Table of contents [ hide ]  A set of the blocked processes each holding some resources and waiting to acquire a resource held by another process in the set. Necessary conditions All four conditions must hold for possible deadlock: Mutual exclusion:  Only 1 process at a time can use a resource. Hold and wait: A process holding some resources is waiting for another resource No preemption: A resource can be only released by a process voluntarily. Circular wait: There exists a set {P0,P1…} of waiting processes such that P0 -> P1 -> P2 …..Pn -> P0 Handling Deadlocks Ensure the system will never enter a deadlock state. Deadlock prevention: ensure that at least one of the 4 necessary conditions cannot hold. Deadlock avoidance: dynamically examines the resources allocation state before allocation. Allow to enter a deadlock state and then recover. Deadlock detection. Deadlock recovery. Ignore the problem and pretend that deadlock never occurs in the system. Use by most op...

Background Concurrent access to shared data may result in data inconsistency. Maintaining data consistency requires a mechanism to ensure the orderly execution of the cooperating process. Race condition Race condition: the situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes the list. To prevent a race condition, concurrent processes must be synchronized. On a single-processor machine, we could disable interrupt or use non-preemptive CPU scheduling. Commonly described as a critical section problem Critical Section Requirements Mutual Exclusion: if process P is executing in its CS, no other processes can be executing in its CS. Process: if no process is executing in its CS and there exist some processes that wish to enter their CS, these processes cannot be postponed indefinitely. Bounded waiting: a bound must exist on the number of times that other processes are allowed to enter their C...

Table of contents [ hide ] Basic concept The idea of multiprogramming: Keep several processes in memory. Every time one process has to wait, another process takes over the use of the CPU. CPU-I/O burst cycle: Process execution consists of a cycle of CPU execution and I/O wait(i.e., CPU burst and I/O burst). Generally, there is a large number of short CPU bursts and a small number of long CPU bursts An I/O-bound program would typically have many very short CPU bursts. A CPU-bound program might have a few long CPU bursts. CPU scheduler Select from the ready queue to execute(I.e allocates an APU for the selected process) CPU scheduling  decision may take place when a process: Switch from running to waiting state. Switch from running to ready state. Switch from waiting to ready. Terminates. Non-preemptive scheduling: Scheduling under 1 and 4(no choice in terms of scheduling). The process keeps the CPU until it is terminated or switched to the waiting state. Preemptive schedul...