1주차 2 - CodingInterviewStudy/CrackingTheCodingInterview GitHub Wiki

데이터베이스

SQL 문법

  • 명시적 JOIN

    -- ANSI 문법을 사용
    SELECT 
    	CourseName, 
    	TeacherName
    FROM Courses
    INNER JOIN Teachers
    ON Courses.TeacherID = Teachers.TeacherID
  • 묵시적 JOIN

    -- 일반 WHERE JOIN을 사용
    SELECT
    	CourseName,
    	TeacherName
    FROM Courses, Teachers
    WHERE Courses.TeacherID = Teachers.TeacherID

비정규화 vs 정규화

  • 정규화 데이터베이스
    • 중복을 최소화 하도록 설계
    • 데이터의 중복을 최소화 시키지만 여러 테이블로 분리되어 JOIN을 많이 하게 됨
  • 비정규화 데이터베이스
    • 읽는 시간을 최적화 하도록 설계
    • 데이터는 중복되지만 높은 규모 확장성을 실현 할 수 있다.

소규모 데이터 베이스 설계

  1. 모호성 처리
    • 설계를 시작하기 전에 정확히 무엇을 설계해야 하는지 이해해야 한다.
    • 요구사항 정의하는 과정
  2. 핵심 객체 정의
    • 보통 핵심 객체 하나당 하나의 테이블을 사용한다.
  3. 관계 분석
    • 테이블의 관계(다대다인지 일대다인지 등)를 설계한다.
  4. 행위 조사
    • 마지막으로 세부적인 부분을 채워 넣는다.
    • 디테일적으로 마무리 하는 부분

대규모 데이터베이스 설계

  • 대규모의 경우 JOIN 연산이 아주 느리다고 간주하여야 한다.

문제

우유와 요거트가 담긴 장바구니


스레드와 락

자바의 스레드

자바의 모든 스레드는 java.lang.Thread 클래스 객체에 의해 생성되고 제어된다.

main() 메서드를 실행하기 위한 스레드를 주 스레드(main thread)라고 한다.

스레드를 만드는 방법

  • Runnable 인터페이스 사용

    public interface Runnable {
    	void run();
    }
    • Runnable 인터페이스를 구현하는 클래스를 만든다.
    • Thread 타입의 객체를 만들 때, Thread의 생성자에 Runnable 객체를 소유하게 된다.
    • Thread 객체의 start() 메서드를 호출한다.
  • Thread 클래스 상속

    • 항상 run() 메서드를 오버라이드 해야한다.
    • 인스턴스 자체에서 start() 를 직접 호출한다.

Thread 상속 vs Runnable 인터페이스 구현

보통 Runnable 인터페이스를 구현한다.

큰 이유론 자바는 다중 상속을 지원하지 않는다는 점이다. Thread 상속시 다른 클래스를 상속할 수 없는데, Runnable 인터페이스를 구현하면 다른 클래스 상속이 가능하다.

동기화와 락

프로세스 안에서 생성된 스레드들은 같은 메모리 공간을 공유한다. 하지만 두 스레드가 같은 자원을 동시에 변경하는 경우에 문제가 생기는데, 자바는 공유 자원에 대한 접근을 제어하기 위한 동기화(synchronization) 방법을 제공한다.

동기화

synchronized 키워드를 사용할 때는 공유 자원에 대한 접근을 제어한다.

동기화 메서드

해당 키워드는 메서드에 적용할 수도 있고, 특정한 코드 블록에 적용할 수도 있다. 여러 스레드가 같은 객체를 동시에 실행하는 것 또한 방지해준다.

public class MyClass extends Thread {
  private String name;
  private MyObject myObj;
  
  public MyClass(MyObject obj, String n) {
    name = n;
    myObj = obj;
  }
  
  public void run() {
    myObj.foo(name);
  }
}

public class MyObject {
  public synchronized void foo(String name) {
    try {
      System.out.println("Thread " + name + ".foo(): starting");
      Thread.sleep(3000);
      System.out.println("Thread " + name + ".foo(): ending");
    } catch (InterruptedException exc) {
      System.out.println("Thread " + name + ": interrupted.");
    }
  }
}

위의 코드는 synchronized 키워드를 foo() 에 적어두었다.

  • 서로 다른 객체인 경우 동시에 foo() 호출이 가능하다.

    // 가능
    MyObject obj1 = new Object();
    MyObject obj2 = new Object();
    MyClass thread1 = new MyClass(obj1, "1");
    MyClass thread2 = new MyClass(obj2, "2");
    
    thread1.start();
    thread2.start();
  • 서로 같은 객체인 경우 하나만 호출 가능하고 다른 하나는 기다리고 있어야한다.

    // 메서드 대기 처리
    MyObject obj = new Object();
    MyClass thread1 = new MyClass(obj, "1");
    MyClass thread2 = new MyClass(obj, "2");
    
    thread1.start();
    thread2.start();

정적 메서드(static method)는 클래스 락에 의해 동기화 되어 같은 클래스의 정적 메서드는 두 스레드에서 동시에 실행될 수 없다. 설사 동일 클래스의 다른 메서드를 호출한다고 해도 동일하다.

아래는 해당 현상의 예시 코드이다.

public class MyClass extends Thread {
  ...
  public void run() {
    if (name.equals("1")) {
      MyObject.foo(name);
    } else if (name.equals("2")) {
      MyObject.bar(name);
    }
  }
}
#결과
Thread 1.foo(): starting
Thread 1.foo(): ending
Thread 2.bar(): starting
Thread 2.bar(): ending

동기화 블록

메서드만이 아닌 특정 코드 블록을 동기화 할 수도 있다.

public class MyClass extends Thread {
  ...
  public void run() {
    myObj.foo(name);
  }
}

public class MyObject {
  public void foo(String name) {
    synchronized(this) {
      ...
    }
  }
}

메서드와 마찬가지로 MyObject 인스턴스 하나당 하나의 스레드만 synchronized 블록 안의 코드를 실행할 수 있다.

즉, thread1과 thread2가 동일한 MyObject 인스턴스를 바라보고 있다면 둘 중 하나만 해당 코드블록을 실행할 수 있다.

세밀하게 동기화를 제어하고 싶을때는 락(lock)을 사용한다.

락을 공유 자원에 붙이면 자원에 대한 접근을 동기화 할 수 있다. 스레드가 해당 자원을 접근하려면 락을 획득(acquire)해야 하는데, 특정 시점에 락을 쥐고있을 수 있는 스레드는 하나뿐이기 때문에 해당 공유자원은 즉 한번에 한 스레드만이 사용할 수 있다.

public class LockedATM {
  private Lock lock;
  private int balance = 100;
  
  public LockedATM() {
    lock = new ReentrantLock();
  }
  
  public int withdraw(int value) {
    lock.lock();
    int temp = balance;
    
    try {
      Thread.sleep(100);
      temp = temp - value;
      Thread.sleep(100);
      balance = temp;
    } catch (InterruptedException e) { }
    
      lock.unlock();
      
      return temp;
    }
    
    public int deposit(int value) {
      lock.lock();
      int temp = balance;
      try {
        Thread.sleep(100);
        temp = temp + value;
        Thread.sleep(300);
        balance = temp;
      } catch (InterruptedException e) { }
      
      lock.unlock();
      
      return temp;
    }
  }
}

위 코드는 ATM기에서 입금, 인출을 하는 기능을 하는 소스이다. 락을 사용하면 동시에 입금, 인출을 하지 못하기 때문에 자원이 예기치 않게 변경되는 일을 막을 수 있다.

교착상태와 교착상태 방지

교착상태(deadlock)란 첫번째 스레드는 두번쨰 스레드가 들고있는 객체의 락이 풀리기를 기다리고 있고, 두번째 스레드 역시 첫번째 스레드가 들고 있는 객체의 락이 풀리기를 기다리는 상황을 일컫는다. (무한대기)

교착상태가 발생하려면 다음 네가지 조건이 모두 충족되어야 한다.

  1. 상호배제(metal exclusion)
    • 한번에 한 프로세스만 공유 자원을 사용할 수 있다. (정확하게는 공유 자원에 대한 접근 권한이 제한적일 경우)
  2. 들고 기다리기(hold and wait)
    • 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가 해당 접근권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구할 수 있다.
  3. 선취(preemption) 불가능
    • 한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소할 수 없다.
  4. 대기 상태의 사이클(circular wait)
    • 두 개 이상의 프로세스가 자원 접근을 기다리는데 그 관계에 사이클이 존재한다.

교착상태를 해결하기 위해선 이 조건 중 하나를 제거하면된다.

대체적으로 1번 조건은 제거하기 힘들기 때문에 4번 조건인 대기상태의 사이클이 발생하는 일을 막는데 초점을 맞춘다.

문제

쓰레드와 프로세스의 차이점은?

프로세스는 실행중인 프로그램을 의미하며 스레드는 실행 제어만 분리한 것을 의미합니다.

프로세스는 운영체제로부터 자원을 할당 받지만, 스레드는 프로세스를 통해 자원을 할당 받습니다. 한 프로세스 안에 여러개의 스레드가 생성될 수 있으며 각 스레드는 프로세스의 자원을 공유하기 때문에 좀 더 효율적으로 통신할 수 있습니다. 하지만 스레드는 이러한 자원 공유로 인해 문제가 생성될 수 있으니 이를 염두에 둔 프로그래밍을 해야합니다.

해당 방식을 물어보면

  1. synchronized를 통해 임계영역을 설정하는 방식이 있습니다. 비관적 락으로 무조건 적인 스레드 차단을 시킵니다.
  2. volatile을 통해 무조건 변수를 main memory에서 읽도록 하여 가장 최신의 값을 보장하게 하여 값 불일치를 해소합니다. (cpu 캐시보다 main memory가 비용이 더 크기 때문에 변수값 일치를 보장해야 할 경우에만 사용하는것이 좋음)

자바에서는 concurrent 패키지가 제공하는 쓰레드 세이프 자료구조를 통해 자원을 사용할 수 있습니다.

멀티 프로세스와 멀티 쓰레드 차이점은?
  • 멀티 프로세스 : [데이터 영역, 힙, 스택 ]영역 모두비공유
  • 멀티 쓰레드 : [ 데이터 영역, 힙, 스택 ]영역중 스택 영역만 비공유
⚠️ **GitHub.com Fallback** ⚠️