[인프런 워밍업 클럽 스터디 3기] CS - 1주차 발자국
1주차 학습내용
운영체제
운영체제
폴링 방식: CPU가 주기적으로 I/O 장치를 확인하여 작업 완료 여부를 확인하는 방식.
인터럽트 방식: I/O 작업이 완료되면 장치가 CPU에게 신호를 보내 작업 완료를 알리는 방식. CPU는 인터럽트를 받아 ISR을 실행함.
프로세스: 하드디스크에 저장된 프로그램이 메모리에 올라와 실행 중인 상태.
프로세스 구조: 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 구분.
컴파일 과정: C 언어 코드는 전처리 -> 컴파일 -> 링킹을 거쳐 실행 파일로 변환됨.
프로그래밍과 프로세싱
유니 프로그래밍: 하나의 프로세스만 메모리에 올라가며, I/O 작업 중 CPU가 대기하는 방식.
멀티 프로그래밍: 메모리에 여러 프로세스를 올려, I/O 작업 동안 다른 프로세스를 실행함.
멀티 태스킹: CPU가 여러 프로세스를 짧은 시간 동안 교대로 처리하는 방식.
멀티 프로세싱: 여러 CPU를 사용하여 작업을 처리하는 방식.
PCB
프로세스 제어 블록: 각 프로세스의 정보를 저장하는 자료 구조.
구조: 프로세스 ID, 상태, 프로그램 카운터, 레지스터 정보 등을 포함.
프로세스 상태: 생성(NEW) -> 준비(READY) -> 실행(RUNNING) -> 대기(WAITING) -> 종료(TERMINATED).
컨텍스트 스위칭
정의: 실행 중인 프로세스의 상태를 저장하고 다른 프로세스의 상태로 교체하는 작업.
스위칭 이유: CPU 점유 시간 초과, I/O 요청, 인터럽트 발생 등.
스레드
정의: 프로세스 내에서 실행되는 가장 작은 작업 단위.
공유 자원: 스레드는 같은 프로세스 내에서 코드, 데이터, 힙 영역을 공유함.
CPU 스케줄링
FIFO: 먼저 들어온 프로세스를 먼저 처리하는 방식.
SJF: 실행 시간이 짧은 프로세스를 우선 처리하는 방식.
RR: 각 프로세스에 일정 시간씩 CPU를 할당하는 방식.
MLFQ: 우선순위에 따라 다중 큐를 사용하는 방식. 짧은 작업은 낮은 타임 슬라이스를, 긴 작업은 긴 타임 슬라이스를 부여함.
자료구조와 알고리즘
자료구조
데이터를 효율적으로 저장하고 관리하는 방법으로, 다양한 형태의 데이터 처리를 가능하게 함. 예를 들어 배열, 연결 리스트 등이 있음.
배열: 메모리상에서 연속적으로 데이터를 저장하는 구조로, 인덱스를 통해 빠르게 접근 가능함.
연결 리스트: 각 요소가 다음 요소의 주소를 저장해 연결된 구조로, 삽입과 삭제가 용이하지만, 특정 요소에 접근할 때는 순차 탐색이 필요함.
알고리즘
문제를 해결하기 위한 명확한 절차나 규칙의 집합. 자료구조와 결합하여 다양한 문제 해결을 가능하게 함.
시간 복잡도: 알고리즘의 성능을 측정하는 척도로, 입력 크기에 따라 알고리즘이 실행되는 데 걸리는 시간을 빅오(Big-O) 표기법으로 표현함. 예: O(n), O(log n).
스택: LIFO(Last In First Out) 방식으로, 마지막에 삽입된 데이터가 먼저 처리되는 구조. 호출 스택, 되돌리기 기능 등에 사용됨.
큐: FIFO(First In First Out) 방식으로, 먼저 삽입된 데이터가 먼저 처리되는 구조. 작업 큐나 대기열 관리에 사용됨.
덱(Deque): 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 스택과 큐의 기능을 모두 갖춘 구조.
해시테이블
키를 기반으로 값을 빠르게 찾을 수 있는 자료구조. 해시 함수로 키를 계산해 데이터를 저장하고 검색함.
평균적으로 빠른 데이터 접근 속도를 제공하지만, 해시 충돌이나 메모리 사용량 문제가 발생할 수 있음.
Set
중복된 데이터를 허용하지 않는 자료구조로, 각 요소가 유일한 값을 가짐.
중복을 제거하거나 유일한 항목만 저장하는 경우에 자주 사용됨.
1주차 미션
운영체제
while(true){
wait(1); // 1초 멈춤
bool isActivated = checkSkillActivated(); // 체크
}
위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?
현재 코드는 1초마다 checkSkillActivated()
함수를 호출해 스킬 사용 여부를 확인하는 폴링 방식입니다. 이 방식은 일정 주기로 계속 CPU를 사용하기 때문에 리소스 낭비가 발생할 수 있습니다.
이를 해결하기 위해 인터럽트 방식을 사용할 수 있습니다. 인터럽트 방식에서는 스킬이 사용된 시점에만 인터럽트 신호가 발생하고, CPU는 이 신호를 받아 즉시 인터럽트 서비스 루틴을 실행하여 필요한 작업을 처리합니다. 이렇게 하면 CPU는 스킬이 사용될 때만 작업을 처리하므로, 불필요한 주기적인 체크를 없애고 성능을 향상시킬 수 있습니다.
2.프로그램과 프로세스가 어떻게 다른가요?
프로그램은 정적인 개념으로, 디스크와 같은 보조 기억 장치에 저장된 실행되지 않은 코드의 집합입니다. 이 파일 자체는 CPU에서 실행되지 않으며, 단지 명령어들이 기록된 상태입니다. 반면, 프로세스는 동적인 개념으로, 실행 중인 프로그램을 의미합니다. 프로세스는 메모리에 로드되어 CPU에 의해 실제로 실행되고 있는 상태이며, 이를 통해 메모리, CPU 스케줄링 등의 자원을 할당받아 작업을 수행합니다. 즉, 프로그램은 실행되지 않은 코드이고, 프로세스는 실행 중인 프로그램입니다.
멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?
멀티프로그래밍은 단일 CPU 환경에서 여러 프로그램이 동시에 메모리에 적재되어 번갈아가며 실행되는 방식입니다. 이 방식은 CPU가 효율적으로 작업을 처리할 수 있도록 다양한 프로세스를 동시에 실행할 수 있게 하지만, 한 번에 하나의 프로세스만 CPU에서 실제로 실행됩니다. 반면, 멀티프로세싱은 다중 CPU 환경을 사용하는 방식으로, 여러 CPU 코어가 동시에 여러 프로세스를 병렬로 실행할 수 있습니다. 이를 통해 시스템은 더 높은 처리 성능을 발휘하게 됩니다.
운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?
운영체제는 PCB (Process Control Block)이라는 구조체를 사용해 각 프로세스를 관리합니다. PCB는 프로세스에 관한 다양한 정보를 포함하고 있으며, 프로세스의 상태, 프로세스 ID, 프로그램 카운터, CPU 레지스터 값, 메모리 할당 정보 등을 저장합니다. PCB는 각 프로세스가 CPU에서 실행되는 동안의 문맥(context)을 저장하고, 프로세스가 CPU를 할당받을 때 이전의 상태를 복원하는 데 사용됩니다. 프로세스가 생성되거나 종료될 때 PCB가 추가되거나 제거되며, PCB 간의 관계는 연결 리스트와 같은 자료구조로 관리됩니다.
컨텍스트 스위칭이란 뭔가요?
컨텍스트 스위칭은 CPU가 한 프로세스에서 다른 프로세스로 작업을 전환할 때 발생하는 과정입니다. 현재 실행 중인 프로세스의 상태(프로그램 카운터, CPU 레지스터 값 등)를 PCB에 저장한 후, 다음으로 실행할 프로세스의 상태를 PCB에서 가져와 복원하는 과정입니다. 이로 인해 CPU는 새로운 프로세스를 계속해서 실행할 수 있습니다. 컨텍스트 스위칭이 자주 발생하면 시스템 오버헤드가 증가해 성능 저하를 유발할 수 있지만, 이는 멀티태스킹 환경에서 필수적인 과정입니다.
자료구조와 알고리즘
여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.
이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.
저는 HashMap을 사용할 것 같습니다. 이유는 학생의 정보는 학번이나 이름과 같이 고유한 식별자를 기반으로 관리되는 경우가 많기 때문에, 이러한 고유 식별자를 키로 사용하는 HashMap은 효율적입니다. HashMap은 평균적으로 O(1)의 시간복잡도로 데이터를 삽입하고 검색할 수 있기 때문에, 대규모 학생 정보를 빠르게 처리하는 데 적합합니다.
여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.
Queue 자료구조를 선택하겠습니다. 주문을 처리할 때는 FIFO(First-In-First-Out) 방식이 적합합니다. 큐는 먼저 들어온 데이터가 먼저 처리되는 방식으로, 주문이 들어온 순서대로 처리를 보장합니다.
우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.
import { LinkedList } from './LinkedList.mjs';
class Stack {
constructor() {
this.list = new LinkedList();
}
push(data) {
this.list.insertLast(data); // 마지막 인덱스에 삽입
}
pop() {
try {
return this.list.deleteLast(); // 마지막 인덱스에서 삭제
} catch (e) {
return null;
}
}
peek() {
return this.list.getNodeAt(this.list.count - 1); // 마지막 인덱스의 데이터 확인
}
isEmpty() {
return this.list.count === 0;
}
}
export { Stack };
해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력
이름의 각 문자의 ASCII 값을 이용하여 해시값을 계산하고, 이를 해시 테이블의 크기로 나눈 나머지를 반환하여 분산도를 높이는 해시 함수를 작성할 수 있습니다.
public class HashUtil {
public int hashFunction(String name, int tableSize) {
int hashValue = 0;
for (int i = 0; i < name.length(); i++) {
hashValue = (31 * hashValue + name.charAt(i)) % tableSize; // 31은 좋은 해시 계수
}
return hashValue;
}
public static void main(String[] args) {
HashUtil util = new HashUtil();
String name = "이운재";
int tableSize = 100; // 해시 테이블 크기
System.out.println("Hash value of" + name + ":" + util.hashFunction(name, tableSize));
}
}
1주차 미션 회고
이번주에 너무 많은 스케줄들이 몰려서 힘겹게 학습을 따라가느라 버거웠다. 복습도 필요할 거 같고, 다음 주에는 지금의 아쉬운 마음을 동력 삼아서 더 열심히 해나가야겠다.
댓글을 작성해보세요.