yonilip / os-ex3 Goto Github PK

yonilipman, danielle.kut
Yonatan Lipman (305629750), Danielle Kutner (204094460)
EX: 3

FILES:
README -- This file
Makefile -- makefile for the project, compiles the library and a demo
            of its use called Search. creates tar and cleans the file
MapReduceFramework.cpp -- MapReduceFramework library implementation
Search.cpp -- Demo of the framework that searches for a substring in file names
              in the given directories

REMARKS:
We designed the framework such that the main function runMapReduceFramework
runs each part of the process in different modules.
Specifically, the framework will create threads that handle the mapping and
reduction. each thread will handle a chunk of the given data at a time and
we make sure that there is a seperation between the shared data structures
using pthread's mutex feature.
In order to tell between the different threads and their data structures and
mutexes, we used thread_local, which allows to have a global int that is unique
to each thread.
When shuffle is signaled to start working, it iterates over all of the
mapping containers and works on them. mapping in chunks ensures that we dont
work too hard when shuffling in each iteration over the containers so each time
the containers are small when not empty. we ensure that we emptied all of the
containers by iterating one final time after the mapping process is finished.
We used deque and map as the containers of choice and List when we had to
comply to the given header files.
Notice that each time that the framework runs, it is initialized and terminated
properly such that it is possible to run it multiple times in the same process.

ANSWERS:

1) Design:
   The framework will create a pipe for each thread created.
   Mapping and Shuffling:
   Each thread has a pipe that reads chunks of k1 and v1 from the main
   data given to read. ExecMap will write the emitted k2 and v2 to fd's that
   are unique to each thread. Shuffle will read the k2 and v2's from each
   fd that map wrote to and will write to a single fd that will hold the
   shuffled data. shuffle will choose the pipe to read from using select.
   Reduce:
   Each thread has a pipe that reads from the shuffled data fd the k2 and the
   list of v2's. ExecReduce will write the emitted k3 and v3 to the main
   threads mapped and reduced data fd.

   The data that is read and written will be composed entirely from pointers,
   such that it is easier to read and write known chunks of bytes and let the
   user handle the dereferencing of the pointers.

   Generally lists are good enough for the needed result.
   ExecMap could use lists of k1*,v1* and lists of k2*,v2* for storing the
   mapped pointers. Shuffle would have a list of (k2*,list(v2*)).
   ExecReduce would get shuffle's list and have its own list of k3*,v3*
   that would be returned to the user.

   In order for the consumers to know that there is no more data,
   we will make use of boolean variables.
   Such that when reading data for mapping, we will keep reading until the
   var will turn false. Shuffle will use the select function to choose which
   fd to read from when the fd is ready. when ExecMap is done writing, it will
   close the fd thus select could use the fd to read from it using pipe.
   when 0 will be read then shuffle will know that it is done with the fd
   in context.
   ExecReduce will work in a similar fashion and such will the end of the
   frameworks run.



2) We would use 7 threads for multiThreadLevel.
   in our implementation shuffle thread does not count as one of the thread in
   multiThreadLevel (creating multiThreadLevel amount of
   execMap and execReduce).
   and ignoring main thread since it will waits (for join) most time framework
   runs, this way 8 threads can run on each core in parallel manner:
   7 will execute map and reduce actions, and one will shuffle.

3)
    a. Utilizing multi-cores:

        a- Nira:
        Nira's thread will run on one core at most and will not utilize
        multi-core actions.
        there is no concurrency.
        b- Moti:
        we cannot know for sure if Moti's program will support multi-threading.
        it is able to utilize seperate cores but won't necessarily do so.
        c- Danny:
        Danny uses user-level threads so one thread will run at any given time.
        Concurrency is not achieved.
        d- Galit:
        Galit has the best approach, each thread is actually a process, so the
        OS will try and take advantage of multi-core abilities: running each
        process on an available core.

     b. Creating sophisticated scheduler ability:

        a- Nira:
        each time main thread will get run time from the kernel, the thread
        will run.
        b- Moti:
        OS responsible of scheduling kernel level threads,
        it can be affected by using mutexes, condition variables, barriers...
        c- Danny:
        user level threads scheduling isnt difficult and can be implemented
        using scheduling
        algorithm (such as Round Robin that we implemented in ex2).
        d- Galit:
        OS would be in charge of scheduling each process and circumventing it
        would be very difficult.

     c. Communication between threads and processes:

        a- Nira:
        thread can easily communicate with itself
        b- Moti:
        threads share the same memory pool of their process. We can easily
        implement a communication between memory using locks and flags.
        c- Danny:
        we can access the same memory for each thread by locks and flags,
        communication is fast.
        d- Galit:
        communication between processes will take a long time since multiple
        processes communication is done by reading and writing into the
        pipe) which is slower then shared memory
        communication (Danny and Moti).

     d. Ability to progress while a thread is blocked:

         a- Nira:
         Nira has only one thread so in case it will be blocked, the whole
         process will be blocked.
         b- Moti:
         in case one thread is blocked, there will be other thread that c
         ontinue with the map reduce work ad the process will continue.
         c- Danny:
         User-level threads doesn't cannot progress while a certain thread
         is blocked.
         OS takes all user level threads as one unit, so the process will be
         blocked.
         d- Galit:
         blocking one thread will not block others. OS will manage each process
         and runs them on different cores when possible. If a thread is blocked
         then the OS will run another process in its place.


     e. Overall speed:

          a- Nira:
          In case context switch is expensive, Nira's solution will be
          better then Moti's and Galit's since a single thread is running-
          no context switching!
          in most cases framework contains many items so the major time would
          be spent in the map and reduce stages where more threads/processes
          would save time using concurrency
          b- Moti:
          Moti's solution will be the faster among othe solutions.
          creation and communication time are faster using
          threads over processes (threads communicate
          through shared memory in contrast to I/O actions). synchronization
          of our shared data forces us to use mutexes and flags which also take
          time but we think in overall this will probably be the best way to
          implement this task.
          c- Danny:
          Danny uses user level threads, not creating separate processes or
          kernel level threads.
          His solution may still be faster than Nira's depending on the cost
          vs benefit of the context switches.
          But may be slower than others
          for the same reason Nira's will most likely be slower. And may
          be faster than the other's due to the lower cost of creating
          user-level threads and doing context switches.
          d- Galit:
          Galit solution will be fast since Galit since it takes advantage of
          any possible multi-cores available on the machine the
          program runs on.
          it can be slower than multithreading due to the time it takes to
          create processes and the time it takes us to switch between them.

4)

    Kernel-level thread:
        Global variables
        Heap

    User-level thread:
        Global variables
        Heap

    Process:
        None


5) Livelock vs Deadlock:
   Although they are similar in a way, we will notice that when in deadlock,
   the thread will get stuck waiting for a condition that wont be fulfilled.
   Livelock on the other hand wont have the threads waiting but it wont make
   any progress since the threads will always respond to each other creating
   an endless chain of replies to one another.

   Deadlock example:
   ----------------------------
   Process 0:

   flag[0] = true;
   while (flag[1]); // does nothing until false
   /* critical section and actions */
   flag[0] = false;

   Process 1:

   flag[1] = true;
   while (flag[0]); // does nothing until false
   /* critical section and actions */
   flag[1] = false;

   // notice that if both flags are true before getting to the while command,
   // they will never reach the critical section and stay in deadlock.

   Livelock example:
   ----------------------------
   Process 0:

   flag[0] = true;
   while (flag[1])
   {
        flag[0] = false;
        // wait constant time
        flag[0] = true;
   }
   /* critical section and actions */
   flag[0] = false;

   Process 1:

   flag[1] = true;
   while (flag[0])
   {
        flag[1] = false;
        // wait constant time
        flag[1] = true;
   }
   /* critical section and actions */
   flag[1] = false;

   If both flags are true, then p0 makes flag0 false and p1 makes flag1 false
   and then p0 makes flag0 true and p1 makes flag1 true we will experience
   livelock.

6) Process|Arrival Time| Running Time| Priority (higher number-higher priority)
   P1      0                10           1
   P2      1                1            3
   P3      3                2            2
   P4      7                12           3
   P5      8                1            1

   RR (quantum = 2):
       -Turnaround time: (18+2+4+19+4)/5 = 9.4
       -Average wait time: 8+1+2+7+3)/5 = 4.2

   FCFS:
       -Turnaround time: (10+10+10+18+18)/5 = 13.2
       -Average wait time: (0+9+8+6+17)/5 = 8
   SRTF:
       -Turnaround time: (14+1+2+19+1)/5 = 7.4
       -Average wait time: (4+0+0+7+0)/5 = 2.2

   Priority Scheduling:
       -Turnaround time : (25+1+2+12+18)/5 = 11.6
       -Average wait time : (15+0+0+0+17)/5