Saturday 18 June 2011

Software engineering

  • Algorithms for Recovery and Isolation Exploiting Semantics. Recovery.
  • Unicode Collation. Provides a standard way to put names, words or strings of text in sequence.
  • CHS conversion. Converting between disk addressing systems.
  • Cyclic redundancy check. Calculation of a check word.
  • Parity control. Simple/fast error detection technique. Is a number even or odd?

Memory allocation

  • Boehm garbage collector. Conservative garbage collector.
  • Buddy memory allocation. Algorithm to allocate memory such that fragmentation is less.
  • Generational garbage collector. Fast garbage collectors that segregate memory by age.
  • Mark and sweep.
  • Reference counting. Simple memory manager that counts links to data and reclaims the space when the count is zero.

Distributed systems

  • Lamport ordering. A partial ordering of events based on the happened-before relation.
  • Snapshot. A snapshot is the process of recording the global state of a system.
  • Vector clocks. A total ordering of events.
  • Marzullo. Distributed clock synchronization.
  • Intersection. Another clock agreement algorithm.

Operating systems algorithms

  • Banker. Algorithm used for deadlock avoidance.
  • Page replacement. Selecting the victim page under low memory conditions.
  • Bully. Selecting new leader among many computers.

Disk scheduling algorithms.

  • Elevator. Disk scheduling algorithm that works like an elevator.
  • Shortest seek first. Disk scheduling algorithm to reduce seek time.

Process synchronisation algorithms.

  • Peterson. Allows two processes to share a single-use resource without conflict, using shared memory for communication. Can be generalized.
  • Lamport's Bakery algorithm. Improve the robustness of multiple thread-handling processes by means of mutual exclusion.
  • Dekker. Another concurrent programming algorithm, as the Peterson's one.