운영체제#18

LeeMir, 14 June 2021

8강 - Multiple Processor Systems

Multiple Processor Systems
  • Multi core system
    • 여러 개의 CPU들이 메모리를 공유
    • CPU 개수에 제한이 있음(32개 정도)
      • Memory Access에 있어서 병목이 있기 때문
  • Inter-connection
    • 여러 CPU들이 각각 local 메모리를 보유
    • 다른 CPU의 local 메모리도 접근할 수 있음(살짝 느림)
    • 슈퍼 컴퓨터
  • 분산 시스템
    • Internet으로 각각 독립적인 컴퓨터 시스템을 연결
    • 시스템이 서로의 메모리에 접근할 수 있음
    • 각 시스템은 특수한 역할을 도맡기도 함
  • UMA / NUMA
    • (None) Uniform Memory Access
      • 공유 메모리를 접근하는 속도가 각 CPU가 동일한지
      • Inter-connection의 경우 NUMA (원격 저장소는 접근하기 느림)
  • UMA Multiprocessors with Bus-Based System
    • (주로 Multi core system에서) 하나의 Bus에 CPU들과 Shared Memory를 연결
    • 병목이 일어날 수 있음
      • 그것을 해결하기 위해 각 CPU가 Shared Memory가 아닌 Private Memory를 보유하기도 함
      • 이 경우 UMA가 아니게 됨
    • Cache coherence
      • 한 CPU가 Shared Memory의 내용을 변경할 경우, 다른 CPU들의 Cache들의 기존 내용을 삭제해줘야함(Snooping)
  • UMA Multiprocessors using Crossbar Switches
    • CPU 개수가 N개, 메모리 개수가 N개라면 N x N의 Crossbar switch로 연결
    • 같은 메모리에 동시 접근은 불가능
    • 비쌈
  • UMA Multiprocessors using Multistage Switching Networks
    • Omega Switching Network
      • Crossbar의 비해 훨씬 적은 Switch의 개수로 구현할 수 있음
      • 각 switch는 output이 두개로 다음 Stage의 switch에 연결되는데, 이는 목적지 메모리의 주소의 2진수를 보고 정함
        • 1이면 아래로 0이면 위로
  • NUMA Multiprocessors
    • UMA를 사용하는 system은 병목 때문에 CPU 개수의 한계가 있음
    • NUMA System에서 모든 CPU는 모든 Memory에 접근할 수 있음(single address space로 표현 가능)
    • Interconnection network의 속도는 Local bus보다는 느리지만, 일반 network보다는 월등히 빠름
      • 찾고 싶은 내용이 어느 원격 memory에 있는지는 각 노드마다 Directory라는 구조를 사용
      • 노드마다 16MB의 Memory가 존재, 그 Memory는 64바이트의 Block 단위로 쪼개져있음
      • Node num(8) / Block num(18) / offset(6)의 형태로 32-bit 주소를 사용함
OS for Multiprocessor Systems
  • 옛날에는 CPU가 하나였었으나, Multiprocessor System으로 발전함
  • OS도 Multiprocessor용으로 수정해야했음
    • Windows는 처음부터 Multiprocessor 용도로 설계됨
  • OS를 CPU 한 개가 아닌 여러 개를 쓸 수 있게 수정하는 과정에서 여러 방법이 나옴
    • 각각의 CPU가 독립적으로 OS를 갖고 있음
      • OS Code는 공유할 수 있으나, Memory는 각 CPU가 영역을 분할해서 사용
    • Master-Slave Multiprocessors
      • 하나의 CPU가 Master CPU 역할을 해 OS를 실행
      • 다른 CPU(Slave)에서는 오로지 응용 프로그램만을 실행(Memory는 공유함)
        • 만약 시스템 호출로 OS Code를 사용해야할 경우 스케쥴링을 통해 Master CPU를 실행해야 함
      • Master CPU에 병목이 일어나는 문제 + Master CPU에 문제가 생기면 전체 시스템이 마비되는 문제
    • Symmetric Multiprocessors
    • 모든 CPU가 동등하게 응용 프로그램을 실행하거나 OS Code를 실행할 수 있음
      • 이 때, 각각 독립된 OS가 아니라 하나의 OS를 공유
    • 현재 PC들이 사용하는 방법
    • 두 개 이상의 CPU가 같은 데이터에 접근할 수 없도록 코드를 짰음(Lock / Unlock)
    • 메모리의 OS Code 부분에 병목이 일어나는 문제가 있음
Multiprocessor Synchronization
  • 다른 CPU가 동시에 같은 데이터에 접근하면 안됨
  • lock 기법을 사용
    • 매번 lock 변수를 검사하는 것은 bus traffic을 늘리기 때문에 좋지 않음
    • Revised TSL algorithm
    • exponential backoff algorithm을 사용해 lock 변수를 검사하는 주기를 점점 늘림
    • Private lock variable
      • 공유 lock 변수를 cache에 저장할 경우 한 CPU가 lock 변수를 1로 만들었을 때, Cache Coherence에 의해 모든 CPU의 cache를 수정해야함, 이는 좋지 않음
      • CPU마다 각각 private한 lock 변수를 가짐
      • lock 변수를 linked list로 만듦
        • CPU들이 linked list를 나눠가짐
Multiprocessor Scheduling

  • Time Sharing

    • Global Queue 방식
      • Queue에 병목이 일어날 수 있음
    • 어떤 process가 lock을 갖고 있을 경우, 그 process에 시간을 더 부여해주는 smart scheduling이 가능
    • 가능한 process는 같은 cpu에서만 실행되는 것이 캐시 친화적임
    • 이런 사항들을 고려해 Two-level scheduling algorithm을 사용함(Global Queue + Local Queue)

  • Space Sharing

    • Process를 CPU에 할당하지 말고, CPU를 Process에 할당하자
    • CPU 개수가 많아져서 가능한 방식
    • CPU 개수가 많으면 딱히 Scheduling Algorithm은 중요하지 않음

  • Gang Scheduling

    • 한 프로그램의 쓰레드들은 동시에 실행되어야 함

      • 서로 동기적으로 실행되게 짜여지는 경우가 많기 때문

    • 서로 관련 있는 쓰레드들을 하나의 집단(gang)으로 묶음

Multi-Computer System
  • Inter-connection으로 Computer Node들을 연결
  • 다양한 형상의 연결 방법 존재(single switch, ring, grid, double torus, cube, hypercube 등)
  • Store-and-forward 방법을 사용하는 packet switching 방식을 주로 사용
  • Network Interfaces
    • 응용프로그램에서 다른 노드로 데이터를 보내고 싶으면 OS로 전달(Copy)함
    • OS에서는 Network Card에 데이터를 Copy하고, Internet이나 Switch Network를 이용해 다른 Node로 전달함
    • 목적지 노드의 Network Card에 데이터가 도착하면, 이것을 OS로 Copy한 후 그것을 또 응용프로그램으로 Copy
      • Network에서 온 데이터를 바로 메모리로 보내기는 쉽지 않기 때문에 OS를 거쳐야 함
      • 바로 메모리로 보내는 최신 기술이 개발되긴 했음
    • Copy가 너무 많이 일어나서 초고속 Network의 경우 오버헤드가 너무 크기도 함
Blocking vs Nonblocking Calls
  • Sender가 Receiver한테 Data를 보낼 때 Receiver가 받을 때까지 Sender가 Blocking됨(Blocking send)
  • Receiver가 받든 말든 Nonblocking할 수도 있음(Nonblocking send)
  • 어떤 방식이든 Receiver는 받을 때까지 Blocking되어야 함
  • Sending side의 선택지
    • Blocking send
      • Sender가 보낼 메시지를 갖고 기다리고 있다가 Receiver가 요청하면 보내주면 끝
    • Nonblocking send with copy
      • Sender가 보낼 메시지를 OS가 다른 곳에 Copy 해놓고 Sender는 다른 일 수행, Receiver가 요청하면 Copy해놓은 메시지를 보냄
      • 이 때, Copy를 해놨으므로 메시지가 저장되어있던 메모리를 Sender가 다른 용도로 쓸 수 있음
      • Copy를 해야한다는 오버헤드가 존재
    • Nonblocking send with interrupt
      • Copy를 하지도 않고, Sender가 다른 일 수행도 함
      • 그러나 메시지가 저장된 곳을 건드려서는 안됨
      • OS가 interrupt를 통해 receiver가 메시지를 받았다고 알려주면 그제서야 메시지가 저장되었던 곳을 사용함
    • Copy on write
      • 논리적으로는 Sender에서 OS로 Copy가 되었지만 실질적으로는 Copy가 안되는 상태..?
Distributed Shared Memory
  • 분산 공유 시스템은 Hardware(Directory based) / OS / 사용자 레벨의 Library에서 구현할 수 있음
False Sharing
  • 서로 다른 CPU가 서로 다른 데이터가 필요한데, 이 데이터들이 하나의 페이지에 있을 경우 마치 sharing처럼 보임
  • false sharing이 발생하면 성능이 많이 떨어져 발생하지 않도록 데이터 배치를 잘 해야함
Multiprocessor Scheduling
  • A Graph-Theoretic Deterministic Algorithm
    • 그래프 이론에 의해 Node들에 어떤 Process를 할당한 것인지 Scheduling
    • 한 노드 안에 Process들은 통신 비용이 없지만, 다른 노드의 Process와 통신할 때에는 비용이 존재
    • 어떻게 최소 비용으로 노드들을 나눌 것인가
  • A Sender-Initiated Distributed Heuristic Algorithm
    • 바쁜 노드가 한가한 노드한테 Process를 나눠줌
    • Sender가 바쁘다고 Broadcast
  • A Receiver-Initiated Distributed Heuristic Algorithm
    • 한가한 노드가 한가하다고 Broadcast
Virtualization
  • Type 1 Hypervisor
    • Hardware에 Hypervisor(가상화 소프트웨어)부터 설치하고 그 위에 Guest OS를 설치하는 방법
    • Hypervisor가 Kernel mode이고, Guest OS와 그 위의 User process가 User mode
      • Guest OS가 Virtual kernel mode, User process는 Virtual user mode
      • Guest OS는 User mode이기 때문에 직접 입출력을 할 수 없고 Hypervisor에게 부탁해야함
  • Type 2 Hypervisor
    • Hardware에 OS를 설치한 후, 그 위에 VMWare(가상화 소프트웨어)를 설치해 Guest OS를 실행하는 방법
  • Paravirtualization
    • Windows나 Linux가 조금만 도와줘도 가상화가 쉬워짐
    • 원래는 Type 1 Hypervisor에서 Guest OS가 입출력을 하면 CPU에서 막았음
    • OS를 조금 수정해 입출력시 Hypervisor를 호출하도록 만듦
Jini
  • 모든 기기들을 Java로 동작하게 만들겠다는 Java의 원대한 꿈