跳到主要內容

發表文章

Distributed transactions

Table of contents [ hide ] Basic theory  CAP States that any distributed data store can provide only two of the following three guarantees. Consistency Every read receives the most recent write or an error. Availability Every request receives a (non-error) response, without the guarantee that it contains the most recent write. Partition tolerance The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes. Typical architecture of distributed systems When a network partition failure happens, it must be decided  whether to do one of the following: CP: cancel the operation and thus decrease the availability but ensure consistency AP: proceed with the operation and thus provide availability but risk inconsistency. BASE Basically-available, soft-state, eventual consistency. Base theory is the practical application of CAP theory, that is, under the premise of the existence of partitions and copies, through certain syste
張貼留言
閱讀完整內容

Virtual memory

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
張貼留言
閱讀完整內容

Memory

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 the file system
張貼留言
閱讀完整內容

Deadlocks

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 operating s
張貼留言
閱讀完整內容

Synchronization

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
張貼留言
閱讀完整內容

Cpu scheduling

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 scheduling: Sche
張貼留言
閱讀完整內容

Thread and concurrency

Table of contents [ hide ] Thread Thread is a lightweight process, a basic unit of CPU utilization. All threads belonging to the same process share: Code section. Data section. OS resources(e.g. open files and signals) Each thread has its own(thread control block): Thread ID. Program counter. Register set. A tack. Benefits of multithreading: Responsiveness. Resource sharing. Utilization of NP arch. Economy. User vs Kernel threads User threads Thread management is done by the user-level thread library. POSIX Pthreads. Win32 threads. Java threads. Thread library provides support for thread creation, scheduling, and deletion. Generally fast to create and manage. If the kernel is single-threaded, a user-thread block -> entire process blocks even if other threads are ready to run. Kernel threads Supported by the kernel(OS) directly. Windows 2000(NT) Solaris Linux Tr64 UNIX The kernel performs thread creation, scheduling, etc. Generally slower to create and manage. If a thread is blo
張貼留言
閱讀完整內容

Process

Table of contents [ hide ] A process is a program that is executed in memory. Process layout A process includes: Code segment. Data section-global variables. Stack-temporary local variables and functions. Heap-dynamic allocated variables or classes. Current activity(program counter, register contents). A set of associated resources. Process status Process control block A process control block (PCB) is the kernel data structure that represents a process in an operating system.   Context switch means the kernel saves the state of the old process and loads the saved state for the new process. Process state. Program counter. Cpu register. Cou scheduling. Memory-management information. I/O status information. Accounting information. Process Schedulers Short-term(CPU scheduler) Selects which process should be executed and allocated CPU(ready state -> run state). Long-term(job scheduler) Selects which processes should be loaded into memory and brought into the ready queue(new state -
張貼留言
閱讀完整內容