HTTP, DNS 둘 다 Application Layer Protocol 로서 Transport Layer Protocol 인 TCP 와 UDP 를 사용한다. HTTP 가 TCP 기반이라는 것은 잘 알려져 있다. 그렇다면 DNS 는 어떤 프로토콜을 사용할까 ? 직관적으로 생각하면 데이터가 유실되면 안 되기 때문에 TCP 를 사용할 것만 같다. 하지만 현재 DNS 는 UDP 를 사용한다. 그렇다면 데이터 유실을 감수하고도 왜 DNS 는 UDP 기반으로 동작하는 것일까 ? 실제 TCP 는 UDP 에 비해 데이터를 담고, 보내는 전송 과정에서 딜레이가 있다. DNS 는 단지 아주 크기가 적은 데이터인 주소만 알면 되는데, TCP 는 너무 오래 걸린다. 그럼 데이터 유실 문제는 어떻게 할까 ? HTTP 커뮤니케이션에서는 HTTP Response 내 데이터 양이 매우 많을 수도 있고, 대량의 데이터가 유실되는 것은 큰 문제가 될 수 있다. 그러나 DNS 의 경우 DNS Query 내 Response 에 들어가는 데이터 자체가 매우 작다. 호스트 네임을 전송하고, IP 주소를 받아오는 것이 끝이므로 데이터 자체가 몇 바이트 채 되지 않는다. 유실될 확률이 적을 뿐더러, 유실이 되더라도 큰 부담이 없다. 무엇보다 UDP 기반으로 동작하는 것이 빠르고, TCP 보다 현실적으로 훨씬 효율적이다. 따라서 DNS는 현재 UDP 기반으로 동작한다.
소켓 (Socket)
An interface between applicatioin and network
The application creates a socket
The socket type dictates the style of communication
reliable vs best effort
connection-oriented vs connectionless
Once configured, the application can
pass data to the socket for networt transmission
receive data from the socket (transmitted through the networt by some other host)
소켓의 종류 (Two essential types of sockets)
SOCK_STREAM
a.k.a. TCP
reliable delivery
in-order guaranteed
connection-oriented
bidirectional
SOCK_DGRAM
a.k.a. UDP
unreliable delivery
no order guarantees
no notion of "connection"
app indicates dest, for each packet
can send or receive
Socket Functions (TCP case)
TCP 기반의 소켓 통신을 위한 C 언어 함수에 대해 알아본다.
아래와 같은 순서로 함수를 호출하여 클라이언트와 서버를 연결한다.
TCP Server
socket():이 함수를 call 하며 Socket API 를 사용을 시작한다. socket 함수의 파라미터로 TCP Socket, UDP Socket 을 정할 수 있다.
bind() : 생성한 Socket 을 몇 번 port 에 장착할지 정한다.
listen() : 서버에 특화된 함수이다. 이 소켓을 듣는 용도로 쓰겠다는 것이다. 즉, 서버이므로 액션을 취하는 것이 아니라 클라이언트를 기다리는 것을 의미한다.
accept() : bloking 함수이다. 클라이언트로부터 Request 가 올 때까지 기다린다.
blocks until connection from client
TCP Client
socket(): 역시 Socket 을 시작한다.
connect() : 상대 Server 에 TCP connection 을 맺는다. 서버 주소 등이 들어간다. bloking 함수이다.
TCP three-way handshaking
연결 후, TCP Client 는 write()를 통해 데이터를 요청하고, TCP Server 는 read() 를 통해 데이터를 처리하는 것을 반복한다.
두 함수 역시 blocking 함수이다.
통신 완료 후, close()를 통해 소켓을 종료한다.
UDP 기반 소켓 통신은 간단하다. Server 측에서 Socket 을 열고 Bind 하면, Client 측에서도 Socket 을 열고 바로 통신하면 된다.
캐시 일관성이란 각각 클라이언트의 로컬 캐시 데이터와 메인 공유 메모리의 데이터가 모두 일치하는 것을 의미한다. 캐시 일관성이 지켜지지 않는 상황을 두고 캐시 일관성 문제라고 한다.각 클라이언트가 자신 만의 로컬 캐시를 가지고 다른 여러 클라이언트와 메모리를 공유하고 있을 때, 캐시의 갱신으로 인해 데이터 불일치 문제가 발생할 수 있다. 이러한 문제를 방지하고, 캐시 일관성을 유지하기 위해서 사용하는 방법 중 하나는 Conditional GET 이다.
한양대학교 이석복 교수님의 2017년 2학기 컴퓨터 네트워크 강의를 듣고 정리한 글입니다.
캐시 일관성이란 각각 클라이언트의 로컬 캐시 데이터와 메인 공유 메모리의 데이터가 모두 일치하는 것을 의미한다. 캐시 일관성이 지켜지지 않는 상황을 두고 캐시 일관성 문제라고 한다. 각 클라이언트가 자신 만의 로컬 캐시를 가지고 다른 여러 클라이언트와 메모리를 공유하고 있을 때, 캐시의 갱신으로 인해 데이터 불일치 문제가 발생할 수 있다. 이러한 문제를 방지하고, 캐시 일관성을 유지하기 위해서 사용하는 방법 중 하나는 Conditional GET 이다.
Conditional GET
don't send object if cache has up-to-date cached version
no object transmission delay
lower link utilization
if-modified-since: <date> HTTP 요청 헤더는 날짜와 시간 정보를 담고 있으며, 조건부 요청이다. 서버는 지정된 날짜 이후 수정이 되었다면 HTTP Status 200 과 함께 요청된 리소스 (Object)를 돌려준다. 하지만 만약 수정되지 않은 리소스에 대한 요청은 리소스 없이 HTTP Status 304 (Not Modified) 응답을 한다.
여기까지는 HTTP 프로토콜에 대한 이야기이다.
이제부터 또 다른 애플리케이션 프로토콜인 DNS 에 대해 알아본다.
DNS (Domain Name System)
How to map between IP address and name, and vice versa ?
distributed database : implemented in hierarchy of many name servers
application-layer protocol : hosts, name servers communicate to resolve names
프로세스와 프로세스 간의 커뮤니케이션을 위해서는 다른 머신에 존재하는 프로세스를 지칭하기 위해 주소가 필요하다. 즉, 인터넷 상의 한 컴퓨터에서 다른 컴퓨터로 데이터를 주고 받으며 통신하기 위해서는 주소를 알아야 한다. IP 주소와 Port 번호가 바로 해당 주소라고 할 수 있다. Port 번호는 통상적으로 고정된 번호가 있다. 예를 들어 HTTP 는 80으로 고정되어 있다. 그러나 IP 주소는 32 bit 로 이루어진 고유한 주소이다. 이를 일일이 기억하기는 어렵다. 친구들에게 연락하기 위한 전화번호를 일일이 외우기 힘든 것처럼 말이다. 그래서 마치 전화번호부와 같이 알아보기 쉬운 영단어 (Name Server)를 각 주소와 매핑시키자는 생각에서 DNS 개념이 생겨났다. 예를 들어 구글의 Name Server는 www.google.com 이고, IP Address는 123.xxx... 인 것이다. 이는 좋은 방법이지만 문제는 세계의 모든 서버 정보가 저장된 하나의 데이터베이스에 Access 하여 사용하기 어렵다는 것이다. 데이터도 무수히 많고, 검색 시간도 방대하다. 또한, 비유를 하자면 DNS는 상대방에게 전화를 걸기 위한 준비 운동과 같다. 핵심은 상대방에게 전화를 거는 것이지만 이 DNS는 전화를 걸기 위해 전화번호부를 찾아보는 부가적인 행동이기 때문이다.
분산 시스템
무엇보다 만약 정전으로 인해 서버가 잠시 다운된다면 전세계 사람들은 웹 브라우저를 사용하는데 어려움을 겪게 될 것이라는 치명적인 문제 (SPOF)를 안고 있다. 따라서 지금은분산 시스템으로 구조화되어 존재한다.
" SPOF (single point of failure, 단일 장애점) "
시스템 구성 요소 중에서, 동작하지 않으면 전체 시스템이 중단되는 요소를 말한다.
DNS Query
도메인 이름을 웹 브라우저에 입력할 때 최종 사용자를 어떤 서버에 연결할 것인지를 제어한다.
이 요청을 쿼리라고 부른다.
DNS Query 방법에는 두 가지가 있다.
반복적 질의 (Iterative Query)
최종 IP 주소를 받을 때까지 요청과 응답을 계속해서 Local DNS 서버가 반복한다. 클라이언트 입장에서는 Root 에 접근할 일이 거의 없다.
재귀적 질의 (Recursive Query)
사용자가 Local DNS 서버에 Query 를 보내면 Local DNS 서버가 Root Name 서버에 Query를 보내고, Root Name 서버는 자신의 서버에 없다면 해당 TLD 서버에 요청하는 식으로, 실제 도메인 정보를 가지고 있는 서버까지 Query가 이동하여 IP 주소를 재귀적으로 얻는다.
contacted by local name server that ccan not resolve name
contacts authoritative name server if name mapping not known
gets mapping
returns mapping to local name server
💡 TLD, authoritative servers
top-level domain (TLD) servers
responsible for com, org, net, edu, aero, jobs, museums, and all top-level country domains (e.g. uk, fr)
network solutions maintains servers for .com TLD
educause for .edu TLD
authoriative DNS servers
organization's own DNS server(s), providing authoritative hostname to IP mappings for organization's named hosts
can be maintained by organization or service provider
second-level domain (SLD) servers
DNS records
distributed db storing resource records (RR)
RR format : (name, value, type, ttl)
권한 있는 DNS 서버에 있는 명령으로서, 도메인에 연계된 IP 주소 및 해당 도메인에 대한 요청의 처리 방법에 대한 정보를 제공한다. 이 레코드는 DNS 구문이라고 하는 일련의 텍스트 파일로 구성된다. DNS 레코드에는 일반적으로 Name, Value, Type, TTL 이 있다.Type 에 따라 레코드가 의미하는 바가 결정이 된다. 여러 type 중, A 와 NS 가 있다.
type = A
name is hostname
value is IP address
type = NS
name is domain
value is hostname of authoritative name server for this domain
🔎 TTL (Time to live) 컴퓨터나 네트워크에서 데이터의 유효 기간을 나타내기 위한 방법이다.
DNS 에서 권한 있는 네임서버는 특정 리소스 레코드의 TTL 값을 설정한다. 재귀적 (recursive) 캐시 네임서버가 권한있는 네임서버에 질의를 보낼 때, 캐시 네임서버는 그 레코드를 TTL 값에 해당하는 시간동안 캐시에 저장해 둔다.
추후 스터브 리졸버(stub resolver)가 캐시 네임서버에 동일한 레코드에 대한 질의를 보냈을 때, 해당 레코드의 TTL 값이 아직 만료되지 않았다면 캐시 네임서버는 권한있는 네임서버에 질의를 보낼 필요 없이 캐시에 저장된 정보를 이용해 바로 응답을 하게 된다. 네임서버는 특정 도메인이 존재하지 않음을 나타내는 NXDOMAIN 응답에 대해서도 TTL 값을 가질 수 있다. 다만 이 경우에는 일반적으로 그 값이 최대 3시간 정도로 짧다.
TTL 값이 짧으면 상위의 권한있는 네임서버에 가해지는 부하가 커진다는 단점이 있지만, 반면에 메일 교환 레코드(mail exchange record)와 같이 주소 변경에 민감한 서비스에 적합하다는 장점을 가진다. 이 때문에 특정 서비스의 주소가 옮겨지는 경우, 이로 인한 혼란을 최소화하기 위해 DNS 관리자는 관련 레코드의 TTL 값을 낮춘다.
로버트 마틴 (Robert C. Martin)이 2000년대 초반에 명명한 객체 지향 프로그래밍 및 설계의 다섯 가지 기본 원칙을 마이클 페더스 (Michael C. Feathers)가 두문자어 기억술로 소개한 것이다. 프로그래머가 시간이 지나도 유지 보수와 확장이 쉬운 시스템을 만들고자 할 때 이 원칙들을 함께 적용할 수 있다.
컴퓨터 프로그래밍에서 SOLID란 로버트 마틴 (Robert C. Martin)이 2000년대 초반에 명명한 객체 지향 프로그래밍 및 설계의 다섯 가지 기본 원칙을 마이클 페더스 (Michael C. Feathers)가 두문자어 기억술로 소개한 것이다. 프로그래머가 시간이 지나도 유지 보수와 확장이 쉬운 시스템을 만들고자 할 때 이 원칙들을 함께 적용할 수 있다. SOLID 원칙들은 소프트웨어 작업에서 프로그래머가 소스 코드가 읽기 쉽고 확장하기 쉽게 될 때까지 소프트웨어 소스 코드를 리팩터링하여 코드 냄새를 제거하기 위해 적용할 수 있는 지침이다. 이 원칙들은 애자일 소프트웨어 개발과 적응적 소프트웨어 개발의 전반적 전략의 일부이다.
: 프로그래머는 추상화에 의존해야지, 구체화에 의존하면 안된다. 의존성 주입은 이 원칙을 따르는 방법 중 하나이다. 상위 모듈은 하위 모듈에 의존하면 안된다.
Single Responsibility Principle, SRP
• 단일 책임 원칙
• “ There should never be more than one reason for a class to change. ”
• 한 클래스는 하나의 책임 (axis of change)만 가져야 한다.
• 어떤 변화에 의해 클래스를 변경해야 하는 이유는 오직 하나 뿐 이어야 한다.
• 책임은 “ 캡슐화 ” 한다.
•.응집도 (Cohesion)를 높이고 결합도 (Coupling)를 낮춘다.
• 가독성이 향상되고, 유지보수가 용이해진다.
• 다른 원칙들을 적용하는 기초가 된다.
📌 Extract Class
Extract Class는 마틴 파울러의 책 <Refactoring: Improving the Design of Existing Code>2에서 소개된 클래스를 분리하는 객체지향 리팩토링의 한 방법이다. 이 책에서 소개하는 대부분의 위험상황에 대한 해결방법은 직/간접적으로 SRP 원리와 관련이 있다. 항상 코드를 최상으로 유지한다는 리팩토링의 근본정신도 항상 객체들의 책임을 최상의 상태로 분배한다는 것에서 비롯되기 때문이다. Extract Class는 두 개의 클래스가 해야 할 일을 하나의 클래스가 하고 있는 경우, 새로운 클래스를 만들어서 예전 클래스에서 새로운 클래스로 옮기는 것을 의미한다. 객체지향 설계에서 클래스는 분명히 추상화되어야 하고, 명확한 책임을 가져야 한다.
Move Method
메소드가 자신이 정의된 클래스보다 다른 클래스의 기능을 더 많이 사용하고 있다면, 이 메소드를 가장 많이 사용하고 있는 클래스에 비슷한 몸체를 가진 새로운 메소드를 만들고, 이전 메소드는 간단한 위임으로 바꾸거나 완전히 삭제한다.
Move Field
필드가 자신이 정의된 클래스보다 다른 클래스에 의해 더 많이 사용되고 있다면, 타겟 클래스에 새로운 필드를 만들고 기존 필드를 사용하는 모든 부분을 변경한다.
Open Closed Principle, OCP
• 개방 폐쇄의 원칙
• “ You should be able to extend a classes behavior, without modifying it. ”
• 소프트웨어는 확장에는 열려 있어야 하고, 변경에는 닫혀 있어야 한다.
•.요구사항의 변경이나 추가사항이 발생하더라도 기존 구성요소에는 수정이 일어나지 않아야 한다.
• 쉽게 확장이 가능하여 재사용이 가능하도록 구성되어야 한다.
• 변하는 것은 숨기고 변하지 않는 것에 의존한다.
• 변하는 것과 변하지 않는 것을 엄격히 구분한다.
• 관리와 재사용이 가능한 코드를 만드는 기반이 된다.
• “ 추상화 ”는 OCP 의 핵심요소이다.
개방 폐쇄의 원칙은 버틀란트 메이어 (Bertrand Meyer)가 1998년 책 3에서 정의한 개념이다. 소프트웨어 구성요소 (컴포넌트, 클래스, 모듈, 함수)는 확장에는 열려있고, 변경에는 닫혀있어야 한다는 원리이다. 즉, 변경을 위한 비용은 가능한 줄이고, 확장을 위한 비용은 가능한 극대화 해야 한다는 것이다. 버틀란트 메이어는 이 원칙을 적용하기 위해 상속을 사용해야 한다고 했다. 하지만 상속은 서브 클래스가 구현에 의존하는 경우 슈퍼 클래스의 세부 정보와 긴밀히 결합한다. 따라서, SOLID 원칙을 정리한 로버트 마틴 (Robert C. Martin)은 개방 폐쇄의 원칙을 인터페이스를 사용하여 행위 (behavior)를 정의하고, 정의된 코드를 쉽게 대체할 수 있는 다양한 구현을 허용하도록 하였다. 또한, OCP의 주요한 메커니즘은 추상화와 다형성이라고 하였다.
📌 그래디 부치 (Grady Booch)가 말하는 추상화란 ?
다른 모든 종류의 객체로부터 식별될 수 있는 객체의 본질적인 특징이다.
Liskov Substitution Principle, LSP
• 리스코프 치환 원칙
• “ Functions that use pointers or references to base classes must be able to use objects of derived objects of derived classes without knowing it. ”
• Sub type은 언제나 Super type을 대체할 수 있어야 한다.
• 계약에 의한 설계 (Design by Contract)와 유사성을 지닌다.
• OCP를 위반하지 않도록 하는 기반 원칙이다.
• 행동적 하위형 (Behavioral Subtype) : 객체에 대한 대체 가능성 (Notion of substitutability for object)을 정의한다.
• LSP를 위반하는 전형적인 예로 Circle-ellipse Problem이 있다.
📌 Signature 요구사항
• 서브 타입에서 메소드 파라미터 타입은 반공변성 (Contravariance)
• 서브 타입에서 메소드 return 타입의 공변성 (Covariance)
• 서브 타입에서 메소드는 상위 클래스의 메소드에서 throw한 하위형을 제외하고 새로운 예외를 던질 수는 없다.
📌 Sub type의 행동 조건
• 서브 타입에서 선행 조건 (pre-condition)은 강화될 수 없다.
• 서브 타입에서 후행 조건 (Post-condition)은 약화될 수 없다.
• 서브 타입에서 수퍼 타입의 불변형은 반드시 유지되어야 한다.
• 이력 제약 조건 (History constraint - History rule)
• 객체는 그 자신의 메소드를 통해서만 수정 (캡슐화) 될 수 있는 것으로 간주된다.
• 따라서 변경 가능 지점 (mutable point)을 변경 불가 지점 (immutable point)의 서브 타입으로 만든다.
📌 공변성 (Convariance)와 반공변성 (Contravariance)
• 공변성 : 한 변수가 변하면 다른 변수도 변하는 성질
• 반공변성 : 그 반대의 성질
Interface Segregation Principle, ISP
• 인터페이스 분리 원칙
• “ Clients should not be foreced to depend upon interfaces that they do not use. ”
• 범용 인터페이스보다 특정 클라이언트를 위한 인터페이스 여러 개를 선언한다.
• 시스템 내부 의존성을 약화시켜 리팩토링, 수정, 재배포를 쉽게 할 수 있도록 한다.
인터페이스 분리 원칙은 자신이 사용하지 않는 인터페이스는 구현하지 말아야 한다는 원칙이다. 즉, 하나의 큰 인터페이스를 상속받기 보다는 인터페이스를 구체적이고 작은 단위들로 분리시켜 꼭 필요한 인터페이스만 상속하자는 의미이다. SRP는 클래스의 단일 책임을 강조한다면 ISP는 인터페이스의 단일 책임을 강조한다.
Dependency Inversion Principle, DIP
• 의존 관계 역전 원칙
• “High level modules should not depend upon low level modules. Both should depend upon abstractions.”
• “Abstractions should not depend upon details. Details should depend upon abstractions.”
• 추상화에 의존해야 하고, 구체화에 의존하면 안된다.
• 상위 모듈은 하위 모듈에 의존해서는 안된다.
• “상위와 하위 객체 모두 동일한 추상화에 의존해야 한다”는 객체지향 설계의 대원칙을 제공한다.
의존 관계 역전 원칙은 추상화에 의존하고, 세부 사항에 의존해서는 안된다는 원칙이다. 클래스 사이에 의존 관계는 당연히 존재하지만, 최대한 추상화된 클래스에 의존하라는 것이다. Java의 인터페이스와 같은 타입에 기반한 응용 프로그램을 작성하라는 의미이기도 하다. DIP의 키워드는 ‘IOS’, ‘훅 메소드’, ‘확장성’이다.
평범한 배낭이지만 절대 평범하지가 않다. 알고 보니 배낭 문제 (knapssack problem)로 Dynamic Programming의 대표적인 문제라고 한다. Knapsack Algorithm이라고도 불리는 배낭 문제는 두 가지 문제로 분류된다. 짐을 쪼갤 수 있는 경우와, 짐을 쪼갤 수 없는 경우이다. 전자는 Fraction Knapsack Problem이라고 하고, Greedy를 사용한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] dp = new int[N + 1][K + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
int W = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
for (int j = 1; j <= K; j++) {
if (j < W) {
dp[i][j] = dp[i - 1][j];
continue;
}
dp[i][j] = Math.max(V + dp[i - 1][j - W], dp[i - 1][j]);
}
}
System.out.println(dp[N][K]);
}
}
일부 작은 조각이 전체와 비슷한 기하학적 형태를 말한다. 이런 특징을 자기 유사성이라고 한다. 즉, 자기 유사성을 갖는 기하학적 구조를 프랙탈 구조라고 한다. 프랙탈 구조는 자연물에서 뿐만 아니라 수학적 분석, 생태학적 계산, 위상 공간에 나타나는 운동모형 등 곳곳에서도 발견되어 자연이 가지는 기본적인 구조이다. 프랙탈은 수학적 도형으로도 연구되고 있다고 한다. 프랙탈 도형은 종종 컴퓨터 소프트웨어를 이용한 재귀적이거나 반복적인 작업에 의한 반복되는 패턴으로 만들어진다.
프랙탈 트리 (Fractal Tree)
프랙탈 구조가 나무의 모양인 프랙탈 트리를 Java를 이용해 재귀 함수로 그려볼 수 있다. 가지를 그리기 위해서 삼각함수를 이용한다.
import java.awt.Frame;
import java.awt.Graphics;
/**
* FractalTree.
*/
public class FractalTree extends Frame {
int startX;
int startY;
int angle;
int length;
int rotate;
int growth;
int depth;
/**
* Constroctors.
*
* @param width width
* @param height height
* @param x x
* @param y y
* @param angle angle
* @param length length
* @param rotate rotate
* @param growth growth
*/
public FractalTree(int width, int height, int x, int y,
int angle, int length, int rotate, int growth) {
this.startX = x;
this.startY = y;
this.angle = angle;
this.length = length;
this.rotate = rotate;
this.growth = growth;
this.setSize(width, height);
}
/**
* Paint branch.
*
* @param graphics graphics
* @param startX startX
* @param startY startY
* @param degree degree
* @param length length
*/
public void branch(Graphics graphics, int startX, int startY, int degree, int length) {
if (length > 1) {
int endX = (int) (startX - length * Math.cos(Math.toRadians(degree)));
int endY = (int) (startY - length * Math.sin(Math.toRadians(degree)));
int branchLength = (int) (length * growth * 0.01);
graphics.drawLine(startX, startY, endX, endY);
branch(graphics, endX, endY, degree - rotate, branchLength);
branch(graphics, endX, endY, degree + rotate, branchLength);
}
}
@Override
public void paint(Graphics graphics) {
branch(graphics, startX, startY, this.angle, this.length);
}
public static void main(String[] args) {
FractalTree tree = new FractalTree(500, 500, 250, 450, 90, 100, 30, 75);
tree.setVisible(true);
}
}
정말 아무리 뜯어봐도 모르겠던 개념들도 이제는 이해하고 구현하기 위해 고민해 볼 수라도 있다는 게 신기하다. 물론 아직 잘 풀지는 못하지만 ,,, 모르더라도 마음을 편히 가지고 유사한 유형의 문제를 자주 접하면 체화되는 것 같다.
⏰ 기간
2022년 7월 즈음부터 9월 즈음까지 백준에서 약 100문제를 풀었다. 프로젝트랑 병행하느라 뜨문뜨문 풀었다. 9월 중순부터는 알고리즘 스터디를 시작하며 프로그래머스 기출문제들로부터 호되게 당했다 (?) 특히 카카오 ,,^^ 지금 보니 프로그래머스에서는 63문제 풀었다. 기출보다 알고리즘 개념 유형을 익히고 싶어서 한 달 전 백준으로 다시 돌아왔다. 현재는 백준에서 작고 귀엽게 총 145문제 풀었다.
🔎 공부
주로 단계별로 풀어보기 순으로 풀었다. 문제를 읽고 손으로 정리하면서 문제를 접근하는 방법에 대해 고민하고 풀었다. 머릿속이 아득해지는 문제가 있다면 경험상 오래 끙끙 고민하는 것보다는 적당히 고민한 후 구글링을 통해 풀이 방법을 참고해서 공부하는 게 좀 더 효율적인 것 같다. 그리고 알고리즘 스터디를 통해 팀원들과 코드 리뷰를 하면서 함께 풀어나가는 것도 좋았다.
💪앞으로
이제 목표는 플래티넘이다 ,,!
NHN 아카데미 + 정보처리기사 필기 공부랑 겹쳐서 당분간 몰두하지는 못하겠지만 그래도 꾸준히 풀어나가자 !
대부분의 리눅스 배포판은 서버용으로 사용되고 있지만 우분투는 개인 사용자 데스크톱 환경에 최적화되도록 사용자 편의를 중점으로 개발이 된 특징이 있다.
Window 10은 다른 OS보다 성능이 낮다고 한다. 우분투 역시 동일한 프로그램에서 Window 10보다 더 나은 성능을 보여준다고 한다. 그리고 심플한 UI를 가지고 있다고 하는데 ,, 그건 경험해 봐야 알겠다.
💡 주피터 노트북 (Jupyter notebook)
주피터 노트북은 오픈소스 기반의 웹 플랫폼으로, 파이썬을 비롯한 다양한 프로그래밍 언어로 코드 작성 및 실행하는 개발 환경을 말한다고 한다. 즉, Jupyter에서 제작한 Python 용 통합 개발 환경(IDE)이다. 실행해 보며 신기했던 점은 터미널에서 주소로 들어가면 웹 사이트가 나온다는 것이다. 웹 기반이라니 ! 주피터 노트북은 데이터 분석에 유용하게 사용이 될 수 있다고 한다. 최근 들어 머신러닝, 딥러닝에 많이 활용이 된다고 한다. 아래는 주피터 노트북의 특징이다.
- 단계적으로 쉽게 실행하고, 시각적으로 빠르게 확인해 볼 수 있다.
- 큰 Python 파일도 셀 단위로 나누어 번역 및 실행하며 Interactive 한 동작이 가능하다.
➳ 교착상태이다. 즉, 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태이다.
Resource (자원)
➳ 하드웨어, 소프트웨어 등을 포함하는 개념이다.
➳ e.g. I/O device, CPU cycle, memory space, semaphore 등
➳프로세스가 자원을 사용하는 절차 : Request - Allocate - Use - Release
Deadlock 발생의 4가지 조건
1. Mutual exclusion (상호 배제)
➳ 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
2. No Preemption (비선점)
➳ 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지는 않는다.
3. Hold and wait (보유 대기)
➳ 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다.
4. Circular wait (원형 대기)
➳ 자원을 기다리는 프로세스 간에는 사이클이 형성되어야 한다.
이러한 Deadlock 이 발생하지 않도록 처리하는 방법에 대해서 알아본다.
그 전에 자원과 프로세스의 관계를 그림으로 표시하는 하나의 방법을 알아본다.
이것을 자원할당그래프라고 한다.
Resource-Allocation Graph (자원할당그래프)
자원에서 프로세스로 향하는 화살표의 의미는 해당 자원을 해당 프로세스가 점유하고 있다는 의미이다. 반대로 프로세스로부터 자원으로 향한는 화살표의 의미는 해당 프로세스가 애타게 해당 자원을 기다리고 있다는 의미이다. 자원 사각형 안 여러 개의 동그라미는 해당 자원의 인스턴스가 여러 개라는 의미이다. 1번 자원은 한 개, 2번 자원은 두 개, 4번 자원은 3개라는 의미이다.
💡 그래프에 cycle이 없으면 deadlock이 아니다.
💡 그래프에 cycle이 있으면
➳ if only one instance per resource type, then deadlock
➳ if serveral instances per resource type, possibility of deadlock
자원할당그래프를 활용해 deadlock을 판가름해보자 !
왼쪽 그래프와 같은 경우는 deadlock이다. 비록 자원 2의 instance가 두 개이지만 cycle도 두 개 존재하기 때문이다.
오른쪽 그래프와 같은 경우는 cycle이 있지만 자원의 instance가 두 개이므로 deadlock이 아니다.
Deadlock의 처리 방법
1. Deadlock Prevention
➳ 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것이다.
2. Deadlock Avoidance
➳ 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당한다.
➳ 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다.
3. Deadlock Detection and Recovery
➳ deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover 한다.
4. Deadlock Ignorance
➳ deadlock을 시스템이 책임지지 않는다.
➳ UNIX를 포함한 대부분의 OS가 채택한 방법이다.
1, 2번은 deadlock을 미연에 방지한다. 3,4번은 deadlock을 그냥 놔둔다.
Deadlock Prevention
Mutual Exclusion
➳ 공유해서는 안되는 자원의 경우 반드시 성립해야 한다.
No Preemption
➳ process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
➳ 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
➳ state를 쉽게 save 하고 restore 할 수 있는 자원에서 주로 사용한다. (CPU, memory)
Hold and Wait
➳ 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
➳방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법이다.
➳방법 2 : 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청한다.
Circular Wait
➳ 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.
➳ 만약 순서가 3인 자원을 보유 중인 프로세스가 순서가 1인 자원을 할당받기 위해서는 우선 보유한 자원을 release 해야 한다.
🌀 Utilization 저하, throughput 감소, starvation 문제 - 비효율적 !
Deadlock Avoidance
자원 요청에 대한 부가 정보를 이용해서 자원 할당이 deadlock으로부터 안전 (safe)한지를 동적으로 조사해서 안전한 경우에만 할당한다. 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.
시스템이 safe state에 있으면 ➳ no deadlock
시스템이 unsafe state에 있으면 ➳ possibility of deadlock
즉, Deadlock Avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장한다.
2가지 경우의 avoidance 알고리즘
➳ Single instance per resource types
• Resource Allocation Graph algorithm 사용
➳ Multiple instances per resource types
• Banker's Algorithm 사용
safe state
➳ 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태이다.
safe sequence
Resource Allocation Graph algorithm
점선으로 된 화살표는 프로세스가 자원을 평생에 걸쳐 자원을 요청하는 시기가 있을 수 있다는 의미이다. 점선까지 고려하여 deadlock이 예상되는 cycle을 생각한다. 미래의 deadlock을 미리 걱정하고, 방지하므로 무조건 현재 안전하다.
Banker's Algorithm
🌀 가정
➳ 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.
➳ 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 자원을 다시 반납한다.
🌀 방법
➳ 기본 개념 : 자원 요청 시 safe 상태를 유지할 경우에만 할당한다.
➳ 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택한다.
•그런 프로세스가 없으면 unsafe 상태이다.
•그런 프로세스가 있으면 그 프로세스에게 자원을 할당한다.
➳ 할당받은 프로세스가 종료되면 모든 자원을 반납한다.
➳ 모든 프로세스가 종료될 때까지 이러한 과정을 반복한다.
Example of Banker's Algorithm
Deadlock Detection and Recovery
Detection
Resource type 당 single instance인 경우,
➳ 자원할당 그래프에서의 cycle이 곧 deadlock을 의미한다.
Resource type 당 multiple instance인 경우,
➳ Banker's algorithm과 유사한 방법을 활용한다.
Wait-for graph 알고리즘
➳ Resource type 당 single instance인 경우에 사용한다.
➳ 자원할당 그래프의 변형된 알고리즘이다.
➳ 프로세스만으로 node를 구성한다.
➳ 프로세스 A가 가지고 있는 자원을 프로세스 B가 기다리는 경우 : 프로세스 B ➳ 프로세스 A
➳ Wait-for graph에 cycle이 존재하는지를 주기적으로 조사한다.
➳ O(n^2)
Resource type 당 single instance인 경우
위 그래프는 cycle이 존재하므로 deadlock이다.
오른쪽 그래프는 왼쪽 그래프에서 자원을 빼고, 프로세스에서 프로세스로 화살표를 연결하여 표시한다.
Wait-for graph로 보면 cycle을 조금 더 빨리 찾을 수 있다고 한다.
Resource type 당 multiple instance인 경우
여유 자원이 있으면 무조건 준다. 자원을 다 사용하면 다시 반납할 것이라고 생각하기 때문이다. Banker's algorithm 보다 훨씬 긍정적으로 생각한다. 대신 detection을 한다. 현재의 deadlock을 생각한다.
아래의 경우 deadlock이 발생한다.
Recovery
Process termination
➳ Abort all deadlocked processes
➳ Abort one process at a time until the deadlock cycle is eliminated
Resource Preemption
➳ 비용을 최소화할 victim의 선정
➳ safe state로 rollback하여 process를 restart
➳ Starvation 문제
• 동일한 프로세스가 계속해서 victim으로 선정되는 경우
• cost factor에 rollback 횟수도 같이 고려
Deadlock Ignorance
deadlock이 일어나지 않는다고 생각하고, 아무런 조치도 취하지 않는다. deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다. 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처한다. UNIX, Window 등 대부분 범용 OS가 채택한다.
Monitor는 공유 데이터에 대한 접근은 오직 Monitor 안에 정의된 함수를 통해서만 접근이 가능하도록 하고, Monitor 안에서 active 하게 실행되는 프로세스는 하나로 제한한다. 따라서 프로그래머는 lock을 걸 필요 없이 Monitor 안에 있는 코드로 데이터에 접근하도록 하면 알아서 동기화가 된다.
이전 글에서는 프로세스 동기화의 문제점과 이 문제를 해결하기 위한 초기 알고리즘 3가지를 알아보았다.
Synchronization Hardware는 앞서 나온 알고리즘들의 한계점을 보안해 준다.
이제는 좀 더 추상적인 동기화 문제 해결 방안 두 가지를 알아본다.
바로 세마포어 (Semaphore)와 모니터 (Monitor)이다.
이 방안들은 프로그래머로 하여금 더욱 쉽고 효율적으로 문제를 해결할 수 있도록 도와준다.
Semaphore
➳ 이전 글에서 나온 방식들을 추상화시킨다.
➳ Semaphore S
• integer variable
• 아래 두 가지 atomic 연산에 의해서만 접근이 가능하다.
P 연산은 자원을 획득하는 과정이고, V 연산은 자원을 반납하는 과정이다.
예를 들어 Semaphore 5라면 자원이 5라는 의미이다. 만약 프로세스 5개가 동시에 P 연산을 하면 모든 자원을 쓰고 있게 된다. 다른 프로세스가 자원을 획득하고 싶어도 자원의 여분이 없다면 기다려야 한다. 자원의 사용은 P 연산과 V 연산 사이에서 이루어진다. 자원을 다 사용했다면 V 연산을 통해 자원을 내놓게 된다. S는 자원을 count 한다고 볼 수도 있다.
Critical Section of n Processes
mutex : mutual exclusion의 줄임말
여기에서도 쓸데없이 while문을 도는 busy-wait 문제가 있다. 이는 어떻게 해결하면 좋을까 ?
Block / WakeupImplementation
value 값과 줄을 세우는 list 구조를 둔다. 만약 Semaphore 여분이 없어 기다려야 한다면 변수 L에 대해서 프로세스를 block 시키고, 줄을 세워서 기다리게 한다. 이는 busy-wait 문제를 해결해 준다. busy-wait는 spin lock이라고도 부른다. 따라서 block/wakeup 방식을 sleep lock이라고 부르기도 한다.
이제 Block/Wakeup 방식으로 Semaphore 연산을 정의해 보자 !
P 연산은 자원을 획득하므로 value 값에 1을 빼준다.
S.value가 음수라면 S.L (Semaphore list)에 Block 시킨다.
V 연산은 자원을 내놓으므로 value 값에 1을 더한다.
S.value가 0 이하라면 S.L에서 하나를 꺼내 깨워준다.
Which is better ?
" busy-wait VS block/wakeup "
일반적으로는 block/wakeup이 훨씬 낫다. 하지만 block 하고 wakeup 하는 것도 어떻게 보면 overhead라고 볼 수도 있다.
➳ block/wakeup overhead VS critical section 길이로 판단한다.
• critical section의 길이가 긴 경우 block/wakeup이 적당하다.
• critical section의 길이가 매우 짧은 경우 block/wakeup overhead가 busy-wait overhead보다 더 커질 수가 있다.
• 일반적으로는 block/wakeup 방식이 더 좋다.
💡
사실 길이보다는 얼마나 경쟁이 치열한가로 이해하는 것이 올바르다.
경쟁이 치열하다면 block/wakeup이, 별로 치열하지 않다면 busy-wait이 더 좋을 수가 있다는 것이다.
Two Types of Semaphores
Counting semaphore
➳ 도메인이 0 이상인 임의의 정수값
➳ 주로 resource counting에 사용
Binary semaphore (= mutex)
➳ 0 또는 1 값만 가질 수 있는 semaphore
➳ 주로 mutual exclusion (lock / unlock)에 사용
Semaphore는 프로그래밍을 조금만 잘 못 해도 큰 문제가 생길 수가 있다.
바로 Deadlock과 Starvation이다.
다음은 이러한 Semaphore의 문제점에 대해서 알아보자 !
Deadlock and Starvation
Deadlock
" 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이다. "
e.g. S와 Q가 1로 초기화된 semaphore라고 하자.
세마포어 변수 S와 Q, 두 자원 모두 있어야만 작업이 가능한 경우를 생각해 보자. S와 Q를 동시에 얻어서 작업을 하고, 동시에 반납해야 한다. P0가 S를 얻은 상태에서 P1에게 CPU를 빼앗겼다고 해보자. 그리고 P1은 Q를 획득했다. P0은 S를 획득하였고, P1은 Q를 획득한 것이다. 이 상태에서 P1은 S가 없으므로 계속 실행할 수가 없다. P0으로 넘어가도 S는 있지만 Q가 없으므로 실행이 불가하다. 이처럼 각각 프로세스가 자원을 하나씩만 가져서 영원히 그 아래로는 수행이 안 되는 문제점이 발생할 수 있다.
프로세스는 자원을 획득하면 무조건 일을 다 끝난 다음에서야 자원을 내놓는다는 점이 바로 이 문제의 근본적인 이유이다. 다른 프로세스가 또 다른 자원을 가지고 있으니 어차피 자원을 가지고 있어 봐야 소용이 없다고 생각해 자원을 내어준다면 애초에 이런 문제가 안 생길 것이다.
Starvation
" indefinite blocking이다. 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상이다. "
만약 아래 그림처럼 획득하는 자원의 순서를 동일하게 정해준다면 위와 같은 문제가 발생하지 않을 것이다 !
Classical Problems of Synchronization
공유 데이터에 접근 시 발생하는 전통적인 동기화의 문제점 세 가지에 대해서 알아보자.
해결하는 방안은 Semaphore를 이용한다.
➳ Bounded-Buffer Problem (Producer-Consumer Problem)
➳ Readers-Writers Problem
➳ Dining-Philosophers Problem
1. Bounded-Buffer Problem (Producer-Consumer Problem)
Bounded-Buffer는 크기가 유한한 공유 buffer이다. 즉, 여러 프로세스가 동시에 접근할 수 있다. 여기서 프로세스는 producer(생산자) process와 consumer(소비자) process, 두 가지로 나뉜다. 이 프로세스들이 공유 buffer에서 하는 일은 무엇일까 ? producer process는 데이터를 만들어서 buffer에 넣어주는 역할을 한다. consumer process는 데이터를 꺼내가는 역할을 한다.
producer process는 빈 버퍼를 발견하고, '여기에다 데이터를 넣어야지 !' 생각하는 찰나 CPU를 빼앗겼다고 해보자. 다른 producer process도 똑같이 빈 버퍼를 발견하고 똑같은 생각을 한다면 데이터 유실의 문제가 생긴다.
이 문제를 해결하기 위해서는 공유 buffer를 접근할 때 lock을 걸고, 작업이 끝나면 lock을 풀어주는 방법을 사용한다. 이는 consumer process도 마찬가지이다.
✨ Shared data
- buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)
- resource count ➳ Need integer semaphore (남은 full/empty buffer의 수 표시)
코드로 보면 다음과 같다.
mutex는 lock을 거는 세마포어 변수이다.
2. Readers-Writers Problem
➳ 한 process가 DB에 write 중일 때 다른 process가 접근하면 안 된다.
➳ read는 동시에 여럿이 해도 된다.
➳ solution
• Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해 준다.
• Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
• 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
• Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
✨ Shared data
- DB 자체
- readcount ➳ 현재 DB에 접근 중인 Reader의 수
✨ Synchronization variables
- mutex ➳ 공유 변수 readcount를 접근하는 코드 (critical section)의 mutual exclusion 보장을 위해 사용한다.
- db ➳ Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할이다. (역시 lock을 걸고 푼다.)
코드는 다음 그림과 같다.
이는 starvation이 발생할 수 있다는 문제가 있다. Reader가 계속 들어온다면 아무리 Writer가 먼저 도착했어도 영영 기다려야 할 수가 있다. 어떻게 하면 이 문제를 해결할 수 있을까 ? 일정 시간 내 접근한 Reader만 접근이 가능하도록 하고, 일정 시간 후에는 기다리고 있는 Writer에게도 접근 기회를 주는 방식으로 starvation 문제를 해결할 수 있다.
3. Dining-Philosophers Problem
젓가락 다섯 짝이 공유 데이터이고, 다섯 명의 철학자는 굶어 죽으면 안 된다. 철학자는 생각을 할 수도 있고, 밥을 먹을 수도 있다. 만약 모든 철학자가 동시에 배고파서 동시에 왼쪽에 있는 젓가락 한 짝을 집었다면 오른쪽에 있는 나머지 한 짝을 모두 집을 수 없으므로 모두 밥을 먹을 수 없는 사태가 발생한다.
❓ 문제점
➳ 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락 한 짝을 집어버린 경우 Deadlock 가능성이 있다.
❗ 해결 방안
➳ 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
➳ 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
➳ 비대칭 : 짝수 (홀수) 철학자는 왼쪽 (오른쪽) 젓가락부터 집도록 한다. 획득하는 자원의 순서를 정해주는 것이다.
두 번째 해결 방안을 코드로 살펴보면 다음과 같다.
Monitor 방안으로 Dining-Philosophers Problem를 해결한 코드를 semaphore 방안으로 고스란히 옮긴 것이다.
Semaphore의 문제점
➳ 코딩하기 힘들다.
➳ 정확성 (correctness)의 입증이 어렵다.
➳ 자발적 협력 (voluntary cooperation)이 필요하다.
➳ 한 번의 실수가 모든 시스템에 치명적인 영향을 준다.
그렇다면 좀 더 쉽게 프로세스 동기화를 할 수는 없을까 ?
이 생각으로부터 나온 방안이 바로 Monitor이다.
Monitor
동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
Monitor는 공유 데이터 동시 접근에 대한 모든 책임을 진다. 하지만 Semaphore는 그렇지 않다. Semaphore는 P 연산이나 V 연산을 통해 원자적으로 자원의 남은 개수를 count 하는 연산을 제공한다. 실제 동기화 문제는 프로그래머의 몫이다. 공유 데이터에 접근하기 전에 프로그래머가 lock을 걸고, 접근이 끝나면 프로그래머가 lock을 풀어주어야 한다.
Monitor는 공유 데이터에 대한 접근은 오직 Monitor 안에 정의된 함수를 통해서만 접근이 가능하도록 하고, Monitor 안에서 active 하게 실행되는 프로세스는 하나로 제한한다. 따라서 프로그래머는 lock을 걸 필요 없이 Monitor 안에 있는 코드로 데이터에 접근하도록 하면 알아서 동기화가 된다.
아래는 Monitor를 추상적으로 그린 것이다.
하나의 프로세스가 이미 Monitor 안에서 작업을 수행 중이라면 접근을 하고 싶어 하는 또 다른 프로세스는 Queue에 줄을 서서 기다리도록 한다.
Monitor의 특징
➳ 모니터 내에서는 한 번에 하나의 프로세스만이 활동이 가능하다.
➳ 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.
➳ 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용한다. ( condition x, y; )
➳ condition variable은 wait와signal연산에 의해서만 접근이 가능하다.
x.wait();
➳ x.wait()를 invoke 한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.
x.signal();
➳ x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다. suspend 된 프로세스가 없으면 아무 일도 일어나지 않는다.
condition variable은 semaphore 변수와 비슷한 역할을 한다. 자원의 여분이 있을 때에는 그냥 수행을 하도록 하고, 없을 때에는 잠들도록 한다. 잠들도록 한다는 것은 queue에 줄을 세워 blocked 상태로 만든다는 의미이다. x라는 자원이 없다면 x.wait()를 호출하고, condition variable은 x라는 queue에 줄을 서서 잠들도록 하는 역할을 담당한다. 만약 x라는 자원을 다 사용하고 반환하는 프로세스가 있다면 x.signal()을 호출해 혹시 x 자원의 여분이 없어 잠들어있는 프로세스가 있다면 깨우도록 한다.
이제 Monitor를 사용해 동기화 문제를 해결하는 예를 살펴보자 !
앞서 나온 Semaphore를 사용한 예와 비교하면 이해하는데 도움이 된다.
1. Bounded-Buffer Problem (Producer-Consumer Problem)
full.signal()을 호출했을 때, 만약 줄 서서 기다리고 있는 프로세스가 없다면 그냥 아무 일도 안 일어난다.
2. Dining-Philosophers Problem
공유 데이터인 다섯 짝의 젓가락과 다섯 명의 철학자 상태 변수가 monitor 함수 안에 있다. condition variable은 철학자가 밥을 먹고자 할 때 젓가락 두 짝을 모두 잡을 수 있는 상태라면 밥을 먹도록 하고, 그렇지 않은 상태라면 큐에 잠들어서 기다리도록 한다.
