2015-06-10

Learning Scratch (2)

My last blog entry, I briefly talk about what is Scratch. There are ``events'' and that is the trigger of the program. In this article, I would like to talk about one of my students who made a character animation program by Scratch.

Scratch provides key events. When I push the right arrow key, then ``right arrow key push event'' is triggered. When that event happened, I add 10 to the x coordinate of the cat. This means, when the right arrow button pushed, the cat move to the right for 10 steps. If I add more programs like the up arrow moves the cat to upper direction, I can control the cat position by the arrow keys. This is a cat control program.

Today, my student used a dragon. He wrote the same program with the cat. Then, the cat and the dragon move exactly the same way. Of course they should. A current computer is very fast, very precise, and very stupid. It does only what the developer wrote. My student asked me, how he can make the dragon faster. I answered, increase the moving step. Currently one key push moves the dragon ten unit steps. A speed is a moving distance in a certain time. If the step was increased to twenty from ten, the speed of the dragon becomes twice. While after, when I came back to him, he duplicated the key events. Interesting.

His method is the following: when the right arrow push event was triggered, two programs started in parallel. One program change the dragon's x coordinate plus 10, and another program does the same. In the end, the dragon's x coordinate increased by twenty. It seems the Scratch environment takes care the parallel change (i.e., locking), so this program works correctly. When he wanted to move the dragon three times faster than the cat, he copied the program again. What an interesting idea he had! Out of the blue, I recalled one scene of a cartoon, JoJo's Bizarre Adventure. (If you don't know it, please ignore the rest of the paragraph.) It's a scene that Jotaro floated in the air using his stand. He can move in the air by pushed his stand. My idea was increase the speed of the stand, but my student idea was increase the number of stands. Two stands can push twice faster, three stands can push three times faster.

But this student's idea can only make whole number times speed. He cannot make the dragon 1.5 times faster than the cat. Of course one program can push the dragon ten steps and another program can push the dragon five steps, make it 1.5 times faster. But then, there is not so much difference from one program pushed fifteen steps. His idea is just coping all the events and nothing more, still he can change the speed twice. However, if you learn the idea of generalization from mathematics, you will realize that which method can be applied to more situations. In this case, changing the speed itself in one program is better since you are not limited to multiple of positive integer (not only fractional times speed up, but you can stop and can also go backwards). If you learn computer science, the one program is considered better since the resource consumption of multi-threading, synchronization overhead, and so on. Also code maintenance point of view, one program is much easy to manage in general compare to the multiple copies of the program. Despite these disadvantages, I still like his idea, so free and unique.

When I saw 20 key events for handing four direction's control to speedup dragon five times faster (Figure 2), I was surprised by his idea, especially how freely and creatively he can think. At the same time, I felt the importance of the learning of basic concepts. I wish he will continue to learn without forgetting this thinking way, a free and creative way of thinking.

Figure 2. Using multiple same key events

Learning Scratch (1)

I teach Scratch [1], a computer programming language, to 10 to 12 years old students from last year. Sometimes they show me an interesting creative idea. I would like to write one of them here.

Before I explain what my students did, I will explain what is Scratch. First I will explain it in a conceptual way, then with an example. If someone can understand a conceptual explanation, he/she can apply the idea to many cases, but this is a bit difficult since their understanding must be deep. An explanation by example is rather easy to understand since it is shallow, that means you don't know it is still true in other cases. So there is a trade-off.

Scratch is a computer language, but also a programming environment.  In the environment, the developer writes event driven programs to control many sprite [2] characters. You can think each sprite character an object. Each event invokes a program and each program runs in parallel.

Maybe this explanation doesn't make sense for whom has never written a program. There are many conceptual words here: programming environment, sprite, event, object, and so on.. Each term is a concept in programming and we need to lean them. But I usually don't explain these concepts to 10 years old students. So I use examples. But I hope they can understand the concept in the future.

When you start scratch programming environment, there is a cat (Figure 1).  The developer writes a program what the cat does when something happened. ``Something happened'' means, for instance, a key is pushed, a mouse button is pushed. These ``something happened'' is called an ``event.'' An event starts a program. Such program can also create other events. This type of program is called an event driven program. Each character, for instance, a cat, a dog, and so forth, usually has an own state. The developer uses this state to write a program. Here ``a state'' is for example, where is the cat (position), which direction the cat is looking at (directional angle). An object is a programming instance that has a state. Here, you can consider that a cat is an object, a dog is also an object.
Figure 1. Scratch programming environment
In the scratch environment, the green flag button is the start button of the program. Most of the scratch programs use this green flag as the start event. For example, when the green flag button is pushed, the cat moves to the center of the screen and says ``Hello!'' I usually first tell my students about ``a coordinate system.'' My explanation is simple as ``x'' means left or right, ``y''means up or down. If you set both value to 0, the character moves to the center of the screen. When you make the x value large, the character moves to the right. In the scratch environment, the coordinates x and y are always shown. So I can show how the coordinates change as I move the character. When I catch the cat by the mouse (I mean a computer mouse), I say ``See, when the cat move to the right, the x value becomes larger.''  I drag the cat and move it around to show them.

This time I explained briefly what is Scratch. In the next blog entry, I would like to talk about 10 years old student story who made a character animation program on Scratch.

References

2015-06-06

Inter process communication by a shared memory

I made an experience for an inter process communication using a Unix shared memory on a host. I look up on the Internet, but I could not find a good example code. In the end, I found some explanation articles, some Stack overflow threads. (I might do something wrong when I search...)

Some pages suggest to use shmem_open() and mmap(), that is the POSIX direction. I think I can believe the discussion, so I implemented it the following way.

The basic idea is the following:
  1. A process creates an shared memory area using shm_open().  To identify the shared memory area between processes, we use an identifier string (e.g., ``identifier''). (On Linux environment, You can see via /dev/shmem, e.g., /dev/shmem/identifier .)
  2. All processes map that shared memory are to main memory using mmap(). When we succeeded mmap(), we obtained a shared memory pointer (shared_ptr).
  3. The processes can communicate via shared_ptr.
  4. When we finished to use the shared_ptr, remove the map using munmap().
  5. One of the process removes the shared memory object using shm_unlink().
The following implementation shows how two processes (server and client) communicate each other via a shared memory area. Here, the number of server processes and the number of client processes are both one. In this example, each process only writes a value to own area. Thus, we don't need a lock. Each process reads the other process's value and write one grater value of the read value at the own area. This is simple, but enough to demonstrate how to communicate between processes via a shared memory on a host. 

The following is the source code (shmem_test.cpp). You can find how to compile and run in the comment of the code.

/*
  Shared memory inter process communication minimal example
  Copyright (C) 2015 Hitoshi

  Compile:
    g++ shmem_test.cpp -o shmem_test -lrt

  Run (as a server):
    shmem_test server

  Run (as a client)
    shmem_test client

  Note: no locking. (but writes are not the same location.)

  Basic idea: server, shared memory creator

  1. Create a shared memory object by shm_open().
  2. Change the shared memory object by ftruncate().
  3. mmap the shared memory object to access via a pointer.
  4. Use the pointer to share the memory (may need lock, etc.)
  5. munmap the shared memory object
  6. Remove the shared memory object by shm_unlink()

  Basic idea: client

  1. Open the created shared memory object by shm_open().
  2. mmap the shared memory object to access via a pointer.
  3. Use the pointer to share the memory (may need lock, etc.)
  4. munmap the shared memory object

 */

#include <iostream>

#include <fcntl.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

//----------------------------------------------------------------------
/// shard memory identifier name
const char* SHMEM_NAME = "/test.shmem";
/// shared memory size (align to the page size)
const size_t SHMEM_SIZE = 4096;

//----------------------------------------------------------------------
/// print out the usage and exit of this example
void usage_exit()
{
    std::cerr
        << "Shard memory inter process communication minimal test\n"
        << "shmem_test [server|client]\n"
        << "  server ... create/read/write shared memory\n"
        << "  client ... read/write shared memory"
        << std::endl;
    exit(1);
}

//----------------------------------------------------------------------
/// server
void run_server()
{
    // create/open the shared memory object
    int fd = shm_open(SHMEM_NAME,
                      // oflags
                      O_CREAT|  // create if not exist
                      // O_TRUNK|  // destroy once if exists
                      O_EXCL|   // error if exists
                      O_RDWR    // read/write
                      ,
                      // mode
                      S_IRUSR|  // user read
                      S_IWUSR   // user write
        );

    if (fd >= 0)
    {
        std::cout << "server: shmem_open succeed fd: " << fd << std::endl;
    }
    else
    {
        std::cerr << "server: shmem_open failed: " << fd
                  << ", if /dev/shm"    << SHMEM_NAME
                  << " exists, remove it." << std::endl;
        exit(1);
    }

    // resize the shmem object
    const int ret = ftruncate(fd, SHMEM_SIZE);
    if (ret != 0)
    {
        std::cerr << "Server: failed to ftrancate to " << SHMEM_SIZE
                  << std::endl;
        exit(1);
    }

    // get shmem address
    const size_t access_offset = 0;
    void* shmem_adder = mmap(0, SHMEM_SIZE,
                             // memory protection mode
                             PROT_READ| // Pages may be read.
                             PROT_WRITE // Pages may be written.
                             ,
                             // mapping flag
                             MAP_SHARED, // Share this mapping with other process
                             fd,
                             access_offset);
    if (shmem_adder == 0)
    {
        std::cerr << "Serevr failed to mmap." << std::endl;
        exit(1);
    }
    close(fd);                 // fd is no longer needed

    // server process work
    int* int_ptr = reinterpret_cast<int*>(shmem_adder);

    // initialize
    int_ptr[0] = 0;
    int_ptr[1] = 0;

    for (int i = 0; i < 10; ++i)
    {
        int my_int    = int_ptr[0];
        int other_int = int_ptr[1];

        if (my_int <= other_int)
        {
            my_int = other_int + 1;
            int_ptr[0] = my_int;
            std::cout << "I am taller. " << my_int << ", "
                      << other_int << std::endl;
        }
        usleep(800000);
        std::cout << "Checking client " << i << std::endl;
    }
    std::cout << "Quit server: " << int_ptr[0] << ", " << int_ptr[1] << std::endl;

    // unmap
    int ummap_ret = munmap(shmem_adder, SHMEM_SIZE);
    if (ummap_ret != 0)
    {
        std::cerr << "Failed to munmap. " << ummap_ret << std::endl;
        exit(1);
    }

    // remove shmem object
    int unlink_ret = shm_unlink(SHMEM_NAME);
    if (unlink_ret != 0)
    {
        std::cerr << "Failed to shm_unlink. " << unlink_ret << std::endl;
        exit(1);
    }
}

//----------------------------------------------------------------------
void run_client()
{
    // open the shared memory object
    int fd = shm_open(SHMEM_NAME,
                      // oflags
                      O_RDWR    // read/write
                      ,
                      // mode
                      S_IRUSR|  // user read
                      S_IWUSR   // user write
        );

    if (fd >= 0)
    {
        std::cout << "shmem_open succeed fd: " << fd << std::endl;
    }
    else
    {
        std::cerr << "shmem_open failed: " << fd
                  << ", Are you running the server?" << std::endl;
        exit(1);
    }

    // get shmem address
    const size_t access_offset = 0;
    void* shmem_adder = mmap(0, SHMEM_SIZE,
                             // memory protection mode
                             PROT_READ| // Pages may be read.
                             PROT_WRITE // Pages may be written.
                             ,
                             // mapping flag
                             MAP_SHARED, // Share this mapping with other process
                             fd,
                             access_offset);
    if (shmem_adder == 0)
    {
        std::cerr << "Failed to mmap." << std::endl;
        exit(1);
    }
    close(fd);                 // fd is no longer needed

    // server process work
    int* int_ptr = reinterpret_cast<int*>(shmem_adder);

    // initialize
    int_ptr[0] = 0;
    int_ptr[1] = 0;

    for (int i = 0; i < 10; ++i)
    {
        int my_int    = int_ptr[1];
        int other_int = int_ptr[0];

        if (my_int <= other_int)
        {
            my_int = other_int + 1;
            int_ptr[1] = my_int;
            std::cout << "I am taller. " << my_int << ", "
                      << other_int << std::endl;
        }
        usleep(500000);
        std::cout << "Checking server " << i << std::endl;
    }
    std::cout << "Quit client: " << int_ptr[0] << ", " << int_ptr[1] << std::endl;

    // unmap
    int ummap_ret = munmap(shmem_adder, SHMEM_SIZE);
    if (ummap_ret != 0)
    {
        std::cerr << "Failed to munmap. " << ummap_ret << std::endl;
        exit(1);
    }
}

//----------------------------------------------------------------------
/// main
int main(int argc, char* argv[])
{
    if (argc == 1)
    {
        usage_exit();
    }
    else if ((argc == 2) && std::string(argv[1]) == "server")
    {
        run_server();
    }
    else if ((argc == 2) && std::string(argv[1]) == "client")
    {
        run_client();
    }
    else
    {
        usage_exit();
    }

    return 0;
}

I hope someone can find this example useful.