15-410 Self-assessment ExerciseAbout the self-assessmentThe prerequisite for 15-410, Operating Systems Design & Implementation, is 15-213, Introduction to Com-puter Systems. The latter is a sort of “Computer Architecture for Programmers” class, covering topics suchas disks, caches, virtual memory, threads, and assembly language. It forms a solid basis for courses such asOS and Computer Architecture.This self-assessment exercise, based on questions from a recent 15-213 final exam, is designed to provideprospective students with an understanding of the core 213 skills which will be used in 410. Projects 0and 1 will be written mostly in C, with small scraps of x86 assembly language. Project 2, a thread library,will require a firmer understanding of assembly language and the relationship between a sequence of Ccode and the corresponding assembly language. In addition, Project 2 will naturally require (and develop)understanding of concurrency. These skills will then be used in Project 3 to write a small operating system.Again, this will be mainly in C, but critical parts will be in assembly language.Thus, the questions in this exercise focus on decoding simple assembly language sequences, C memorylayout and pointer arithmetic, and concurrency. This format is artificial in the sense that we will not askyou to demonstrate mastery of this material in an exam setting on the first day of class. However, byapproximately three weeks into the semester we will be relying on all of these skills to the extent thatcompleting these three questions should take well under an hour. For example, both the thread library andthe operating system kernel are responsible for building a standard C runtime environment from underlyingprimitives. In order to debug sequences of C code which are correct but execute incorrectly you will needto translate between C and assembly language.“Taking the test”If you had 15-213, this is a good opportunity to dust off your textbook and review parts of it, primarilyChapter 3. You might want to also briefly look over your malloc() lab code.If you haven’t had 15-213, but you have programmed in C and some processor’s assembly language, youmay wish to consult either the 15-213 text or Intel’s Instruction Set Reference, available locally at http://www.cs.cmu.edu/˜410/doc/intel-isr.pdf (keep in mind that the Intel document specifiesoperands in the opposite order from the GNU assembler, gas, which we will be using).If you haven’t programmed in C (as opposed to C++ or Java), or haven’t been exposed to assembly languagefor any processor, these are serious issues. We recommend you take 15-213 or 15-441 before 15-410.For this exercise to end with a meaningful result, you must answer the questions. In other words, work onthe problems until you have an answer for each one which you are 95% confident is correct, then “gradeyourself” in terms of how many hours it took. Do not skim each problem and tell yourself, “Oh, that is aproblem about Topic X, which I basically understand. I could answer it in NN minutes if I had to.” If youhave not completed 15-213, we will collect and look over your self-assessment answers in the first weekof the semester. Finally, you must work on your own. The purpose of this exercise is to determine howwell prepared you are for the class, not the preparation levels of your friends or somebody who might beyour project partner. Having these few problems explained to you can’t stand in for a missing semester-longprerequisite class!Page 1 of 9Problem 1. (9 points):In this problem you will be given the task of reconstructing C code based on the declarations of C struc-tures and unions provided below and the assembly code on the next page generated from the C code by aLinux/IA32 C compiler.struct s1 {char a[3];union u1 *b;int c;};struct s2 {struct s1 d;struct s1 *e;struct s2 *f;double g;int h[4];};union u1 {int i;struct s2 j;struct s1 *k;};Page 2 of 9For each IA32 assembly code sequence below on the left, fill in the missing portion of the corresponding Csource line on the right.A proc1:pushl %ebpmovl %esp,%ebpmovl 8(%ebp),%eaxmovl 4(%eax),%eaxmovl 40(%eax),%eaxmovl %ebp,%esppopl %ebpretint proc1(struct s1 *x){return x->___________________ ;}B proc2:pushl %ebpmovl %esp,%ebpmovl 8(%ebp),%eaxmovl 32(%eax),%eaxmovl %ebp,%esppopl %ebpretint proc2(struct s2 *x){return x->___________________ ;}C proc3:pushl %ebpmovl %esp,%ebpmovl 8(%ebp),%eaxmovl (%eax),%eaxmovl 4(%eax),%eaxmovl (%eax),%eaxmovl %ebp,%esppopl %ebpretint proc3(union u1 *x){return x->___________________ ;}Page 3 of 9Problem 2. (6 points):This problem tests your understanding of pointer arithmetic and pointer dereferencing.Harry Q. Bovik, as part of his 15-213 course work, was asked to write a dynamic memory allocator(malloc(), free(), etc.). Since you have already completed 15-213, you have been pressed into serviceas a teaching assistant. Harry is having trouble figuring out how to write a C macro to access part of his datastructure, and he is asking you for help.The following is a description of Harry’s memory-block structure:HDR ID STRING PAYLOAD FTR• HDR - Header of the block (4 bytes)• ID STRING - Unique ID string (8 bytes)• PAYLOAD - Payload of the block (arbitrary size)• FTR - Footer of the block (4 bytes)The size of the payload of each block is stored in the header and the footer of the block. Since there is an 8byte alignment requirement, the least significant of the 3 unused bits is used to indicate whether the block isfree (0) or allocated (1). Harry has also decided to uniquely label each block with a string stored right afterthe header of the block. The size of this ID field is 8 bytes.For this problem, you can assume that:• sizeof(int) == 4 bytes• sizeof(char) == 1 bytes• sizeof(short) == 2 bytes• The size of any pointer (e.g. char*) is 4 bytes.Page 4 of 9Your task is to help Harry figure out and circle clearly which of the following definitions of the macroGET ID will cause print block() to output the string that is stored in the ID STRING field. Theremay be multiple macros that are correct, so be sure to circle all of them.Also, assume that the block pointer bp points to the first byte of the payload./* Harry Q. Bovik’s print_block() functionRefer to this function in order to figure outthe context in which the GET_ID macro is used.*/void print_block(void *bp){printf("Found block ID: %s\n", GET_ID(bp));}/* A. */#define GET_ID(bp) ((char
View Full Document
Unlocking...