DOC PREVIEW
U of I CS 241 - System Programming

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Homework 2 – System ProgrammingCS241, Spring 2007 Deadline: Wednesday 05/02/2007, 4pm, 3120 SCSubmission Steps: (1) YOUR NETID MUST BE AT THE TOP OF EVERY PAGE;(2) PROVIDE THE SOLUTION IN HARD COPY – DO NOT USE HANDWRITTING; (3) START EACH OF THE FOUR PROBLEMS ON A NEW PAGE – IT WILL MAKE THE GRADING PROCESS MUCH FASTER!!(3) BRING THE HARD COPY HW2 SOLUTION TO ANDA OHLSSON’S OFFICE, 3120 SIEBEL CENTER BY WEDNESDAY, May 2, 4PMProblem Points GraderProblem 1 /25Problem 2 /25Problem 3 /25Problem 4 /25Total /1001. Problem on Input/Output (25 Points)1A. (9 Points) Although DMA does not use the CPU, the maximum transfer rate isstill limited. Consider reading a block from the disk. Name three factors that mightultimately limit the rate transfer. 1B. (6 Points) An alternative to interrupts is polling. What are the circumstances inwhich polling is better than interrupts? Give at least two circumstances. 1C. (10Points) Let us assume a disk with rotational speed of 15,000 rpm, 512 bytesper sector, 400 sectors per track and 1000 tracks on the disk, average seek time is4ms. We want to transmit a file of size 1 MByte, that is stored contiguously on thedisk. What is the transfer time for this file? What is the average access time for thisfile? What is the rotational delay in this case? What is the total time to read 1 sector?What is the total time to read 1 track?2. Problem on Basic Memory Management (25 Points) 2A. (13 Points) In this problem you are to compare the storage needed to keep trackof free memory using a bitmap versus using linked list. The 128 MB memory isallocated in units of n bytes. For the linked list, let us assume that memory consists ofan alternative sequence of filled fragments and empty holes, each 128 KB. Alsoassume that each node in the linked list needs 32 bit memory address, a 16-bit length,and a 16-bit next-node field. How many bytes of storage are required for eachmethod? Which one uses less storage space? 2B. (12 Points) Let us consider the swapping system in which memory consists ofthe following hole sizes in memory order: 10KB, 5KB, 18KB, 6KB, 7KB, 12KB,15KB, 20KB. Which hole is taken for successive fragment requests of (a) 18KB, (b)5KB, (c) 18KB for the following policies: first fit, best fit, and worst fit? Specifyclearly what is the allocation of the fragment requests (a), (b) and (c) for each policy.3. Problem on Virtual Memory (25 Points) 3A. (15 Points) A process has four page frames allocated to it (All the following numbersare decimal, and everything is numbered starting from zero). The time of the last loadingof a page into each page frame, the time of last access to the page in each page frame, thevirtual page number in each page frame, and the referenced (R) and modified (M) bits foreach page frame are as shown in the table below (the times are in clock ticks from theprocess start at time 0 to the event – not the number of ticks since the event to thepresent). Virtual pagenumberPage frame Time loaded Timereferenced R bit M Bit2 0 60 161 0 11 1 130 160 1 00 2 26 162 1 03 3 20 163 1 1A page fault to virtual page 4 has occurred at time 164. Which page frame will have itscontents replaced for each of the following memory management policies? Explain whyin each case:(a) FIFO (b) LRU(c) Optimal (Use the following virtual page reference string before the page fault tovirtual page 4 occurred : 4,0,0,0,2,4,2,1,0,3,2)(d) How many page faults would occur if the working set policy with LRU were usedwith a window size of 4 (use the future virtual page reference string, starting before thepage fault to virtual page 4 occur 4,0,0,0,2,4,2,1,0,3,2). Start counting page faults withthe page fault of page 4.3B. (10 Points) Consider the following page table below. All numbers are decimal,everything is numbered starting from zero, and all addresses are memory byte addresses.The page size is 1024 bytes and the processor architecture is 32-bit. Virtual page # Valid Bit Reference Bit Dirty Bit Page frame #0 1 1 0 41 1 0 1 72 0 0 0 -3 1 0 0 24 0 0 0 -5 1 0 1 0a. (5 Points) Describe exactly how, in general, a virtual address generated by the CPU istranslated into a physical main memory address? Your answer should explain how theValid, Reference and Dirty bits are used or set. b. (5 Points) What physical address, if any, would each of the following virtual addressescorrespond to? (do not try to handle any page faults if any). Note that the addresses aredecimal addresses, not hexadecimal. addressesi. 1052ii. 2221iii. 54994. Problem on File Systems (25 Points) Consider the command line cat /var/log/log.0 /var/log/log.1 >> /var/log/mystuff/biglog4A. (3 Points) Briefly explain in English how the 'cat' command and '>>' redirection areused and their actions on the three files.4B. (10 Points) Calculate the precise amount of time (to the nearest 1/100th second)required to perform the above command. Your calculation should consider - I/O requiredto traverse directory and inode structure of each file; creating additional inodes andindirect blocks of inode pointers; reading the contents of the files; writing the contents ofthe files; updating last accessed time information on all inodes.Assume the following - /var is a mount point of a local hard disk with a block size of4096 bytes. The files 'log.0','log.1' and 'biglog' are initially 2^20 ,2^20 and 2^10 bytesrespectively. A pointer to a disk block requires 4 bytes. An inode has 10 direct entries, asingle indirect, a double indirect and a triple indirect entry.Only the 'cat' program and directory entries (names & inode pointers) of /var/ are initiallycached in memory. All other information requires a disk read. Assume that caching ismaximal, i.e., the least number of disk reads is performed (if there is an in memoryrepresentation the data is not re-read from disk) and no errors occur. The reading orwriting time for a single disk block is always 0.01 seconds (i.e., reading then writing thesame block requires 0.02s).4C. (12 Points) Let us consider the following shell commands on a local inode-based filesystem.cd /tmpmkdir subdirecho "hello" > subdir/file1ln -s subdir/file1 file2ln -s subdir/file1 file3ln subdir/file1 file4ln file4 file5chmod 744 file4touch file3rm file5chmod 000 subdira) How many disk


View Full Document

U of I CS 241 - System Programming

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download System Programming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view System Programming and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view System Programming 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?