admin管理员组

文章数量:1642466

文章目录

  • Introduction
    • What is an operating system
    • What Operating system do
      • Computer system structure
      • User view
      • System view
    • Computer-System organization
      • Von Neumann Model
      • Common Functions of Interrupts
      • Interrupt handling
      • Storage structure
      • IO structure
    • Computer System Architecture
    • Operating System Structure
      • Interrupt driven
      • Dual mode
      • Timer
      • System boot
    • System call
      • system call
    • Process management
      • Process
        • Process Management Activities
    • Memory Management
    • Storage Management
    • Conclusion
  • Operating System Structures
    • Objectives
    • Operating System Service
      • User view
      • System view
    • Operating System Structure
  • Process
    • Objectives
    • Concept
      • Process Execution
    • Process Scheduling
    • Operating on Processes
    • interprocess communication
  • Threads
    • Objectives
    • Introduction
      • Multicore programming
      • Multithreading models
    • Thread library
    • Implicit Thread
    • Thread Issues
  • CPU scheduling
    • Objectives
    • Basic concepts
      • CPU Scheduler
      • Dispatcher
      • Scheduling Criteria
      • Scheduling timing
    • Scheduling algorithm
      • First Come First Serve (FCFS)
      • Priority
        • Shortest Job First (SJF)
        • Highest Response Ratio Next (HRRN)
        • Preemptive SJF
      • Round Robin (RR)
      • Multilevel queue
      • Multilevel feedback queue
      • Lottery Scheduling
    • Thread Scheduling
    • Multiple-Processor Scheduling
  • Process synchronization
    • Objectives
    • Background
      • Race Condition
    • The critical section problem
      • critical section
      • solution to critical-section problem
    • Mutex Locks
      • Pthread Locks
      • Controlling Interrupt (failed)
      • Using lock flag (failed)
      • Peterson’s solution
      • Bakery Algorithm
      • test and set
      • compare and swap
        • Using CAS to implement lock-free synchronization
      • Lock-Link and Store Conditional
      • Fetch and Add
      • Span waiting
      • Yield:
      • Using queue
      • `setpark()`
    • Lock Data Structures
      • Concurrent Counter
      • Concurrent Linked List
      • Concurrent Queue
      • Concurrent Hash Table
    • Condition Variables
    • semaphore
      • Basic Synchronization Patterns
        • Signaling
        • Rendezvous
        • Mutex
        • Multiplex
        • Barrier
        • Pairing
        • The Producer-Consumer Problem
        • The Dining Philosophers
        • The Readers-Writers Problem
    • monitors
  • Deadlock
    • Objectives
    • system model
    • Deadlock Characterization
      • Four necessary condition
      • Resource-allocation graph
    • Deadlock Prevention
      • circular wait
      • hold and wait
      • no preemption
      • Mutual exclusion
    • Deadlock Avoidance
      • safe state
      • Avoidance Alg.
        • Resource-allocation graph alg.
        • The Banker's Algorithm
    • Dead Detection
      • Wait-for graph alg.
    • Deadlock recovery
  • Main memory
    • Objectives
    • Background
      • Program loading and linking
      • address binding
      • Dynamic Loading and Linking
      • Address Space
    • Address Translation
    • Segmentation
    • free space management
    • paging
    • Translation Lookaside Buffer
    • Structure page table
      • Paging and Segments
      • hierarchical page tables
        • basic idea
        • page directory table
    • Structure of the Page Table
    • Swapping
    • Example Architectures
  • Virtual Memory
    • Objectives
    • Background
    • Demand paging
      • Features
      • basic concepts
      • Valid-invalid bit
      • Page fault
      • aspect of demand paging
      • Performance of demand page
        • stage in demand paging
        • Besides the context switch
        • demand paging optimization
      • Inverted page table
    • Copy on write
    • page replacement
    • page and frame replacement algorithm
      • optimal algorithm
      • First in first out
      • Least recently used(LRU) algorithm
      • LRU approximation algorithm
      • Most frequently used(MFU)
      • Page buffering algorithm
      • Random algorithm
    • allocation of frames
      • global/local replacement
    • Thrashing
    • Memory Mapped Files
    • Allocating Kernel Memory
      • Buddy Allocator
      • Slab Allocator
  • Mass Storage System
    • Objectives
    • Disk structure
      • Track skew
    • disk scheduling
      • first come first serve
      • shorest seek time first
      • SCAN algorithm
      • C-SCAN
      • LOOK
      • C-LOOK
      • Shortest Positioning Time First (SPTF)
      • Selecting a Disk-scheduling algorithm
    • Raid Structure
  • File System
    • Objectives
    • File and Directories
    • File-system Interface
      • File Interface
      • Directory Interface
      • Links
      • File System Interface
  • File-system implementation
    • Objectives
    • Typical File System
      • Overall Organization
      • Typical File System
    • Fast File System
    • FSCK and Journaling
    • Log Structure File System
    • Network File System
      • Basic Distributed File System
  • I/O System
    • polling
    • Interrupt-driven
    • direct memory access

Introduction

What is an operating system

  • A program that acts as an intermediary between a user of a computer and the computer hardware
  • operating system goals:
    • Execute user programs and make solving user problems easier
    • Make the computer system convenient to use
    • Use the computer hardware in an efficient manner

What Operating system do

Computer system structure

  • hardware: provides basic computing resources: CPU,memory, IO device
  • operating system: controls and coordinates use of hardware among various applications and users
  • Application programs: define the ways in which the system resources are used to solve the computing problems of the users
  • User: people, machines, other computers

User view

  • cares:
    • convience
    • ease of use
    • good performance
  • don’t cares:
    • resource utilization

System view

  • OS is a resource allocator
    • Manages all resources
    • decides between conflicting requests for efficient and fair resource use
  • OS is a control program
    • Controls execution of programs to prevent errors and improper use of the computer

Computer-System organization

Von Neumann Model

an electronic digital computer with parts consisting of :

  • a processing unit containing an arithmetic logic unit and processor registers
  • a control unit containing an instruction register and program counter
  • a memory to store both data an instructions
  • external mass storage
  • input and output machanisms

Common Functions of Interrupts

  • an interrupt is an input signal to the processor indicating an event that needs immediate attention
  • interrupt transfer control to the interrupt service routine generally, through the interrupt vector, which contains the addresses of all the service routines
  • Interrupt architecture must save the address of the interrupted instruction
  • A trap or exception is a software-generated interrupt caused either by an error or a user request
  • An operating system is interrupt driven

Interrupt handling

  • the operating system preserves the state of the CPU by storing registers and the program counter
  • determines which type of interrupt has occurred:
    • polling
    • vectored interrupt system
  • separate segments of code determine what action should be taken for each type of interrupt

Storage structure

  • Main memory: only large storage media that the CPU can access directly
    • random access
    • typically volatile
  • Secondary storage: extension of main memory that provides large nonvolatile storage capacity
  • hard disks: rigid metal or glass platter covered with magnetic recording material
    • disk surface is logically divided int tracks, which are subdivided into sectors
    • the disk controller determines the logical interaction between the device and the computer
  • Solid state disk: faster than hard disks, nonvolatile
    • various technologies
    • becoming more popular

IO structure

  • No interrupts: after IO starts, control returns to user program only upon IO completion
    • wait instruction idles the CPU
    • Wait loop
    • At most one IO request is outstanding at a time, no simultaneous IO processing
  • Interrupt Driven: after IO starts, control return to user program without waiting for IO completion
    • system call: request to the OS to allow user to wait for IO completion
    • Device status table contains entry for each IO device indicating its type, address, and state
    • OS indexes into IO device table to determine device status adn to modify table entry to include interrupt
    • Device Driver for each device controller to manage IO. Provides uniform interface between controller and kernel
  • Direct Memory Access:;
    • Used for high speed IO devices able to transmit information at close to memory speed
    • Device controller transfer blocks of data from buffer storage directly to main memory without CPU intrevention
    • Only one interrupt is generated per block, rather than the one interrupt per byte

Computer System Architecture

  • Multiprocessor systems growing in use and importance
    • two types
      • Asymmetric multiprocessing: each processor is assigned a specific task
      • symmetric multiprocessing: each processor performs all tasks
  • Dual core design
  • Cluster systems
    • like multiprocessor system, but multiple systems working together
    • Loosely coupled systems:
      • ussually sharing storage viaa a storage area network
      • provides a high availability service which survives failures
        • Asymmetric clustering has one machine in hot standby mode
        • Symmetric clustering has multiple nodes running applications, monitoring each other
      • Some clusters are for high performance computing
        • Applications must be written to use parallelization

Operating System Structure

  • multiprogramming
    • single user cannot keep CPU and IO devices busy at all times
    • Multiprogramming organizes jobs so CPU always has one to execute
    • A subset of total jobs in system is kept in memory
    • One job selected and run via job scheduling Long term scheduling
    • when it has to wait, OS switches to another job
  • Timesharing: is logical extension in which CPU switches jobs so frequently that users can interact with each job while it is running, creating interactive computing

Interrupt driven

  • hardware interrupt by one of teh devices
  • software interrupt
    • Software error
    • request for operating system service
    • other process problems include infinite loop, processes modifying each other or the operating system

Dual mode

operation allows OS to protect itself and other system components

  • user mode and kernel mode
  • Mode bit provided by hardware
    • provides ability to distinguish when system is running user code or kernel code
    • some instructions designated as privileged, only executable in kernel mode
    • system call changes mode to kernel, return from call reset it to user
  • Increasingly PCUs support multi-mode operations
    • Virtual machine manager(VMM) mode for guest VMs

Timer

  • Timer to prevent infinite loop / process hogging resources
    • Timer is set to interrupt the computer after some time period
    • keep a counter that is decremented by the physical clock
    • operating system set teh counter
    • when counter zero generate an interrupt
    • set up before scheduling process to regain control or terminate program that exceeds allowed time

System boot

OS@run(kernel mode) Hardware Program(user mode) initialize trap table remember address of: system call handler timer hander,illegal instruction handler start interrupt timer start timer, interrupt after X ms to startprocess A: return from trap move to user mode run process timmer interrupt, move to kernel mode, jump to interrupt handler OS@run(kernel mode) Hardware Program(user mode)

System call

system call

  1. programming interface to teh services provided by the OS
  2. most accessed by a program via a high-level API rather than direct system call use

Process management

Process

  • A process is a program in execution. It is a unit of work within the system. Program is a passive entity, process is an active entity
  • Process needs resources to accomplish its task
    • CPU, memory, IO, files
    • initialization data
  • Process termination requires reclaim of any reusable resources
  • single threaded process has one program counter specifying location of next instruction to execute
  • Multi-threaded process has one program counter per thread
  • Typically system has many processes, some user, some operating system running concurrently on one or more CPUs
Process Management Activities
  • scheduling processes and threads on the CPUs
  • Creating and deleting both user and system processes
  • Suspending and resuming processes
  • Providing mechanisms for process synchronization
  • Providing mechanisms for process communication

Memory Management

  • to execute a program, all of the instructions must be in memory
  • All of the data that is needed by the program must be in memory
  • memory management determines what is in memory and when
    • Optimizing CPU utilization and computer response to users
  • Memory management activiteis:
    • Keeping track of which parts of memory are currently being used and by whom
    • Deciding which processes and data to move into and out of memory
    • allocating and deallocating memory space as needed

Storage Management

  • OS provides a uniform, logical view of information storage

  • Abstracts physical properties to logical storage unit: file

  • each medium is controlled by a device

    • varying properties include access speed, capacity, data-transfer rate, access method

  • File system managemnt

    • Files usually organized into directories
    • access control on most systems to determine who can access what
    • OS activities include
      • Creating and deleting files and directories
      • primitives to manipulate files and directories
      • mapping files onto secondary storage
      • backup files onto stable storage media

  • Mass storage management

    • Usually disks used to store data that does not fit int main memory or data that must be kept for a “long” period of time
    • proper management is of central importance
    • entire speed of computer operation hinges on disk subsystem and its algorithms
    • OS activities
      • Free space management
      • storage allocation
      • disk scheduling
    • Some storage need not be fast
      • Tertiary storage includes optical storage, magnetic tape
      • still must be managed by OS or applications
      • Varies between WORM write one , read many times, and RWread write

  • Caching

    • important principle, performed at many levels in a computer

    • Information in use copied from slower to faster storage temporarily

    • faster storage checked first to determine if information is here

      • if cache hit: information used directly from cache
      • if cache miss: data copied to cache and used there

    • Cache smaller than storage being cached

      • cache management important design problem
      • cache size and replacement policy

    • Multitasking issue

      • Multitasking environments must be careful to use most recent value, no matter where it is stored in the storage hierarchy
      • multiprocessor environment must provide cache coherency in hardware such that all CPUs have the most recent value in their cache
      • Distributed environment situation even more complex

  • IO subsystem

    • One purpose of OS is to hide peculiarities of hardware devices from the user
    • IO subsystem consists of
      • Memory management of IO including buffer storing data temporarily while it is being transferred caching storing parts of data in faster storage for performance, spooling the overlapping of output of one job with input of other jobs
      • general device driver interface
      • drivers for specific hardware devices

Conclusion

  • key ideas:
    • Virtualization: the OS takes a physical resource and transforms it into a more general, powerful and easy-to-use virtual form of itself
    • Concurrency: many problems arise, and must be addressed when working on many things at once in the same program
    • Persistence: the OS makes information persist, despite computer crashes, disk failures, or power outages
    • Protection: any mechanism for controlling access of processes or users to resources defined by the OS
    • security: defense of the system against internal and external attacks
  • Systems generally first distinguish among users, to determine who can do what
    • User identities include name and associated number, one per user
    • User ID then associated with all files, processes of that user to determine access control
    • Group identifier allows set of users to be defined and controls managed, then also associated with each process, file
    • privilege escalation allows user to change effective ID with more rights

Operating System Structures

Objectives

  1. To describe the services an operating system provides to users, processes, and other systems.
  2. To discuss the various ways of structuring an operating system
  3. To explain how operating systems are installed and customized and how they boot

Operating System Service

User view

  1. User interface
    1. Almost all operating systems have a user interface (UI)
    2. Varies between Command-Line (CLI), Graphics User Interface (GUI), Batch.
  2. Program execution
    1. The system must be able to load a program into memory and to run that program, end execution, either normally or abnormally (indicating error).
  3. I/O operations
    1. A running program may require I/O, which may involve a file or an I/O device.
  4. File-system manipulation
    1. The le system is of particular interest. Programs need to read and write les and directories, create and delete them, search them, list le Information, permission management.
  5. Communications
    1. Processes may exchange information, on the same computer or between computers over a network.
  6. Error detection
    1. OS needs to be constantly aware of possible errors

System view

  1. Resource allocation
    1. When multiple users or multiple jobs running concurrently, resources must be allocated to each of them.
    2. Many types of resources—CPU cycles, main memory, le storage, I/O devices.
  2. Accounting
    1. To keep track of which users use how much and what kinds of computer resources.
  3. Protection and security
    1. The owners of information stored in a multiuser or networked computer system may want to control use of that information, concurrent processes should not interfere with each other.
    2. Protection involves ensuring that all access to system resources is controlled
    3. Security of the system from outsiders requires user authentication, extends to defending external I/O devices from invalid access attempts

Operating System Structure

Process

Objectives

  1. To introduce the notion of a process – a program in execution, which forms the basis of all computation.
  2. To describe the various features of processes, including scheduling, creation and termination, and communication.
  3. To explore interprocess communication using shared memory and message passing.
  4. To describe communication in client-server systems.

Concept

  1. Process:

    1. a program in execution; process execution must progress in sequential fashion
    2. Program is passive entity stored on disk (executable le), process is active

  2. Process State

    1. new: the process is being created
    2. running; instruction are being executed
    3. Waiting: the process is waiting for some event to occur
    4. ready: the process is waiting to be assingned to a processor
    5. Terminated: the process has finished execution

  3. Process Data Structure: Process Control Block:

Process Execution

  1. Direct Execution
    1. Advantage:
      1. fast
    2. Disadvantage:
      1. Protection
        1. How can the OS make sure the program doesn’t do anything that we don’t want it to do
        2. Protection via dual mode and system call
      2. Time sharing
        1. How does the operating system stop it from running and switch to another process
        2. Time sharing via context switch
  2. Limited Execution
  3. Process Switch
    1. Via interrupt
  4. Context Switch: saving and restoring context
    1. User registers are implicitly saved by the hardware, into the kernel stack.
    2. Kernel registers are explicitly saved by the OS, into the PCB in memory.

Process Scheduling

  1. Process scheduler selects among available processes for next execution on CPU

  2. Scheduling queues

    1. Job queue: set of all processes in the system

    2. Ready queue: set of all process residing in main memory, ready and waiting to execute

    3. Device queues: set of processes waiting for an IO device

  3. Classification

    1. Short term schedule: select which process should be executed next and allocates CPU
    2. Long term schedule: select which process should be brought into ready queue
    3. Medium term scheduler : can be added if degree of multiple programming needs to decrease remove process from memory, store on disk, bring back in from disk to continue execution: swapping

Operating on Processes

  1. Process Creation

    1. Parent process create children processes, which, in turn create other processes, forming a tree of processes
    2. Generally, process identified and managed via a process identifier (pid)

  2. Resource sharing options

    1. Parent and children share all resources
    2. Children share subset of parent’s resources
    3. Parent and child share no resources

  3. Execution options

    1. Parent and children execute concurrently
    2. Parent waits until children terminate

  4. Address space

    1. Child duplicate of parent
    2. Child has a program loaded into it

  5. UNIX examples:

  6. Process Termination:

    1. Process executes the last statement and then asks the operating system to delete it using the exit() system call.
      1. Returns status data from child to parent
      2. Process’ resources are deallocated by operating system
    2. Parent may terminate the execution of children processes using the abort()system call
    3. If no parent waiting , process is a zombie
    4. If parent terminated without invoking wait(), process is an orphan

interprocess communication

  1. Shared memory

    1. an area of memory sahred among the processes that wish to commnunicate

    2. the communication is controlled under users process not the operating system

  2. Message passing

    1. Classification Block and non-block
      1. Blocking is considered synchronous
      2. Non-blocking is considered asynchronous

  3. Comparison between Message passing and Shared Memory

    1. Message passing is useful for exchanging smaller amounts of data, because no conflict need be avoided.
    2. Message passing is easier to implement in a distributed system than shared memory.
    3. Shared memory can be faster than message passing
    4. Message passing provides better performance than shared memory in multi-processing systems
      1. Shared memory suers from cache coherency issues

  4. Communication in Client-Server Systems

  5. Remote Procedure Calls

    1. Remote procedure call (RPC) abstracts procedure calls between processes on networked systems

  6. Pipes

    1. Ordinary pipes — cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created.
    2. Named pipes—can be accessed without a parent-child relationship.

Threads

Objectives

  1. To introduce the notion of a thread—a fundamental unit of CPU utilization that forms the basis of multithreaded computer systems
  2. To discuss the APIs for the Pthreads, Windows, and Java thread libraries
  3. To explore seral strategies that provide implicit threading
  4. To examine issues related to multithreaded programming
  5. To cover operating system support for threads in Windows and Linux

Introduction

Multicore programming

  1. Parallelism implies a system can perform more than one task simultaneously
  2. Concurrency supports more than one task making progress
  3. Type of parallelism
    1. data parallelism: distributes subsets of the same data across multiple cores, same operation on each
    2. Task parallelism: distribute across cores, each thread performing unique opeartion
  4. Amdahl’s Law: s p e e d u p ≤ 1 s e r i a l + 1 − s e r i a l n c o r e s speedup \le \frac{1}{serial+\frac{1-serial}{ncores}} speedup≤serial+ncores1−serial​1​

Multithreading models

  1. User thread and Kernel thread:

    1. user threads: management done by user-level thread library
    2. kernel thread: Supported by the kernel

  2. Motivation of User thread and kernel thread

    1. User thread
      1. advantage:
        1. no kernel intervention, hence more efficient
      2. disadvantage:
        1. Since the kernel only recognizes the containing process, if one thread is blocked, every other threads of the same process are also blocked because the containing process is blocked
    2. Kernel thread
      1. advantage:
        1. block one thread will not cause other thread of the same process to block
        2. In a multiprocessor environment, the kernel can schedule threads one different processors
      2. disadvantage:
        1. slower than user thread

  3. Many to One model:

  4. One to One:

  5. Many to Many:

  6. Two Level Model:

Thread library

  1. Create thread API
int phread_create(phread_t* thread, const pthrad_atrr_t* attr, void* (*start_toutine)(void*), void* arg)
  //create a pointer to structure of this thread
  //args are the arguments
  //run start_routine and store in thread
  1. thread completion
int pthread_join(phread_t* thread, void** value_ptr)
  //complete thread
  //return value_ptr

Implicit Thread

  1. Thread pools: Create a number of threads in a pool where they await work
    1. Usually slightly faster to service a request with an existing thread than create a new one
    2. allows the number of thread in the applications to be bound to the size of the pool
    3. separating task to be performed from mechanics of creating task allows different strategies for running task

Thread Issues

  1. Semantics of fork() and exec() system calls
    1. for fork: provides two version of fork()
    2. for exec: replace the entire process, including all thread
  2. Thread cancellation
    1. Asynchronous cancellation: terminates the target thread to be cancled immediately
    2. deferred cancellation: allows the target thread to periodically check if it should be cancel
  3. Signal Handling
    1. Signals are used in UNIX system to notify a process that a particular event has occurred
    2. A signal handler is used to process signals
  4. Thread Local storage: allows each thread to have its own data
  5. Scheduler Activations
    1. Lightweight process: used to maintain an appropriate number of kernel threads allocated to the application
    2. Appears to be virtual processor on which process can schedule user thread t orun
    3. each LWP. attached to kernel thead

CPU scheduling

Objectives

  1. To introduce CPU scheduling, which is the basis for multiprogrammed operating systems
  2. To describe various CPU-scheduling algorithms
  3. To discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular system
  4. To examine the scheduling algorithms of several operating systems

Basic concepts

CPU Scheduler

  1. nonpreemptive:
    1. switches form to running ro waiting state
    2. switching form running to ready state
    3. switch from waiting to ready
    4. Terminate
  2. preemptive:
    1. Consider access to shared data
    2. Consider preemption while in kernel mode
    3. Consider interrupts occurring during crucial OS activities

Dispatcher

  1. dispatcher module gives control of the CPU to the process selected by the short-term scheduler which involves:
    1. switching context
    2. switching to user mode
    3. jumping to the proper location in the user program to restart that program

Scheduling Criteria

  1. CPU utilization: keep the CPU as busy as possible
  2. Throughput: # of processes that complete their execution per time unit
  3. Turnaround time: amount of time to execute a particular process T t u r n a r o u n d = T c o m p l e t i o n − T a r r i v a l T_{turnaround}=T_{completion}-T_{arrival} Tturnaround​=Tcompletion​−Tarrival​
  4. Waiting time: amount of time a process has been waiting in the ready queue
  5. Response time: amount of time it takes from when a request was submitted until the first response is produced, not output

Scheduling timing

CPU scheduoling decision decisions may take place when a process

  1. switches form to running ro waiting state
  2. switching form running to ready state
  3. switch from waiting to ready
  4. Terminate

Scheduling algorithm

First Come First Serve (FCFS)

  1. first come first serve

Priority

  1. The higher priority, the earlier executed
  2. problem:
    1. starvation: low priority processes may never execute
    2. solution: aging: as time progresses increase the priority
Shortest Job First (SJF)
  1. the shortest job first then the next shortest
  2. The SJF algorithm is a special case of the general priority-scheduling algorithm.
Highest Response Ratio Next (HRRN)
  1. the next job is not that with the shortest estimated runtime, but that with the highest response ratio

R e s p o n s e   R a t i o = 1 + w a i t i n g   t i m e e s t i m a t e d   r u n   t i m e Response\ Ratio = 1 + \frac{waiting\ time}{estimated\ run\ time} Response Ratio=1+estimated run timewaiting time​

Preemptive SJF
  1. Compare SJF, if A is shorter than B, and come later than b, A is preemptively executed
  2. Shortest time to completion first

Round Robin (RR)

  1. runs a jog in a time slice and ten switch it to the next job in the ready queue

Multilevel queue

  1. ready queue is partitioned into separate queues
  2. process permanently in a given queue
  3. each queue has its own scheduling algorithm
  4. scheduling must be done btween queues

Multilevel feedback queue

  1. The multilevel queue (MLQ) has a number of distinct queues, each assigned a different priority level.

  2. basic rules for MLQ

    1. If P r i o r i t y ( A ) > P r i o r i t y ( B ) Priority(A) > Priority(B) Priority(A)>Priority(B), A runs (B doesn’t).
    2. If P r i o r i t y ( A ) = P r i o r i t y ( B ) Priority(A) = Priority(B) Priority(A)=Priority(B), A & B run in RR

  3. For MLFQ: change priority over time:

    1. when a job comes, assume it might be a short job given high priority
    2. if actually a short job, complete it fast
    3. if not a short job, slowly move down the queues, and thus soon prove itself to be a log job

  4. Limitations:

    1. Starvation: If there are “too many” interactive jobs in the system, they will combine to consume all CPU time, and thus long-running jobs will never receive any CPU time (they starve).
    2. Gaming the scheduler: Doing something sneaky to trick the scheduler into giving you more than your fair share of the resource (e.g., by running for 99% of a time slice before relinquishing the CPU).
    3. Changeable program behaviors: A program may change its behavior over time; what was CPU bound may transition to a phase of interactivity. With our current approach, such a job would be out of luck and not be treated like the other interactive jobs in the system.
    4. Solution: Priority boost: after some time period S, move all the jobs in the system to the topmost queue

Lottery Scheduling

  1. Instead of optimizing for turnaround or response time, a scheduler might instead try to guarantee that each job obtain a certain percentage of CPU time.
  2. Every so often, hold a lottery to determine which process should get to run next
  3. Processes that should run more often should be given more chances to win the lottery.

Thread Scheduling

  1. Distinction between user-level and kernel-level threads
  2. Kernel levele threads are schedule by kernel
  3. User level threads are schedule by thread library in LWP

Multiple-Processor Scheduling

  1. Asymmetric Multiprocessing: single queue multiprocessor scheduling
    1. Simply reuse the basic framework for single processor scheduling, by putting all jobs that needs to be scheduled into single queue
  2. Symmetric Multiprocessing: multi-queue multiprocessor scheduling
    1. One queue per CPU. Each queue will likely follow a particular scheduling discipline
    2. Load imbalance: By migrating a job from one CPU to another, true load balance can be achieved

Process synchronization

Objectives

  1. To present the concept of process synchronization
  2. To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data
  3. To present both software and hardware solutions of the
    critical-section problem
  4. To examine several classical process-synchronization problems
  5. To explore several tools that are used to solve process
    synchronization problems

Background

Race Condition

  1. Several processes (threads) access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.
  2. Result indeterminate

The critical section problem

critical section

  1. Problem:

    1. Multiple threads executing a segment of code, which can result in a race condition

  2. Critical section problem is to design protocol to solve this

  3. Each process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section
    4.

solution to critical-section problem

  1. Mutex Exclusion: If process P i P_i Pi​ executing in its critical section, then no other processes can be executing in their critical section
  2. Progress: If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
  3. Bounded waiting: a bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is grant
    1. Assume that each process executes at a non-zero speed
    2. no assumption concerning relative speed of the n processes

Mutex Locks

  1. Precondition(Hardware synchronization primitives):

    1. Lock-related source codes are put around critical sections, thus ensure that any such critical section executes as if it were a single atomic instruction.

  2. A lock is just a variable.

  3. Usage:

    1. Declare a lock variable
    2. The lock variable holds the state of the lock. It is either available (or unlocked or free), means that no thread holds the lock;
    3. Or acquired (or locked or held), means that exactly one thread
      holds the lock.

  4. General Structure:

  5. The semantic of the lock() routines

    1. Calling the routine lock() tries to acquire the lock.
    2. If no other thread holds the lock (i.e., it is free), the thread will acquire the lock and enter the critical section; this thread is sometimes said to be the owner of the lock.
    3. If another thread then calls lock() on that same lock variable, it will not return since the lock is held by its owner.
    4. Other threads are prevented from entering the critical section while the first thread that holds the lock is in there.

  6. The semantic of the unlock() routines

    1. Once the owner of the lock calls unlock(), the lock is now available (free) again.
    2. no other threads are waiting for the lock, the state of the lock is simply changed to free; otherwise, one of the waiting threads will notice this change of the lock’s state, acquire the lock, and enter the critical section.

Pthread Locks

Controlling Interrupt (failed)

  1. disavantage:
    1. May be abused by malicious program which could cause endless loop by calling lock()
    2. Does not work on multiprocessors
    3. lost interrupt: the OS may lost IO interrupt
    4. inefficient: Codes that mask or unmask interrupts are executed slowly

Using lock flag (failed)

reason

Peterson’s solution

  1. precondition
    1. Two process
    2. load and store machine-language instructions are atomic
  2. use a flag array to show that which process is ready to enter the critical section

Bakery Algorithm

  1. compared to peterson’s solution, bakery algorithm supports mutiprocess synchronization
  2. solution
    1. before entering its critical section, process receives a number.
    2. The process which holds the smallest number enters the critical section others wait in queue
    3. if process P i P_i Pi​ and process P j P_j Pj​ receive the same number, and i < j i<j i<j, then P i P_i Pi​ served first for i < j i<j i<j
  3. implementation:

    1. shared data:

    2. lock:

test and set

  1. hardware support:

  2. lock implementation:

  3. evaluation：

  4. example:

compare and swap

  1. hardware support:

  2. implementation:

  3. Evaluation:

  4. Benefit:

    1. can be used to implement lock-free synchronization
    2. No dead lock
Using CAS to implement lock-free synchronization

Lock-Link and Store Conditional

Fetch and Add

  1. solution:

    1. Atomically increments a value while returning the old value at a particular address

  2. implementation:

Span waiting

  1. disadvantage of spin waiting:
    1. inefficient: if there are N N N threads contending for lock; then N − 1 N-1 N−1 time slices may be wasted
  2. advantage:
    1. No context switch is required
    2. On multi processor systems, one thread can spin on one processor while another thread performs its critical section on another processor.
  3. Two-phase locks in Linux
    1. In the rst phase, the lock spins for a while, hoping that it can acquire the lock.
    2. If the lock is not acquired during the rst spin phase, a second phase is entered, where the caller is put to sleep, and only woken up when the lock becomes free later.
  4. priority inversion: A higher-priority thread waiting for a lock held by lower-priority thread.
  5. priority inheritance —a higher-priority thread waiting for a lower-priority thread can temporarily boost the lower thread’s priority, thus enabling it to run and overcoming the inversion.

Yield:

  1. yeild()is simply a system call that moves the caller from the running state to the ready state

  3. evaluation:

    1. Better than spin, but still inefficient
    2. Think about N N N threads contending for a lock; N − 1 N-1 N−1 threads may execute the run-and-yield pattern.

Using queue

  1. problem: the scheduler determines which thread runs next
  2. solution: A queue can be used to keep track of which threads are waiting to acquire the lock
  3. example of Solaris: using park() puts a calling thread to sleep. unpark(threadID) wakes a particular thread as designated by threadID
  4. implementation:

setpark()

  1. Race condition before the call to park(): With just a wrong timing switch, the subsequent park by the rst thread would then sleep forever (potentially).
  2. A third system call: setpark(): A thread indicates it is about to park.
  3. If it then happens to be interrupted and another thread calls unpark() before park() is actually called, the subsequent park() returns immediately instead of sleeping.

Lock Data Structures

Concurrent Counter

  1. Non-concurrent counter:

  2. Concurrent Counter：

Concurrent Linked List

Scaling Linked Lists

  1. Hand-over-hand locking (a.k.a. lock coupling)
  2. Instead of having a single lock for the entire list, you instead add a lock per node of the list.
  3. When traversing the list, the code rst grabs the next node’s lock and then releases the current node’s lock
  4. High degree of concurrency in list operations. In practice, it is hard to make such a structure faster than the simple single lock approach. (Surprise? Guess why.)
  5. A hybrid would be worth investigating.

Concurrent Queue

Concurrent Hash Table

Condition Variables

  1. Problem：

  2. Using a shared variable:

  3. using condition variable which calls wait()and signal() system call :

semaphore

  1. benefit:
    1. Functionality
      1. A single primitive for all things related to synchronization
      2. Both locks and condition variables
    2. Correctness and Convenience
      1. Avoid errors—can signal() first then wait().
      2. Clean and organized—making it easy to demonstrate their correctness.
      3. Efficient.

Basic Synchronization Patterns

Signaling

Rendezvous

Mutex

Multiplex

Barrier

Pairing

The Producer-Consumer Problem

The Dining Philosophers

The Readers-Writers Problem

  1. problem:

    1. writes change the state of data
    2. reads do not change the data
    3. first reader writer problem: no reader should be kept waiting unless a writer has already obtained permission to use the shared object
    4. second reader writer problem: once a writer is ready that writer perform its write as soon as possible

  2. The first readers-writers problem solution:

  3. The No-starve readers writers problem:

  4. second reader-writer problem:

monitors

  1. problem: As object-oriented programming was gaining ground, people started to think about ways to merge synchronization into a more structured programming environment.
  2. Solution: With a monitor class —the monitor guarantees that only one thread can be active within the monitor at a time.

Deadlock

Objectives

  1. To develop a description of deadlocks, which prevent sets of concurrent processes from completing their tasks
  2. To present a number of different methods for preventing or avoiding deadlocks in a computer system

system model

  1. System consists of resources: R 1 , R 2 , R 3 … R_1, R_2,R_3\dots R1​,R2​,R3​…
  2. Each resources type R i R_i Ri​ has W i W_i Wi​ instances
  3. Each process utilizes a resource as the following order: request, use, release

Deadlock Characterization

Four necessary condition

  1. Mutex exclusion: only one process at a time can use a resource
  2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes
  3. no preemption: a resource can be release only voluntarily by the processes holding it, after that process has completed its task
  4. Circular wait: there exists a set P 0 , P 1 … P n − 1 {P_0,P_1\dots P_{n-1}} P0​,P1​…Pn−1​ of waiting processes such that P 0 P_0 P0​ is waiting for a resource that is held by P 1 … P n − 1 {P_1\dots P_{n-1}} P1​…Pn−1​ which is waiting for a resource held by P n P_n Pn​, and P n P_n Pn​ is waiting for a resource held by P 0 P_0 P0​

Resource-allocation graph

  1. use vertices to represent a process and an edge to represent an request
  2. use vertices to represent a resource and an edge to represent an assignment
  3. use circle to determine whether there is a deadlcok
    1. if no circle: no deadlock
    2. contains circle(s): and only one instance per resource: a deadlock
    3. contains circle(s): not only one instance per resource: possibility deadlock
      4.

Deadlock Prevention

Method: denying the four necessary conditions

circular wait

  1. All process request resources in an increasing order of enumeration
void doSomething(mutex_t* m1. mutex_t* m2)
{
	if(m1 >m2)
    {
        pthread_mutex_lock(m1);
        pthread_mutex_lock(m2);
    }
    else
    {
        pthread_mutex_lock(m2);
        pthread_mutex_lock(m1);
    }
}

hold and wait

  1. require process to request an be allocated all its resources before it begin its execution
  2. low resource utilization
  3. possible cause starvation

no preemption

lock(L1);
if(L2 is preemptive)
{
    unlock(L1);
}

Mutual exclusion

  1. Not required for sharable resources, must hold for non-sharable resource
  2. Use CAS replace mutex lock

Deadlock Avoidance

safe state

  1. When a process requests an available resource, system must decide if immediate allocation leaves the system in safe state
  2. a system is in safe state if there exists a sequence < P 1 , P 2 … P n > <P_1,P_2\dots P_n> <P1​,P2​…Pn​> of all the processes in the system such that for each P i P_i Pi​, the resources that P i P_i Pi​ cam still request can be satisfied by currently available resource + resources held by all the P j P_j Pj​, with j<i
    3.

Avoidance Alg.

Resource-allocation graph alg.
  1. claim edge converts to a request edge when a process request a resource
  2. request edge converted to an assignment edge when the resource is allocated to the process
  3. when a resource is released by a process assignment edge reconverts to a claim edge
  4. resources must be claimed a priori in the system
  5. the request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph
The Banker’s Algorithm

  1. The Banker’s Algorithm

    1. each process must a priori claim maximum use

    2. when a process requests a resource it may have to wait

    3. when a process gets all its resources it must return them in finite amount of time

  2. Safety Algorithm

    1. find a safe sequence
    2. use greedy alg. Satisfy the process which will release resource first

  3. Resource-request alg.

    1. if safe, then request are granted,

Dead Detection

Wait-for graph alg.

  1. Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock

Deadlock recovery

  1. Process termination

    1. Abort all deadlocked process
    2. or abort one process at a time until the deadlock cycle is eliminated

  2. Resource Preemption

    1. Select a victime
    2. Rollback: return to some safe state, restart process for that state
    3. Starvation: same process may always be picked as victim, include number of rollback in cost factor

Main memory

Objectives

  1. To provide a detailed description of various ways of organizing memory hardware
  2. To discuss various memory-management techniques, including paging and segmentation
  3. To provide a detailed description of the Intel Pentium, which supports both pure segmentation and segmentation with paging

Background

Program loading and linking

  1. program must be brought into memory and placed within a process for it to be run
  2. Main memory and register are only storage CPU can access directly
  3. Memory only sees address + read(data) request
  4. Register access in one CPU clock
  5. Main memory can take many cycles casing a stall
  6. Cache sits between main memory and CPU register

address binding

  1. Source code often use symbolic
  2. Compiled code bind to relocatable address
  3. Linker or loader will bind relocatable addresses to absolute addresses
  4. each binding maps one address space to another

Dynamic Loading and Linking

  1. Dynamic loading: a routine is not loaded until it is called. All routines are kept on disk in a relocatable load format
  2. Static linking: system libraries and program code combine by the loader into the binary program image
  3. Dynamic linking: linking postponed until execution time

Address Space

  1. logical address

    1. generated by CPU
    2. also referred to as virtual address

  2. physical address

    1. address seen by the memory unit

  3. logical and physical addresses are identical in compile-time and load time address-binding schemes; logical and physical addresses differ in execution time address binding scheme

Address Translation

  1. base and limit

    1. p h y s i c a l = v i r t u a l + b a s e physical = virtual + base physical=virtual+base
    2. p h y s i c a l ∈ [ b a s e , l i m i t ] physical \in [base, limit] physical∈[base,limit]

  3. MMU:

    1. The base and limit registers are hardware structures kept on the chip
    2. the part of the processor that helps with address translation is the MMU

  4. Internal fragmentation

    1. The space between the stack and heap of a process is wasted

Segmentation

  1. segmentation: generalized base/limit

  1. problem:
    1. external fragmentation: total memory space exists to satisfy a request, but it is not contiguous

free space management

  1. best fit
  2. worst fit
  3. first fit
  4. next fit

paging

  1. paging

    1. to chop up space into fixed-size pieces. i.e. pages
    2. the physical memory can be viewed as an array of fixed-sized slots called page frames; each of these frames can contain a single virtual memory page

  2. why paging

    1. Flexibility: with a fully-developed paging approach, the system will be able to support the abstraction of an address space effectively, regardless of how a process uses the address space
    2. Simplicity: The free-space management can be easy

  3. Address translation:

    1. page table: stores address translations for each of the virtual pages of the address space, thus letting us know where in physical memory each page reside
    2. virtual address has two components: Virtual page number and the offset within the page
    3. the virtual page number is mapped to the Physical frame number

  4. Where are page tables stored

    1. In physical memory
    2. Page table base register points to the page table
    3. page table length register indicates size of the page table

Translation Lookaside Buffer

  1. Translation Lookaside buffer

    1. part of the chip’s memory-management unit(MMU)

    2. simply a hardware cache of popular virtual-to-physical address translation

  1. Issues with a Context Switch

    1. TLB contains virtual-to-physical translations that are only valid for the currently running process
    2. When Context Switch happening, emptying it before running the next process
    3. or use an address space identifier
      1. but cause other issues
      2. Serval entries for different processes that point to the same physical pages
      3. Solution: shared pages: An advantage of paging is the possibility of sharing common code

  2. Effective Access Time

    1. ϵ \epsilon ϵ: Time Unit can be less than 10% of memory access time
    2. α \alpha α: Hit ratio
    3. Effective Access Time = ( 1 + ϵ ) α + 2 ( 1 + ϵ ) ( 1 − α ) \text{Effective Access Time}=(1+\epsilon)\alpha+2(1+\epsilon)(1-\alpha) Effective Access Time=(1+ϵ)α+2(1+ϵ)(1−α)

  3. Page size issue

    1. fragmentation

    2. table size/ page fault

    3. I/O over head

    4. locality

Structure page table

Paging and Segments

  1. one page table per logical segment:

  2. A pair of base and bound registers, telling the address and size of the segment, and those of the page table

hierarchical page tables

basic idea
  1. chop up the page table into page-size units
  2. If an entire page of page-table entries is invalid, don’t allocate that page of the page table at all
  3. a page directory is used to track whether a page of the page table is valid. It tells where a page table is, or that the entire page of the page of the page table contains no valid pages
page directory table

Structure of the Page Table

  1. Hashed Page tables:

    1. Common in address spaces > 32 bits
    2. The virtual page number is hashed into a page table:
    3. This page table contains a chain of elements hashing to the same location

  2. Cluster Page Tables:

    1. Similar to hashed but each entry refers to serval pages
    2. Especially useful for sparse address spaces

  3. Inverted Page Tables:

    1. Rather than each process having a page table and keeping track of all possible logical pages, track all physical pages

Swapping

  1. problem
    1. page tables may still be too big
    2. some systems place such page tables in kernel virtual memory, thereby allowing the system to swap some of the these page tables to disk

Example Architectures

  1. Intel IA-32 Page Address Extensions:

Virtual Memory

Objectives

  1. To describe the benefits of a virtual memory system
  2. To explain the concepts of demand paging, page-replacement algorithms, and allocation of page frames
  3. To discuss the principle of the working-set model
  4. To examine the relationship between shared memory and memory-mapped files
  5. To explore how kernel memory is managed

Background

  1. Code needs to be in memory to execute, but entire program rarely used

  2. Virtual Memory: separation of user logical memory from physical memory

    1. Only part of the program needs to be in memory for execution
    2. Logical address space can therefore be much larger than physical address space
    3. Allows address spaces to be shared by several processes
    4. Allows for more efficient process creation
    5. More programs running concurrently
    6. Less I/O needed to load or swap processes
    7. Can be Implemented via
      1. Demand paging
      2. Demand segmentation

Demand paging

Features

  1. bring entire process into memory in load time
  2. bing a page into memory when it is needed
    1. less I/O needed
    2. less memory needed
    3. faster response
    4. more users
  3. Similar to paging system with swapping
  4. page is needed
  5. lazy swap: never swap a page into memory unless it’s needed

basic concepts

  1. With swapping, paper guesses which pages will be used before swapped out again
  2. papers only bring in those pages in memory
  3. if pages needed are alreaded memory resident:
    • nodifferent from non demanding-pagin
  4. if page needed and not memory resident

Valid-invalid bit

  1. if it’s in memory
  2. initially set to invalid on all entries
  3. in MMU translation, if valid-invalid bit in page table entry, then i → \rightarrow → page fault

Page fault

if there is a reference to a page, first reference to that page will trap to operating system

  1. operating system looks at an internal table to deside:

    • Invalid reference:abort
    • just not in memory

  2. find free frame

  3. swap page into fram via scheduled disk operation

  4. reset table to indicate page now in memory

  5. restart the instruction that caused the page fault
    6.

  6. effective access time

p  is teh page fault rage and 0 ≤ p ≤ 1 E A T (effect access time) = ( 1 − p ) T m e m o r y   a c c e s s + p × ( T p a g e   f a u l t   o v e r h e a d + T s w a p   p a g e   o u t + T s w a p   p a g e   i n ) p\text{ is teh page fault rage and}0\le p \leq 1\\ EAT\text{(effect access time)} = (1-p)T_{memory\ access}+p\times (T_{page\ fault\ overhead} + T_{swap\ page\ out}+T_{swap\ page\ in}) p is teh page fault rage and0≤p≤1EAT(effect access time)=(1−p)Tmemory access​+p×(Tpage fault overhead​+Tswap page out​+Tswap page in​)

aspect of demand paging

  1. Extreme cases

    1. start process without page in memory
    2. OS sets instruction pointer to the first pointer of the process, non-memory-resident → \rightarrow → page fault
    3. and for every other process pages on first access
    4. pure demand paging

  2. actually

    1. a given instruction could access multiple pages ⇒ \Rightarrow ⇒ multiple page fault
    2. consider fetch and decode of instruction which adds 2 numbers from memoru and stores result back to memory
    3. pain decreased because of locality of reference

  3. Hardware support

    1. page table with valid-invalid bit

    2. secondary memory(swap device with swap space)

    3. instruction restart

Performance of demand page

stage in demand paging
  1. Trap to the operating system
  2. save the user rigister adn process state
  3. determine that the interrupt was a page fault
  4. Check that the page reference ws lwgal and determine the location of the page on the disk
  5. issue a disk read form the disk to a free frame
    1. wait in a queue for this device until the read request is serviced
    2. wait for the device seek and/or latency tiem
    3. begin the transfer of the page to a free frame
  6. while waiting, allocate the CPU to some other users
  7. Receive an interrupt from the disk when I/O request finished an interrupt occurred
  8. save the resigeters and precess state for the other user
  9. Determine that the interrupt was form the disk
  10. correct teh page table and other tables to show page is now in memory
  11. wait for the CPU to ve allocated to this process again
  12. resotre the user registers, process state, adn new page table, adn then resume the interrupted instruction
Besides the context switch
  1. servide the interrupt
  2. read the page
  3. restart the process
demand paging optimization
  1. swap I/O is faster than file system I/O
  2. Dopy entire process image to swap spaceat rpocess load tiem
  3. demand page in from program binary on disk, but discard rather than paging out when freeing frame
  4. Mobile system: typically don’t support swap instead reclaim read-only pages

Inverted page table

  1. Inverted page table no longer contains complete information about the logical address space of a process.
  2. That information is required if a referenced page is not currently in memory.
  3. Demand paging requires this information to process page faults.
  4. For the information to be available, an external page table (one per process) must be kept (can be on the backing store).
  5. A page fault may now cause the virtual memory manager to generate another page fault as it pages in the external page table it needs to locate the virtual page on the backing store.

Copy on write

  1. Allows both parents and child processes to initially share the same pages in memory
  2. COW allows more effecient process creation as only modified pages coped
  3. In general, free pages are allocated from a pool of zero-fill-on-demand pages
  4. vfork() Use COW rather thanfork() doesn’t
  5. Diagram

page replacement

  1. what happens when there is no free frame

    1. Used up by the process pages
    2. also in demand from the kernel, I/O buffers, etc
    3. Page replacement: some page in memory, but not really use
    4. prevent over-allocation of memory by modifying page-fault service routine to include page replacement
    5. Use modify(diet)bit to reduce overhead of page transfer
    6. page replacement completes separation between logical memory and physical memory

  2. Basic page replacement

    1. find the location of the desired page on disk

    2. find a free frame

      • if there is a free frame, use it

      • if there is no free frame, use a page replacement algorithm to select a victim frame

      • write victime frame to disk if dirty

    3. bring the desired page into the free frame, update the page and frame tables

    4. continues the process by restarting the instruction that caused the trap

page and frame replacement algorithm

  1. frame allocation algorithm determines
    1. how many frames to give each processes
    2. which frames to be replaced
  2. page replacement algorithm
    1. Want lowest page-fault rate on both first access and re-access
  3. Evaluate algoritm
    1. running on a particular strign of memory references and computing reh numver of page fault
    2. string is just page numbers, not full address
    3. repeated access to the same page doesn’t cause a page fault
    4. result depend on number of frames avaiable

optimal algorithm

  1. basic idea

    1. replace page that will not be used for longest period of time

First in first out

use a FIFO queue

Least recently used(LRU) algorithm

  1. Basic idea

    1. use the history knowledge

    2. replace page that has not been used in the most ammount of time

  2. Implementation

    1. every page entry has a counter

    2. when a page needs to change, look into the counter

    3. only back store the dirt one

    4. possible keep some free frame

  3. Advantage and disadvantage

    1. It needs special hardware

LRU approximation algorithm

  1. basic idea

    1. generally FIFO, olus hardware-provide reference bit

    2. if reference bit = 1 then replace it, else set the reference bit = 0, and check the next frame

    3. basic idea of reference bit

      1. with each page associate a reference bit

      2. when page is referenced, set the bit to 1

      3. replace any with reference bit = 1

  2. Use additional reference bit: basic idea of additional reference bit

    1. use 8-bit for each page instead 1 bit

    2. replace the lowest number

Most frequently used(MFU)

compare to LRU

Page buffering algorithm

  1. Keep a pool of free frame
    1. Then frame available when needed, not found at fault time
    2. read page into free frame and select victim to evict and add to free pool

Random algorithm

  1. simply pick a random page to replace

  2. workload example

    1. no locality workload

    2. 20-80 locality workload:80% reference caused by 20%

    3. loop workload

allocation of frames

  1. equal allocation
    1. If there are 100 frames, and 5 processes, and 20 frames one processes
  2. proportional allocation
    1. Allocation according to the size of process;

m = 64 , s 1 = 10 , s 2 = 20 , m 1 = 10 30 × 64 , m 2 = 20 30 × 64 m=64, s_1=10,s_2=20,m_1=\frac{10}{30}\times64, m_2=\frac{20}{30}\times64 m=64,s1​=10,s2​=20,m1​=3010​×64,m2​=3020​×64

  1. priority allocation
    1. use priority instead of promotion

global/local replacement

  1. global replacement: process selects a replacement frame from the set of all frames; one process can take a frame from another
  2. local replacement: each process selects from only its own set of allocated frames

Thrashing

  1. trashing: a process is busy swapping page in and out

  3. Work-set model

    1. If total working set size > working set window, then thrashing

    2. Policy: swap out or suspend one of the process

  4. Solution: dynamic rearrange the Working Set Size

    1. page fault frequency is more direct

    2. if rate too low, then loose frame. not good for multiprogramming

    3. if too high then gain frame. trashing

Memory Mapped Files

  1. Memory-mapped le I/O allows le I/O to be treated as routine memory access by mapping a disk block to a page in memory
  2. Can be access by driving file IO through memory rather than read() and write() system call

Allocating Kernel Memory

  1. Treated differently from user memory
  2. Often allocated from a free-memory pool
  3. Some kernel memory needs to be contiguous like for device IO

Buddy Allocator

  1. Allocates memory from fixed-size segment consisting of physically-contiguous pages
  2. Memory allocated using power-of-2 allocator
    1. Satisfies requests in units sized as power of 2
    2. Request rounded up to next highest power of 2
    3. When smaller allocation needed than is available, current chunk split into two buddies of next-lower power of 2

Slab Allocator

  1. Slab is one or more physically contiguous pages
  2. Cache consists of one or more slabs
  3. Single cache for each unique kernel data structure
  4. When cache created, filled with objects marked as free
  5. When structures stored, objects marked as used
  6. If slab is full of used objects, next object allocated from empty slab
    1. If no empty slabs, new slab allocated
  7. Benefits include no fragmentation, fast memory request satisfaction

Mass Storage System

Objectives

  1. To describe the physical structure of secondary storage devices and its effects on the uses of the devices
  2. To explain the performance characteristics of mass-storage devices
  3. To evaluate disk scheduling algorithms
  4. To discuss operating-system services provided for mass storage, including RAID

Disk structure

  1. Disk interface

    1. atomic unit is 512B

    2. Most program read 4K or more once

  2. disk io

    1. T I / O = T s e e k + T r o t a t i o n + T t r a n s f e r T_{I/O}=T_{seek}+T_{rotation}+T_{transfer} TI/O​=Tseek​+Trotation​+Ttransfer​

    2. R I O = S i z e T I O R_{IO}=\frac{Size}{T_{IO}} RIO​=TIO​Size​

  3. Seek time: time of arm move to the correct track

    1. T ˉ s e e k ∼ 1 3 T ˉ f u l l s e e k \bar{T}_{seek}\sim \frac{1}{3}\bar{T}_{full seek} Tˉseek​∼31​Tˉfullseek​
    2. average seek time is roughly one third of the full seek time [prove](single.dvi (wisc.edu))

Track skew

  1. to ensure the sequential read

disk scheduling

first come first serve

  1. first come first serve

shorest seek time first

  1. shortest seek time first

SCAN algorithm

  1. the head starts at one end of the disk, and move towards the other end

C-SCAN

  1. the head move from one end of the disk to the other serving requests as it goes, when it reach the other end, it immediately return to the begin of the disk without serving any requests on the return trip

LOOK

  1. it’s like SCAN, but it reverse when encounter the last request in the direction

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-egwyC1WN-1659962757789)(figures/Operating System/image-20220807194756571.png)]

C-LOOK

  1. it’s like SCAN, but it reverse when encounter the last request in the direction, when return to the end, it doesn’t serving any request

Shortest Positioning Time First (SPTF)

  1. SCANs (or LOOKs) do not represent the best scheduling technology (they ignore rotation).

Selecting a Disk-scheduling algorithm

  1. SSTF (or SPTF) is common and has a natural appeal
  2. SCAN and C-SCAN perform better for systems that place a heavy load on the disk
    1. Less starvation

Raid Structure

  1. Redundant Arrays of Inexpensive Disks: A technique to use multiple disks in concert to build a faster, bigger, and more reliable disk system.
  2. Benefits:
    1. Performance: Using multiple disks in parallel can greatly speed up I/O times.
    2. Capacity: Large data sets demand large disks
    3. Reliability: With some form of redundancy, RAIDs can tolerate the loss of a disk and keep operating as if nothing were wrong

File System

Objectives

  1. To explain the function of file systems.
  2. To describe the interfaces to le systems.
  3. To discuss le-system design tradeoffs, including access methods, le sharing, le locking, and directory structures.
  4. To explore le-system protection

File and Directories

  1. Virtualize the persistent storage
  2. A file is simply a linear array of bytes, each of which you can read or write
  3. A directory contains a list of entries, each of which is a pair, referring to either a file or other directory

File-system Interface

File Interface

  1. Create File: open() system call:

  2. Access File: read(), write() system call:

  3. Reading/Writing Not Sequentially: lseek() system call:

  4. Writing immediately: fsync() system call:

  5. renaming files: rename() system call:

  6. Get information about files:

    with stat() or fstat() system call

  7. permission bits: change the file mode with chmod() system call

  8. removing files: unlink() system call

Directory Interface

  1. Making directories: mkdir() system call
  2. Reading Directories: ls() system call
  3. deleting directories: rmdir() system call

Links

  1. hard link: link() system call
  2. recall that removing a file is performed via unlink():
    1. on creating file: create a structure inode that will track all relevant information about the file
    2. when unlinking a file: the file system checks a reference count within the inode number; only when the reference count reaches zero, does the file system also free the inode and related data blocks
  3. Symbolic links
    1. Limits to hard link:
      1. can’t create one to a directory
      2. can’t cross file system

File System Interface

  1. make file system: mkfs() command
  2. mounted them to make their contents accessible: mount() command

File-system implementation

Objectives

  1. To describe the details of implementing local le systems and directory structures.
  2. To describe the implementation of remote le systems
  3. To discuss block allocation and free-block algorithms and trade-offs

Typical File System

Overall Organization

  1. divide the disk into blocks:

  2. To track information about each file, the inodes are stored in inode table:

  3. To track whether inodes or data blocks are free or allocated, an inode bitmap and a data bitmap are required:

  4. Inode

    1. An Inode in UNIX FS is a File Control Block
    2. The name inode is short for index node
    3. Each inode is implicitly referred to by a number, called the inumber
    4. Use direct pointers to refer to the data block
    5. when the file is really big: use indirect pointers Usually 12 direct pointers and 1 indirect pointer

  5. Multi-level Index

    1. double indirect pointer
    2. triple indirect pointer
    3. using extents instead of pointers (ext4)
      1. An extent is simple a disk pointer plus a length to specify the on-disk location of a file
      2. Extent-based file system often allows for more than one extent

Typical File System

  1. Very Simple File System: A simplified version of a typical UNIX file system

  2. FAT (File-Allocation Table):

  3. NTFS (new technology le system):

Fast File System

  1. Design the le system structures and allocation policies to be "disk aware” and thus improve performance.

  2. It keeps the same interface to the FS, but changes the internal implementation

  3. Organizing structure: the cylinder group:

    1. By placing two les within the same group, FFS can ensure that accessing one after the other will not result in long seeks across the disk

    3. FFS keeps a copy of the super block (S) in each group for reliability reasons.

    4. A per-group inode bitmap and data bitmap to track whether the inodes and data blocks of the group are allocated.

    5. The inode and data block regions are just like those in the previous very-simple le system.
      6.

FSCK and Journaling

  1. file system checker: check if the inode is valid
  2. Journaling(write ahead logging):
    1. Journal write: Write the contents of the transaction (including TxB, metadata, and data) to the log; wait for these writes to complete.
    2. Journal metadata write: Write the begin block and metadata to the log; wait for writes to complete.
    3. Journal commit: Write the transaction commit block (containing TxE) to the log; wait for write to complete; transaction is said to be committed.
    4. Checkpoint: Write the pending metadata and data updates to their final locations in the le system.
    5. Free: Some time later, mark the transaction free in the journal by updating the journal superblock.
  3. Copy on Write
    1. Never overwrite files or directories in place; rather, it places new updates to previously unused location on disk
    2. Used on log-structured file system

Log Structure File System

  1. problems:

    1. System memories are growing
    2. There is a large gap between random IO performance and sequential IO performance
    3. Existing file systems perform poorly on many common workloads
    4. File system are not RAID-aware

  2. LSF:

    1. When writing to disk, LFS first buffers all update in an in-memory segment
    2. when the segment is full, it is written to disk in one long, sequential transfer to an unused part of the disk
    3. LFS never overwrites existing data, but rather always writes segments to free locations
    4. because segments are large, the disk is used efficiently, and performance of the file system approaches its zenith

  3. Writing to disk sequentially, when a user writes a data block, it’s not only data that gets written to disk; there is also other metadata that needs to be updated:

  4. Find Inodes:

    1. LFS uses a level of indirection between inode numbers and the nodes through a data structure called the inode map
    2. The file system must have some fixed and known location to begin a file lookup such location is the checkpoint region CR

  5. find impas

    1. the file system must have some fixed and known location to begin a file lookup. Such location is the checkpoint region (CR)

  6. Reading a file

    1. read the checkpoint region, which contains pointers to the entire inode map
    2. read the inode map, and caches it in memory
    3. looks up the inode number to inode-disk-address mapping in the imap
    4. reads in the most recent version of the inode

  7. Considering directories

    1. When creating a file on disk, LFS must both write a new inode some data, as well as the directory data and its inode that refer the this file
    2. Recursive update problem: Even though the location of an inode may change, the change is never reflected in the directory itself

  8. Garbage Collection

    1. Using compaction, to get rid of free holes

  9. Determining Block Liveness

    1. LFS includes, for each data block D, its inode number and its offset. This information is recorded in a structure at the head of the segment known as the segment summary block

Network File System

Basic Distributed File System

  1. on the client side, there are client applications which access files and directories through the client side file system
  2. A client application issues system call to the client side file system in order to access files which are stored on the server
  3. The client side file system may send a message to the server side file system to perform the IO operation
  4. A subsequent read() of the same block on the client may be cached in client memory or on the client’s disk even
  5. A challenge deals with fast server crash recovery

I/O System

polling

未准备好 准备好 未准备好 未准备好 为完成 给IO模块发出读命令 读IO模块的状态 检查状态 从IO模块中读取字 往存储器中写入字 完成 完成 错误条件

Interrupt-driven

未准备好 准备好 未准备好 未完成 给IO模块发出读命令 读IO模块的状态 检查状态 从IO模块中读取字 往存储器中写入字 完成 完成 错误条件 CPU做其他事 终端

direct memory access

给IO模块发出命令 读取DMA状态 下一条指令 CPU->DMA, CPU做其他事 DMA->CPU, 中断

本文标签： 操作系统笔记

版权声明：本文标题：【操作系统】操作系统笔记 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1729339924a1197410.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。