[UCSD CSE120]进程间通信-inter process communication(IPC)

本文是我在上UCSD的 CSE 120: Principles of Operating Systems (Winter 2020) 整理的笔记,这一课主要介绍了操作系统里面不同进程之间通信的算法和实现。

  1. Cooperating Processes and IPC

    • Advantage of Cooperating Processes

      • performance: speed

        • Exploit inherent parallelism of computation
        • Allow some parts to proceed why other do I/O
      • Modularity: resuable self-contained programs

        • Each may do a useful task on its own
        • May also be useful as a sub-task for others
      • Examples:

    • IPC: communication between processes

    • IPC requires:

      • data transfer
      • synchronization
    • Three abstraction for IPC

      • shared memory + semaphores
      • monitors
      • message passing
  2. The producer/consumer problem

    • Producer produces data, inserts in shared buffer

    • Consumer removes data from buffer, consumes it

    • Cooperation: Producer feeds Consumer

      • How does data get from producer to consumer?
      • How does consumer wait for producer?
    • Example:

  3. Shared memory + semaphore

    • implementation:
      shared int buf[N], in = 0, out = 0;
      sem filledslots = 0, emptyslots = N, mutex = 1;
    
      // Producer1, 2, ...
      while (true) {
        wait (emptyslots); // wait for available empty slots
        wait (mutex); // avoid racondition
        buf[in] = Produce();
        in = (in + 1) % N;
        signal(mutex);
        signal(filledslots); // increment the number of filled slots
      }
    
      // Consumer1, 2, ...
      while (true) {
        wait(filledslot);
        wait(mutex);
        Consume(buf[out]);
        out = (out + 1) % N;
        signal(mutex);
        signal(emptyslots);
      }
    
    • work for multiple producers and consumer
    • Not easy to understand(many wait/signal statements), easily leads to bugs
  4. monitors

    • Programming language contruct for IPC

      • monitors are variables requiring controlled access
      • accessd via procedures
      • condition variables
        • wait(cond)
        • signal(cond)
    • Only one process can be active inside monitor

    • Usage

    // a possible monitor implementation (provided by programming language)
    monitor ProducerConsumer {
      int buf[N], in = 0, out = 0, count = 0;
      cond slotavail, itemavail;
    
      void PutItem (int item) {
        if (count == N) wait(slotavail);
        buf[in] = item;
        in = (in + 1) % N;
        count++;
        signal(itemavail);
      }
    
      int GetItem() {
        int item;
        if (count == 0) wait(itemavail);
        item = buf[out];
        out = (out + 1) % N;
        count--;
        signal(slotavail);
        return (item);
      }
    }
    
    // Producer
    while (true) {
      PutItem(Produce());
    }
    
    // Consumer
    while (true) {
      Consume(GetItem());
    }
    
    • mechanism

    • more on Monitors

      • If one process A siganl condition c while another process B is waiting on c, at that time two process are able to run at the same time, which breaks mutual exclusion. So each process only signal condition just before returning.
      • Contition variable have no memory
        • It has no value and only indicate whether an event occurs or not
        • Signal without someone waiting does nothing
        • Signal is “lost”
      • Monitors bring structure to IPC
        • localizes critical sections and synchronization
  5. Message Passing

    • Model:

    • methods:

      • send(destination, &message)
      • receive(source, &message)
    • Data transfer: in to and out of kernel message buffer

    • Synchronization: receive blocks to wait for message

    • Usage

      • basic

        /* NO SHARED MEMORY */
        // Producer
        int item;
        
        while (true) {
        item = Produce();
        send(Consumer, &item);
        }
        
        // Consumer
        int item;
        
        while (true) {
        receive(Producer, &item);
        Consume(item);
        }
        
      • with Flow Control

        // Producer
        int item, empty;
        
        while (true) {
            item = Produce();
            receive (Consumer,&empty);
            send(Consumer, &item);
        }
        
        // Consumer
        int item, empty;
        
        do N times {
            send(Producer, &empty);
        }
        
        while (true) {
            receive(Producer, &item);
            send(Producer, &empty);
            Consume(item);
        }
        
    • more on Message Passing

      • who should message be addressed to?

        • ports(“mailbox”) rather than specific process
      • how to make process recieve from anyone?

        • pid = receive(*, &message)?
      • kernel buffering: outstanding message

        • message sent that haven’t been received yet
      • Good praradigm for IPC over networks

      • Safer than shard memory paradigms

Built with Hugo
Theme Stack designed by Jimmy