ECE 391 Exam 2, Spring 2013
Tuesday, April 2nd
Copyright By PowCoder代写 加微信 powcoder
• Be sure that your exam booklet has 16 pages.
• Write your name at the top of each page.
• This is a closed book exam.
• You are allowed one 8.5× 11″ sheet of notes.
• The last few pages of the exam contain reference information and
scratch paper.
• Absolutely no interaction between students is allowed.
• Show all of your work.
• Don’t panic, and good luck!
Total 100 points
Page 3 10 points
Page 4 10 points
Page 5 5 points
Page 6 10 points
Page 8 15 points
Page 9 10 points
Page 10 10 points
Page 11 10 points
Pages 13-14 20 points
Problem 1 (25 points): Short Answers
Part A (3 points): Suppose a request is made for a large chunk of memory that exceeds the smallest page size
supported by the kernel. Give three reasons why it is beneficial for the memory allocator to provide either contiguous
page frames or a single large enough page, instead of randomly picking multiple (smaller) free page frames.
Part B (2 points): Any memory allocator for dynamic requests of various sizes from a common memory pool
(such as a buddy allocator) has to implement two core operations on that memory pool, one on allocation and one on
deallocation. What are they?
Part C (2 points): Explain why disabling interrupts is the only precaution necessary for protecting a critical
section that is shared between an application and an interrupt handler in the development environment for this class.
Part D (3 points): Give one reason interrupt chaining is useful.
Problem 1, continued:
Part E (2 points): Name one disadvantage AND one limitation of the EXT2 file system.
Part F (3 points):
Please fill-in the following sentence with the following terms: User Program, Interrupt Handler, System Call
Operating systems leverage special assembly linkage within the (A) and a particular calling convention to allow the
(B) to request the service of the desired (C).
Part G (2 points): Linux uses x86 segmentation in a very limited way. All processes in user mode use the same
pair of segments, user code segment and user data segment. Similarly, all processes in kernel mode use a pair of
segments, kernel code segment and kernel data segment. The Linux operating system effectively makes segmentation
a pass-through operation by the way it establishes those segments. Please write the base address (starting address) of
these four segments in Linux.
Part H (3 points): Virtual memory acts as a logical layer between the application memory requests and the
hardware Memory Management Unit (MMU). Please list three advantages of using virtual memory instead of sending
application memory addresses directly to the MMU.
Problem 1, continued:
Part I (2 points): In lecture, one of the solutions we came up with for connecting multiple devices to the single
interrupt pin was to connect all devices to an OR gate. Give two reasons why this solution is not used.
Part J (3 points): Explain why neither the master nor slave PIC alone has enough information to know what data
to send to the CPU during an INTA. For full credit, you must explain why that is the case for both PICs.
Problem 2 (10 points):
It is fairly common for FPGA’s to have larger memory storage standards than an x86-style 32-bit addressable memory.
One of your friends has designed a Memory-Management Unit for an x86-style architecture (byte-addressable) to deal
with translating a 36bit virtual address space into a 32bit physical address space. There is an x86 32-style 2-level
paging system (Page Directory→ Page Table→ Page) and each entry is 32 bits. The fields in the virtual address are
split evenly for use in indexing into the page directory, the page table, and the page itself.
Part A (2 points): How many entries are in the PD? in the PT?
Part B (2 points): What is the biggest possible page size? (Assume the Page Size Extension bit has been set)
Part C (2 points): If only 10 bits are used for options/modifiers in the PTE, what is the smallest possible page
granularity supported by a PTE?
Part D (2 points): Why is using the smallest granularity possible in the PTE a bad idea for this paging scheme?
Part E (2 points): Why would recycling this MMU scheme for a 32bit virtual address space (and zero-extending
by 4 bits) be a bad idea?
Problem 3 (15 points): Fill in the blanks on the next page with entries from the following list of possible tasks.
(note: you will not use every listed task and you may leave some blanks empt)
This particular system call has the following prototype:
long sys open (const char* name, int flags, int mode);
open wrapper system call
• Save all register values • Save all register values
• Restore all register values • Restore all register values
• Save callee-saved registers • Save callee-saved registers
• Restore callee-saved registers • Restore callee-saved registers
• Push the parameters to stack • Push the parameters to stack
•Pop the parameters off stack • Pop the parameters off stack
•Move the parameters into registers •Move the parameters into registers
• Call the system call function • Call the system call function
• Throw the 0x80 interrupt (int 0x80) • Throw the 0x80 interrupt (int 0x80)
• RET • RET
• IRET • IRET
• Return • Return
• Jump back to label • Jump back to label
• Push the system call number to stack • Call via given pointer to system call
• Pop the system call number off stack • Call via system call number and syscall table
• Push the system call pointer to stack • Push the return value to stack
• Pop the system call pointer off stack • Pop the return value off stack
•Move the system call number to a register • Ensure the return value is in a register
•Move the system call pointer to a register • Ensure the return value is on the stack
• Jump back to label
Problem 3, continued:
open wrapper (x86) system call (x86) sys open (C)
// note: assume all registers
are in use
// Open the desired file:
→ //Execute the desired action
//Done: ready to return
put return value in proper place
//Done: ready to return
//Done: ready to return
Problem 4 (10 points): Buddy allocator
Let the pages available to the kernel memory allocator be defined in terms of offset P starting from a base index. It
may be assumed that the page size is fixed. It may further be assumed that contiguous page indices refer to contiguous
page frames. Contiguous page frames are used to form blocks, whose sizes are determined by the parameter order.
The size of a block is 2order pages. Each block is identified by the offset of the first page in the memory block.
We use buddy system algorithm for managing page allocation and de-allocation requests. The buddy allocator has two
methods, shown below, and a current state given by the following table. The table lists the free blocks available at each
This function allocates contiguous pages.
Input: order: size of block as 2ˆorder pages
Output: On success returns page index allocated.
On failure to allocate a page, returns -1.
int pg_alloc(int order);
block_id: First page index of the block being freed
order: size of block as 2ˆorder pages
Output: Final order of the block after de-allocation is done.
int pg_free(int block_id, int order);
Order Free Block Ids
0 1, 3, 5, 8
1 6, 12, 16, 24
4 80, 112, 144
5 32, 160, 256
The following calls are invoked on this buddy allocator in sequence. Write the value returned by each function call
in the space provided next to that function call, and the final state of the buddy allocator in the table below, using the
same format as the initial table above.
1. pg alloc(8) Returns:
2. pg alloc(2) Returns:
3. pg free(22, 1) Returns:
4. pg free(96, 4) Returns:
5. pg free(128, 4) Returns:
Order Free Block IDs
Problem 5 (10 points): MP2 – ModeX
In MP2, you drew an image into the build buffer, then copied the entire screen area from the build buffer to the io-
mapped video memory. This only worked for the MP due to some subtleties with using a VM. In this question, you
will be taking advantage of the plane system of ModeX in order to draw a solid shape directly to video memory.
Implement the draw horizontal line function below using the following information:
• (x, y) is the leftmost coordinate of the line.
• length is the length of the line in pixels.
• Assume the line fits within the valid screen area.
• color is the palette index for the fill color of the line.
• SET MASK(x) will set the VGA plane mask based on the low 4 bits of x.
i.e. 0001 sets the VGA to write to plane 0, 1010 sets the VGA to write to plane 3 and 1
NOTE: there are 10 blanks for you to fill in
#define SCREEN_X_DIM 320
#define SCREEN_Y_DIM 200
#define SCROLL_X_WIDTH (SCREEN_DIM_X / 4);
static char *const mem_image; //points to the start of video memory
void draw_horizontal_line(int x, int y, int length, char color)
int end_x;
int start_plane, end_plane;
int start_addr, end_addr;
if(length <= 0) {
__________;
end_x = x + length - 1; //x coordinate of the last pixel
start_plane = __________; //plane for first pixel
end_plane = ____________; //plane for last pixel
start_addr = x / ____ + SCROLL_X_WIDTH * y; //address of first pixel
end_addr = end_x / ____ + SCROLL_X_WIDTH * y; //address of last pixel
if(start_addr == end_addr) { //draw line which doesn’t cross addresses
SET_MASK((0xf<
mem_image[start_addr] = _____;
SET_MASK(0xf<
mem_image[end_addr] = _____;
Problem 6 (10 points): PIC design and interface
For this problem you may assume the system uses two cascaded Intel 8259A PICs. You may also assume the defined
constants (i.e. EOI, MASTER 8259 PORT) are correct and defined elsewhere.
wrote your MP3 group’s send eoi function. Here is his code:
void send_eoi(uint32_t irq_num)
if (irq_num & 8) {
outb( (irq_num-8) | EOI, SLAVE_8259_PORT);
outb(irq_num | EOI, MASTER_8259_PORT);
Ben says his send eoi works, but he didn’t test it very thoroughly. When you test it you notice that after a while some
interrupts are no longer received. Provide a short answer for each of the following questions for full credit.
Part A (5 points): What is wrong with the function?
Part B (3 points):
Why does it only affect some interrupt lines?
Part C (2 points):
Which specific interrupt lines are affected?
Problem 7 (20 points): MP3 Filesystem
Consider the simplified file system described in your MP3 specification sheet (attached as a reference at the end of the
exam). You are now required to extend the given file system to allow writes. To keep things simple, you must use the
given constants and structs defined below and you are only required to implement a function that creates and writes to
a new file.
void write new file (const uint8 t* filename, const void* buf, int32 t filelength);
This function takes in a file name, a data buffer, number of bytes to write. write new file creates a new directory
entry at index 12. You then have to create a new inode for this file at index 24. Lastly, you have to create data blocks
for the file and write the contents of the buffer to the data blocks starting at index 36.
The following helper functions are to be written by you to aid in implementing write new file and for partial credit:
void create_dir_entry (const uint8_t* filename);
void create_inode (int32_t filelength);
void write_data_blocks (const void* buf, int32_t filelength);
Things you may assume:
• All memory is statically allocated for you already to create this new file.
• Directory entry at index 12 is the next free directory entry index.
• Inode 24 is the next free inode index and the first data block starts right after the created inode(s) for the new file.
• Similarly, data block index 36 is the next free data block index and data is written to data blocks contiguously.
• The new file will not take up more than one inode.
• Arguments to your functions will be valid.
// Variables:
bootblock_t* Fs_start //starting address of file system
// Constants:
#define BLOCK_SIZE 4096
// Library functions:
void* memcpy(void* dest, const void* src, uint32_t n);
int8_t* strcpy(int8_t* dest, const int8_t* src);
// Directory entry structure
typedef struct dentry {
int8_t filename[32];
int32_t filetype;
int32_t inode;
uint8_t de_reserved[24];
} dentry_t;
// Boot block structure
typedef struct bootblock {
int32_t dir_ent_number;
int32_t inode_number;
int32_t data_block_number;
uint8_t bb_reserved[52];
dentry_t dir_ent_table[63];
} bootblock_t;
// Inode structure
typedef struct inode {
int32_t filelength;
int32_t data_block_table[1023];
} inode_t;
Problem 7, continued:
Write your code here. Aside from the ones we already gave you, STATE ANY ASSUMPTIONS!
* create_dir_entry:
* DESCRIPTION: this function creates a new directory entry at index 12.
* INPUTS: filename: name of new file
* OUTPUTS: None
* RETURN VALUE: Void
void create_dir_entry (const uint8_t* filename)
* create_inode:
* DESCRIPTION: this function creates new inode(s) at index 24.
* INPUTS: filelength: length of new file
* OUTPUTS: None
* RETURN VALUE: Void
void create_inode (int32_t filelength)
Problem 7, continued:
* write_data_blocks:
* DESCRIPTION: this function creates new datablock(s) at index 36.
* INPUTS: buf: pointer to a buffer that holds contents of new file
* filelength: length of new file
* OUTPUTS: None
* RETURN VALUE: Void
void write_data_blocks (const void* buf, int32_t filelength)
* write_new_file:
* DESCRIPTION: this function creates and writes to a new file. This involves
* creating a directory entry, inode(s), and data block(s) in the file system.
* INPUTS: filename: name of new file
* buf: pointer to a buffer that holds contents of new file
* filelength: length of new file
* OUTPUTS: None
* RETURN VALUE: Void
void write_new_file (const uint8_t* filename, const void* buf, int32_t filelength)
(Scratch paper. Remove if desired. Contents of this page will not be considered during grading.)
You may tear off this page to use as a reference
MP3 Filesystem
File System Utilities: The figure below shows the structure and contents of the file system. The file system memory is
divided into 4 kB blocks. The first block is called the boot block, and holds both file system statistics and the directory
entries. Both the statistics and each directory entry occupy 64B, so the file system can hold up to 63 files. The first
directory entry always refers to the directory itself, and is named “.”, so it can really hold only 62 files.
index nodes (inodes) data blocks
block # dir. entries
52B reserved
64B dir. entries
# inodes (N)
# data blocks (D)
24B reserved
length in B 4B
0th data block #
1st data block #
absolute block numbers (4kB per block)
Each directory entry gives a name (up to 32 characters, zero-padded, but not necessarily including a terminal EOS or
0-byte), a file type, and an index node number for the file. File types are 0 for a file giving user-level access to the
real-time clock, 1 for the directory, and 2 for a regular file. The index node number is only meaningful for regular files
and should be ignored for the RTC and directory types.
Each regular file is described by an index node that specifies the file’s size in bytes and the data blocks that make up
the file. Each block contains 4 kB; only those blocks necessary to contain the specified size need be valid, so be careful
not to read and make use of block numbers that lie beyond those necessary to contain the file data.
8259A Master-Slave PIC configuration
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com