New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Allie West II


Allie West II

GPA 3.51

Shivakant Mishra

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Shivakant Mishra
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 177 page Class Notes was uploaded by Allie West II on Thursday October 29, 2015. The Class Notes belongs to CSCI 3753 at University of Colorado at Boulder taught by Shivakant Mishra in Fall. Since its upload, it has received 20 views. For similar materials see /class/231982/csci-3753-university-of-colorado-at-boulder in ComputerScienence at University of Colorado at Boulder.




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
CSCI 3753 Operating Systems Process Scheduling Lecture Notes By Shivakant Mishra Computer Science CUBoulder Last Update 012506 Process Scheduling Process scheduling problem When more than one processes are ready to run how does OS decide which process to run next Preemption or voluntary yield New Process Done Running Resource M Resources Goals Efficiency 100 CPU utilization Fairness each process should get a fair share of the CPU Response time minimize for interactive users Turnaround time minimize for batch users Throughput maximize the number of jobs processed per unit time Some of these goals are contradictory Any scheduling algorithm that favors some class of jobs hurts another class of jobs Every process is unique and unpredictable IO intensive CPU intensive Cannot predict how long a process will run before blocking Two classes of scheduling algorithms 1PreemptiVe scheduling a running process can be suspended by the scheduler and moved to the ready queue 2NonpreemptiVe scheduling a running process is suspended only when it blocks or terminates Preemptive Scheduling Round Robin Scheduling Most Widely used algorithm Simple and fair A xed time interval called quantum is de ned When a process is scheduled to run it can run for at most one quantum If the process is still running at the end of its quantum it is preempted and the CPU is given to another process from the ready queue lfthe process blocks or terminates before its quantum expires another process from the ready queue is scheduled to run Preempted processes are placed at the end of the ready queue Example four processes in the ready queue with execution times as follows pl 500 ms p2 300 ms p3 150 ms p4 100 ms Context switoh time 5 ms ltFiguregt Quantum size Too small too many context switches Too large Response time for smaller jobs is poor Quantum of 100 ms are good compromise 0 Priority scheduling Not all processes are equally important for example system administrator vs other users Each process is assigned externally a priority Process with the highest priority runs Preemptive version the running process is preempted whenever a higher priority process is ready to run Priority scheduling is often combined with RR scheduling Multiplelevel queues Separate queue for each priority Priority scheduling to choose a queue RR strategy among processes in the same queue Problem Lowerpriority processes may starve Priority of a process can be changed dynamically Assign high priority to IO bound processes It is more ef cient give CPU bound processes a large quantum once in a While than to give small quanta frequently Reduce number of context switches How do we determine if a process is 10 bound or CPU bound Multiple queues with priority classes in CTSS Processes in highest priority class run for one quanta processes in the next priority class run for 2 quanta processes in next priority class run for 4 quanta and so on If a running process uses all of its time slice it is preempted and its priority is lowered If a running process blocks before its allocated quantum expires its priority is raised Reading assignment BSD UNIX Scheduling Policy Page 278 Windows NT2000XP Thread Scheduling Page 279 Firstcomefirstserved F CF S Processes are scheduled in the order they request the CPU Nonpreemptive strategy Simple but suffers from poor performance Not used Shortest Job Next Service times of all processes are known in advance an unusual situation Schedule a process Whose service time requirement is least Minimize the average wait time Can be used in routine data processing systems Deadline Scheduling Hard realtime systems processes have a realtime deadline by which their execution must complete Scheduling goal Must be able to meet the deadlines of all processes A process is admitted in the ready list only if the scheduler can guarantee that it will be able to meet each deadline imposed by the process Example Earliest deadline rst scheduling Twolevel scheduling If the main memory is insufficient some processes in the ready list may reside on a disk Context time for processes in the disk is considerably larger than that for processes in main memory Use a twolevel scheduler A lowerlevel scheduler schedules processes that are in mam memory A higherlevel scheduler shuf es periodically processes between main memory and disk Criteria for higherlevel scheduler How long a process has been in main memory or disk How much CPU time has a process used up so far How big is the process Priority CSCI 3753 Operating Systems Device Management Lecture Notes By Shivakant Mishra Computer Science CUBoulder Last Update 041206 IO Devices Output Device Processor Input Device Device Manager Control IO devices Issue 10 commands to the devices Catch interrupts Handle errors Provide a simple and easytouse interface Device independence same interface for all devices Device Characteristics IO devices consist of two highlevel components Mechanical component Electronic component device controllers OS deals with device controllers Software in the CPU Device Controller Application Program Abstract IO Machine Device manager Program to manage device controller Supervisor mode software Device Controller Device Device Controller Interface idle nished working unde ned Command Status Logic Device Controller Each controller exports a set of registers for communication with CPU Data buffers Command register Status register two ags busy done busy done 0 O idle O I nished 1 0 working 1 1 unde ned Device Driver Software that implements device management functions using device controllers A separate device driver for each device Provide a uniform access to higher level Example disk driver ReadBlockO WriteBlockO Etc Device Driver Interface ivrite Cg ll Device Interface 3 Terminal Driver Printer Driver i 7 Disk Driver ii V Terminal Controller Printer Controller Disk Controller Device Management Organization System Interface Application Process li File Manager Hardware Interface DeviceIndependent ll DeviceDependent ll Command I Status I Data I Device Controller System Call Interface Functions available to application programs Abstract all devices and les to a few interfaces Make interfaces as similar as possible Block vs character Sequential vs direct access Device driver implements functions one entry point per API function Example BSD UniX Driver open close ioctl read write strategy select stop Prepare deV for operation No longer using the device Character deV speci c info Character deV input op Character deV output op Block deV inputoutput ops Character deV check for data Discontinue a stream output op IO Strategies Direct 10 with Polling InterruptDriven IO Memorymapped IO Direct Memory Access Direct 10 with Polling CPU starts the IO and polls the status register to determine when the operation is complete Read operation Device driver queries the status register to check if the device is idle if busy wait Store command in controller s command register Repeatedly check status register for operation completion polling Copy controller s data registers into user s space Write Operation Device driver queries Copy data from user space to controller s data registers Store command in controller s command register Repeatedly check status register Polling IO Read Operation readdeVice Data System Interface read function write function 4 Hardware Interface Command Status Device Controller Problem Polling wastes CPU time Step 4 Interrupt Driven IO IO device interrupts the CPU when an IO operation is complete Interrupt Driven IO Operation readdevice Al Sy 1 Data II E 8b stem Interface Device Status Table 4 7 39 read dr1ver Dev1ce Handler g 2 6 Interrupt Handler Hardware Interface 5 Device Controller I Command I Status I Data I 8a Memorymapped IO Device controller s registers belong to the address space of the computing system No separate readwrite instructions are needed to access device registers Reduces of instructions in the processor instruction set Memory Mapped IO Memory Addresses Device Addresses MUN Primary Memory H Device 0 Device 1 Device nl Memory Addresses MUN Primary Memory HI Device 0 Device 1 Device n Direct Memory Access DMA controllers read and write information directly fromto memory addresses with no CPU intervention after the driver has initiated an lO operation Overlaps with CPU DMA Controller Controll Device I Device Device Management Consists of two parts Device independent part A set of system calls that an application program can use to invoke IO operations A particular device will respond to only a subset of these system calls A keyboard does not respond to write system call POSIX set open close read write lseek and ioctl Device Independent Function Call TTap39Table nwxu 1 devfuncidevID m Processing common to all devices switchdevID case devO devOfunci break case devl devlfunci break case deWM devMfunci break Processing common to all devices Device dependent part Use device controller command data status registers Adding a New Device Write devicespeci c functions for each IO system call For each system call add a new case clause to the switch statement in device independent function call Compile the kernel and new drivers Recon gurable Device Drivers Allows system administrators to add a device driver to the OS Without recompiling the OS OS binds its code to the driver function at runtime An entry table stores the actual function pointers for each system call devfunciN Replace switch statement with devfuncij Device registration make a system call to ll appropriate function pointers in the entry table Recon gurable Device Drivers Svstem call interface open in 1 read 2 4 etc Driver for Device j Entry Points for Device j Other Kernel 39 services Data Buffering A technique to keep the IO devices busy during times when a process is not requiring IO operations Input buffering Copy information into the primary memory before the process requests it Output buffering Save information in memory and then write to the device While the process continues execution Hardware Buffering Controller Con roller Device I Device I Device I Unbuffered W14 W1 Controller reads bi Controller read bi1 Double Buffering in the Driver 3 1 0 2 3 1 G Controller Controller D A Bo 3 A Bg ll A A 5 ct E DeV1ce DeVICe Circular Buffering To data consumer From data producer Device Characteristics Block devices and character devices of bytes transferred on an individual operation Block devices disks tape etc Character devices terminals line printers mouse etc Storage devices and communication devices Storage devices for permanently storing data even when system is turned off Example Disk tape etc Communication devices for introducing data into a system and passing data from one system to another Example keyboard mouse Ethernet etc Communication Devices Character devices that transfer bytes of information between a computer and a remote device Communications controller Driver manipulates a communications controller Serial and parallel communications controllers Device and controller must agree on the interface and a protocol for using that interface A Generic Communications Device Bus Generic Controller Local Device Communications Controller Cabling connecting the controller to the device Device oPrinter Modem Networllt Serial Port Serial Memoryl Device I 0 Printer 0 Terminal 0 Modem 0 Mouse 0 etc UART Serial communications controllers are implemented using a specialized microprocessor Universal Asynchronous Receiver Transmitter UART Includes onboard RAM and ROM RS232 Standard controllerdevice protocol Standardized to support RS232 controllerdevice interactions Driver only needs to supply a few parameters to UART Examples Terminal keyboard and monitor modem RS232 Protocol De nes the interface between an asynchronous device and the controller Physical nature of cabling that connects device and controller 9pin or 25pin connector Signal exchanged meaning of signals Signals are exchanged at the speed of 110 57600 signals per secbaud rate 11 signals are exchanged for each 8bit byte transmitted For a device to be connected to a serial communications port the device and port must agree on interface and protocol used Serial Port Device Driver API Device Driver 0 Set UART parms readwrite ops Software on the CPU Bus Interface Interrupt hander UART API Serial Device 39Pal ity UART obits per byte I etc RS232 Interface 9pin connector 4Wires 0 bit transmitreceive Adding a Modem Serial Device Dialing amp connecting 0 Convert analog voice to from digital 0 Convert bytes tofrom bit streams Transmitreceive protocol Switched Telephone Network Adding a Modem Device Driver Set UART parrns readwrite ops Interrupt hander Serial Device Transmitreceive pr RS232 Exploiting the Phone Network CPU Ilti ogical Communicatiorgt CPU I y 0mm Switched Telephone Network Data Networks Technology focus includes grotocols and software CPU I ltogical Communication CPU I Network Network Memo Device ry Device Data Network Parallel Communication Ports To connect a printer to a computer Supports twoway communication Zip drive Universal Serial Bus USB For higherspeed bidirectional data exchange 100s of Mbps USB port External port Supports USB protocol Can connect any USBcornpliant device Also provides power to the device Firewire IEEE 1394 Firewire Adopted at the same time as USB 1995 Higher speed alternative to USB De nes a serial bus that Operates at 100 200 or 400 Mbps Future 32Gbps for devices in close proximity Better suited for streaming media applications Rotating Media Cylinder set of tracks Track Cylinder y C 03 a Multisurface Disk b Disk Surface 0 Cylinders Storage Device Device Driver API Driver 0 Get disk description 0 Set SCSI params readwrite ops Interrupt handler SCSI API commands obits per byte etc Controller Magnetic Disk SCSI Disk Optimizations Transfer Time Time to copy bits from disk surface to memory Disk latency time Rotational delay waiting for proper sector to rotate under RW head Disk seek time Delay While IUW head moves to the destination trackcylinder Access Time seek latency transfer Seek time dominates the access time Optimizing Seek Time Seek time dominates access time gt minimize seek time across the set Tracks 099 Head at track 75 requests for 23 87 36 93 66 Firstcome rstserve F CFS 52 64 51 57 27 251 steps Requests 23 87 36 93 66 Shortest Seek Time First SSTF 75 66 8793 3623 112165713107steps Scan 75 87 93 99 66 36 23 12663330131005teps Look 75 8793 66 3623 12627301387steps Requests 23 87 36 93 66 Circular ScanLock Homing command Circular Scan 75 87 93 99 23 36 66 1266h0mc23133090h0mc Circular Look 75 87 93 23 36 66 126h0me23 13 3084h0mc CSCI 3753 Operating Systems File Management Lecture Notes By Shivakant Mishra Computer Science CUBoulder Last Update 041806 High Level View Application Program mount write WriteFile CreateFile open close read CloseHandle ReadFlle lseek SetFilePointer I 7777 a b v o ni ago E0222 70222 205 8 205 8 saga eEga c quot c 5 gs UNIX Windows Hardware Why Programmers Need Files ltheadgt HTML headgt Web Editor I E ltbodygt E Browser a boolygt foohtml ltheadgt ltbodygt ltbodygt Persistent storage Shared device ltheadgt Structured information Can be read by any app Accessibility Protocol File Management File is a named ordered collection of information The le manager administers the collection by Storing the information on a device Mapping the block storage to a logical View Allocatingdeallocating storage Providing le directories What abstraction should be presented to programmer Information Structure Applications Records Structured Record Files RecordStream Translation Byte Stream Files Storage device E Byte Stream File Interface fileID openfileName closefileID readfileID buffer length writefileID buffer length seekfileID filePosition Low Level Files fid open fileName geadmid buf buflen lbolbllbzl I closefid int open m int close m int read m int write m int seek m Storage device response to commands E Structured Files Records Record Oriented Sequential Files Logical Record fileID openfileName closefileID getRecordfileID record putRecordfileID record seekfileID position RecordOriented Sequential Files Logical Record H byte header k byte logical record Record Oriented Sequential Files Logical Record H byte header k byte logical record Physical Storage Blocks Example Electronic Mail struct message putRecordstruct message msg The mail message putAddressmsg gtto address to putAddressmsggtfrom address from putAddressmsggtCC line subject putLinemsg gtsubject address cc putStringmsggtbody string body struct message getRecordvoid struct message msg msg allocatesizeofmessage msg gtto getAddress msg gtfrom getAddress msg gtcc getAddress msg gtsubject getLine msg gtbody getString returnmsg Indexed Sequential Files Suppose we want to directly access records Add an index to the le fileID openfileName closefileID getRecordfileID index index putRecordfileID record deleteRecordfileID index Indexed Sequential Files Application structure lAecount Index 012345 123456 p n 294376 index i 529366 965987 index j index k More Abstract Files Inverted les System index for each datum in the le Databases More elaborate indexing mechanism DDL amp DML Multimedia storage Records contain radically different types Access methods must be general Implementing Low Level Files Secondary storage device contains Volume directory sometimes a root directory for a le system External le descriptor for each le The le contents Manages blocks Assigns blocks to les descriptor keeps track Keeps track of available blocks Maps tofrom byte stream Boot Sector Disk Organization Volume Directory Blk Blk Blk Blk Blk Blk Track 0 Cylinder 0 Track 0 Cylinder 1 Track 1 Cylinder 0 Track N 1 Cylinder 0 Track N 1 Cylinder Ml LowLevel File System Architecture Sequential Device Randomly Accessed Device File Descriptors Externa1 name Current state Sharable Owner User Locks Protection settings Length Time of creation Time of last modi cation Time of last access Reference count Storage device details An open Operation Locate the ondeVice external le descriptor Extract info needed to readwrite le Authenticate that process can access the le Create an internal le descriptor in primary memory Create an entry in a per process open le status table Allocate resources eg buffers to support le usage File Manager Data Structure Keep the state of the process le session 6 Copy info from 7 Open File external to the Return a ProcessFile Descriptor Open le reference to Session desc ptor the data structure External File Descriptor Opening a Unix File fid open fileA readfid buffer len flags OnDevice File Descriptor 0 File structure f inQde 0 stdin l stdout 2 stderr 3 Open File Table Internal File Descriptor Block Management The job of selecting amp assigning storage blocks to the le For a xed sized le of k blocks File of length In requires N lmkl blocks Byte bi is stored in block Likl Three basic strategies Contiguous allocation Linked lists Indexed allocation Contiguous Allocation Maps the N blocks into N contiguous blocks on the secondary storage device Dif cult to support dynamic le sizes File descriptor Head position 237 First block 785 Number of blocks 25 Linked Lists Each block contains a header with Number of bytes in the block Pointer to next block Blocks need not be contiguous Files can expand and contract Seeks can be slow First block I 39 J Length Length Length Byte 0 Byte 0 Byte 0 Head 417 Byte 4095 Byte 4095 Byte 4095 Extract headers and put them in an index Indexed Allocation Simplify seeks May link indiees together for large les Index block Head 417 Byte 0 Byte 4095 Block 0 Byte 0 Byte 4095 Byte 0 Block 1 Byte 4095 Block N l Unix Files inode mode ata owner Data Direct block 0 Direct block 1 Direct block 11 Single indirect Index Double indirect Triple indirect Data Data Index j gt Index Data I gt Data Index Index Index Index Data rm Index J Data Unallocated Blocks How should unallocated blocks be managed Need a data structure to keep track of them Linked list Very large Hard to manage spatial locality Block status map disk map Bit per block Easy to identify nearby free blocks Useful for disk recovery Directories A set of logically associated les and sub directories File manager provides set of controls enumerate copy rename delete traverse etc Directory Structure How should les be organized Within directory Flat name space All les appear in a single directory Hierarchical name space Directory contains les and subdirectories Each ledirectory appears as an entry in exactly one other directory a M Popular variant All directories form a tree but a le can have multiple parents Directory Implementation Device Directory A device can contain a collection of les Easier to manage if there is a root for every le on the device the device root directory File Directory Typical implementations have directories implemented as a le with a special format Entries in a le directory are handles for other les which can be les or subdirectories Unix mount Command IA 1 FS blah mount FS at foo CSCI 3753 Operating Systems Memory Management Lecture Notes By Shivakant Mishra Computer Science CUBoulder Last Update 030906 Introduction Memory is an important shared resource in a computing systems Shared among all processes Used by processes to store their state code heap stack Used for execution of processes CPU registers Can be used for interprocess communication and synchronization Store information that can outlive the lifetime of a process Memory Manager Memory allocation and deallocation Static allocation Dynamic allocation Memory protection Address space The External View of the Memory Manager Application Program System Calls VirtualAlloc exec VMQuerY shmalloc Sbrk virtualLock V1rtualFree getrlimit ZeroMemory Flle Mgr Device Mgr Process Mgr Flle Mgr Device Mgr Process Mgr UNIX 7 39 g Hardware Memory manager functions Requirements Minimize executable memory access time Maximize executable memory size Executable memory must be costeffective Today s memory manager Allocates primary memory to processes Maps process address space to primary memory Minimizes access time using costeffective memory con guration May use static or dynamic techniques Storage Hierarchies The Basic Memory Hierarchy CPU Registers W z o 39 6 60 6 Jae O Primary Memory O Executable Memory 6 90 eg RAM 00 6ch egg 939 4 Secondary Memory e g Disk or Tape HWH Larger storage Contemporary Memory Hierarchy amp Dynamic Loading CPU Registers fit i i A L2 Cache Memory 39 y i Main Memory 7 39 i 7 Li W Secondary Rotating Magnetic Memory t f Optical Memory i f c C Sequentially Accessed Memory Faster access Exploiting Memory Hierarchy Upward moves are usually m operations Require allocation in upper memory Image exists in both higher amp lower memories Updates are rst applied to upper memory Downward move is usually destructive Destroy image in upper memory Update image in lower memory Place frequentlyused info high infrequentlyused info low in the hierarchy Recon gure as process changes phases Address Space vs Primary Memory Process Address Space Hardware Primary MemOl39y rrrrrrrrrrrrrrrrrrrrrr Mapped to Object other than memory Creating an Executable Program Source code Stored in secondary storage Compile Translate elements External references eg library calls are unresolved Relocatable object code Link Combine elements Resolve external references Addresses Relative starting at address 0 Loadable object module stored in secondary storage Load Allocate primary memory Adjust addresses in address space Copy address space from secondary to primary memory I III I II II I Source Library Other code code objects Secondary memory Primary memory Process address space A Sample Code Segment static int gVar int procaint arg gVar 7 putrecordgVar The Relocatable Object module Code Segment Relative Address Generated Code 0000 Data Segment 0008 entry proca Relative Address Generated variable space 0220 load 7 Rl 0224 store R1 0036 0036 Space for gVar variable 0228 push 0036 0232 call putrecord 0049 last location in the data segment 0400 External reference table 0404 putrecord 0232 0500 External definition table 0540 proca 0008 0600 symbol table 0799 last location in the code segment The Absolute Program Code Segment Relative Addres s 0000 1008 1220 1224 1228 1232 1399 2334 2670 2999 Generated Code Other module s t en ry prOC a Data Segment Relative load 7 R1 Store R1 0136 Address Generatedvarlable space 0136 Space for gVar variable 1000 last location in the data segment End of proca Other modules entry putrecord optional symbol table last location in the code segment The Program Loaded at Location 4000 Ilelative Address 0000 4000 5008 5036 5220 5224 Generated Code Other process s programs Other modules entry proca Space for gVar variable load 7 Rl store R1 7136 push 5036 call 6334 End of proca Other modules entry putrecord optional symbol table last location in the code segment first location in the data segment Space for gVar variable Other process s programs Memory Allocation Loader OS needs to allocate memory to process Two approaches Fixed partition Memory is divided into N xed size regions Variable partition Number location and size of memory regions vary dynamically as processes come and go Fixed Partition A process that needs x amount of memory can be loaded in any free memory region of size r such that r gt x May try to minimize r x Advantages Simplicity Memory protection can be easily implemented Widely used in batch processing systemsWhy Problems Two problems with xed partitions Internal fragmentation Memory in a region that a process does not need rx is wasted Memory requirements of a process may grow over time dynamic memory What if the memory requirements exceed the allocated region size pi needs ni un1ts T E Operating pi System Region 0 N0 Region 1 N1 Region 2 N2 Region 3 N3 Internal Fragmentation Operating System Region 0 Region 1 pi Region 3 Variable Partitions Memory is con gured as a single large block Basic allocation strategy Find x units of contiguous memory that is currently available Advantages No internal fragmentation Improves memory utilization Problems Complexity Complicates memory allocationdeallocation Need for memory compaction Operating Operating Operating Operating System System System System Process 0 Process 0 Process 0 Process 1 Process 6 Process 6 Process 2 Process 2 Process 2 Process 3 PIOCGSS 5 Process 5 Process 4 Process 4 Process 4 Loader adjusts every address in every absolute module When placed in memory C0m2actlon moves program 1n memory External fragmentation External fragmentation Small fragments of available memory that are too small for any process Question How is external fragmentation different from internal fragmentationquot Cost of memory compaction load R1 OxO20lO 3F013010 ltj Program loaded at OXOlOOO 3F016010 Program loaded at OXO4OOO Must run loader over program again To address the problems of internal fragmentation and external fragmentation and to support dynamic memory allocation memory is divided into small allocation units Allocate multiple consecutive units to a process Two ways to keep track of available memory blocks Bit maps Linked list Dynamic memory allocation Divide memory into small xed size allocation units Allocate multiple consecutive units to a process Two ways to keep track of available memory blocks Bit maps Linked list Bit maps A bit is reserved for each unit ltFiguregt Allocation K units are needed Memory overhead small Not used much Linked list maintain a linked list of free and allocated memory segments ltFiguregt Linked list can be stored in free memory segments Doubly linkedlist will simplify updates Maintain a pointer from PCB to the corresponding node simpli es deallocation Allocation Traverse the list Allocation strategies First Fit allocate the rst memory hole that is big enough Next Fit same as rst t except that the scan begins from the last allocation point instead of beginning Best Fit Search the entire list and choose a memory hole that is closest in size but larger than the requested size External fragmentation Worst Fit Choose the largest memory hole All four allocation strategies can be speeded up by maintaining separate lists for memory holes and allocated portions Deallocation is more complicated Memory holes list can be maintained in sorted order Memory holes list can be maintained in the memory holes itself An executable program Text Segment Initialized Part Data Segment Uninitialized Part Data Segment Heap Storage Stack Segment Environment Variables Assume that there is no memory limit 32bit address space a process can be as large as 4 GB This address space is divided User address space process is running in user mode 3 GB Supervisor address space process is running in supervisor mode Map absolute program address space into process address space Extra level of indirection simplifies memory management and enable dynamic binding Program and Process Address Spaces Process Address Primary Space Memory Absolute 0 Program Address Space IJser gt Process Address 8px 3GB Supervisor Process Address Space Multiprogramming Support 0 Operating Unused A System R0 In Use B E Process 1 R1 C Process 3 R2 D E Process 0 R3 F G Process 1 H R4 Memory Mgmt Strategies FixedPartition used only in batch systems VariablePartition used everywhere except in Virtual memory Swapping systems Popularized in timesharing Relies on dynamic address relocation Now dated Dynamic Loading Virtual Memory Exploit the memory hierarchy Paging mainstream in contemporary systems Segmentation the future Moving an Executable Image 02000 Executable E Loader l Program 39 Executable Image Dynamic Address Relocation CPU Relative Address OX0 2 O l O OX1 2 O l O V load MAR Addresses in load module start at O Program loaded at OXIOOOO gt Relocation Register Program loaded at OXO4OOO gt Relocation Register We never have 10 Change the load module addresses Multiple Segment Relocation Registers CPU Relative Address Stack Register Oxl20lO MAR Runtime Bound Checking CPU Relative Address E lt TBound checkmg IS M AR meXpenswe to add Limit register Length of memory segment allocated Interrupt Provides excellent memory protection Swapping Special case of dynamic memory allocation Suppose there is high demand for executable memory Equitable policy might be to timemultiplex processes into the memory also spacemuX Means that process can have its address space unloaded when it still needs memory Usually only happens when it is blocked Image for pj Sharing a Portion of the Address Space Multiprocessors Address Space for Process 1 Primary Memory Address Space for Process 2 Shared memory as separate segment CPU Executing Process 1 Relocation Private to Process 1 7 Private to Process 2 Primary Memory CSCI 3753 Operating Systems Introduction Lecture Notes By Shivakant Mishra Computer Science CUBoulder Last Update 011306 Operating Systems OS is an essential and perhaps the most important part of a computing system Controls hardware components Provides a usable interface Allows sharing of various computing components One of the largest piece of software Two views of an OS Extended machine Hardware is too complex for most computer users to understand OS provides users with an equivalent of an extended or virtual machine that is easier to use 39 RCSOUI CC manager Computer system comprises of many resources processors CPUs memory clocks disks key board mouse monitor etc OS allows sharing and effective utilization of these resources Evolution of OS 1940 s and 50 s Vacuum tubes Single user No programming language machine language Used for straightforward numerical calculations No OS mid 50 s to mid 60 s Transistors more reliable Punch cards Batch processing Used for scienti c and engineering calculations FORTRAN Batch Processing Execute a prede ned collection of programs jobs called a batch No human interaction mid 60 s to mid 70 s Integrated circuits Multiprogramming CPU is shared among several programs that execute simultaneously Timesharing multiple terminals interactive programming user view Multitasking A single user can run several programs simultaneously Examples CTSS Multics UniX mid 70 s to 90 s LSIVLSI LANs PCs and workstations Process control and realtime systems User friendly software Distributed operating systems At present OS has evolved from technologies such as batch processing multiprogramming time sharing multitasking and communication networks LANs and WANs Networked systems User friendliness Webbased OS design is guided by two factors Technology Applications Realtime operating systems OS to support NOWs OS to support multimedia Highly secure OS OS for small resource constrained devices CSCI 3753 Operating Systems Distributed Systems Lecture Notes By Shivakant Mishra Computer Science CUBoulder Last Update 050106 Computer Networks Interconnect different computing components using a communication medium A computer network that can support widely different applications distributed computer games air traffic control system teleconferencing Videoondemand medical applications accounting banking and so on Widely different components PCs Workstations Supercomputers Laptops Palmtops home appliances and so on Widely different software Operating systems Unix LINUX Windows Connecting Components 1 Links Physical medium that connects two or more computers PointtoPoint Multiple Access 2 Nodes Computersspecial hardware Connecting Computers Using the Telephone Network Local Computer Remote Computer CPU I CPU I Serial Serial Memory I Port I Port I Memory I Modem Modem Switched Telephone Network I Network Device Data Networks Network Device Broadcast Network Li Network Multiple senders Can address multiple receivers Direct connection between every pair of nodes will make a network very expensive Indirect Connectivity Nodes forward data received from one link to another Forwarding nodes form a switched network Two types of switched networks 1Packet switched network 2Circuit switched network Packet switched networks Most popular Nodes send discrete blocks of data called packetmessage Store and forward receive entire packet store it in internal memory forward the entire packet Circuit switched network Used in telephone systems Establish a dedicated circuit across a sequence of links Source can send a stream of bits to the destination Indirect Networks Telephone Circuit Based Pacet Based Cloud Distinguishes between nodes that implement a network and the nodes that use it Any type of network single pointtopoint link multiple access link a switched network Internetwork 112m Router 0r Gateway Router or Gateway Forwards messages from one network to another Address Byte string that identi es a node or a set of nodes Typically unique for each node Routing Process of determining how to forward messages towards the destination node based on its address Unicast Multicast Broadcast Network Architecture Networks must evolve to accommodate changes in both the underlying technologies upon which they are based as well as changes in the demands placed on them by applications program Network architecture Guides the design amp implementation of networks Network design is a very complex task System is divided into several layers of abstractions to deal with the complexity Multiple abstractions can be provided at the same level Abstraction Defines a model with some functionalities Provides an interface Hides details Abstraction leads to layering of the system Application Logical Channels HosttoHost Connectivity Hardware Abstract objects that make up the layers of a network are called protocols A protocol provides a communication service that higher level objects can use to exchange messages Host 1 Host 2 Service 39 I f 3 Peer to Peer genIce nter acu v Interface Interface Protocol Protocol Protocol Protocol speci cation Protocol implementation A protocol may be implemented in many different ways For peertopeer communication to work correctly protocol implementations must implement the same speci cation Two or more protocol modules that do accurately implement a protocol speci cation are said to interoperate with each other Protocol stacks must be same at different hosts for applications to communicate Standardization bodies Establish policies for a particular protocol graph ISO International Standards Organization IETF Internet Engineering Task Force OSI Architecture De ned by ISO Open System Interconnection Seven layers ISO in conjunction with International Telecommunications Union ITU publishes a series of protocol speci cations based on the OSI architecture X25 X400 X500 and so on Public X25 network Private Tymnet network Application Datalink Presentation Session Transport Physical Physical handles transmission of raw bits over a communication link Datalink collects a stream of bits into larger aggregates called frames Implemented by network adaptors Network collects frames into packets routing These three layers provide hosttohost connectivity They are implemented on all nodes in the network


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.