Specification of Hare and Tutle ------------------------------- Turtle() { while (not finish) { moveleg1(); moveleg2(); moveleg3(); moveleg4(); } } Hare() { while (Turtle is far behind) Sleep(for_a_while); RunLikeCrazy_A_bit(); } God() { wait for keyboard; choose hare or turtle from keyboard; reposition hare or turtle; } Report() { while (game not over) report positions of hare and turtle; /* use ncurses for graphics if you are ambitious, printf otherwise */ } Main() { loop { Tutle(); Hare(); God(); Report(); } until somebody wins; } Specification of Sleeping Barber Problem ---------------------------------------- A customer will not enter the shop if it is filled to capacity with other customers. Once inside, if no barber is free then the customer grabs a Filmfare if available or a S+G OS book otherwise (essentially sleeps). When a barber is free, the customer who has been reading Filmfare the longest is served and, if there are customers studying S+G OS (sleeping), the one who has been studying for the longest time now gets to read Filmfare. When a customer's hair-cut is finished, any barber can accept payment, but because there is only one cash register, payment is accepted for one customer at a time. The barbers divide their time between cutting hair, accepting payment, and sleeping in their chair waiting for a customer (they are not interested in either Filmfare or OS). No customer should sit on the lap of another (improper aggressive behaviour) and the barbers should be fair - if one barber is very fast or one of the customers is quite bald, then a customer who has only had a partial hair cut should not be evicted from his seat and made to pay, neither should the bald guy be restrained in his seat even though his hair cut is complete. Implement processes customer, barber and cashcounter and synchronize using the following semaphores. semaphore max_capacity = 20, filmfare = 4; semaphore barberchair = 3, barberfree = 3; /* intended usage of the above are obvious */ semaphore cust_ready=0,leavechair=0,payment=0,receipt=0; /*barber waits/sleeps on cust_ready till a customer is in the chair, barber waits on leavechair till customer gets up from the chair, cashcounter waits on payment for a customer to pay, customer waits on receipt for a receipt from the cashcounter */ semaphore finished[50]; /*initialized to 0. customer n waits on finished[n] until his haircut is complete. assume a maxm of 50 customers on a fine sunday morning */ /* anything else you may wish to define */ Problem No 1: ------------- 1. Expand the hare and turtle process descriptions and implement IPC solutions by defining cooperating processes. 2. First use fork() and execve() to create the processes and develop complete applications using the following LINUX IPC (message passing) mechanisms separately: (i) pipes (ii) FIFO files and (iii) message queues. 3. Develop the same applications using Linux pthreads (shared memory). Problem No 2: ------------- Implement one of the following using pthreads and semaphores you may either use linux posix compliant semaphores, or use semaphores built using pthreads mutex locks - see Appendix A of the last pthreads tutorial above. Make sure that your solution is free of deadlock and starvation. 1. hare and turtle 2. Dining philosophers. 3. The sleeping barber problem Problem No 3: ------------- 1. Implement an user level threads package. See the specs for Threads, scheduler and context switching 2. Implement the following applications on your threads package: 1. Bounded buffer producer consumer 2. Deadlock and starvation free dining philosophers 3. The sleeping barber problem of Minor 1 Use semaphores available in Linux for synchronization. 3. Implement your own semaphores as spin-lock critical sections. Implement semaphore wait and signal such that threads waiting on a semaphore do not busy wait. Instead, they should be blocked and placed in a queue associated with the semaphore to be made awake later with a signal. 4. Re-implement the applications using your own semaphores. Problem No 4: ------------- 1. Use Bochs (a free X86 emulator) to develop your own OS. Use OSKit to boot your machine (or emulator) in to protected mode and first run a "hello world" application. 2. Change the "hello world" application in to an init process that sets up the interrupt vector table and initializes the timer and the CPU registers and passes control to a scheduler. 3. Implement a round-robin preemptive scheduler and context switching. Initialize the timer appropriately and explicitly save the register contents during context switch (unlike the scheme used in Problem 3). 4. Port your semaphore implementation of Problem 3 on to your new OS and intregrate it with the new context switching mechanism. semaphores can now be implemented as spin-lock critical sections using compare and exchange. 5. Use a flat memory model. Use OSKit's malloc, printf etc. Do not use any external devices (including keyboard) except the monitor screen. 6. Re-implement the applications of Problem 3 in your new OS. Problem No 5: ------------- Write a comprehensive report on OsKit's memory management for the flat memory model of your OS which you have developed for problem 4. Note that segmentation cannot really be switched off on X86 architectures. In particular, elaborate on 1. How are the OsKit library functions linked with your code? 2. The role of the bootloader. Where exactly does it load your code (including functions and sub-routines) in the memory? 3. What all go in the reserved low memory segments? 4. Where is the interrupt vector table? 5. Where are the special data structures for memory management that OsKit may be creating? 6. Where are the data segments - stacks and heaps, anything you malloc, the kernel data structures? how are they managed?