• Homework extension

    September 25, 2006

    Homework regarding Heapsort was posted late. Since it was posted Sunday afternoon, whereas it should have been posted Friday afternoon, the due date is extended until Monday, Oct 2.

  • Comparing full precision integers

    September 22, 2006

    The Linux operating system keeps a tick count in a variable called jiffies. Use of this term for clock ticks seems to be strongly associated with Linux, however, I don’t know if it is a Linus original. In 32 bit Linux, jiffies overflow every 49.7 days, so comparing time values in jiffies requires care. The [...]

  • Kernel coding project

    September 21, 2006

    There is an issue of getting syscall to work, to invoke the newly installed system call. The book suggests using __syscall0, which is a macro which expands out to a function during cc preprocessing. This has worked for us in the past, but newer kernels (2.6.13) seem not to have this symbol anymore, and instead [...]

  • Heapsort

    September 20, 2006

    We have been learning about heapsort. A Heap is an array with elements arranged in Heap Order. A heap supports fast selection and removal of an element of least (or greatest) priority among the elements stored in the heap. Heapsort accomplishes sorting by placing all the elements to sort into a heap, using the element’s [...]

  • Synchronization

    September 20, 2006

    Chapters 8 and 9 of Love’s Linux Kernel book provide an excellent reference for synchronization in theory as well as the particulars of synchronization and locking primitives in the Linux kernel. Four synchronization topics were presented in class: Peterson’s algorithm: how to do synchronization with minimal assumptions. Spin-locks: how to create a synchronization primitive using [...]

  • Scheduling, continued

    September 20, 2006

    You have been assigned to write about the differences between Windows NT scheduling and Linux scheduling, based on the book readings. In addition to dynamic priorities for normal processes, both Windows and Linux have a Real-time class. Real-time processes have deadline requirements. Other operating systems also have a Batch class which have very low priority, [...]

  • Scheduling

    September 13, 2006

    Processes receive cpu time by the decision of the scheduler. A good scheduling algorithm is immensely important to the sucess of an operating system. Different operating systems have different approaches, and it noticibly impacts the character and quality of the system. To better recognize the requirements of the decision, processes are divided into two classes: [...]

  • Big Oh notation

    September 13, 2006

    Big-Oh and Little-Oh are analogous to inequality of numbers, but defined for functions. If one writes g=O(f), this means g and f are functions, and f is a bigger function than g, or equal; if one writes g=o(f), this means g and f are functions, and f is definitely bigger than g, and not equal [...]

  • Problem 1-1 time extension

    September 8, 2006

    There has been some confusion about the first assignment, and many students did not do problem 1-1. I have extended until this Friday, 15 September for students to hand in this one problem in the first assignment. The numbering of exercises and problems in the textbook requires a bit of care. Exercises are at the [...]

  • Loop Invariants

    September 8, 2006

    The second of three tools in the analysis of algorithms is the loop invariant. We discussed in detail the loop invariant presented in the book for Insertion Sort. The loop invariant is a kind of assertion. An assertion is a logical statement, such as: the elements of array A are all distinct (that is, A[i]==A[j] [...]

Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org