how to prevent output from getting interleaved

If an application only has one process and one thread, that is fine, there will be no competition to print information, which goes to stdout.
But what if there is one process but multiple threads? It is fine to use a single printf to print whatever you want, and that will not get interleaved with information printed by other threads. Below is an example.

void ThreadFn() {
    while (true) {
       printf("This is first info\nThis is second info\n");
       printf("This is third info\n");
   }
}

For the example above, you can always see a first info is followed by a second info, but may not followed by a third info. As far as we use a single printf, we are safe to guarantee that it is in integrity. However, information printed by more that one printf is vulnerable to get interleaved. The reason is in the implementation of printf, when it want to write to stdout, there is a line buffer(of course you can set it to unbuffered mode, but that is unusual). Multiple threads will use the same buffer for the same file, like stdout. To make sure the access to the buffer is thread-safe, it is considered by libraries to be a critical section which is protected by a mutex. Only up to one thread can access the buffer at a time. So the content written by a single printf is copied to the buffer in a single access to the buffer. But for two printf, the thread should apply for the mutex and access buffer more than once, there may be other thread accessing the buffer between two printf.

Then what about multiple processes? There is no synchronization mechanism between multiple processes for printing. When a process calls printf, the content goes to a buffer, when the buffer is full, it is dumped to the terminal/file by write/writev system call. There is no guarantee of the buffer size or how the buffer content will be dumped. To dump the buffer, some libraries may dump constant size at a time, others may dump all at once. So to guarantee integrity of information printed, we'd better call write/writev system call directly when multiple processes is getting involved. Below is an example.

void ProccessFn() {
   ...
   int nwrite = strlen(buf);
   char* p = buf;
   while (nwrite > 0) {
      int written = write(fileno(stdout), p, nwrite);
      if (written == -1) {
          if (errno != EINTR) {
             perror("write");
             break;
          }
      } else {
          nwrite -= written;
          p += written;
      }
   }
}

use popen to implement single direction communication between two processes

popen() is a posix api to implement single direction communication between two processes. It is suitable for the following conditions: 1. create a subprocess and read its standard output. 2. create a subprocess and write to its standard input.
I think it is something between system() and pipe() plus fork/exec. With system(), you can only start a child process and wait for the termination of child process. With pipe/fork/exec, as it is a little complex, I will show the typical usage below:

MainProcessFn() {
  int pipe_fd[2];
  pipe(pipe_fd);
  int pid = fork();
  if (pid == 0) {
     close(pipe_fd[0]);  // close read side
     dup2(pipe_fd[1], 1); // dup to stdout
     close(pipe_fd[1]);
     exec("some command");
  } else {
     close(pipe_fd[1]) // close write side
     FILE *fp = fdopen(pipe_fd[0], "r");
     // read from child process's standard output.
  }
}

As we can see, we can do bidirectional communication between two processes with pipe. We can only do unidirectional communication with popen, while the benefit is simpler code.

MainProcessFn() {
  FILE* fp = popen("some command", "r");
  // read from child process's standard output.
  pclose(fp);
}
With pclose, we can wait for the termination of child process, and get the exit status. In fact, popen/pclose is just a library api implemented based on system calls like pipe/fork/exec/waitpid, but just more convenient to use.

One way to realize parallelism

When we want to take benefits from multiprocessors, or just multitasking operating systems, we have to write multi-threads or multi-processes system. I met with such a condition before.
What I need to do is to spawn many processes in one process, each process does a small piece of job, gives feedback to the main process. There are about 1000 processes I need to spawn, so I may not spawn them at once as it makes heavy burden in system.
The first solution I can think up of is to use multi-threads to spawn processes. For example, I first create 10 threads in the main process, and in each thread, it spawns a process and waits for its finish, then it spawns and waits another process. This progress goes on until all jobs are finished. And I can make sure at any time there will not be more than 11 processes and 10 more threads. But the problem is I use pthread to create thread, and use fork to create process. It is very dangerous to use thread and fork at the same time. When you call fork in one thread, the new process will only have one thread, other threads are just stopped running, but the resources (like memory/lock) they occupy are not freed for reuse. For example, when one thread calls fork, another is using printf to print something to stdout. It seems fine, but in printf implementation, it may uses mutex lock to prevent different threads accessing the print buffer at the same time (that is the reason why we have clean output in multi-threads). If the thread using printf has just got the mutex lock when fork happens, the mutex lock will not be freed, so the result is the new forked process can not print anything to stdout (Because it will get the mutex lock for stdout which will never be freed).
After taught a lesson by pthread plus fork, I should find another way to realize parallelism. The idea is simple that if I can't spawn 1000 processes at once, what about 10 at a time? I can keep an array of spawned processes, once one child process is finished, I can spawn another one. By using an array of 10, I can make up to 10 spawned processes running at the same time. The work process is like below:

   while (not all work finished) {
      spawn processes until the running process array is full.
      wait for some process finish, collect the result.
   }

It is even simpler than the multi-thread one, but it works better.  So I think it deserves to record it :-)

How to write a binary search

Binary search algorithm is a simple and widely used search algorithm. It works for sorted arrays. However, it is also error-prone. When I write a piece of binary search code, I usually want to check each case to make sure everything is handled. Just like below:

int BinarySearch(int s[], int len, int key) {
  int low = 0, high = len - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;  // It is not easy to take care of the overflow.
    if (s[mid] > key) {
      high = mid - 1;
    } else if (s[mid] == key) {
      return mid;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

While it is right, I need to write two comparisons in the loop. What if only one comparison can be used?

int BinarySearch(int s[], int len, int key) {
  int low = 0, high = len - 1;
  while (low + 1 < high) {
    int mid = low + (high - low) / 2;
    if (s[mid] > key) {
      high = mid - 1;
    } else {
      low = mid;
    }
  }
  // We need to test both low and high, as both of them may be the result.
  if (low < len && s[low] == key)
    return low;
  if (high >= 0 && s[high] == key)
    return high;
  return -1;
}

But I just read a piece of binary search code written in <Beautiful code>, as below.

int BinarySearch(int s[], int len, int key) {
  int low = -1, high = len;
  while (low + 1 < high) {
    int mid = low + (high - low) / 2;
    if (s[mid] > key) {
      high = mid;
    } else {
      low = mid;
    }
  }
  // We only need to test for low, because high is always above result.
  if (low != -1 && s[low] == key) {
    return low;
  }
  return -1;
}

Of course, all of the three can be used, and have little difference with each other. But it may be fun to compare them.

Reading "Inside c++ object model"

While it is easy for us to imagine how c language code is translated into assembly code and corresponding machine code, things become complicate in c++ language.

C++ programming styles

C++ language brings at least four programming styles: procedure programming, object based programming, object oriented programming and generic programming.

1. Procedure programming style is to keep compliance with c, allowing us to keep a bunch of data, make some operations on the input data like a pipeline, and produce whatever data we want. While It is clear in itself, the problem is the real world is complex. It becomes harder and harder to maintain and develop when the data and operation becomes more and more complex. That's the reason why object oriented programming languages are invented.

2. Object based programming style gives the concept of object, which binds data and operations on the data together. In procedure programming, what you can use are only the built-in types like int, float, char. But in object based programming style, you can build more powerful types called abstract data type(ADT). You can define the data inside ADT and operations supported by ADT. You can construct ADT based on other ADTs. ADTs are easier to use and maintain than built-in types, because it provides an important concept in computer science called Abstract Layer. Encapsulation and interface are inherently included in it.

3. Object oriented programming style is even more powerful than object based programming. Object oriented programming supports a concept called polymorphism. Derived class can implement operations in a different way of the base class. It means user can use the same code to deal with both base class and derived classes. It becomes easier to extend and maintain, and does good to code reuse. Many interesting stories happen in object oriented programming because of inheritance and polymorphism.

4. Generic programming style is believed to be an extreme programming style for code reusing. You can define a template for a class or a function, without deciding the real data type it needs to deal with until instantiation time. While it is more familiar to many c++ programmers, it is widely use in implementing c++ standard library.

How to implement C++ ?

Well, how to implement c++ is big question which is better left for c++ standard committee and compiler producers. However, we c++ programmers always can't help to wonder what is going on under c++ programming language. How is the constructors and destructors be called? How to implement inheritance and even multiple inheritance? How does polymorphism happen? How is exception handling implemented? Absolutely no magic is here, only c++ compiler, linker/loader, runtime library work together to fulfill all the functions supported by c++.
The book <Inside c++ object model>, written as early as 1996, is trying to give us an insight of how c++ features are implemented by the compilers. I was astonished by the content of the book. It just said things like how can we synthesis default constructor, or how can we record data to support inheritance. It is a big challenge for the c++ compilers and runtime libraries to fulfill the c++ features, but they are very smart, and do a lot of work behind that. So I think it may be fun to study the details.
As time goes on, more powerful c++ features are supported, the compilers are becoming more and more smart. Many of the technologies described in the book may be out-of-date. So I should prove the implementation carefully.
I plan to partition the study into several chapters.
Chapter1: How to implement a class? It is a class with only data members and member functions.
Chapter2: How to implement class inheritance? We study three types of inheritance: single inheritance, multiple inheritance, and virtual inheritance.
Chapter3: How to implement polymorphism? We focus on the implementation of dynamic binding of virtual functions.
There may be further data added after this, according to the study condition.

The first blog

I just want to see the blog effect here. It is simple, but maybe a good start!