Problem Set 2 Harvard Extension School CSCI E-92: Principles of Operating Systems Fall 2025 Due: October 5, 2025 at Midnight ET (Eastern Time) Total of 171 Points 1. (10 Points) Memory Management. The following program is run on two different computers with the same command line arguments. #include int main(int argc, char *argv[]) { printf("%d %d\n", *(int *)argv[1], *(int *)argv[2]); return 0; } On computer A, which has an Intel x86 processor, it produces this output: 1701998445 1936942444 On computer B, which is a Motorola 68000, it produces this output: 1836020325 1818588019 a. (5 Points) Why does the same program produce different outputs on these two machines? What is different about these computers? Exactly how does this difference affect the output? b. (2 Points) What command line was used in both cases? c. (3 Points) If the following program was run with the same command line arguments as for the program above, on which of these computers would the printf output be correct (i.e., the printf output would be a true statement)? #include int main(int argc, char *argv[]) { int before = *(int *)argv[1] < *(int *)argv[2]; printf("\"%s\" is %s \"%s\" in alphabetical order\n", argv[1], before ? "before" : "not before", argv[2]); return 0; } 2. (12 Points) Memory Allocation. Consider a swapping system in which memory consists of the following hole sizes in memory order: 10 MB, 4 MB, 20 MB, 18 MB, 7 MB, 9 MB, 12 MB, 15 MB. Which hole is taken for successive segment requests of (a) 12 MB (b) 10 MB (c) 9 MB for first fit? Now repeat the question for best fit, worst fit, and next fit. Tanenbaum 5/e 3.3 (Tanenbaum 4/e 3.4, Tanenbaum 3/e 3.4, Tanenbaum 2/e 4.5) (3 Points) First fit for request (a), followed by (b), then (c). (3 Points) Best fit for request (a), followed by (b), and (c). (3 Points) Worst fit for request (a), followed by (b), and (c). (3 Points) Next fit for request (a), followed by (b), and (c). 3. (8 Points) Page Replacement Algorithms. A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as shown below (the times are in clock ticks): --------------------------------------- | Page | Loaded | Last access | R | M | |------|--------|-------------|---|---| | 0 | 126 | 280 | 1 | 0 | | 1 | 230 | 265 | 0 | 1 | | 2 | 140 | 270 | 0 | 0 | | 3 | 110 | 285 | 1 | 1 | --------------------------------------- Tanenbaum 5/e 3.35 (Tanenbaum 4/e 3.36, Tanenbaum 3/e 3.28, Tanenbaum 2/e 4.29) (2 Points) Which page will NRU replace? (2 Points) Which page will FIFO replace? (2 Points) Which page will LRU replace? (2 Points) Which page will second chance replace? 4. (100 Points) Memory Management. Using the C programming language, write code to implement memory allocation and deallocation. Externally there should be three visible interfaces: "myMalloc", "myFree", and "myFreeErrorCode". The myFreeErrorCode function is to be used only by your shell and for testing purposes. All other programs will use myMalloc and myFree. The myMalloc function is declared as taking a parameter of type size_t as its only parameter and returning a pointer to void, as follows: void *myMalloc(size_t size); The "size" parameter is the size in bytes of the storage needed by the caller. The myMalloc function should allocate an appropriately sized region of memory and it should return a pointer to (i.e., the address of) the first byte of that region. If the storage cannot be successfully allocated for any reason, the function should return a NULL pointer (i.e., the value 0). If a request is made to allocate 0 bytes of memory, the function should return a NULL pointer. The allocated memory is not to be initialized. Your implementation must allow the "size" to be up to but not including 128M bytes less some overhead for structs to manage the storage (that is, less than (134,217,728-overhead structs)). This allows the size in bytes to be represented by 27 bits. The pointer returned by myMalloc should always point to a region of memory that starts on an 8-byte (double-word) boundary for the NXP K70. This allows a user to place any data at the beginning of a myMalloc region -- including data that requires a double-word boundary. This requirement may cause you to round-up the amount of memory requested by the user so that the alignment requirement is satisfied. The myFree function is declared as taking a pointer to void as its only parameter and not returning anything, as follows: void myFree(void *ptr); The "ptr" parameter is a pointer to a region of memory previously allocated by the myMalloc function. The myFree function deallocates the entire region of memory pointed to by the parameter. If the value of the parameter is NULL, the call has no effect. If the "ptr" parameter does not point to the first byte (i.e., does not have the same value that was returned from a call to myMalloc) of a *currently* allocated region of memory, the call should have no effect. A region of memory allocated by the myMalloc function should only be deallocated once. Once a region of memory has been deallocated by calling myFree, the storage should not be accessed in any way by the calling program. The myFree function should make the freed storage be available for a future call of myMalloc. In addition to implementing the myFree function that conforms to the standard declaration in for the free function, you should implement a myFreeErrorCode function declared as follows: int myFreeErrorCode(void *ptr); The behavior of myFreeErrorCode is the same as for myFree except that myFreeErrorCode returns an int to indicate success or failure of the storage deallocation request. Error returns might include: (1) success, (2) attempt to free storage at an invalid block address, (3) attempt to free storage that is not currently allocated, and (4) attempt to free storage owned by a different PID. You can add additional error return codes if appropriate for your implementation. Your myFree function may simply invoke myFreeErrorCode and ignore its return value. Your program should be written in two modules (files). One should contain the main program and any functions necessary to test the myMalloc, myFree, and myFreeErrorCode functions. The other should contain the myMalloc, myFree, and myFreeErrorCode functions and any other functions needed by your implementation of myMalloc, myFree, and myFreeErrorCode. Part two of this Problem Set has more information about the testing performed by the main program. Your program should run on our class' cscie92.dce.harvard.edu instance using the "gcc" GNU C compiler. However, you should write your code so that it is portable to the NXP/Freescale ARM platform. This portability will be achieved by having your program on the cscie92.dce.harvard.edu instance allocate a 128M byte region of memory using the Unix malloc system call and then perform memory allocation and deallocation within that 128M byte region of memory. When running on the real hardware platform, the region of memory from which allocation will occur will be defined by variables or constants in the code. Your code should be written so that it can be relatively easily ported to a system where the basic C types have different sizes than on the cscie92.dce.harvard.edu instance. This can be accomplished by using sizeof, typedef, #define, and const syntactic elements in your program. When your code is ported to the NXP/Freescale ARM platform and is running under your operating system, you will need to maintain information that designates which process performed the myMalloc call. That is, your internal data structure that maintains information about allocated regions of memory will need to include the identity of the process, or PID, that allocated the storage. Your implementation must support at least 128 distinct PIDs. Only the process that allocated a particular region of memory should be allowed to successfully deallocate that region using myFree or myFreeErrorCode. In preparation for later problem sets, in this problem set you should allocate a single PCB (Process Control Block) struct that contains a place-holder PID (Process ID) number. The PID in the PCB should be set to zero for now. The PCB should be pointed to by a global file-scope variable named, say, currentPCB. You should implement an accessor function named getCurrentPID that returns the PID contained in the PCB of the current process (i.e., in the PCB pointed to by currentPCB). For now, because our PID is always zero, it will always return zero. The value returned by this function will be used to tag each region of storage when that region is allocated via myMalloc. In later problem sets, you will be allocating multiple PCBs. Keep in mind that you may need to maintain bookkeeping information in the 128M byte region of memory in order to be able to implement the myMalloc, myFree, and myFreeErrorCode functions efficiently. It is perfectly acceptable for your algorithm to effectively allocate more space than the caller requested and use the beginning of that space for bookkeeping information and pointers, etc. The code that you write should contain ample documentation in the three forms we discussed in class: (1) comments attached to lines of code or to code blocks to describe difficult to understand constructs or local algorithms, (2) interface specification documentation as a prefix to each function to describe the types and meanings of each parameter and the return value to the function and any side effects the function may have (including access or changes to global variables, I/O, manipulation of heap and data structures, etc.), and (3) an overview document separate from the program which gives information on the purpose, solution (algorithm), and use of the module. You should always follow code programming practice, including: o Always use meaningful names for functions, variables, and constants. o Do not use magic numbers. All constants should be declared with initialization. o Constant names should be written entirely in upper case with underscores separating words. Do not begin constant names with an underscore. o Variables should be written entirely in lower case except that the first letter of words other than the first should be capitalized. Do not begin variable names with an underscore. o Types (typedef'ed) should begin with an uppper case letter and the first letter of all other words should be capitalized as well. o All code should modular and well structured. For the memory allocation routines you will be implementing for this assignment, you will need to find an appropriate compromise between code that efficiently utilizes the storage being allocated and freed and one in which the myMalloc, myFree, and myFreeErrorCode functions are fast. Clearly there are many algorithms that solve the memory allocation problem. We are not going to specify an required algorithm, but if you are looking for ideas, take a look at Section 3.2.3 in 5/e (Section 3.2.3 in 4/e & 3/e) (Section 4.2.1 in 2/e) concerning Memory Management with Bitmaps on pages 188 to 189 in 5/e (pages 190 to 191 in 4/e) (pages 184 to 185 in 3/e) (pages 199 to 200 in 2/e) of Tanenbaum; Section 3.2.3 in 5/e (Section 3.2.3 in 4/e & 3/e) (Section 4.2.2 in 2/e) concerning Memory Management with Linked Lists on pages 190 to 192 in 5/e (pages 192 to 194 in 4/e) (pages 185 to 187 in 3/e) (pages 200 to 202 in 2/e), and in Section 10.4.3 see the Buddy Algorithm described on pages 752 to 753 in 5/e (pages 761 to 763 in 4/e) (pages 766 to 767 in 3/e) (pages 721 to 722 in 2/e). Remember that your code will *not* be graded solely on correctness. 5. (20 Points) Memory Management Performance. Add to the module containing your myMalloc, myFree, and myFreeErrorCode functions a new function named "memoryMap" which outputs to stdout a map of all used and free regions in the 128M byte region of memory. By running a succession of memory allocation and deallocation requests with calls to memoryMap after each call to a memory management routine, demonstrate that your memory allocation algorithm is allocating memory from an appropriate free memory region. Justify the choice of your algorithm using data from the textbook (e.g., first fit vs. next fit vs. best fit vs. worst fit vs. quick fit, etc.) and from other sources to show why you chose the algorithm that you implemented. That justification should show why the algorithm you chose is a good compromise between efficient storage utilization and speed. 6. (10 Points) Additional Shell Commands. Add five new commands to your shell. These commands are malloc, free, memorymap, memset, and memchk. The malloc command should accept a single argument which is the number of bytes of memory to be allocated. The argument should be able to be specified either as a decimal unsigned integer constant (of arbitrary length), an octal unsigned integer constant (indicated by a prefix of 0 not followed by x or X followed by an arbitrary length octal constant), or as a hexadecimal unsigned number (indicated by a prefix of 0x or 0X followed by an arbitrary length hexadecimal constant). The alphabetic hexadecimal digits should be able to be specified in either upper or lower case. The malloc command should call myMalloc and output to stdout the address in hexadecimal of the storage allocated (i.e., the return value of myMalloc) if the call is successful. The hexadecimal address should be output with a prefix of 0x followed by the hexadecimal constant followed by a newline character. If the call is not successful, it should output an appropriate error message to stderr. The free command should accept a single argument which is the address of a region of memory previously allocated using myMalloc and then call myFreeErrorCode to deallocate that region of memory. The address should be able to be specified either as a decimal unsigned integer constant (of arbitrary length), an octal unsigned integer constant (indicated by a prefix of 0 not followed by x or X followed by an arbitrary length octal constant), or as a hexadecimal unsigned number (indicated by a prefix of 0x or 0X followed by an arbitrary length hexadecimal constant). The alphabetic hexadecimal digits should be able to be specified in either upper or lower case. After the call returns, a message should be output to stdout indicating the success or failure code returned by myFreeErrorCode. The memorymap command should accept no arguments. It will call memorymap to output the map of both allocated and free memory regions. For each block, the values shown by memorymap should be (1) whether the block is free or allocated, (2) if allocated, the PID, (3) if free, the size of the free space after the block header; if allocated, the rounded-up size requested by and allocated to the user (i.e., not including the size of the header), and (4) address of the memory after the block header; if allocated, this is the address returned to the user. The memset command is used to initialize every byte in a range of memory addresses to a specified value. The memset command should accept three arguments. The first is the beginning address of an allocated area of memory, the second is the value to which each byte in the specified memory will be set, and the third is the length (in bytes) of the specified memory. Each argument should be able to be specified either as a decimal unsigned integer constant (of arbitrary length), an octal unsigned integer constant (indicated by a prefix of 0 not followed by x or X followed by an arbitrary length octal constant), or as a hexadecimal unsigned number (indicated by a prefix of 0x or 0X followed by an arbitrary length hexadecimal constant). The alphabetic hexadecimal digits should be able to be specified in either upper or lower case. Ensure that the arguments are all within range for their intended usage (i.e., the "beginning address" must lie within the currently allocated memory from some myMalloc call, the "byte value" must be within range for a byte, and the "size" when added to the "beginning address" must cause all addresses to lie within the currently allocated memory from a single myMalloc call). For memset, also ensure that the PID associated with the memory block is the same as the currently processes' PID. There is no output from memset if memset is successful. memset should output any errors to stderr. The memchk command is used to validate that every byte in a range of memory addresses is set to a specified value. The memchk command should accept three arguments. The first is the beginning address of an allocated area of memory, the second is the value that each byte in the specified memory should contain, and the third is the length (in bytes) of the specified memory. Each argument should be able to be specified either as a decimal unsigned integer constant (of arbitrary length), an octal unsigned integer constant (indicated by a prefix of 0 not followed by x or X followed by an arbitrary length octal constant), or as a hexadecimal unsigned number (indicated by a prefix of 0x or 0X followed by an arbitrary length hexadecimal constant). The alphabetic hexadecimal digits should be able to be specified in either upper or lower case. Ensure that the arguments are all within range for their intended usage (i.e., the "beginning address" must lie within the currently allocated memory from some myMalloc call, the "byte value" must be within range for a byte, and the "size" when added to the "beginning address" must cause all addresses to lie within the currently allocated memory from a single myMalloc call). For memchk, also ensure that the PID associated with the memory block is the same as the currently processes' PID. If all bytes within the specified region contain the "byte value," then the memchk command should output "memchk successful". If any byte within the specified region does *not* contain the "byte value," then the memchk command should output "memchk failed". memchk should output any other errors to stderr. Remember that your shell should check that the appropriate number of arguments are specified on the command line for each command. If exactly one argument is needed, the shell needs to guarantee that only one argument -- no more and no less -- is specified. The same is true if no arguments are appropriate for a command (i.e., the shell should guarantee that no arguments have been specified). Also, ensure that there are no unparsed character remaining on the command line after the last argument. Use these shell commands to ensure that your implementations of myMalloc, myFree, and myFreeErrorCode are correct. It is imperative that these functions work absolutely correctly before you use them throughout your operating system. The memset and memchk commands allow you to initialize and check the contents of malloc'ed storage. You are able to use the functions strtol, strtoul, strtoll, and/or strtoull from stdlib.h in your solution for this and all future problem sets. 7. (1 Point) Using myMalloc and myFree in your Shell. After you are comfortable that your myMalloc, myFree, and myFreeErrorCode functions are working correctly, convert your shell to use myMalloc instead of the system malloc, and myFree instead of the system free. 8. (10 Points) NXP/Freescale K70 Programming. Establish the NXP/Freescale K70 Special Edition CodeWarrior for Microcontrollers 11.1 programming environment on an appropriate Windows computer or in a Windows VM. When building this project under CodeWarrior, specify "No I/O" under "I/O Support" in the "Language and Build Tools Options" screen. Write a C program for the NXP/Freescale K70 Tower Kit that flashes the four LEDs using non-interrupt driven output. After your program completes its initialization, the Orange LED should be on and all the other LEDs should be off. Each time pushbutton SW1 is depressed, the lit LED will rotate one position to the Yellow LED (i.e., only the Yellow LED will be lit after a single depression of SW1). The next time pushbutton SW1 is depressed, only the Green LED will be illuminated. The next time pushbutton SW1 is depressed, only the Blue LED will be illuminated. Then, the process starts again the next time pushbutton SW1 is depressed (i.e., only the Orange LED will be illuminated). The rotation should happen on the pressing of the button (not on the releasing of the button). In order to make sure that the LEDs rotate only a single position each time SW1 is pressed, ensure that: (1) you wait for the pushbutton to be released before another button press could cause the LEDs to rotate and (2) you delay for a short while after you notice that the pushbutton has been pressed and after you notice that the pushbutton has been released to eliminate contact bounces in the pushbutton. Without these brief delays spurious button presses or releases may be detected. Try to make the delays as short as possible so that the pushbutton is responsive to the user's actions without exhibiting any spurious behavior. Last revised 3-Aug-25