크래프톤 정글 WEEK07 DAY56 - PintOS(Alarm Clock - priority) / 7주차 퀴즈 리뷰

📆2024.3.5

1. PintOS (Alarm Clock - Priority)
2. 7주차 퀴즈
3. 백준

 

PintOS (Alarm Clock - Priority)

 

어제 PintOS Project 1 Alarm Clock Priority 제외하고 다 구현해서 오늘 Priority 부분을 구현하였다.

우리가 생각한 Priority의 조건은 "만일 같은 sleep_time을 가진 스레드들이 sleep_list에 있을 때(동시에 깨어나는 스레드들이 여러 개 일 때) 우선순위로 구분하여 우선순위가 높은 스레드 먼저 ready_list에 넣어준다" 고 생각하였다.

 

그래서 greater_list라는 우선순위를 담을 큐를 만들고 thread_wakeup 함수 부분에서 먼저 sleep_list 맨 앞에 있는 스레드를 pop한 sleep_pop_front_thread를 구조체를 만들어줬다.

우선순위가 높은 순서대로 정렬해야하니까 내림차순으로 정렬해주는 priority_greater bool형 함수를 만들어서 정렬시키고 

greater_list에 삽입해주었다.

마지막으로 greater_list가 비기 전까지 ready_list에 넣어주었다.

 

+ 추가한 코드

void
thread_wakeup(int64_t ticks)
{
	if(list_empty(&sleep_list))
		return;

	enum intr_level old_level;
	
	//sleep_list의 시작 지점에 대한 iterator를 반환하여 해당 요소를 struct thread로 캐스팅
	struct thread *sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);

	struct thread *sleep_pop_front_thread;

	while(sleep_front_thread->wakeup_tick <= ticks)
	{
		old_level = intr_disable();
		sleep_front_thread->status = THREAD_READY;
        
		/* alarm clock - priority */
		sleep_pop_front_thread = list_entry(list_pop_front(&sleep_list), struct thread, elem);
		list_insert_ordered(&greater_list, &sleep_pop_front_thread->elem , (list_less_func *) &priorty_greater, NULL);
		
		// list_push_back(&ready_list, list_pop_front(&sleep_list));
		sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);	
		intr_set_level(old_level);
	}

	while(!list_empty(&greater_list))
	{
		old_level = intr_disable();
		list_push_back(&ready_list, list_pop_front(&greater_list));
		intr_set_level(old_level);
	}
}

 

bool
priorty_greater(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct thread *ta = list_entry(a, struct thread, elem);
	struct thread *tb = list_entry(b, struct thread, elem);
	return ta->priority > tb->priority;
}

 

이게 되나..?? 했는데 pass tests/threads/alarm-priority ...  

 

 

7주차 퀴즈 

 

[1] 응용 프로그램을 구현할 때 multiprocess와 multithread 중 하나를 선택하는 기준은 어떤 것이 있는지 몇 가지 제시하세요.

 

안정성 VS 자원 사용

시스템의 안정성이 매우 중요한 경우, 멀티프로세스가 선호된다. 리소스가 제한적인 환경에서는 멀티 스레드가 더 효율적일 수 있다.

- 다중 프로세스는 독립적인 주소 공간을 가지기 때문에 메모리 침범 및 데이터 오염이 발생할 가능성이 적다.

- 다중 스레드는 하나의 스레드가 예외를 발생시키면 프로세스 전체가 영향을 받을 수 있으므로 안정성이 상대적으로 낮다.

 

구현의 복잡성

스레드는 공유 메모리로 인해 동기화 문제가 복잡해질 수 있으므로, 개발자의 동시성 제어에 대한 이해도가 중요하다

- 멀티 프로세스의 각각의 프로세스는 운영 체제에 의해 분리되므로 실패한 프로세스를 다시 시작하는 것이 비교적 간단하다.

 

응답 시간

멀티 스레드는 컨텍스트 스위칭이 빠르기 때문에, 더 빠른 응답 시간을 요구하는 경우 유리할 수 있다.

 

플랫폼 및 언어 지원

사용 중인 프로그래밍 언어나 플랫폼이 멀티스레드 또는 멀티프로세스 중 어느 쪽을 더 잘 지원하는지도 중요한 요소가 될 수 있다.

 

-> 안정성이 중요한 시스템에서는 다중 프로세스, 빠른 응답 및 처리가 필요한 웹 서버와 같은 응용 프로그램에서는 다중 스레드가 적합하다.

 

---> 완전히 틀려버린 문제..

 

 

[2]  데드락을 해결하기 위한 전략을 두 가지 이상 설명하시오.

 

* 데드락 : 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못하여 다음 처리를 못하는 상태

 

데드락 해결 전략

 

1. 데드락 예방 (Deadlock Prevetion)

이 접근법은 데드락 발생을 원천적으로 차단한다. 데드락이 발생하는 네 가지 필수 조건(상호 배제, 점유와 대기, 비선점, 순환 대기) 중 적어도 하나를 제거함으로써 데드락을 방지한다. 예를 들어 비선점 조건을 제거하면 어떤 리소스도 필요할 때 다른 프로세스에 의해 선점될 수 있으며, 이는 데드락을 방지할 수 있다.

 

2. 데드락 회피 (Deadlock Avoidance)

데드락 회피는 시스템이 데드락 상태로 진입하는 것을 회피하는 전력이다. 이를 위해 시스템은 리소스 할당 결정 시 데드락의 가능성을 고려한다. 가장 유명한 예는 뱅커스 알고리즘(Banker's Algorithm)으로, 이는 프로세스에 리소스를 할당하기 전에 안전 상태를 유지할 수 있는지 확인한다. 만약 할당으로 인해 데드락이 발생할 위험이 있다면, 리소스는 할당되지 않는다.

 

3. 데드락 탐지 및 회복 (Deadlock Detection and Recovery)

이 전략은 시스템이 데드락을 탐지하고, 이를 해결하기 위한 조치를 취하는 것을 포함한다. 데드락 탐지는 주기적으로 리소스 할당 그래프를 검사하여 순환 대기 조건을 찾는 것으로 이루어질 수 있다. 데드락이 탐지되면, 시스템은 프로세스를 중지하거나 리소스 할당을 콜백하여 데드락을 해결한다.

 

4. 자원의 상호 배제 제거 (Ignoring Mutual Exclusion)

일부 경우에, 리소스의 상호 배제 조건을 제거할 수 있다. 예를 들어 리소스가 복사가 가능하거나 공유가 가능한 경우, 여러 프로세스가 동시에 해당 리소스를 사용할 수 있다. 이러한 방식으로 상호 배제 조건을 제거함으로써 데드락 발생 가능성을 줄일 수 있다.

 

---> 어제 퀴즈 공부하면서 봤던 부분인데 제대로 안봐서 답을 애매하게 적었다.... 다음부터 제대로 하나하나 다 꼼꼼히 봐야겠다

 

 

[3]  Semphore와 Mutex의 특징과 주요 차이점은 무엇인가요?

 

Semaphore는 공유 자원에 대한 접근을 제한하는 데 사용되며, 이는 특정 숫자로 초기화된다. 이 숫자는 동시에 해당 자원에 접근할 수 있는 스레드의 최대 수를 나타낸다. Semaphore는 스레드가 자원을 사용할 때마다 감소하고, 자원을 해제할 때마다 증가한다.

 

Mutex(Mutual Exclusion)는 공유 자원에 대한 접근을 단일 스레드에게만 허용한다. 이는 주로 데이터의 무결성을 보호하기 위해 사용되며, 한 번에 하나의 스레드만이 공유 자원에 접근할 수 있도록 한다. Mutex는 소유권 개념을 가지고 있어, 잠금을 건 스레드만이 잠금을 해제할 수 있다.

 

이 두 가지 메커니즘은 모두 동시성을 관리하고 데이터 무결성을 보장하는 데 필수적이지만, 사용되는 상황과 목적에 따라 선택된다. Mutex는 보다 엄격한 제어가 필요할 때, Semaphore는 여러 자원에 대한 동시 접근을 허용할 때, 특히 Counting Semaphore는 자원의 수량이 제한되어 있을 때 유용하다.

 

-> 세마포어는 임계영역에 접근할 수 있는 수가 1개 이상이고, 뮤텍스는 임계영역에 접근할 수 있는 수가 1개이다.

 

--> 답 적음. 코치님이 원하는 답변은 세마포어와 뮤텍스틑 공유 자원에 대한 접근을 조율하기 위한 동기화 기법인데, 세마포어는 임계영역에 접근할 수 있는 수가 1개 이상이고, 뮤텍스는 임계영역에 접근할 수 있는 수가 1개이다. 인거 같다. 비스무리하게 적음

 

 

[4] 다음 ANSI C 프로그램에서 출력되는 내용은 무엇인가?

#include <stdio.h>

int f(int x, int *py, int **ppz)
{
    int y, z;
    **ppz += 1;
    z = **ppz;
    *py += 2;
    y = *py;
    x += 3;
    return x + y + z;
 }
 
 int main()
 {
     int c , *b , **a;
     c = 4;
     b = &c;
     a = &b;
     printf("&d\n", f(c , b, a));
     return 0;
 }

 

c = 4 , b = 4, a = 4

f 함수 내에서 **ppz (즉, c) 를 1증가 시키면 c의 값은 5가 된다. -> z = 5

*py(즉, c)를 2 증가시키면 , c의 값은 7이 된다. -> y = 7

x (c의 복사본) 을 3 증가시키면, x의 값은 7이 된다.  ->  x = 7

 

7 + 7 + 5 = 19 

 

---> 참고로 이 부분에서 실수를 해서 7+ 7+ 7 = 21의 답을 제출.... 나 왜그랬냐고오오 

 

 

[5]  다음 C코드에서 발생하는 메모리 누수를 찾고, 해결 방안을 제시하시오.

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int data;
    char *description;
} item;

item* create_item(int data, const char *desc) {
    item *new_item = (item *)malloc(sizeof(item));
    if (new_item == NULL) {
    	return NULL;
    }
    new_item->data = data;
    new_item->description = (char *)malloc(strlen(desc) + 1);
    strcpy(new_item->description, desc);
    return new_item;	
}

int main() {
    item *myItem = create_item(5, "Test Item");
    printf("Item: %d, Description: %s\n",
    myItem->data, myItem->description);
    // 다른 작업 수행
    free(myItem); // 메모리 해제
    return 0;	
}

 

create_item 함수에서 item 구조체와 description 문자열에 대한 메모리를 할당한다. 그러나 main 함수에서는 오직 item 구조체에 대해서만 메모리를 해제하고 있고, description 필드에 대한 메모리 해제가 누락되어 있다. 올바른 메모리 해제를 위해 main 함수에서 free(myItem->description); 을 추가해야 한다.

 

---> 하 이 부분도 틀려버림 제대로 맞은 문제가 없네요...반성합시다...

 

 

백준 1012 유기농 배추

 

bfs 문제다. 오랜만에 bfs 문제 풀어서 감을 잃어버렸다. 생각보다 어렵지 않은 문제인데 감을 잃어버린 탓에 구현에서 우당탕탕 결국 gpt 도움으로 수정하면서 풀었다. 

내일부터 bfs 다시 시작이다..

from collections import deque
import sys
input = sys.stdin.readline

dx = [0, 1, 0, -1]
dy = [1, 0,-1, 0]

def bfs(x,y):
    q = deque()
    q.append((x,y))
    baechu[x][y] = 0
    
    while q:
        x_ , y_ = q.popleft()

        for i in range(4):
            nx = x_ + dx[i]
            ny = y_ + dy[i]
            
            if nx < 0 or nx >= M or ny < 0 or ny >= N or baechu[nx][ny] == 0:
                continue
            
            if baechu[nx][ny] ==1:
                q.append((nx,ny))
                baechu[nx][ny] = 0
     
T = int(input())
for _ in range(T):
    M,N,K = map(int,input().split())
    baechu = [[0] * N for _ in range(M)]
    
    for _ in range(K):
        x,y = map(int,input().split())
        baechu[x][y] = 1
    
    cnt = 0
    for i in range(M):
        for j in range(N):
            if baechu[i][j] == 1:
                  bfs(i,j)
                  cnt +=1
    print(cnt)

 

.

.

.

 

요즘 너무 피곤하고 확실히 PintOS 들어가니까 머리가 넘 아파서 컨디션이 좋지 않은 것 같다.

예전같지 않아... 컨디션 조절을 잘 해야겠다ㅠㅠ