Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
74 Cards in this Set
- Front
- Back
|
long term
|
decides when to admit a process to the ready queue
degree multiprogram whether to add and which one limit number of active, activate due to idle time scheduling algorithm batch sent to long intereactive system allow user until system is full |
|
|
medium
|
decides when to swap processes in and out of memory
blocked processes swapped out to make more room activate if underutilized |
|
|
short
|
decides which ready process to execute next
dispatcher interrupts, calls, traps, signals meet objectives criteria set for scheduling algorithm |
|
|
short term sched crit
|
user oriented-what a user sees
system-system concerns, not for single user performance other |
|
|
user oriented, performance
|
turnaround time, time bw submission and completion wait time plus exec
response time request and response deadline, maximize deadline |
|
|
user, other
|
predictability, exec not affected by system load
|
|
|
system, performance
|
throughput, num proc completed per time
processor util, percent time proc is busy |
|
|
system, other
|
fairness, proc treat same
enforce prior, favor high prior balance resourse, keep busy |
|
|
priorities
|
diff priorities
basis of sched decisions high before low range of prior single q vs diff ready q for proc of diff prior pure prior, as long as there are high before going to other q low prior, no proc in high prior q starve low prior age low prior to reach high |
|
|
sched policy
|
select funct, which proc runs next
decision, when run the select funct |
|
|
selection funct
|
based on prior, resouse require, time spent wait, time spent exec, total service time require = user or estimate
|
|
|
decision mode
|
non premptive, runs until termination or block
preemptive, moves between run and ready q, timeouts |
|
|
fcfs
|
max(time spent so far), non pre, penal short and io bound proc
|
|
|
rr
|
constant, pre at time, fair
|
|
|
spn
|
min(total service time), non pre, penal long
|
|
|
srt
|
min(s-exec) pre at arrive, penal long
|
|
|
hrrn
|
max(w+s/s), non pre, balanced
|
|
|
feedback
|
pre at time, favor short and io proc
|
|
|
multi proc sched
|
loose, autonomous systems, own mem and io channels
tight couple, share mem and control by os func spec proc, master slave, io proc special |
|
|
granularity
|
freq of synch
independent parallel, unrelated proc, no synch, multiprogram uni or multi no sched impact coarse, gross level of synch, concurrent proc, distributed procs, same medium, parallel application, threads, one thread may effect entire system fine, parallel instruct steam. idk |
|
|
multi sched issues
|
assign proc to procrs
multiprog on indiv procrs dispath of proc |
|
|
assign proc to procrs
|
if procrs alike, assign procs to procrs on demand
static, assign to procr until fin. less overhead, group or gang sched, doesnt distibute variable, single to many, cost of sched is independent of procr master/slave, cpu dedicate to os, sched all jobs peer, self sched, more fault tolernat than slave |
|
|
thread sched
|
greatly affect performance if threads can run simul on sep procrs
load sharing, not assigned to particular, self sched from global q, even distibute, no central scheduler (each cpu self scheds), global q affects performance, preempt threads not run on same cpu (worse cache), not all threads in exec, if coordination not efficient gang sched, sched threads of a single process to run at same time, thread switch if waiting on thread not running, greatly affects performance if this happens a lot, great for medium app w high synch...approach: division vs div weight?????????????????? dedicate proc assign, group of procrs for the app, avoids proc swithc, anal to allocate frames of memory to process, allocate too few procrs leads to proc switch (page fault), procrs allocated but unused is like fragmentation dynamic, coop OS and app to decide how many threads to run, OS says this many, proc says these threads run, experimental |
|
|
real time sched
|
assure results and time produced
hard real time task: one must meet deadline or else system fails, aperiodic has a deadline or time constraint, periodic time units apartt soft real time task, should meet deadline |
|
|
characterists
|
determinism time to acknowldege interrupt...extent at which os performs operations at fixed time intervals...speed it can response and capacity to respond. based on how long the OS dealys between arrival and service
responsiveness service interrupt + deter = response time...how long it takes to service one ack user control, specify hard and soft tasks. specify prior. specify paging. specify swapping (what always resides mem). disk transfer algo. reliabilty fail soft peration ability to fail to preserve as much capability and data as possible. fix problem or minimize effect while continue to run. stability...cant meet requests, meet crit even if it must delay less crit fail maintains partial funct vs fail safe avoids unsafe behavior |
|
|
features or real OS
|
fast context switch, small size, response to external interrupts quickly, multitasking with semaphores signal and events, files accumulate data at a fast rate, preemt sched base on prior, minimization of intervals during which interrupts are disabled, primitives to delay taks for fized amount of time, alarms and timeouts.
|
|
|
real time scheduling
|
Static table-driven: schedule is computed in advance from set of jobs and their requirements. Predictable, but not flexible. New job requires schedule to be redone.
Static priority-driven: priorities are assigned to jobs in advance from set of jobs and their requirements, but no explicit schedule is produced. Relies on normal priority-driven preemptive scheduler. Dynamic planning-based: allows accepting new tasks at run-time. Does feasibility analysis of existing jobs plus new job to see if new job can be fit in. Dynamic best effort: assigns priorities based on task characteristics. System tries to meet all deadlines, and aborts jobs that do not. Easy to implement, but until a deadline arrives, it is unknown whether it will be met. |
|
|
sched facotrs
|
Ready time: time at which task is ready to execute.
Starting deadline: time by which task must begin. Completion deadline: time by which task must end. Processing time: time required to execute task. Resource requirements: resources required by the task. Priority: relative importance of the task. Subtask structure: task may be decomposed into hard and soft subtasks. |
|
|
deadline scheduling
|
Some real-time systems start a task as soon as possible.
However, real-time applications are not concerned with speed but with completing tasks on time. It has been shown for a given preemption strategy that scheduling tasks with the earliest deadline minimizes the fraction of tasks that miss their deadlines. |
|
|
rate monotonic scheduling
|
Can be used for periodic tasks.
Assigns priorities to tasks on the basis of their periods. Highest-priority task is the one with the shortest period. If the priority of tasks are plotted as a function of their rate, this scheme yields a monotonically increasing function (hence the name). When more than one task is available, the one with the shortest period is executed first. Performs almost as well as earliest deadline scheduling. Can be easier to achieve stability by giving essential tasks shorter periods and thus higher priorities. |
|
|
IO devices
|
Data rate: rate of data transfer. May differ by several orders of magnitude among different devices.
Application: how the device is being used. Same device may be used in different ways (disk drive for file storage or for swap space). Complexity of control: some devices are much more complex than others (disk more complex than printer). Unit of transfer: one character at a time or blocks. Data representation: data is represented different ways on different devices. Error conditions: the kind of errors and their handling can be different among different devices. |
|
|
evoluation of io funct
|
CPU directly controls the device.
An I/O module controls the device, the CPU busy-waits on the I/O module. Interrupts used so CPU need not busy-wait. I/O module can do DMA to free CPU. I/O module has its own separate CPU, can run I/O programs. I/O module has a local memory of its own, can control large number of devices, for example, computer terminals. I/O function becomes more independent of main CPU. |
|
|
DMA
|
DMA occurs when the processor sends a command to the DMA module.
The command contains the following information: Whether it wants to read or write The address of the I/O device The starting memory address to read or write to The number of words to read or write The processor then continues with other work. The DMA module performs the data transfer to or from memory without processor assistance. When the transfer is complete, the DMA module interrupts the processor to indicate the transfer has been completed. DMA CONFIGS??????????????????? |
|
|
OS design objectives for IO
|
efficiency, generality
|
|
|
IO layers
|
The I/O facility may be organized in a hierarchical structure composed of layers.
Each layer relies on the next layer to perform more primitive functions and thus conceal the details of those functions. Ideally changes made to one layer do not impact the other layers. Layering helps bridge the difference in time scale between the hardware, which operates at time scales in the billionths of a second, and the user, which operates at time scales of a few seconds. Logical I/O layer: provides simple high-level interface to user with generic commands like open, close, read, write. Device I/O layer: converts requested operations into appropriate sequences of I/O instructions. Scheduling and control layer: low-level layer that interacts directly with the I/O module, including interrupts. A communications device might require several layers of communications architecture. A secondary storage device might require extra layers to manage it effectively. |
|
|
IO buffering
|
IO device: Block-oriented
Information is stored in fixed sized blocks. Transfers are made a block at a time. Used for disks and tapes. Stream-oriented Transfers information as a stream of bytes (no block structure). Used for terminals, printers, communication ports, mouse, and most other devices that are not secondary storage. single buffer....Operating system assigns a buffer in main memory for an I/O request. Transfers made to buffer. Buffer copied to user space when needed. Next unit is read into the buffer (read ahead, in anticipation of next request). Advantages: Allows next unit to be read while previous is processed. Process can be swapped since I/O is using OS buffer. For block-oriented devices, the buffer holds a block. For stream-oriented devices, the buffer might hold a byte of data, or an entire line of data. double Use two system buffers instead of one (double buffering). A process can transfer data to or from one buffer while the operating system empties or fills the ot |
|
|
circular
|
Two buffers may be inadequate if the process performs rapid bursts of I/O.
Use more than two buffers arranged in a circular queue. Peak demands are smoothed out. It should be noted that no amount of buffering will allow an I/O device to keep up with process requests indefinitely if the average demand is greater than the I/O device can service |
|
|
disk sched
|
Processor and memory speed continue to far outperform disk devices, leaving disk devices around four orders of magnitude slower.
To read or write, the disk head must be positioned at the desired track and at the beginning of the desired sector: Access time sum of seek time and rotational delay. Seek time time it takes to position the head at the desired track Rotational delay time its takes for the beginning of the sector to reach the head Data transfer time occurs as the sector moves under the head. |
|
|
timing
|
b=bytes to transfer, r=revolutions/second, N=bytes/track
Average seek time: Ts Average rotational delay: 1/(2r) If r=10 rev/sec, then rotates once in 1/10 sec On avg, need ½ rotation, takes 1/20 sec, or 1/(2r) Average transfer time: b/(rN) rN is how much data transfers per second b/(rN) tells how long to transfer b bytes Total average access time: Ts + 1/(2r) + b/(rN) // seek + rotate + transfer |
|
|
timing example
|
Suppose we want to read a file of 2500 sectors on 5 adjacent tracks, given:
Average seek time: 4ms Rotational speed: 7500 rpm 512-byte sectors, 500 sectors/track To read one track: Ts + 1/(2r) + b/(rN) 4ms + 1/(2*7500/60) + (512*500)/((7500/60)*512*500) 4ms + 4ms + 8ms = 16ms Assuming data on adjacent tracks means we essentially incur seek time only once, then reading remaining 4 tracks is: 4 * 12ms = 48ms. So, total time is 16ms + 48ms = 64ms. Suppose instead sectors are scattered across disk randomly. For each sector: Average seek: 4ms Rotational delay: 4ms Read 1 sector: b/(rN) = 512/((7500/60)*512*500) = 0.016ms Total for one sector is: 8.016ms To read file of 2500 sectors: 2500 * 8.016 = 20,040ms = 20.04 seconds So, seek time has a tremendous impact on I/O time. |
|
|
disk sched policy
|
fifo, sst, scan, c scan
deal with arm stickiness n step scan Divides the queue into subqueues of length N. When the requests in a subqueue are being processed, new requests are added to another subqueue. Therefore new requests to a particular track do not influence the current scan. If N is large, this approaches the SCAN policy. If N is small, it approaches the FIFO policy. FSCAN: Uses just two queues. While one queue is being processed, new requests are added to the other queue. |
|
|
RAID
|
“Redundant Array of Independent Disks”.
Each level represents a different approach with these three characteristics: Multiple physical drives viewed by the OS as a single drive. Data distributed across the drives. Redundancy to ensure recoverability if a drive fails. RAID levels 2 and 4 are not commercially available and are unlikely to be accepted. More disk devices increases the risk of disk failure. Therefore, redundancy is more important than for a single disk device. |
|
|
raid 0
|
Not a true RAID member because it doesn’t include redundancy.
Each disk is divided into “strips”. A strip can be a block, sector or other unit. The strips are sequenced across each disk, so strip 0 is on disk 0, strip 1 is on disk 1, etc. If there are n disks, then the first n strips form the first “stripe”, the second n strips from the second stripe, etc. So, if a read or write consists of n strips, these can be handled in parallel, one strip per disk. |
|
|
raid 1
|
Duplicates all data for redundancy.
Every disk has a mirror disk. Simple recovery but higher cost. |
|
|
raid 2
|
Strips very small, may be only a single byte.
All disks participate in each read or write. Uses parity disks for recovery. Hamming code can correct single-bit errors or detect double-bit errors. Only useful if lots of disk errors occur, which is not common today. |
|
|
raid 3
|
Like RAID 2 but only uses a single additional parity disk.
Uses parity bit instead of an error-correcting code. |
|
|
raid 4
|
Disks operate independently, so separate requests can be processed in parallel.
Strips are blocks. Parity strip stores parity information for blocks. |
|
|
raid 5
|
Like RAID 4 but distributes parity strips across all disks.
Keeps parity disk from being a performance bottleneck. |
|
|
raid 6
|
Uses two parity strips on different disks instead of just one.
Requires N+2 disks. Can recover even if two disks fail. Three disks must fail to be unavailable. |
|
|
disk cache
|
Buffer in main memory for disk sectors.
Contains a copy of some of the sectors on the disk. Reduces average disk access time. Replacement algorithms: LRU: replace least recently used block. LFU: replace least frequently used block. Some blocks may be used infrequently, but when they are used might be used repeatedly, thus building up a high reference count. This could cause LFU to make a poor choice. Frequency-based replacement: Divides the queue into sections new, middle, old. Reference moves block to new and increments reference count. Reference to block already in new section does not increment count. This helps blocks that will be frequently accessed over time compete with blocks that may be accessed repeatedly and then fall out of use. |
|
|
files and file systems
|
long term exist: secondary storage
sharable between process: shared access struct: vsome file systems manage the internal structure of a file, which can be organized in a way suitable for particular applications |
|
|
file operations
|
Create
creates a new file and adds it to the directory Delete remove from the directory and destroyed Open allows a process to perform functions on the file Close the process is no longer allowed to operate on the file Read read all or a portion of the file Write add new data or change existing data in the file Retrieve_All – to process the whole file Retrieve_One – selects a single record Retrieve_Next – move forward in file Retrieve_Previous – move backward in file Insert_One – may require adding at a particular position Delete_One – may need to preserve sequence Update_One – harder if length changes, preserve sequence Retrieve_Few – records matching a set of criteria |
|
|
file struct
|
Field:
Basic element of data Contains a single value Characterized by its length and data type Can be fixed length or variable length Record: Collection of related fields Treated as a unit Example: employee record Can be variable length if some of the fields are variable length, or if the number of fields may vary File Collection of similar records Treated as a single entity Have unique file names May restrict access Database Collection of related data (one or more files) Relationships exist among elements Managed by separate DBMS |
|
|
fms
|
Unix files are simply streams of bytes and do not have internal structure as far as the operating system is concerned.
Some OS’s such as mainframe systems provide various file structures the application can use. Set of system software providing file services to users and applications. Users and applications access files through the file management system. Programmer does not need to develop file management software for each application. Meet the data management needs and requirements of the user (described on next slide). Guarantee that the data in the file are valid. Optimize performance. Provide I/O support for a variety of storage device types. Minimize or eliminate the potential for lost or destroyed data. Provide a standardized set of I/O interface routines Provide I/O support for multiple users. |
|
|
user require
|
Each user:
Should be able to create, delete, read, and change files. May have controlled access to other users’ files. May control what type of accesses are allowed to the user’s files. Should be able to restructure the user’s files in a form appropriate to the problem. Should be able to move data between files. Should be able to back up and recover the user’s files in case of damage. Should be able to access the user’s files by using symbolic names. |
|
|
architecture
|
Device driver: communicates directly with hardware device.
Basic file system: handles physical I/O. Basic I/O supervisor: responsible for file I/O initiation and termination, device selection, I/O scheduling, buffer allocation. Logical I/O: Enables users and applications to access records. Provides record-oriented I/O capability. Access method: access files based on their structure and method of access. |
|
|
fms funct
|
See illustration on next slide:
Identify and locate a selected file. Use a directory to describe the location of all files plus their attributes. Enforce user access control (shared system). Employ access method on the records. Provide blocking for file I/O. Block for output and unblock for input. Manage secondary storage Allocate files to available blocks. Manage free storage of available blocks. Scheduling of I/O requests |
|
|
orgo and access
|
Criteria for choosing a file organization:
Rapid Access Ease of update Economy of storage Simple maintenance Reliability There may be trade-offs between criteria. Priority of criteria depends on how application will use the file. 5 file orgo |
|
|
pile
|
Data are collected in the order they arrive
Purpose is to accumulate a mass of data and save it Records may have different structures or no structure. Data access is by exhaustive search May be useful to store data prior to processing |
|
|
sequential file
|
Fixed format used for records.
Records are the same length. All fields the same (order and length). Field names and lengths are attributes of the file. One field is the key field Uniquely identifies the record Records are stored in key sequence New records are placed in a log file or transaction file. Log file is periodically merged with the master file. Useful in batch processing. |
|
|
indexed sequential file
|
File is like a sequential file with key and data.
Index provides a lookup capability to quickly reach the vicinity of the desired record. Greatly reduces the time required to access a single record, while still providing sequential processing. Additions can be handled by an overflow file, which can be periodically merged with the main file. |
|
|
indexed file
|
Uses multiple indexes for different key fields.
Abandons sequential format with single key. Records are accessed only by their index. Records can be variable length. Exhaustive index has pointers to every record. Partial index only has pointers to records having the field of interest. Useful in applications such as an airline reservation system that need to access particular records quickly, but rarely need to process them sequentially. |
|
|
direct or hash table
|
Turn key value into an address to support direct access of records in the file.
Gives very rapid access to data. Useful if records are only accessed one at a time. |
|
|
b trees
|
Indexes are often implemented as B-trees.
The B-tree will have a large branching factor resulting in a tree of low height. This results in fewer disk accesses to traverse the tree in a search. |
|
|
directory
|
The directory contains information about the files, including attributes, location, and ownership.
The directory is itself a file, owned by the OS and managed by the file management system. The next slides give information typically found in the directory for each file. |
|
|
dir oper and struct
|
Search: find a file in the directory.
Create file: add entry to directory when a file is created. Delete file: remove entry from directory when file is deleted. List directory: all or a portion may be listed. Update directory: change file attributes stored in directory struct A tree-structure is used for storing the file directory. At the top is the master directory, beneath it are each user directory. Every level may contain files and subdirectories. |
|
|
dir naming
|
Users refer to files by their symbolic names.
Each name must be unique. In a tree structure, the path to the file helps eliminate duplicate name problems. Most systems provide for a working directory, where file names can be specified relative to it. Users typically have a default, or home, directory upon logging in. |
|
|
file sharing
|
In a multiuser system, files should be able to be shared between users.
This presents two issues: Access rights Simultaneous access When sharing files, we have to have a way of controlling access to the file. Typically one user is the owner. The owner has all of the access rights and may grant rights to others. Access rights may be given to different classes of users. Typical classes are: Specific user Group of users All: Examples of access rights: None: file is unknown to user. Knowledge: user can determine file existence and owner. Execution: can execute the file. Reading: can read the file. Appending: can only append to end of file. Updating: can modify file contents. Changing protection: can change access rights. Deletion: can remove the file. These rights may constitute a hierarchy, with higher level rights including the lower level ones. When access is granted to append or update a file to more than one user, the OS or file management system must enforce discipline. One appro |
|
|
file sharing
|
One approach is to lock the entire file when it is to be updated.
Another approach is to lock individual records during update. |
|
|
record blocking
|
Users work with a logical view of a file as a set of records.
The I/O device works with the physical view of a file as a set of blocks. Blocking of records is performed when writing data, unblocking is performed when reading data. Blocking considerations: The larger the block, the more records that are passed in a single I/O. For sequential access this reduces I/O’s, but may result in unnecessary data transfer for random access. Typically blocks are of fixed length to simplify the I/O transfer. There are three blocking methods: Fixed: fixed-length records. May cause internal fragmentation. Variable-length spanned: variable-length records which may span blocks. Permits unlimited record size. May require multiple I/O’s. Variable-length unspanned: variable-length records which do not span blocks. May cause internal fragmentation. |
|
|
secondary storage management
|
A file consists of a collection of blocks on the secondary storage device.
The OS or file management system manages the blocks. There are two management issues: Allocating blocks to files. Maintaining a list of free blocks. |
|
|
file allocation
|
File allocation issues:
Whether to allocate the maximum space required all at once, or to allocate space in portions. If portions are used, how big should a portion be? If portions are used, how to keep track of the portions. Preallocation requires that the maximum file size be declared and allocated when the file is created. May create waste as users over-estimate required size to ensure space needs are met. Dynamic allocation allows portions of space to be given to the file so that it may grow dynamically. Two basic methods: Large, variable-length contiguous portion. Good performance. May cause fragmentation. Allocation table is simple, just need pointer to beginning and length. Small fixed-sized blocks. Good flexibility. Requires more complicated allocation table to keep track of non-contiguous blocks. |
|
|
methods
|
Three methods of file allocation:
Contiguous allocation – a single contiguous set of blocks is allocated to a file at the time of file creation. Thus, this is a preallocation method of a variable-size portion. May require periodic compaction due to fragmentation. Good for sequential file access. Chained allocation – allocate individual blocks. Each block contains a pointer to the next block. Indexed allocation – an index specifies the location of each block. |
|
|
free space management
|
It is necessary to know what space is available in order to perform allocations.
A “disk allocation table” keeps track of available space. Techniques: Bit tables: each bit represents a block Chained free portions: free portions are chained together. Indexing: index keeps track of every free portion as if it was a file. Free block list: blocks are numbered and list of free block numbers is maintained. |
