토론해봐요 ~시스템면접 + 프로그래밍 코딩 면접질문들 몇몇 더 올려봅니다 ~

Sailor_moon의 이미지

안녕하세요 , KLDP 는 정말 대단하신 분들이 많은것 같습니다.

사실 전에 올렸던 면접질문에서 저는 인피니 밴드 에 대한 것 자체를
몰랐었거든요 . 이번 질문은 제가 모아뒀던 것들 중 하나인데, 학부때 배우는 OS 수업과 관련있지 않나 싶네요.
몇몇 사이트에서 가져온것도 있는데 , 답이 없는것들이 꽤 되는군요. 명확한 정답보다는
의견을 물어보는 문제들 같습니다.

운영체제 메모리 할당 / 페이징좀 공부 열심히 해둘걸 하는 느낌이 팍팍듭니다.
유명한 공룡책을 한번 정독해야할까요 ?

======이하 질문입니다======

Grid computing 이란 세계 곳곳의 컴퓨팅 기기(nodes)를 하나의 초고속 네트워크로 연결하여 신경망화한 하나의 클라우드 컴퓨팅입니다. 시중에 있는 컴퓨터들같은 디바이스를 한데로 묶는 이런 시스템의 로직을 디자인 해본다고 가정해봅시다.

1. Memory allocation 에 대하여 질문해보고자 합니다.

만약에 프로세스가 현재 실행되고 있는 node 즉 컴퓨터의 용량을 넘어서는 메모리 할당을 요구한다면, 프로세스를 다른 node 의 메모리에 할당하겠는가 ? 아니면 기억장치 (local disk)의 swapping 에 의존하겠는가 ?
퍼포먼스를 고려하여 대답해보시오. 스왑을 한다면 , 스왑을 어떻게 구현할 것인가 ?

2. 이런 시스템에서, 두개의 스레드를 갖는 프로세스가 있다면, 각각의 쓰레드는 각각의 물리적인 노드에서 실행되는것이 좋은가 ? 아니면 꼭 그렇지만은 않은가 ? 의견을 말해보시오.

3. 만약에 두개의 프로세스들이 메모리 페이지를 커뮤니케이션을 위해 셰어한다면 ?

4. 이런 시, 프로세스가 실행중인 노드에서가 아닌 다른 노드(컴퓨터)에 있는 리소스 가 더 현재 프로세스의 니즈(needs)에 적합할때
프로세스를 다른 노드로 어떻게 재배치 (relocate) 할 수 있는지 설명해보시오.

=========================

1번 같은 경우는 그냥 혼자쓰는 시스템이라면 , 저같으면 절대로 느린 기억장치를 스왑하진 않을것 같습니다만 , 이경우에는
밴드의 속도에 따라 다르지 않을까 추측해 봤습니다. 그런데 스왑을 어떻게 구현하냐니 ;;; 이거 뭘 물어보는거죠 ?

2번은 아무래도 물리적 노드에서 실행되는게 좋지않을까요 ? 각각의 물리적인 메모리를 할당받는게 아닌지 ... ?

이후에도 화이트 보드 혹은 google doc 을 이용하여 code 를 짜는 문제들이 나왔습니다. 어려웠던 문제들을 되살려보면

1. 3D 에서의 Convex-hull 을 어떻게 구할 수 있는지 수도코드를 작성하시오.
2. 100만이 넘는 고객정보를 가진 데이터베이스가 있는데, 이중에서 특정 middle name 을 가진 사람만을 골라내려고 한다.
Time complexity 를 고려하여 수도 코드 작성 //이건 나중에 해시를 왜 쓰려고 하는지 꼬치꼬치 캐묻는 바람에 힘들었네요

3. 배열이 있는데 , 이 배열 안에는 1 ~n 까지의 숫자가 들어있습니다. n은 32000 에 근접합니다. 배열 안에는 중복된 수가 존재할 수도 있으면 n 이 정확히 얼마이지는 모릅니다. 오직 4 킬로 바이트의 메모리만 사용가능한데, 자 , 중복되는 원소들을 어떻게 모두 프린트 아웃 해낼 수 있을까요 ?

프로그래밍 파트는 ...
1번은 전 도저히 모르겠습니다. 그래픽스 할때 배웠던 3차원의 3x3 매트릭스에 1 dummy 값들을 넣어서 4 x4 로 만든 후 R^2 차원으로 선형변환한다면 어떻게 2D Convex hull 찾는 식으로 찾아낼 수 있지 않을까 생각해봤지만 도저히 안나오더군요.

혹시 미국쪽 취업 준비하시는분 계신가요 ? 참고로 1번은 W주에 있는 M사 , 위의 운영체제 질문과 , 프로그래밍 3번은 C 주에 있는 g 사 문제였습니다.

태훈의 이미지

1.
원격 노드에서 메모리를 할당하는 비용(Network bound)과 로컬 디스크에 스왑하는 비용(I/O bound)에 따라 다를 것 같습니다. 이기종 그리드 컴퓨팅이면 원격 노드에서 메모리 할당 비용을 측정하는 별도의 메커니즘이 필요할 것이고(PPBE등 활용), 비용에 따라 스왑을 하거나 원격 노드에 할당하거나 해야겠네요. 인피니밴드등을 이용해서 분산 시스템을 처음부터 구성 하는것이면 스와핑하지 않고 모두 원격 노드에서 할당하는게 좋아 보입니다.
(Keyword> DSM(Distributed Shared Memory)

스왑은 LRU 정책에 따라 디스크로 내려 보낼 페이지를 선택하고, 스왑된 페이지는 x86 같은 경우에는 present 필드를 false로 설정 해 놓고 해당 페이지를 쓰려고 하면 '페이지 폴트'가 발생하고 페이지 폴트 핸들러에서 스와핑된 페이지를 실제 메모리에 로드하는 방식으로 구현했던 것 같네요. (자료를 찾아보지 않아서 명확하진 않습니다. 생각나는대로...)

2.
같은 프로세스이면 같은 노드에서 실행해야 할 것 같습니다. 동일한 프로세스에서 쓰레드가 다른 노드에서 실행된다면 각 쓰레드는 동일한 메모리 영역(가상 메모리)을 사용하고 있는데, 이것을 분산 시켜버리면 메모리 관리 시스템이 너무 복잡 해 집니다.

3.
공유 메모리 매커니즘(API)을 제공하고, 이 API는 내부적으로 각 프로세스의 페이지 테이블을 수정하여 동일한 메모리를 사용 할 수 있게 하면 되겠습니다. 분산 시스템을 지원하기 위해서는 별도의 공유 메모리 테이블이 하나 필요할 것 같네요.

4.
프로세스 이주(migration)에 대한 것이네요. 우선 현재 프로세스 동작을 중단시키면서 문맥을 저장하고, 저장된 문맥과 프로세스가 사용하는 메모리를 네트웍으로 전송합니다. 수신 노드에서는 먼저 새로운 프로세스를 할당하고 수신된 프로세스의 문맥과 메모리 영역으로 초기화 한 뒤에 스케쥴러에 포함시켜서 수행 합니다.

이게 개념상으로는 간단해 보이지만 실제 구현을 하려면 꽤나 복잡하므로, 프로세스 이주를 수월하게 하기 위해서 커널단에 JVM을 내장하고 각 프로세스를 java 클래스 단위로 관리하면 어떨까라는 생각을 하고 있습니다. 분산 시스템을 고려하다보니 java가 분산 시스템에 용이하도록 설계가 되어 있더군요.
(Keyword> Process Migration, Thread Migration)

Just do it!

Sailor_moon의 이미지

혹시 ... 무슨 일 하시는지 여쭤봐도 될까요 ? 정말 잘 알고 계시네요 ... 현업에 계신거같아서 ...

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

태훈의 이미지

백숩니다. :-)

Just do it!

Sailor_moon의 이미지

우선 답변감사드립니다.
한가지 잘 이해가 안되는 부분이 있스니다.
처음부터 구상하는 것이라면 , 스와핑 대신, 다른 노드들에 할당하는게 더 좋은 이유가 무엇인가요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

태훈의 이미지

인피니밴드등으로 별도의 분산 시스템을 구성하였다면, 분산 I/O(네트웍을 이용한)을 하는 일정한 비용을 예측 할 수가 있습니다.
예측된 분산 I/O 비용이 스와핑하는 비용보다 적을 것이라는 가정을 했습니다.

이기종 그리드 컴퓨팅과 같은 경우에는 분산 I/O 비용 예측이 어려우므로 별도의 비용 측정 매커니즘이 필요하다는 생각을 한 것이구요.

Just do it!

Sailor_moon의 이미지

자꾸 궁금증이 생기는데 , 혹 한가지만 더 지룬 드려도 될까요 ? 이러한 분산처리 / 그리드 컴퓨팅 시스템에서,
그럼 현재 실행되고 있는 프로세스를 다른 노드를 옮기는 시간적인 코스트가 얼마나 될까요 ? 대략적으로라도 ...
단순히 네트워크의 속도에 달려있을것 같진 않은데요 ...

그리고 ....
와 .. 혹시 이쪽으로 종사하셨나요 ? 이렇게까지 자세히 알고계시다니 놀랍습니다. 전 학부를 전공했지만 , 이런 시스템 쪽은 완전 백지거든요.

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

태훈의 이미지

단순히 생각하면 (문맥 저장 비용) + (문맥 전송 비용) + (문맥 로드 비용) 이 되겠네요.

각 비용은 시스템마다 다를테니 예측하는건 의미가 없다고 생각합니다. 제가 제안했던 PPBE(Packet-Pair Bandwidth Estimation)은 종단(End-to-End)간에 대역폭을 측정하는 매커니즘이므로 이것을 이용하면 세가지 비용 중에서 (문맥 전송 비용)은 측정 할 수 있습니다. DOS(Distributed Operating System) 분야에서 프로세스 이주를 좀 더 효율적으로 하기 위해서 여러가지 문맥 전송 방식이 제안되었습니다. 문맥 전송 방식이 어떤 종류가 있는지 찾아보려면 책을 봐야하는데 현재 PC방이라 좀 힘들것 같네요.

ps. 현재 DINOS(DIstributed Node Operating System)라는 DOS(Distributed Operating System)를 고려한 OS를 만들고 있습니다. 현재하고 있는 프로젝트와 관련된 내용이라 평소에 이런 고민을 많이 합니다.

Just do it!

Sailor_moon의 이미지

혹 대학원생이신가요 ? 어떤 프로젝트를 하시길래 OS 를 직접 만드시는지 신기합니다 .. 학부수준인 저로써는 ...

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

태훈의 이미지

석사 학위를 가지고 있긴합니다. :-)

DOS는 대학원때 지도교수님께 배웠었죠.

Just do it!

Sailor_moon의 이미지

정말 큰 도움이 되었습니다. 혹 이런 쪽으로 공부해보거나 연구해볼만한 책이 있으면 추천좀 해 주실수 있으신지요 ?

-------------------------------------------
정의의 이름으로 널 ! 용서하지 않겠다 !!

태훈의 이미지

아마존에서 "Distributed Operating System" 키워드로 검색 해 보시고, 평점 좋은 책을 추천합니다.

제가 배운 교재가 어떤건지 모르겠네요. (지금 PC방이라...)

Just do it!

kws4679의 이미지

1.

convexHull(Node a, Node b, Node c){
makeTriangle(a, b, c);
n = findNormalVector(a, b, c);

for each Nodes{
if(!(newNodes = find points with Minimum inner product sharing at least two points not already found points(a,b,c, n, Points))) return Points;
Points.add(newNodes);

convexHull(newNodes);
}
}

익명 사용자의 이미지

음... 이것도 재밌는 주제네요.
저는 전산 전공자가 아니라서 구현은 관심 없지만, Distribute Shared Memory라는 주제로 90년대에만 한 100개 쯤 진행되었던 프로젝트입니다.
인피니밴드를 이용해서 Distributed Shared Memory를 구현하는 것보다는 Swapping을 하면서 I/O를 높이는 쪽으로 장치(SSD 등)등을 사용하는 것이 더 낫지 않을까 싶군요.

그리고 프로세스를 마이그레이션하는 것도 역시 이스라엘애들이 90년대 말에 열심해 해서 제품 출시까지 나갔다고 했으나, 역시... 현실화는 별로였었지요.
구현방법에 대해서도 아마 그 프로젝트가 MOSES 였던가 뭐 비슷한 걸로 기억하는데, 2000년대 초반에 그리드 프로젝트 하면서 좋은 주제로 많이 이용되다가 역시 현실화에서는 실패했었지요.

왜냐, 그거 만들어서 완성되는 동안 메모리 가격이 폭락해서 그냥 더 꽂으면 되니까요.

오늘도 비슷한 내용으로 이야기를 했는데, 시스템 구축을 주로하는 입장에서 보면 좋은 알고리즘을 개발해서 구현하는데 들어가는 시간동안 장비의 성능개선과 가격하락이 훨씬 더 빨라져서, 그냥 전통적인 방식에서 장비를 추가하는 것이 더 유리한 형태로 가버리는 것이 현실이지요.

ScaMPI 였던가(기억이 가물가물) 하는것이 Infiniband + Distributed Memory를 구현해준다고 제품을 팔고 있더군요.

ydhoney의 이미지

1. 메모리는 디립다 꼽습니다. 이 말은 농담이 아닙니다. 1TB급 메모리를 장착한 시스템 수십대를 운용한 적도 있습니다. 물론 256GB정도 되는 소용량(?) 메모리 시스템은 수천대 되죠 당연히;;

2. 같은 operation에 대한 분산인지 job operating으로 분리할 수 있는지에 따라서 다르겠죠. 일단 MulthThreading가능하다는 가정하에 Job 특성에 따라서 다르다고 말씀드리는게 낫겠습니다..만 3번의 질문을 포함하자면 분산하면 안되는 구조의 어플리케이션으로 판단됩니다. -_-a Operation이 뭐냐, 분산 가능하냐 등을 구분하는게 핵심입니다. 분산 안되면 단일시스템 파워 올리는게 훨씬 좋습니다. Cell B/E나 GPU Computing을 포함해서라도 말이죠.

4. 이건 사실 된다고 말은 하지만 Job Batch/Operating 쪽에서 보면 안타깝게도 그냥 해당 Job을 날리거나 일부 Processing이 덜 처리된 시스템의 Job만 별도로 처음부터 다시 돌리는 경우가 많습니다. 비용이 너무 과다합니다. 그 비용을 지불할 의사가 있을 정도로 Job Operating Performance가 중요하더라도, Performance 증가가 가져오는 이득이 비용보다 많다는 보장을 하는것이 불가능하므로 기업 입장에서는 시스템/인프라를 지르지 않게 되고, Job Operator 인력이 해당 부분을 커버하게 됩니다.

뭐 질문하시는 분..면접관? 의 의도에 맞는 대답은 아닐지도 모르지만 현업에서 보자면 위와 같은 조건을 가집니다. 질문에 환상적으로 대답해야지! 혹은 제안서를 끝내주게 써주겠어! 하는것과 현실세계의 Operating이 다른 경우가 많습니다 안타깝게도. 많은 설계자들이 제대로 된 실무를 모르니 환상적인 설계를 하지만 현실은 크게 달라지지 않죠. 심지어 이 어설픈 설계자들은 비용이 깎였을 때 구현되는 사항이 달라지는 것에 대해서도 고려하지 않는단 말입니다. ㅎㅎ

익명 사용자의 이미지

면접시험 볼려고 미리 자료수집 하는 것처럼 보입니다.