Thursday, January 13, 2011

Process Thread Task

Process vs. Thread
  • Processes are typically independent, while threads exist as subsets of a process.
  • Processes have separate address spaces, whereas threads share their address space.
  • Processes carry considerate state information (Execution context: program counter, stack pointer, data registers; Code; Data; Stack), whereas multiple threads within a process share text/data segment.
  • Processes interact only through inter-process communication, whereas threads can directly communicate with other threads of their process.

C/C++ Library

Wiki: C POSIX Library

Wednesday, January 12, 2011

Memory Management

Understanding Memory - From University of Alberta
Virtual memory is an abstraction layer that the operating system uses to insulate the memory hardware.

Executing a program interactively at the shell's command prompt is a common way to create a new process. The new process is literally spawned, or forked, from the shell process. In this way, a process hierarchy is established, with the shell as parent and the new process as child.

Programs comprise executable statements and data declarations. Each datum has a property known as storage class that reflects its lifespan during program execution. A related property called scope characterizes the extent of a datum's visibility. Storage class and scope are assumed from the location of a datum's declaration, and determine its placement within virtual memory.

Compilers translate a program's executable statements into CPU instructions, and declarations of static data are translated into machine-specific data specifications. To create an executable file, the system linker aggregates the instructions and the data into distinct segments. All of the instructions go into one segment traditionally called text. Meanwhile, the data are arranged into two segments. One is called data, for the initialized static data and literal constants, and the other, bss, for the uninitialized static data.

When the ELF file is executed, the text and the two data segments are loaded into separate areas of virtual memory.

Instead of mapping individual bytes, the page table maps larger chunks of virtual memory called pages. The corresponding increment of real memory is called a page frame. Page size is architecture-specific and often configurable. It is always some power of two.

Linking a static library into a program integrates the library's text and data segments into the ELF program file.

Tuesday, January 11, 2011

Endianness

C++ General: What do 'ntohl()/ntohs()' and 'htonl()/htons()' actually do?
This family of functions convert between host byte order and network byte order. These functions should not be used when one simply wants to change endian-ness in a platform independent way.

C++ General: How do I convert between big-endian and little-endian values?

CodeProject: Basic concepts on Endianness

Wednesday, January 5, 2011

Graph Algorithm

Shortest Path Problem:
1. Bellman-Ford Algorithm: solves the single-source shortest-paths problem for weighted directed graphs in which edge weights may be negative. It can detect negative cycles and report their existence, but it can not produce a correct answer if a negative cycle is reachable from the source.
Wiki: Bellman-Ford Algorithm
2. Directed Acyclic Graph (DAG): relax the edges according to a topological sort of vertices. The application of this algorithm is to determine the critical path, which is a longest path through the DAG.
3.Dijkstra's Algorithm: solves the single-source shortest-paths problem for weighted directed graphs in which all edge weights are nonnegative.
Wiki: Dijkstra's Algorithm
Longest Path Problem: NP-complete problem.
Wiki: Longest Path Problem
For a DAG,
1) can be solved in polynomial time by negating the edge weights and running a shortest-path algorithm.
2) can be solved in linear time using dynamic programming via a topological sort.

Dynamic Programming

Wiki: Dynamic Programming
Algorithmist: Dynamic Programming
Dynamic Programming Practice Problem
Examples:
1. Longest Common Subsequence
    Wiki: Longest Common Subsequence
    Algorithmist: Longest Common Subsequence
2. Longest Increasing Subsequence
    Wiki: Longest Increasing Subsequence
    Algorithmist: Longest Increasing Subsequence
3. Longest Common Substring
    Wiki: Longest Common Substring
    WikiBooks: Algorithm Implementation/Strings/Longest Common Substring

Saturday, January 1, 2011